Algorytm Apriori w prostym języku angielskim?

9

Czytam artykuł wiki o Apriori. Mam problem ze zrozumieniem śliwek i kroku dołączenia. Czy ktoś może mi wyjaśnić, jak działa algorytm Apriori w prostych słowach (tak, że nowicjusz taki jak ja może łatwo zrozumieć)?

Dobrze będzie, jeśli ktoś objaśni proces zaangażowany w to krok po kroku.

Mrówki
źródło
Być może zainteresuje Cię moja implementacja języka Python .
Martin Thoma,

Odpowiedzi:

11

Artykuł w Wikipedii nie jest szczególnie imponujący. Te slajdy mogą okazać się bardziej pomocne: 1 , 2 , 3 .

Na każdym poziomie masz zestawy elementów, które są częste (mają wystarczające wsparcie). kk

Na następnym poziomie zestawy elementów + które należy wziąć pod uwagę, muszą mieć właściwość, że każdy z ich podzbiorów musi być częsty (mieć wystarczające wsparcie). Jest to właściwość apriori : każdy podzbiór częstych zestawów przedmiotów musi być częsty.k1

Jeśli więc wiesz na poziomie 2, że zestawy , , i są jedynymi zestawami z wystarczającą obsługą, to na poziomie 3 łączysz je ze sobą, aby wyprodukować , , i ale musisz tylko rozważyć dalej: pozostałe mają podzbiory z niewystarczającym wsparciem (takie jak lub ).{1,2)}{1,3)}{1,5}{3),5}{1,2),3)}{1,2),5}{1,3),5}{2),3),5}{1,3),5}{2),3)}{2),5}

Henz
źródło
2

Algorytm Apriori jest algorytmem eksploracji reguł asocjacyjnych wykorzystywanym w eksploracji danych. Służy do znajdowania częstego zestawu pozycji wśród podanej liczby transakcji.

Składa się zasadniczo z dwóch kroków

  1. Self-Join
  2. Przycinanie

Powtarzając te kroki k razy, gdzie k jest liczbą przedmiotów, w ostatniej iteracji otrzymujesz częste zestawy przedmiotów zawierające k przedmiotów.

Spójrz tutaj na bardzo proste wyjaśnienie ze szczegółowym przykładem http://nikhilvithlani.blogspot.com/2012/03/apriori-algorithm-for-data-mining-made.html .

Ma proste wyjaśnienie bez skomplikowanych równań.

użytkownik1239631
źródło
2
Zostawiłem to powiadomienie, ponieważ zwykle lepiej jest przedstawić streszczenie głównych punktów, które chcesz podkreślić, niż link do bloga bez dalszych wyjaśnień. Ponadto celem tej witryny jest zbudowanie zbioru kompetentnych odpowiedzi na określone pytania, przy minimalnym uzależnieniu od wiszących lub ulotnych linków. Jeśli nie możesz zagwarantować, że powyższy link będzie nadal istniał za 10 lat, powiedzmy, zdecydowanie zachęcam do streszczenia jego głównych punktów w niniejszej odpowiedzi.
chl
1

Apriori zwykłym angielskim.

Priori stosuje iteracyjnego podejścia znane jako poziom mądry wyszukiwania, w którym K-itemsets stosuje się w celu zbadania (k + 1) -itemsets . Po pierwsze, zestaw częstych zestawów 1-elementowych można znaleźć, skanując bazę danych w celu zgromadzenia liczby każdego elementu i zbierając elementy, które spełniają minimalne wsparcie. Powstały zestaw jest oznaczony jako L1 . Następnie L1 służy do znalezienia L2 , zestawu częstych 2-itemsetów , który jest używany do znalezienia L3, i tak dalej, aż nie będzie już więcej częstych zestawów k-item . Znalezienie każdego Lk wymaga jednego pełnego skanowania bazy danych.

Na końcu pojawi się wiele zestawów przedmiotów, które są w zasadzie nazywane regułami asocjacji . Aby wybrać interesujące reguły z zestawu wszystkich możliwych reguł, stosuje się różne środki ograniczające , takie jak wsparcie i zaufanie .

Warunki i terminologie

  • 1-itemset oznacza {a}, {b}, {c}
  • 2-itemset oznacza {a, b}, {d, d}, {a, c}
  • Zestawy K oznaczają {i1, i2, i3, ... ik}, {j1, j2, j3, .... jk}

Krok dołączania: oznacza, że ​​1-elementowy zestaw umożliwia samodzielne połączenie się ze sobą, aby wygenerować 2-elementowy zestaw.

Krok przycinania: tutaj zestaw wynikowy z łączenia jest filtrowany z minimalnym progiem wsparcia.

zestaw liczności: wynikowy zestaw z kroku przycinania.

Wsparcie = liczba transkacji zawierających „a” i „b” / całkowita liczba transakcji.

Wsparcie => supp (a, b) => p (a U b)

Przekonany = liczba transakcji zawierających „a” i „b” / nr transakcji zawierającej „a”.

Pewność => con (a, b) ==> P (b | a) nic oprócz prawdopodobieństwa warunkowego.

shakthydoss
źródło