郭紅建，陳一飛

(1.南京審計大學 管理科學與工程學院，江蘇 南京 211815；2. 南京審計大學 工學院，江蘇 南京 211815)

Web1.0到Web2.0的革新，使得互聯(lián)網(wǎng)的應用更加廣泛。用戶越來越多地參與互聯(lián)網(wǎng)信息建設，從被動的信息瀏覽者成為主動的參與者，用戶標注信息、評論、標簽等越來越流行。作為 Web2. 0 環(huán)境下用戶生成內(nèi)容的典型應用,標注系統(tǒng)允許用戶以自由的形式對Web 資源進行標注形成標簽，如www.delicious.comwww.flickr.com,www.youtube.com。通過標注人們可以對大量信息進行組織分類，并可以與其他用戶共享這些標簽。

聚類算法是文本數(shù)據(jù)挖掘的一個重要方法，它的應用非常廣泛。其中網(wǎng)頁聚類和文本聚類算法的研究成果已經(jīng)非常多，總結(jié)起來，主要有3類：(1)基于文本內(nèi)容的文本聚類算法。該方法將文本表示為文本模型, 如VSM(Vector Space Model)模型[2]、N-gram模型、基于短語的模型、基于概念的模型、文本的圖表示及概率模型[3]。文本特征抽取與權(quán)重計算的方法主要有Salton 等[1]提出的TF×IDF函數(shù)[2]、互信息(Mutual Information)、布爾函數(shù)、頻度函數(shù)、期望交叉熵(Expected Cross Entropy)、二次信息熵(QEMI)、信息增益(Information Gain) 等。然后采用標準聚類算法(例如k-means算法[3]等)對文本向量進行聚類。優(yōu)化方法只是基于內(nèi)容中的特征選項改進或者聚類算法的調(diào)優(yōu), 提高聚類質(zhì)量；(2)基于用戶標簽的聚類算法。該聚類算法采用標簽取代了文本特征詞語,也考慮了用戶和鏈接之間的關(guān)系等, 然后對網(wǎng)頁進行聚類分析。但這種算法經(jīng)常只考慮了用戶標簽和其鏈接關(guān)系, 忽略了用戶標簽和文本內(nèi)容之間的信息。何文靜等[4]以社會標簽和特征詞語抽取方法, 采用k-means 聚類算法對文本內(nèi)容進行聚類，提高了文本聚類的效果。楊鯤等[5]分析了社會標注系統(tǒng)中用戶、標簽和被標注資源間的關(guān)系, 由此提出了基于用戶標簽的Web 資源語義描述獲取算法。Li 等[6]針對互聯(lián)網(wǎng)上網(wǎng)頁標簽過少的問題, 提出了一個與用戶相關(guān)的標簽擴展的方法, 添加標簽到原文件, 設計了Folk-LDA 模型有效地阻止主題漂移并取得了較好的聚類效果。Lu 等[7]用Tripartite Clustering聚類算法對標注網(wǎng)頁中3種類型的節(jié)點(網(wǎng)頁、用戶和標簽)進行聚類, 實驗結(jié)果表明Tripartite Clustering 顯著優(yōu)于基于內(nèi)容的k-means 方法；(3)基于內(nèi)容和標簽的網(wǎng)頁聚類方法。該聚類算法選取標簽和特征詞語的并集對網(wǎng)頁進行聚類,只是將標簽作為文本內(nèi)容的補充而已。賀秋芳等[8]提出一種挖掘用戶標簽的增強型社區(qū)網(wǎng)頁聚類算法, 用多種距離度量挖掘網(wǎng)頁鏈接關(guān)系, 結(jié)合網(wǎng)頁的內(nèi)容信息相似度和鏈接關(guān)系進行聚類。Ramage等[9]采用生成的大規(guī)模標簽的社會書簽網(wǎng)站作為網(wǎng)頁文字和錨文字的補充數(shù)據(jù)信息來提高網(wǎng)頁聚類質(zhì)量。李鵬等[10]提出基于標簽的網(wǎng)頁關(guān)鍵詞抽取方法,通過目標網(wǎng)頁中的每個標簽引入相關(guān)文檔計算詞項圖的邊權(quán)重, 進而計算得到詞項的重要度, 最后綜合考慮不同Tag 下的詞項權(quán)重計算結(jié)果。顧曉雪等人[11]探索社會標簽與文本內(nèi)容的結(jié)合對文本聚類的影響。使用TF×IDF、TextRank、TextRank×IDF共3種特征抽取方法, 線性函數(shù)和Sigmod函數(shù)進行相似度加權(quán), AP算法進行聚類。盧露等人[12]針對Web用戶聚類時社會標注系統(tǒng)中用戶訪問資源數(shù)據(jù)稀疏從而導致傳統(tǒng)聚類算法效率不高的問題，提出了一種3向迭代聚類算法,對用戶、標簽和資源分別聚類,利用三者之間的關(guān)聯(lián)關(guān)系不斷相互交叉迭代調(diào)整,直到各聚類簇達到穩(wěn)定為止。

