• Wprowadzenie
• Procedury obliczeniowe i terminologia
• Tabelaryczne przedstawienie asocjacji
• Graficzna prezentacja asocjacji
• Interpretacja i porównanie wyników

Wprowadzenie

Opisywane tu techniki służą wykrywaniu asocjacji, czyli powiązań albo skojarzeń pomiędzy konkretnymi wartościami zmiennych kategorialnych, w dużych zbiorach danych. Jest to typowe zadanie różnych projektów data mining , jak również projektów text mining , podkategorii data miningu. Dobra skuteczność tych technik powoduje, że znajdują one zastosowanie na wielu polach działalności biznesowej oraz badawczej. Od analizy preferencji klientów, poprzez wspomaganie zarządzania zasobami ludzkimi, a kończąc, na przykład, na badaniach historii rozwoju języka. Analitycy i badacze wykrywają struktury i zależności ukryte w wielkich zbiorach danych, stwierdzając na przykład, że "klienci nabywający produkt A często kupują też produkt Blub C", albo: "pracownicy zadowoleni z reorganizacji X często krytykują Y, lecz podoba im się pomysł Z". Dzięki zastosowaniu algorytmu a priori (patrz: Agrawal i Swami, 1993; Agrawal i Srikant, 1994; Han i Lakshmanan, 2001; oraz Witten i Frank, 2000), możliwe jest szybkie przetwarzanie ogromnych zasobów danych, w poszukiwaniu wspomnianego typu powiązań, z wykorzystaniem do ich wykrywania, zdefiniowanych wstępnie wartości progowych.

Jak działa technika reguł asocjacji? Użyteczność omawianej techniki najlepiej zilustruje prosty przykład. Przypuśćmy, że zebraliśmy sporo danych z rejestru kasy w dużej księgarni. Wszystkie zakupy zapisane są w bazie danych. Mamy tam tytuły książek zakupionych przez kolejnych klientów, wraz z tytułami nabytych, być może również czasopism, nazwami ewentualnych prezentów itp. Każdy rekord w bazie opisuje zakup dokonany przez jednego klienta, a występować może w nim jedna książka lub wiele książek i innych produktów (może i setka), a produkty te występują w dowolnej kolejności, takiej, w jakiej znalazły się na taśmowym transporterze kasy. Celem analizy będzie znalezienie asocjacji pomiędzy zakupywanymi przez klientów produktami, czyli wspólnego ich występowania w "koszyku" klienta. Pożądana, na przykład, mogłaby być wiedza o tym, jakimi tytułami interesować może się klient, który kupił (lub zamierza kupić) konkretną książkę. Pozwoliłoby to obsłudze zaproponować mu te dodatkowe zakupy. Jak wykorzystywane są wyniki tego typu analiz, możemy zaobserwować dokonując zakupów w internecie, gdzie po wyrażeniu chęci nabycia jakiegoś produktu, są nam sugerowane również produkty podobne, wg zasady "klienci kupujący książkę A, kupują też często tytuł B," i jej podobnych.

Szczególne wymagania analizy. Tabele wielodzielcze , a w szczególności tabele wielokrotnych odpowiedzi można użyć do analizowania danych omawianego tu typu. Natomiast, w przypadku, gdy liczba różnych obiektów (kategorii) jest duża, a dodatkowo nie jest ona znana przed przystąpieniem do analizy, oraz gdy nie jest wstępnie znany stopień podziału, dla ważnych reguł asocjacji, wtedy tabelaryzowanie za pomocą Statystyk podstawowych może być kłopotliwe i praktycznie niewykonalne. Rozważmy ponownie przykład z księgarnią. Po pierwsze, liczba tytułów książek jest praktycznie nieograniczona. Oznacza to, że jeśli chcielibyśmy utworzyć tabelę, w której każdy tytuł stanowiłby osobny wymiar i zakup książki oznaczałby wtedy przypisanie wartości (tak/nie) w każdym wymiarze, to otrzymana, kompletna tabela wielodzielcza byłaby ogromna, a zawierałby głównie puste komórki. Alternatywnie moglibyśmy też utworzyć tabele wszystkich możliwych dychotomii, dla wszystkich oferowanych produktów, co pozwoliłoby nam wykryć asocjacje par produktów. Jednak liczba takich tabel, znowu byłaby ogromna, a informacja w nich byłaby rozproszona. Co gorsza, jakiekolwiek potrójne asocjacje istniejące być może w danych, pozostały by dla nas tajemnicą. Algorytm a priori, zastosowany w Analiza koszykowa, nie tylko automatycznie wykryje związki ("tabele wielodzielcze"), które są ważne (tabele wielodzielcze pełne treści, a nie pustych komórek), ale określi też stopień podziału dla tabel zawierających ważne reguły asocjacji.

