Każdy z nas robi zakupy przez internet. I każdy z nas, po dodaniu kilku produktów do koszyka, widział zapewne automatyczne podpowiedzi kolejnych produktów, zatytułowane “Inni klienci kupili też…”, “Sugerowane produkty” lub podobnie. Lista owych sugerowanych produktów to właśnie efekt analizy koszykowej (Market Basket Analysis).
Dane do takiej analizy to informacje o poprzednich transakcjach dokonanych w danym sklepie. A dokładniej o składzie koszyków w tych transakcjach. Mogą one wyglądać na przykład tak:
Analiza koszykowa polega na wyszukaniu w tego typu danych tak zwanych reguł asocjacyjnych (association rules). Reguła asocjacyjna (lub prościej, po prostu “reguła”), to implikacja postaci \(X \implies Y\) (czyt. “jeśli \(X\) to \(Y\)”). \(X\) i \(Y\) są tu zbiorami produktów. Czyli np. reguła \(\{mleko, chleb\} \implies \{jajka, mąka\}\) mówi, że jeśli klient kupił mleko i chleb to z dużym prawdopodobieństwem kupi też jajka i mąkę.
Oczywiście, interesują nas tylko reguły, w których owo prawdopodobieństwo jest rzeczywiście duże. Zwykle ocenia się je za pomocą parametru pewności (lub inaczej: trafności) reguły, nazywanego z angielskiego confidence.
Confidence reguły \(X \implies Y\) mówi jaki odsetek transakcji zawierających \(X\), zawiera też \(Y\). Zobaczmy to na przykładzie z pięcioma transakcjami wypisanymi wyżej. Policzmy confidence reguły \(\{mleko, chleb\} \implies \{jajka\}\). Transakcji zawierających mleko i chleb mamy cztery, a dwie z nich zawierają też jajka. confidence tej reguły to więc \(2/4 = 50\%\).
Innymi słowy, confidence to prawdopodobieństwo “zadziałania” reguły. Możemy więc powiedzieć, że jeśli klient kupił mleko i chleb, to z prawdopodobieństwem 50% kupi też jajka.
Innym ważnym parametrem oceniającym przydatność reguły asocjacyjnej jest jej support, nazywany czasem po polsku “wsparciem”. Support reguły \(X \implies Y\) to po prostu odsetek transakcji, w których występują wszystkie składniki \(X\) i \(Y\). Na przykład support reguły \(\{mleko, chleb\} \implies \{jajka\}\) to 40%, bo wśród pięciu transakcji, dwie (a więc 40%) zawierają i mleko i jajka i chleb.
Support mówi nam więc, jak często zdarzają się transakcje opisywane przez daną regułę. Reguły z niskim supportem są mało ciekawe, bo w “prawdziwym życiu” okazja do ich zastosowania zdarza się rzadko. W praktyce, szukając reguł asocjacyjnych, z góry narzuca się pewien warunek na support (zwykle ma on wynosić co najmniej 1%), a reguły warunku tego niespełniające pomija się w dyskusji wyników.
Trzecią często stosowaną miarą jakości reguły jest lift (tu nie ma chyba rozsądnego polskiego tłumaczenia). Lift reguły \(X \implies Y\) mówi nam ile razy prawdopodobieństwa wystąpienia \(X\) i \(Y\) w transakcji jest wyższe niż w hipotetycznej sytuacji, w której \(X\) i \(Y\) występują niezależnie od siebie. Im wyższy jest lift, tym lepsza jest reguła. Lift równy 1 oznacza, że reguła opisuje niezależnie od siebie występujące \(X\) i \(Y\), a więc rozsądne, niosące jakieś dodatkowe informacje, reguły powinny mieć lift znacznie przekraczający 1.
Pomimo groźnie wyglądającej definicji, wzór jest bardzo prosty. Lift reguły to jej confidence podzielone przez support \(Y\):
\[ \textrm{lift}(X \implies Y) = \frac{\textrm{confidence}(X \implies Y)}{\textrm{support}(Y)} \]
Jak policzyliśmy wyżej, confidence reguły \(\{mleko, chleb\} \implies \{jajka\}\) wynosi 50%. Support zbioru zawierającego tylko jajka to 40% (bo jajka znajdują się w 2 z 5 transakcji). Lift reguły \(\{mleko, chleb\} \implies \{jajka\}\) to więc 50 dzielone przez 40, czyli 1,25. To nieco więcej od 1, a więc reguła ta niesie nieco informacji.
Analizę koszykową można wykorzystać nie tylko do analizy składu “tytułowych” koszyków. Można ją też zastosować do wyszukiwania kombinacji cech, które najlepiej prognozują wystąpienie jakiejś innej cechy. Możemy mieć na przykład dane o nauczycielach: ich płci, wieku i przedmiocie, którego uczą i próbować znaleźć kombinacje tych trzech cech, które najlepiej przewidują zgodę na udział w wycieczce szkolnej.
Interesujące nas reguły będą miały postać \[ \{\textrm{płeć=mężczyzna, wiek=25-30 lat, przedmiot=WF}\} \implies \{\textrm{zgoda=tak}\}\]
lub \[ \{\textrm{płeć=kobieta, wiek=ponad 55 lat}\} \implies \{\textrm{zgoda=nie}\}.\]
Jedyne, co trzeba zrobić, by taka analiza była wykonalna, to odpowiednio przekształcić zmienne. Ponieważ w oryginalnej analizie koszykowej wszystkie zmienne są wyrażone za pomocą zer i jedynek (jedynka oznacza, że dany produkt znalazł się w danej transakcji, a zero, że nie), tutaj też trzeba przejść na taką postać.
Ze zmiennymi jakościowymi (nie-liczbowymi) jest łatwo: wystarczy stworzyć po jednej zmiennej zero-jedynkowej dla każdej z możliwych wartości. Oryginalna zmienna \(\textrm{płeć}\) daje nam więc dwie nowe zmienne zero-jedynkowe. Pierwsza z nich będzie przyjmowała wartość 1 dla kobiet a 0 dla mężczyzn a druga na odwrót. Możemy zmienne te nazwać \(\textrm{płeć żeńska}\) i \(\textrm{płeć męska}\) (lub bardziej “technicznie” \(\textrm{płeć=kobieta}\) i \(\textrm{płeć=mężczyzna}\)) i myśleć o nich jak o produktach, które każdy z nauczycieli może “wybrać” do swojego “koszyka”. 1 Zmienna \(\textrm{przedmiot}\) da tych “produktów” dużo więcej.
Zmienne ilościowe (liczby) wymagają dodatkowego przekształcenia. Trzeba koniecznie podzielić je najpierw na przedziały i dopiero wtedy stworzyć po jednym zero-jedynkowym “produkcie” dla każdego z przedziałów.
Na szczęście to wszystko robią za nas programy komputerowe. One też wyszukują reguły asocjacyjne. To zadanie potrafi być mocno złożone obliczeniowo, jeśli baza danych jest duża (mamy wiele transakcji i/lub produktów). Stosuje się tu specjalnie do tego celu opracowane algorytmy, z których najpopularniejszym jest algorytm o nazwie “Apriori” autorstwa R. Agrawala i R. Srikanta. 2
Fakt, iż nie da się “wrzucić do koszyka” obu tych produktów na szczęście nie przeszkadza w poszukiwaniu reguł asocjacyjnych.↩︎
Agrawal R, Srikant R (1994). “Fast Algorithms for Mining Association Rules.” In JB Bocca, M Jarke, C Zaniolo (eds.), Proc. 20th Int. Conf. Very Large Data Bases, VLDB, pp. 487–499. Morgan Kaufmann.↩︎