Nauka reguł asocjacyjnych - Association rule learning

Uczenie reguł asocjacyjnych to oparta na regułach metoda uczenia maszynowego służąca do odkrywania interesujących relacji między zmiennymi w dużych bazach danych. Ma na celu zidentyfikowanie silnych reguł odkrytych w bazach danych przy użyciu pewnych miar zainteresowania.

Opiera się na koncepcji silnych zasad, Rakesh Agrawal , Tomasz Imieliński i Arun Swami wprowadził do odkrywania reguł asocjacyjnych prawidłowości między produktami w danych transakcyjnych wielkoskalowych nagranych przez punkt w miejscu sprzedaży (POS) w supermarketach. Na przykład reguła zawarta w danych sprzedażowych supermarketu wskazywałaby, że jeśli klient kupuje razem cebulę i ziemniaki, prawdopodobnie kupi również mięso do hamburgerów. Takie informacje mogą służyć jako podstawa do podejmowania decyzji o działaniach marketingowych, takich jak np. ceny promocyjne czy lokowanie produktów .

Oprócz powyższego przykładu z analizy koszyka rynkowego, reguły asocjacji są obecnie stosowane w wielu obszarach aplikacji, w tym w eksploracji wykorzystania sieci Web , wykrywaniu włamań , ciągłej produkcji i bioinformatyce . W przeciwieństwie do eksploracji sekwencji , uczenie się reguł asocjacji zazwyczaj nie uwzględnia kolejności elementów ani w ramach transakcji, ani między transakcjami.

Definicja

Przykładowa baza danych z 5 transakcjami i 5 pozycjami
Identyfikator transakcji mleko chleb masło piwo pieluchy
1 1 1 0 0 0
2 0 0 1 0 0
3 0 0 0 1 1
4 1 1 1 0 0
5 0 1 0 0 0

Zgodnie z pierwotną definicją Agrawala, Imielińskiego, Swamiego problem kopania reguł asocjacyjnych definiuje się jako:

Niech będzie zbiorem atrybutów binarnych zwanych elementami .

Niech będzie zbiorem transakcji zwanym bazą danych .

Każda transakcja w ma unikalny identyfikator transakcji i zawiera podzbiór pozycji w .

Zasada jest zdefiniowana jako pośrednio w postaci:

, gdzie .

W Agrawal, Imieliński, Swami reguła jest zdefiniowana tylko pomiędzy zbiorem a pojedynczym przedmiotem, dla .

Każda reguła składa się z dwóch różnych zestawów przedmiotów, znany również jako itemsets , i , gdzie jest nazywany poprzednik lub lewej stronie (LHS) i konsekwentna lub prawostronną boczną (RHS).

Aby zilustrować pojęcia, posłużymy się małym przykładem z domeny supermarketu. Zbiór pozycji to i w tabeli pokazana jest niewielka baza danych zawierająca pozycje, gdzie w każdym wpisie wartość 1 oznacza obecność pozycji w odpowiedniej transakcji, a wartość 0 oznacza brak pozycji w tej transakcji transakcja.

Przykładową zasadą dla supermarketu może być to, że jeśli kupowane są masło i chleb, klienci kupują również mleko.

Uwaga: ten przykład jest bardzo mały. W praktycznych zastosowaniach reguła wymaga obsługi kilkuset transakcji, zanim zostanie uznana za statystycznie istotną, a zbiory danych często zawierają tysiące lub miliony transakcji.

Przydatne koncepcje

Aby wybrać interesujące reguły ze zbioru wszystkich możliwych reguł, stosuje się ograniczenia dotyczące różnych miar istotności i zainteresowania. Najbardziej znanymi ograniczeniami są minimalne progi wsparcia i zaufania.

Niech będą zbiorami pozycji, regułą asocjacji i zbiorem transakcji danej bazy danych.

Wsparcie

Wsparcie wskazuje, jak często zestaw elementów pojawia się w zestawie danych.

Obsługa w odniesieniu do jest zdefiniowana jako odsetek transakcji w zbiorze danych, który zawiera zbiór pozycji . Oznaczając transakcję przez gdzie jest unikalnym identyfikatorem transakcji i jest jej zestawem pozycji, wsparcie można zapisać jako:

