Metoda asocjacyjna

Metoda asocjacyjna (odkrywania asocjacji) – metoda eksploracji danych stosowana 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{m}\mathrm{a}\mathrm{k}\mathrm{a}\mathrm{r}\mathrm{o}\mathrm{n},\mathrm{o}\mathrm{r}\mathrm{e}\mathrm{g}\mathrm{a}\mathrm{n}\mathrm{o},\mathrm{p}\mathrm{o}\mathrm{m}\mathrm{i}\mathrm{d}\mathrm{o}\mathrm{r}\mathrm{y}\}\Rightarrow \{\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{g}\mathrm{h}\mathrm{e}\mathrm{t}\mathrm{t}\mathrm{i}\}$

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 problem określania reguł asocjacyjnych definiowany jest jako: Niech $I=\{i_1,i_2,\dots ,i_n\}$ będzie zbiorem $n$ atrybutów binarnych nazywanych elementami.

Niech $D=\{t_1,t_2,\dots ,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 gdzie $Y$ jest nazywane sekwencją lub „right-hand-side” (RHS). Aby zilustrować te pojęcia, używamy przykładu

supermarketów. Zestaw przedmiotów to $I=\{\mathrm{m}\mathrm{l}\mathrm{e}\mathrm{k}\mathrm{o},\mathrm{c}\mathrm{h}\mathrm{l}\mathrm{e}\mathrm{b},\mathrm{m}\mathrm{a}\mathrm{s}\mathrm{l}\mathrm{o},\mathrm{p}\mathrm{i}\mathrm{w}\mathrm{o},\mathrm{p}\mathrm{i}\mathrm{e}\mathrm{l}\mathrm{u}\mathrm{c}\mathrm{h}\mathrm{y}\}$ 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{m}\mathrm{a}\mathrm{s}\mathrm{l}\mathrm{o},\mathrm{c}\mathrm{h}\mathrm{l}\mathrm{e}\mathrm{b}\}\Rightarrow \{\mathrm{m}\mathrm{l}\mathrm{e}\mathrm{k}\mathrm{o}\}$ 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{s}\mathrm{u}\mathrm{p}\mathrm{p}(X\Rightarrow Y)=\frac{\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}(X\cup Y)}{N},$ gdzie N jest sumą elementów zbioru. Ponadto, $\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ł $X\cup Y$ aby określić wszystkie elementy danych całkowitych, które zawierają zarówno zestaw elementów zbioru $X$ oraz $Y.$

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

$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{f}\mathrm{i}\mathrm{d}\mathrm{e}\mathrm{n}\mathrm{c}\mathrm{e}(X\Rightarrow Y)=\frac{\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}(X\cup Y)}{\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}(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{l}\mathrm{i}\mathrm{f}\mathrm{t}(X\Rightarrow Y)=\frac{\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}(X\cup Y)}{\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}(X)\times \mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}(Y)},$ z zastrzeżeniem:

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

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ścią), 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
• Eclat
• FP-Growth
• Partition