基于有向圖的緩存內(nèi)容選取算法研究

基于有向圖的緩存內(nèi)容選取算法研究

web路徑挖掘主要影響用戶(hù)體驗(yàn)的背景隨著互聯(lián)網(wǎng)硬件技術(shù)的發(fā)展，網(wǎng)站的數(shù)據(jù)內(nèi)容和數(shù)據(jù)結(jié)構(gòu)的范圍變得越來(lái)越大。大量的數(shù)據(jù)和訪(fǎng)問(wèn)帶來(lái)了網(wǎng)站快速響應(yīng)的巨大挑戰(zhàn)。在海量數(shù)據(jù)中選取合適的內(nèi)容同時(shí)讀取并緩存,是提高網(wǎng)站響應(yīng)速度和用戶(hù)對(duì)此滿(mǎn)意度的重要方法。而在這些數(shù)據(jù)如何選取合適的數(shù)據(jù)作為緩存內(nèi)容成為關(guān)鍵的問(wèn)題之一。其中web路徑挖掘?yàn)榫彺鎯?nèi)容的選取問(wèn)題給出了自己的方法,就是根據(jù)用戶(hù)訪(fǎng)問(wèn)站點(diǎn)的結(jié)構(gòu)關(guān)聯(lián)度,選取用戶(hù)會(huì)連續(xù)訪(fǎng)問(wèn)的相關(guān)的頻繁路徑數(shù)據(jù)進(jìn)行緩存,減少硬盤(pán)讀寫(xiě)次數(shù),降低站點(diǎn)服務(wù)器壓力,提高用戶(hù)請(qǐng)求的響應(yīng)速度。本文主要闡述的帶權(quán)路徑模式挖掘(WeightedPathPatternmining),是在AprioriAll算法中增加頻度為權(quán)值,緩存內(nèi)容的選取上不僅僅在原來(lái)AprioriAll算法中選取用戶(hù)訪(fǎng)問(wèn)內(nèi)容的頁(yè)面結(jié)構(gòu)關(guān)聯(lián)度,而且增加選取內(nèi)容的整體訪(fǎng)問(wèn)頻度,從而提高緩存內(nèi)容為用戶(hù)訪(fǎng)問(wèn)頁(yè)面的命中度,更好地發(fā)揮了緩存機(jī)制的作用。1網(wǎng)站內(nèi)容記錄1.1運(yùn)行速度和擴(kuò)基于鏈路的方法是當(dāng)瀏覽器訪(fǎng)問(wèn)一個(gè)Web頁(yè)時(shí),服務(wù)器端會(huì)在響應(yīng)請(qǐng)求頁(yè)面的同時(shí)在后臺(tái)取出用戶(hù)可能會(huì)連續(xù)訪(fǎng)問(wèn)的Web頁(yè)存入服務(wù)器的高速緩沖區(qū),以后當(dāng)用戶(hù)點(diǎn)擊下一條鏈接時(shí),若所訪(fǎng)問(wèn)頁(yè)面已經(jīng)存在于服務(wù)器的高速緩沖區(qū),則只需從緩沖區(qū)取出web頁(yè)進(jìn)行響應(yīng),提高了服務(wù)器的響應(yīng)速度和并發(fā)響應(yīng)能力。1.2基于頻域的方法,充分利用有限資源,提高用戶(hù)訪(fǎng)問(wèn)對(duì)于緩存內(nèi)容的選取,目前有兩種常見(jiàn)的解決方法:一種是系統(tǒng)自動(dòng)記錄頁(yè)面中每個(gè)鏈接被訪(fǎng)問(wèn)的次數(shù)并按頻率排序,頻率越高說(shuō)明被訪(fǎng)問(wèn)的可能性越大,當(dāng)需要時(shí)選擇頻率高的頁(yè)面緩存。另一種是基于歷史的方法,記錄用戶(hù)經(jīng)常訪(fǎng)問(wèn)的站點(diǎn),并通過(guò)數(shù)據(jù)挖掘的方法獲得用戶(hù)訪(fǎng)問(wèn)頻繁的路徑,并只緩存這些頻繁路徑中的頁(yè)面,從而最大程度上充分利用有限資源,提高站點(diǎn)的響應(yīng)速度。以上兩種方法中,前一種方法考慮了站點(diǎn)的訪(fǎng)問(wèn)頻率,后一種方法考慮了用戶(hù)訪(fǎng)問(wèn)站點(diǎn)的關(guān)聯(lián)性和序列性。但兩種方法沒(méi)有結(jié)合考慮用戶(hù)訪(fǎng)問(wèn)站點(diǎn)的頻率性和關(guān)聯(lián)性。本文介紹的加權(quán)路徑模式挖掘則可以克服這個(gè)缺點(diǎn)。2路徑模型開(kāi)挖2.1緩沖頁(yè)面頁(yè)面之間的關(guān)系在因特網(wǎng)上用戶(hù)一次瀏覽中依次訪(fǎng)問(wèn)的站點(diǎn)形成瀏覽路徑,本文結(jié)合例子來(lái)說(shuō)明,如圖1所示:原始瀏覽路徑為{(A,B,CD,E,D,F,D,G,A,H,I,J,K,J,L,J,I,M,I,N,I,H,O)}。路徑站點(diǎn)的權(quán)定義為站點(diǎn)在瀏覽路徑中出現(xiàn)的次數(shù)。可以得到結(jié)果如表1。第一種最容易想到的利用緩存頁(yè)面站點(diǎn)的選擇是按照用戶(hù)瀏覽路徑的訪(fǎng)問(wèn)頻率或者次數(shù)。如表1,可以看出如果按照頁(yè)面的訪(fǎng)問(wèn)次數(shù)為標(biāo)準(zhǔn),選擇緩存頁(yè)面則當(dāng)選擇的緩存頁(yè)面的數(shù)量為4時(shí),顯然為I,J,D,A或者為I,J,D,H。如當(dāng)緩存頁(yè)面選擇數(shù)量為4時(shí)分別為I,J,D,A,頁(yè)面之間沒(méi)有相互的順序關(guān)聯(lián)關(guān)系。用戶(hù)的訪(fǎng)問(wèn)A后,再訪(fǎng)問(wèn)B或者H時(shí)卻沒(méi)有緩存,沒(méi)有有效地達(dá)到緩存的目的。2.2面后頻繁序列提取第二種緩存選取算法思想是:選取的緩存中的頁(yè)面在用戶(hù)瀏覽路徑中有著前后序列關(guān)系,一些頁(yè)面為用戶(hù)訪(fǎng)問(wèn)頁(yè)面后的后續(xù)路徑中的頁(yè)面,有更高的機(jī)率被用戶(hù)后續(xù)訪(fǎng)問(wèn),從而提高緩存的效果,更好地提高網(wǎng)站的響應(yīng)速度和減輕服務(wù)器的負(fù)擔(dān)。可以利用數(shù)據(jù)挖掘的關(guān)聯(lián)規(guī)則,發(fā)現(xiàn)用戶(hù)瀏覽路徑的頻繁序列集,并緩存相關(guān)站點(diǎn)。從瀏覽路徑中發(fā)現(xiàn)潛在的用戶(hù)瀏覽路徑的頻繁序列稱(chēng)為路徑模式挖掘(pathpatternmining)。2.3確定頻繁路徑(1)生成深度路徑。由瀏覽過(guò)程中的每個(gè)站點(diǎn)構(gòu)成的序列稱(chēng)為原始路徑,其中每一個(gè)沒(méi)有重復(fù)站點(diǎn)的最長(zhǎng)訪(fǎng)問(wèn)路徑,稱(chēng)為深度路徑(deeppath)。既包括到達(dá)一個(gè)新頁(yè)面的向前引用,也包括由于訪(fǎng)問(wèn)失敗或未找到所需信息造成的向后引用。只有向前引用是有用的信息,因此從原始路徑中刪除向后引用,得到一組瀏覽子序列,其中每個(gè)子序列是從用戶(hù)的訪(fǎng)問(wèn)起點(diǎn)開(kāi)始的深度路徑。如圖1表示的原始瀏覽路徑,可以得到深度路徑為{(ABCDE),(ABCDF),(ABCDG},(AHIJK),(AHIJL),(AHIM),(AHIN),(A-HO)}。(2)從得到的深度路徑中獲取頻繁路徑(frequentpath),即在全部瀏覽過(guò)程出現(xiàn)次數(shù)超過(guò)給定閾值的序列。頻繁路徑的搜索從一維開(kāi)始,利用迭代找到所有滿(mǎn)足閾值的頻繁路徑。(3)確定頻繁深度路徑,即不包含在其他任何頻繁深度路徑中的頻繁路徑。一個(gè)頻繁深度路徑對(duì)應(yīng)于Web中一條頻繁出現(xiàn)的最深瀏覽路徑。3頻域生成算法3.1有向圖深度遍歷在一次瀏覽路徑過(guò)程中,可以看到瀏覽的結(jié)點(diǎn)形成了一個(gè)特殊的有向圖。特點(diǎn)為:可以從一個(gè)起點(diǎn)沿方向深度優(yōu)先可以遍歷所有的結(jié)點(diǎn)。因此生成頻繁路徑的過(guò)程中,可以通過(guò)一次有向圖的深度優(yōu)先遍歷的過(guò)程找到所有的頻繁路徑。有向圖深度遍歷過(guò)程生成頻繁路徑算法如下:在深度優(yōu)先遍歷過(guò)程中,若棧頂有未被訪(fǎng)問(wèn)的鄰接頂點(diǎn),則鄰接頂點(diǎn)入棧,并重復(fù)。直到遇到鄰接頂點(diǎn)非首次訪(fǎng)問(wèn),則記錄當(dāng)前棧內(nèi)頂點(diǎn),形成一條深度路徑。此時(shí)退棧并重復(fù),直到下一結(jié)點(diǎn)為首次訪(fǎng)問(wèn),則訪(fǎng)問(wèn)下一結(jié)點(diǎn),并入棧此結(jié)點(diǎn)。以上過(guò)程重復(fù),直至棧為空或棧內(nèi)結(jié)點(diǎn)未有未被訪(fǎng)問(wèn)的有向邊,即遍歷了所有結(jié)點(diǎn),得到所有的深度路徑。3.2計(jì)算模式1階大序列尋找頻繁路徑與關(guān)聯(lián)規(guī)則中的大項(xiàng)集有相似之處,它們都是滿(mǎn)足在事務(wù)庫(kù)中出現(xiàn)的足夠次數(shù)(規(guī)定的閾值),但是頻繁路徑必須是連續(xù)且有順序的,而大項(xiàng)集僅僅是項(xiàng)的組合,根據(jù)這個(gè)特點(diǎn),本文運(yùn)用序列模式挖掘中的大序列計(jì)算機(jī)方法AprioriAll的一個(gè)改進(jìn)算法,從第一步生成的深度路徑集中找到滿(mǎn)足閾值的所有頻繁路徑。AprioriAll算法的過(guò)程與關(guān)聯(lián)規(guī)則中的大項(xiàng)集搜索過(guò)程類(lèi)似,也是由1階大序列構(gòu)造2階候選序列,掃描數(shù)據(jù)庫(kù)計(jì)算候選序列的支持?jǐn)?shù),得到2階大序列,這樣依次循環(huán),直至找到所有的大序列為止。AprioriAll算法的詳細(xì)過(guò)程描述如下:這里用到這樣一個(gè)性質(zhì):如果A是大序列,那么A的所有子序列也必定是大序列;反之,如果一個(gè)序列的某個(gè)子序列不是大序列,那么這個(gè)序列也一定不是大序列。AprioriAll算法適用于處理這樣的序列:序列中的項(xiàng)集有順序,但不一定是連續(xù)出現(xiàn)的。但是,在本文中要處理的序列不僅僅有順序,而且必須是連續(xù)出現(xiàn)的。假設(shè)Lk-1表示k-1階大序列,Ck表示k階候選序列。首先對(duì)Lk-1進(jìn)行自連接,對(duì)于兩個(gè)k-1階大序列S、T:如果S的后k-2個(gè)項(xiàng)集和T的前k-2個(gè)項(xiàng)集相同,那么就由S和T的第k-1個(gè)項(xiàng)集連接,得到一個(gè)k階候選序列,這就保證了連續(xù)性和有序性,同時(shí)生成的候選序列數(shù)也減少了,提高了算法的效率。然后,對(duì)候選序列進(jìn)行消減,如果k階候選序列A的某個(gè)Lk-1階子序列不在Lk-1中,那么A就不可能是大序列,需要將它從候選序列集Ck中刪除。消減也是一個(gè)重要的步驟,可以減少掃描數(shù)據(jù)庫(kù)的次數(shù)。比如:2階大序列為L(zhǎng)2={(AE),(EF)},由上面的連接條件可得到C3={AEF)}。因?yàn)?AF)不在L2中,所以(AEF)不是3階候選序列,應(yīng)當(dāng)刪除。4加權(quán)頻繁路徑在這里對(duì)上文運(yùn)用生成深度路徑算法得到深度路徑集,然后以其為對(duì)象,用改進(jìn)的AprioriAll算法計(jì)算頻繁路徑,設(shè)閾值為2。第一次掃描深度路徑集,得到1階頻繁路徑。然后產(chǎn)生2階候選頻繁路徑,第二次掃描深度路徑集計(jì)算候選頻繁路徑的支持?jǐn)?shù),得到2階頻繁路徑。接著構(gòu)造3階候選頻繁路徑,如此循環(huán),直到5階候選頻繁路徑為空,循環(huán)結(jié)束。計(jì)算頻繁路徑的執(zhí)行過(guò)程和結(jié)果如圖2所示。最后從得到的頻繁路徑中過(guò)濾掉子頻繁路徑,生成最終的頻繁深度路徑。本例最后得到的頻繁深度路徑為{(ABCD)(AHIJ)},詳細(xì)過(guò)程不再贅述。從圖2可知,如果選擇四個(gè)結(jié)點(diǎn)作為緩存,當(dāng)然會(huì)選擇支持?jǐn)?shù)為3的頻繁路徑。加權(quán)頻繁路徑的加權(quán)支持?jǐn)?shù)定義為支持?jǐn)?shù)與相應(yīng)階所有路徑結(jié)點(diǎn)權(quán)和的積。由前文結(jié)點(diǎn)權(quán)定義及所求的權(quán)可以得出頻繁路徑(ABCD)的權(quán)的和為:2+1+1+3=7。此頻繁路徑的加權(quán)支持?jǐn)?shù)為:3*7=21。同理可得加權(quán)頻繁路徑(AHIJ)的加權(quán)支持?jǐn)?shù)為:2*(2+5+4+2)=22。盡管(ABCD)支持?jǐn)?shù)大于(AHIJ)的支持?jǐn)?shù),但其加權(quán)支持?jǐn)?shù)小于(AHIJ)的加權(quán)支持?jǐn)?shù)。從表2可以看出各種算法的優(yōu)點(diǎn)與不足,加權(quán)頻繁路徑算法結(jié)合依據(jù)簡(jiǎn)單訪(fǎng)問(wèn)頻率和關(guān)聯(lián)規(guī)則的優(yōu)點(diǎn),對(duì)緩存內(nèi)容的選取算法做到更好的均衡。使得緩存內(nèi)容命中率與有效性在整體效果有了更佳表現(xiàn),即有了更好的加權(quán)支持?jǐn)?shù)。加權(quán)支持?jǐn)?shù)反應(yīng)了結(jié)點(diǎn)關(guān)聯(lián)的頻繁程度,并且考慮頻繁路徑中結(jié)點(diǎn)的訪(fǎng)問(wèn)頻率更加全面地反應(yīng)了用戶(hù)訪(fǎng)問(wèn)路徑結(jié)點(diǎn)的相互和頻率均衡。5帶權(quán)路徑挖掘算法的改進(jìn)隨著電子商務(wù)的高速發(fā)展,以及交友網(wǎng)站等用戶(hù)關(guān)聯(lián)性強(qiáng)的一些基于web2.0的大型網(wǎng)站的興起和迅猛發(fā)展,未來(lái)web挖掘的一個(gè)重要應(yīng)用方向?qū)⑹穷?lèi)似大型網(wǎng)站系統(tǒng)的以用戶(hù)特征為基礎(chǔ)的各種知識(shí)的挖掘,而與用戶(hù)最為密切的將會(huì)是用戶(hù)路徑模式挖掘。在本文提出的帶權(quán)路徑挖掘算法的應(yīng)用過(guò)程中,其權(quán)值可以根據(jù)需要和實(shí)際參數(shù)賦為不同的意義和變量,如門(mén)戶(hù)網(wǎng)站中的文章的正文、評(píng)論以及文字與多媒體等不同類(lèi)型的信息因文件大小或客戶(hù)不同響應(yīng)要求而對(duì)他們分別賦有相應(yīng)權(quán)值,給予客戶(hù)更好的體驗(yàn)。本文針對(duì)挖掘?qū)ο蟮奶匦?對(duì)AprioriAll算法中生成候選序列的函數(shù)做了一定的改進(jìn),并對(duì)路徑賦