Podsumowując: Analizę koszykową możemy użyć do znalezienia (odkrycia) reguł typu: Jeżeli X to (prawdopodobnie) również Y, gdzie X i Y to pojedyncze wartości (kategorie), pozycje, słowa itp., albo też związki wartości, słów itp. (np. jeżeli (samochód=Porsche i wiek<20) to (ryzyko=wysokie i składka ubezpieczenia=wysoka)). Programu używamy do analizowania prostych zmiennych kategorialnych, zmiennych dychotomicznych, jak i zmiennych wielokrotnych odpowiedzi. Algorytm określi reguły asocjacji nie wymagając wstępnego podania liczby kategorii obecnych w danych ani maksymalnego stopnia faktoryzacji, czy złożoności ważnych asocjacji. Algorytm zbuduje tabele wielodzielcze bez konieczności wstępnego określania liczby ich wymiarów i liczby kategorii dla każdego wymiaru. Dlatego algorytm ten jest odpowiedni dla data i text miningu w wielkich bazach danych.

Indeks

Procedury obliczeniowe i terminologia

Zmienne jakościowe. Zmienna jakościowa to pojedyncza zmienna (kolumna) zawierająca kody lub wartości tekstowe oznaczające kategorie (klasy). Typowym przykładem może tu być zmienna Płeć, o dwóch wartościach: Mężczyzna i Kobieta.

Zmienne wielokrotnych odpowiedzi. Taka zmienna składa się zwykle z wielu zmiennych (kolumn), jest więc listą zmiennych. Każda z jej zmiennych składowych zawiera kody lub wartości tekstowe opisujące pojedynczy "wymiar" czy jedną transakcję. Dobry przykład zmiennej wielokrotnych odpowiedzi otrzymujemy w przypadku zakupów dokonywanych przez klienta, zapisywanych w jednym rekordzie, który może zawierać jeden lub więcej sprzedanych produktów, w dowolnej kolejności. I jest to typowy format, w jakim tego typu informacja jest zapisywana.

Wielokrotne dychotomie. W tym formacie danych, każdy obiekt czy klasa reprezentowana jest przez osobną zmienną, której (dychotomiczne, dwustanowe) wartości wskazują czy dana kategoria ma zastosowanie do danego przypadku, czy nie. Powiedzmy, na przykład, że dostawca utworzył arkusz, w którym, w nagłówkach kolejnych kolumn umieścił nazwy oferowanych produktów. Każda sprzedaż, czyli przypadek (wiersz), rejestrowana jest przez wpisanie do wszystkich kolumn (w odpowiednim wierszu) wartości wskazujących, czy dany produkt został w tej transakcji sprzedany, czy nie.

Reguły asocjacji: Jeżeli A to B. Algorytm a priori ustala, na podstawie danych, reguły asocjacji, które mają postać: Jeżeli A to B (ang. If Body then Head), gdzie A (zwane poprzednikiem) i B (następnikiem) to kody (wartości tekstowe) lub związki kodów. Na przykład: Jeżeli (samochód=Porsche i płeć=mężczyzna i wiek<20) to (ryzyko=wysokie i składka ubezpieczenia=wysoka). W tym wypadku A= (samochód=Porsche i płeć=mężczyzna i wiek<20), B=(ryzyko=wysokie i składka ubezpieczenia=wysoka).

Wstępny przegląd danych: poziom wsparcia. Na początku analizy program przegląda wszystkie zmienne (wybrane do analizy) w poszukiwaniu unikalnych kodów lub wartości tekstowych. Obliczane są przy tym względne częstości występowania kodów. Prawdopodobieństwo, że transakcja (przypadek) zawiera dany kod nazywane jest wsparciem. W kolejnych "przeglądach" danych obliczane jest również wsparcie, jako łączne prawdopodobieństwo (względna częstość współwystępowania) dla par, trójek itd. kodów, osobno dla części A i B każdej reguły asocjacji.

