一種結構化Web文檔的聯合聚類算法

鄧冬梅，龍際珍，尹湘舟

(1. 湖南師范大學 計算機教學部，湖南 長沙，410081；2. 長沙理工大學 計算機與通信工程學院，湖南 長沙，410114；3. 中國科學院 計算技術研究所，北京，100190)

聚類是網上多媒體檢索和過濾常用的一種方法[1-2]，依據事物的某些屬性將其聚集成類，使同類間相似性盡量小，類與類之間相似性盡量大，是一種無監督的模式識別問題。很多聚類方法都是基于單一文本聚類[3-4]和單一圖片聚類[5]。然而，有時不僅需要對單一的文本信息或圖片信息進行聚類，還需要對一些屬性信息同時進行聚類，以便挖掘更多有用的信息[6]，這就需用到聯合聚類的思想。Dhillon[7]在2001年提出了基于二部圖劃分思想來解決聯合聚類的問題，這是目前聯合聚類方法最常用的一種方法。Giannakidou等[8]介紹了一種標簽和社會資源的聯合聚類方法，它是一種基于文本的圖像聯合聚類方法。現在網絡上的多媒體信息通常不是單一的文本信息或圖片信息，它所呈現的是一種結構化文檔的特性，融合了文本信息和圖片信息。許多研究者開始研究包含這2種信息在內的Web文檔檢索。Chen等[9]采用線性組合方式實現文本信息和圖像低層視覺信息的融合來檢索圖像。Blei等[10]使用 LDA(Latent dirichlet alfocation)模型捕獲圖像視覺特征和文本特征之間的聯合概率分布以及條件概率分布。Denoyer等[11]介紹了一種結構化文檔的分類方法，該方法結合結構化文檔的文本信息和圖片信息對結構化文檔進行有效分類。利用這種結構化文檔分類的思想，本文作者在考慮文本自身相似性的基礎上，引入圖片自身內容信息之間的相似性，再通過文本和圖片相似性融合實現結構化 Web文檔的聯合聚類，從而實現Web文檔的快速檢索與過濾。

1 問題描述

一個結構化文檔稱為一個資源，它不僅包含圖片信息，還包含用來描述圖片的標簽(描述圖片資源的特征詞)，分別用 R，T，AS，P分別表示資源、標簽、屬性、圖片集合[8]，并從圖片信息中選擇最具有特征的m個圖片作為圖片關鍵詞，用PF表示。這樣，問題就可以描述為資源—屬性—圖片關鍵詞聯合聚類的問題：給定資源集R、圖片集P、屬性集AS、圖片關鍵詞集合PF、整數k和相似函數，由聯合聚類得到一個集合C且Cx(1≤x≤k)包含有資源、屬性或圖片關鍵詞，最大(i=1, …, n; j=1, …, d; t=1, …, m)。其中：similarity(ri, aj)表示資源與屬性之間的相似性；similarity(pi, ft)表示圖片與圖片關鍵詞之間的相似性。

2 融合文本和圖片信息的聯合聚類算法

2.1 文本相似性融合

每個資源都可以用標簽來表示，而屬性集由d個出現頻率最高的標簽組成，這樣，資源與屬性之間的相似性就轉化為標簽之間的相似性。為了更好地表示2個標簽之間的相似性，可以同時考慮它們的社會相似性和語義相似性。語義相似性是利用Ohillon[7]所提出的方法，來計算詞的語義相似程度。tx和ty是標簽T1和T2的本體映射概念，則語義相似性定義為：

depth(tx)表示從 tx到 tx和 ty共同父節點的路徑長度；depth(P)表示從 tx和 ty的共同父節點到最終的祖節點的路徑長度。

社會相似性是通過關鍵詞同時出現在不同文檔中的概率來計算，則2個標簽tx和ty之間的社會相似性表示為：

為了考察每種相似性對聚類結果的影響，2個標簽之間的相似性可用這 2種相似性的權重之和來表示。利用文獻[10]中的方法，2個標簽之間總的相似性可表示為：

