基于d-AIFCM的Web用戶聚類分析*

楊毓茹，林錦賢

（福州大學 數學與計算機科學學院，福建 福州 350108）

0 引言

在互聯網高速發展的時代，Web服務的方式趨于多元化，如何為不同需求的Web用戶提供個性化服務是當前網絡服務的研究熱點。目前，多個研究小組通過對Web用戶進行聚類分析，研究用戶的行為、興趣等信息，從而為用戶提供個性化服務。在實際應用中，用戶的興趣受多方面影響，采用FCM進行聚類分析能較客觀地反映現實世界。本文對傳統的FCM算法進行改進，并將其應用于Web用戶聚類分析，具有一定的研究意義。

1 相關工作

FCM算法對初始化數據較敏感，易陷入局部最優。針對該問題有兩種解決辦法：一種是在聚類過程中進行全局隨機搜索，參考文獻[1]利用模擬退火算法擾動當前聚類結果，擾動結果以一定的概率被認為是當前的全局最優解，但計算耗時長。另一種是改善初始化條件，參考文獻[2]提出的FaiNet算法利用生物克隆免疫系統的原理對原始數據進行初始化，但其初始抗體群是隨機生成的；參考文獻[3]利用參考區域獲取聚類中心，算法的性能依賴于區域半徑的選取。本文引入密度權值，將自適應免疫原理與FCM算法結合提出d-AIFCM算法，該算法可自動生成最佳分類，解決了FCM算法對初始聚類中心敏感的問題，能夠最大程度找到全局最優解。

2 算法設計

2.1 用戶興趣矩陣

設pj為網站頁面，ui為訪問用戶，則ui對pj的興趣度Iij為：

其中，ω表示ui對pj的瀏覽次數，Tijt表示ui第t次訪問pj的瀏覽時間。

定義1（用戶興趣矩陣）以pj為橫坐標，以ui為縱坐標，以Iij為矩陣元素構造用戶興趣矩陣：

2.2 算法思路

設DS為樣本數據集合，D為樣本的密度權值；RS為候選初始聚類中心集合；MS為初始聚類中心集合。

2.2.1 確定候選聚類中心

聚類中心處于所代表類的中心位置，且在樣本點密度連續的范圍內應該只具有一個聚類中心，以防止兩個類高度重疊。故聚類中心的選取應該滿足：具有較高的密度且與其他中心的距離盡可能大。

本文對每一個樣本點賦予密度權值：

其中，‖xi-xj‖2為樣本點間的歐氏距離，rd表示領域密度半徑：

2.2.2 確定初始聚類中心

自適應免疫系統是人體的重要防御系統。當機體受到抗原性異物刺激時，被激活的抗體會發生選擇性克隆與變異，部分與抗原具有較高親和力的個體保存并組建成為該抗原的記憶細胞。受自適應免疫系統的啟發，抗體的克隆過程相當于用戶興趣的傳播過程，變異過程相當于用戶的興趣變化，記憶細胞類似于聚類中心。將RS中的元素Ri視為抗體，DS中的元素Gj視為抗原，產生的記憶細胞即為初始聚類中心。

定義2（親和度）親和度用來衡量抗體與抗原之間的匹配性，用 τij表示：

定義3（克隆）克隆是抗體進行的自我復制過程，其克隆體的數量為：

定義4（變異）變異是抗體在克隆過程中為增加個體多樣性而進行的操作，變異公式如式（6）所示：

其中，α表示變異率，計算公式為：

2.2.3 算法實施

d-AIFCM算法的具體實施過程如下：

（1）選取候選聚類中心。

輸入：DS

輸出：RS

①初始化樣本密度權值D；

②選取擁有最大密度權值的樣本點xi，RS←xi，Set←xi，從DS中移除xi；

③選擇與xi最近的樣本點xl，Seti←xl，從DS中移除xl；

④選取xk，xk與Set中的樣本點距離最近；

⑤如果Dk小于Set中所有樣本點的密度權值，從DS中移除xk，轉到步驟④，否則轉至步驟②；

⑥輸出RS。

（2）確定初始聚類中心。

輸入：DS，RS

輸出：MS

初始閾值 σ、ε；

ForGjin DS；

IfGj與MS中的記憶細胞的距離大于ε；

計算RS中抗體Ri與抗原Gj的親和度；

選取親和度最大的前n個抗體→RS′；

計算numRi

