Metoda asocjacyjna

Metoda asocjacyjna (odkrywania asocjacji) – metoda eksploracji danych stosowana w uczeniu maszynowym, bioinformatyce, eksploracji danych oraz w produkcji ciągłej^[1].

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^[2]. 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^[3]. 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^[4].

Definicja edytuj

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 {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^[3].

Wskaźniki reguł^[5] edytuj

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, ${\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 {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 edytuj

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^[1] edytuj

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

Apriori
Eclat
FP-Growth
Partition

Przypisy edytuj

↑ ^a ^b GrzegorzG. Bryda GrzegorzG., CAQDAS, Data Mining i odkrywanie wiedzy w danych jakościowych, Wydawnictwo Uniwersytetu Łódzkiego, 2014, DOI: 10.18778/7969-549-2.02, ISBN 978-83-7969-549-2 [dostęp 2019-02-15] .
↑ Acta Universitatis Lodziensis. Folia Oeconomica, Uniwersytet Lodzki (University of Lodz), DOI: 10.18778/0208-6018 [dostęp 2019-02-15] .
↑ ^a ^b RakeshR. Agrawal RakeshR., TomaszT. Imieliński TomaszT., ArunA. Swami ArunA., Mining association rules between sets of items in large databases, „Proceedings of the 1993 ACM SIGMOD international conference on Management of data – SIGMOD '93”, Washington, D.C., United States: ACM Press, 1993, s. 207–216, DOI: 10.1145/170035.170072, ISBN 978-0-89791-592-2 [dostęp 2019-02-15] (ang.).
↑ JiaweiJ. Han JiaweiJ. i inni, Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach, „Data Mining and Knowledge Discovery”, 8 (1), 2004, s. 53–87, DOI: 10.1023/b:dami.0000005258.31418.83, ISSN 1384-5810 [dostęp 2019-02-15] .
↑ KlausK. Nordhausen KlausK., The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Second Edition by Trevor Hastie, Robert Tibshirani, Jerome Friedman, „International Statistical Review”, 77 (3), 2009, s. 482–482, DOI: 10.1111/j.1751-5823.2009.00095_18.x, ISSN 0306-7734 [dostęp 2019-02-15] .

[:0-1] GrzegorzG. Bryda GrzegorzG., CAQDAS, Data Mining i odkrywanie wiedzy w danych jakościowych, Wydawnictwo Uniwersytetu Łódzkiego, 2014, DOI: 10.18778/7969-549-2.02, ISBN 978-83-7969-549-2 [dostęp 2019-02-15] .

[2] Acta Universitatis Lodziensis. Folia Oeconomica, Uniwersytet Lodzki (University of Lodz), DOI: 10.18778/0208-6018 [dostęp 2019-02-15] .

[autonazwa1-3] RakeshR. Agrawal RakeshR., TomaszT. Imieliński TomaszT., ArunA. Swami ArunA., Mining association rules between sets of items in large databases, „Proceedings of the 1993 ACM SIGMOD international conference on Management of data – SIGMOD '93”, Washington, D.C., United States: ACM Press, 1993, s. 207–216, DOI: 10.1145/170035.170072, ISBN 978-0-89791-592-2 [dostęp 2019-02-15] (ang.).

[4] JiaweiJ. Han JiaweiJ. i inni, Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach, „Data Mining and Knowledge Discovery”, 8 (1), 2004, s. 53–87, DOI: 10.1023/b:dami.0000005258.31418.83, ISSN 1384-5810 [dostęp 2019-02-15] .

[5] KlausK. Nordhausen KlausK., The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Second Edition by Trevor Hastie, Robert Tibshirani, Jerome Friedman, „International Statistical Review”, 77 (3), 2009, s. 482–482, DOI: 10.1111/j.1751-5823.2009.00095_18.x, ISSN 0306-7734 [dostęp 2019-02-15] .

[1]

[2]

[3]

[4]

[5]