基于關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的web序列關(guān)聯(lián)度發(fā)現(xiàn)

基于關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的web序列關(guān)聯(lián)度發(fā)現(xiàn)

現(xiàn)在，隨著世界上日益快速發(fā)展的web覆蓋物，web世界產(chǎn)生了大量數(shù)據(jù)。因此，web數(shù)據(jù)結(jié)構(gòu)方法（即web數(shù)據(jù)結(jié)構(gòu)）成為一個(gè)重要的研究領(lǐng)域。web世界數(shù)據(jù)主要包括web頁(yè)面數(shù)據(jù)、web結(jié)構(gòu)數(shù)據(jù)和用戶(hù)訪(fǎng)問(wèn)日志。因此，web數(shù)據(jù)的挖掘分為web內(nèi)容挖掘、web結(jié)構(gòu)挖掘和web訪(fǎng)問(wèn)信息挖掘。Web頁(yè)面之間存在著豐富的結(jié)構(gòu)信息,這種結(jié)構(gòu)信息和用戶(hù)的訪(fǎng)問(wèn)方式是緊密相連的.當(dāng)一個(gè)用戶(hù)訪(fǎng)問(wèn)一個(gè)Web站點(diǎn)時(shí),會(huì)留下他對(duì)該站點(diǎn)的訪(fǎng)問(wèn)日志.一個(gè)中等規(guī)模的站點(diǎn),一天也會(huì)留下幾兆的日志.日積月累的日志更是Web數(shù)據(jù)挖掘的良好對(duì)象.通過(guò)對(duì)這些日志的挖掘,可以發(fā)現(xiàn)用戶(hù)的訪(fǎng)問(wèn)模式,用于改進(jìn)Web站點(diǎn)的設(shè)計(jì).這種訪(fǎng)問(wèn)模式反映著設(shè)計(jì)者所設(shè)計(jì)的Web頁(yè)面所關(guān)聯(lián)的優(yōu)劣,可以被用來(lái)改進(jìn)Web站點(diǎn)的結(jié)構(gòu),更好地幫助用戶(hù)訪(fǎng)問(wèn).用戶(hù)的訪(fǎng)問(wèn)模式主要分為:(1)用戶(hù)的訪(fǎng)問(wèn)序列模式;(2)用戶(hù)所訪(fǎng)問(wèn)頁(yè)面之間的關(guān)聯(lián)規(guī)則.前者反映的是用戶(hù)的總的遷移序列,著重于序列的發(fā)現(xiàn);后者反映的是群體用戶(hù)所訪(fǎng)問(wèn)的頁(yè)面之間的關(guān)聯(lián)度,著重于獨(dú)立頁(yè)面之間的關(guān)聯(lián).由于Web站點(diǎn)的頁(yè)面存在著網(wǎng)狀結(jié)構(gòu)信息,也由于用戶(hù)的訪(fǎng)問(wèn)存在著序列性,在本文中,我們將提出一種新的發(fā)現(xiàn)序列關(guān)聯(lián)規(guī)則的方法.這種方法基于用戶(hù)事務(wù)訪(fǎng)問(wèn)文法(useraccesstransactiongrammar),據(jù)此得出一個(gè)用戶(hù)訪(fǎng)問(wèn)事務(wù)內(nèi)的各個(gè)訪(fǎng)問(wèn)序列,然后應(yīng)用關(guān)聯(lián)規(guī)則發(fā)現(xiàn)方法和互信息的思想求得并進(jìn)一步解釋所發(fā)現(xiàn)的序列關(guān)聯(lián)規(guī)則.這種序列關(guān)聯(lián)規(guī)則可以更好地幫助Web站點(diǎn)的設(shè)計(jì)者理解用戶(hù)的訪(fǎng)問(wèn)模式.現(xiàn)有的一些可利用的商業(yè)分析工具用于分析Log,但這些工具僅能產(chǎn)生一些簡(jiǎn)單的統(tǒng)計(jì)結(jié)果,如頁(yè)面的訪(fǎng)問(wèn)頻度等.文獻(xiàn)應(yīng)用Hypertextprobabilisticgrammar發(fā)現(xiàn)用戶(hù)遷移模式,并用grammar的熵值評(píng)估挖掘到的模式.但它不能發(fā)現(xiàn)不同頁(yè)面集之間的關(guān)聯(lián)關(guān)系.文獻(xiàn)首次給出Web挖掘的定義,并且給出一個(gè)關(guān)于Web訪(fǎng)問(wèn)信息挖掘的系統(tǒng)WEBMINER.文獻(xiàn)中提到的思路是通過(guò)對(duì)Web站點(diǎn)的日志進(jìn)行處理,將數(shù)據(jù)組織成傳統(tǒng)的數(shù)據(jù)挖掘方法能夠處理的事務(wù)數(shù)據(jù)形式,然后利用傳統(tǒng)的數(shù)據(jù)挖掘方法(如關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法)進(jìn)行處理,所得的挖掘結(jié)果也是傳統(tǒng)的數(shù)據(jù)挖掘結(jié)果,沒(méi)有考慮Web站點(diǎn)的結(jié)構(gòu)和用戶(hù)訪(fǎng)問(wèn)的序列特性,因而不能用于發(fā)現(xiàn)序列關(guān)聯(lián)規(guī)則.“Footprints”的思想是:訪(fǎng)問(wèn)者在訪(fǎng)問(wèn)一個(gè)Web站點(diǎn)時(shí),會(huì)留下“足跡”,經(jīng)過(guò)一段時(shí)間,最頻繁訪(fǎng)問(wèn)的區(qū)域會(huì)形成路徑,于是新的訪(fǎng)問(wèn)者會(huì)依據(jù)這些路徑進(jìn)行訪(fǎng)問(wèn).“足跡”被自動(dòng)地留下,并且訪(fǎng)問(wèn)者不需要提供自己的任何信息.WUM是對(duì)“Footprints”方法的一種補(bǔ)充,定義g-sequences用于挖掘遷移模式,并給出一種挖掘語(yǔ)言MINT.這些方法發(fā)現(xiàn)的是一些局部的信息,不能發(fā)現(xiàn)跨不同頁(yè)面集之間的關(guān)系.而本文的方法本質(zhì)上是一種發(fā)現(xiàn)不同頁(yè)面集關(guān)聯(lián)關(guān)系的方法.本文第1節(jié)描述了需要挖掘的對(duì)象.第2節(jié)定義了用戶(hù)訪(fǎng)問(wèn)事務(wù)文法以及如何應(yīng)用該文法得到用戶(hù)序列訪(fǎng)問(wèn)事務(wù),并給出了相應(yīng)的算法.第3節(jié)定義了序列關(guān)聯(lián)規(guī)則,并引入互信息概念以評(píng)價(jià)發(fā)現(xiàn)到的關(guān)聯(lián)規(guī)則.第4節(jié)給出實(shí)驗(yàn)過(guò)程,并與Cooley的方法進(jìn)行了比較.1細(xì)訪(fǎng)問(wèn)標(biāo)記生成訪(fǎng)問(wèn)事務(wù)挖掘?qū)ο驦og存在Web服務(wù)器上,其日志格式遵循W3C標(biāo)準(zhǔn).在進(jìn)行挖掘時(shí),首先要將一段時(shí)間用戶(hù)的訪(fǎng)問(wèn)日志組織成用戶(hù)訪(fǎng)問(wèn)事務(wù)數(shù)據(jù).設(shè)L為用戶(hù)訪(fǎng)問(wèn)日志,其中的一個(gè)項(xiàng)l∈L包括用戶(hù)的IP地址l.ip,用戶(hù)的標(biāo)識(shí)符l.uid,被存取頁(yè)的URL地址l.url,以及存取訪(fǎng)問(wèn)的時(shí)間l.time.定義1(用戶(hù)訪(fǎng)問(wèn)事務(wù)).用戶(hù)訪(fǎng)問(wèn)事務(wù)被定義為t=〈ipt,uidt,{(lt1.url,lt1.tim),...,(ltm.url,ltm.tim)}〉where,for1≤k≤m,ltk∈L,ltk.ip=ipt,ltk.uid=uidt,ltk.tim-ltk-1.tim≤C.表示一個(gè)用戶(hù)對(duì)一個(gè)Web站點(diǎn)的一次訪(fǎng)問(wèn).這里,C是一個(gè)固定的時(shí)間窗.設(shè)一個(gè)Web站點(diǎn)有n個(gè)Web頁(yè)面,每一個(gè)頁(yè)面可以被記為ai,i=1,...,n;那么A={a1,...,an}表示頁(yè)面的集合,則t可以被簡(jiǎn)記為t=〈at1,at2,...,atm〉,其中ati=lti.url且ati∈A.對(duì)Log進(jìn)行處理,找到每一個(gè)事務(wù).尋找訪(fǎng)問(wèn)事務(wù)的算法為:(1)對(duì)日志進(jìn)行預(yù)處理;(2)根據(jù)每一個(gè)訪(fǎng)問(wèn)者的IP,劃分日志,即在Log中找到每一個(gè)訪(fǎng)問(wèn)者的訪(fǎng)問(wèn)記錄集;(3)對(duì)每一個(gè)訪(fǎng)問(wèn)者的訪(fǎng)問(wèn)記錄集,根據(jù)C進(jìn)行分割,找到每一個(gè)訪(fǎng)問(wèn)者的每一次訪(fǎng)問(wèn)記錄集,這時(shí),每一個(gè)訪(fǎng)問(wèn)者的每一次訪(fǎng)問(wèn)記錄集就構(gòu)成了一個(gè)訪(fǎng)問(wèn)事務(wù);(4)在一個(gè)訪(fǎng)問(wèn)事務(wù)內(nèi)每一個(gè)被訪(fǎng)問(wèn)的頁(yè)面按照被訪(fǎng)問(wèn)的時(shí)間排序;(5)最終按時(shí)間排序的所有訪(fǎng)問(wèn)事務(wù)構(gòu)成我們進(jìn)行挖掘的基礎(chǔ).處理完日志后我們就得到一個(gè)用戶(hù)訪(fǎng)問(wèn)事物集.2b用戶(hù)訪(fǎng)問(wèn)事務(wù)語(yǔ)法s的模式定義用戶(hù)訪(fǎng)問(wèn)事務(wù)文法的目的是要得到用戶(hù)訪(fǎng)問(wèn)事務(wù)中用戶(hù)訪(fǎng)問(wèn)的有序性.一個(gè)Web站點(diǎn)的節(jié)點(diǎn)表是一個(gè)有限非空的符號(hào)集合,如A={a1,...,an}.A*表示在A上所有的有限長(zhǎng)度序列的集合,它包括空序列ε,表示用戶(hù)訪(fǎng)問(wèn)該站點(diǎn)時(shí)可能訪(fǎng)問(wèn)的路徑.A+表示集合A*-{ε}.一個(gè)在A上的序列集合L是A*的任何子集,一個(gè)用戶(hù)訪(fǎng)問(wèn)事務(wù)文法是一種能夠從一個(gè)用戶(hù)的訪(fǎng)問(wèn)事務(wù)中得到所有訪(fǎng)問(wèn)序列的設(shè)備.定義2(用戶(hù)訪(fǎng)問(wèn)事務(wù)文法(useraccesstransactiongrammar)).在一個(gè)用戶(hù)訪(fǎng)問(wèn)事務(wù)t中,其用戶(hù)訪(fǎng)問(wèn)文法是一個(gè)四元組G=〈V,Σ,S,P〉,其中:(1)V是一個(gè)有限的序列集合:V={S,A1,...,An}.(2)Σ是t事務(wù)中所訪(fǎng)問(wèn)到的頁(yè)面的集合:Σ={a1,...,am};V∩Σ=?.被訪(fǎng)問(wèn)的頁(yè)面a1到am按被訪(fǎng)問(wèn)的時(shí)間排序,并給予相應(yīng)的下標(biāo).(3)S∈V是一個(gè)惟一的起始符.(4)P是一個(gè)具有導(dǎo)出形式Ai→at或Ai∈atAj的有限導(dǎo)出規(guī)則集,其中Ai,Aj∈V,at∈(Σ∪ε),序列Aj中所有頁(yè)面的下標(biāo)都要大于t,并且序列Aj的第1個(gè)頁(yè)面的下標(biāo)等于t+1.在一個(gè)用戶(hù)訪(fǎng)問(wèn)事務(wù)文法G中,一個(gè)一步導(dǎo)出d:s1?s2是指,當(dāng)應(yīng)用一個(gè)導(dǎo)出規(guī)則從s1序列得到s2時(shí),稱(chēng)為從s1一步導(dǎo)出s2.一個(gè)導(dǎo)出d:s1?*sn是指,有限步地應(yīng)用一步導(dǎo)出規(guī)則從s1得到sn.一個(gè)序列格式是從惟一的起始符S導(dǎo)出的任意導(dǎo)出形式.由一個(gè)用戶(hù)訪(fǎng)問(wèn)事務(wù)文法G產(chǎn)生的序列集合是所有的僅由終止符構(gòu)成的序列格式的集合,L(G)={s∈Σ*|S?*s}.如果有一個(gè)序列s∈L(G),s至少有兩個(gè)從起始符S的不同導(dǎo)出,則稱(chēng)G為歧義的,否則稱(chēng)G是非歧義的.在一個(gè)用戶(hù)訪(fǎng)問(wèn)事務(wù)文法中,一個(gè)句子格式至少有一個(gè)非終止符.因此,形如Ai→a的導(dǎo)出被稱(chēng)為最終導(dǎo)出,因?yàn)槠浣K止了導(dǎo)出過(guò)程;形如Ai→ajAj的導(dǎo)出被稱(chēng)為轉(zhuǎn)換導(dǎo)出.一個(gè)導(dǎo)出的長(zhǎng)度D被定義為在該序列被導(dǎo)出的過(guò)程中導(dǎo)出規(guī)則被應(yīng)用的次數(shù),在用戶(hù)訪(fǎng)問(wèn)事務(wù)文法中相應(yīng)為所產(chǎn)生的序列的長(zhǎng)度,序列長(zhǎng)度為m的序列我們稱(chēng)為m序列.m序列的集合成為m序列集.定義3(用戶(hù)序列訪(fǎng)問(wèn)事務(wù)st).一個(gè)用戶(hù)訪(fǎng)問(wèn)事務(wù)經(jīng)過(guò)用戶(hù)訪(fǎng)問(wèn)事務(wù)文法處理所得到的序列的集合.用戶(hù)訪(fǎng)問(wèn)事務(wù)集ST為用戶(hù)序列訪(fǎng)問(wèn)事務(wù)st的集合,見(jiàn)表1.從用戶(hù)訪(fǎng)問(wèn)事務(wù)中生成用戶(hù)序列訪(fǎng)問(wèn)事務(wù)的算法如下:算法.GUSATG/*GeneratingUserSequenceAccessTransactionGrammars*/對(duì)每一個(gè)用戶(hù)訪(fǎng)問(wèn)事務(wù)應(yīng)用該算法就可以生成一個(gè)用戶(hù)序列訪(fǎng)問(wèn)事務(wù),最終形成用戶(hù)序列訪(fǎng)問(wèn)事務(wù)集.3序列關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則發(fā)現(xiàn)主要用于在事物數(shù)據(jù)庫(kù)中發(fā)現(xiàn)大項(xiàng)集之間的關(guān)聯(lián)度.為了在用戶(hù)序列訪(fǎng)問(wèn)事務(wù)集中發(fā)現(xiàn)序列關(guān)聯(lián)規(guī)則,我們給出如下定義:定義4(序列的支持度Support(s)).給定一個(gè)序列s,在用戶(hù)序列訪(fǎng)問(wèn)事務(wù)集ST中,含有序列s的事務(wù)的個(gè)數(shù).定義5(序列關(guān)聯(lián)規(guī)則).s,s′代表在用戶(hù)序列訪(fǎng)問(wèn)事務(wù)集中的兩個(gè)序列,其支持度大于一個(gè)給定的支持度閾值,則定義可信度confidence為confidence(s,s′)=support(s,s′)support(s).(1)如果confidence(s,s′)≥θ,θ為給定的一個(gè)閾值(例如5%),那么s→s′構(gòu)成一條序列關(guān)聯(lián)規(guī)則.注:定義5中的support(s,s′)表示在一個(gè)ST中,同時(shí)含有s和s′的用戶(hù)序列訪(fǎng)問(wèn)事務(wù)的個(gè)數(shù).我們所采用的發(fā)現(xiàn)算法為文獻(xiàn)所述的AprioriHybrid關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法.為了進(jìn)一步評(píng)價(jià)所發(fā)現(xiàn)的序列關(guān)聯(lián)規(guī)則,我們引入互信息的概念,即如果兩個(gè)序列頻繁出現(xiàn)在同一個(gè)用戶(hù)序列訪(fǎng)問(wèn)事務(wù)中,那么它們之間有較高的關(guān)聯(lián)度:ΜΙ(s,s′)=logΡ(s,s′)Ρ(s)Ρ(s′).(2)由于這種方式?jīng)]有考慮到在一個(gè)用戶(hù)序列訪(fǎng)問(wèn)事務(wù)中,s和s′其中一個(gè)或兩個(gè)都未出現(xiàn)所造成的影響,因此我們進(jìn)一步引入平均互信息概念來(lái)處理兩個(gè)序列缺席的情況,即如果兩個(gè)序列總是同時(shí)出現(xiàn)或者同時(shí)不出現(xiàn),那么它們之間有較高的關(guān)聯(lián)度:EΜΙ(s,s′)=∑s,ˉs∈S∑s′,ˉs′通過(guò)序列關(guān)聯(lián)規(guī)則以及對(duì)所發(fā)現(xiàn)的規(guī)則進(jìn)一步求出互信息和平均互信息,就可以發(fā)現(xiàn)由用戶(hù)訪(fǎng)問(wèn)事物文法而得到的用戶(hù)序列訪(fǎng)問(wèn)事務(wù)集中的更加有用的信息.與Cooley所用到的方法相比較,Cooley等人的方法處理的是用戶(hù)訪(fǎng)問(wèn)事務(wù)集,而沒(méi)有考慮到一個(gè)事務(wù)內(nèi)部被訪(fǎng)問(wèn)頁(yè)面的被訪(fǎng)問(wèn)相關(guān)性.本文的方法所產(chǎn)生的關(guān)聯(lián)規(guī)則集包含Cooley的方法所產(chǎn)生的關(guān)聯(lián)規(guī)則集.在本文的方法中,由用戶(hù)訪(fǎng)問(wèn)事物文法得出這種被訪(fǎng)問(wèn)頁(yè)面的序列之間的相關(guān)性,可以更好地為站點(diǎn)的設(shè)計(jì)者服務(wù),以發(fā)現(xiàn)的序列關(guān)聯(lián)規(guī)則被用于改進(jìn)Web站點(diǎn)的結(jié)構(gòu)設(shè)計(jì)為例(如圖1和圖2所示).通過(guò)對(duì)用戶(hù)序列訪(fǎng)問(wèn)事務(wù)集的挖掘,如果在1-序列集中我們可以發(fā)現(xiàn)(B,A)→(D,C)這樣一條關(guān)聯(lián)規(guī)則,其可信度為80%(等價(jià)與Cooley的方法),其解釋為訪(fǎng)問(wèn)了B,A這兩個(gè)節(jié)點(diǎn)的用戶(hù)有80%也訪(fǎng)問(wèn)了D,C這兩個(gè)節(jié)點(diǎn),那么通過(guò)對(duì)2-序列集進(jìn)行挖掘,我們針對(duì)該規(guī)則可以進(jìn)一步知道AB→CD,可信度為70%,這樣一條序列關(guān)聯(lián)規(guī)則的解釋為訪(fǎng)問(wèn)了A緊接著又訪(fǎng)問(wèn)B的用戶(hù)有70%訪(fǎng)問(wèn)C后又緊接著訪(fǎng)問(wèn)了D.由此,我們可以在B和C之間加入一個(gè)從B指向C的鏈接以方便用戶(hù).也就是說(shuō),通過(guò)對(duì)序列關(guān)聯(lián)規(guī)則的發(fā)現(xiàn),我們可以更好地理解我們所發(fā)現(xiàn)的知識(shí),以用于改進(jìn)Web站點(diǎn)的結(jié)構(gòu)設(shè)計(jì).4結(jié)論:互信息的引入和生成我們實(shí)驗(yàn)的主要目的是:(1)給出我們的方法和Cooley的方法的比較.求1-序列的關(guān)聯(lián)規(guī)則(等價(jià)于Cooley的方法),我們得到一條關(guān)聯(lián)規(guī)則,見(jiàn)表2.根據(jù)我們的方法,相對(duì)于這條關(guān)聯(lián)規(guī)則,算法發(fā)現(xiàn)的結(jié)果見(jiàn)表3.顯然,與Cooley的方法相比,我們的方法對(duì)發(fā)現(xiàn)的規(guī)則給出了更好的解釋.(2)互信息的引入.引入互信息可以更好地對(duì)所發(fā)現(xiàn)的序列關(guān)聯(lián)規(guī)則給予解釋,見(jiàn)表4.對(duì)比式(1)和式(2),在引入P(s′)參數(shù)后,可以更好地說(shuō)明s和s′的相關(guān)性.即如果P(s)和P(ss′)固定不變,那么隨著P(s′)的增加,兩個(gè)序列互信息的值會(huì)縮小.較大的P(s′)會(huì)降低互信息的值.互信息的值更好地解釋了所發(fā)現(xiàn)的規(guī)則.如表4所示的第2和第3條規(guī)則:第2條規(guī)則相對(duì)于第3條規(guī)則而言有較低的可信度,但卻有較高的互信息和平均互信息值.即說(shuō)明/cjc/cjccw.html/cjc/absc.html/cjc/abstc.html比/cjc/cjccw.html/cjc/othersc.html/cjc/ly.html更有可能是一條用戶(hù)訪(fǎng)問(wèn)的路徑.(3)算法執(zhí)行的性能.我們采用AprioriHybrid來(lái)求得序列關(guān)聯(lián)規(guī)則.圖3給出算法執(zhí)行時(shí)每一遍所用的時(shí)間.圖4則給出最小支持度和算法的運(yùn)行時(shí)間的關(guān)系.5基于序列關(guān)聯(lián)規(guī)則的訪(fǎng)問(wèn)關(guān)聯(lián)在Web挖掘中,傳統(tǒng)的一些關(guān)聯(lián)規(guī)則發(fā)現(xiàn)方法可以發(fā)現(xiàn)Web頁(yè)面之間用戶(hù)訪(fǎng)問(wèn)的關(guān)聯(lián)度.由于Web站點(diǎn)內(nèi)含豐富的Web頁(yè)面結(jié)構(gòu)信息,也由于用戶(hù)的訪(fǎng)問(wèn)總是要遵循一定的訪(fǎng)問(wèn)順序,使得本文提出一種新的可以發(fā)現(xiàn)用戶(hù)訪(fǎng)問(wèn)序列之間的關(guān)聯(lián)度的方法——序列關(guān)聯(lián)規(guī)則發(fā)現(xiàn)方法.該方法包含了Cooley的方法,并且進(jìn)一步發(fā)現(xiàn)用戶(hù)不同的訪(fǎng)問(wèn)序列之間的關(guān)系.在該方法中,我們首先挖掘用戶(hù)訪(fǎng)問(wèn)日志以得到用戶(hù)訪(fǎng)問(wèn)事務(wù),然后根據(jù)正則文法定義了一種新的用戶(hù)訪(fǎng)問(wèn)事務(wù)文法,以用于從用戶(hù)訪(fǎng)問(wèn)事務(wù)中得到用戶(hù)序列訪(fǎng)問(wèn)事務(wù),同時(shí)也給出了相應(yīng)的算法.然后應(yīng)用關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法進(jìn)而發(fā)現(xiàn)序列關(guān)聯(lián)規(guī)則.為了進(jìn)一步評(píng)價(jià)所發(fā)現(xiàn)的序列關(guān)聯(lián)規(guī)則,本文引入互信息的概念.發(fā)現(xiàn)的序列關(guān)聯(lián)規(guī)則可以幫助Web站點(diǎn)的設(shè)計(jì)者更好地