1 社會標注系統(tǒng)自適應網(wǎng)頁聚類算法

社會標注系統(tǒng)網(wǎng)頁之間的鏈接類型有多種。如圖1所示，u,r和t分別代表用戶，網(wǎng)頁和標簽。每當用戶對網(wǎng)頁注明標簽時，也就建立了一個標簽，網(wǎng)頁和用戶的三元關(guān)系。

圖1 用戶，網(wǎng)頁和標簽的關(guān)系圖

假設D={di,i=1,2,…,n}是網(wǎng)頁文檔集, 能夠用一個無向圖G來表示。訓練數(shù)據(jù)構(gòu)成節(jié)點vi(i=1,…,Ntr)的鄰接表，用Vtr表示訓練數(shù)據(jù)節(jié)點集，Ntr表示訓練數(shù)據(jù)節(jié)點集的基數(shù)，用Vvalid和Vtest分別表示驗證集和測試集，基數(shù)分別為Vvalid和Ntest。

使得e=Φω+bNtr,=1,…,k-1。其中，是在特征空間的投影是核矩陣Ω的逆，Φ是Ntr×dh特征矩陣，γ∈+是常量。

Ωi,j=K(xi,xj)=φ(xi)Tφ(xj)可以通過xi和xj之間的余弦相似度計算而獲得。聚類模型可以通過下面的公式表示：

其中，φ:N→dh是到高維特征空間dh的映射。

如何利用驗證集的節(jié)點來評估聚類的數(shù)目，在文獻[13]提出了一個稱為平衡度適應BAF的評估標準。該標準的思想是屬于相同類的節(jié)點在特征空間有近乎零或者非常小的角度距離。

本文所采用的自適應選擇類別數(shù)目k的算法如下:

輸入E=[e1,e2,…,eNvalid]。

輸出類別數(shù)目k。

(2)設定td=[0.1,0.2,…,1]；

(3)對于每一個t∈td：

將A臨時保存為B，即：B=A；

將SizeCt初始化為空向量；

如果B是非空矩陣，采用公式CosDist(ei,ej)≤t定位驗證節(jié)點ei使得節(jié)點數(shù)達到最大值，將這些節(jié)點加入到向量SizeCt中，并將這些節(jié)點的行和列信息從矩陣B中移除；

(4)根據(jù)F-measure值達到最大值來設定閾值maxt；

(5)根據(jù)向量SizeCmaxt的元素個數(shù)來設定類別數(shù)k。

本文所采用的自適應網(wǎng)頁聚類算法如下:

輸入用戶，網(wǎng)頁和標簽的關(guān)系圖G=(V，E)。

輸出關(guān)系圖G聚成K個類。

步驟

(1)轉(zhuǎn)換和存儲關(guān)系圖G為矩陣形式；

(2)采用FURS算法[13-14]選擇訓練節(jié)點集Xtr；

(3)采用FURS算法移除子圖S后選擇有效地節(jié)點集；

(4)對?i,j,vi,vj∈Xtr進行余弦相似度計算得到核矩陣Ω；

(5)對核矩陣Ω進行特征分解得到α,b；

