張春娜，李軼然

（遼寧科技大學(xué) 軟件學(xué)院，遼寧 鞍山114051）

0 引 言

隨著網(wǎng)絡(luò)的快速發(fā)展，Web站點的體系結(jié)構(gòu)以及服務(wù)模式與以往大大不同，用戶訪問模式與傾向自由度也發(fā)生了深層次的變化。網(wǎng)站設(shè)計人員需盡可能的優(yōu)化站點吸引用戶，他們也試圖去發(fā)現(xiàn)一些隱含性的信息，比如某些Web活動的有用模式或是潛在的行為知識，日志文件中用戶的關(guān)聯(lián)性、訪問習(xí)慣、時序關(guān)系等。這樣，通過有效的分析即可了解用戶的行為模式。

一般意義上聚類過程是對某一空間域有限數(shù)據(jù)集中有限點實施聚類，其最終目的是將有用數(shù)據(jù)劃分為不同的類，保持異類低相似度，同類高相似度［1］。以一個 Web站點為例，通常頁面間的關(guān)系是網(wǎng)狀的，彼此之間通過鏈接相聯(lián)系，同一個節(jié)點下的子頁面相似度較高，也可理解為用戶的對該類子頁面的興趣度相似。用戶訪問Web站點的時序性與興趣度具有正相關(guān)性，對于一個用戶群，興趣相投者往往訪問時序也有一定相似性，體現(xiàn)某種規(guī)律。比如，用戶us1依次訪問了網(wǎng)頁UR1，UR2，UR3，...，URn，可以以下列式子來表示該用戶訪問順序與興趣度之間的關(guān)系

I（UR1）＞I（UR2）＞I（UR3），...，＞I（URn）

這個式子說明用戶對頁面的訪問次序與興趣度存在一定關(guān)系，最先被訪問的頁面往往興趣度較高，因此需要采用一種聚類方法對日志文件中頁面關(guān)系予以處理［2］，對相似度較高頁面實施歸類，據(jù)此管理者可根據(jù)這種規(guī)律性調(diào)整站點結(jié)構(gòu)，迎合用戶個性化要求。目前，對Web站點日志的分析通常的步驟是對站點信息的預(yù)處理［3－4］，用戶訪問行為處理，然后進(jìn)行路徑聚類。

其中文獻(xiàn)［5］將用戶事務(wù)轉(zhuǎn)化為一個三元組，提出一種基于用戶訪問事務(wù)聚類算法。聚類過程中考慮了用戶訪問頁面的先后次序以及時長，但缺乏對訪問頻繁度的分析，這一點與本文考察重點相悖。

文獻(xiàn)［6］所構(gòu)建的系統(tǒng)基于代理技術(shù)，是在線推薦引擎和URL聚類的結(jié)合體。提出的推薦規(guī)則集生成算法，主要參考關(guān)聯(lián)規(guī)則，算法同時考慮了用戶瀏覽次數(shù)和停留時間等因素，考慮因素較為全面，只是沒有涉及頁面的訪問次序。

文獻(xiàn)［7］采用模糊聚類的方法來處理用戶訪問事務(wù)。其思想是基于模糊和模糊集理論，提出一種從集群模糊邊界考慮問題的路徑聚類方法，同樣，該方式也沒有考慮用戶訪問頁面的先后次序；文獻(xiàn)［8］另辟蹊徑，從提高路徑搜索性能的角度出發(fā)，結(jié)合道路建設(shè)的相似性，給出預(yù)期路徑；而文獻(xiàn)［9］是提出了一種新的頁面預(yù)處理方式，是數(shù)據(jù)整理工作的前提；文獻(xiàn)［10］是關(guān)于數(shù)據(jù)集的聚類簇隸屬關(guān)系的討論；文獻(xiàn)［11］則從競爭策略的角度獲取最佳聚類數(shù)。

以上文獻(xiàn)中缺少一個共同的聚類分析切合點——網(wǎng)頁訪問次序，也就是同類中不同節(jié)點的有序關(guān)系，而這正式本文所研究的重點。

