Metoda asocjacyjna

Metoda asocjacyjna (odkrywania asocjacji) jest jedną z metod eksploracji danych stosowaną w uczeniu maszynowym, bioinformatyce, eksploracji danych oraz w produkcji ciągłej.

Polega ona na analizie zbioru zmiennych w celu znalezienia występujących w nim powtarzających się zależności. Rezultatem tej analizy są reguły asocjacyjne oraz odpowiednie parametry. W odróżnieniu od wyszukiwania sekwencji, metody asocjacyjne zazwyczaj nie uwzględniają kolejności towarów ani w ramach transakcji, ani w transakcjach. W 1991 Piatetsky-Shapiro opisuje analizę i prezentację silnych reguł odkrytych podczas analiz baz danych za pomocą miar ciekawości (measures of interestingness), na bazie tej koncepcji w 1993 Rakesh Agrawal, Tomasz Imieliński i Arun Swami zastosowali reguły asocjacyjne w celu wykrycia prawidłowości między produktami w dużych transakcjach rejestrowanych przez kasy (point-of-sale)w supermarketach. Takie dane służą jako podstawa strategii cenowej, oraz rozlokowania produktów. Na podstawie danych transakcyjnych mogą powstaną reguły asocjacyjne:

Przykładowo : $\{\mathrm {makaron,oregano,pomidory} \}\Rightarrow \{\mathrm {spaghetti} \}$

Po zakupie pomidorów i oregano, klient prawdopodobnie również zakupi makaron, dlatego optymalnym rozwiązaniem byłaby lokalizacja tych produktów blisko siebie. Celem metod asocjacyjnych jest próba naśladownictwa cech ludzkiego mózgu i możliwości asocjacji abstrakcyjnej z nowych nieskategoryzowanych danych przez maszynę, przy założeniu wystarczająco dużego zestawu danych.

Definicja

Bazując na definicji Agrawala, Imielińskiego, Swamiego [3] problem określania reguł asocjacyjnych definiowany jest jako: Niech$I=\{i_{1},i_{2},\ldots ,i_{n}\}$ będzie zbiorem $n$atrybutów binarnych nazywanych elementami.

Niech $D=\{t_{1},t_{2},\ldots ,t_{m}\}$ będzie zbiorem transakcji nazywanych bazą danych.

Każda transakcja w $D$ma unikalny identyfikator transakcji i zawiera podzbiór elementów w $I$. Reguła jest zdefiniowana jako implikacja formuły:$X\Rightarrow Y$, gdzie $X,Y\subseteq I$.

Reguła jest zdefiniowana tylko pomiędzy zestawem a pojedynczym elementem $X\Rightarrow i_{j}$ dla $i_{j}\in I$.

Każda reguła składa się z dwóch różnych zestawów przedmiotów, znanych również jako zestaw danych (itemsets)

$X$ i $Y$, gdzie $X$ jest nazywane “poprzednikiem” lub “left-hand-side” (LHS) i $Y$sekwencją lub “right-side-side” (RHS). Aby zilustrować te pojęcia, używamy przykładu

supermarketów. Zestaw przedmiotów to$I=\{\mathrm {mleko,chleb,maslo,piwo,pieluchy} \}$ i w tabeli przedstawiono małą bazę danych zawierającą pozycje, gdzie w każdym wpisie wartość 1 oznacza obecność towaru w odpowiedniej transakcji, a wartość 0 oznacza brak pozycji w tej transakcji.

Przykładową regułą dla supermarketu może być $\{\mathrm {maslo,chleb} \}\Rightarrow \{\mathrm {mleko} \}$oznacza, że przy zakupie masła i chleba klienci kupują również mleko.

W zastosowaniach praktycznych reguła wymaga wsparcia kilkuset transakcji, zanim będzie można ją uznać za statystycznie istotną, a zestawy danych często zawierają tysiące lub miliony transakcji.

Wskaźniki reguł

Wsparcie: zbioru jest definiowane jako względna częstotliwość danych transakcji zawierający tę grupę. ]

$\mathrm {supp} (X\Rightarrow Y)={\frac {\mathrm {supp} (X\cup Y)}{N}}$,gdzie N jest sumą elementów zbioru.Ponadto, ${\textstyle {\text{supp}}(X\cup Y)}$definiuje wsparcie dla zestawu elementów. Odpowiada to bezwzględnej częstotliwości ilości pozycji w danych całkowitych. W tym momencie używamy sumy dwóch stron reguł ${\textstyle X\cup Y}$aby określić wszystkie elementy danych całkowitych, które zawierają zarówno zestaw elementów zbioru ${\textstyle X}$ oraz ${\textstyle Y}$.

Zaufanie: względna częstotliwość przykładów, w których reguła jest prawidłowa.

$\mathrm {confidence} (X\Rightarrow Y)={\frac {\mathrm {supp} (X\cup Y)}{\mathrm {supp} (X)}}$

Przyrost (lift): Przyrost wskazuje, jak duża wartość ufności dla reguły przekraczającej oczekiwaną wartość, więc pokazuje ogólne znaczenie reguły.

$\mathrm {lift} (X\Rightarrow Y)={\frac {\mathrm {supp} (X\cup Y)}{\mathrm {supp} (X)\times \mathrm {supp} (Y)}}$, z zastrzeżeniem:

${\begin{aligned}{\text{lift}}(X\Rightarrow Y)>1&\rightarrow X{\text{ und }}Y{\text{ są pozytywnie skorelowane}}\\{\text{lift}}(X\Rightarrow Y)<1&\rightarrow X{\text{ und }}Y{\text{ są negatywnie skorelowane}}\\{\text{lift}}(X\Rightarrow Y)=1&\rightarrow X{\text{ und }}Y{\text{ są niezależne}}\end{aligned}}$

Opis procesu

Reguły asocjacyjne muszą spełnić określone przez użytkownika minimalne wsparcie i minimalną pewność określoną przez użytkownika w tym samym czasie. Generowanie reguły asocjacyjnej zwykle dzieli się na dwa osobne etapy:

Minimalny próg wsparcia jest stosowany, aby znaleźć wszystkie częste zestawy przedmiotów w bazie danych. Minimalne ograniczenie zaufania jest stosowane do tych częstych zestawów przedmiotów w celu utworzenia reguł.

Znalezienie wszystkich częstych zestawów przedmiotów w bazie danych jest trudne, ponieważ wymaga przeszukiwania wszystkich możliwych zestawów przedmiotów (kombinacji produktów). Zbiorem możliwych zestawów przedmiotów jest zbiór potęgowy $I$I i ma rozmiar$2^{n}-1$ (z wyłączeniem pustego zestawu, który nie jest prawidłowym zbiorem). Chociaż rozmiar zestawu rośnie wykładniczo w liczbie pozycji $n$ w $I$ efektywne wyszukiwanie jest możliwe przy użyciu właściwości zamknięcia w dół wsparcia (zwanego także antymonotoniczność ), która gwarantuje, że w przypadku częstego zestawu przedmiotów wszystkie jego podzbiory są również częste, a zatem nieczęsty zestaw przedmiotów może być podzbiorem częstego zestawu przedmiotów. Wykorzystując tę właściwość, wydajne algorytmy mogą znaleźć wszystkie częste zestawy przedmiotów.

Algorytmy

Istnieje kilka algorytmów, które wykonują wyszukiwania reguł asocjacyjnych w bazach danych. Oto kilka przykładów:

• Apriori
• Partition
• Eclat
• FP-Growth