W przykładowym zestawie danych zestaw elementów ma wsparcie, ponieważ występuje w 20% wszystkich transakcji (1 z 5 transakcji). Argument z jest zbiorem warunków wstępnych, a zatem staje się bardziej restrykcyjny w miarę wzrostu (zamiast bardziej inkluzywny).

Ponadto zestaw przedmiotów ma wsparcie, które pojawia się również w 20% wszystkich transakcji.

Zaufanie

Zaufanie jest wskaźnikiem tego, jak często zasada jest prawdziwa.

Wartość ufności reguły , w odniesieniu do zbioru transakcji , to odsetek transakcji, które zawierają, który zawiera również .

Zaufanie definiuje się jako:

Np. reguła ma zaufanie do bazy danych, co oznacza, że ​​dla 100% transakcji zawierających masło i pieczywo reguła jest prawidłowa (w 100% przypadków, gdy klient kupuje masło i pieczywo, kupowane jest również mleko).

Zauważ, że oznacza to wsparcie połączenia pozycji w X i Y. Jest to nieco mylące, ponieważ zwykle myślimy w kategoriach prawdopodobieństw zdarzeń, a nie zbiorów pozycji. Możemy przepisać jako prawdopodobieństwo , gdzie i są zdarzeniami, które transakcja zawiera odpowiednio itemset i .

Zatem zaufanie można interpretować jako oszacowanie prawdopodobieństwa warunkowego , prawdopodobieństwa znalezienia RHS reguły w transakcjach pod warunkiem, że transakcje te zawierają również LHS.

Wyciąg

Wyciąg z reguły określa się jako:

lub stosunek obserwowanego wsparcia do oczekiwanego, gdyby X i Y były niezależne .

Na przykład reguła ma windę .

Gdyby reguła miała podwyższenie o 1, oznaczałoby to, że prawdopodobieństwo wystąpienia poprzednika i następnika są od siebie niezależne. Gdy dwa zdarzenia są od siebie niezależne, nie można narysować reguły dotyczącej tych dwóch zdarzeń.

Jeśli wzrost jest > 1, pozwala nam to poznać stopień, w jakim te dwa zdarzenia są od siebie zależne, i czyni te reguły potencjalnie użytecznymi do przewidywania następstwa w przyszłych zbiorach danych.

Jeśli winda jest < 1, oznacza to, że elementy są względem siebie substytucyjne. Oznacza to, że obecność jednego przedmiotu ma negatywny wpływ na obecność drugiego i odwrotnie.

Wartość podnoszenia polega na tym, że uwzględnia zarówno wsparcie reguły, jak i ogólny zestaw danych.

Przekonanie

Przekonanie z reguły definiowana jest jako .

Na przykład reguła ma przekonanie o wartości i może być interpretowana jako iloraz oczekiwanej częstości występowania X bez Y (czyli częstości, dla której reguła dokonuje nieprawidłowej prognozy), jeśli X i Y były niezależne podzielone przez zaobserwowana częstotliwość błędnych prognoz. W tym przykładzie wartość przekonania wynosząca 1,2 pokazuje, że reguła byłaby niepoprawna o 20% częściej (1,2 razy częściej), gdyby związek między X i Y był czysto losowy.

Alternatywne miary ciekawości

Oprócz zaufania zaproponowano inne miary atrakcyjności reguł. Niektóre popularne środki to:

  • Całkowite zaufanie
  • Siła zbiorowa
  • Wpływ

Kilka innych miar jest przedstawionych i porównanych przez Tan et al. i przez Hahslera. Poszukiwanie technik, które mogą modelować to, co użytkownik znał (i wykorzystywanie tych modeli jako miar ciekawości) jest obecnie aktywnym trendem badawczym pod nazwą „Subiektywne zainteresowanie”.

Proces