1 聚類準(zhǔn)備

路徑聚類是找出用戶訪問行為中某種特性，它體現(xiàn)在用戶點擊頁面路徑的相似性所形成的域中。用戶對Web站點的訪問過程用興趣軌跡來描述，即由一組鏈接地址所構(gòu)成的訪問路徑。用戶群體現(xiàn)出相似路徑時，則可將該群體劃分為一類，并為其定義訪問行為模式，在其域上進(jìn)行聚類分析，獲取有用信息。

日志文件中存放用戶訪問信息，格式需遵循W3C標(biāo)準(zhǔn)，站點的結(jié)構(gòu)可用有向圖表示，如D＝（V，M），其中V代表頁面集合，M代表頁面鏈接集合。據(jù)此可以得到用戶行為訪問模式。

定義1 Web站點日志文件：假定F為用戶訪問信息，令F＝｛（fu.ip，fu.us，fu.url，fu.time）｜1≤u≤n，f∈F｝，其中F代表Web站點日志信息，fu表示實際用戶u的訪問信息，包括用戶本身的IP地址fu.ip、用戶的標(biāo)識fu.us、用戶訪問頁的地址fu.url、用戶訪問頁面的具體時間fu.time。

下一步工作的重點是日志文件的整理，即剔除非研究對象，包括頁面中的視頻、圖像、聲音等多媒體文件信息，保留文字和HTML格式信息。經(jīng)過整理后，還需識別出用戶事務(wù)信息。

在定義用戶事務(wù)時，需提到一點，用戶對某一頁面的訪問稱為會話，不同用戶或是同一用戶對指定頁面的間隔時間訪問理解為不同的會話，因為用戶對頁面的訪問可能會有多次。處理事務(wù)過程中，需定義一個時間間隔以區(qū)分不同會話。

定義2 用戶訪問事務(wù)

其中，m為用戶u訪問的最后一個頁面。用戶在網(wǎng)不同訪問行為用T＝fi.time－fj.time表示，記T為該用戶的時間窗口，1≤i，j≤m。

定義3 用戶訪問子事務(wù)：不同用戶不同時間段的訪問行為可進(jìn)一步劃分為用戶訪問子事務(wù)。設(shè)用戶訪問事務(wù)為UT，則子事務(wù)可表示為：.url｜1≤v≤n｝∈ ｛fu.url｜1≤u≤n｝，即用戶訪問事務(wù)中任何一個頁面列表長度不超過原始頁面列表長度的子列表。

定義4 頁面鏈接參數(shù)：Web站點中頁面不僅僅包括內(nèi)容信息頁面，也需要功能性頁面，比如導(dǎo)航頁、搜索頁、主題頁等。頁面作用各有不同，數(shù)據(jù)挖掘中要加以區(qū)分，不同類型頁面附應(yīng)于相應(yīng)權(quán)值，涉及到應(yīng)用的范圍權(quán)值有高低之分，設(shè)定是依據(jù)經(jīng)驗，并不失一般性，也可能選取樣本數(shù)據(jù)實施訓(xùn)練進(jìn)行自適應(yīng)計算。這里，為了方便以及更好的說明頁面的差異性，以經(jīng)驗量化指標(biāo)限定，稱作頁面鏈接向量參數(shù)

式中：RLk——第k個頁面的頁面鏈接參數(shù)，si——該頁面被鏈接的總數(shù)，S——頁面間總鏈接數(shù)，Q——頁面加權(quán)因子。

為了遍歷每個用戶事務(wù)，本文試圖找到通用的處理方式，步驟如下：

（1）站點用戶信息篩選；

（2）對經(jīng)過篩選后的站點日志文件進(jìn)行預(yù)處理；

（3）將日志中每個用戶進(jìn)行歸類，即將每個IP地址相關(guān)內(nèi)容劃分成集；

（4）確定訪問事務(wù)，利用時間窗口T確定每個用戶的訪問內(nèi)容，每段訪問內(nèi)容構(gòu)成一個數(shù)據(jù)集，稱為用戶訪問事務(wù)，進(jìn)而劃分子事務(wù)。

