tt7
VE B-L OG-M I N ER: APLI KASI PENGENALAN POLA NAVI GASI PENGGUNASITUS\TEBYANGDIDASARKANPADA MODEL HY"ERTDff PROBABILISTIC GRAMMAR Arif Djunaidy, Febriliyan Samopa, dan Sugianto Hdim$ .4BSTRAK maTPu menemukan \fakalah ini membahasdesaindan implementasidari perangkatlunak VeblogMinel.yalg Grammar (HPG)' Probabilistic. Hye*ext web situs ytode.l ,,.r"t,, p"d" poia-polanavigasipengguna 'Drl"-.rrggon^k"r, sebagaisebuahstring yang.disertai dengan nilai *od.l-ini,^sebuah lintasan navigasidirepresentasikan lintasan navigasiyang pr"u*irir* yang mengindikasikanpror"-nr"r. poi"-pol" silancardari.paraPenggunaunruk memPunyai.nilai yang string mencari-sekumpulan untuk etplorasi pohon dilibatkan L-od.lk"n.'Alloritm-" perangkatlunak elaperimen Hasil oleh.pengguna. ditentukan yagn batas yanfi melebihi ,,il"i ;;;"bilir* "-b".,g kebutuhan dengan navigasi lintasan-tintasan marirpu P.:lgq*n" HPG model *..,,r.rjukka' bihwa ^.njh.rilk"n .*,akrueksekusisebandingsecaralinier d.ng"n j-umlahkeadaandari grammaryang dihasilkan' Sifat inkremenal mampu menunjukkan dari HpG yang diimflementasikan dafim'perangkat-lunak- Vebl,og\iney telahjuga menunjukkan eksperimen hasil itu, Selain efisien. ir"rr"rrg"ni lonjakan-darasecaia k.-"-pr*.y"i"1"'CJ*" oleh faktor sangat dihasilkan. yang navigasi p."irig dan kualit"s i"ri liniasanJintasan .dipengaruhi navigasi riwayat kedalaman faktor serta oleh ditentukan yang keyakinan Pengguna auk,rrrgln dan" tingkat dimodelkan' yang pengguna probabilisticgrammar modcl,pola-polanavigasi,algoritmaeksplorasipohon Kata kunci: web log mining, hypertext
ABSTRACT
'VeblogMinet) that is.cap.ableof finding This paper explainsthe design and implementation of a sofnvare(i.e., the Hypertexr.?robabilisticGrammar using web site on a certain ,rs.rs'^.ra.'nigation p"tt.rn, (oi brows;ngpatterns) probabiliry value indicating the certain with a as a string (HpG). In"this rnodel, ,r*ig"tion i"ih ir represented " modeled..A leg exploration path being navigation the for the users Dercenraseof rhe browsing i"tr.rrri of than a threshold'(cutpoint) gfgatel value having_probabiliry of strings a ser nnai"g Foi ig"rrrr,ri-1, ,r,." ir*op.a users'navigation de"terminedby a user.Experimenraliesultsshow that th. HPG method is capableof pr"ducing statesof the resulting of number the to proportional linearly are required rimes pro".rririg wirh ,h. parhs The incremen,"f .r"r,r.. of tn. UpC that is imptementedin the WeblogMincr has proved its capabiliry !r.--"r. resultsalso show in handling the incremental data in a very efficient manner. In addition to ,this,experimental. support aswell the b.of by influenced largely paths are. navigation ,r.,"i it lerigrh and the quality of the resufting ".onfrd.rr". p^r"-.rer values determired iy rhe user and thi number of users' history depths being ,h. ", modeled. Keyrvords:web log mining, hypertextprobabilisticgrammarmodel, navigationPatterns' tree exploration
1. PENDAHULUAN Pesatnya pertumbuhan sumber-sumber r07eb informasi yang iersedia pada \7orld \7ide (\7V\0 telah menjadikan internet sebagai on'line terbesardi dunia. Dengan data sumber sangat bervariasi dan masingyang pengguna masingmemiliki latar belakangdan tujuan yang berbeda,internet merupakan sumber informasi vang heterogen baik dilihat dari segi ketersediaan, penyajianmaupun dari kualitas informasi v"ng dik"ttdungnya. Kecenderunganini telah meriimbulkan berbagaikesulitan baik dalam hal
desain situs web yang dapat memuaskanpara penggunasitus yang sangat bervariasidan juga koulit"tt dalam melakulrannavigasipada struktur situs web yang besar.Permasalahantersebut pada gilirannya mendorong Peningkatan-kebuluhan-akan fasilitas otomatis (automatedtook) yang dapat mencari, mengekstrak,menyaring, dan-mengevduasiinformasi baik yang berkaitan dengan kontela informasi itu sendiri mauPun yang berkaitan dengan pola penggunaaninformasitersebut(Mobasher,2000)' Selanjutnya, terjadinya ledakan dalam pertumbuhan dan penyebaran'WIW'Wpada saatini
t FakultasTeknologiInformasi,KampusITS Sukolilo,Surabaya 601l l
2004- MajalahIPTEK Vol. 15,No. 3, Agustus
118 telah rnenyebabkansemakinmenjamurnyasitussitusueb yang bersifatkomersial,mulai dari situs yang berjenis e-commerce sePerti toko/ supermarket on-line, situs penyedia informasi seperti koran on-line, hingga kepada situs-situs hiburan dan musik. Kesuksesandari berbagai situs uteb tersebut sangat bergantung pada kualitas pelayanan yang diberikan, terutama karena j"t*k antar kompetitor yang hanya berbeda satu "mouseclich" saia.Kenyataan ini menyebabkanpara penggunaitus webcenderung untuk berpindah ke situs lain jika merekatidak menemukan apa yang dicarinya dengan cepat dan mudah. Akibatnya' suatu situs uteb yang dapat memfalisilitasi dirinya dengan metode yang mampu menganalisis perilaku Penguna pada saat melakukan navigasi (browsing) pada suatu layanan on'line dapat menjadi sangat bermanfaat baik terhadap penyedia layanan itu sendiri maupun kepada P^ra Penggunanya' Pengetahuanterhadap pola-pola navigasipengguna dapat membantu para penyedia layanan atau pengelolasittis dalam meningkatkandesain, struktur dan topologi situs untuk dapat lebih menarik minat pengguna dan memudahkan pengguna dalam mencari informasi yang dikehendaki. Data mining dan hnoruledgediscouerytelah diakui secaraluas sebagaisuatu disiplin ilmu yang digunakanuntuk meneliti dan mempelajari teknik-teknik pengenalanpola pada kumpulan data dengan skala sangat besar (Berry, 200; Djunaidy, 2002a-2002d).Berbagaiaplikasi data mining pada \feb, atau yang lebih populer dikenal dengan istrlah web mining merupakan salahsatu metode teknik data mining yang dapat digunakan untuk secaraotomatis menemukan dan mengelstrak berbagai informasi yang terdapat dalam \( (N(/, baik yang berkaitan dengan konteks isi data (web content)mauPun dengan pemanfaatan data (usage data) (Djunaidy, 2002e;Mobasher,I 999-2001)' Makalah ini membahas hasil penelitian mengenai desain dan implementasi sebuah perangkat lunak "VeblogMiner". Perangkat lunak ini didesain agar mamPu mencari polapola navigasipenggunasuatu situs web rcrtentu. Metode yang digunakan dalam perangkatlunak didasarkanpada konsep yang relatif baru, yaitu HypertextProbabi listi c Gramrnar (HPG) (Borges, 1999).Kontribusi utama yang dapat diberikan oleh penelitian ini adalah tersedianya satu perangkat lunak yang mamPu untuk mendapatkanpola-pola navigasiPengguna.Pola-pola navigasiini diekstraksi dari suatu log f.le suatu situsueb yang di dalamnyaberisikansesinavigasi
dalam jumlah yang sangat besar. Perangkat lunak yang dihasilkan merupakan inti dari perangkat lunak pemandu untuk melakukan Prosesnavigasi dalam suatu situs uteb Qteb nauigation assistant), seperti yang diimplementasikan dalarn perangkat lunak Web Nauigation Guide Systern(Djunaidy,
2002e). DATA MINING 2. TltrEB lVeb data mining dapat didefinisikan sebagai studi atas teknik data mining yang dapat secara otomatis menemukan dan mengekstrak berbagai informasi penting yang rerdapat dalam \f\ilf$7. Penelidan dalam bidang ini didxari oleh dua rujuan utarna yang bersifat j*glo panjang, yaitu pengembangan teknik unruk membantu dalam mendesain suatu sirus web yang baik dan pengembanganteknik unruk membantu seorang pengguna individual dalam melakukan navigasi
di \fr\Jruf (Cooley,1997). Pada satu sisi, rerdapat kebutuhan al€n teknik-teknik yang dapat membantu Proses pengambilan keputusan bisnis dalam suatu situs e-czmmerce.Sebagai contoh dari kebutuhan ini adalah kebutuhan unruk memahami perilaku pengguna atau pengunjung unruk menempatkan Contoh lain iklan yang repat di \7\0-!f. berkaitan dengan proses desain suatu situs peb agar dapat mencapai rujuan bisnis tertentu' seperti suatu situs y'ang dapar mengarahkan Para penggunanya ke suaru produk yang memiliki margin keuntungan yang lebih besar. Pada sisi lain, terdapat kebutuhan akan ketersediaan fasilitas dan layanan 1'ang dapat membantu dalam mempermudah pengguna individual Dalam kaitan ini, proses navigasi di \7!7W. seorang pengguna dapat mengambil manfaat dari mesin pencarian web (searchengine), personalisasi antar-muka, hingga pada web personal assistant atau web agent y^ng mampu membantu pengguna dalam berhadapan dengan informasi yang sangat banyak dan tersebar secara luas dalam Khusus deJamtaeb mining terdapat dua \f$7\f. kategori penelitian utalna, yairu prosespencarian terhadap informasi (web content mining) dan navigasi proses pencarian terhadap pola (Cooley, (web 1997; mining) usage pengguna Djunaidy, 2002e, Mobasher, 1999-2001). 2.1. lVeb Content Mining Proses pencarian terhadap informasi (ueb content mining) memfokuskan pada pengembangan teknik-teknik yang dapat membantu pengguna dalam menemukan dokumen yang
Majalah IPTEK Vol. 15,No. 3, Agustus2004'
t-
119 rxTirsr-j:1 kriteria tertentu (Cooley, L997)' l,:u:"r'-r,e:l t'ang ditemukan digunakan untuk ri"a,, basis Pengetahuan lokal' msrrr:;:.srn pada kasus ini adalah pendekatan of lrl.s hnguage yang qaery milibatkan ocnlciii g.ui:rr:;ien untuk menemukan sumber informasi Berbagai teknik discouery) di \f\il7\7. n$!.mir:*-:, retrieadl information dengan ruirg barkainn ini bidang pada digunakan l'*;"* -untuk ekstraksi informasi melakukan :rs-bar':,ru rs-,"-Eenpresisi dan mempunyai kualitas yang * -Fr -"':c"
1-).. Vcb UsageMining r,{eb usagemining adalah bidang penelitian teknik','og .n.-fJkuskan pada pengembangan. ..kriik dan fasilitasuntuk mempelajarikelakukan navigasi pengguna di web (Cooley, 1997; Ditrlaidy,' idozr, Mobasher, 1999-2001)' Densan memahami pola navigasi pengunjung rn.*--rrngkitkan pihak penyedil layanan atau pung.loi" situs untuk minyesuaikan antar-muka ,i*f ,r.rt,tk setiap pengguna secaraindividud' dan juga untuk meningkatkan struktur statis sirusddam suatusistemhYPertext. 2.3..VebLog
bahwa probabilitas seorangpen$glna di mana lebih dari 25,5 menir tidak melakukan request yang sangatrendah'Oleh mempunyaiprosentase yang mengunakanf = peneliri ba"yak k"r.rr".ry" 30 menit sebagaibataswaktu antat requestdalam satusesi.Ga-i", 1 memperlihatkansatucontoh
b7rth. isisebuah
Akurasi dari informasi sesi Penggunayang dapat diperoleh dari lo7 fi|, pada.web smter oleh beberapataktor, s.ePertt sangatdipengaruhi p.rr-ggtrn""t cache, seruerProx!, dan sharing IP. Oleh sebabitu teknik-teknik seperti iari; coohiesdan modifikasi URL diperlukan untuk mengidentifikxi requestyang-dalangdari alamat IP yi"g samadan ,tntttk melakukanrekonstruftsi ,.ri ,,"iig"ri penggunasecaraakurat dari logf'le' 3.
HYPERTEXT GMMMAR
PROBABIUSTIC
Kumpulan dari seiumlah, sesi navigasi p.r,ggrrn" yang didapat dari hg fle (atausumber iai"- y"ng serupa) dimodelkan sebagai suatu Hyprrtt*l tVerghnd Grarnmar (H\fG)' Dalam \Veb-Log Miner ini, H\7G tersebut "pfik"ti kemudian ditransformasi menjadi suatu H72er' text Probabilistic Grammar (HPG)' Dengan menggunakanHPG ini, berbagai ceknik. data ntiniii dapat diaplikasikan untuk mengekstrak pola-poladari sesinavigasiPengguna' ' SebuahH\fG dapat dibangun dengancara menyusun informasi yang diperoleh dari sesi pengguna ke dalam stsatu hype,rtextgra'rnrnar' infol"-"ti yang dapat diperoleh dari sebuah H\fG antaralain adalah(Borges,1999): r Jumlah permintaan terhadapsetiaphdaman
Web accesslog adalah fle yang meyimpan setiap transaksi permintaan (request)dokumen o"d" s,,"t,, web-seraer.Sebagianbesar format 'arcess log ini mengikuti format standar (common lns furiat\ vans dispesifikasikansebagaibagian diri proro.ot f-tffp oleh CERN dan NCSA (Vorid \7ide \feb Consortium, 1998). Dalam ini, setiap request dalam lo7 filt fo.-". lA,l, mengandunginformasi sePertiberikut: damat IP o Jumlah suatu halaman menjadi first state dari tmpuier yang melakukan rlque:t, userID dalamsuatusesilS/,1, (pada ,r-*-tty* feld ini tidak digunakan)' tanggal dan waktu request,status yang menano Jumlah suatu halaman menjadi last state d"lii-t t,tkt.s tidaknya su ur requesr,ukuran dari dalam suatusesi1,4fl, dan yang ditransfer' referer URL (alama.tURL fle 'd"ri' o Jumlah suatu urutan dari dua buah halaman permintaan tersebut berasal),dan yang muncul bersamaandalam suatu sesi dan veisi dari web browseryangdigunakan' nama-irr" (menyatakan jumlah linh Yang iai,l Informasi yang terdapat dalam web hg dapat dilewati). digunakan uttt,tk merekonstruksi suatu sesi sesi Suatu ,ra:uig"sipenggunadalam suatu situs' Menurut (Borges, 1999), sebuah H\7G pengqunaumumnyadidefinisikansebagaiurutan adalahsebuahhypertextgrarnrnAr'di mana setiap 'rtoii, vans berasaldari alamat IP yang sama' aturan produlsi (productionrule) memiliki bobot 'ini," requett dua terdapat yang boleh ddak Ui-rtuk yang diasosiasikandengan: jumlah sessia.n (r menit r dari lebih (start production), berurutan yang dipisahkan dim-ulai dari suatu halaman p"t"t tlr.t yang harus dim.asukkan jumlah linh yang dilewati (transitiueproduction), merupakan ^ oleh penguna aplikasi). Hasil studi. yang dan jumlah sessionyang diakhiri pada suatu -oleh Eotg.t (1999) menyebutkan dilakuLn s 2004- MajalahIPTEK Vol. I 5, No' 3, Agustu
@0:ll:02.0400]"GET/career/private/98/database/HTfP/l'0"40l 401 "-" "ia-archiver" "'" gr""r."l.*"Lom - - [01/Septl999:00:28:24-0400] "GET /careerlprivatelgglHTTP/1.0" 401 401 "ia-archiver" HT|P/l'0" 401 gr..-r,."1.*".com- - [0]/Sepll999:0037A2 -04O0]"GET /careertprivxelggldatabase/ "ia-archiver" 401 "-" HTTP/l.0" jt".n.A.*"-m - - [0]/Sepll999:00:57:31-0400] "GET /careerlprivatelgglinv-brochure/ 401 401 "-" "ia-archiver"
Ga.mbar1. Contoh isi dari sebuahloe file halaman (final production). Hlpertext Grammar (HG) itu settdiri merePresentasikan - sebuah hypenextdanbase H= <S,R> yang terdiri dari empatrupleHG=
,di mana: o V={S,A,,...4*,F} adalah kumpulan "bj"d terbatasdari'iimbol non-terminallNl+2. S dan F berturut-turut menyatakanstart stt te dan final stute yang unik, dan berlaku pemetaansatu-ke-satuantaraV-{S,F} ke N.
HPG sepertiberikut. Suarulrypertatprobabilisrtc grarnmar merepresentasikansebuah hYpertext database,H=<S,R> )zang meruPakan 2 tuple HPG= di mana H!7G adalahsebuah hlpertext weighnd grammar dan P adalah sekumpulanprobabilitasPoe P, yang diberikan pada produksi Pi eP yang bersesuaian. Probabilitas dari suatu produlisi dihitung berdasarkanaturan sepeni dirunjukkan oleh persamaan(l) hingga(4) (Borges,1999).
o E = {a,,...,a6,1}adalah kumpulan. abjad terbatasdari simbol terminal,di mana berlaku pemetaan satu-ke-satuantara E ke N atau
Padapersamaan(1) di aas, nilai cr € [0' 1] menyatakansebuahparamererlang harus ditenrukan oleh penggunaterhadapsebuahstateyang antaraE ke V-{S,F}' berkorespondensi dengan halaman Pertama dalam sebuah sesi navigasi.Jika o = 0, hanya o P merupakan kumpulan terbatasdati aturan sejumlah state yerg benindak sebagai stdte produhsi dengan bentuk X+ yY denganXY pertamadalam sebuahsesiyang mempunyai-nilai e V dan y € > u e sePertidi bawahini: probabilitas lebih besar dari nol ddam sebuah (a)S+ a14,eP,.VA,e V, start production.Dalam hal ini, hanya sejumlah strin[ yang diawali dengan sebuahstate yang eda (b)A,+ ai4j e P jika dan hanyajika (rut € dalam posisi penama dalam sebuahsesinavigasi & yang dilimbulkan oleh gr4mnar. Sebaliknya,jika (c)A,+ F e P,YA,e V, dan €[ = l, probabilias dari sutc untuk ada dalam sebuah start prod:uction proporsional dengan (d),F+ E e P. jumlah berapa l, di mana HG adalahltypertact yang telah dijelaskan sebelumnya. skenario grd.rntnardan'$?'adalahhimpunan urutan bobot Dengan demikian, Parameter o memberikan w- e W yang diasosiasikandengan aturan pengguna kemampuan untuk mengatur model pioduksi P,, e P yang bersesuaian.Bobot dari untuk berbagai jenis pola pelacakan yang produksi diberikan berdasarkan s.ti"p berbedadalam navigasipengguna' "tutln aturan sepertiberikut:
G) \7(S+ a,4)=lMl, (b) \7(,4,+afl =V/il, 'S7(,{,-+ ff =lAF, dan G) (d) \7(F+
s) = l.
Akhirnya, dengan menggunakan definisi hypertextweightedgra.rnmar(H\(G)-seperti di atas,dap"t diberikan sebuahdefinisi formal dari
l4t
p (S-+ a iA )= " # -n + (l-a )-f f i -J=r
J
is4i -J=rl
(l)
Jl
l+n)
p (A i) a iA i)= W
p(Ar + rr=W
Vol. 15,No. 3, Agustus2004'MajalahIPTEK
bl
tzl
l*rl +.1=l 4j P\Ar
(3)
p \F + e) = l
(4)
Unnrk memberikan ilustrasi bagaimana s€buahHPG dapat dibentuk, perhatikansebuah ;onroh yang ditunjukkan dalam Gambar 2 yang n:enggambarkan sekumpulan sesi navigasi :Engguna yang terdiri dari 6 nail sesinavigasi. Kurnpulan dari sesinavigasiini dapat diperoleh ;Ln sebuahfle web log. Dengan menggunakan ;etrnisi HWG yang dijelaskan sebelumnya --erhadap sekumpulan sesi navigasi y{rg ;:nrnjukkan dalam Gambar 2, maka akan ::peroleh H\fG seperti diperlihatkan dalam Sarnbar 3 yang menyatakan diagram ransisi r:::ar halamanweb (r4) dari sesinavigasi.
Trail SesiNavigasi
\o. Sesi I
A,+Ar+4"+Ao A,+Ar+Au+Ao+A,
1
3
4+4-+4+4
{ 5 3;Ll:ie.r 2. fierrgguna
Ar-+Ar-rA, Ar-+Ar+A,+A. Ar-+A,-+Ar+A, Contoh kumpulan sesi navigasi
'l;-lrrbar 3
menunjukkan sebuah fnite
HPG yang 4lrdftNttt{,,,t:,,,t }"ang sesuai untuk navigasi sesi sekumpulan dad drlmdkn purrugs"lr.amng ditunjukkan dalam Gambar 2. Sm"l::-: d:runjukkan dalam Gambar 3, setitp state #-*nnn p;p1 HI7'G adalah seimbang (baknced). ll-rTmnurLfln. suaru ttate dikatakan seimbang ulrtrmftar:.a 'unlah bobot dari linh yang menuju ke ,iEir,r rHs€5ur sarna dengan jumlah linh yang rli*i'rn*na;--; rTstr rersebut. Jumlah dari linh yang muuuilJrn. nralt keluar dari suatu state disebut firnrr"qus,!dETrr'1.Sedang derajat dari suatu state terhadap permintaan lmmil{wtirc' i"tttl"h oleh state l'ang direpresentasikan iiiirNnuirrr,"mmm "{ IIMfiililihEIt
unruk sesinavigasiddam Grudnr n F"nWfG rffifu"1
Dengan menggunakandefinisi dari HPG yang dijelaskan sebelumnya, maka satu set aturan produlai dari HPG untuk H\fG Yang bersesuaiandapat dibentuk. Sebagai contoh, untuk sebuah HPG yang terdiri dari 6 sesi navigasipenggunadan total requestsebanyak24 (Gambar 3), dapat dihasilkan.satuset aturan produlai seperti ditunjukkan dalam Gambar 4. Dalam gambar ini, nilai probabilitasdari setiap aturan produksi dihitung dengan menggunakan aturan sepertidiperlihatkandalam Persamaan(1) 'ersamaan(4)
hi
(i)
I
nilai G=0. (iii
0.33 A,+ay\ 0.25 A,-+F s+q4 0.00 A,+a.A. 0.50 Ar-+F S-+arA, 0.00 4+".A. 0.75 4-+F S-+a,A, a . r 7 Lr+"oAo 0.25 4-+F S-+"r4 0.50 A,+aoAo 0.40 4+F S+a.A. 0.00 A,+arA,o 0.20 4-+F .Ao+a,A, 0 . 5 0 &+"4 0.25 4-+"4 0.60 0.40 A+a.A
S-)a,A,
0.25 0.00 0.40 0.25 0.00 1 . 00
Gambar 4. Aturan produksi dari HPG untuk H\7G Gambar 3. Sebuah string termxuk dalam suau HPG languagejikanilai probabilimsderivasinyadi atas nilai ambangbatasl, yang diberikan. Probabilitas dari derivasidihirung dari hasil perkalian antara probabilitas-probabilitasyang digunakan dalam derivasirersebut,yaitu P(rz) = n,.nr1.*p pGn);di mana p(Pr) adalah probabilitas dari aturan produksi ke-h (l < p < ld,,l) dan ld-l merupakan panjang derivasi. Nilai ambang batas HPG dibentuk dari dua nilai berbeda,yaitu 1, = 0.6; di mana 0, 6 e (0,1) berturut-turut menyatakan nilai supportdan conf.drncedari sting. Support 0 merupakan faktor yang bertanggung jawab untuk menyisihkan (pruning out) sejumlah string yang derivasi Pertamanya memiliki probabilitas rendah (menggambarkan dari hypertext slstem yang jarang b.gt* dikunjungi). Penentuannilai supportbergantung pada jumlah sesinavigasi(0 y""g ada, di mana semakin besarjumlah sesisemakin kecil probabilitas dari suatustart production, yaitu 0 = 1$ yang berarti hanya aturan produksi y^ng memiliki nilai di atas rata-rata (rara-rata probabilitassuatu aturan produksi meniadi start production)akandimasukkanddamf nal string' Vol. 15,No. 3,,AgustusL004 - MajalahIPTEK
122 Conf.denced'merupakan faktor yang bercanggung jawab untuk menyisihkan selumlah s*ing yang derivasinya mengandung transitiue production dengan probabilitas rendah. Untuk menentukan nilai confidence perlu diperhitungkan branching factor (BF) dari sebuah grarwnar, yaitu jumlah rat^-rata linh yang keluar dari suaru halaman dalam opologr fupertat (outlinksper page).Sebagaicontoh, jik"-*"t,t sistem hypertextmemiliki rata-ratalima linh yang keluar dari suatu halaman, maka rata-rata probabilitas link adalah 0.2. Nilai sap?ort dan confid.ence memberikan f*ilitas bagl seorang pengguna untuk mengenddikan jumlah, probabilitas, dan' panjang dari trail yang ingin dihasilkan dari suatugrdlnrnar knguage. Ruh-setdidefinisikan sebagaikumpulan dari maximal strings (maximal traik) yang terdapat ddam sebuah kngaage, di mana sting disebut maxirnal jika bukan merupakanprefx dari sting lainnya. Jadi sebuah maximal sting adaleh sebuah rule, dan non-maxirnal strings adalah sebuah sub-ruh. Untuk menemukan sejumlah pola (rahs) dari sebuahHPG diperlukan sebuah algoritma eksplorasi pohon (*ee exphration algorithrn),yang dalam penelitian ini digunakan algoritma BreadthFirst Search(BFS). Algorirma BFS bekerjadengan membangunsebuahpohon dengan sebuah start state S sebrgai root, dan setiapcabangdari pohon dapat ditelusuri hingga nilai probabilitasnya berada di bawah nilai ambang batas. Gambar 5 memperlihatkan sebuahcontoh hasil eksplorasipohon dari aturan produksi HPG yang ditunjukkan dalam Gambar 4. Sebuahcabangdari pohon yang mempunyai probabilitas di atas ambang batas dinamakan candidate trail atau candidate rule jika branch tersebut masih dapat ditelusuri lebih lanjut. Sedang sebuah cabang dari pohon yang mempunyai probabilitas di atas nilai ambang baras dan ddak dapat diperluas lagi disebut sebuah rule atau rnaximal trail, Karena suaru HPG tidak memiliki perulangan (cych) maka dapat dipastikan bahwa algoritma akan berhenti padasuatutitik tertentu.
Gambar 5. Contoh hasil eksplorasipohon pencarianseluruhpola dari HPG Gambar4. (nauigationruhs) yang memiliki probabilitas di atas nilai ambang batas yang diberikan oleh pengguna. Aplikasi 'VeblagMiner ini tediri atas sejumlah modul. Setiap modul dibuat secara khusus untuk menangani tugas teftentu, seperti kelas LogManagcr benanggung jawab dalam membacahsfh dan melakukanidentifikasi scsi (sessionidzntifcation) rerhadap data wcb hg tersebut unruk selanjutnya diserahkan pada DatabaseManager yang benanggung jawab terhadap seluruh prosesyang berkairan dengan operasidatabase.Secarakeseluruhanterdapat tiga tahap proses yang dilakukan dalam aplikasi WeblogMiner, yairu preparasi data pembangunangramma4 dan pencarian pola (tah).
Afr n u l a
Caab
(cu0 l: i: ti
HPG Engar.
| ,.*.,-.l-":*"
Og I.n .9 ..
--------_
{!.bct.
,i.
h..d.
!td.L.
-t-. Y
w'b Loe DSM.
Gambar 6. fusitektur WebLogMiner. 4. IMPLEMENTASI
PERANGKAT LUNAK
Secara umum arsitekrur dari aplikasi rYebLogMiner yang telah berhasil dibuat ditunjukkan dalam Gambar 6. Masukan urama dari aplikasi WebLogMiner adalah dacaweb hg yang berasal dari sebuah situs ueb, sedangkan keluarannyaberupalaporansejulahpola navigasi
Proses preparasi daa diperlukan untuk menyiapkan data web log ddam pembentukan sebuah HS7G. Proses ini terdiri dari proses transformasi data dan proses identifikasi sesi. Traniformasi data bertanggungjawab untuk mengubah data dari serni-structureddata menjadi structured data sehingga dapat membedakan informasi mengenai userid, waktu al<sesdan
Vol. 15,No. 3, Agusrus2004- MajalahIPTEK
123 halaman URL yang diakses.SedangkanProses identifikasi sesi dilakukan untuk mengelompokkan urutan requestke dalam suatuunit logika yang merepresentasikan sesi Pengguna' Pengelompokkanini dilakukan dengan melakukan sorting dan splitting terhadap daa web log untuk menemukan unit-unit ransaksi Penguna. Prosespreparasidata ditangani sepenuhnyaoleh modul LogManager yang bertanggung jawab melakukan melakukan pembacaan log fb, sesi, dan identifikasi data, inrepretasi feld modul Databasekepada memberikan hasilnya -\{anageruntuk diproseslebih lanjut. Tahap kedua dari WebLogMineradalahProses pembentukan grammar dari sekumpulan sesi oenggunayang telah teridentifikasi. Prosesini rnemisahkansesipenggunamenjadi sekumpulan :ute dan aturan produlai untuk membentuk arau meremajakan)suatugrttmrnaryang berada dalam database. Pemisahan tersebut j,tg" memperhitungkan history depth (Ngram) yang Cigunakanoleh sebuahgrarnman Untuk dapat r:nembangungrarnmar secaraefisien dibutuhkan secuahmodel data, seperti diperlihatkan dalam Gambar 7, yang mamPu menangani Pertam:ahan data dengan memanfaatkan sifat incre**tral dali metodeHPG.
O.mdrdO
D.stsbn Numsbtl NrnLhla HicoryD.plh Br.ndhgFrdor L.lUPd.b Pr.vS!ppod Pr.vCotrlid.ne M.xiubr
lamnn;r -. Diagram ER dari WeblogMiner. J:'rucs p'encarian pola merupakan tahap bLogMineryangbertujuanuntuk :;n' \Yre uumrurrrr.r r pola-pola navigasi dari grammar ,,ruun$ wlprmCnenruk sebelumnya.SebelumProses 'ilnuprrnnrnfrrr eola dilakukan, terlebih dahulu dfiiltllluuuulsur orrs€s normalisasidari H'S7G menjadi #{',!',S"'r rnenghirung nilai probabilitas dari fiiffiqf, ilMury murrrrrrprcduksi. Proses ini dilakukan *rnnr'.rr,:ri* seluruh kemungkinan Kandi'lt|','''|ryf,,rub) yang dapat dihasilkan unlrmsi,i,t:t mooun 'M rNiure'r:.'t probabilitasyang ditemuaifi n''milrmmn Irmr ilLmfim n'lih,;;n[arrg batasyang ditentukan. kbm hesar atau sama, maka JUlr lurJil,hmup L-,'nrrmfriniil,qn dimasukkan ke dalam p'crra r*rbur
stach untuk digunakan dalam prosespencarian pola yang lebih panjang. Eksplorasipola ddam suarupohon dilakukan dengan meliba*an algoitma Bread.th First Search lang telah dimodifikasi untuk dapat menemukan pola-pola dengan nilai di atas nilai ambang batasdengan ditentukan kedalaman maksimum yang sebelurnnya. Perangkatlunak ini diimplementasikandalam dua jenis aplikasi.Aplikasi yang pertamaadalah Jaua Application (client/seruer) yang berfungsi unuk utama dalam memproses log fle membangun suatu H'WG padadatabase.Sedang aplikasi kedua merupakan aplikasi berbxis web dengan bantuan Java Servlet dan PHP yang dapat diakses dengan menggunakan web browser.Aplikasi berbasisweb ditqul
5. UJI COBA PERANGKAT LUNAK Keseluruhan perangkat lunak WebLogMiner diimplementasikandenganmenggunakanbahasa pemrograman Java, dan dijalankan pada platform 'Windows 2000 Profesional dengan menggunakandiuerJDBC yang disediakanoleh Oracle untuk membuat koneksi database. Spesifikasikomputer yang digunakan pada sisi client adalah HP Vectra dengan prosesorIntel Pentiumll 400MHz dengan kapasitasmemory 128M8. Untuk seruer databae digunakan komputer HP-LX pada platform Unix yang menjalankan Oracle 8.1.6 sebagai DBMS. Vol. 15,No. 3, Agustus2004 - MajalahIPTEK
124 Sedang untuk aplikasi yang berbasis web digunakan web seruer Apache 1.3.20 yarlrg berjalan dalam lingkungan Vindows 2000 Profesionaldengantambahanmodul PHP 4.0.5 dan Apache Jserv 1.L.2. Keseluruhansistem berjalan pada suatu jaringan LAN (intranet) denganbandwidth 100 Mbps. Seluruh data yang digunakan dalam ujicoba ini merupakan data web log riil dan tanpa dilakukan rekayasa apapun. Data Pertama (Dataset-l) merupakan data web log yeng didapat dari situs www.cs.washington.edu/ yang berisi homes/map/adaptive/download.html, situs log dari ueb data selama dua bulan http://macltines.hypeneal.org dalam tahun 1997. Menurut pengelola situs (Perkowirz,2000), situs lersebutmemiliki sekitar 2500-3000 halaman web dan setiap harinya menerima kira-kira 10000 requett dari sekiar 1200 pengunjung. Data uji coba ini terdiri dari 61 buah losfb dengankapasitastotal T3MB dan berisi 600000 requestdari sekitar 80000 sesi navigasipengguna.Informasi mengenaiPengunjung telah disamarkan dan penggunaan cache ditiadakan, sehingga setiap halaman harus direqaest kembali meskipun pernah dikunjungi sebelurnnya.Data kedua (Dataset-2)didapat dari html, yang sirus http://euroclub.mit.edu/logslindex. berisi data web hg selarnadua bulan dalam tahun 1999 dari situs http://euroclub.mit.edu.Situs ini berisikan sekitar 1500-2000 halaman web dan setiap harinya menerima kira-kira 3000 request dari sekitar 500 pengunjung. Data uji coba kedua ini terdiri dari dua buah hg f.le yang berukuran total 53MB dengan total 93000 requettdan 16000 sesi pengguna.Seluruh data digunakan tanpa dilakukan pembersihan data khusus, kecuali pemisahanimage reqaestsePerti .gifdan.jpg. Dalam pelaksanaan uji coba, pengukuran waktu proses (running time) dimulai dari saat seluruh data telah beradadalam memori utama. Untuk mengurangi bias yang mungkin terjadi, maka waktu yang diperlukan untuk menyimpan hasil pola yang ditemukan ke dalam databare diabaikan. Ujicoba dilakukan sebanyakl0 kali untuk setiap parameter dan data yang sama, dengan tujuan mengurangi bias yang mungkin terjadi. Batas sesi pengguna ditetapkan sebesar 30 menit, sehinggasesiyang id.h lebih dari 30 menit akan dipisah menjadi dua buah sesi navigasiyang berbeda. Secara umum, uji coba ditujukan untuk dari penerapan mengukur kinerja Qterforrnance) metode HPG dengan menggunakan statistik yang didapat dari elaperimen. Uji coba kinerja
ini antara lain meliputi: pengaruh jumlah states terhadap jumlah pola yang dapat dihasilkan, pengaruhjumlah statesrcrhadapjumlah iterasi, pengaruh jumlah states rcrhadap waktu Proses, pengaruh nilai conf.dcnceterhadap jumlah pola, pengaruh nilai confdenceterhadap waktu proses untuk menghasilkan pola, dan pengaruh besarnya panjang pola (history deptfi rcrtade;p pola yangdapatdihasilkan. Dalam uji coba,j"orl"h iterasiyang dimaksud addah jumlah perbandingan (number of comParation)yang dilakukan dalam prosesuntuk mengetahui apakah suatu kandidat pola merupakan sebuahpola. Nilai su??ort(0) ditetapkan ekivalen dengan probabilitas rera4ata suatu state menjadi stdrt state, yaitu lln, di mana n merupakan j"rr,l"h start ttatc ddam grammar. Sedangkanuntuk rriu confdence(6) ditentukan berubah-ubahanuua 0 dan 1, sesuaidenganuji coba yang dilakul€n. Selain itu juga dilalcukan uji coba yang berrujuan unruk menganalisis pengaruhhistorydcpth xau ingatan pengunjung (Ngram) yang dimodelkan terhadap panjang pola yang dihasilkan. Uji coba ini dilakukan dengan membandingkan beberapa pola yang didapat denganNgr* berbeda. Hasil uji coba perangkatlunak berturut-turut dapat dilihat dalam Gambar 8 sampai dengan Gambar 14. Ddam Gambar 8 ditampilkan grafik jumlah pola terhadap perubahan jumlah stdtes dengan rulai conpncc (6) = 0.4 dan jumlah state yeng bervariasi ancara 300-3000. Dengan menggunakan nilai confdznce yartg sama, grafik j"otl"h iterasi dan waktu proses terhadap j"ml"h siaas, bemrrut-nrrut dirunjukkan dalam Gambar 9 dan 10. Kemudian, Gambar 1l dan 12 bemrrut-nuut memPerlihatkan grafik perubahan j"rrrl"h pola dan waktu proses terhadap bcberapa rulu confdence ant^ra coba yang 0.05-0.5. Grafik hasil "ji memperlihatkan pengaruh history depth *au ingatan pengguna (Ngram) yang bebeda terhadap jumlah p"L d"" panjang pola yang dihasilkanditunjukkan dalam Gambar 13. memberikan ilustrasi Akhirnya, untuk mengenaibentuk pola plg dihasilkan,Gambar 14 memperliharkanbeberapaconmh pola yang dihasilkan oleh VeblogMincr untuk dataset-2. Gambar 14 menunjukkan bahwa semakinbesar jumlah ingatan pengguna (Ngram) semakin besarjumlah pola dan panjang pola yang dapat ditemukan.
Vol. 15, No. 3, Agustus2004 - MajalahIPTEK
t25 4.50 425 4.00 g 3.75
14000 13000 12000
r5 1ffi3 cso
I
tg 3.50 325 E 3.00
iqryg iI ffi5m0 8 '
?
E 712 # f;!
3m0 zD0 1000
h
t.t)
!. 2J0
1000
250 JJo 85t1il50 1450175020J023$26fr295fr Jurihlt Strbt
lJ0 t25 lr10
0 0u5 0.t 0.150.2 0.2J0.3 0.350.4 0.rt50.5
Gambar 8. Grafik Jumlah Pola terhadapJumlah States.
I
I a T
(
Gambar12.Grafik\7akru Proses terhadapNilai Confidence.
1 6l *
l
i
, ,
!.
!
t., r 4tt r.3t t.2
141 t1)
T
al4 o tlu
r .t t rt
rtm pql
0et B 0sf
I80 ^. 70
ts E 40
;;f
ttr
300 600 900 12001500180021002rm 2700306 Junle}
Stetce
Gambar 9. Grafik Jumlah Iterasi terhadap Iumlah States.
a I
a
NiId Crrfidcrca
'n l0 0 Puje4
Prle
Gambar 13. Grafik Jumlah Pola terhadap panjang pola (hktoryfupfi.
l 1000 10(D0 9000 80@
4, 70m 5
E t
II
6(m 50(n 4000 3000 2ooo 1000 0 0
I
/career/studentside/navigation.html /career/studentside/studcorner.html /career/studentside/register.html 0.05 0.1 0.15 0.: 0.25 0.3 0.35 0.4 0.45 0.5 0.55 Nlld Cor6dcna
I I
ir t
Gambar 10. Grafik \7aktu Proses terhadap J"otl"h States. Itmo Itfip €. 9m0 € emo gmo { amo
6-3 [Prob:0.113 /contest.html /head.ft.html /contest.fr.html /buttons.activ.ft .html /gallery98.html /head.ft.html
Gambar 14. Contoh Pola yang Dihasilkan (Dataset2).
:r m
4iln
!
5 :mo '
200t] 1000 0 0 0.0J0.1 0.150.2 0.2J 0.3 03J 03 0.450.J 0.55 Nilei Con6rhra
Gambar 11. GrafikJumlah Pola terhadapNilai Confdcnce.
Vol. 15,No. 3, Agustus2004- MajdahIPTEK
t26
6. SIMPUTAN DAN PENGEMBANGAN
IGMUNGICNAN
Dari hasil uji coba perangkat lunak lVeblogMi1er dapat dierik b.br"p" sirnpulan sepertiberikut: a) Merode HPG mampu menghasilkanpola navigasipenggunadenganjumlah iterasi-dan waktu pemrosesanyang berbanding lurus denganjumlah halaman web. Sedangi"r,t"t, i:1S"."1t.,pengguna yang ,(history fupn dlmodelkan merupakan salah saru fa_Lcor penentu terhadap panjang dan kuantias pola yang dapat dihasilkan, disamping paramerersupport(0) dan confdence(6). b) Perangkar lunak y_ang dib,r"t mampu menangani penambahan data secaraefisiin dengan memanfaatkan sifat incremental dan metode HPG. Selainitu, metodeHpG lebih cocok direrapkanpada situs-situsyang relatif stabil, Halaman web dengan kontela dinamis terurzrma yang menggunalcan metode POST ddak dipat di;;delkan secara akurat, karena satu state dapat merepresentasikan .beberapa konteks yang berbeda. Untuk kasus lni, guna men_ daparkan data web hg yang -benar_b.na, merepresentasikankelakukan pengunjung sirus diperlukan penanganankhusui sepefi penambahan web seruerpl"g-in y ng 3^p^, menghasilkandata web log sendtri,. Hasil eksekusidari metodeHpG yang berupa pola-pola navigasi masih memb-utuhkan pemaknaan lebih lanjut oleh pengguna sesuai de1Sa3 bidang dan kepenti"g;- pengguna ttlha{in d"r1l"lg diolah d"n poL na.,,ig"siy"r,g dihasilkan. Di bawah ini diterika, 6.b"r"p" saran yang dimungkinkan untuk dilakukan sebagai pengembangan lebih laniut dari lunak \Y/ebLogMiner yang telah perTgkT berhasildibuat. a) Pengembangan model dengan memperhadkan konteks dari dokumin web untuk menghitung relevansi dari suatu halaman uteb terhadap kumpulan kata kunci (keyord) rertenru. Sehinggadimungkinkan unrrrk.lnsngidentifikasipol" y*g """igii memiliki probabilitas tinggi dan 1.t "iig; relevan rerhadap qaer! yang dilakukan (searchenginesimprouement). b) Pembuatan user agent di sisi client memungkinkan pembuatanpersonalto7 fiL, unruk setiap pengunjung wib. Dengaric"r" ini, HPG yang dibangun dari personalhg
rerssur dapar digunakan untuk fl, membanru pengunjung dalam proses rnvigasi sdanjumy'a dan juga untuk membuar desainhalaman urcb yangsesuaidengan keburuhan pcngunjung (custornized irb pagcsl. DAFTARACUAN
Berry, l\{", and Linofi, G. (2000), Mastering Data Mining, John Viley & Sons,New york.Borges, J. and lrvene, M. (l9gg), 'Mining Pattern with Hyperrort faviganonal Probabilisric Grammar', Research' Note RN/99/08, D?. of Computer Science, UniversiryC"ll.g. London, U.K. Coole.vR,l\[obasher, B., and Srivasta, J.0997), 'Web I'fining: Informadon and pacern Diroven' on the I7orld \fide 'il7eb', Procccdingrofnx f Inunational Conference on _Toob vith Anifcial Inulligence (ICTAI,g7). Djunaidy, A, Soelaiman,R, dan Dharmawan, Z.P. (Z0O2!),'pengembangan perangkat Lunak Constraint-Based Rule Mining Urituk Pencarian Kaidah Arcsiasi dari SuaL Basis Dea', Procccdingrof the Seninar of Intelligent
l!:!ybs
and Is Apptications {itrWobzS,
ITS, Surabaya Djunaidn A, Soetaiman,R, dan Evianti, H.H. (2002b), .'Perangkar Lunak Data Mining Pengeksuaksi Kaideh AsosisasiM.nggunakai Dekomposisi l-anice dan Metode Flrrcari"n Bonom-Up', Pmtiding ScminarNasionalllmu _Komputcr dan TchnohgiWrmasi lll,Jakarta. Dlunaidy, A, Soelaiman, R, dan Tyasiamadya, D. Q002c),'Mining AssociationRies From large Darabases using rhe Lattice-Based Approach and Hybrid Search Method,, of thc / In*rnational Conference on lro:ed;ngt Infor-mation Integration and Wb-baed lPPllcatUns and Smtices (ffV/AS 2002), Bandung. Djunaidy,A, Samopa,F., dan Darmasusila, I.p. (2002d), _'Aplikai Dara Mining untuk PencarianPolaAsosiasiMeng-gunakairMetode Dekomposisi Pola', p-cridi"gs of the .4 Industial Ehctronic Seminar ltESZdAZl, Sur^_ baya. Djunaidy, A., Samopa, F., dan Halim, S. 909?d:'Dwelopment of a \7eb Navigation Guide Systembased-onHypertext probaSilistic Grammar', The 2002 IEEE Asia-pacifc Conference Circuhs and Systems "f (APCCAS2002), Singapore. M-obasher,8., 'Creadng Adaptive ITeb Sites Through Usage-Based-Clusteringof URIs',
Vol. 15,No. 3, Agustus2004 - MajalahIPTEK
