基于Web日志的自適應站點優(yōu)化研究與應用
2009-04-29 00:00:00麥權(quán)幫,傅仁毅
電腦知識與技術(shù) 2009年14期
摘要:論文主要從理論上分析了一種自適應網(wǎng)站性能優(yōu)化算法，該算法首先以Web站點的URL為行、以用戶的UserID為列，建立URL_UserID關(guān)聯(lián)矩陣，元素值為用戶的訪問次數(shù);接著對行向量進行分析獲得頻繁閉相關(guān)頁面集;最后，對頻繁閉相關(guān)頁面集進一步處理發(fā)現(xiàn)頻繁訪問路徑。Web站點可根據(jù)頻繁路徑自動改進鏈接結(jié)構(gòu)，提高Web站點對所有用戶的整體服務性能，提高客戶訪問的效率。
關(guān)鍵詞:頻繁訪問路徑;URL_UserID 關(guān)聯(lián)矩陣;閉相關(guān)頁面集;自適應站點
中圖分類號:TP393文獻標識碼:A文章編號:1009-3044(2009)14-3671-02
An Adaptive Optimization Method Based on the Web Logs
MAI Quan-bang， FU Ren-yi
(Shunde Polytechnic， Shunde 528333， China)
Abstract: A theoretical analysis of adaptive Web site performance optimization algorithm for the first to the Web site URL for the trip to the UserID users listed， the establishment of URL_UserID association matrix， the elements of value for the user visits; proceeded to Row vector analysis of the relevant pages were frequently closed-end， the frequent closure of the relevant pages set processed further found that frequent access path. Web site under frequent automatic path to improve link structure， improve the Web site for all users of the overall service performance， enhance the efficiency of customer visits.
Key wrods: Frequent access path; URL_UserID association matrix; closed-related pages; adaptive site
1 引言
Internet技術(shù)和智能電子商務的普及，人們希望能夠快速準確的從Web頁中尋找需求的信息，各網(wǎng)站設計者們也希望能夠根據(jù)用戶的偏好確定網(wǎng)站內(nèi)容的設置，提高其市場競爭力。自適應Web網(wǎng)站能夠更好地理解用戶，發(fā)現(xiàn)用戶隱藏的興趣和群體用戶的行為規(guī)律，從而制定相應的信息過濾策略，按照用戶的個性化信息進行主動式的推薦服務。
自適應Web網(wǎng)站(Adaptive Web Site)[1-2]是指Web服務器通過學習用戶的訪問模式，自動地改進Web站點信息的組織與顯示。Chen等人[3]首先將數(shù)據(jù)挖掘技術(shù)應用于Web服務器日志文件，以期發(fā)現(xiàn)用戶瀏覽模式。他們提出了最大前向引用序列MFR的概念，并用它將用戶會話分割成一系列的事務，然后采用與關(guān)聯(lián)規(guī)則相似的方法挖掘頻繁瀏覽路徑。
2 Web站點的表示
2.1 用戶瀏覽行為描述
Web服務器日志包括訪問日志、引用日志和代理日志。通過對這些日志進行恰當?shù)念A處理后，可以L=
T=
URLt={(L1t.URL，L1t.HITS)，(L2t.URL，L2t.HITS)，…，(Lmt.URL，Lmt.HITS)}
其中，Lt∈L，Lt.IP=IPt，Lt.UID=UIDt，t≥1，HITS表示到目前為止用戶UIDt瀏覽頁面Lt.URL的次數(shù)。
2.2 Web站點拓撲結(jié)構(gòu)
一個Web站點的拓撲結(jié)構(gòu)就是一個有向圖，而用戶在一段時間內(nèi)的訪問模式則為其子圖。具有相似訪問子圖的客戶就是需求相似的用戶，即用戶群體聚類。用戶訪問頻繁的有向邊，就是頻繁路徑。假設Web站點G就是一個具有如下形式的有向圖:
G=(N，Np，E，Ep)
其中，N為結(jié)點集:NP={Node∈N，{(UserID，HITS)}n}，n≥1，記錄客戶UserID及其訪問結(jié)點Node的次數(shù)，為結(jié)點屬性集;E為有向邊集:Ep={(e∈E，{Number of path}p)}m，p，m≥1，記錄有向邊及該有向邊所在路徑的編號，為有向邊屬性集。從有向圖G的結(jié)點集N中可以得到該站點的所有URL從相應的結(jié)點屬性集NP中可以獲得訪問每一個結(jié)點的UserID及相應的訪問次數(shù)，據(jù)此可以建立如下所示的關(guān)聯(lián)矩陣Mmxn:
其中，Mij 是第j個用戶在一段時間內(nèi)訪問第i個URL的次數(shù)。因此某行向量Mj表示所有用戶對URLj的訪問情況，某列向量Mi表示第i個用戶對該Web站點中所有URL的訪問情況。即行向量既代表了站點的結(jié)構(gòu)，又反映出用戶共同的訪問模式;列向量既歸納了用戶類型，也描繪出了用戶的個性化訪問子圖。由于行向量反映了所有客戶對站點中不同頁面的訪問情況，如果客戶對某些頁面的訪問情況相同或相似，那么這些頁面可聚為一類，然后根據(jù)相關(guān)Web頁面，進一步分析還能獲得用戶訪問模式，即頻繁訪問路徑。在實際應用中，?坌M[i，j]>0，令M[i，j]=1。那么矩陣中每一個行向量中含1的個數(shù)就是該網(wǎng)頁的訪問頻繁度。每一個列向量中，為1的位表示其所對應的URL網(wǎng)頁在同一個用戶會話中。當某一個URL的行向量中“1”的個數(shù)大于給定支持度，則稱該頁面為頻繁訪問頁。
假設從用戶會話數(shù)據(jù)庫得到5個頻繁訪問頁的網(wǎng)頁訪問情況，U1=10100，U2=01010，U3=10101，U4=10111，U5=01011，則得到的矩陣如圖1所示。
3 相關(guān)頁面集的挖掘
3.1 相關(guān)概念
定義1:許多用戶會話中往往同時包含有一些網(wǎng)頁，用C表示這些網(wǎng)頁構(gòu)成的集合，C的支持度Supp(c)表示包含C的用戶會話所占用戶會話總數(shù)的百分比(有時也用包含C的事務的頻數(shù)簡化表示)。例如C={url1，url2，...，urlk}，在矩陣 URL-SID中，SUPP(C)=U1∧U2∧...∧Uk中“1”的數(shù)目。如果C的支持度不小于給定最小支持度閾值δ，則稱C為相關(guān)頁面集。
由Apriori原理，頻繁項集的任意子集也是頻繁項集，所以要從事務庫中挖掘出所有的頻繁項集，結(jié)果是非常多的。根據(jù)閉項集[6]的概念，可以大大的減少挖掘結(jié)果中冗余的頻繁項集，由此我們提出閉相關(guān)頁面集。
定義2:設C1和C2為兩個相關(guān)頁面集，C1?奐C2，且滿足條件:任給用戶會話S包含C1則S也包含C2成立，那么稱C1被C2覆蓋。記為C1∠C2。
定義3:設C為一相關(guān)頁面集，如不存在相關(guān)頁面集C'，C∠C'，即C不被任何相關(guān)頁面集覆蓋，則稱C為閉相關(guān)頁面集。
3.2 挖掘閉相關(guān)頁面集
本文在URL_SID矩陣上遞歸的挖掘閉相關(guān)頁面集。因為將不再掃描數(shù)據(jù)庫，對閉相關(guān)頁面集的挖掘都集中在位矢量上，從而大大提高了速度。
在各頻繁訪問頁的頁面訪問情況的位矢量被設定好后，算法利用位矢量在各頻繁訪問頁之間建立有向圖。顯然，相關(guān)頁面集{url1，url2，...，urlk}的支持度就是URL_SID矩陣中，位矢量U1∧U2 ∧...∧Uk中“1”的個數(shù)，其中“∧”表示邏輯與操作符。
當位矢量Ui∧Uj中1的個數(shù)不小于最小支持度，設Q是頻繁訪問頁上的一個序，在Q中i>j，則算法在頁面i和頁面j之間作一有向邊i→j，表明項集{i，j}是一個頻繁二項集。
命題1:{i1，i2，...，ik}是頻繁頁面集，如在ik與u之間沒有關(guān)聯(lián)邊，則{i1，i2，...，ik，u}不可能是頻繁頁面集。
證明:因為ik，u之間沒有邊，{ik，u}是非頻繁頁面集。由Apriori性質(zhì):任何包含非頻繁頁面集的的項集也是非頻繁頁面集。所以，{i1，i2，...，ik，u}不可能是頻繁頁面集。
因此如果要將頻繁k項集{url1，url2，...，urlk}擴展為頻繁k+1項集，只需考慮項Uk出發(fā)，指向的頻繁頁面urlj，如U1∧U2∧...∧Uk∧Uj中1的個數(shù)不少于支持度閾值，則{url1，url2，...，urlk，urlj}也是頻繁頁面集。
定義4:設Q是頻繁訪問頁上的一個序，且所有相關(guān)頁面集中的頁面按Q排列，如f={i1，i2，...，ik}為一相關(guān)頁面集，則相關(guān)頁面集的集合:
Cf={C|C={i1，i2，...，ik}∪{j1，j2，...，jl}，im>jn，1≤m≤k，1≤n≤l} (1)
稱為f的前綴項集簇。集合
C'f ={C|C={i1，i2，...，ik}∪{j}，im>j， 1≤m≤k}(2)
稱為f的一項擴展前綴項集簇。有關(guān)系 C'f?哿Cf 成立。
命題2:設I={i1，i2，...，ik}是一個相關(guān)頁面集，則I中所有的相關(guān)頁面集的集合可表示為C=Ci1∪Ci2∪…∪Cik。
證明 當所有相關(guān)頁面集按Q排列，則這些相關(guān)頁面集可按第1個頻繁訪問頁進行分類，每一類即以各頻繁訪問頁為前綴的相關(guān)頁面集簇。
命題3:設f={i1，i2，...，ik}為一相關(guān)頁面集，則相關(guān)頁面集簇Cf可表示為
Cf =∪C(f∪u)，u 證明:同命題2，Cf也可按f后所跟的頻繁訪問頁u進行分類，且由于所有相關(guān)頁面集按Q進行排序，u 有了命題2和命題3，證明算法可以遞歸的遍歷所有的相關(guān)頁面集。并且可以證明算法可以找出所有的閉相關(guān)頁面集。 4 基于URL-userID關(guān)聯(lián)矩陣的頻繁訪問路徑發(fā)現(xiàn) 頻繁訪問路徑可以在基于URL_UserID關(guān)聯(lián)矩陣Web頁面聚類的基礎上進行發(fā)現(xiàn)，一方面是因為這些頁面為相似客戶群體所訪問，一方面則是受Web站點拓撲結(jié)構(gòu)約束而劃分在一起的。對于已發(fā)現(xiàn)的Web頁面聚類Pm，若Pm中所有URL都不在一條路徑上，則該Web頁面聚類Pm就不能構(gòu)成頻繁訪問路徑。若Pm中存在n條路徑，現(xiàn)將其分為n個Pim?奐Pm(1≤i≤n)，每個Pim為一條單一路徑。 現(xiàn)在我們來計算路徑頻度:設站點SWeb中的路徑P={URL1，URL2，...，URLn}的頻度fp為其中每一條最短路徑尾節(jié)點被訪問次數(shù)之和與該站點所有URL被訪問次數(shù)之和的比值，即有: (4) 那么滿足頻度閾值的路徑即為頻繁訪問路徑。 若Pim與已處理過的某個或某些URL類位于同一路徑且路徑頻度都在閾值許可的范圍內(nèi)，則可將它們合并起來，計算該合并后路徑的頻度fp′，若路徑頻度fp′超過閾值∧，則該路徑即為頻繁訪問路徑。 5 Web站點的性能優(yōu)化的方法 Web站點的優(yōu)化，是指從整體上改進站點，學習所有用戶的行為，讓所有人的瀏覽變得容易，而不是針對每個用戶分別做出修改，不需要實時性。(下轉(zhuǎn)第3679頁) (上接第3672頁) 由于Web站點是基于假設大多數(shù)用戶的訪問模式而設計的，是不知道用戶頻繁訪問路徑的，所以它往往與用戶的頻繁訪問路徑存在較大差別。但此時可以利用用戶獲取所需信息的難易程度來評價該Web站點的設計優(yōu)劣，并依此進行優(yōu)化。通常是以用戶獲取所需信息而經(jīng)過的超級鏈接的數(shù)目來表示用戶獲取信息的難易程度，因此對Web瀏覽路徑的優(yōu)化就是在盡量不破壞Web站點原有文檔和超級鏈接結(jié)構(gòu)的前提下，通過增加新的超級鏈接或文檔使得用戶獲取所需信息容易化。如果在一定時期內(nèi)大多數(shù)用戶都表現(xiàn)出訪問路徑的相似性，此時Web站點就要做相應的訪問路徑優(yōu)化。例如在用戶群頻繁訪問路徑中設計一條直指終點的超級鏈接，就可以顯著提高整個用戶群的訪問頻率。因此，我們可以充分利用用戶訪問的頻繁路徑來自動改進Web站點連接的結(jié)構(gòu)，提高Web站點對所有用戶的整體服務性能，同時提高客戶訪問的效率。 6 結(jié)束語 該論文從理論上論證了基于URL_UserID關(guān)聯(lián)矩陣進行頻繁閉相關(guān)頁面集和頻繁訪問路徑挖掘的可行性，提出了在頻繁訪問路徑的基礎上進行自動改進Web站點連接的結(jié)構(gòu)的方法。但是論文中并沒有對其方法進行實驗驗證，還需要進一步的研究。 參考文獻: [1] Perkowitz M.，Etzioni O.Towards adaptive Web sites:Conceptual framework and case study. Artificial Intelligence. 2000，118:245-275. [2] Zaiane OR，Xin M，Han J.Discovering Web access patterns and trends by applying OLAP and data mining technology on Web logs.In:Proc of Advances in Digital Libraries Conf.Santa Barbara.CA.1998. [3] 宋擒豹，沈鈞毅.Web日志的高效多功能挖掘算法[J].計算機研究與發(fā)展，2001，3(38).
