Algorytmy



Wstęp

Odkrywanie asocjacji

Asocjacje w IBM Digger

Klasteryzacja


Warto zobaczyć:
odzyskiwanie danych Etykiety specjalistyczne winamp download serwery wirtualne

Odkrywanie asocjacji

Charakterystyka algorytmów asocjacji W pracy wykorzystamy do analiz testowego zbioru danych zaimplementowane w pakiecie IM4D algorytmy odkrywania asocjacji. Rozwijając definicję asocjacji z rozdziału 2 proces ten jest prostym probabilistycznym stwierdzeniem o współwystępowaniu zdarzeń w zbiorze danych i ma szczególne zastosowanie przy rzadkich zbiorach transakcyjnych [Han05]. Dokładniejszej charakterystyki algorytmów odkrywania asocjacji dokonamy na przykładzie ich najczęstszego wykorzystania, czyli w tzw. podejściu analizy koszykowej (ang. MBA – Market Basket Analisys).
Celem analizy MBA jest odnalezienie wzorców zachowań klientów sklepów, hipermarketów czy hal targowych. Dzięki analizie MBA odkrywamy preferencje zakupowe klientów ich upodobania i przyzwyczajenia. Odnajdujemy grupy produktów, które są kupowane najczęściej razem i znajdujących się w koszykach klientów – stąd nazwa analizy koszyka zakupów. Odkryte wzorce zachowań są następnie wykorzystywane w celu organizacji produktów na półkach sklepowych, w celu opracowania akcji i kampanii promocyjnych oraz zaplanowania i modyfikacji oferty handlowej analizowanych podmiotów. Podejście analizy MBA wykorzystywane jest także w innych dziedzinach (telekomunikacja i analiza połączeń telekomunikacyjnych, badania medyczne – analiza objawów chorób występujących wspólnie, bankowość – analiza transakcji płatniczych). Analizując problem MBA mamy do czynienia ze zbiorem danych, który możemy zobrazować tworząc tzw. tablicę obserwacji. Jest to formalna reprezentacja, która umożliwia zamodelowanie relacji „wiele do wielu”, czyli zależności pomiędzy koszykami a znajdującymi się w nich produktami. Przykładową tablicę obserwacji prezentujemy poniżej:
Tablica obserwacji – przykład

Dany jest zbiór atrybutów (produktów) P = { P1, P2, …, P8}. Przedstawiona powyżej tablica obserwacji zawiera zbiór 12 obserwacji {O1, …, O12}. Jedynki i zera w tablicy obserwacji oznaczają czy dany produkt P został zakupiony lub nie w obserwacji O (transakcji).

Wynikiem odkrywania asocjacji są reguły asocjacyjne mające postać (dla uproszczenia zakładamy, że zmienne są binarne) [HAN05]:
IF A = 1 AND B = 1 THEN C = 1 z prawdopodobieństwem p, gdzie A, B, C są zmiennymi binarnymi, a p = p (C = 1 | A = 1, B = 1) tzn. jest prawdopodobieństwem warunkowym, że C = 1 pod warunkiem, że A = 1 i B = 1. Prawdopodobieństwo warunkowe p jest nazywane w ujęciu asocjacji „dokładnością” lub „ufnością” (ang. confidence) reguły, a p (A = 1, B = 1, C = 1) jest nazywane „wsparciem” (ang. support). Z reguły celem odkrywania asocjacji jest znalezienie wszystkich reguł, które spełniają warunek, że dokładność (ufność) p jest większa od zadanego progu pa oraz wsparcie jest większe od zadanego progu ps . Progi pa oraz ps nazywamy odpowiednio minimalną ufnością (ang. minimum confidence treshold, w skrócie minconf) i minimalnym wsparciem (ang. minimum suport treshold, w skrócie minsup). Dla przykładu przeanalizujemy sytuację, przy następujących założeniach: · minsup = 50% · minconf = 50%
Reguły asocjacyjne - przykład

W przedstawionej powyżej bazie mamy 4 transakcje oraz produkty (A, B, C, D, E, F), które zostały zakupione w każdej z transakcji (w każdym z koszyków). Dla założenia, że interesują nas tylko reguły mające minsup = 50% oraz minconf = 50%, możemy wyróżnić następujące reguły asocjacyjne:
· A => C, gdzie sup = 50% i conf = 66,6%
· C => A, gdzie sup = 50% i conf = 100%

Dla Reguły A => C, dla której sup wynosi 50% (ilość transakcji potwierdzających regułę do wszystkich transacji), możemy wyliczyć conf, która jest stosunkiem transakcji, zawierających A=>C, do wszystkich transakcji zawierających A. Analogiczne rozważania możemy przeprowadzić dla drugiej z reguł. Regułę C=>A określają wartości sup = 50% oraz conf 100% (stosunek transakcji C=>A do wszystkich zawierających C).

Wsparcie jest bardzo istotną miarą wartościującą reguły asocjacyjne, gdyż określa liczbę transakcji w analizowanym zbiorze D, które potwierdzają daną regułę. Analizując przykład zakupów w supermarkecie, wsparcie reguły określa liczbę klientów, których zachowanie jest zgodne z daną regułą. Reguły mające niewielkie wsparcie są mało reprezentatywne, gdyż opisują niewielką liczbę klientów. Natomiast reguły, mające wysokie wsparcie, są najczęściej mało interesujące dla analityka, gdyż ze względu na swoją powszechność są dobrze znane i nie wnoszą nowych informacji. Ufność danej reguły oznacza jej poziom pewności. Reguły mające niską ufność są mało wiarygodne, natomiast reguły charakteryzujące się wysoką ufnością stanowią „prawie pewną” informację.  photoshop Patrick Geryl, rok 2012, światowa apokalipsa, katastrofa programy Sony vaio