Siatka częstego zestawu przedmiotów, w której kolor pola wskazuje, ile transakcji zawiera kombinację przedmiotów. Zauważ, że niższe poziomy sieci mogą zawierać co najwyżej minimalną liczbę elementów ich rodziców; np. {ac} może mieć tylko większość pozycji. Nazywa się to właściwością zamykania w dół .

Reguły asocjacji są zwykle wymagane, aby jednocześnie zapewnić minimalną obsługę określoną przez użytkownika i minimalną ufność określoną przez użytkownika. Generowanie reguł asocjacyjnych zwykle dzieli się na dwa oddzielne kroki:

  1. Minimalny próg wsparcia jest stosowany w celu znalezienia wszystkich częstych zestawów elementów w bazie danych.
  2. Minimalne ograniczenie ufności jest stosowane do tych częstych zestawów elementów w celu utworzenia reguł.

Podczas gdy drugi krok jest prosty, pierwszy krok wymaga więcej uwagi.

Znalezienie wszystkich częstych zestawów przedmiotów w bazie danych jest trudne, ponieważ wymaga przeszukiwania wszystkich możliwych zestawów przedmiotów (kombinacji elementów). Zbiór możliwych zestawów przedmiotów jest ustawiony na potęgę i ma rozmiar (z wyłączeniem pustego zestawu, który nie jest prawidłowym zestawem przedmiotów). Chociaż rozmiar zestawu potęg rośnie wykładniczo wraz z liczbą elementów w , możliwe jest wydajne wyszukiwanie przy użyciu właściwości wsparcia zamykania w dół (zwanej również antymonotonicznością ), która gwarantuje, że w przypadku częstego zestawu elementów wszystkie jego podzbiory są również częste. a zatem żaden rzadki zestaw przedmiotów nie może być podzbiorem częstego zestawu przedmiotów. Wykorzystując tę ​​właściwość, wydajne algorytmy (np. Apriori i Eclat) mogą znaleźć wszystkie częste zestawy przedmiotów.

Historia

Koncepcja reguł asocjacyjnych została spopularyzowana przede wszystkim dzięki artykułowi Agrawal i in. z 1993 roku, który według Google Scholar uzyskał ponad 23 790 cytowań według stanu na kwiecień 2021 r. i jest tym samym jednym z najczęściej cytowanych artykułów z dziedziny Data Mining. . Jednak to, co obecnie nazywa się „regułami stowarzyszenia”, zostało wprowadzone już w artykule z 1966 r. na temat GUHA, ogólnej metody eksploracji danych opracowanej przez Petra Hájka i in.

Wczesnym (około 1989) zastosowaniem minimalnego wsparcia i pewności w celu znalezienia wszystkich reguł asocjacji jest struktura modelowania opartego na cechach, która znalazła wszystkie reguły z ograniczeniami zdefiniowanymi przez użytkownika i większymi niż te zdefiniowane przez użytkownika.

Statystycznie poprawne skojarzenia

Jednym z ograniczeń standardowego podejścia do odkrywania asocjacji jest to, że przy przeszukiwaniu ogromnej liczby możliwych asocjacji w celu wyszukania zbiorów elementów, które wydają się być powiązane, istnieje duże ryzyko znalezienia wielu fałszywych asocjacji. Są to kolekcje elementów, które współwystępują z nieoczekiwaną częstotliwością w danych, ale tylko przypadkowo. Załóżmy na przykład, że rozważamy zbiór 10 000 elementów i szukamy reguł zawierających dwa elementy po lewej stronie i 1 element po prawej stronie. Istnieje około 1 000 000 000 000 takich zasad. Jeśli zastosujemy test statystyczny na niezależność z poziomem istotności 0,05, oznacza to, że przy braku związku istnieje tylko 5% szans na zaakceptowanie reguły. Jeśli założymy, że nie ma skojarzeń, powinniśmy mimo wszystko spodziewać się znalezienia 50 000 000 000 reguł. Statystycznie poprawne wykrywanie skojarzeń kontroluje to ryzyko, w większości przypadków zmniejszając ryzyko znalezienia jakichkolwiek fałszywych skojarzeń do poziomu istotności określonego przez użytkownika.

Algorytmy

Zaproponowano wiele algorytmów generowania reguł asocjacyjnych.