其中：w為語義相似性和社會相似性之間的權值。若w=1，則表示單獨的語義相似性；若 w=0，則僅僅表示社會相似性。當w取任何其他值時，2種相似性都起作用，但是，其作用要看w取值。這樣，資源的標簽信息與屬性之間的相似函數就可以表示為：

則 n個資源和 d個屬性之間的相似性就構成了 1個n×d的矩陣RA：

2.2 文本和圖片相似性融合

目前，計算圖片之間相似性的方法很多，如絕對值距離計算法、歐氏距離法、余弦距離和直方圖的相關系數法、卡方法、相交法和Bhattacharyya 距離法等等，還有基于SIFT特征提取的計算方法。

對于整個圖片資源集合，首先人工按圖片內容信息將圖片資源分類，然后，從每個類中挑選一些能代表這些類的圖片，稱為圖片關鍵詞。圖片之間的相似性simp(pi, fj)定義為圖片和關鍵詞之間的相似性：

其中：N表示pi與fj匹配的關鍵點個數；ipN 代表pi中關鍵點個數。

本文在進行圖片相似性計算時，利用了基于SIFT特征提取的計算方法、直方圖的相關系數法、卡方法、相交法和Bhattacharyya 距離法，然后，對幾種方法進行比較。對于n個圖片資源和m個圖片關鍵詞的數據集合，計算它們之間的相似性，這些相似性構成了n×m階矩陣PF，

文本相似性矩陣和圖片相似性矩陣的行都是用標簽信息表示的資源信息，因此，可以進行矩陣的水平拼接融合。由式(5)和(7)，定義文本和圖片相似性融合矩陣：

式(8)中：⊕表示矩陣RA和PF水平拼接融合。文本和圖片相似性矩陣融合以后，融合矩陣中既包含了文本的相似性，也包含了圖片的相似性。

2.3 聯合聚類算法

輸入：n個資源集R，n個圖片資源集p，l個Tags集合T，整數k和w∈[0, 1]

輸出：1個有k個簇的集合C，且每個簇中都包含資源、圖片關鍵詞和屬性，并且使得簇內部的相關性最大，而簇之間的相關性最小。

第1步：Tunitags=UnitaryTags(T); /*標簽拼寫歸一化*/；

第 2步：PureTag=EliminateNoiseTags(Tunitags);

/*過濾標簽*/；

第 3步：Attribs=ExtractAttrib(PureTag); /*抽取頻率最高的標簽形成屬性集*/；

第4步：PurePict=E liminateNoisePict(p); /*過濾噪音圖片*/；

第5步：PictFeat=ExtractPictKey(PurePict); /*抽取圖片特征*/；

第 6步：PKEY=ExtractPictKey(PurePict); /*形成圖片關鍵詞*/；

第7步：SOS=CalculateSocialSimilarity(R, Attribs);/*計算文本相似性RA*/；

第 8步：SES=CalculateSemanticSimilarity(R,Attribs);

第9步：RresAttribSS=w*SES+(1-w)*SOS;

第10步：RA=RresAttribSimilarityScore(RresAttrib SS);

第 11步：PictPictKeySS=CalculateSimilarity(Pure Pict, PKEY, PictFeat); /*計算圖片相似性PF*/;

第12步：PF=SimilarityScore(PictPictKeySS);

第13步：RA_PF=MatrixFusion(RA, PF); /*將RA和PF水平拼接形成RA_PF*/;

第14步：Drow=CalculatePictDiagMatrix(RA_PF); /*形成矩陣NAR_PF*/;

第15步：Dcol=CalculatePictKeyDiagMatrix(RA_PF);

第16步：(Drow-1/2, Dcol-1/2)=CalculateMitrix(Drow,Dcol);

第17步：NAR_PF=CalculateNormalizedMatrix(Drow,Dcol); /*計算得到NAR_PF的左奇異向量Lrow和右奇異向量Rcol*/