（5）考察訪問次數(shù)與停留時間，對于同一用戶同一地址的記錄，在訪問事務(wù)中記錄一次，其它訪問只記錄次數(shù)且不放入數(shù)據(jù)集；每次訪問的停留時間則需一一記錄，附于每個事務(wù)末端；

（6）數(shù)據(jù)集整理，按時間對用戶訪問事務(wù)進(jìn)行排序，組成時間序列事務(wù)集。

偽代碼如下：

在一個時間窗口內(nèi)，每一個用戶訪問事務(wù)都有一個頁面鏈接列表；同樣，相對于全體用戶訪問事務(wù)而言，時間窗口內(nèi)，新生成的用戶事務(wù)代表了一個非重復(fù)的訪問路徑，數(shù)據(jù)集中存放了用戶某一段時間訪問路徑，尋找到路徑的相似性，通過算法即可路徑聚類，最終發(fā)現(xiàn)用戶訪問模式。

2 K－PathSearch

本文提出K－PathSearch路徑聚類算法，該方法通過生成的數(shù)據(jù)集進(jìn)行特征聚類，同時考慮到用戶的興趣度，對用戶訪問頁面的先后次序進(jìn)行處理，經(jīng)過多次迭代聚類，得到真正反映用戶實際情況的訪問序列。本文在充分考慮訪問次序的前提下，剔除了多余的同址訪問記錄，比照其它方法，該算法更加高效可靠，具體算法思想如下：

（1）設(shè)定數(shù)據(jù)集F，設(shè)定參數(shù)k用來劃分聚類數(shù)；

（2）設(shè)計聚類中心，并對其初始化。即將數(shù)據(jù)集中n個事務(wù)，以k為單位劃分聚類，注意聚類中每個用戶事務(wù)必須保證與聚類中心相似度總和最??；

（3）依據(jù)聚類中心模型重新計算聚類中心，并將聚類結(jié)果演化成矩陣，整理聚類中心與相關(guān)矩陣，組成收斂評價函數(shù)Q；

（4）經(jīng)過有限次循環(huán)計算收斂評價函數(shù)Q，算法返回值應(yīng)逐步收斂，直到符合要求止，否則跳轉(zhuǎn)到（3）繼續(xù)迭代。

定義5 興趣度：傳統(tǒng)的聚類分析是對給定的空間散列點有限集的取樣，或是對某一數(shù)據(jù)體的分析與歸納，最終使零散變?yōu)橐?guī)整；而針對Web站點，因其具有一定的規(guī)律性，站點間可組成有序的序列。因此，用戶訪問Web站點對某一頁面的關(guān)注度，可表示為Interest（fuurl，RL），用戶訪問地址序列可表示為（f1url，f2url，···，fnurl），不同興趣度決定訪問次序

其中Interest（fkurl，RL）1＜k＜n。

設(shè)有群體用戶u1，u2，···，un，訪問 Web站點用數(shù)列表示

可見，訪問次序不僅適用于單體，亦適用于群體特征描述。分析數(shù)列得到群體用戶訪問路徑url11，url12，url15，url13，url14，相應(yīng)興趣度可表示為

其中，U代表群體，即個體用戶的訪問次序決

定整個群體的興趣度。

需提出一點，若用戶訪問事務(wù)中出現(xiàn)重復(fù)出現(xiàn)的url，注意用戶地址興趣度的累計，地址信息只記錄一次即可。

定義6 相似度：相似度與興趣度存在一定因果關(guān)系，即在同一鏈接中，兩個用戶對于某一網(wǎng)頁興趣度一致，說明兩個用戶相似度較高；反之較低。設(shè)兩個用戶訪問事務(wù)分別為Si和Sj，則相似度可表示為

其中，興趣度差值的絕對值越接近于0，表明二者相似度越高。

定義7 聚類中心：基于回歸分析中散點圖，本文假設(shè)用戶興趣度為自變量，選擇的鏈接地址為因變量，則不同類型的訪問用戶相關(guān)數(shù)據(jù)點應(yīng)產(chǎn)生聚合，并最終擬合。通過定義3，得到用戶訪問路徑圖如圖1所示。

