1 UVOD Svetovni splet je postal eden najpomembnejših virov informacij, tako za zasebne kot tudi za poslovne uporab- nike. Omogoča skoraj neomejeno izmenjavo podatkov med različnimi strankami. Podjetja uporabljajo spletne strani za oglaševanje in prodajo svojih izdelkov, in- stitucije za zagotavljanje informacij o svojih storitvah, posamezniki pa za učinkovit dostop do različnih virov informacij. Blogi in socialna omrežja pridobivajo na popularnosti in so že prerasla mejo zasebnega obja- vljanja. Vedno več ljudi za pridobivanje novic namesto tradicionalnih medijev uporablja družabna omrežja [17]. Obstoječe spletne strani se vsako leto soočajo z več in čedalje boljšimi tekmeci. Vse težje je pritegniti nove stranke in obdržati obstoječe. V takšnih okoliščinah bodo preživele le spletne strani, ki izčrpno razumejo po- trebe svojih strank in njihovo obnašanje na spletni strani. Posledično je analiziranje vedenja uporabnikov postalo sestavni del analize spletnih podatkov. Pomembno vlogo ima tako pri vsakodnevnih kot tudi strateških odločitvah. Kakovost odkritih vzorcev obnašanja uporabnikov je zelo odvisna od kakovosti pridobljenih in obdelanih podatkov. Vedno več tretjih oseb beleži in analizira vedenje uporabnikov na spletu. Po drugi strani pa uporabniki ne želijo sledenja. Nasprotovanje uporabnikov sledenju sta v svojem članku predstavila Mayer in Mitchell [16]. Teh- nologije sledenja lahko grobo razdelimo v dve skupini: sledenje s hranjenjem stanja in sledenje brez hranjenja ANALIZIRANJE OBNAŠANJA UPORABNIKOV NA SPLETU 145 stanja (angl. fingerprinting). V prvi skupini najdemo na- vadne piškotke in piškotke HTML5, sledenje geolokaciji in piškotke raznih vtičnikov (npr. Flash). Sledenje brez hranjenja stanja temelji na zaznavi lastnosti brskalnika in ustvarjanju edinstvene oznake na podlagi teh lastnosti. Aktivno sledenje brez hranjenja stanja vključuje aktivno odkrivanje lastnosti oddaljnega odjemalca (vrsta CPE, nastavitve zaslona, pisave ipd). Pasivno sledenje brez hranjenja stanja pa je omejeno na čisti komunikacijski protokol HTML in njegove lastnosti (oddaljeni naslov IP, jezik, napotitelj ipd). Prednost pasivnega sledenja je, da za uporabnika ni preveč vsiljivo, saj uporabnik ne ve, da je predmet proučevanja, niti se mu ne more izogniti. Eden glavnih virov podatkov za izvedbo analize obnašanja uporabnikov na spletnih straneh so dnevniške datoteke spletnega strežnika (angl. web server log files). Dnevniki spletnih strežnikov so integralni del spletnih strežnikov, vendar prvotno niso bili namenjeni analizi obnašanja uporabnikov. Vsebujejo le omejene, včasih pomanjkljive podatke, njihova vsebina pa ni vedno ja- sno določena. V članku se ukvarjamo z enim izmed izzivov analize podatkov iz tega vira, prepletenimi upo- rabniškimi sejami. Predstavili bomo sorodne pristope in predlagali novo tehniko za izboljšanje kakovosti infor- macij, ki jih pridobimo iz prepletenih sej. Dnevniške datoteke spletnega strežnika so najpogo- stejši in najprimernejši vir podatkov o klikotoku (angl. clickstream) [13]. Klikotok je zaporedje dejanj (klikov), ki jih uporabnik naredi med brskanjem po določenem spletnem mestu. Ker je vir podatkov o klikotoku pra- viloma na voljo, so podatki o klikotoku glavni vir podatkov za analizo obnašanja uporabnikov [27], [2]. Spiliopoulou in sod. [26] so dnevnik spletnega strežnika formalno definirali kot: Naj množica U označuje vse mogoče spletne zahteve (angl. Web requests) na spletnem mestu. Ta množica vsebuje tako statične strani kot tudi strani, ki jih je mogoče dinamično generirati glede na vhodne parame- tre. Dnevnik spletnega strežnika L je seznam zahtev strani iz množice U vseh uporabnikov. Zapisi v seznamu L so urejeni po časovni oznaki zahteve. Dnevniki spletnega strežnika so bili sprva namenjeni za razhroščevanje spletnih strežnikov in ne kot vir po- datkov za analize. Zato v dnevnikih spletnih strežnikov pogosto manjkajo nekateri ključni podatki za pridobitev vzorcev obnašanja uporabnikov, posledica tega pa so določene težave z razpoložljivostjo in kakovostjo podat- kov [13]. Podatki o klikotoku, pridobljeni iz dnevnikov spletnih strežnikov, so zato lahko nepopolni, vsebujejo šum in ne morejo popolnoma verno zajeti obnašanja uporabnika po spletnem mestu. Zato sta čiščenje in priprava podatkov zahtevna in nagnjena k napakam. Pri uporabi dnevnikov spletnega strežnika kot vir podatkov lahko naletimo na vrsto težav. Kljub temu zaradi široke dostopnosti in nevsiljivosti ostajajo eden privlačnih virov podatkov. Namenski sistem za prijavo uporabnikov, prilagojen za določeno spletno aplikacijo, je seveda veliko boljša rešitev. Vendar taka rešitev zah- teva znatne finančne, računalniške in človeške vire. Po- leg tega je treba načrtovati dovolj vnaprej, da pravočasno zberemo želene količine podatkov o obnašanju uporab- nikov, tako na strežniški strani kot na strani odjemalca. Takšen način zbiranja podatkov lahko povzroča tudi zakonske težave zaradi zasebnosti podatkov (npr. po- misleki glede uporabe piškotkov [12], [25]). Z uporabo izključno dnevnika spletnega strežnika se izognemo tem težavam, saj je beleženje dostopov sestavni mehanizem spletnega strežnika, relativno nezahteven za vire, na voljo pa je ogromna količina že zbranih zgodovinskih podatkov. Zato večina študij analize spletnih uporab- nikov uporablja kot vir za podatke dnevnik spletnega strežnika [3], [29]. 2 PREGLED PODROČJA Uporabniško sejo sestavlja zaporedje akcij, ki jih upo- rabnik izvede med brskanjem po spletnem mestu v določenem časovnem obdobju. Podatki o sejah se največkrat v razpršeni obliki beležijo v dnevniške dato- teke. Pri rekonstrukciji sej podatke pretvorimo v obliko, ki je primerna za nadaljnjo uporabo [5], [21]. Verna rekonstrukcija uporabniških sej ni lahka naloga, ker HTTP-protokol nima stanja in individualne zahteve za spletne vire niso povezane med sabo (tj. zahteve nimajo identifikatorja seje). Pri reaktivnem pristopu re- konstrukcije sej [6], [7] identificiramo uporabnike na podlagi dnevnikov brez uporabe drugih podatkov z odje- malca (npr. piškotki). V takem primeru bodo uporabniki, ki so skriti za strežnikom proxy ali pa sočasno upora- bljajo več zavihkov spletnega brskalnika, v dnevniških datotekah kreirali seje, ki imajo enak IP in bodo zato lahko obravnavani kot en sam uporabnik. Pri uporabi reaktivnih strategij za rekonstrukcijo sej so soočamo s pomanjkanjem nekaterih podatkov (npr. identifikator seje), zato se poslužujemo različnih hevri- stičnih pristopov. Izzivi, na katere naletimo pri uporabi te metode, so: • Identifikacija posameznih uporabnikov. Identifika- cija uporabnika glede na naslov IP je lahko netočna. Izboljšamo jo lahko z vključitvijo podpisa brskal- nika (atribut user-agent) v dnevnik [6]. Mehanizmi, ki posegajo v zasebnost uporabnika, zaradi zaščite zasebnosti niso zaželeni [16]. • Identifikacija spletnih sej iskalnih robotov, še zlasti, če spletni dnevnik ne hrani podpisa brskalnika. Identificiramo jih lahko na podlagi njihovega pod- pisa v atributu user-agent, preverbo naslova IP v podatkovni zbirki spletnih robotov ali drugih značilnostih [18]. • Verna rekonstrukcija aktivnosti posameznih upo- rabnikov, kjer so posamezne zahteve dodeljene pra- vim uporabnikom. V literaturi so bile predlagane različne hevristike: časovno usmerjena hevristika [6], navigacijsko usmerjena hevristika [7], pristop 146 POŽENEL, KUKAR z uporabo linearne optimizacije (angl. Integer pro- gramming) [8], uporaba navigacijskih zaporedij [1]. • Obravnavanje uporabe gumba za nazaj v brskal- niku. Akcija nazaj se ne zabeleži nujno v dnevniški datoteki spletnega strežnika [9], [18]. Manjkajoči zapisi v dnevniški datoteki pa lahko negativno vplivajo na rekonstrukcijo sej in lahko povzročijo nepravilno rekonstrukcijo sej. • Vzporedno brskanje v več zavihkih brskalnika [11], [19]. Postopek rekonstrukcije sej mora upoštevati scenarij, v katerem ima uporabnik odprtih več zavihkov ali oken brskalnika za brskanje po is- tem spletnem mestu. Za uporabnika vsak zavihek običajno pomeni ločeno uporabniško sejo. Takšno obnašanje je pogosto za napredne uporabnike in povzroča prepletene seje. Ker se spletni strežnik ne zaveda različnih zavihkov, se take seje na strežniški strani vidijo kot ena dolga seja in jih je treba ustrezno razplesti [21]. Veliko zgornjih izzivov lahko rešimo z uporabo pro- aktivnih strategij [10], [24], kot je uporaba piškotkov, ali pa z dinamičnim generiranjem zahteve za spletno stran na odjemalcu, ki ji pripnemo identifikator uporabnika. Pomanjkljivost tega pristopa je, da moramo spremeniti strukturo spletne strani, kar pomeni poseganje v ob- stoječo rešitev. Ena od aktivnih strategij je tudi uporaba sistemov za sledenje tretjim osebam (orodje Web Ana- lytics, npr. Google Analytics), kjer se v vsako spletno stran vstavi JavaScript koda tretjih oseb. Slabost tega pristopa so varnostna vprašanja, saj se podatki o uporabi spletnih strani običajno pošiljajo na spletno mesto tretje osebe, kjer se obdelujejo in analizirajo [1]. Uporaba storitev tretjih oseb poleg vrednosti prinaša tudi pomi- sleke glede zasebnosti. Spletni uporabniki so namreč čedalje manj naklonjeni uporabi piškotkov, posredovanju podatkov tretjim osebam in uporabi njihovih vzorcev brskanja za namene oglaševanja [16]. Zato se lastniki spletnih mest raje izogibajo uporabi proaktivnih strategij. Nobeden izmed predstavljenih pristopov ne rešuje problema prepletenih sej. Kolikor vemo, je edini pristop, ki se ukvarja s problemom vzporednega brskanja in prepletenih sej, predstavil Viermetz s sod. [28]. Vendar je njihov pristop usmerjen k boljšemu razumevanju vedenja uporabnikov spletnega mesta, manj poudarka je na samem postopku razpletanja. Želeli smo zapolniti vrzel in razvili izviren pristop za razpletanje prepletenih sej, ki temelji na markovskih verigah prvega reda in omogoča učinkovito razpletanje prepletenih sej. 3 PREDSTAVITEV PODATKOV Predobdelani podatki zajemajo podatke o klikotoku, združenih v uporabniške seje, in načrt spletnega mesta. Načrt spletnega mesta je graf spletnih strani iz množice U, ki so dostopni uporabnikom in med sabo povezani s hiperpopezavami. Neposredna povezava med spletnima stranema xi in xj v načrtu pomeni večjo verje- tnost prehoda uporabnika med tema dvema stranema, kot če neposredne povezave ni. Načrt spletnega mesta lahko zelo olajša analizo podatkov, zlasti kadar so spletne strani med sabo zelo redko povezane. Uporabniško sejo S lahko predstavimo kot zaporedje spletnih strani S = [x1, x2, . . . , xk], (1) kjer stran x1 pomeni začetno (vstopno) spletno stran in xk zadnjo obiskano spletno stran v uporabniški seji. Posamezno uporabniško sejo lahko obravnavamo kot pot skozi graf, ki v našem primeru predstavlja načrt spletnega mesta. Pot se začne v začetnem vozlišču, ki ustreza prvi strani x1 v seji, in konča v zadnjem vozlišču, ustreza zadnji obiskani strani xk uporabniške seje. Postopek razpletanja sej temelji na vzorcih, prido- bljenih iz preteklih uporabniških sej. Surove podatke o klikotoku iz dnevnika spletnega strežnika je treba preoblikovati v obliko, primerno za nadaljnjo obdelavo. Vsaka uporabniška seja v klikotoku je predstavljena kot zaporedje zahtevanih strani. Klikotok lahko preobliku- jemo v graf, kjer vsaka uporabniška seja predstavlja pot skozi graf. Vozlišča v grafu pomenijo zahtevane spletne strani, povezave pa prehode med temi stranmi. Začnemo s praznim grafom, ki vsebuje vsa vozlišča iz množice U, in postopoma dodajamo povezave glede na prehode v uporabniških sejah. Če uporabljamo pred- znanje (npr. načrt spletnega mesta), začnemo z gra- fom, ki vsebuje povezave v skladu s predznanjem (npr. povezave, ki se nahajajo v načrtu spletnega mesta). Na podlagi dveh sosednjih strani xi, xi+1 v zaporedju uporabniške seje povežemo ustrezni dve vozlišči ni in ni+1 v grafu in nastavimo utež povezave w(ni, ni+1). Če sta vozlišči ni in ni+1 že povezani, samo ustrezno posodobimo utež povezave w(ni, ni+1). Več ko je poti v grafu, ki si deli odsek poti ni → ni+1, večja je utež w(ni, ni+1). Ko graf posodobimo s podatki vseh uporabniških sej, dobimo utežen graf, ki ustreza kliko- toku. Utežene poti grafa lahko uporabimo za izračun verjetnosti prehoda med sosednjimi vozlišči. Vsako vo- zlišče ni je povezano z več vozlišči nj in za vsako povezavo poznamo verjetnost prehoda v vozlišče nj , tj. P (ni → nj). Markovski modeli se pogosto uporabljajo za mode- liranje časovno odvisnih zaporednih problemov. Lahko jih uporabimo za napovedovanje najverjetnejšega nasle- dnjega stanja, izračun verjetnosti opazovanega zaporedja ali za iskanje najverjetnejšega zaporedja. Markovska veriga je definirana kot zaporedje na- ključnih spremenljivk, s0, s1, s2, . . . , ki imajo mar- kovsko lastnost. To pomeni, da je prihodnost pogojno neodvisna od preteklosti. Markovsko verigo lahko upo- rabimo pri izračunu verjetnosti določene uporabniške seje. Vsako stanje (označeno z si) v markovski verigi ustreza spletni strani (označeno z xi). Dogodki (kliki hiperpovezav) ustrezajo prehodu iz enega stanja v drugo. Pri razpletanju smo uporabili markovsko verigo prvega reda. Verjetnosti prehodov med stanji smo določili iz ANALIZIRANJE OBNAŠANJA UPORABNIKOV NA SPLETU 147 n n n 40 7 n1 n2 n6 n3 n5 p = 0.5 p = 0.9 p = 0.1 p = 0.2 p = 0.1 p = 0.9 p = 0.9 p = 0.6 p = 0.4 p = 0.8 p = 0.5 p = 1.0 Slika 1: Markovska veriga spletnega mesta. Vozlišče n0 je začetna stran, n7 pa končna stran. Prehodi med stanji označujejo verjetnosti prehodov med stranmi. Verjetnost poti n0 → n2 → n6 → n7 je 0.9 ∗ 0.9 ∗ 0.9 = 0.729. preteklih uporabniških sej, kjer smo markovsko verigo naučili s podatki čistih, neprepletenih sej. Slika 1 prika- zuje markovsko verigo spletnega mesta. 4 METODA RAZPLETANJA V naših zgodnejših poskusih smo razvili osnovno me- todo za razpletanje sej, ki uporablja markovski model prvega reda [20]. Temelji na požrešnem pristopu, ki zaporedno razporeja strani prepletene seje v delno raz- pletene seje. Temelji na dejstvu, da prehod med stranema prepletene seje xi → xi+1 z večjo verjetnostjo pripada eni izmed razpletenih sej. Pomanjkljivost te metode je, da ne zagotavlja najbolj verjetnih razpletenih sej. Za zagotovitev optimalnejše rešitve med drugim lahko uporabimo metode preiskovanja v prostoru stanj. Našo osnovno metodo lahko premočrtno obravnavamo kot požrešno iskanje lokalno optimalne rešitve v prostoru stanj. Obstaja veliko pristopov za iskanje rešitev v prostoru stanj. Osnovni iskalni strategiji sta iskanje v globino in iskanje v širino. Iskanje v globino ima linearno pomnilniško zahtevnost glede na dolžino poti, vendar ne najde nujno rešitve. Iskanje v širino preišče celo- ten prostor stanj, zato vedno najde vse rešitve in tudi optimalno. Pomanjkljivost iskanja v širino je velika prostorska zahtevnost, ker mora v pomnilniku hraniti vsa vozlišča, da lahko generira vozlišča na naslednji ravni. Če je na voljo znanje o problemski domeni, ki lahko usmerja iskanje, lahko uporabimo metode informiranega iskanja, kot je na primer best-first search [4], ki iskanje usmerja v smeri najbolj perspektivnega vozlišča. V tem članku bomo predstavili metodo za razpletanje sej, ki uporablja informirano iskanje v širino (RBFS). 4.1 Prostor stanj za razpletanje sej Prostor stanj lahko predstavimo kot usmerjen graf, katerega vozlišča (stanja) ustrezajo rešitvam delnih pro- blemov, povezave med vozlišči pa ustrezajo legalnim prehodom med stanji. Problem iskanja se pretvori v problem iskanja poti med začetnim stanjem (začetno vozlišče) in končnim stanjem (končno vozlišče). Preho- dom med stanji lahko pripišemo ceno. V našem primeru nas zanimajo rešitve z minimalno ceno. Prostor stanj za razpletanje sej je graf oz. bolj natančno drevo. Začnemo z dobro definiranim začetnim stanjem, iz katerega potem rekurzivno izpeljemo delne razplete po nivojih drevesa, ki tvori prostor stanj. Problem razpletanja sej lahko formuliramo kot pro- blem iskanja v prostoru stanj. Vsako stanje Z pomeni prepleteno sejo SI = [x1, x2, . . . , xn] z dolžino n z r delno razpletenimi sejami SS , Z = 〈[S(1)S , S (2) S , . . . , S (r) S ], SI〉 = 〈[(xS (1) S 1 , x S (1) S 2 , . . . , x S (1) S a ), ... (x S (r) S 1 , x S (r) S 2 , . . . , x S (r) S b )], (xj , xj+1, . . . , xn)〉, kjer S(i)S pomeni i-to delno razpleteno sejo, SI preple- teno sejo (razpleteno do elementa xi) in xk stran v seji. Začetno stanje je predstavljeno kot ZS = 〈[], (x1, x2, . . . , xn)〉 s praznim seznamom na začetku, kar pomeni, da ni- mamo še nobenih delno razpletenih sej, in zaporedjem strani, ki pomeni celo prepleteno sejo. Če imamo pre- pleteno sejo z dolžino n, lahko razpletanje vrne največ n razpletenih sej. Če domnevno prepletena seja sploh ni prepletena, dobimo eno samo razpleteno sejo. Pri razpletanju se premikamo med stanji po poveza- vah, ki imajo pozitivne uteži (cena). Prehod iz stanja v sosednje stanje ustreza bodisi dodeljevanju naslednje strani prepletene seje eni od delno razpletenih sej ali začetku nove razpletene seje. Akcije dodeljevanja strani ne moremo razveljaviti, posledica pa je velik prostor stanj v obliki drevesa. Število naslednikov vsakega vo- zlišča je odvisno od števila začetih razpletenih sej v trenutnem vozlišču. Vsak prehod dodeli naslednjo stran prepletene seje xi na konec ene izmed delno razpletenih sej SS ali pa začne novo sejo S (r+1) S . Slika 2 prikazuje primer dveh stanj Z1 in Z2 in akcije, ki označuje prehod med stanjema. [x0 x4 x5] [x0 x4 x5] [x1] [x1 x8] [ x8 x7 x4]x0 x4 x1 x5 [ x7 x4]x0 x4 x1 x5 x8 cost(z1 z2) = z1 z2 p(x1 x8) Slika 2: Primer prehoda med dvema stanjema v našem prostoru stanj. Zaporedje nad črtkano črto pomeni prepleteno sejo. Krepko napisane strani so že bile dodeljene delno razpletenim sejam pod črtkano črto. Akcija doda naslednjo stran prepletene seje x8 na konec druge razpletene seje. 148 POŽENEL, KUKAR Primer prehoda med dvema državama v našem is- kalnem prostoru. Zaporedje nad črtkano črto pomeni prepleteno sejo s krepkimi stranmi, ki so že dodeljene delno ločenim sejam pod pikčasto črto. Dejanje doda naslednjo stran od prepletene seje (x8) do konca druge ločene seje. 4.2 Hevristično preiskovanje Če želimo razplet prepletene seje, da je produkt verje- tnosti prehodov med stranmi največji, moramo načeloma preiskati celoten prostor stanj. Skupno število vozlišč drevesa stanj z n nivoji je enako ∑n k=0 Bk in raste eksponentno v odvisnosti od v n. Preiskovanje vseh poti v drevesu stanj je časovno izjemno potratno za- radi eksponentnega večanja alternativ na vsakem nivoju drevesa, kar kliče po uporabi problemsko specifične hevristike. Namen hevrističnega iskanja je s pomočjo funkcije f(Z) = g(Z) + h(Z) ovrednotiti, katera vozlišča množice kandidatov so najbolj obetavna, in naprej iskati v smeri najbolj obetavnega. Pri tem h(Z) pomeni hevristično ocena obetavnosti vozlišča in g(Z) ceno najkrajše poti od začetnega vozlišča do vozlišča Z. Zaradi linearne prostorske zahtevnosti smo uporabili prostorsko učinkovito implementacijo algoritma A∗ – algoritem recursive best-first search (RBFS) [14]. 4.2.1 Dopustnost hevristične funkcije: je zaželena lastnost hevristične ocenjevalne funkcije. Naj za vsako vozlišče Z v prostoru stanj velja, da je h∗(Z) cena optimalne poti od vozlišča Z do ciljnega vozlišča. Izrek o popolnosti trdi, da je hevristična funkcija dopustna (optimistična), če za vsa vozlišča Z v prostoru stanj velja h(Z) ≤ h∗(Z). Ko pri iskalnih algoritmih iz družine A∗ (vključno RBFS) za usmerjanje iskanja uporabimo dopustno he- vristično funkcijo, iskalni algoritmi vedno najdejo op- timalno rešitev (najcenejšo pot) [22]. Nedopustne (pe- simistične) hevristične funkcije ne zagotavljajo iskanja optimalnih rešitev, lahko pa delujejo hitreje [4]. 4.2.2 Hevristična funkcija za razpletanje: Za pro- blem razpletanja prepletenih sej nas zanima ciljno vo- zlišče, ki maksimira produkt verjetnosti prehodov med stranmi v vseh razpletenih sejah. Dopustna hevristična funkcija h(Z) mora optimistično oceniti razplet pre- ostalega dela prepletene seje. Maksimirati mora pro- dukt verjetnosti prehodov med stranmi (ali enakovredno, zmanjšati vsoto njihovih negativnih logaritmov), ki še niso bile razporejene delno razpletenim sejam. Trivialna dopustna hevristična funkcija za problem razpletanja sej, je kar h0(Z) = 1 ∗ 1 ∗ . . . ∗ 1 = 1 (2) Taka hevristična funkcija bi obravnavala vsa vozlišča enako, vendar ne bi pripomogla k smiselnemu usmerja- nju iskanja. Za dobro vodenje mora biti h(Z) čim bliže h∗(Z). Dopustna hevristična funkcija h, ki ponuja dobro usmerjanje, je predstavljena v nadaljevanju. x0 x1 x4 x5 x7x15 max{ P(? x ) } i Z3 x3 Slika 3: Vozlišče Z3 hrani stanje delno razpletene prepletene seje. Oglejmo si sliko 3, ki prikazuje vozlišče Z3. Preple- tena seja je delno razdeljena na dve začeti razpleteni seji, kot prikazuje slika 4. Prvo stran prepletenega dela (stran x4) lahko bodisi dodamo na konec ene izmed delno razpletenih sej bodisi začnemo novo razpleteno sejo. Ko računamo vrednost max{P (? → xi)}, ne smemo upoštevati vseh strani v razporejenem delu, ampak samo zadnjo stran vsakega delno razpletenega dela. Pri vo- zlišču Z3 in dodelitve strani x4 je izračun enak: max{P (?→ x4)} = max{P (x0 → x4), P (x1 → x4)} prepletena seja S X X X X X X X X XX3 0 1 4 6 17 2 3 0 1 S (1) S S (2) X4 X4 X2 Slika 4: Delno razpletena prepletena seja. Naslednjo nerazpo- rejeno stran prepletene seje (x4) lahko dodamo na konec enega od začetih delnih razpletov. Pri izračunu vrednosti hevristične funkcije moramo upoštevati vse strani, ki se v še nerazpletenem delu prepletene seje nahajajo pred stranjo xi. Postopek za izračun izraza max{P (? → xi)} je prikazan na sliki 5. Hevristika h je dopustna pod pogojem, da lahko nedvoumno določimo začetne strani razpletenih sej. Če ta pogoj ni izpolnjen, bo rezultat morda vseboval preveč razpletenih sej. Pokazalo se je, da je predstavljena he- vristična funkcija h izjemno učinkovita pri usmerjanju iskanja za problem razpletanja prepletenih sej, zato smo jo uporabili tako pri sintetičnih kot tudi pri realnih podatkih. zaklju�na stanja delno razpletenih sej nerazpleteni del x maksimum i Slika 5: Izračun izraza max{P (→ xi)} hevristične funkcije ANALIZIRANJE OBNAŠANJA UPORABNIKOV NA SPLETU 149 Tabela 1: Rezultati razpletanja sej na podlagi podatkov spletne trgovine Metoda vrednotenja Požrešno RBFS Popolno ujemanje 0.334 0.398 WLCS 0.504 0.541 5 REZULTATI Umetno generirana množica prepletenih sej je sesta- vljena iz različnega števila preverjenih, čistih sej. Tre- tjina prepletenih sej vsebuje dve čisti seji, ena tretjina tri čiste seje, preostala tretjina pa so neprepletene čiste seje. Tako generirane prepletene seje odražajo realno obnašanje uporabnikov in omogočajo testiranje zmo- gljivosti postopka razpletanja v odvisnosti od števila vsebovanih sej. Po razpletanju smo primerjali podobnost dobljenih sej z originalnimi sestavnimi sejami. Za oce- njevanje podobnosti smo uporabili kriterija popolnega ujemanja in najdaljšega skupnega podzaporedja (WLCS) [15]. Popolno ujemanje je zelo natančna metoda, WLCS pa se izkaže kot zelo uravnotežena metoda. Rezultate ovrednotenja razpleta sej spletne trgovine prikazuje tabela 1. Vrstice označujejo metodo vredno- tenja (popolno ujemanje, WLCS), stolpci tabele pa me- tode razpletanja. Vrednosti v tabeli pomenijo povprečno podobnost med razpletenimi in dejanskimi sejami in se gibljejo med 0 (popolnoma različni) in 1 (popolno ujemanje). Prva vrstica tabele vsebuje povprečno podobnost po metodi popolnega ujemanja. Seje so bodisi popolnoma pravilno razpletene (podobnost zaporedij strani v refe- renčni in razpleteni seji je 1) bodisi napačno razple- tene (podobnost enaka 0). Pri vrednotenju razpletanja po tej metodi že ena sama napačno razporejena stran v uporabniški razpleteni spletni seji pomeni napačen razplet. Povprečna podobnost za popolno ujemanje torej je odstotek vseh razpletenih sej iz množice prepletenih sej, ki so bile popolnoma pravilno razpletene. Rezultat 0.334 torej pomeni, da je bilo 33.4% razpletenih sej po požrešni metodi (Greedy) razpletenih popolnoma pravilno. Podobno velja za metodo preiskovanja prostora stanj s hevristično funkcijo, kjer je bilo popolnoma pra- vilno razpletenih 39.8% sej. Druga vrstica tabele vsebuje rezultate vrednotenja razpletanja po metodi najdaljšega skupnega podzaporedja (angl. WLCS). Rezultat vredno- tenja predstavlja podobnost sej na podlagi najdaljšega skupnega podzaporedja strani v obeh sejah. Torej, če dve seji nimata skupnih strani, je rezultat 0. Če imata dve seji polovico strani zaporedja v istem vrstnem redu, je rezultat 0.5, če pa so vse strani obeh sej v istem vrstnem redu, je podobnost enaka 1. Razpletanje prepletenih sej spletne trgovine je iz- ziv zaradi velikega števila spletnih strani in neenotne vstopne točke. Načrt strani spletnega mesta trgovine je velik, kar pomeni, da obstaja veliko (potencialnih) Tabela 2: Delež kupcev v prepletenih in neprepletenih sejah. seje št. sej št. kupcev % kupcev neprepletene 10353 1751 17 prepletene 9343 2792 30 uporabniških poti po spletnem mestu. Z združevanjem strani v skupine smo zmanjšali število vhodov v mar- kovski model na obvladljivo raven, izgubili pa smo del informacije o individualnih sejah. Poleg tega je vstopna (začetna) stran uporabnika lahko skoraj poljubna stran spletnega mesta (npr. povezave s pasic), kar prinaša težjo identifikacijo začetnih strani v prepletenih sejah. To po- meni, da je kršena predpostavka o popolnosti (angl. ad- missibility), da lahko zanesljivo zaznamo začetne strani. Zato hevristično preiskovanje prostora stanj (RBFS) pogosto daje neoptimalne rešitve. Slika 6 prikazuje podrobne rezultate vrednotenja za obe metodi razpletanja in obe metodi vrednotenja. Vsak graf prikazuje rezultate za eno metodo razpletanja in eno metodo vrednotenja razpletanja. Stolpci predsta- vljajo metode vrednotenja (tj. požrešna in preiskovanje prostora stanj), vrstice pa metode razpletanja (tj. po- polno ujemanje in WLCS). Vsak stolpični diagram je histogram, ki prikazuje porazdelitev rezultatov razpletanj sej. Na osi x so navedeni intervali podobnosti sej, na osi y pa sta navedena število in odstotek razpletenih sej po posameznih intervalih podobnosti. Črtkana črta prikazuje končni rezultat (povprečje podobnosti vseh sej), ki je naveden v tabeli 1. Grafi na sliki 6 poleg končnega rezultata prikazujejo razporeditev podobnosti med referenčnimi in razplete- nimi sejami. Porazdelitev je lahko enako pomembna kot sam končni povprečni rezultat, saj končni rezultat ne pokaže celotne slike. Veliko število razpletenih sej s podobnostjo 0.9 je veliko boljše kot veliko število sej s podobnostjo 0.1. Idealen graf (histogram) rezultata razpletanja bi imel en sam stolpec s podobnostjo vseh razpletenih sej med 0.9 in 1.0. Rezultate razpletanja smo testirali s t-testom za odvi- sne vzorce (parni t-test). Test je pokazal, da je razple- tanje s preiskovanjem prostora stanj (RBFS) statistično značilno boljša metoda razpletanja kot požrešna metoda (p < 0.01). Zanimale so nas tudi značilnosti uporabnikov, ki generirajo prepletene seje. Analizirali smo uporabniške seje, ki smo jih lahko nedoumno identificirali na podlagi uporabnikove prijave. Rezultate analize prikazuje tabela 2, kjer vrstice označujejo vrsto sej. Delež prepletenih sej, ki ga generirajo kupci, je skoraj dvakrat večji od tistih, ki ga generirajo drugi uporabniki. 6 DISKUSIJA IN SKLEP Danes sta na spletu praviloma povsod prisotna sledenje uporabnikom in hranjenje podatkov o njihovih akcijah za 150 POŽENEL, KUKAR 66.6 % 33.4 % 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 1 0 0 0 2 0 0 0 3 0 0 0 4 0 0 0 5 0 0 0 Perfect match, N = 7600 Session similarity N u m b e r o f s e s s io n s [Web shop], greedy R= 0.334 38.7 % 0.6 % 1.9 % 2.9 %3.6 % 4.3 % 4 % 4.4 %3.8 % 35.9 % 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 5 0 0 1 0 0 0 1 5 0 0 2 0 0 0 2 5 0 0 3 0 0 0 WLCS, N = 7600 Session similarity N u m b e r o f s e s s io n s [Web shop], greedy R= 0.504 60.2 % 39.8 % 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 1 0 0 0 2 0 0 0 3 0 0 0 4 0 0 0 Perfect match, N = 7600 Session similarity N u m b e r o f s e s s io n s [Web shop], RBFS R= 0.398 33.9 % 2.4 %3.1 % 3 % 3.2 %3.1 %3.2 %3.5 %3.3 % 41.3 % 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 5 0 0 1 0 0 0 1 5 0 0 2 0 0 0 2 5 0 0 3 0 0 0 WLCS, N = 7600 Session similarity N u m b e r o f s e s s io n s [Web shop], RBFS R= 0.541 Slika 6: Rezultati razpletanja sej spletne trgovine. Uporabili smo dve metodi za merjenje podobnosti med dvema sejama: popolno ujemanje in WLCS. izboljšanje uporabniške izkušnje ali prikazovanje ustre- zne vsebine (npr. oglasov). Za uporabnike je to lahko moteče in sproža čedalje več vprašanj s področja zaščite zasebnosti. Zakonodajalci si prizadevajo ustvariti pravne okvire, ki strogo omejujejo tehnike sledenja. Zato je za razumevanje obnašanja uporabnikov smiselno uporabiti pristope, kot je predlagan v tem članku, ki niso moteči za uporabnika in ne posegajo v njegovo zasebnost. V tem delu smo predstavili metodo za izboljšanje po- stopka obdelave podatkov o klikotoku. Metoda omogoča razpletanje prepletenih spletnih sej. Vključuje uporabo markovske verige prvega reda, načrta spletne strani (angl. web site map) in iskalno strategijo prostora stanj na podlagi hevristike. Predstavili smo motivacijo, delo- vanje metode in ovrednotili metodo v praksi na realnem viru podatkov spletne trgovine. Predlagana hevristika za usmerjanje iskanja se je izkazala za uspešno, saj dosega uporabne rezultate. Metoda samodejno določi najverjetnejše število prepletenih sej, zato jo lahko upo- rabimo ne glede na število sestavnih sej v prepletu. Uporabimo jo lahko za različnie vire podatkov o kliko- toku, vendar lahko pričakujemo boljše rezultate za dobro definirane uporabniške seje z manj vstopnimi točkami v sistem. Predstavljena hevristična metoda iskanja deluje po načelu iskanja najverjetnejšega zaporedja strani, kar pa ni vedno ustrezno (seje z manj verjetnimi prehodi med stranmi). Predlagan pristop je koristen za poglobitev ozaveščenosti o obstoju prepletenih spletnih sej, ki so značilne za napredne spletne uporabnike. Z razpletanjem takšnih sej izboljšamo kakovost podatkov o klikotoku za to pomembno skupino uporabnikov. Rezultati kažejo, da na podlagi strukture spletne strani in številke IP kot identifikatorja uporabnika verno razpletemo velik del prepletenih sej. Predpostavka našega pristopa je, da pričakujemo pra- vilno identifikacijo začetnih strani. Če začetne strani ni mogoče dovolj dobro določiti, hevristična funkcija teži k pesimističnemu ocenjevanju. V posebnih (večinoma realnočasovnih) primerih lahko pesimistične hevristične ANALIZIRANJE OBNAŠANJA UPORABNIKOV NA SPLETU 151 funkcije premagajo optimistične (popolne) [22], [23]. V velikih prostorih stanj (kot je naš) je pogosto bolje imeti dobro pesimistično hevristično funkcijo kot skoraj neinformativno optimistično. Tak primer je tudi sple- tna trgovina, kjer so začetne strani samo verjetnostno določene, kljub temu pa še vedno dobimo koristne rezultate. Najbolj spodbuden rezultat je nedvomno ugotovitev, da bodo uporabniki, ki generirajo prepletene seje, z dvakrat večjo verjetnostjo kaj kupili v primerjavi s tistimi, ki takih sej ne generirajo. To pomeni, da je lahko že zaznavanje vzporednega brskanja uporabnikov uporabno in podlaga za nadaljnjo prilagoditev vsebine spletnih strani.