計算Rit與Gj的親和度，按一定比例保留親和度較大的克隆體→MS′；

計算MS′中克隆體之間的歐式距離，刪除距離小于閾值σ的克隆體；

計算MS′的重心，得到記憶細胞M，M→MS；

（3）以MS中數據為初始聚類中心執行FCM算法的迭代過程。

3 實驗結果與分析

3.1 實驗數據與環境

實驗數據：實驗數據采用某學院網站2012年1月份一周內的Web日志，對Web日志進行預處理，處理后共有2 786個用戶，28個網站頁面。

實驗環境：Intel（R）Core（TM）i3-3210M@3.20 GHz CPU，4 GB內存，WindowsXP32位操作系統。采用JAVA實現算法，并利用MATLAB制作實驗圖表。

3.2 評價指標

實驗分別從迭代 次數 （I）、分支 系數（PC）[4]和分配熵系數（PE）[5]對本文算法、原始的FCM算法以及參考文獻[3]的FaiNet算法進行了比較分析。

PC值反應了模糊集群之間成員共享的程度，值越高，集群之間的重疊就越小，計算公式為：

PE是驗證模糊聚類的另一個指標，值越小，算法就越穩定，計算公式為：

3.3 實驗分析

在本實驗中，FCM算法中的加權指數b取值為2，閾值σ取0.18～0.98共9個值，進行9組實驗。實驗過程發現，類別數與σ相關，σ越小，產生的記憶細胞數越多，類別數越多，反之亦然，如圖1所示。

圖1 閾值σ-類別數關系圖

3.3.1 迭代次數的比較

FaiNet算法中的抗體群是隨機生成的，屬不完全匹配的記憶細胞法。d-AIFCM算法在進行聚類之前已經充分考慮密度權值和距離等因素，又經過克隆和變異操作，挑選出一批較精確的初始聚類中心，類別數也隨之確定，屬完全匹配記憶細胞法，避免了原始FCM算法隨機選取初始聚類中心的弊端，這樣可以加快聚類過程的收斂速度。可以通過實驗來進行驗證，實驗結果如圖2所示。

圖2 算法迭代次數比較圖

3.3.2 PC和PE的比較

PC值和PE值的對比分別如圖3、圖4所示。從圖3及圖4可知，d-AIFCM算法具有較小的重疊性和較大的穩定性。同時，算法的PC值呈上升狀態最后趨于平穩，PE值呈下降狀態最后趨于平穩，說明當類別數越多，針對用戶的分類越詳細，一個用戶所歸屬的類別數也越多，則類間的重疊性就會增加；當類別數越少，分類結果趨于平穩，極端情況下，所有用戶同屬于一個類，則重疊性最小且最穩定，但是這不符合實際情況，故在實際應用中應根據實際的需要選擇合適的σ值。

圖3 PC值比較圖

圖4 PE值比較圖

可以注意到，實驗中閾值σ取不同的值時，PC值的跳躍性較大，且PE值明顯均較高，這與數據集的特性有關，數據集是從實際的Web日志中提煉出來的，數據稀疏性較大，可能影響算法的性能。

4 結論

本文針對FCM算法中存在的對初始聚類中心敏感的問題，在自適應免疫算法的啟發下，提出了一種新的基于Web日志的聚類方法。該方法無需人工作指定類別數，類別數可在算法實施過程中自動生成，并減輕了數據初始化對聚類結果的影響。實驗表明，該算法與相關算法相比，在收斂次數和聚類效果上具有一定的優越性。在后續的工作中，將圍繞如何降低數據稀疏性對算法性能的影響等方面展開。

[1]Zhao Xinchao.Simulated annealing algorithm with adaptive neighborhood[J].Applied Soft Computing，2011，11（2）：1827-1836.

[2]SZABO A，DE CASTRO L N，DELGADO M R.FaiNet：an immune algorithm for fuzzy clustering[C].Fuzzy Systems（FUZZ-IEEE），IEEE，2012：1-9.

[3]李鑫，張繼福，蔡江輝.一種基于大密度區域的模糊聚類算法[J].小 型 微型計算 機 系 統 ，2012，33（6）：1310-1315.

[4]XieXuanli，BENIG.Avaliditymeasureforfuzzy clustering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1991，13（8）：841-847.

[5]AMIGó E，GONZALO J，ARTILES J，et al.A comparison of extrinsic clustering evaluation metrics based on formal constraints[J].Information Retrieval，2009，12（4）：461-486.