面向Weblog的模糊協同聚類算法

宗 瑜 金 萍 陳恩紅 李 紅 劉仁金

①(中國科學技術大學計算機科學與技術學院 合肥 230036)

②(皖西學院信息工程學院 六安 237012)

1 引言

近年來，Web技術的迅猛發展使互聯網成為信息發布與共享的重要平臺[1]。由Web應用產生的海量數據使得用戶使用信息的效率下降的現象被稱為信息超載。推薦引擎是解決信息超載的有效方法，包含基于決策規則的過濾、內容過濾、協同過濾及Weblog挖掘4種類型。Web聚類是Web信息挖掘的重要內容，通過對Web數據重組使有意義的數據聚集成簇，從而達到信息檢索和信息表示等目的[2-5]。在Weblog挖掘中，Web聚類可以分為Weblog用戶聚類和Weblog頁面聚類。Weblog用戶聚類旨在從用戶的訪問行為中發現用戶行為模式、分析用戶之間的關聯關系。每個用戶的訪問會話是由(頁面，權重)對組成的，而該對信息反映了用戶對不同頁面的興趣程度，因此對用戶會話執行聚類將會發現能反映用戶行為模式的會話簇。文獻[6]調用傳統的K-means算法對用戶會話進行聚類發現具有相似行為的用戶會話，以實現個性化推薦。Xu等人[7]首先利用概率語義分析模型對Weblog數據進行語義分析，產生語義空間S'；然后將Weblog數據映射到S'中，最后調用K-means算法在S'中對Weblog數據進行聚類，產生用戶訪問模式。Weblog頁面聚類從Web頁面的側面考慮Weblog信息挖掘，旨在發現具有相似功能或語義的頁面簇。文獻[8]詳細地闡述了基于Snippet的頁面聚類算法實現。文獻[4]對單一文本執行層次聚類，以實現搜索結果的匯總。不論是Weblog用戶聚類，還是Weblog頁面聚類，都僅反映了Weblog數據某個側面的信息。在某些應用中，Weblog的聚類結果往往是由協同出現的用戶和頁面組成，即同簇中的用戶僅對某些頁面子集感興趣，而且同簇中的頁面僅被某些用戶關注。因此，同時發現用戶簇及與之對應的頁面簇，對實現Weblog行為模式和更新頁面設計具有重要的意義[7,8]。Xu等人[9]2010年給出了一種針對Weblog的協同譜聚類算法SCC(Spectral Co-Clustering)，該算法首先將“會話-頁面”之間的關系用二分圖表示；然后調用協同譜聚類算法發現其中的聚類結果C={CSk,CPk},k=1,…,K，其中CSk為會話或用戶聚類結果，而CPk則是與之相對應的頁面聚類結果。為了降低Weblog數據稀疏性對算法的影響，Zong等人[10]給出了基于語義分析的協同聚類算法COCS(Co-Clustering in Semantic space)。COCS算法框架首先利用概率隱形語義分析(PLSA)模型學習Weblog的語義空間；然后再將Weblog數據映射到該語義空間；最后執行譜協同聚類算法發現與之對應的聚類結果。

現有的面向Weblog的協同聚類算法大多采用硬劃分方法，以發現具有共現特征的聚類結果，即用戶和頁面要么屬于某個聚類結果，要么不屬于任何聚類結果。硬劃分方法雖然可以發現數據中隱含的聚類結果，但是不能很好地處理聚類邊界的問題。由于SCC[9]和COCS[10]聚類算法在不同的屬性空間中，采用硬劃分方法對用戶和頁面進行聚類，因此，這兩種算法的聚類質量都會受到聚類邊界的影響。因此，本文給出了一種模糊協同聚類FCOW(Fuzzy CO-clustering for Weblog)算法。該方法首先利用Hadamard積來發現Weblog數據中不同的用戶模式PA={pa1,…,paK}；然后依據獨立模式包含的頁面子集，將剩余用戶分配給不同的用戶模式，組成協同聚類結果C={CSk,CPk},k=1,…,K；最后計算協同聚類結果中模式與頁面之間的模糊關聯關系，產生關聯關系矩陣。在3個實際數據的實驗結果顯示，FCOW算法的精度和覆蓋率均優于其他比較算法。

