Správanie návštevníkov a dolovanie v dátach
Ako som pomocou dolovania v dátach analyzoval správanie užívateľov na forum.animacia.sk a taktiež navštevníkov mojej stánky.
Dolovanie v dátach
Problémom v dnešnej dobe už nie je získať množstvo informácií, ale paradoxne nájsť v záplave informácií nejaké zaujímavé údaje či závislosti. Presne na tento problém vznikli a stále vznikajú rôzne dolovacie algoritmy, ktoré dokážu takéto závislosti nájsť. Dolovanie v dátach je teda možné robiť rôznymi technikami, no ja sa zameriam len jednu z nich, známu pod názvom objavovanie asociačných pravidiel (association rule discovery).
Predtým ako však vhupneme do samotného algoritmu predstavme si najprv ukážkové zadanie takého problému.
Tu máš bloky z pokladníc v našom hypermarkete za posledný mesiac a zisti mi nejaké zaujímavé veci o nákupoch našich zákazníkoch.
Taký blok obsahuje všeličo možné, ale my sa sústreďme iba na kúpené tovarové položky. Predpokladajme taktiež, že jeden blok predstavuje jedného zákazníka. To je vlastne vo väčšine prípadov pravda a zopár výnimiek to aj tak nepokazí. Naše údaje teda teraz vyzerajú asi takto:
zákazník 1: maslo, chlieb, pivo
zákazník 2: pivo, soletky, rum, chlieb
zákazník 3: chlieb, maslo, rohlíky, šunka
V praxi ich však bude o dosť viac lebo keby mal hypermarket takúto tržbu za mesiac tak ho nezachráni žiadne dolovanie v dátach. V každom prípade si každý mierne matematicky zdatný stredoškolák teraz vie jednoducho vypočítať, že ak si zákazník kúpil chlieb tak s akou pravdepodobnosťou si kúpi aj maslo. Toto voláme asociačné pravidlo. Problémom však pri veľkom množstve dát je to, že vlastne nevieme čo máme hľadať. Musíme na to ísť teda trochu inak.
Apriori princíp
Tento princíp je založený na tom, že hľadáme frekventované výskyty nejakých množín (dvojice, trojice,…) tovarov a tvrdí, že každá podmnožina frekventovaných množín musí byť taktiež častá. V reči pozemskej to znamená asi toľko, že keď sa napríklad nejaká trojica tovarov vyskytuje často na nákupných blokoch tak sa tam často budú nachádzať aj všetky dvojice a "jednoice" tovarov, ktoré z tejto trojice môžeme vytvoriť. Úplne laicky povedané:
Ak si 80% zákazníkov kúpi chleba a maslo tak to znamená, že minimálne 80% zákazníkov si kúpi chleba.
Keď sa človek nad tým zamyslí tak je to dosť triviálne tvrdenie.
Celá finta hľadania je teda v tom, že nájdeme najprv počty "jednoíc" v zozname všetkých zákazníkov. Zoberieme tie, ktoré sú najviac časté a budeme hľadať už len dvojice, ktoré obsahujú aspoň jednu z týchto vyvolených "jednoíc". Takto dostaneme časté dvojice, usporiadame podľa podpory, vyberieme tie, ktoré sú najviac časté a hľadáme trojice. Takto môžeme ďalej samozrejme aj pokračovať. Praxi sa to robí tak, že sa zavedie konštanta minimálnej podpory a do ďalšieho kola výberu sa dostávajú len tie n-tice, ktoré prekročia túto podporu.
Teraz už máme nejaké tie dvojice a trojice, ale tích je stále veľa a v podstate to ani nemusí o ničom zaujímavom vypovedať. Zavedieme teda ešte jednu charakteristiku týchto asociačných pravidiel a nazveme ju dôveryhodnosť (confidence). Zoberme si teda príklad dvojicu (chlieb, maslo). Pravdepodobnosť, že ak si niekto kúpi chlieb tak si kúpi aj maslo je 2/3. Toto je teda dôveryhodnosť pravidla "ak chlieb potom maslo". Pravdepodobnosť pravidla "ak maslo tak chlieb" je však 1 a logicky toto pravidlo vyzerá byť dôveryhodnejšie. V praxi to však môže byť ešte trochu inak, ale to už radšej nechajme na pokoji. Toto nám teraz aj tak bude stačiť. Keby sa o to silou mocou niekto zaujímal tak dobré kľučové slová sú Piatesky, Shapiro, interestingness.
Takže teraz, keď už máme asociačné pravidlá s ich podporou a dôveryhodnosťou, nič nám nebráni dobehnúť za šéfom a zvestovať mu skvelú správu o tom, že keď napríklad spravíme akciu na balíček obsahujúci chlieb a maslo zarobíme tažké milióny.
Experiment na internetovom fóre
Doteraz to bola skoro čistá teória, ktorá sa dá pri troche štastia a rozumu vyčítať z múdrych knižiek. Pozrime sa na nejaké iné aplikácie tohto algoritmu.
V prvom experimente som vzal dáta z internetového fóra forum.animacia.sk, ktoré som už dávnejšie analyzoval pomocou Kohonenových máp a upravil som si ich takto. Zobral som nejakého používateľa a zistil, do ktorých kategórií najčastejšie prispieva. Bral som v úvahu len tie kategórie kde napísal aspoň 5% svojich príspevkov aby som predišiel zbytočnému šumu z náhodných pisateľských úletov niektorých jedincov. Takúto tranformáciu dát voláme diskretizácia, ale to je len pre informáciu tích, čo sa vyžívajú v cudzích slovách tak ako ja. Ak toto spravíme pre každého užívateľa fóra tak dostaneme dáta štrukturálne rovnaké ako v príklade s hypermarketom. Jediné čo nám ostáva je len pretlačiť to cez algoritmus a pozerať na výsledky.
Nasleduje výber pravidiel, ktoré som týmto spôsobom našiel.
3D CGI Software + Výstavný sál 3D CGI => 3D CGI WIP (74%)
3D CGI WIP => Výstavný sál 3D CGI (71%)
Výstavný sal 2D Grafiky => Výstavný sál 3D CG (53%)
Výstavný sál 3D CG => 3D CGI Software (50%)
Výstavný sál 2D Grafiky => Teória výtvarnej tvorby (45%)
Len v krátkosti vysvetlím čo znamená. Napríklad prvý riadok znamená, že ak niekto prispieva do kategórií 3D CGI Software a Výstavný sál 3D CGI tak na 74% prispeje aj do kategórie 3D CGI.
Experiment na mojej stránke
Ďalšia aplikácia tohto experimentu bola zanalyzovať správanie návštevníkov tejto stránky. Ako zdroj dát mi poslúžil Apache log, ktorý zaznamenáva každú návštevu tento stránky. Z tohto logu sa dá zistiť aké stránky daný návštevník pozeral. Pre jednoduchosť som ešte predpokladal, že jedna IP adresa je jeden návštevník a tak som znova dostal vhodné dáta pre náš algoritmus a za pomoci logu z posledných dvoch mesiacov som zistil okrem mnohého iného aj toto:
/autor.html + /archiv/ => index.html (89%)
/archiv/ => index.html (81%)
robots.txt => index.html (53%)
/archiv/ => autor.html (51%)
/archiv/webdesign-pristupnost-v-praxi.html => index.html (78%)
/autor.html => /SLAP/ (29%)
Zápis a jeho interpretácia je rovnaká ako v predchádzajúcom experimente avšak tu si treba dávať pozor na to, že ak mám pravidlo /autor.html => /SLAP/ nemusí to znamenať, že človek si pozrel tieto stránky práve v poradí /autor.html, /SLAP/. V kľude si ich mohol pozrieť aj v opačnom poradí. Týmto problémom sa zaoberá dolovanie sekvencí z dát, ale to je už úplne iné rozprávanie.
(18. december 2004)