面向Weblog的模糊協(xié)同聚類(lèi)算法

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

①(中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 合肥 230036)

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

1 引言

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

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

2 符號(hào)約定及背景知識(shí)

本節(jié)我們首先給出了相關(guān)的符號(hào)約定。

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

表1 會(huì)話(huà)-頁(yè)面矩陣?yán)?/p>

本文的目的是從SP矩陣中發(fā)現(xiàn)其中具有共現(xiàn)特征的聚類(lèi)結(jié)果，即C={CSk,CPk},k=1,…,K，其中CSk的會(huì)話(huà)記錄僅在CPk子集上相似。例如，表1所示的用戶(hù)訪(fǎng)問(wèn)記錄中包含的協(xié)同聚類(lèi)結(jié)果如表2所示。

表2 表1中包含的協(xié)同聚類(lèi)結(jié)果

本文涉及的相關(guān)符號(hào)及其意義如表3所示。

表3 符號(hào)約定

3 模糊協(xié)同聚類(lèi)算法FCOW

模糊協(xié)同聚類(lèi)算法主要由模式提取、頁(yè)面分配及隸屬度值計(jì)算等步驟組成。本小節(jié)將對(duì)這些部分進(jìn)行詳細(xì)的闡述。

3.1 模式抽取與隸屬度定義

本文考察的“會(huì)話(huà)-頁(yè)面”矩陣中元素aij∈{0,1}，表示用戶(hù)i是否對(duì)頁(yè)面j進(jìn)行訪(fǎng)問(wèn)操作，若訪(fǎng)問(wèn)，則aij=1，否則aij=0。為了抽取SP矩陣中抽取出不同的模式，本文采用矩陣Hadamard積來(lái)完成。矩陣Hadamard積如定義1所示。

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

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

定義 2(獨(dú)立模式)給定生SP的 Hadamard積矩陣H,SP的獨(dú)立模式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矩陣中隱含的獨(dú)立模式如表4所示。

從表4中可以看出每個(gè)模式的頁(yè)面子集與表2所示的相關(guān)協(xié)同聚類(lèi)結(jié)果中的頁(yè)面子集相同，而且用戶(hù)聚類(lèi)個(gè)數(shù)與模式個(gè)數(shù)相同。這個(gè)現(xiàn)象說(shuō)明，Hadamard積發(fā)現(xiàn)的獨(dú)立模式與聚類(lèi)結(jié)果之間存在著比較直觀的聯(lián)系。因此，本文以每個(gè)模式所對(duì)應(yīng)的頁(yè)面子集為基準(zhǔn)，按照定義3來(lái)發(fā)現(xiàn)與之對(duì)應(yīng)的用戶(hù)聚類(lèi)。

圖4 Hadamard積方法產(chǎn)生的獨(dú)立模式

定義 3(聚類(lèi)定義)給定模式pak∈PA,k=1,…,K，本文定義pak包含的頁(yè)面為第k個(gè)頁(yè)面聚類(lèi)CPk，那么與之相對(duì)應(yīng)的用戶(hù)聚類(lèi)CSk定義為

其中|pak|表示第k個(gè)頁(yè)面子集包含的頁(yè)面數(shù)。

本文通過(guò)計(jì)算每個(gè)會(huì)話(huà)和頁(yè)面與協(xié)同聚類(lèi)結(jié)果C={CSk,CPk},k=1,…,K之間的隸屬度來(lái)刻畫(huà)它們之間的關(guān)聯(lián)程度，實(shí)現(xiàn)軟聚類(lèi)的目的。

定義 4(用戶(hù)隸屬度)給定協(xié)同聚類(lèi)結(jié)果C={CSk,CPk},k=1,…,K,m個(gè)用戶(hù)與CSk會(huì)話(huà)聚類(lèi)之間的隸屬度由如下公式定義：

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

定義 5(頁(yè)面隸屬度)給定協(xié)同聚類(lèi)結(jié)果C={CSk,CPk},k=1,…,K,n個(gè)頁(yè)面與CSk會(huì)話(huà)聚類(lèi)之間的隸屬度定義為

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

3.2 模糊協(xié)同聚類(lèi)算法框架

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

表5 模糊協(xié)同聚類(lèi)算法流程

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

3.3 時(shí)間復(fù)雜度分析

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

4 實(shí)驗(yàn)及分析

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

4.1 評(píng)價(jià)標(biāo)準(zhǔn)及參數(shù)設(shè)置

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

定義6給定t時(shí)間窗口內(nèi)用戶(hù)si的訪(fǎng)問(wèn)記錄集合T，及由聚類(lèi)結(jié)果產(chǎn)生的推薦集合R，精度定義為：

定義7給定t時(shí)間窗口內(nèi)用戶(hù)si的訪(fǎng)問(wèn)記錄集合T，及由聚類(lèi)結(jié)果產(chǎn)生的推薦集合R，那么覆蓋率定義為：

由定義6，定義7可以看出，精度標(biāo)準(zhǔn)度量了推薦子集R的推薦精度，而覆蓋率則衡量了推薦結(jié)果被用戶(hù)使用的頻度，因此，精度和覆蓋率的值越高，說(shuō)明由本文提出的聚類(lèi)算法的質(zhì)量就越高，對(duì)個(gè)性化推薦的支撐作用越好。

4.2 實(shí)驗(yàn)數(shù)據(jù)集

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

4.3 實(shí)驗(yàn)結(jié)果及其分析

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

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

圖1 6種算法在5個(gè)實(shí)際數(shù)據(jù)集上的精度值對(duì)比

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

圖2 6種算法在5個(gè)實(shí)際數(shù)據(jù)集上的覆蓋率值對(duì)比

圖3 6種算法在5個(gè)實(shí)際數(shù)據(jù)集上的時(shí)間消耗對(duì)比

5 結(jié)論

近年來(lái)，Weblog協(xié)同聚類(lèi)成為Weblog信息挖掘的重要研究?jī)?nèi)容?，F(xiàn)有的 Weblog聚類(lèi)算法大多采用硬劃分方法將用戶(hù)和頁(yè)面唯一地分配給協(xié)同聚類(lèi)結(jié)果。硬劃分方法的剛性要求使得聚類(lèi)算法無(wú)法處理聚類(lèi)結(jié)果邊界問(wèn)題，從而影響了聚類(lèi)質(zhì)量。本文給出了一種面向 Weblog的模糊協(xié)同聚類(lèi)算法，該方法首先用Hadamard積識(shí)別Weblog中獨(dú)立模式及其對(duì)應(yīng)屬性子集；然后以屬性子集為基礎(chǔ)，分配用戶(hù)到對(duì)應(yīng)的模式中，產(chǎn)生協(xié)同聚類(lèi)結(jié)果；最后通過(guò)迭代計(jì)算用戶(hù)與頁(yè)面之間的模糊隸屬度來(lái)產(chǎn)生模糊關(guān)聯(lián)關(guān)系，并以此來(lái)做推薦。實(shí)驗(yàn)結(jié)果表明，本文提出的方法具有獲得高質(zhì)量協(xié)同聚類(lèi)結(jié)果的能力。

[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.