基于Ｋ－ｃｅｎｔｅｒ和信息增益的Ｗｅｂ搜索結果聚類方法

 收稿日期：2008-01-22；

修回日期：2008-03-19

基金項目：國家“863”計劃資助項目（2004AA1Z2520）； 軍隊網絡互聯與信息安全策略研究資助項目（2006QB1069）



作者簡介：丁振國（1959-），男，陜西三原人，碩導，主要研究方向為計算機網絡與信息處理技術；孟星（1984-），女，碩士研究生(emeng_841@163.com).

（西安電子科技大學 計算機學院 西安 710071）

摘要：

基于K-center和信息增益的概念，將改進后的FPF（furthest-point-first）算法用于Web搜索結果聚類，提出了聚類標志方法，使得聚類呈現出的結果更易于用戶理解，給出了評價聚類質量的模型。將該算法與Lingo，K-means算法進行比較，其結果表明，本算法能夠較好地平衡聚類質量和速度，更加適用于Web檢索聚類。

關鍵詞：Web文檔； 聚類； 聚類標志； K-center； 信息增益

中圖分類號：TP183

文獻標志碼：A

文章編號：1001-3695(2008)10-3125-03

Web search result clustering based on K-center and information gain

DING Zhen-guo MENG Xing

(College of Computer Science Xidian University Xi’an 710071 China)

Abstract:

Based on K-center and information gain this paper represented a version of modified FPF algorithm and cluster labeling algorithm on Web search clustering made the result better understood. At last presented a simple and intuitionistic criterion NMI for estimating cluster quality. The proposed solution was evaluated in search results returned from actual Web search engine and compared with other methods like Lingo K-means. The result proves that the algorithm can balance better clustering time and quality and meets the requirements of Web searching clustering.

Key words：Web document; clustering; cluster labeling; K-center; information gain

0引言

隨著網絡和信息技術的發展，Web帶來了人們使用和發現信息的革命，為了幫助用戶快速準確地獲得所需要的信息，涌現出了許多著名的搜索引擎。搜索引擎(search engine)是目前 Web 信息檢索的主要工具，大約有 85%的用戶是通過搜索引擎尋找自己需要的 Web信息[1]。目前搜索引擎的狀況還不能令人十分滿意。對于用戶提交的檢索要求，現存的搜索引擎，如Google、Yahoo、 MSN和百度等通常返回給用戶一長串結果列表，用戶需要在大量的搜索結果中尋找自己需要的信息，這往往帶來很多不便。例如用戶想在百度檢索汽車引擎方面的信息，輸入關鍵字“引擎”后，在返回的網頁信息中，排在前列的內容基本都是關于“搜索引擎”方面的知識；而“汽車引擎”的內容可能出現在100位以后。在如今搜索引擎普遍采用相關度排序的情況下，用戶將不得不經歷一系列無關網頁后才會獲取到自己想要的內容。這種檢索方式顯然是存在缺陷的。

為了解決上述問題，自動有效組織Web搜索結果是一個巨大挑戰，對搜索結果進行聚類是一種幫助用戶導航瀏覽以及快速準確地查找所需信息的較好途徑。Web檢索聚類是一種無監督的方式，將搜索的結果自動地形成類別。綜合Zamir等人[2]描述的聚類算法的幾個重要指標，得出聚類的質量和速度是衡量聚類算法的兩大基本指標，但是現在的很多聚類算法不能很好地平衡兩者。經典聚類算法K-means，雖然在時間上占有優勢，但是要求事先指定聚類的類別數目，并且對文檔的限制很多；如果初始聚類中心選擇不好，會降低聚類的質量。而著名的基于概念的Lingo[3，4]聚類算法 它首先從返回結果中確定概念文檔，從頻繁出現的相聯系的特征詞形成一定的概念文檔作為類標記。 類標記描述性強、易理解，搜索結果聚類把似乎松散的文檔集按主題進行了重新組織類，給用戶增強了直觀感。由于在Lingo算法中，要對特征詞—文檔矩陣進行奇異值分解(singular value decomposition SVD)，這是一個比較耗時的過程。雖然Lingo算法的聚類質量較好，但是速度會隨著文檔數的增多而變得越來越慢。

