郭紅建，陳一飛

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

將A臨時(shí)保存為B，即：B=A；

將SizeCt初始化為空向量；

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

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

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

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

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

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

步驟

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

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

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

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

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

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

2 實(shí)驗(yàn)結(jié)果與分析

2.1 實(shí)驗(yàn)結(jié)果評測方法

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

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

R=N/K

準(zhǔn)確率P可以定義為

P=N/M

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

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

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

2.2 實(shí)驗(yàn)過程與結(jié)果

為了下載真實(shí)社會標(biāo)注網(wǎng)頁作為語料進(jìn)行實(shí)驗(yàn)，本文下載了www.delicious.com網(wǎng)站2013年1月～2014年1月的683 529個(gè)網(wǎng)頁。

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

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

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

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

表2 自適應(yīng)網(wǎng)頁聚類算法進(jìn)行聚類實(shí)驗(yàn)

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

表3 15組網(wǎng)頁語料進(jìn)行聚類對比實(shí)驗(yàn)

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

3 結(jié)束語

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