Niektóre dobrze znane algorytmy to Apriori , Eclat i FP-Growth, ale wykonują tylko połowę pracy, ponieważ są algorytmami do wyszukiwania częstych zestawów przedmiotów. Kolejny krok należy wykonać po wygenerowaniu reguł z częstych zestawów przedmiotów znalezionych w bazie danych.

Algorytm apriori

Apriori wykorzystuje strategię wyszukiwania wszerz do zliczania obsługiwanych zestawów przedmiotów i używa funkcji generowania kandydatów, która wykorzystuje właściwość obsługi zamykania w dół.

Algorytm Eclat

Eclat (alt. ECLAT, skrót od Equivalence Class Transformation) to algorytm wyszukiwania w głąb oparty na przecięciu zbiorów. Nadaje się zarówno do wykonywania sekwencyjnego, jak i równoległego z właściwościami poprawiającymi lokalizację.

Algorytm wzrostu FP

FP oznacza częsty wzór.

W pierwszym przebiegu algorytm zlicza wystąpienia elementów (par atrybut-wartość) w zbiorze danych transakcji i przechowuje te liczby w „tabeli nagłówkowej”. W drugim przebiegu buduje strukturę drzewa FP, wstawiając transakcje do trie .

Pozycje w każdej transakcji muszą być posortowane w porządku malejącym według ich częstotliwości w zbiorze danych przed wstawieniem, aby drzewo można było szybko przetworzyć. Pozycje w każdej transakcji, które nie spełniają minimalnych wymagań dotyczących pomocy technicznej, są odrzucane. Jeśli wiele transakcji współdzieli najczęściej występujące elementy, drzewo FP zapewnia wysoką kompresję blisko korzenia drzewa.

Rekurencyjne przetwarzanie tej skompresowanej wersji głównego zbioru danych bezpośrednio zwiększa częstość zestawów pozycji, zamiast generowania pozycji kandydujących i testowania ich na całej bazie danych (jak w algorytmie apriori).

Wzrost zaczyna się od dołu tabeli nagłówka, tj. pozycji z najmniejszym wsparciem, odnajdując wszystkie posortowane transakcje, które kończą się na tej pozycji. Zadzwoń do tego przedmiotu .

Tworzone jest nowe drzewo warunkowe, które jest oryginalnym drzewem FP rzutowanym na . Podpory wszystkich węzłów w rzutowanym drzewie są ponownie liczone, a każdy węzeł otrzymuje sumę zliczeń swoich dzieci. Węzły (a tym samym poddrzewa), które nie spełniają minimalnego wsparcia, są przycinane. Rekursywny wzrost kończy się, gdy żadne pojedyncze pozycje pod warunkiem spełnienia minimalnego progu wsparcia. Wynikowe ścieżki od korzenia do będą częstymi zestawami elementów. Po tym kroku przetwarzanie jest kontynuowane z następnym najmniej obsługiwanym elementem nagłówka oryginalnego drzewa FP.

Po zakończeniu procesu rekurencyjnego zostaną znalezione wszystkie częste zestawy przedmiotów i rozpocznie się tworzenie reguł asocjacji.

Inni

ASSOC

Procedura ASSOC jest metodą, która kopalnie dla uogólnionych reguł asocjacyjnych z wykorzystaniem szybkiej Guha bitstrings operacje. Reguły asocjacji wydobywane tą metodą są bardziej ogólne niż te wyprowadzane przez apriori, na przykład „elementy” można łączyć zarówno z koniunkcjami, jak i alternatywami, a relacja między poprzednikiem i następnikiem reguły nie ogranicza się do ustalenia minimalnego poparcia i zaufania, jak w przypadku apriori: można zastosować dowolną kombinację wspieranych miar interesu.

Wyszukiwanie OPUS

OPUS to wydajny algorytm do odkrywania reguł, który w przeciwieństwie do większości alternatyw nie wymaga ograniczeń monotonicznych ani antymonotonicznych, takich jak minimalne wsparcie. Początkowo używany do znajdowania reguł dla ustalonego następnika, został następnie rozszerzony o wyszukiwanie reguł z dowolnym elementem jako następnikiem. Wyszukiwanie OPUS to podstawowa technologia w popularnym systemie wykrywania stowarzyszenia Magnum Opus.

