一種快速的Web用戶和URL聚類算法

張線媚

摘 要：本文提出一個基于Web日志的用戶和URL聚類的快速算法。利用用戶瀏覽行為建立用戶事務矩陣，在此基礎上綜合考慮用戶瀏覽時間以及點擊頻率來獲取用戶權值和頁面權值，構建帶權值的模糊聚類。為了縮小運算量，構造等價事務，進行事務約減；并針對于FCM算法簇數目初始化敏感的問題，提出了一種全局搜索的方法，搜尋最優的類中心數。實驗證實，該算法在精度和效率上都獲得了大大提高。

關鍵字：權值距離；等價事務；事務約減；全局搜索

中圖分類號： TP274.2 文獻標識碼：A 文章編號1672-3791（2015）06（a）-0000-00

因為網站的內容及結構的組織形式是否合理直接決定了網站是否受歡迎，所以需要對Web訪問信息進行有效的聚類，分析挖掘出合理有效的運行模式和隱含信息等知識，而在Web訪問信息的聚類過程中，最常用到的方法是頁面聚類和用戶聚類。頁面聚類方法主要是通過分析頁面之間的關聯知識來改進站點的組織結構，而用戶聚類則是以相似訪問喜好的用戶作為集合進行聚類，為同一集合的用戶提供針對性的服務。因此聚類算法研究在Web訪問信息挖掘中起到決定性的作用。

目前多數日志聚類以Web站點的URL為行、以User-ID為列，建立關聯矩陣，對用戶的訪問時間進行離散后用作矩陣的元素值，經過User-ID的相似性分析，得到相似客戶群體，經過對URL的相似性度量獲得相關Web頁面。

本文首先清洗日志數據，然后根據用戶的瀏覽行為建立矩陣，通過對矩陣的列向量和行向量進行模糊聚類，從而得到用戶聚類和URL聚類。為了提高聚類算法的精度和整體效率，在確定初始中心時采用了全局搜索方法。

1.日志的清洗

1.1 用戶事務集合

WEB服務器日志包括訪問日志、引用日志和代理日志，數據清洗主要完成錯誤和冗余數據的剔除和重復數據的合并操作，用來表示日志信息，利用最大時間間隔法來得到用戶事務集合。結合用戶在頁面上的停留時間及其點擊次數，總結用表示用戶事務集合，對于， 有：。其中： ，m表示站點的URL數，表示到截止到當前時間用戶在上的瀏覽時間，表示點擊次數。

1.2瀏覽時間的離散化

將用戶事務在站點URL上的瀏覽時間屬性用間隔（即離散值）表示，將時間離散化。離散值和實際時間的關系如表1所示：

表1 離散值與瀏覽時間對照表

在進行離散化時，當用戶在URL上的停留時間少于5s時，則離散值取0，表示URL是導航頁而不是內容頁，應該刪除。考慮主頁訪問的普遍性，所以對主頁的研究意義不大，也應該刪除，即使用戶對網頁的瀏覽時間很長，離散值也只有3。這樣可有效判別區分在用戶事務的相似性，當用戶瀏覽時間過長或過短時，如果采用連續時間則會造成聚類結果畸變。

1.3用戶瀏覽矩陣和用戶點擊矩陣

（1）用戶瀏覽矩陣：

其中：代表Web站點URL的個數，代表用戶事務數，代表第個用戶事務對第個URL 的訪問時間總和。

（2）用戶點擊矩陣：

其中：為Web站點URL的個數，為用戶事務數，為第個用戶事務對第個URL 的點擊次數總和。

用戶瀏覽矩陣中用戶對該站點中所有URL的訪問情況可表示為，即列向量；所有用戶對URL“”的訪問情況表示為，即行向量。分別度量二者的相似性，就能得到用戶聚類和URL聚類。

2.聚類算法

2.1 模糊聚類

在數學上模糊聚類可用如下的目標函數求極值來表示：

（1）

（2）

綜合考慮（1）式的優化和（2）式的約束條件，用拉格朗日乘數法可求得到和分別為：

（3） （4）

對（1）式優化采用FCM算法：

a.取常數，令迭代次數t=0，任選聚類中心；

b.對按式（3）求得；

c.由式（4）算出下一次類別中心；

d.如果，退出迭代；否則，令t的值加1，跳至步驟b；

數據點的分類在每次迭代中同時進行調整，而且聚類中心需要更新。當先后兩次迭代隸屬度矩陣很接近，則算法處于收斂。在得到用戶瀏覽矩陣以后，分別對行向量和列向量進行聚類，得到相似的用戶簇和URL簇。

2.2 帶屬性權重的歐氏距離

如果采用傳統的歐氏距離，度量列向量和的距離公式為： （5）

度量行向量和的距離公式為：

（6）

由于傳統的距離公式忽略權重，故提出帶權重的歐氏距離公式：

（7）

其中：表示第k維數據的重要性。

由此可以求得帶權重的模糊聚類算法目標函數為：

在URL聚類和用戶聚類中，分別代表第k個用戶的權重和第k個URL的權重。

2.3頁面權重

用戶具體的瀏覽行為體現在用戶對頁面的點擊次數和停留時間，采用極值法對點擊次數進行歸一化處理，則對應的點擊權重值為：

（8）

其中：為單頁面點擊的最大次數，為單頁面點擊的最小次數。

同理可得到對應的瀏覽時間權重值：

（9）

其中：為單頁面瀏覽的最長時間，為單頁面瀏覽的最短時間。