第18步：(Lrow, Rcol)=GETLeftRightSingularVector(NRA_PF);

第19步：SV=CreatUltimatelyMatrix(Drow-1/2, Dcol-1/2,Lrow, Rcol); /*構成矩陣SV*/

第 20步：C=K-Means(SV, k); /*對 SV進行k-means聚類*/

為了獲得更高效的聚類效果，首先對實驗數據進行預處理，標簽拼寫歸一化(第 1步)和過濾掉缺少嚴格意義并且不能映射具體概念的標簽(第 2步)，抽取頻率最高的標簽形成屬性集(第 3步)。對圖片的預處理首先是過濾噪音圖片(第4步)，抽取圖片特征(第5步)，最后形成圖片關鍵詞(第6步)。預處理完成后進入相似性計算階段，通過計算文本相似性RA(第7～10步)和圖片相似性PF(第11～12步)，然后將RA和PF水平拼接形成 RA_PF(第 13步)。當得到融合后的矩陣RA_PF，就可以進入聯合聚類的處理過程，通過計算對角矩陣Drow和Dcol，形成矩陣NAR_PF(第14～17步)，然后計算得到NAR_PF的左奇異向量Lrow和右奇異向量Rcol(第18步)，這樣，Drow-1/2, Dcol-1/2, Lrow和Rcol就構成了矩陣SV(第19步)。最后，對SV進行k-means聚類(第20步)，可得到k類包含資源、屬性和圖片信息的簇。

3 實驗結果與討論

3.1 實驗數據集和實驗方法

本文實驗都是基于一個文本特征和圖像特征相融合的Web圖片檢索系統。該系統建立在一個擴展性良好的統一框架上，系統核心采用C/C++編碼，實現了文本和圖片的特征提取、融合、文檔的高效聚類以及統一的數據集和數據I/O模塊。實驗所使用的數據集是利用Flickr網站提供的API，從該網站下載，包括由 cityscape，seaside，mountain，roadside，landscape，sport和locations組成的7個場景近7 000幅(每個場景大約有1 000幅)結構化文檔的圖像。每個場景表示聯合聚類中的1個類，即1個簇。這些圖像分別包含圖片信息以及圖片所對應的文本信息。每個場景的圖片信息用1個文件夾保存，文件夾的命名就是這個場景的名字。每個場景中所有圖片的文本信息用1個大的txt文件保存，每張圖片的文本信息叫做1條記錄。記錄中有圖片的名字、URL、描述信息、tags信息。Flickr網站的一個特點就是tags信息是人為地標注上去的，比其他任何信息都能很好地表述圖片內容的語義信息，所以，文本的特征提取是從圖片的tags信息中得到。由文本和圖片特征提取模塊提取大量文本特征向量和圖片關鍵點，創建特征參數。然后，將文本特征和圖片特征融合在一起，進行聯合聚類，最后分析聚類結果。

3.2 實驗結果分析

在實驗過程中，采用精確率和召回率來評價聚類結果。精確率高和召回率低(把一些本應該在一個簇的聚類予以分開)表明聚類的結果就好，RCj和ACj分別表示屬于簇Cj的資源集合和屬性集合。簇Cj的精確率和召回率定義如下：

在很多聚類的評估方法中，通常也用 F-Measure值同時反映精確率和召回率。根據精確率和召回率的定義，1個簇Cj的F-Measure值可定義為：

F-Measure的值F(Cj)在區間[0, 1]之間波動，其值越高，表示聚類越好。

3.2.1 文本聯合聚類分析

首先從實驗數據集中初步提取所有圖片的文本信息，經過文本相似性計算后進行k-means方法聯合聚類。試驗時實驗數據取自7個場景，所以，簇數k取為7，w (社會相似性和語義相似性的權重)設置為0.2，0.5和0.8。由式(10)和(11)算出每個聚類所獲得的精確率和召回率，然后，按式(12)推導出每一簇的F-Measure值，如圖1所示。可以看出：當w=0.5時，與w=0.2和w=0.8相比，它在編號為2，4，5和6的4個簇中取得的值較高，在另外3個其值稍低。總體來說，它能產生較好的聚類效果。