為了既能有較高的聚類質量又能有較快的速度，本文基于K-center和信息增益概念，從FPF[5] (furthest-point-first)算法出發，改進了FPF算法并用于Web搜索結果聚類中的K個中心點計算，給出了度量文檔相似度的函數D，在文檔歸類時，提出了更新“centers”的方法。相比較K-means提高了聚類的質量，而相比較改進前的FPF算法，減少了冗余計算、提高了效率；同時，基于信息增益的概念提出的聚類標志方法，使得聚類呈現出的結果更易于用戶理解。最后，給出了聚類質量評估模型，驗證出了本文算法在聚類質量上大大優于K-means，逼近Lingo，而在速度上卻比Lingo算法快。

1相關工作

1.1K-center問題

給定由度量空間M中的點組成的集合S，度量距離的函數D以及所要產生類的數目K，將S劃分為無重疊的類別C1，C2，…，Ck ，計算出它們的“中心”(centers)μ1，…，μk∈M，使得對任意類別Cj，maxjmaxx∈Cj距離函數D(x，μj)最小。

1.2信息增益

1948年Shannon提出并發展了信息論[6]，研究以數學的方法來度量信息，提出了信息增益等基本概念，并得到了廣泛的應用。信息增益在文本分類中描述為文檔特征詞為整個類別所能提供的信息量。

定義1x為文檔集合S中一個隨機文檔；P(t)表示文檔x中存在特征詞t的概率；P(c)表示文檔x屬于類c的概率；P(t，c)表示x屬于類C且x中存在特征詞t的概率；信息增益[7]公式如下：

IG（t，c)=∑a∈{t，t}∑b∈{c，c}

P(a，b)log (P(a，b))/[P(a)P(b)](1)

2基于FPF和信息增益的Web搜索結果聚類 

2.1Web搜索結果聚類

搜索結果的聚類是從文檔聚類啟發得來的 ，但還是與文檔聚類有很大不同。一般文檔聚類側重的是聚類質量和文檔數量的可擴展性，要求處理整個文檔集；對搜索結果聚類除保證聚類質量外，重點要給出聚類的明確又可理解的類標記，同時它要求處理速度快，滿足用戶查詢需要，可以只處理與查詢緊密相關的前若干返回結果。本文中實現的Web搜索結果聚類過程如圖 1所示。

2.2Web搜索結果文摘預處理

Web搜索結果文摘的預處理對聚類是很必要的，而且它處理的好壞直接影響聚類結果的精度。按一定規則進行文摘預處理:a)英文抽取詞干，中文分詞;b)過濾掉停用詞;c)數字、HTML標簽和詞長小于等于2的詞忽略，搜索中的關鍵詞忽略（因為返回結果一般都會包含）;d)詞的文檔頻率小于閾值(小于兩篇描述文摘出現)的詞忽略，詞的出現頻率小于閾值(如小于10次)的詞忽略。

2.3FPF算法的改進

2.3.1傳統FPF[7，8]算法

利用FPF算法能夠解決K-center問題[9]，如果不特別說明，本文中的文檔相當于向量空間中的點。具體算法描述如下：

在給定向量空間中的n個點組成的集合S中，FPF算法用下面的方法構建了k個中心點的序列T1T2…Tk=T(對Ti={μ1，μ2，…，μi}S)。其中：T1初始化為S中的一個隨機點 給定兩個文檔(向量)s1={s11，…，sh1}和s2={s12，…，sh2}。其中衡量距離(文檔相似度)函數WJD(weighted Jaccard distance)定義為

D(s1，s2)=1 if｜s1∩s2｜=0

0if2p(s1，s2)≥｜s1｜+｜s2｜

(p(s1，s2))/(｜s1｜+｜s2｜-p(s1，s2)otherwise(2)

其中：p(s1，s2)=∑i∈s1∩s2[w(s1，i)+w(s2，i)]/2；w(s，i)表示特征詞i在文檔s中的權重。

算法1FPF算法

輸入：S為n篇文摘集，K為類的數目；

輸出：k個中心點序列T1T2…Tk=T。

a)給出映射μ，對所有點(文檔)pj∈S/Ti-1，利用μ(pj)=arg minμs D(pj，μs)，μs∈Ti-1計算找出與點pj距離最短的Ti-1中的點，μ(pj)被稱做leader of pj。