結合用戶的瀏覽時間權重和點擊權重，構建URL權重計算的線形公式：

（10）

其中：

（11）

（12）

2.4用戶權重

同理對于用戶訪問頻率和訪問時間，采用權重概念可得到用戶權重的計算公式：

（13）

其中：

（14）

（15）

為歸一化的點擊次數權重，反映了各個用戶總的點擊次數情況；為歸一化的瀏覽時間權重，反映了各個用戶總的瀏覽時間情況。

3.聚類中心的選取

模糊聚類算法中，目標聚類數目K要提前設定，由于算法的迭代都要求沿著使J減小的方向進行，而J可能有多個極值點。當確定的初始聚類中心靠近一個局部極小點時，則算法收斂到局部最小。為了解決這個問題，在聚類中可以使用全局優化方法中的模擬退火技術，但是這樣就增加了計算量，而且收斂速度也會相應減慢，所以實際應用中不常使用。

本文在確定類別數目時采用了全局搜索的方法，即取數據空間中的多個數值進行初始化，則初始中心可分布在較廣的范圍，而且滿足了數據的多樣性。在聚類過程中利用有效性度量函數逐步減少聚類數目K的值，直到有效性函數的變化趨向于某個閾值停止。

3.1取樣

在初始化時為了減少計算量，對原始數據集合進行取樣。采用隨機取樣，選取能基本代表原始數據特性的數據作為訓練集，在訓練集中求得初始化中心點，從而可以快速地找到最優的簇數目。

3.2等價事務和事務約減

當兩個訪問事務的瀏覽時間以和點擊次數相等或相近時，則它們對C個類中心的隸屬度也是相同或相近的。

（1）等價事務：

當隨機的兩個事務對應的與，滿足，，其中為事前選定的任意小整數。而且，它們所對應的和，滿足：，，其中為事先設定的任意小整數。則它們為一對等價事務。

（2）事務約減：

有了等價事務的概念，原瀏覽矩陣和點擊矩陣可以看成多個子集的并集

，其中：

因為等價事務對各中心的隸屬度相同，即：，所以可以利用子集中任意一個事務來代表整個子集，即對訪問矩陣和點擊矩陣進行約減。

3.3全局搜索

為了避免FCM算法中事先確定聚類數目帶來的難題，引入Xie-Beni聚類有效性度量： （16）

可以設定一個較大，（為約減后的事務數目）。確保在最小化Xie-Beni聚類有效性度量的情況下，使得設定的目標函數最優，從而得到的簇數目為最優值。

過程執行步驟如下：

（1）對原始數據集進行取樣，進行數據約減，得到

（2）對簇數目進行初始化

（3）任選k個對象為最初的簇中心集合

（4）計算對象的隸屬度矩陣

（5）由隸屬度矩陣得到新的簇中心集合

（6）重復隸屬度和簇中心的計算過程，當目標函數處于收斂時結束。

（7）迭代XB函數，令，閾值為，當時停止迭代，最后得到簇數目k；否則繼續，令k=k-1，跳轉至（4）

因為最優簇數目是從訓練集求得中，故計算量大為減少。全局的聚類和迭帶是在全局搜索求得最優化簇數目后進行的，而且求解的結果在訓練集中，所以聚類的效率大為提高。

4.算法仿真及分析

仿真數據來自站點的日志數據，下載URL為598的WWW服務器日志文件，選取40000條記錄，對日志進行清洗，最終得到1034個用戶事務。算法的性能分析從算法的有效性和效率兩方面進行比較。

（1）算法的有效性：與傳統的FCM算法比較，適當地調整聚類閾值，得到圖1。

圖1 算法的有效性比較

Fig1.Comparison of the validity of two algorithms

通過圖1中的對比，可以看到本文的算法在用戶聚類和URL聚類上，有效性都是高于FCM算法。

（2）算法的效率比較：仿真得到如圖2結果。

圖2 算法的效率比較

Fig2.Comparison of the performance of two algorithms

算法的效率主要通過CPU運行的時間來衡量，從圖2的顯示結果我們看到本文的算法在進行用戶聚類和URL聚類時，CPU運行時間比FCM算法要小得多，即本文算法在效率上遠勝于FCM算法。

5.結語

本文在對用戶瀏覽時間做了離散處理后提出了一個基于用戶離散化時間、以用戶瀏覽次數為度量的新的聚類算法，可以進行Web用戶和URL的聚類。新算法在傳統FCM算法基礎上，利用訪問時間和頻率確定用戶和URL權值，構建了帶權值的模糊聚類。另外，通過事務約減和全局搜索的方法來確定最優的初始簇中心。與已有的FCM算法對比，仿真結果表明，新算法在有效性和效率上都有很大提升。

參考文獻：

[1]宋春江，沈鈞毅.一種新的Web用戶群體和URL聚類算法的研究[J].控制與決策.2007，22（3）.

[2]田生文，黃明明.密集簇中心二次模糊聚類算法[J].計算機工程與設計.2007，28（2）.

[3]Jiawei Han， Micheline Kambr.數據挖掘概念與技術[M].北京機械工業出版社，2002.223-224.

[4]Xie X，Beni G.A validity measure for fuzzy clustering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1991，13（8）：841一847.

[5]劉小覽，趙英凱，陸金桂.數據挖掘中Fuzzy C-means的自適應聚類算法[J].南京化工大學學報（自然科學版），2001，23 （5）.