Elektrotehniški vestnik 86(3): 144-151, 2019 Izvirni znanstveni članek
Analiziranje obnašanja uporabnikov na spletu brez sledenja stanja (z uporabo prstnega odtisa)
Marko PoZenel, MatjaZ Kukar
Univerza v Ljubljani, Fakulteta za računalništvo in informatiko, VeČina pot 113, 1000 Ljubljana, Slovenija E-pošta: marko.pozenel@fri.uni-lj.si, matjaz.kukar@fri.uni-lj.si
Povzetek. Razumevanje obnašanja uporabnikov spletnega mesta je ključen del nenehnega izboljševanja spletnega mesta in uporabniške izkušnje. Pri beleZenju uporabnikovih akcij lahko trčimo v zakonske omejite, kot sta zakon o varovanju osebnih podatkov in GDPR. Zato je pomembno, da uporabimo pristop, kije nevsiljiv za uporabnika in omogočša anonimno belezšenje akčij uporabnika. Pogosto se kot vir za analizo obnasšanja uporabnikov na spletnem mestu uporablja dnevnik spletnega streznika. Pri tem imamo lahko zaradi slabe strukturiranosti podatkov tezave s kakovostjo pridobljenih končnih uporabniških sej. V članku smo predstavili pristop, ki se ukvarja z enim izmed izzivov v fazi preoblikovanja podatkov, izzivom prepletenih sej. To so seje, kijih določen uporabnik generira s sočasnim brskanjem v več oknih ali zavihkih brskalnika po istem spletnem mestu. Takšne seje kvarno vplivajo na kakovost podatkov in jih je treba analizirati in razplesti. Predstavili smo dva pristopa za razpletanje, ki temeljita na markovskem modelu in preiskovanju prostora stanj. Predstavljena pristopa smo preizkusili na podatkih spletne trgovine. Rezultati kazejo, da lahko na podlagi številke IP in strukture spletne strani verodostojno razpletemo velik del prepletenih sej.
Ključne besede: klikotok, razpletanje sej, hevristično preiskovanje, markovske verige, obnašanje uporabnikov
Analyzing the user browsing behaviour using stateless tracking
Understanding the user' browsing behaviour is a key part of continuous website improvement that enables the delivery of a better user experience. However, identification and tracking a user can violate the legal issues and privacy concerns. It is therefore important to use an approach that is user-unobtrusive and assures anonymous tracking of his/her actions. As a result, the clickstream data obtained from the Web server log files is often used as the main source of data for the user behaviour analysis. However, the data in the Web log files are more or less inadequately structured and therefore eventually leading to an erroneous session reconstruction. In the paper we present an interleaved Web session reconstruction that improves the data quality in the data transformation phase. An interleaved session is a session generated by a particular user concurently browsing the same web site using multiple browser windows or tabs. Such sessions have a detrimental impact on the data quality and have to be analyzed and separated. We propose two approaches for separating interleaved sessions based on the first-order Markov chains and state-space search. The proposed approaches are evaluated on a real-world clickstream data source of a Web shop. The results show that a large amount of the interleaved sessions can be successfully separated on the basis of the IP number and web-site structure.
Keywords: clickstream, session reconstruction, heuristic search, Markov chains, user behaviour
Prejet 19. marec, 2018 Odobren 23. april, 2019
1 Uvod
Svetovni splet je postal eden najpomembnejših virov informacij, tako za zasebne kot tudi za poslovne uporabnike. Omogoča skoraj neomejeno izmenjavo podatkov med različnimi strankami. Podjetja uporabljajo spletne strani za oglaševanje in prodajo svojih izdelkov, institucije za zagotavljanje informacij o svojih storitvah, posamezniki pa za ucšinkovit dostop do razlicšnih virov informacij. Blogi in socialna omrezja pridobivajo na popularnosti in so ze prerasla mejo zasebnega objavljanja. Vedno vec ljudi za pridobivanje novic namesto tradicionalnih medijev uporablja druzabna omrezja [17]. Obstojece spletne strani se vsako leto soocajo z vec in cedalje boljšimi tekmeci. Vse tezje je pritegniti nove stranke in obdrzati obstojece. V takšnih okolišcinah bodo prezšivele le spletne strani, ki izcšrpno razumejo potrebe svojih strank in njihovo obnašanje na spletni strani. Posledicno je analiziranje vedenja uporabnikov postalo sestavni del analize spletnih podatkov. Pomembno vlogo ima tako pri vsakodnevnih kot tudi stratesških odlocšitvah. Kakovost odkritih vzorcev obnašanja uporabnikov je zelo odvisna od kakovosti pridobljenih in obdelanih podatkov.
Vedno vec tretjih oseb belezi in analizira vedenje uporabnikov na spletu. Po drugi strani pa uporabniki ne zelijo sledenja. Nasprotovanje uporabnikov sledenju sta v svojem clanku predstavila Mayer in Mitchell [16]. Tehnologije 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 navadne piškotke in piškotke HTML5, sledenje geolokaciji in piškotke raznih vticnikov (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 prevec vsiljivo, saj uporabnik ne ve, da je predmet proucevanja, niti se mu ne more izogniti.
Eden glavnih virov podatkov za izvedbo analize obnasšanja uporabnikov na spletnih straneh so dnevnisške datoteke spletnega streznika (angl. web server log files). Dnevniki spletnih streznikov so integralni del spletnih streznikov, vendar prvotno niso bili namenjeni analizi obnašanja uporabnikov. Vsebujejo le omejene, vcasih pomanjkljive podatke, njihova vsebina pa ni vedno jasno dolocena. V clanku se ukvarjamo z enim izmed izzivov analize podatkov iz tega vira, prepletenimi uporabniškimi sejami. Predstavili bomo sorodne pristope in predlagali novo tehniko za izboljšanje kakovosti informacij, ki jih pridobimo iz prepletenih sej.
Dnevnisške datoteke spletnega strezšnika so najpogostejši in najprimernejši vir podatkov o klikotoku (angl. clickstream) [13]. Klikotok je zaporedje dejanj (klikov), ki jih uporabnik naredi med brskanjem po dolocenem spletnem mestu. Ker je vir podatkov o klikotoku praviloma na voljo, so podatki o klikotoku glavni vir podatkov za analizo obnašanja uporabnikov [27], [2]. Spiliopoulou in sod. [26] so dnevnik spletnega streznika formalno definirali kot:
Naj mnozica U oznacuje vse mogoce spletne zahteve (angl. Web requests) na spletnem mestu. Ta mnozica vsebuje tako staticne strani kot tudi strani, ki jih je mogocše dinamicšno generirati glede na vhodne parametre. Dnevnik spletnega streznika L je seznam zahtev strani iz mnozšice U vseh uporabnikov. Zapisi v seznamu L so urejeni po casovni oznaki zahteve.
Dnevniki spletnega streznika so bili sprva namenjeni za razhrošcevanje spletnih streznikov in ne kot vir podatkov za analize. Zato v dnevnikih spletnih strezšnikov pogosto manjkajo nekateri kljucšni podatki za pridobitev vzorcev obnasšanja uporabnikov, posledica tega pa so dolocene tezave z razpolozljivostjo in kakovostjo podatkov [13]. Podatki o klikotoku, pridobljeni iz dnevnikov spletnih strezšnikov, so zato lahko nepopolni, vsebujejo šum in ne morejo popolnoma verno zajeti obnašanja uporabnika po spletnem mestu. Zato sta cišcenje in priprava podatkov zahtevna in nagnjena k napakam.
Pri uporabi dnevnikov spletnega streznika kot vir podatkov lahko naletimo na vrsto tezav. Kljub temu zaradi široke dostopnosti in nevsiljivosti ostajajo eden privlacnih virov podatkov. Namenski sistem za prijavo uporabnikov, prilagojen za doloceno spletno aplikacijo,
je seveda veliko boljša rešitev. Vendar taka rešitev zahteva znatne finančne, računalniške in človeške vire. Poleg tega je treba načrtovati dovolj vnaprej, da pravočasno zberemo Zelene količine podatkov o obnašanju uporabnikov, tako na streZniški strani kot na strani odjemalča. Takšen način zbiranja podatkov lahko povzroča tudi zakonske tezave zaradi zasebnosti podatkov (npr. pomisleki glede uporabe piškotkov [12], [25]). Z uporabo izključšno dnevnika spletnega strezšnika se izognemo tem tezavam, saj je belezenje dostopov sestavni mehanizem spletnega strezšnika, relativno nezahteven za vire, na voljo pa je ogromna količina ze zbranih zgodovinskih podatkov. Zato večšina sštudij analize spletnih uporabnikov uporablja kot vir za podatke dnevnik spletnega streznika [3], [29].
2 Pregled področja
Uporabniško sejo sestavlja zaporedje akčij, ki jih uporabnik izvede med brskanjem po spletnem mestu v določenem časovnem obdobju. Podatki o sejah se največkrat v razpršeni obliki belezijo v dnevniške datoteke. Pri rekonstrukčiji sej podatke pretvorimo v obliko, ki je primerna za nadaljnjo uporabo [5], [21].
Verna rekonstrukčija 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-konstrukčije sej [6], [7] identifičiramo uporabnike na podlagi dnevnikov brez uporabe drugih podatkov z odje-malča (npr. pisškotki). V takem primeru bodo uporabniki, ki so skriti za streznikom proxy ali pa sočasno uporabljajo 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 rekonstrukčijo sej so soočamo s pomanjkanjem nekaterih podatkov (npr. identifikator seje), zato se posluzšujemo različšnih hevri-stičšnih pristopov. Izzivi, na katere naletimo pri uporabi te metode, so:
•	Identifikačija posameznih uporabnikov. Identifika-čija uporabnika glede na naslov IP je lahko netočna. Izboljšamo jo lahko z vključitvijo podpisa brskalnika (atribut user-agent) v dnevnik [6]. Mehanizmi, ki posegajo v zasebnost uporabnika, zaradi zasščšite zasebnosti niso zaželeni [16].
•	Identifikačija spletnih sej iskalnih robotov, še zlasti, če spletni dnevnik ne hrani podpisa brskalnika. Identifičiramo jih lahko na podlagi njihovega podpisa v atributu user-agent, preverbo naslova IP v podatkovni zbirki spletnih robotov ali drugih značilnostih [18].
•	Verna rekonstrukčija aktivnosti posameznih uporabnikov, kjer so posamezne zahteve dodeljene pravim uporabnikom. V literaturi so bile predlagane različšne hevristike: čšasovno usmerjena hevristika [6], navigačijsko usmerjena hevristika [7], pristop
146
POŽENEL, KUKAR
z uporabo linearne optimizacije (angl. Integer programming) [8], uporaba navigacijskih zaporedij [1].
•	Obravnavanje uporabe gumba za nazaj v brskalniku. Akcija nazaj se ne zabelezi nujno v dnevniški datoteki spletnega streznika [9], [18]. Manjkajoči zapisi v dnevnisški datoteki pa lahko negativno vplivajo na rekonstrukcijo sej in lahko povzročijo nepravilno rekonstrukcijo sej.
•	Vzporedno brskanje v vec zavihkih brskalnika [11], [19]. Postopek rekonstrukcije sej mora upoštevati scenarij, v katerem ima uporabnik odprtih vecš zavihkov ali oken brskalnika za brskanje po istem spletnem mestu. Ža uporabnika vsak zavihek obicajno pomeni loceno uporabniško sejo. Takšno obnasšanje je pogosto za napredne uporabnike in povzroca prepletene seje. Ker se spletni streznik ne zaveda razlicnih zavihkov, se take seje na strezniš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 dinamicnim 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-stojeco rešitev. Ena od aktivnih strategij je tudi uporaba sistemov za sledenje tretjim osebam (orodje Web Analytics, 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 obicajno pošiljajo na spletno mesto tretje osebe, kjer se obdelujejo in analizirajo [1]. Uporaba storitev tretjih oseb poleg vrednosti prinaša tudi pomisleke glede zasebnosti. Spletni uporabniki so namrecš cedalje manj naklonjeni uporabi piškotkov, posredovanju podatkov tretjim osebam in uporabi njihovih vzorcev brskanja za namene oglaševanja [16]. Žato 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 omogoca ucinkovito razpletanje prepletenih sej.
3 Predstavitev podatkov
Predobdelani podatki zajemajo podatke o klikotoku, zdruzenih v uporabniške seje, in nacrt spletnega mesta.
Načrt spletnega mesta je graf spletnih strani iz mnozice U, ki so dostopni uporabnikom in med sabo povezani s hiperpopezavami. Neposredna povezava med spletnima stranema x¿ in xj v nacrtu pomeni vecjo verje-
tnost prehoda uporabnika med tema dvema stranema, kot če neposredne povezave ni. Nacrt 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 = [xi ,x2,...,xk ],	(1)
kjer stran xi 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, pridobljenih iz preteklih uporabniških sej. Surove podatke o klikotoku iz dnevnika spletnega strezšnika je treba preoblikovati v obliko, primerno za nadaljnjo obdelavo. Vsaka uporabniška seja v klikotoku je predstavljena kot zaporedje zahtevanih strani. Klikotok lahko preoblikujemo v graf, kjer vsaka uporabnisš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 mnoziče U, in postopoma dodajamo povezave glede na prehode v uporabniških sejah. Ce uporabljamo predznanje (npr. načšrt spletnega mesta), začšnemo z grafom, 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 povezemo ustrezni dve vozlišči ni in ni+1 v grafu in nastavimo utez povezave w(ni;ni+1). Ce sta vozlišči ni in ni+1 ze povezani, samo ustrezno posodobimo utez povezave w(ni;ni+1). Več ko je poti v grafu, ki si deli odsek poti ni ^ ni+1, večja je utez w(ni , ni+1). Ko graf posodobimo s podatki vseh uporabnisških sej, dobimo utezšen graf, ki ustreza kliko-toku. Utezšene poti grafa lahko uporabimo za izračšun verjetnosti prehoda med sosednjimi vozlisščši. Vsako vozlišč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 modeliranje časovno odvisnih zaporednih problemov. Lahko jih uporabimo za napovedovanje najverjetnejsšega naslednjega stanja, izračun verjetnosti opazovanega zaporedja ali za iskanje najverjetnejšega zaporedja.
Markovska veriga je definirana kot zaporedje naključnih spremenljivk, s0, s1, s2, ..., ki imajo mar-kovsko lastnost. To pomeni, da je prihodnost pogojno neodvisna od preteklosti. Markovsko verigo lahko uporabimo 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
p = 0.2
p = 0.4
p = 0.9
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
no ^ n2 ^ na ^ 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 prikazuje markovsko verigo spletnega mesta.
4 Metoda razpletanja
V naših zgodnejših poskusih smo razvili osnovno metodo 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 xH ^ 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 pozšresšno iskanje lokalno optimalne resšitve v prostoru stanj.
Obstaja veliko pristopov za iskanje resšitev v prostoru stanj. Osnovni iskalni strategiji sta iskanje v globino in iskanje v sirino. Iskanje v globino ima linearno pomnilnisško zahtevnost glede na dolzšino poti, vendar ne najde nujno resšitve. Iskanje v sširino preisščše čelo-ten prostor stanj, zato vedno najde vse resšitve in tudi optimalno. Pomanjkljivost iskanja v sširino je velika prostorska zahtevnost, ker mora v pomnilniku hraniti vsa vozlisščša, da lahko generira vozlisščša na naslednji ravni. Ce je na voljo znanje o problemski domeni, ki lahko usmerja iskanje, lahko uporabimo metode informiranega iskanja, kot je na primer best-first searčh [4], ki iskanje usmerja v smeri najbolj perspektivnega vozlisščš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 vozlisščša (stanja) ustrezajo resšitvam delnih problemov, povezave med vozlisščš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). Prehodom med stanji lahko pripisšemo čeno. V nasšem primeru nas zanimajo resšitve z minimalno čeno. 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 problem iskanja v prostoru stanj. Vsako stanje Z pomeni prepleteno sejo
S/ = [xi,X2, ...,x„] z dolzino n z r delno razpletenimi sejami SS,
Z
([sS1) ,
S
(2)
■ sSr)],
S/ >
= ([(x


7(1)
7(1)
S S(r) S(r) X1 , x2 , • • • , xb )], (xj, xj + 1, • • • , xn)>,
kjer sSS) pomeni i-to delno razpleteno sejo, S/ prepleteno sejo (razpleteno do elementa xH) in xk stran v seji. Začšetno stanje je predstavljeno kot
Zs = ([], (xi,x2, • • • ,x„)>
s praznim seznamom na začetku, kar pomeni, da nimamo še nobenih delno razpletenih sej, in zaporedjem strani, ki pomeni čelo prepleteno sejo. Ce imamo prepleteno sejo z dolzino n, lahko razpletanje vrne največ n razpletenih sej. Ce domnevno prepletena seja sploh ni prepletena, dobimo eno samo razpleteno sejo.
Pri razpletanju se premikamo med stanji po povezavah, ki imajo pozitivne utezi (čena). Prehod iz stanja v sosednje stanje ustreza bodisi dodeljevanju naslednje strani prepletene seje eni od delno razpletenih sej ali začetku nove razpletene seje. Akčije dodeljevanja strani ne moremo razveljaviti, poslediča pa je velik prostor stanj v obliki drevesa. Število naslednikov vsakega vo-zlisščša je odvisno od sštevila začšetih razpletenih sej v trenutnem vozlisščšu. Vsak prehod dodeli naslednjo stran prepletene seje xci na koneč ene izmed delno razpletenih
(r+1)
sej SS ali pa začne novo sejo S S . Slika 2 prikazuje primer dveh stanj Z1 in Z2 in akčije, ki označuje prehod med stanjema.
@
z2
Slika 2: Primer prehoda med dvema stanjema v nasšem prostoru stanj. Zaporedje nad črtkano črto pomeni prepleteno sejo. Krepko napisane strani so ze bile dodeljene delno razpletenim sejam pod črtkano črto. Akčija doda naslednjo stran prepletene seje x8 na koneč druge razpletene seje.
S
S
S
x
x
1
2
a
148
POŽENEL, KUKAR
Primer prehoda med dvema državama v našem iskalnem 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 konča druge ločene seje.
4.2 Hevristično preiskovanje
Ce želimo razplet prepletene seje, daje produkt verjetnosti prehodov med stranmi največji, moramo načeloma preiskati čeloten prostor stanj. Skupno število vozlišč drevesa stanj ž n nivoji je enako J2 n=0 B in raste eksponentno v odvisnosti od v n. Preiskovanje vseh poti v drevesu stanj je časovno izjemno potratno zaradi eksponentnega večanja alternativ na vsakem nivoju drevesa, kar kliče po uporabi problemsko spečifične hevristike. Namen hevrističnega iskanja je s pomočjo funkčije f(Z) = g(Z) + h(Z) ovrednotiti, katera vozlišča mnoziče kandidatov so najbolj obetavna, in naprej iskati v smeri najbolj obetavnega. Pri tem h(Z) pomeni hevristično očena obetavnosti vozlišča in g(Z) čeno najkrajše poti od začetnega vozlišča do vozlišča Z. Zaradi linearne prostorske zahtevnosti smo uporabili prostorsko učinkovito implementačijo algoritma A* -algoritem rečursive best-first searčh (RBFS) [14].
4.2.1	Dopustnost hevristične funkcije: je zazelena lastnost hevristične očenjevalne funkčije. Naj za vsako vozlišče Z v prostoru stanj velja, da je h* (Z) čena optimalne poti od vozlišča Z do čiljnega vozlišča. Izrek o popolnosti trdi, da je hevristična funkčija dopustna (optimistična), če za vsa vozlišča Z v prostoru stanj velja
h(Z) < h*(Z).
Ko pri iskalnih algoritmih iz druzine A* (vključno RBFS) za usmerjanje iskanja uporabimo dopustno he-vristično funkčijo, iskalni algoritmi vedno najdejo optimalno rešitev (najčenejšo pot) [22]. Nedopustne (pesimistične) hevristične funkčije ne zagotavljajo iskanja optimalnih rešitev, lahko pa delujejo hitreje [4].
4.2.2	Hevristicna funkcija za razpletanje: Za problem razpletanja prepletenih sej nas zanima čiljno vo-zlisščše, ki maksimira produkt verjetnosti prehodov med stranmi v vseh razpletenih sejah. Dopustna hevristična funkčija h(Z) mora optimistično očeniti razplet preostalega dela prepletene seje. Maksimirati mora produkt verjetnosti prehodov med stranmi (ali enakovredno, zmanjšati vsoto njihovih negativnih logaritmov), ki še niso bile razporejene delno razpletenim sejam.
Trivialna dopustna hevristična funkčija za problem razpletanja sej, je kar
max{ P(? —> x) }
ho (Z) = 1 * 1 * ... * 1 = 1
(2)
Z3 xJ xj x, x, x, x,J x,
Slika 3: Vozlišče Z3 hrani stanje delno razpletene prepletene seje.
Oglejmo si sliko 3, ki prikazuje vozlišče Z3. Prepletena seja je delno razdeljena na dve začšeti razpleteni seji, kot prikazuje slika 4. Prvo stran prepletenega dela (stran x4) lahko bodisi dodamo na koneč ene izmed delno razpletenih sej bodisi začnemo novo razpleteno sejo. Ko računamo vrednost max{P(? ^ xj)}, ne smemo uposštevati vseh strani v razporejenem delu, ampak samo zadnjo stran vsakega delno razpletenega dela. Pri vozlišču Z3 in dodelitve strani x4 je izračun enak:
max{P(? ^ x4)} = max{P(x0 ^ x4), P(xi ^ x4)}
prepletena seja
X3	Xo	Xi	X4	X6	X17	X2
X3	Xo	X4
Xi	X4	
Slika 4: Delno razpletena prepletena seja. Naslednjo nerazporejeno stran prepletene seje (x4) lahko dodamo na koneč enega od začetih delnih razpletov.
Pri izračunu vrednosti hevristične funkčije moramo upoštevati vse strani, ki se v še nerazpletenem delu prepletene seje nahajajo pred stranjo xj. Postopek za izračun izraza max{P(? ^ xž)} je prikazan na sliki 5. Hevristika h je dopustna pod pogojem, da lahko nedvoumno določimo začetne strani razpletenih sej. Ce ta pogoj ni izpolnjen, bo rezultat morda vseboval prevečš razpletenih sej. Pokazalo se je, da je predstavljena hevristična funkčija 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.
maksimum
			--*-N		
				Xi	
.........................					
Taka hevristična funkčija bi obravnavala vsa vozlišča enako, vendar ne bi pripomogla k smiselnemu usmerjanju iskanja. Za dobro vodenje mora biti h(Z) čim blize h* (Z). Dopustna hevristična funkčija h, ki ponuja dobro usmerjanje, je predstavljena v nadaljevanju.
nerazpleteni del zaključna stanja delno razpletenih sej
Slika 5: Izračun izraza max {P xi)} hevristične funkčije
S
(2)
S
S
ANALIZIRANJE OBNAŠANJA UPORABNIKOV NA SPLETU
Tabela 1: Rezultati razpletanja sej na podlagi podatkov spletne trgovine
Metoda vrednotenja	Požrešno RBFS
Popolno ujemanje WLCS	0.334 0.398 0.504 0.541
5 Rezultati
Umetno generirana množica prepletenih sej je sestavljena iz različnega števila preverjenih, Čistih sej. Tretjina 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 zmogljivosti postopka razpletanja v odvisnosti od števila vsebovanih sej. Po razpletanju smo primerjali podobnost dobljenih sej z originalnimi sestavnimi sejami. Za oče-njevanje podobnosti smo uporabili kriterija popolnega ujemanja in najdaljšega skupnega podzaporedja (WLCS) [15]. Popolno ujemanje je zelo natančna metoda, WLCS pa se izkazše kot zelo uravnotezšena metoda.
Rezultate ovrednotenja razpleta sej spletne trgovine prikazuje tabela 1. Vrstiče označujejo metodo vrednotenja (popolno ujemanje, WLCS), stolpči tabele pa metode 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 vrstiča tabele vsebuje povprečno podobnost po metodi popolnega ujemanja. Seje so bodisi popolnoma pravilno razpletene (podobnost zaporedij strani v referenčni in razpleteni seji je 1) bodisi napačno razpletene (podobnost enaka 0). Pri vrednotenju razpletanja po tej metodi ze 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 mnoziče prepletenih sej, ki so bile popolnoma pravilno razpletene. Rezultat 0.334 torej pomeni, da je bilo 33.4% razpletenih sej po pozrešni metodi (Greedy) razpletenih popolnoma pravilno. Podobno velja za metodo preiskovanja prostora stanj s hevristično funkčijo, kjer je bilo popolnoma pravilno razpletenih 39.8% sej. Druga vrstiča tabele vsebuje rezultate vrednotenja razpletanja po metodi najdaljšega skupnega podzaporedja (angl. WLCS). Rezultat vrednotenja predstavlja podobnost sej na podlagi najdaljšega skupnega podzaporedja strani v obeh sejah. Torej, če dve seji nimata skupnih strani, je rezultat 0. Ce imata dve seji polovičo 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 izziv zaradi velikega sštevila spletnih strani in neenotne vstopne točke. Načrt strani spletnega mesta trgovine je velik, kar pomeni, da obstaja veliko (potenčialnih)
149
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 zdruzevanjem strani v skupine smo zmanjšali število vhodov v mar-kovski model na obvladljivo raven, izgubili pa smo del informačije o individualnih sejah. Poleg tega je vstopna (začšetna) stran uporabnika lahko skoraj poljubna stran spletnega mesta (npr. povezave s pasič), kar prinaša tezjo identifikačijo začetnih strani v prepletenih sejah. To pomeni, da je kršena predpostavka o popolnosti (angl. admissibility), 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. Stolpči predstavljajo metode vrednotenja (tj. pozrešna in preiskovanje prostora stanj), vrstiče pa metode razpletanja (tj. popolno 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 pokaze čelotne 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 stolpeč s podobnostjo vseh razpletenih sej med 0.9 in 1.0.
Rezultate razpletanja smo testirali s t-testom za odvisne vzorče (parni t-test). Test je pokazal, da je razpletanje s preiskovanjem prostora stanj (RBFS) statistično značilno boljša metoda razpletanja kot pozreš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 identifičirali na podlagi uporabnikove prijave. Rezultate analize prikazuje tabela 2, kjer vrstiče označujejo vrsto sej. Delez prepletenih sej, ki ga generirajo kupči, 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 akčijah za
150
POŽENEL, KUKAR
[Web shop], greedy
Perfect match, N = 7600
-1-1-n—i-1-1-1-1-1-r
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Session similarity
[Web shop], greedy
WLCS, N = 7600
3.6 %4.3 % 4 % 4.4 %3.8 %
_ R= 0.504 _
T-1-1-1-1-r—i-1-1-1-r
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Session similarity
[Web shop], RBFS
Perfect match, N = 7600
T-1-1-1-i-1-1-1-T
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8
Session similarity
[Web shop], RBFS
WLCS, N = 7600
24 %3.1 % 3 % 3.2 %3.1 %3.2 %3.5 %3.3 %
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Session similarity
Slika 6: Rezultati razpletanja sej spletne trgovine. Uporabili smo dve metodi za merjenje podobnosti med dvema sejama: popolno ujemanje in WLCS.
35.9 %
33.4 %
1.9 %
0.6 %
33.9 %
39.8 %
0.9 1
izboljšanje uporabniške izkušnje ali prikazovanje ustrezne vsebine (npr. oglasov). Za uporabnike je to lahko moteče in sproza č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 obnasšanja uporabnikov smiselno uporabiti pristope, kot je predlagan v tem cšlanku, ki niso motecši za uporabnika in ne posegajo v njegovo zasebnost.
V tem delu smo predstavili metodo za izboljšanje postopka 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 motivačijo, delovanje metode in ovrednotili metodo v praksi na realnem viru podatkov spletne trgovine. Predlagana hevristika za usmerjanje iskanja se je izkazala za uspesšno, saj dosega uporabne rezultate. Metoda samodejno določši najverjetnejše število prepletenih sej, zato jo lahko uporabimo ne glede na sštevilo sestavnih sej v prepletu.
Uporabimo jo lahko za razlicnie vire podatkov o klikotoku, 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 taksšnih sej izboljsš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 pravilno identifikačijo začetnih strani. Ce začetne strani ni mogoče dovolj dobro določiti, hevristična funkčija tezi k pesimističnemu očenjevanju. 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 nas) je pogosto bolje imeti dobro pesimistično hevristično funkcijo kot skoraj neinformativno optimistično. Tak primer je tudi spletna trgovina, kjer so začetne strani samo verjetnostno določene, kljub temu pa se 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 Ze zaznavanje vzporednega brskanja uporabnikov uporabno in podlaga za nadaljnjo prilagoditev vsebine spletnih strani.
Literatura
[1]	Murat Ali Bayir, Ismail Hakki Toroslu, Murat Demirbas and Ahmet Cosar. Disčovering better navigation sequenčes for the session čonstručtion problem. Data & Knowledge Engineering, 73:58-72, 2012.
[2]	Fabričio Benevenuto, Tiago Rodrigues, Meeyoung Cha and Virgflio Almeida. Charačterizing user navigation and interačtions in online sočial networks. Information Sciences, 195:1-24, 2012.
[3]	B. Berendt, B. Mobasher, M. Nakagawa and M. Spiliopoulou. The impačt of site stručture and user environment on session rečonstručtion in Web usage analysis. In WEBKDD - KDD Workshop on Web Mining and Web Usage Analysis, pages 159179, 2002.
[4]	I. Bratko. Prolog Programming for Artificial Intelligence. Pearson Addison-Wesley, Harlow, England, 3. edition, 2000.
[5]	V Chitraa, Dr. Davamani and Antony Selvdoss. A survey on prepročessing methods for web usage data. arXiv preprint arXiv:1004.1257, 2010.
[6]	R. Cooley, B. Mobasher and J. Srivastava. Data Preparation for Mining World Wide Web Browsing Patterns. Knowledge and Information Systems, 1(1):5-32, 1999.
[7]	Robert Cooley, Pang-Ning Tan and Jaideep Srivastava. Disčovery of interesting usage patterns from web data. In Web Usage Analysis and User Profiling, pages 163-182. Springer, 2000.
[8]	Robert F Dell, Pablo E Roman and Juan D Velasquez. Web user session rečonstručtion using integer programming. In Proceedings of the 2008 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology-Volume 01, pages 385-388. IEEE Computer Sočiety, 2008.
[9]	Robert F. Dell, Pablo E. Roman, and Juan D. Velasquez. Web user session rečonstručtion with bačk button browsing. In International Conference on Knowledge-Based and Intelligent Information and Engineering Systems, pages 326-332. Springer, 2009.
[10]	Yongjian Fu and Ming-Yi Shih. A framework for personal web usage mining. In International Conference on Internet Computing, pages 595-600, 2002.
[11]	J. Huang and R. W. White. Parallel browsing behavior on the Web. In Proceedings of the 21st ACM conference on Hypertext and hypermedia, pages 13-18. ACM, 2010.
[12]	Sylvia Merčado Kierkegaard. How the čookies (almost) črum-bled: Privačy & lobbyism. Computer Law & Security Review, 21(4):310-322, 2005.
[13]	R. Kohavi. Mining e-čommerče data: The good, the bad, and the ugly. In Foster Provost and Ramakrishnan Srikant, editors, Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, volume 2035, page 2, 2001.
[14]	R. E. Korf. Linear-spače best-first searčh. Artificial Intelligence, 62(1):41-78, 1993.
[15]	C-Y. Lin and F. J. Očh. Automatič evaluation of mačhine translation quality using longest čommon subsequenče and skip-bigram statističs. In ACL '04: Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics, page 605,
Morristown, NJ, USA, 2004. Association for Computational Linguistics.
[16]	Jonathan R. Mayer and John C. Mitchell. Third-party web tracking: Policy and technology. In 2012 IEEE Symposium on Security and Privacy, pages 413-427. IEEE, 2012.
[17]	Sharon Meraz. Is there an elite hold? traditional media to social media agenda setting influence in blog networks. Journal of Computer-Mediated Communication, 14(3):682-707, 2009.
[18]	Michal Munk, Jozef Kapusta and Peter Svec. Data preprocessing evaluation for web log mining: reconstruction of activities of a web visitor. Procedia Computer Science, 1(1):2273-2280, 2010.
[19]	Ashwin Paranjape, Robert West, Leila Zia and Jure Leskovec. Improving website hyperlink structure using server logs. In Proceedings of the Ninth ACM International Conference on Web Search and Data Mining, pages 615-624. ACM, 2016.
[20]	Marko Pozenel, Viljan Mahnic and Matjaz Kukar. Separating Interleaved HTTP Sessions Using a Stochastic Model. Informatica, 34:199-205, 2010.
[21]	Marko Pozenel, Viljan Mahnic and Matjaz Kukar. Separation of interleaved web sessions with heuristic search. In 2010 IEEE International Conference on Data Mining, pages 411-420. IEEE, 2010.
[22]	Aleksander Sadikov and Ivan Bratko. Pessimistic heuristics beat optimistic ones in real-time search. In Proceedings of the 2006 Conference on ECAI2006: 17th European Conference on Artificial Intelligence August 29 — September 1, 2006, Riva Del Garda, Italy, volume 141, pages 148-152, Amsterdam, The Netherlands, The Netherlands, 2006. IOS Press.
[23]	Aleksander Sadikov and Ivan Bratko. LRTA* works much better with pessimistic heuristics. In Proceedings of the ECAI 2008: 18th European Conference on Artificial Intelligence, pages 897898, Amsterdam, The Netherlands, The Netherlands, 2008. IOS Press.
[24]	C. Shahabi, F. Banaei-Kashani and J. Faruque. A framework for efficient and anonymous web usage mining based on client-side tracking. Lecture Notes in Computer Science, 2356:113-144, 2002.
[25]	Edith G. Smit, Guda Van Noort and Hilde A. M. Voorveld. Understanding online behavioural advertising: User knowledge, privacy concerns and online coping behaviour in europe. Computers in Human Behavior, 32:15-22, 2014.
[26]	M. Spiliopoulou, B. Mobasher, B. Berendt and M. Nakagawa. A framework for the evaluation of session reconstruction heuristics in Web-usage analysis. INFORMS Journal on Computing, 15(2):171-190, 2003.
[27]	I. H. Ting, C. Kimble and D. Kudenko. A pattern restore method for restoring missing patterns in server side clickstream data. In Web Technologies Research and Development - APWeb 2005, volume 3399, pages 501-512. Springer-Verlag GmbH, March 2005.
[28]	M. Viermetz, C. Stolz, V. Gedov and M. Skubacz. Relevance and impact of tabbed browsing behavior on web usage mining. In Proceedings of the 2006 IEEE/WIC/ACM International Conference on Web Intelligence, pages 262-269, Dec. 2006.
[29]	J. Zhang and A. A. Ghorbani. The reconstruction of user sessions from a server log using improved time-oriented heuristics. In Communication Networks and Services Research, 2004. Proceedings. Second Annual Conference on, pages 315-322, May 2004.
Marko Poženel je asistent na Fakulteti za računalništvo in informatiko. Doktoriral je leta 2010 s področja računalništva. Njegovo področje raziskovanja vključuje tehnologije programske opreme, agilne metode razvoja programske opreme, podatkovno rudarjenje spletnih podatkov in analizo obnašanja uporabnikov na spletu.
Matjaž Kukar je izredni profesor na Fakulteti za računalništvo in informatiko Univerze v Ljubljani. Njegovi raziskovalni interesi vključujejo strojno učenje, odkrivanje zakonitosti v podatkih na splošno, analizo ROC, očenjevanje zanesljivosti, odkrivanje zakonitosti v prostorsko-čšasovnih podatkih, tehnologije upravljanja velikih podatkov kot tudi aplikačije v medičinskem in poslovnem okolju.