b)在所有的點pj∈S/Ti-1，利用公式μi=arg maxpj D(pj，μ(pj))，計算找出使得D(pj，μ(pj))最大的點pj，將其作為中心點μi新加入到Ti-1中，形成Ti。最終形成的中心集合T={μ1，μ2，…，μk}相當于確定了K個類別，因為中心點μi即隱含地可以確定了Ci 這個類。

c)計算μi到S/Ti中所有點的距離，確定μ(pj)是否需要更新，再進入下一層迭代。

2.3.2FPF算法的改進

改進了算法1的FPFM算法，相比較FPF算法有兩處改進：

a)在FPF中，對Ti的每個中心點μx∈Ti以及計算距離它最近的點的集合N(μx)={pj∈S/Ti｜μ(pj)=μx}。對集合N(μx)的元素按照與μx的距離降序排列，在一個新的中心點μy加入到Ti后，計算與其距離最近點的集合N(μy)。當滿足D(pj，μx)≤D(μy，μx)/2且pj∈N(μx)，計算停止。根據三角不等式原理，對所有點pj滿足該條件距離μx比μy更近，改進后的算法省去了對leader ofpj不可能為μy的那些點的計算，因此加快了確定leader of pj的時間。 

b)更新centers。當Tk形成后，需要進行點(文檔)的歸類，由于當新的點加入到類別Ci中時，可能會影響簇的shape，每次迭代之后，都需要重新計算中心點。方法如下：

在類Ci中，找出距μi最遠距離的點αi和距αi最遠距離的點bi，點mi取代了μi成為類的新中心。mi是取對所有的點x∈Ci使得函數｜D(ai，x)-D(bi，x)｜+｜D(ai，x)+D(bi，x)｜最小的那個點，當Ci有新的點p歸入時，若D(ai，p)或D(p，bi)大于D(ai，bi)，則mi更新。利用mi代替μi，重復更新mi，提高了聚類的質量。

2.4Web搜索結果聚類

基于K-center的Web搜索結果聚類，利用FPFM算法既滿足了聚類時間短，又確保了聚類質量的要求。具體聚類算法如下：

算法2FPFM clustering

輸入：S為N篇文摘集，K為類的數目，δ是文檔間相似的閾值；

輸出：S中的K個類。

a)for i ，i=1，2，…，kdo

b)利用改進的FPF算法計算得到k個centers，初步形成每個Ci的中心

c)end for

d)for每個dj∈S/(C1∪C2∪…∪Ck)，do

e)for每個類Ck ，k=1，2，…，K do

f)計算dj與類Ck的center，dk的相似度D(dj，dk)

g)ifD(dj，dk)>then

h) 將dj劃入類Ck

i) 根據FPFM，更新Ck中的center

j)end if

k)end for

l)end for

m)for對每個類Ck，k=1，2，…，K do

n)對每個類別選取IGm最高的前四個特征詞聚類標志

o)end for

p)處理沒有歸入的文檔到other類

2.5聚類標志

由于式(1)中IG(t，c)包含了正相關(P(t，c)log [P(t，c)/P(t)P(c)]+P(t，c)log [P(t，c)/P(t)P(c)])函數和負相關函數(P(t，c)log [P(t，c)/P(t)P(c)]+P(t，c)log [P(t，c)/P(t)P(c)])。其中，筆者利用它的正相關函數作為類中特征詞標志提取：

IGm(t，c)=P(t，c)log [P(t，c)/P(t)P(c)]+P(t，c)log [P(t，c)/P(t)P(c)] (3)

根據每個類別的特征詞的權重提取了候選詞后，分別計算它們的IGm，選取IGm最高的前四個特征詞作為該類別的聚類標志。

3實驗結果及評價

3.1聚類質量評價模型