(7)通過自適應選擇類別數(shù)目k的算法計算出k，再根據(jù)余弦相似度計算將測試樣本劃分到合適的類中，直到滿足結(jié)束條件。

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

2.1 實驗結(jié)果評測方法

本文采用準確率、召回率、F-Measure值、Purity和NMI這五個指標評測聚類的結(jié)果質(zhì)量[8]。

假設聚類i和一個分類j,N為在文檔集i中屬于類別j的個數(shù)，M為聚類i中所有文檔的個數(shù)，K為分類j中所有文檔的數(shù)目，則召回率R可以定義為[8]

R=N/K

準確率P可以定義為

P=N/M

分類j的F-Measure可以定義為

本文也采用了Purity[15]和Normalized Mutual Information (NMI)[16]進行評測。Normalized Mutual Information (NMI)是根據(jù)即將要歸類的變量和已經(jīng)分類的變量之間的互信息值來計算的。計算NMI的公式如下

其中，變量X是將要歸類的隨機變量，變量Y是已經(jīng)分類的隨機變量，變量k是聚類的數(shù)目。

2.2 實驗過程與結(jié)果

為了下載真實社會標注網(wǎng)頁作為語料進行實驗，本文下載了www.delicious.com網(wǎng)站2013年1月～2014年1月的683 529個網(wǎng)頁。

為了使得實驗結(jié)果具有對比性，選擇k-means聚類算法進行對比實驗，k-means聚類算法的一個關(guān)鍵問題是預先選定的類別數(shù)目k，而本文可以自適應選擇類別數(shù)目k。利用隨機選擇的50 000個網(wǎng)頁對類別數(shù)目k的取值進行k-means聚類算法結(jié)果對比實驗，結(jié)果如表1所示。

表1 類別數(shù)目k不同時k-means聚類算法結(jié)果對比

從表1可以看出，最初選定k的取值對聚類效果影響很大，如果k過大，相關(guān)的網(wǎng)頁被迫分開，影響聚類質(zhì)量；如果k過小，不相關(guān)的網(wǎng)頁聚在一起。當k=16時，聚類效果較好。當然，如果網(wǎng)頁語料不同，適當調(diào)整類別數(shù)目k的取值。

然后將這50 000個網(wǎng)頁采用自適應網(wǎng)頁聚類算法進行聚類，得到的結(jié)果如表2所示。

表2 自適應網(wǎng)頁聚類算法進行聚類實驗

從表1和表2可以看出，自適應網(wǎng)頁聚類算法得出的k值為15并不是最好的結(jié)果，但是與k值為16得到的結(jié)果非常接近。如果網(wǎng)頁語料產(chǎn)生變化，數(shù)目k的取值就需要隨之調(diào)整，這會給k-means聚類算法造成障礙。本文嘗試進行了另一個對比實驗。隨機選擇15組網(wǎng)頁語料，每組語料均含有50 000個網(wǎng)頁，每組語料采用k-means聚類算法取最好記錄，采用本文自適應網(wǎng)頁聚類算法進行結(jié)果對比。

表3 15組網(wǎng)頁語料進行聚類對比實驗

從表3可以看出，15組網(wǎng)頁語料中采用本文算法有12組得到的k值和k-means聚類算法最佳k值相同，第5、8、13的k值不同。除了第6組和第13組在 五個評測指標P、R、F-Measure、Purity、NMI上本文算法偏低外，其他13組的結(jié)果均優(yōu)于k-means聚類算法，可見本文提出的自適應網(wǎng)頁聚類算法效果較好。

3 結(jié)束語

本文提出了一種社會標注系統(tǒng)自適應網(wǎng)頁聚類算法，可以自適應找出類別數(shù)目k并完成聚類。隨機選擇了15組網(wǎng)頁語料進行聚類對比實驗，實驗結(jié)果表明，本文提出的自適應網(wǎng)頁聚類算法效果較好。下一步研究將下載更多的真實社會標注網(wǎng)頁進行聚類實驗，比如新浪微博、騰訊微博等標注網(wǎng)頁；另外，將研究如何改進聚類算法的聚類速度，減少聚類迭代的次數(shù)。