圖1 用戶訪問路徑

由上所述，給出如下定義：用戶訪問最長擬合路徑，即，將從初始地址出發(fā)，集合成員所有訪問地址最為相似的最長路徑。由此，得到聚類C＝｛ci｜1＜i＜n｝，ci中包括若干個用戶訪問事務(wù)，一個類中的事務(wù)相似度較高，群體中心，即類中興趣度累加最大的路徑，全路徑可用下式表示

其中，最大路徑表示為

參考定義5中數(shù)列，即可得到最長擬合路徑，在這個數(shù)列中，我們假定用戶訪問路徑是定長的，為了方便處理，將其轉(zhuǎn)化為向量形式，表示如下

將用戶訪問事務(wù)向量演化成矩陣

式中：m——Web站點日志中所有用戶事務(wù)，n——每個用戶事務(wù)的長度，即訪問地址數(shù)，這里假定長度定長。

本文提出K－PathSearch算法并非傳統(tǒng)的層次聚類方法，而是以相似度為參考條件，對路徑進(jìn)行分類的方法。算法的核心思想是將事務(wù)集合劃分為若干個聚類，cen（ci）表示第i組依據(jù)興趣度組成的頁面，需要提出的是，這個路徑可能并不是真實存在，要考慮的問題圍繞式（5）與式（3）展開，定義聚類擬合函數(shù)如下所示

式中：vi，j——矩陣中一項，最大值m和n可相等，亦可不等。對擬合函數(shù)的求解過程做如下假設(shè)：由于W是V的子集，這里的操作分兩個步驟，分別將Q（V，W，C）中除了W之外其它兩個參數(shù)分別設(shè)為常量，以進(jìn)行求解。

（1）設(shè)C為常量，求解Q（V，W，C）

其中，1≤k≤m。

（2）設(shè)W為常量，求解Q（V，W，C）：

1）設(shè)定初始常量C0，求解Q（V，W，C），從而得到初始W0；

2）設(shè)k＝0，以C0、W0推導(dǎo)C1，依次類推，得到C2，···，Cm，進(jìn)而得到W1，W2···，Wn。推導(dǎo)過程中，若Q（V，W，Ci）＝Q（V，W，Ci＋1），則輸出相應(yīng)W，結(jié)束算法；否則，執(zhí)行第三步；

3）以C0、W0推導(dǎo)W1，同樣得到W2，···，Wn，進(jìn)而得到C1，C2···，Cm。此時，若Q（V，Wj，C）＝Q（V，Wj＋1，C），則輸出相應(yīng)C，算法結(jié)束；否則跳轉(zhuǎn)到第二步。

依此計算，經(jīng)過有限次的迭代，算法將收斂并得到一個局部最優(yōu)解。

3 實驗驗證

本文實驗數(shù)據(jù)取自于電子商務(wù)旅游網(wǎng)站服務(wù)器日志，區(qū)間為2011年5月至2011年9月，數(shù)據(jù)經(jīng)過預(yù)處理剔除掉一些不必要的數(shù)據(jù)，得到多條內(nèi)容訪問記錄。整個網(wǎng)站包括225個頁面，用戶訪問頁面容量56M，經(jīng)過算法分析，得到用戶訪問事務(wù)3221個，群體用戶平均訪問路徑長度為6.2。本文按時間區(qū)間對五組數(shù)據(jù)進(jìn)行驗證，算法應(yīng)用前后對比表見表1。

表1 算法應(yīng)用前后對比

從實驗數(shù)據(jù)看出，算法應(yīng)用后聚類數(shù)較之前提高26%，聚類中心平均長度提高38%，提高幅度較大，達(dá)到預(yù)期效果。二者對站點訪問用戶的細(xì)分以及站點內(nèi)容本身的分類影響較大，其直接對用戶的劃分產(chǎn)生作用，更能有效的反應(yīng)用戶的個性化特征，故，有助于管理者調(diào)整網(wǎng)站結(jié)構(gòu)、細(xì)分用戶，條理清晰。因此，算法可認(rèn)為是有效的。