2 符號約定及背景知識

本節我們首先給出了相關的符號約定。

給定n個頁面P={p1,…,pn}和m個用戶會話S={s1,…,sm}。由于用戶興趣可以用不同權重的頁面描述，因此，每個用戶會話si∈S被定義為si={ai1,…,ain},m個用戶會話向量構成了“會話-頁面”矩陣SP={aij}，其中aij,j=1,…,n表示頁面pj在si中的權重。表1給出了SP矩陣的例子。

表1 會話-頁面矩陣例子

本文的目的是從SP矩陣中發現其中具有共現特征的聚類結果，即C={CSk,CPk},k=1,…,K，其中CSk的會話記錄僅在CPk子集上相似。例如，表1所示的用戶訪問記錄中包含的協同聚類結果如表2所示。

表2 表1中包含的協同聚類結果

本文涉及的相關符號及其意義如表3所示。

表3 符號約定

3 模糊協同聚類算法FCOW

模糊協同聚類算法主要由模式提取、頁面分配及隸屬度值計算等步驟組成。本小節將對這些部分進行詳細的闡述。

3.1 模式抽取與隸屬度定義

本文考察的“會話-頁面”矩陣中元素aij∈{0,1}，表示用戶i是否對頁面j進行訪問操作，若訪問，則aij=1，否則aij=0。為了抽取SP矩陣中抽取出不同的模式，本文采用矩陣Hadamard積來完成。矩陣Hadamard積如定義1所示。

定義1(Hadamard積)給定兩個矩陣Am×n和Bm×n，它們的Hadamard積就是分素乘積(entrywise product)，定義為?(A°B)ij=(A)ij?(B)ij,i=1,…,n;j=1,…,m。

SP矩陣中每一行都代表一個用戶會話si={ai1,…,ain}，而用戶訪問頁面的興趣隱含在這些會話中，因此，本文采用行與行的Hadamard積來捕獲用戶的訪問興趣。我們通過計算每個會話si與其他m-1個會話的Hadamard積的方法來完成這個目標，但是m個會話的Hadamard積計算十分耗時，且需要大量的存儲空間。為了降低時間和空間消耗，本文采用貪心方法來實現該目標：首先，從m個會話中選擇非零分量最多的會話si；然后，計算該會話與其他m-1個會話之間的Hadamard積，產生SP的Hadamard積矩陣H；最后利用獨立模式(如定義2)捕獲用戶的訪問興趣。

定義 2(獨立模式)給定生SP的 Hadamard積矩陣H,SP的獨立模式PA={pa1,…,paK}，其中pak,k=1,…,K定義為：pak={pj|ifH(i,j)==1,i=1,…,m;j=1,…,p}，其中H(i,j)為H的第i行第j列元素。

表1所示的SP矩陣中隱含的獨立模式如表4所示。

從表4中可以看出每個模式的頁面子集與表2所示的相關協同聚類結果中的頁面子集相同，而且用戶聚類個數與模式個數相同。這個現象說明，Hadamard積發現的獨立模式與聚類結果之間存在著比較直觀的聯系。因此，本文以每個模式所對應的頁面子集為基準，按照定義3來發現與之對應的用戶聚類。

圖4 Hadamard積方法產生的獨立模式

定義 3(聚類定義)給定模式pak∈PA,k=1,…,K，本文定義pak包含的頁面為第k個頁面聚類CPk，那么與之相對應的用戶聚類CSk定義為

其中|pak|表示第k個頁面子集包含的頁面數。

本文通過計算每個會話和頁面與協同聚類結果C={CSk,CPk},k=1,…,K之間的隸屬度來刻畫它們之間的關聯程度，實現軟聚類的目的。

定義 4(用戶隸屬度)給定協同聚類結果C={CSk,CPk},k=1,…,K,m個用戶與CSk會話聚類之間的隸屬度由如下公式定義：

其中si∈SP是SP中第i個會話，sm(si,CPk)是會話si與頁面聚類CPk的相似度，通常用向量的余弦相似度來計算[6]。