Drugi przegląd danych: zaufanie i korelacja. Po wstępnym przejściu przez dane zapamiętywane są wszystkie kody o wsparciu mniejszym od zadanej wartości. Chodzi o to, że program oblicza warunkowe prawdopodobieństwo dla wszystkich par kodów o wsparciu większym od zadanej, minimalnej wartości. To warunkowe prawdopodobieństwo, że obserwacja (transakcja) zawierająca kod X, zawiera również Y, nazywane jest poziomem zaufania. W ogólności, w dalszych przebiegach przez dane, zaufanie oznacza warunkowe prawdopodobieństwo danego B (następnika reguły asocjacji), pod warunkiem, że dane A (poprzednik odpowiedniej reguły).

Ponadto, obliczane jest wsparcie dla każdej pary kodów i bazując na tym, poziom korelacji. Korelacja dla pary kodów {X, Y} obliczana jest jako poziom wsparcia pary podzielony przez pierwiastek kwadratowy z iloczynu wsparcia dla X i wsparcia dla Y. Po drugim przejściu przez dane program zachowuje te pary kodów, które (1) mają poziom zaufania większy od zadanej, minimalnej wartości, (2) mają poziom wsparcia większy od zadanej, minimalnej wartości, oraz (3) mają poziom korelacji większy od zadanej, minimalnej wartości.

Kolejne przejścia przez dane: Maksymalna liczba kodów w A i w B. Przeglądając dane, w kolejnych krokach, program oblicza wsparcie, zaufanie i korelację par kodów (czyli asocjacji pomiędzy pojedynczymi kodami), trójek kodów itd. W każdym kolejnym kroku program ustala reguły asocjacji typu: Jeżeli A to B, gdzie B i A są pojedynczymi kodami lub związkami kodów.

Możemy otrzymywać bardzo złożone reguły asocjacji (typu: Jeżeli X1 i X2 .. i X20 to Y1 i Y2 ... i Y20); a cały proces skończy się, gdy w kolejnym kroku nie będą znalezione następne asocjacje spełniające warunki przekroczenia odpowiednich wartości wsparcia, zaufania i korelacji. W celu uniknięcia nadmiernej złożoności, użytkownik może określić maksymalne liczby kodów w A (poprzedniku) i w B (następniku) reguły asocjacji.

Tabelaryczne przedstawienie asocjacji