圖1 文本聚類F-measure值Fig.1 F-measure value of text co-clustering

3.2.2 圖片聯合聚類分析

對實驗數據集中所有圖片單一進行k-means聚類時，用到的圖片相似性矩陣包括：

(1) 根據 SIFT特征提取法計算所得的相似性矩陣；

(2) 利用相關系數(CORREL)法計算圖片所得的相似性矩陣；

(3) 利用卡方(CHISQR)法計算圖片所得的相似性矩陣；

(4)利用交集法計算圖片所得的相似性矩陣；

(5) 利用Bhattacharyya距離計算圖片所得的相似性矩陣。

此時k取為7，算出每個簇的精確率和召回率以及 F-Measure值。圖 2所示為圖片聯合聚類的F-Measure值。從圖 2可以看出：單純地依靠圖片特征信息進行聚類的效果不是十分理想，其中，BHATTACHARYYA方法所得到的F-Measure值較高，但是，也沒有超過50%。其原因是現在所有的直接從圖片的特征信息計算圖片相似性的方法還不能很好地表達它們之間的相似性，計算機對圖片的理解程度還不能達到人對圖片的理解程度。

圖2 圖片聯合聚類F-measure值Fig.2 F-measure value of image co-clustering

3.2.3 文本和圖片融合聯合聚類分析

對文本和圖片融合后的數據進行k-means聯合聚類時，取聚類數k為7，w為0.5，文本聚類效果最好。用SIFT特征提取法、直方圖的相關系數法(CORREL)、直方圖卡方法(CHISQR)、直方圖交集法(INTERSECT)和Bhattacharyya距離法這5種方法計算圖片相似性矩陣，然后，分別與文本相似性矩陣融合進行實驗，所得每簇的精確率和召回率如表1和表2所示。從表1和表2可看到：采用BHATTACHARYYA方法得到的相似性矩陣和文本相似性矩陣融合的結果最好。

為了比較融合以后與單一文本、圖片的聚類效果，在圖3中文本的聚類效果w取0.5，圖片的聚類方法取 BHATTACHARYYA，融合的聚類方法取BHATTACHARYYA，與文本融合。從圖3可以看出：融合后效果比單純的圖片聯合聚類的效果要好很多，F-Measure值基本上是單純的圖片聯系聚類的2倍以上。與文本聚類進行比較，在第1，2，3和7簇都比文本的高，在第4～6簇時聚類稍差。由此可以推斷：融合后的聯合聚類結果比單獨進行文本和圖片聚類的效果好。

表1 文本和圖片融合聯合聚類精確率Table 1 Precision rate of text and image integration co-clustering

表2 文本和圖片融合聯合聚類召回率Table 2 Recall rate of text and image integration co-clustering

圖3 文本、圖片和文本圖片融合聚類F-measure值對比Fig.3 F-measure value’s comparison of three approaches

4 結論

(1) 在進行文本聯合聚類時，社會相似性與語義相似性的權重w對聚類結果有影響：當w為0.2時，社會相似性居主要地位；當w取0.8時，語義相似性居主要地位；而當w取0.5時，二者的權重相等，而此時的聚類效果最好。

(2) 在進行圖片聚類時，聚類效果很不理想。原因是現在一些計算圖片相似性的方法還不能很好地表達2張圖片之間的相似性。

(3) 文本和圖片融合聯合聚類效果最好。對于網絡所呈現的多媒體結構化信息，單靠基于文本或圖片的聚類方法不能滿足聚類的精確性和高效性。融合文本相似性和圖片相似性的聯合聚類方法能有效針對結構化Web文檔的特征，使得聚類效果更精確，從而為進一步有效進行多媒體檢索和過濾研究提供一種新的研究方法。