Fabuła

Słynna historia o wydobywaniu zasad stowarzyszenia to historia „piwa i pieluch”. Rzekome badanie zachowań kupujących w supermarketach wykazało, że klienci (przypuszczalnie młodzi mężczyźni), którzy kupują pieluchy, zwykle kupują również piwo. Ta anegdota stała się popularna jako przykład tego, jak można znaleźć nieoczekiwane reguły asocjacji z codziennych danych. Istnieją różne opinie co do tego, jaka część tej historii jest prawdziwa. Daniel Powers mówi:

W 1992 roku Thomas Blischok, kierownik grupy doradczej ds. handlu detalicznego w Teradata , wraz ze swoim personelem przygotowali analizę 1,2 miliona koszyków rynkowych z około 25 drogerii Osco. Zapytania do bazy danych zostały opracowane w celu identyfikacji powinowactw. Analiza „odkryła, że ​​między 17:00 a 19:00 konsumenci kupowali piwo i pieluchy”. Menedżerowie Osco NIE wykorzystywali relacji piwa i pieluch, przesuwając produkty bliżej siebie na półkach.

Inne rodzaje wydobywania reguł stowarzyszeniowych

Multi-Relation Association Rules : Multi-Relation Association Rules (MRAR) to reguły asocjacji, w których każdy element może mieć kilka relacji. Relacje te wskazują na pośredni związek między podmiotami. Rozważmy następujący MRAR gdzie pierwszy element składa się z trzech stosunków żyć w , w pobliżu i wilgotny : „Ci, którzy mieszkają w miejscu, które jest w pobliżu miasto z wilgotnym rodzaju klimatu, a także są młodsze niż 20 -> ich stan zdrowia jest dobry”. Takie reguły asocjacji można wyodrębnić z danych RDBMS lub danych sieci semantycznej.

Uczenie się przez zestaw kontrastów jest formą uczenia się asocjacyjnego. Uczniowie korzystający z zestawu kontrastowego stosują reguły, które znacząco różnią się pod względem ich rozmieszczenia w podzbiorach.

Uczenie się w klasach ważonych to kolejna forma uczenia się asocjacyjnego, w której waga może być przypisana klasom, aby skoncentrować się na konkretnym zagadnieniu dotyczącym konsumenta wyników eksploracji danych.

High-order wzór odkrycie ułatwi zdobycie wysokiego rzędu (polythetic) wzory lub stowarzyszeń zdarzeń, które są nieodłącznym elementem złożonych danych rzeczywistych.

Funkcja wykrywania wzorców K-optymalnych stanowi alternatywę dla standardowego podejścia do uczenia reguł asocjacji, które wymaga częstego pojawiania się każdego wzorca w danych.

Wydobywanie przybliżonych zestawów częstych przedmiotów to zrelaksowana wersja eksploracji zestawów częstych przedmiotów, która pozwala niektórym elementom w niektórych wierszach mieć wartość 0.

Uogólnione zasady asocjacyjne taksonomia hierarchiczna (hierarchia pojęć)

Ilościowe zasady asocjacyjne dane kategoryczne i ilościowe

Interval Data Association Rules np. podział wieku na 5-letnie przedziały przyrostu

Eksploracja wzorców sekwencyjnych wykrywa podsekwencje, które są wspólne dla więcej niż sekwencji minsup w bazie danych sekwencji, w której minsup jest ustawiany przez użytkownika. Sekwencja to uporządkowana lista transakcji.

Subspace Clustering , specyficzny typ danych wielowymiarowych klastrowania , jest w wielu wariantach również oparty na właściwości zamykania w dół dla określonych modeli klastrowania.

Warmr jest dostarczany jako część pakietu do eksploracji danych ACE. Umożliwia uczenie się reguł asocjacyjnych dla reguł relacyjnych pierwszego rzędu.

Zobacz też

Bibliografia

Bibliografie