為了探討Web搜索結果聚類質量，本文提出了評價聚類質量的模型，利用分類引擎將查詢出來的文檔在未知分類的情況下進行聚類，通過比較其聚類結果與其分類類別的相似程度來衡量聚類的質量。對已知的類別C={c1，c2，…，ck}以及在給定類別下查詢出的所有n個文檔集S，最理想的聚類算法是將這些文檔聚類后的類別C′={c′1，c′2，…，c′k}，對文檔sj∈S，當且僅當sj∈ci時，sj∈c′i。利用標準化共有信息（normalized mutual information）來衡量聚類質量：

NMI(C，C′)=2/log ｜C‖C′｜∑c∈C- ∑c′∈C′P(c，c′)×

log P(c，c′)/P(c)P(c′) (4)

其中：P(c)表示任意一個文檔sj屬于類c的概率；P(c，c′)表示任意一個文檔sj同時屬于類c和c′的概率。 利用2/log ｜C||C′|對公式進行標準化，NMI值越大，說明聚類質量越好。

3.2實驗結果

根據式(4)將本文提出的算法與著名的K-means和Lingo算法進行了聚類質量和時間的比較。實驗中采用了開放式分類目錄搜索系統ODP(open directory)，實驗在 Intel Pentium4 CPU 3.0 GHz 主頻1.3 GHz、DDR 內存1 GB的機器上運行，在Windows XP Professional+MyEclipse 平臺上使用Java語言開發完成。

首先評價算法的質量，本文用30個不同查詢詞在ODP[10]上進行搜索。按照統計，ODP對每次查詢平均返回25.6個類別，而將ODP查詢出的Web文檔作為聚類的輸入文檔。在沒有ODP分類信息的情況下，用FPFM、Lingo和K-means算法分別進行聚類，由于Lingo算法產生了20個類，設定FPFM中與K-means中的K為20。圖2所示為給出的幾種算法的NMI值比較。

對算法速度的測試，本文不僅用到了ODP，同時用到了

Yahoo搜索引擎。利用ODP進行了40次查詢，算法時間比較如圖3所示，由于ODP不能夠限制搜索數目，筆者再利用Yahoo進行搜索聚類，時間比較如圖4所示。

4結束語

本文基于K-center問題，將改進后的FPF算法用于Web檢索聚類，同時本文基于信息增益的概念提出了聚類標志方法，使得聚類呈現出的結果更易于用戶理解。為了與其他聚類算法進行比較，在聚類的質量評價方面提出了聚類質量評估模型，實驗得出該算法在聚類質量上大大優于K-means 算法，聚類結果逼近Lingo，而在時間上卻比Lingo算法占優。而如何優化準確處理類邊界，縮小其他類數量等值得進一步詳細實驗研究。

參考文獻：

［1］CNNIC.第19次中國互聯網發展狀況統計報告[R].2007.

[2]ZAMIR O，ETZIONIO.Web document clustering:a feasibility demonstration[C]//Proc of the 19th International ACM SIGIR Conference on Research and Development of Information Retrieval.1998:46-54.

[3]OSINSKI S. An algorithm for clustering of Web search result[D].Poland:Poznan University of Technology 2003.

[4]OSINSKI S WEISS D. Conceptual clustering using Lingo algorithm: evaluation on open directory project data[C]//Proc of the 5th Confe-rence on Intelligent Information Processing and Web Mining. 2004:369-377.

[5]GONZALEZ T F. Clustering to minimize the maximum inter cluster distance[J].Theoretical Computer Science，1985，38(2/3):293-306.

[6]COVER T M THOMAS J A. Elements of information theory[M]. New York: Wiley 1991.

[7]GERACI F. A scalable algorithm for high quality clustering of Web snippets[C]//Proc of the 21st ACM Symposium on Applied Computing. New York: ACM Press 2006:1058-1062.

[8]FEDER T GREENE D. Optimal algorithms for approximate clustering[C]//Proc of the 20th ACM Symposium on Theory of Computing. New York: ACM Press 1988:434-444.

[9]GONZALEZ T F. Clustering to minimize the maximum inter cluster distance[J]. Theoretical Computer Science，1985，38(2/3):293-306.

[10]ODP[EB/OL]. http://www.dmoz.org/.