[1] ZHANG Yan-chun, XU Guan-dong. Using Web clustering Web communities mining and analysis[C]//Web Intelligence and Intelligent Agent Technology. Sydney, 2008: 78-85.

[2] Fakouri R, Zamani B, Fathy M. Region-based image clustering and retrieval using fuzzy similarity and relevance feedback[C]//2008 International Conference on Electrical Engineering. Lahore, 2008: 343-347.

[3] 劉遠超, 王曉龍, 劉秉全, 等. 信息檢索中的聚類技術[J]. 電子與信息學報, 2006, 28(4): 606-609.LIU Yuan-chao, WANG Xiao-long, LIU Bing-quan, et al. The clustering analysis technology for information retrieval[J].Journal of Electronics & Information Technology, 2006, 28(4):606-609.

[4] Dhillon I S, Modha D S. Concept decompositions for large sparse text data using clustering[J]. Machine Learning, 2001,42(1): 143-175.

[5] 劉康苗, 仇光, 陳純, 等. 基于視覺和語義融合特征的階段式圖像聚類[J]. 浙江大學學報: 工學版, 2008, 42(12):2043-2048.LIU Kang-miao, QIU Guang, CHEN Chun, et al. Structured image clustering based on fusion of visual and semantic features[J]. Journal of Zhejiang University: Engineering Science,2008, 42(12): 2043-2048.

[6] Djouak A, Maaref H. Two levels similarity modelling: A co-clustering approach for image classification[C]//2009 6th International Multi-Conference on System, Signals and Devices.Djerba, 2009: 803-807.

[7] Dhillon I S. Co-clustering documents and words using bipartite spectral graph partitioning[C]//Proc of the 7th ACM SIGKDD Int Conf on Knowledge Discovery and Data mining. New York,2001: 269-274.

[8] Giannakidou E, Koutsonikola V, Vakali A, et al. Co-clustering tags and social data sources[C]//The Ninth International Conference on Web-Age Information Management. Zhangjiajie,2008: 317-324.

[9] Chen Z, Wenyin L, Zhang F, et al. Web mining for Web image retrieval[J]. Journal of the American Society for Information Science and Technology, 2001, 52: 831-839.

[10] Blei D M, Jordan M I. Modeling annotated data[C]//Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Toronto,2003: 127-134.

[11] Denoyer, Jean-Noel Vittaut, Patrick Gallinari, et al. Structured multimedia document classification[C]//Proceedings of the 2003 ACM Symposium on Document Engineering. New York, 2003:153-160.

[12] Wu Z, Palmer M. Verb semantics and lexical selection[C]//Proc of the 32nd annual meeting of the association for computational linguistics. Annual Meeting of the ACL. New Mexico:Association for Computational Linguistics, 1994: 133-138.

[13] Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004,60(2): 91-110.

[14] Hartigan J A. Direct clustering of a data matrix[J]. Journal of the American Statistical Association, 1972, 67: 123-129.

[15] 白雪生, 徐光佑. 基于內容的圖像檢索及其相關技術的研究[J]. 機器人, 1997, 19(3): 231-240.BAI Xue-sheng, XU Guang-you. Images searching based on content and research on related technology[J]. Robot, 1997,19(3): 231-240.

[16] 袁承興. 基于內容的圖像檢索技術研究[D]. 西安: 西安理工大學計算機科學與工程學院, 2008: 40-63.YUAN Cheng-xing, Research of images searching technology based on content[D]. Xi’an: Xi’an Technological University.Institute of Computer Science and Engineering, 2008: 40-63.

[17] 黃鵬. 基于文本和視覺信息融合的 Web圖像檢索[D]. 杭州:浙江大學計算機科學與技術學院, 2008: 33-50.HUANG Peng. Web images searching based on texts and images’ integration[D]. Hangzhou: Zhejiang University. Institute of Computer Science and Technology, 2008: 33-50.