Metody odkrywania wiedzy: wykład 11
Odkrywanie reguł asocjacyjnych

Paweł Cichosz

Date: 2001/2002

Wykład jest poświęcony metodom znajdowania reguł asocjacyjnych, opisujących częste współwystępowanie w analizowanych danych pewnych elementów -- w najprostszym ujęciu pewnych wartości atrybutów.

Odkrywanie asocjacji

Algorytmy indukcyjnego uczenia się omawiane dotąd stosowane są do odkrywania wiedzy o klasyfikacji: zależności wybranego atrybutu, traktowanego jako kategoria, od pozostałych atrybutów, pozwalającej na wyznaczanie nieznanej kategorii na podstawie znanych wartości atrybutów dla dowolnych przykładów -- rekordów w bazie danych. Nie zawsze jednak jest to ten rodzaj wiedzy, który może być najbardziej przydatny. Nie zawsze też udaje się taką zależność wyznaczyć z dostateczną dokładnością, a jednocześnie opisać w dostatecznie prosty sposób, aby mogła być faktycznie użyteczna. Innym rodzajem wiedzy, który w takich sytuacjach może być odkrywany, są asocjacje. Są to zależności polegające na (względnie) częstym współwystępowaniu pewnych elementów w analizowanych danych (pewne towary są często kupowane jednocześnie, klienci pewnych firm są często klientami pewnych innych firm). W pewnych zastosowaniach wiedza o asocjacjach może być bardziej użyteczna od wiedzy o klasyfikacji, a też odkrycie takiej wiedzy o praktycznie przydatnej jakości może być łatwiejsze -- chociaż niekoniecznie prostsze obliczeniowo.

Reprezentacja danych i hipotez

Opis przykładów

Nie zmniejszając ogólności rozważań możemy założyć, że interesują nas asocjacje polegające na częstym współwystępowaniu pewnych wartości atrybutów w rekordach bazy danych, czy też -- dalej używając dla wygody terminologii wywodzącej się z maszynowego uczenia się -- pewnych wartości atrybutów przykładów. Wygodnie będzie jednak nie zajmować się wprost atrybutami, lecz tylko ich wartościami. Możemy w szczególności dopuścić, że dla różnych przykładów mogą być częściowo różne zestawy atrybutów lub że niektóre atrybuty dla pewnych przykładów mogą przyjmować nie pojedyncze wartości, lecz wartości będące zbiorami. Chodzi o to, aby wygodnie reprezentować dane dotyczące np. towarów zakupionych przez klienta w ramach jednej transakcji -- dla różnych klientów mogą być to różne liczby towarów. Abstrahując od tego, jak fizycznie tego typu dane są organizowane w relacyjnej bazie danych za pomocą powiązanych odpowiednimi związkami tabel, przyjmiemy, że każdy przykład $x$ jest opisywany za pomocą pewnego zbioru wartości atrybutów $V_x$ (nazywanego krótko zbiorem wartości), nie interesując się tym, ile faktycznie jest tych atrybutów i ile każdy z nich może mieć wartości. Wartości te będziemy traktować jako nominalne, zakładając, że w razie potrzeby zostały uprzednio poddane dyskretyzacji. Przez $\mathbb{V}$ oznaczymy zbiór wszystkich wartości, jakie mogą wystąpić w opisach przykładów z rozważanej dziedziny. Przyjmujemy więc opis przykładów nie za pomocą atrybutów i wartości, jak dotąd, lecz za pomocą wyłącznie wartości, aby uwolnić się od konieczności zakładania czegokolwiek na temat tego, ile jest atrybutów i ile oraz jakich każdy z nich może mieć wartości.

Reguły asocjacyjne

Wiedzę dotyczącą asocjacji reprezentuje się za pomocą reguł asocjacyjnych, które z kolei będziemy opisywać w najbardziej naturalny sposób, zbliżony do opisu przykładów. Przyjmiemy, że każda taka reguła jest strukturą złożoną z dwóch zbiorów wartości, z których pierwszy nazwiemy zbiorem wartości warunkujących, a drugi -- zbiorem wartości warunkowanych. Regułę ze zbiorem wartości warunkujących $Y\subset\mathbb{V}$ i zbiorem wartości warunkowanych $Z\subset\mathbb{V}$ zapiszemy jako:

