摘  要： 傳統(tǒng)FCM聚類算法存在初始聚類中心較為敏感的問題，易陷入局部最優(yōu)。針對此問題，提出了基于密度權(quán)值和自適應免疫系統(tǒng)的FCM算法（d-AIFCM）。算法在對Web用戶進行聚類分析的過程中，基于用戶群體之間的相似性，引入密度權(quán)值生成候選初始聚類中心，采用自適應免疫系統(tǒng)的原理確定初始聚類中心，自動生成最佳分類，解決傳統(tǒng)FCM算法對初始聚類中心敏感的問題。實驗結(jié)果表明，d-AIFCM算法在收斂次數(shù)和聚類效果方面較其他同類算法有所提升。

　　關鍵詞： 初始聚類中心；FCM；自適應免疫算法；Web用戶聚類

0 引言

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

1 相關工作

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

2 算法設計

　　2.1 用戶興趣矩陣

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

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

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

　　2.2 算法思路

　　設DS為樣本數(shù)據(jù)集合，D為樣本的密度權(quán)值；RS為候選初始聚類中心集合；MS為初始聚類中心集合。

　　2.2.1 確定候選聚類中心

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

　　本文對每一個樣本點賦予密度權(quán)值：

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

　　2.2.2 確定初始聚類中心

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

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

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

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

　　Ri=Ri-α（Ri-Gj）（6）

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

　　其中，r為[0，1]之間的隨機數(shù)，，DGj表示抗原Gj的密度權(quán)值。

　　2.2.3 算法實施

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

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

　　輸入：DS

　　輸出：RS

　　①初始化樣本密度權(quán)值D；

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

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

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

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

　　⑥輸出RS。

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

　　輸入：DS，RS

　　輸出：MS

　　初始閾值σ、ε；

　　For Gj in DS；

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

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

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

　　For Ri in RS′

　　Rit=Ri-α（Ri-Gj）

　　End for

　　End for

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

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

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

　　End if

　　End for

　　（3）以MS中數(shù)據(jù)為初始聚類中心執(zhí)行FCM算法的迭代過程。

3 實驗結(jié)果與分析

　　3.1 實驗數(shù)據(jù)與環(huán)境

　　實驗數(shù)據(jù)：實驗數(shù)據(jù)采用某學院網(wǎng)站2012年1月份一周內(nèi)的Web日志，對Web日志進行預處理，處理后共有2 786個用戶，28個網(wǎng)站頁面。

　　實驗環(huán)境：Intel（R）Core（TM）i3-3210M@3.20 GHz CPU，4 GB內(nèi)存，Windows XP 32位操作系統(tǒng)。采用JAVA實現(xiàn)算法，并利用MATLAB制作實驗圖表。

　　3.2 評價指標

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

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

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

　　3.3 實驗分析

　　在本實驗中，F(xiàn)CM算法中的加權(quán)指數(shù)b取值為2，閾值σ取0.18~0.98共9個值，進行9組實驗。實驗過程發(fā)現(xiàn)，類別數(shù)與σ相關，σ越小，產(chǎn)生的記憶細胞數(shù)越多，類別數(shù)越多，反之亦然，如圖1所示。

　　3.3.1 迭代次數(shù)的比較

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

　　3.3.2 PC和PE的比較

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

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

4 結(jié)論

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

參考文獻

　　[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] 李鑫，張繼福，蔡江輝.一種基于大密度區(qū)域的模糊聚類算法[J].小型微型計算機系統(tǒng)，2012，33（6）：1310-1315.

　　[4] Xie Xuanli， BENI G. A validity measure for fuzzy 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.