定義 5(頁面隸屬度)給定協同聚類結果C={CSk,CPk},k=1,…,K,n個頁面與CSk會話聚類之間的隸屬度定義為

其中pj∈SP是其中第j列向量，即頁面j。

3.2 模糊協同聚類算法框架

模糊協同聚類算法 FCOW(Fuzzy CO-clustering for Weblog)由3部分組成：(1)利用貪心方法計算SP的Hadamard積矩陣，并由定義2發現其中隱含的獨立模式；(2)在獨立模式的基礎上，發現會話聚類和頁面聚類結果；(3)利用迭代更新方法計算每個會話與會話聚類之間的隸屬度和每個頁面與會話聚類之間的隸屬度。具體流程如表5所示。

表5 模糊協同聚類算法流程

步驟(1)首先計算SP的Hadamard積矩陣H，確定其中的獨立模式PA及其對應的頁面子集；步驟(2)依據定義3，確定與頁面子集相關的會話聚類，從而形成了協同聚類結果C={CSk,CPk},k=1,…,K；步驟(3)則是頁面隸屬度矩陣的初始值設定；步驟(4)-步驟(6)迭代地執行頁面隸屬度矩陣的更新操作，直到最近兩次更新值的差小于給定閾值ε，其中m'為模糊因子，通常情況下m'=2。參數minp為與獨立模式相關的最小頁面數。本文首先統計SP矩陣中每個會話中權重為1的頁面數，然后取m個會話的平均頁面數為minp的值設定。

3.3 時間復雜度分析

算法FCOW的步驟(1)需要考慮m對會話之間的Hadamard積，而每對會話的Hadamard積需要n次乘法運算，因此步驟(1)共需消耗O(m?n)時間。步驟(2)依據產生的獨立模式，進行會話分配，產生會話聚類結果。每個會話都需要與K個頁面子集進行比較分配，其總的時間消耗為O(m?K)。步驟(3)為每個頁面分配初始隸屬度，其最多時間消耗為O(n)。步驟(4)，步驟(5)共同完成會話隸屬度計算功能：首先，計算n個會話與K個會話聚類之間的相似度，需要耗時O(n?K)，然后根據定義(3)計算會話相似度需要O(m?K)時間。步驟(6)更新n個頁面與會話聚類之間的隸屬度消耗O(n)時間。假設步驟(4)-步驟(6)共迭代允許了λ次，那么FCOW算法的總的時間消耗為O(m?n)+O(m?K)+O(n)+λ?(O(m+n)?K+O(n))。

4 實驗及分析

本節在3組實際數據集上對比了算法FCOW,SCC[9],COCS[10],CCMD(Co-Clustering using Matrix Decomposition)[11],RB (Robust Biclustering)[12]及模糊聚類算法FWLC (Fuzzy Web Log Clustering)[13]的算法性能。FCOW及5種對比算法均由Matlab 7.0編程語言實現，并在Intel 2.0/ 4 GM/250 G兼容機、windows XP環境下執行。

4.1 評價標準及參數設置

由于我們需要利用協同聚類結果進行推薦，因此本文采用信息檢索領域的傳統評價標準精度和覆蓋率作為對比算法的評價標準。本文的推薦過程描述如下：對t時間窗口內的用戶si，首先，發現與新用戶si具有最大相似度的用戶sj；然后，從用戶隸屬度矩陣μu中推薦p≤K個相似聚類CS1,…,CSp；再根據頁面隸屬度矩陣μp所描述的頁面與聚類結果之間的關聯關系，為每個聚類CSk,k=1,…,p推薦pr個頁面，從而形成推薦集合R。本文通過實驗方法設置p=K/2,pr=10。

定義6給定t時間窗口內用戶si的訪問記錄集合T，及由聚類結果產生的推薦集合R，精度定義為：

定義7給定t時間窗口內用戶si的訪問記錄集合T，及由聚類結果產生的推薦集合R，那么覆蓋率定義為：

由定義6，定義7可以看出，精度標準度量了推薦子集R的推薦精度，而覆蓋率則衡量了推薦結果被用戶使用的頻度，因此，精度和覆蓋率的值越高，說明由本文提出的聚類算法的質量就越高，對個性化推薦的支撐作用越好。