$$Y \Rightarrow Z$$ (1)

i będziemy ją interpretować jako stwierdzenie, że wartości ze zbioru $Y$ często pociągają za sobą wartości ze zbioru $Z$. Dokładniej, chodzi o stwierdzenie, że w wielu przykładach, w których opisie występują wszystkie wartości ze zbioru $Y$ występują również wszystkie wartości ze zbioru $Z$. Ponieważ przy stosowaniu reguł asocjacyjnych interesuje nas możliwość wnioskowania na podstawie wystąpienia pewnych wartości o prawdopodobnym wystąpieniu innych wartości, będziemy wymagać, aby $Y\cap Z=\emptyset$.

Oczywiście użyte wyżej określenia ,,często'' czy ,,wielu'' są nieprecyzyjne, ale można je sprecyzować przyjmując stosowne liczbowe kryteria. W celu sprecyzowanie interpretacji reguł asocjacyjnych określa się dla nich wsparcie i wiarygodność. Aby zapisać ich definicję przyjmijmy oznaczenie $P_V$ dla podzbioru dowolnego zbioru przykładów $P$ zawierającego te i tylko te przykłady, których opisy zawierają wszystkie wartości z $V$:

$$P_V = \{x\in P \;\vert\; V\subset V_x\}$$ (2)

Wówczas wsparcie reguły $Y\Rightarrow Z$ na zbiorze przykładów $P$ jest określone następująco:

$$s_P(Y\Rightarrow Z) = \frac{\vert P_{Y\cup Z}\vert}{\vert P\vert}$$ (3)

czyli jako stosunek liczby przykładów z $P$, w których opisach występują wszystkie wartości z obu zbiorów $Y$ i $Z$ do liczby wszystkich przykładów w $P$. Z kolei wiarygodność reguły $Y\Rightarrow Z$ na zbiorze przykładów $P$ definiuje się jako:

$$f_P(Y\Rightarrow Z) = \frac{\vert P_{Y\cup Z}\vert}{\vert P_Y\vert}$$ (4)

czyli jako stosunek liczby przykładów z $P$ w których opisach występują wszystkie wartości z obu zbiorów do liczby tych, w których występują wszystkie wartości tylko ze zbioru wartości warunkujących. Wsparcie mówi o tym, jak często w rozważanym zbiorze przykładów występuje sytuacja opisana przez regułę, a wiarygodność o tym, jak często wystąpienie wartości warunkujących faktycznie pociąga za sobą wystąpienie wartości warunkowanych.

Wsparcie określa się także dla pojedynczych zbiorów wartości. Wsparcie zbioru wartości $V$ na zbiorze przykładów $P$ jest definiowane w następujący oczywisty sposób:

$$s_P(V) = \frac{\vert P_V\vert}{\vert P\vert}$$ (5)

a więc jest to częstość jednoczesnego występowania wszystkich wartości ze zbioru $V$ dla przykładów ze zbioru $P$.

Generowanie reguł asocjacyjnych

Typowe podejście do problemu generowania reguł asocjacyjnych na podstawie zbioru danych (przykładów) polega na rozbiciu go na dwa podproblemy:

1. znalezienie wszystkich zbiorów wartości często występujących w zbiorze przykładów,
2. dla każdej pary zbiorów wartości, z których jeden jest podzbiorem drugiego, utworzenie odpowiedniej reguły asocjacyjnej.

Pierwszy problem polega na znalezieniu wszystkich zbiorów wartości, których wsparcie przekracza zadane minimum. Takie zbiory są nazywane częstymi zbiorami wartości. Efektywne znajdowanie częstych zbiorów wartości stanowi główną trudność przy generowaniu reguł asocjacyjnych.

Tworzenie reguł na podstawie częstych zbiorów

Drugi problem, czyli tworzenie na podstawie znalezionych częstych zbiorów reguł asocjacyjnych, jest w istocie bardzo prosty. Dla dowolnych dwóch częstych zbiorów wartości $Y$ i $Z$, mających wymagane minimalne wsparcie, dla których $Y\subset Z$, może być utworzona reguła asocjacyjna

$$Y \Rightarrow Z-Y$$ (6)

dla której wsparcie i wiarygodność na dowolnym zbiorze przykładów $P$ można bezpośrednio określić na podstawie wsparcia zbiorów $Y$ i $Z$ na $P$ w następujący sposób:

$$s_P(Y\Rightarrow Z-Y) ={} s_P(Z)$$ (7)

$$f_P(Y\Rightarrow Z-Y) ={} \frac{s_P(Z)}{s_P(Z)}$$ (8)

uwzględniając, że $Z\cup(Z-Y)=Z$. Skoro więc wsparcie zbioru $Z$ przekracza zadaną wartość minimalną, przekracza ją także wsparcie tej reguły. Jeśli dodatkowo jej wiarygodność jest dostatecznie duża, to może zostać zaakceptowana.

Znajdowanie częstych zbiorów

Pozostaje określić sposób rozwiązania pierwszego, kluczowego podproblemu, znajdowania częstych zbiorów wartości. Rozpatrywanie wszystkich możliwych zbiorów wartości (wszystkich podzbiorów $\mathbb{V}$) i wyznaczanie ich wsparcia jest oczywiście nie do przyjęcia -- zwłaszcza że wyznaczenie wsparcia dla każdego zbioru wartości może być operacją bardzo kosztowną ze względu na duży na ogół rozmiar zbioru danych. Wynika stąd konieczność pewnej heurystycznej strategii przeszukiwania przestrzeni zbiorów wartości w poszukiwaniu tych, które występują w dostatecznie dużej liczbie przykładów.

Jedna z możliwych strategii opiera się na obserwacji, że każdy zbiór wartości, zawierający się w pewnym częstym zbiorze wartości, także jest częstym zbiorem. W związku z tym rozpoczynając od częstych zbiorów jednoelementowych generuje ona w systematyczny sposób ich nadzbiory, każdorazowo zawierające jedną dodatkową wartość, gdyż tylko nadzbiory częstych zbiorów mogą być częstymi zbiorami. Realizacją tej koncepcji jest algorytm Apriori, którego szkic przedstawiony jest poniżej.

Dla każdego $i=1,2,\dots$ algorytm wyznacza zbiór $S_i$ złożony z częstych zbiorów zawierających dokładnie $i$ wartości, które osiągają minimalne wymagane wsparcie $\theta_s$. Zbiór $S_1$ powstaje przez wybranie spełniających ten warunek pojedynczych wartości ze zbioru wszystkich wartości $\mathbb{V}$. W kolejnych iteracjach dla $i=2,3,\dots$ zbiór $S_i$ jest wyznaczany na podstawie zbioru $S_{i-1}$ w trzech krokach. W pierwszym z nich jest tworzony zbiór tymczasowy $S_i'$ złożony ze zbiorów wartości powstałych przez odpowiednie połączenie pewnych par zbiorów z $S_{i-1}$. Następnie w celu ograniczenia zakresu przeszukiwania pewne zbiory są eliminowane, co daje w wyniku zbiór $S_i''$. Wreszcie z $S_i''$ do $S_i$ są wybierane zbiory wartości, których wsparcie wynosi co najmniej $\theta_s$. Można się spodziewać, że dla pewnego $i$ uzyskamy $S_i=\emptyset$, czyli nie zostanie znaleziony żaden $i$-elementowy zbiór wartości o dostatecznie dużym wsparciu. Jest to naturalne kryterium stopu dla tego algorytmu.

Operacja $\textit{połączenie}$, która tworzy zbiór $S_i'$ na podstawie zbioru $S_{i-1}$, generuje $i$-elementowe zbiory wartości łącząc wszystkie takie pary $(i-1)$-elementowych częstych zbiorów, które mają $i-2$ wspólnych elementów i różnią się tylko jedną wartością. Połączony zbiór zawiera wówczas te $i-2$ wspólne wartości oraz dwie różne wartości z każdego z łączonych zbiorów. Zatem z połączenia $(i-1)$-elementowych zbiorów:

$$\{v_1,v_2,\dots,v_{i-2},v'_{i-1}\}$$ (9)

$$\{v_1,v_2,\dots,v_{i-2},v''_{i-1}\}$$ (10)

powstaje $i$-elementowy zbiór:

$$\{v1,v2,\dots,v_{i-2},v'_{i-1},v''_{i-1}\}$$ (11)

Operacja $\textit{przycięcie}$ przekształca zbiór $S_i'$ w zbiór $S_i''$ przez eliminację pewnej liczby zbiorów wartości najmniej obiecujących z punktu widzenia celu przeszukiwania, jakim jest znalezienie częstych zbiorów. Ma to na celu jak największe ograniczenie liczby zbiorów wartości, dla których musi być wyznaczone wsparcie, a tym samym utrzymanie kosztów obliczeniowych algorytmu w rozsądnych granicach. W związku z tym elementami zbioru $S_i''$ stają się takie i tylko takie zbiory wartości z $S_i'$, dla których ich wszystkie $(i-1)$-elementowe podzbiory należą do $S_{i-1}$. W ten sposób jest stosowana podana wcześniej heurystyka, zgodnie z którą częstym zbiorem może być tylko taki zbiór, którego każdy podzbiór jest także częstym zbiorem.

Zagadnienia praktyczne

Przedstawiony algorytm odkrywania reguł asocjacyjnych uchodzi za standardowy, ale są znane jego różne modyfikacje. Zmierzają one do poprawienia efektywności obliczeniowej lub uzyskania reguł asocjacyjnych nieco innego rodzaju.

Dla dużych zbiorów danych, a właśnie w takich zazwyczaj poszukuje się asocjacji, generowanie reguł asocjacyjnych jest bardzo kosztowne. Liczba rozpatrywanych potencjalnych częstych zbiorów silnie zależy od zadanego minimalnego wsparcia i zbyt mała wartość łatwo może ,,zadławić'' algorytm nadmiarem obliczeń. Rozsądną strategią jest raczej rozpoczynanie od dużego minimalnego wsparcia i -- jeśli liczba uzyskanych reguł asocjacyjnych okaże się zbyt mała -- ostrożne zmniejszanie go.

Określanie wsparcia zbiorów wartości wymaga zliczania wszystkich przykładów, w których opisie występują określone wartości atrybutów, a to z kolei wymaga intensywnego dostępu do przetwarzanego zbioru danych, który może nie mieścić się w całości w pamięci operacyjnej i być przechowywany w pamięci zewnętrznej, w bazie danych lub pliku. Aby związany z tym koszt zminimalizować, może się niekiedy opłacać wyznaczanie w jednym przebiego częstych zbiorów wartości o dwóch kolejnych rozmiarach. Polegałoby to na tym, aby na podstawie zbioru $S_i$ wyznaczyć od razu nie tylko zbiór $S_{i+1}''$, ale od razu potem na jego podstawie zbiór $S_{i+2}''$, a dopiero później, w jednym przebiegu przez zbiór danych, obliczyć wsparcie wszystkich elementów tych zbiorów i uzyskać zbiory $S_{i+1}$ i $S_{i+2}$ przez pozostawienie tylko tych, które osiągają minimalne zadane wsparcie. W ten sposób w $S_{i+2}''$ znajdzie się więcej niż to konieczne zbiorów wartości (gdyż nie będą wyznaczane na podstawie $S_{i+1}$, lecz na podstawie $S_{i+1}''$, ale oszczędność w dostępie do pamięci zewnętrznej może to zrekompensować.

Jeden z pomysłów na poprawę efektywności polega na zrównolegleniu algorytmu i uruchamianiu go w środowisku wieloprocesorowym. Istnieje odpowiadnia równoległa wersja algorytmu Apriori.

Z innych rodzajów reguł asocjacyjnych, które można by generować za pomocą nieco zmodyfikowanych algorytmów, najbardziej interesujące są temporalne reguły acocjacyjne, w których uwzględnia się czas, z którego pochodzą przykłady (np. czas dokonania transakcji zakupu) i poszukuje nie tyle wartości współwystępujących, co następujących w krótkiej sekwencji czasowej. W tym przypadku analizie podlegają nie pojedyncze transakcje, lecz sekwencje transakcji.

Literatura

1. Cichosz, P. Systemy uczące się. WNT, 2000. (Podrozdział 10.3).
2. Witten, I. A., Frank, E. Data Mining. Morgan Kaufmann, 2000. (Podrozdział 4.5).

About this document ...

Metody odkrywania wiedzy: wykład 11
Odkrywanie reguł asocjacyjnych

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -no_navigation mow-w11.tex

The translation was initiated by Pawel Cichosz on 2004-02-12