Reguły asocjacji mają następującą postać: Jeżeli A to B (ang. If Body then Head), gdzie A (zwane poprzednikiem) i B (następnikiem) to kody (wartości tekstowe) lub związki kodów. Na przykład: Jeżeli (samochód=Porsche i wiek<20) to (ryzyko=wysokie i składka ubezpieczenia=wysoka). Podstawowymi statystykami obliczanymi dla reguł asocjacji są: Wsparcie (względna częstość poprzednika oraz następnika), Zaufanie (warunkowe prawdopodobieństwo następnika, pod warunkiem, że poprzednik) i Korelacja (wsparcie poprzednika i następnika podzielone przez pierwiastek kwadratowy z iloczynu wsparć poprzednika i następnika. Otrzymane wartości tych statystyk można umieścić w arkuszu:

Na tym arkuszu widoczny jest wynik text miningu. Przeprowadzono analizę dialogu z pierwszej sceny szekspirowskiego Wszystko dobre, co się dobrze kończy (w oryginale), przy czym usunięto kilka najczęstszych słów, jak is, of itp. Wartości wsparcia, zaufania i korelacji podane są w procentach.

Indeks

Graficzna prezentacja asocjacji

W wynikiu zastosowania, do dużych zbiorów danych, techniki data mining - Analiza koszykowa, otrzymujemy skojarzenia typu: Jeżeli Poprzednik to Następnik (ang. If Body then Head), gdzie A (zwane poprzednikiem) i B (następnikiem) to kody (wartości tekstowe) lub związki kodów. Na przykład: Jeżeli (samochód=Porsche i wiek<20) to (ryzyko=wysokie i składka ubezpieczenia=wysoka). Otrzymane reguły asocjacji przeglądać można w formacie tekstowym, w tabelach albo w formie graficznej, w postaci wykresów (patrz poniżej).

Sieć reguł asocjacji. Jako przykład, rozpatrzmy zawierające wyniki (fikcyjne) badania ankietowego stu klientów barów, w których ogląda się sportowe programy telewizyjne. Plik zawiera informacje o tematycznych preferencjach klientów. Mamy tu proste zmienne jakościowe, z których każda reprezentuje jedną dyscyplinę sportową. Każdy z respondentów określił jak często ogląda każdą z wyszczególnionych dyscyplin. Reguły asocjacji znalezione dla tego pliku danych wyglądają jak na wykresie:

Na wykresie, wsparcie dla Poprzednika i Następnika każdej ze znalezionych reguł asocjacji ilustrowane jest przez wielkość i kolor odpowiedniego koła. Kolor i grubość linii natomiast, wskazują poziom zaufania (warunkowe prawdopodobieństwo następnika, o ile poprzednik). Wielkość środkowych kółek (nad napisem Sugeruje) określa łączne wsparcie (współwystępowania) odpowiednich par Poprzednika i Następnika. Tak więc, z tego graficznego podsumowania analizy, odczytujemy, że najsilniejsze wsparcie ma Pływanie=Czasem, skojarzone z Gimnastyka=Czasem, Baseball=Czasem i Kosz=Czasem. Inaczej niż w zwykłych tabelach liczności i wielodzielczych, bezwzględne częstości występowania kodów w danych nie odzwierciedlają się w regułach asocjacji. Znajdziemy tu jedynie te kody (lub wartości tekstowe), które wykazują odpowiednie poziomy wsparcia, zaufania i korelacji, tzn. te, które dostatecznie często współwystępują z innymi kodami.

Dwuwymiarowa sieć reguł asocjacji może być prosta, jak poprzednia, lub skomplikowana, jak na przykładzie obok.

Mamy tu wynik text miningu. Przeprowadzono analizę dialogu z pierwszej sceny szekspirowskiego Wszystko dobre, co się dobrze kończy (w oryginale), przy czym usunięto kilka najczęstszych słów, jak is, of itp. To, które słowa i frazy usuwamy w fazie przygotowania danych do text miningu lub data miningu, zależy od celu analizy.

Sieć reguł asocjacji 3W. Sieć reguł asocjacji można przedstawić na wykresie dwu, jak i trójwymiarowym. Niżej pokazany jest (bardzo klarowny) wynik analizy danych. Respondenci byli tu proszeni o podanie swoich trzech ulubionych dań w barach szybkiej obsługi. W danych wykryte zostały reguły asocjacji przedstawione niżej na wykresie trójwymiarowym.

Podobnie jak w sieci asocjacji 2W, wsparcie dla Poprzednika i Następnika wskazywane jest przez wielkość kółek. Kolor i grubość linii natomiast, wskazują poziom zaufania (warunkowe prawdopodobieństwo) odpowiedniej reguły asocjacji. Wielkość kółek "zawieszonych" u góry, na odpowiednim poziomie wzdłuż osi z, wskazuje łączne wsparcie (współwystępowanie) odpowiedniego Poprzednika z Następnikiem. Wysokość kółek (z) wskazuje na poziom zaufania. Na tym wykresie jasno dostrzegamy dwie proste reguły: Respondenci wybierający Pizzę lubią też Hamburgera, i odwrotnie.

Indeks

Interpretacja i porównanie wyników

Porównując wyniki poszukiwania reguł asocjacji z wynikami otrzymanymi w zwykłych tabelach liczności i wielodzielczych, zauważymy, że w niektórych przypadkach kody mające wysokie częstości nie znajdą się w regułach asocjacji. Może to czasem wydać się dziwne.

Dla ilustracji tego zagadnienia rozpatrzmy przykład z dziedziny ubezpieczeń komunikacyjnych (w Ameryce). Tabela częstości wykaże najpewniej, że większość jeździ samochodami produkcji Forda, GM i Chryslera; jednak może się zdarzyć, że żaden z tych samochodów nie będzie wyraźnie skojarzony z jakimś typem ubezpieczenia, tzn. nie będzie miał wysokiego zaufania ani korelacji w regule asocjacji. Z drugiej strony, względnie rzadkie samochody (np. Porsche) mogą dawać wyraźne asocjacje (np. z ubezpieczeniem wysokiego ryzyka). Skutkiem może być reguła asocjacji Jeżeli Samochód=Porsche to Składka=Wysoka. W zwykłej tabeli rozdzielczej, tego typu, wysoce prawdopodobne skojarzenie (Samochód wg Składka) łatwo może umknąć naszej uwadze.

Indeks