4 結(jié)束語

基于用戶對Web站點的訪問次序，本文提出了KPathSearch算法，它是一種分割聚類方法，用于聚類用戶訪問路徑。文中重點考察用戶的興趣度，在設(shè)定用戶訪問事務(wù)的基礎(chǔ)上，引入頁面鏈接參數(shù)，利用參數(shù)因子以區(qū)分頁面性質(zhì)，這樣即可對經(jīng)過預(yù)處理后的頁面實施二次整理，以方便頁面聚類分析。再者，算法應(yīng)用后聚類數(shù)顯著增加，更加便于理解用戶的真實需求，網(wǎng)站管理者可及時調(diào)整站點結(jié)構(gòu)以迎合客戶。同時，算法也考慮了頁面之間的關(guān)系，比照用戶相似度試圖提供一些個性化較強(qiáng)的服務(wù)。

［1］Vassiliki A Koutsonikola，Athena I Vakali.A fuzzy bi－clustering approach to correlate web users and pages［J］.International Journal of Knowledge and Web Intelligence，2009，1（1／2）：3－23.

［2］LIU Yunfeng.A text information extraction algorithm based on tag xpath clustering［J］.Computer Applications and Software，2010，21（11）：199－202（in Chinese）.［劉云峰.一種基于標(biāo)簽路徑聚類的文本信息抽取算法［J］.計算機(jī)應(yīng)用于軟件，2010：21（11）：199－202.］

［3］Yang S H，Lin H L，Han Y B.Automatic data extraction from template generated Web pages［J］.Joumal of Software，2008，19（2）：209－223.

［4］Ou Jian－Chih，Lee Chang－Hung，Chen Ming－Syan.Efficient algorithms for incremental Web log mining with dynamic thresholds［J］.The VLDB Journal，2008，17（4）：827－845.

［5］LU Qun，ZHANG Zhongneng.Research on path clustering in web sites［J］.Computer Applications and Software，2008，25（8）：205－206（in Chinese）.［盧群，張忠能.Web站點的路徑聚類研究［J］.計算機(jī)應(yīng)用與軟件，2008，25（8）：205－206.］

［6］SONG Jiangchun，SHEN Junyi.An intelligent recommendation system based on web navigation path clustering［J］.Information and Control，2007，36（1）：119－124（in Chinese）.［宋江春，沈鈞毅.一個基于Web訪問路徑聚類的智能推薦系統(tǒng)［J］.信息與控制，2007，36（1）：119－124.］

［7］Hong Yu，Hu Luo，Chu Shuangshuang.Web users access paths clustering based on possibilistic and fuzzy sets theory［C］／／ADMA（1），2010：12－23.

［8］Lee Jae－Min，Hwang Byung－Yeon.Two－Phase path retrieval method for similar XML document retrieval［G］.LNCS 3681：Khosla R，et al.（Eds.）：KES，2005：967－971.

［9］WU Junjie，CHEN Junjie，ZHAO Shuanzhu.Research of path clustering based on the access interest of users［J］.Computer Engineering and Applications，2005，41（36）：170－171（in Chinese）.［吳俊杰，陳俊杰，趙栓柱.基于用戶訪問興趣的路徑聚類研究［J］.計算機(jī)工程與應(yīng)用，2005，41（36）：170－171.］

［10］CHEN Jianmei，LU Hu，SONG Yuqing.A possibility fuzzy clustering algorithm based on the uncertainty membership［J］.Journal of Computer Research and Development，2008，45（9）：1486－1492（in Chinese）.［陳健美，陸虎，宋余慶.一種隸屬關(guān)系不確定的可能性模糊聚類方法［J］.計算機(jī)研究與發(fā)展，2008，45（9）：1486－1492.］

［11］Yu Yijun，Lin Huaizhong，Chen Chun.Personalized web recommendation based on path clustering［C］／／Proceedings of the 10th WSEAS International Conference on Computers，2006：148－153.