4.2 實驗數據集

本文在5個實際數據集上對比6種比較算法。CTI.STD數據集是從Depaul CTI Web Sever (http：//www.cs.depaul.edu)網站收集的2002年4月份前2個星期訪問該站點的所有用戶訪問記錄集合。經過處理，CTI.STD數據集包含了13,745個用戶向量，每個用戶向量由683個屬性描述。其中一個用戶可以擁有多個會話，而每個屬性表示一個頁面。用戶向量中包含了非零和零兩類數值(零表示用戶沒有訪問該頁面，而非零則反映了用戶訪問該頁面的次數，本文把所有的非零數值用1代替)。CSD數據集是2003年10月到2004年3月期間訪問AUTH大學信息學院網站(http：//www.csd.auth.gr)的weblog數據。經過預處理后，CSD包含了373個用戶，而每個用戶由255個頁面描述。MUMA數據集則是訪問Hyperreal音樂網站(http：//hyperreal.org/)的Music Machines(http：//machines.hyperreal.org/)的用戶訪問數據。經過預處理之后，MUMA數據集共包含265個用戶，每個用戶則有127個頁面屬性描述。Amazon2011數據集是由UCI于2011年9月份發布的Amazon網站的訪問記錄。由于本文在用戶-頁面矩陣中研究模糊協同聚類，以發現其中隱含的興趣模式，因此，我們對該數據集進行預處理，最終保留15,596個用戶，每個用戶由729個頁面描述。而TechCmantiX數據集則是2010年7月到12月期間訪問www.techcmantix.com的用戶數據，經過預處理后，本文保留了12,599個用戶，每個用戶由698個頁面描述。

4.3 實驗結果及其分析

圖1給出了6種對比算法在5個不同實際數據集上的精度值對比。精度反映了個性化推薦的準確程度，其值越高，說明由算法給出的推薦越好。從圖1的6條變化曲線中，我們可以發現，算法FCOW的精度值變化曲線始終處在最高處。這個現象說明以FCOW算法結果為基礎的個性化推薦精度是6種對比算法中最好的，即使在包含了大規模高維數據集(15,596×729)Amazon2011上，其精度值也在0.8以上。這個現象說明，采用模糊策略的FCOW算法的聚類結果有效地解決了邊界問題，克服了SCC,COCS,CCMD和RB算法存在的固有缺陷。FWLC算法采用模糊概念解決硬劃分聚類算法無法處理邊界問題，但是由于該算法直接采用了經典模糊聚類算法FCM作為子方法，無法實現高維Weblog數據的協同聚類目的。因此，從圖1中可以看出，該算法的精度值曲線在5個數據集中始終處于最下面。同時，從圖1中還可以看出，算法FCOW在5個數據集上的精度值曲線基本保持不變。該現象說明，采用Hadamard積運算可以準確地發現數據集中隱含的獨立模式及其對應的頁面子集，而其他對比算法都不具備這樣的能力。

圖2是6種對比算法在5個實際數據集上的覆蓋率值對比。從定義7可以看出，覆蓋率體現了以聚類結果為基礎的個性化推薦被用戶使用的比例，其值越高，說明推薦結果被用戶接受的程度就越高。從圖中可以看出，6種算法在Amazon2011數據集上的覆蓋率值都小于在其他4個數據集上的覆蓋率值。造成這個現象的原因是由于描述該數據集的屬性個數比較多(729個頁面)，矩陣十分稀疏，從而影響了算法的性能。但是算法FCOW在該數據集上的覆蓋率值接近 0.91，遠遠高于其他對比算法在該數據集上的覆蓋率值。同時，從圖中還可以發現，FCOW算法在其他4個數據集上的覆蓋率值也遠遠高于對比算法的覆蓋率值。圖2的實驗結果再次表明，以FCOW聚類結果為基礎的個性化推薦結果的用戶接受程度好于其他5種算法。

圖1 6種算法在5個實際數據集上的精度值對比

圖3給出了6種對比算法在5個實際數據集上的運行時間對比情況。從圖中可以看出SCC,COCS,CCMD,RB及FWLC算法的時間消耗明顯高于FCOW算法的時間消耗，這是因為，SCC,COCS,CCMD和RB中算法都是以圖運算為基礎的算法，其時間復雜度為O(m2)。而FWLC算法是以FCM聚類算法為子方法，因此該算法的時間消耗也是O(m2)。由于在FCOW算法中，本文采用貪心方法計算Hadamard積，從而達到了降低算法運行時間的目的，同時，用戶隸屬度與頁面隸屬度的計算時間僅僅與m和n成線性關系，因此，算法FCOW的時間消耗遠遠低于其他5種對比算法。

圖2 6種算法在5個實際數據集上的覆蓋率值對比

圖3 6種算法在5個實際數據集上的時間消耗對比

5 結論

近年來，Weblog協同聚類成為Weblog信息挖掘的重要研究內容。現有的 Weblog聚類算法大多采用硬劃分方法將用戶和頁面唯一地分配給協同聚類結果。硬劃分方法的剛性要求使得聚類算法無法處理聚類結果邊界問題，從而影響了聚類質量。本文給出了一種面向 Weblog的模糊協同聚類算法，該方法首先用Hadamard積識別Weblog中獨立模式及其對應屬性子集；然后以屬性子集為基礎，分配用戶到對應的模式中，產生協同聚類結果；最后通過迭代計算用戶與頁面之間的模糊隸屬度來產生模糊關聯關系，并以此來做推薦。實驗結果表明，本文提出的方法具有獲得高質量協同聚類結果的能力。

[1]Zhang Y C,Yu J X,and Hou J.Web Communities：Analysis and Construction[M].Berlin Heidelberg,Springer,2006：1-45.

[2]Xu G D,Zhang Y C,and Li L.Web Mining and Social Networking：Techniques and Applications[M].Berlin Heidelberg,Springer,2010：127-156.

[3]Wang X and Zhai C.Learn from web search logs to organize search results[C].Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval,New York,NY,USA,ACM,2007：87-94.

[4]Kummamuru K,Lotlikar R,Roy S,et al..A hierarchical monothetic document clustering algorithm for summarization and browsing search results[C].Proceedings of the 13th International Conference on World Wide Web,New York,NY,USA,ACM,2004：658-665.

[5]Flesca S,Greco S,Tagarelli A,et al..Mining user preferences,page content and usage to personalize website navigation[J].World Wide Web Journal,2005,8(3)：317-345.

[6]Mobasher B,Dai H,Nakagawa M,et al..Discovery and evaluation of aggregate usage profiles for web personalization[J].Data Mining and Knowledge Discovery,2002,6(1)：61-82.

[7]Xu G D,Zhang,Y C,and Zhou X.A web recommendation technique based on probabilistic latent semantic analysis[C].Proceeding of 6th International Conference of Web Information System Engineering,New York City,USA,2005,LNCS 3806：15-28.

[8]Ferragina P and Gulli A.A personalized search engine based on web-snippet hierarchical clustering[C].Special Interest Tracks and Posters of the 14th International Conference on World Wide Web,New York,NY,USA,ACM,2005：801-810.

[9]Xu G D,Zong Y,Dolog P,et al..Co-clustering analysis of weblogs using bipartite spectral projection approach[C].In Proceeding of the 14th International Conference on Knowledge-based and Intelligent Information and Engineering Systems (KES2010),Part III,Cardiff,Wales,UK,2010：398-407.

[10]Zong Y,Xu G D,Dolog P,et al..Co-clustering for Weblogs in semantic space[C].Proceeding of the 11th Conference on Web Information Systems Engineering (WISE’2010),Hong Kong,2010：120-127.

[11]Ling Y,Ye C Y,and Wei G Y.Fast Co-clustering on large datasets using matrix decomposition[J].International Journal of Intelligent Information Technology Application,2010,3(2)：85-91.

[12]Inbarani H and Thangavel K.A Robust Biclustering Approach for Effective Web Personalization.Visual analytics and Interactive Technologies：Data,Text and Web Mining Applications[M].2011：186-201.

[13]Sudhamathy G and Venkateswaran C.Web log clustering approaches-a survey[J].International Journal on Computer Science and Engineering,2011,3(7)：2896-2902.