蘇 沖,陳清才,王曉龍,孟憲軍

(哈爾濱工業(yè)大學(xué)深圳研究生院智能計(jì)算研究中心,廣東深圳518055)

1 引言

隨著網(wǎng)絡(luò)信息的爆炸式增長,搜索引擎日益成為信息時(shí)代不可或缺的工具?，F(xiàn)在大部分通用的搜索引擎將與用戶查詢相關(guān)的網(wǎng)頁按照其與用戶查詢的相關(guān)度進(jìn)行排序,返回給用戶一個(gè)列表形式的網(wǎng)頁查詢結(jié)果,用戶需要對每個(gè)網(wǎng)頁逐一判斷是否滿足自己的要求。研究[1]表明大多數(shù)用戶使用非常短的不確定的搜索字符串,并且85%的用戶只查看第一頁的結(jié)果,78%的用戶從來不更改他們的查詢詞,另外由于用戶的知識背景不同,對結(jié)果的期望也不同。因此為了滿足日益增長的網(wǎng)絡(luò)用戶對查詢質(zhì)量的要求,必須提高搜索引擎查詢結(jié)果對用戶的可用性。

聚類技術(shù)可以有效地解決這種由于查詢的模糊性而導(dǎo)致結(jié)果集合中主題分散的問題。文獻(xiàn)[2]提出了“聚類假設(shè)”,即緊密聯(lián)系的文檔傾向于與同一查詢相關(guān)。顯然,通過聚類技術(shù)把查詢相關(guān)的網(wǎng)頁按照不同的主題分組呈現(xiàn)給用戶,可以使用戶更快的定位自己需要的信息。然而,傳統(tǒng)的文本聚類算法大多基于向量空間模型和簡單的無序詞的集合(Bag-of-Words)進(jìn)行聚類,不能更好的利用網(wǎng)頁作為文本所擁有的自然語言的特點(diǎn),也很難生成高質(zhì)量的類別標(biāo)簽,因此準(zhǔn)確性不高,且無法生成好的聚類描述信息幫助用戶迅速把握各個(gè)聚類內(nèi)的主題內(nèi)容。

為解決這一問題,研究者提出了后綴樹聚類算法(Suffix Tree Clustering)[3]和Lingo[4]等結(jié)合自然語言特點(diǎn)的聚類算法,這些算法提高了聚類的精度,更重要的是生成了描述性較好的標(biāo)簽。不過基于算法復(fù)雜性考慮,這兩類算法都只是針對網(wǎng)頁摘要進(jìn)行處理,聚類效果難以獲得更大的提高。解決這種算法復(fù)雜性與聚類性能之間的矛盾的關(guān)鍵在于尋找一種更加準(zhǔn)確的網(wǎng)頁文本表示方法。頻繁項(xiàng)集是源自數(shù)據(jù)挖掘領(lǐng)域的概念,簡單地講就是在超過一定數(shù)目的網(wǎng)頁中出現(xiàn)的詞及詞的集合。頻繁項(xiàng)集的挖掘能很好的降低網(wǎng)頁維數(shù),并且在全文級別上挖掘出對聚類有貢獻(xiàn)的詞及詞的集合。最大頻繁項(xiàng)集是那些所有超集都不是頻繁項(xiàng)集的頻繁項(xiàng)集。采用最大頻繁項(xiàng)集能大大降低頻繁項(xiàng)集的規(guī)模,因此可以作為網(wǎng)頁集合的更緊湊表示。同時(shí),基于最大頻繁項(xiàng)集的聚類也有可能進(jìn)一步降低處理時(shí)間。正是基于這一概念,本文提出了一種基于網(wǎng)頁最大頻繁項(xiàng)集的查詢結(jié)果在線聚類算法。通過改進(jìn)最大頻繁項(xiàng)集的挖掘算法,使其可以用于搜索引擎查詢結(jié)果的在線聚類。新的算法利用網(wǎng)頁集合對頻繁項(xiàng)集的共享關(guān)系進(jìn)行聚類,同時(shí)對每個(gè)類別生成清晰明確的標(biāo)簽加以描述。實(shí)驗(yàn)結(jié)果表明：基于最大頻繁項(xiàng)集的聚類降低了基于全文的聚類時(shí)間,同時(shí)聚類精度提高了15%左右。

本文后續(xù)章節(jié)組織如下：第2節(jié)介紹了搜索引擎在線聚類的相關(guān)研究。第3節(jié)介紹了最大頻繁項(xiàng)集挖掘算法。第4節(jié)對基于最大頻繁項(xiàng)集的聚類算法進(jìn)行了詳細(xì)描述。第5節(jié)介紹了類別標(biāo)簽詞的生成算法。最后給出了實(shí)驗(yàn)及結(jié)果,并對研究工作做出總結(jié)和展望。

2 相關(guān)研究

傳統(tǒng)的文本聚類算法基于向量空間模型,將文檔當(dāng)作詞的集合,根據(jù)TFIDF計(jì)算每個(gè)詞的權(quán)重,以此計(jì)算文檔間的相似性。很多聚類算法都已經(jīng)被應(yīng)用到文本聚類中,比如 K-Means[5],BisetKMeans[5-6],遺傳算法[7],自組織映射算法(SOM)[8]等。但由于沒有利用文檔自身的自然語言的特點(diǎn),傳統(tǒng)的聚類算法準(zhǔn)確度不高,且難以生成高質(zhì)量的標(biāo)簽信息。

1997年Zamir和Etzioni[3]提出了后綴樹聚類算法(Su ffix Tree Clustering,STC),突破了傳統(tǒng)文本聚類算法應(yīng)用到文本聚類問題中的局限與不足。隨后研究者們提出了很多基于后綴樹算法的改進(jìn),比如,文獻(xiàn)[9]提出了ESTC(Ex tended STC)算法通過類別選擇來改進(jìn)后綴樹聚類效果,文獻(xiàn)[10]提出GAHC(Group-average Agglomerative Hierarchical Clustering)算法,通過改進(jìn)相似度度量來提高基于后綴樹的聚類效果。各種改進(jìn)算法完善后綴樹聚類算法,提高了聚類精度,但是基于后綴樹的聚類算法在聚類應(yīng)用(特別是中文聚類應(yīng)用中)中有一些問題,主要包括：1)后綴樹模型是針對英語提出來的,對中文不能有效地提取關(guān)鍵短語,容易生成沒有意義的短語,比如“限公司”,“士學(xué)位”等;2)后綴樹聚類算法目前的應(yīng)用主要是基于網(wǎng)頁摘要進(jìn)行聚類,由于不能對網(wǎng)頁進(jìn)行降維,后綴樹算法基于網(wǎng)頁正文的聚類時(shí)間復(fù)雜度較高,難以滿足在線聚類的要求,所以聚類精度的提高有瓶頸。

Lingo算法[4]著重于類別標(biāo)簽的提取,期望通過描有意義的標(biāo)簽來表達(dá)查詢返回結(jié)果中包含的核心概念,然后通過奇異值分解將網(wǎng)頁指派到不同標(biāo)簽對應(yīng)的集合中。Lingo算法優(yōu)勢在于標(biāo)簽的提取,同時(shí)也取得較高的聚類精度。但由于中文語言的特點(diǎn),Lingo算法標(biāo)簽提取的效果不夠理想。

將頻繁項(xiàng)集的思想用到網(wǎng)頁(文本)聚類中的動(dòng)機(jī)在于同一主題的網(wǎng)頁在描述主題時(shí)會(huì)用到一些共同的詞語,比如對于“金剛”這一查詢詞,描述變形金剛動(dòng)畫片中的網(wǎng)頁,“動(dòng)畫,變形,科幻,擎天柱”等詞會(huì)經(jīng)常被用到;描述金剛石方面的網(wǎng)頁,“金剛石,磨料,砂輪,材料”等詞經(jīng)常出現(xiàn);而描述吉利公司金剛汽車的網(wǎng)頁,“汽車,價(jià)格,市場,吉利”等頻繁出現(xiàn)。反過來講,包含相同頻繁項(xiàng)集的網(wǎng)頁傾向于屬于同一類別。在基于頻繁項(xiàng)集的文檔聚類方面,FTC算法(Frequent T rem-based Clustering)[11]挖掘文檔集合的所有頻繁項(xiàng)集,由這些頻繁項(xiàng)集生成候選簇,通過一種貪心策略,每次選擇與其他候選簇重疊程度最小的簇來覆蓋文檔集合,直到所有文檔被覆蓋。文獻(xiàn)[12]則利用挖掘出來的最大頻繁項(xiàng)設(shè)定聚類的初始質(zhì)心,然后進(jìn)行 K-Means聚類,提高了KM eans算法的聚類效果。FIHC(Frequent Item setbased Hierarchical Clustering)算法[13]先是生成每個(gè)頻繁項(xiàng)集對應(yīng)的簇,然后根據(jù)文檔與簇之間的緊密程度將文檔指派到最緊密的簇中,最后對簇進(jìn)行選擇合并生成層次化的簇結(jié)構(gòu),同時(shí)依據(jù)頻繁項(xiàng)生成簇的標(biāo)簽。

雖然與文檔聚類有很大的相似性,但搜索引擎查詢結(jié)果聚類并不等同于文檔聚類,事實(shí)上,查詢結(jié)果聚類是一種實(shí)時(shí),動(dòng)態(tài)的聚類,并且要求產(chǎn)生具有導(dǎo)航作用的標(biāo)簽。之前頻繁項(xiàng)集方面的聚類算法的時(shí)間復(fù)雜度較高不能滿足用戶在線需求,另外其產(chǎn)生的標(biāo)簽僅僅是頻繁項(xiàng)或者頻繁項(xiàng)的組合,可讀性不高,所以并不適用于查詢結(jié)果的在線聚類。

另外,查詢結(jié)果聚類不同于文檔聚類還在于其處理的數(shù)據(jù)集是與用戶查詢詞相關(guān)的網(wǎng)頁集合,查詢詞本身對數(shù)據(jù)集具有很大指導(dǎo)作用。文獻(xiàn)[14]提出利用查詢詞來指導(dǎo)聚類過程,從基類的生成到合并,拆分,到最后的簇的選擇,取得了很好的聚類效果。本文借鑒了這種思想,在我們的聚類算法中利用了查詢詞本身對聚類的指導(dǎo)作用。

目前大部分搜索引擎查詢結(jié)果聚類算法的研究是基于網(wǎng)頁摘要的,Zamir[15]研究表明基于全文的聚類要比基于摘要的聚類更準(zhǔn)確,但處理時(shí)間較長。經(jīng)過對頻繁項(xiàng)集挖掘算法的研究,我們發(fā)現(xiàn)在頻繁項(xiàng)集的挖掘中,只挖掘最大頻繁項(xiàng)集可以顯著降低挖掘時(shí)間;另一方面,長度越長的頻繁項(xiàng)集表達(dá)的意義越具體,對聚類的價(jià)值越大。因此通過挖掘全文最大頻繁項(xiàng)集進(jìn)行聚類是一種有效利用全文內(nèi)容聚類的途徑。

3 最大頻繁項(xiàng)集的挖掘

3.1 頻繁項(xiàng)集的基本概念

為了采用最大頻繁項(xiàng)集來作為基于全文的網(wǎng)頁在線聚類算法的基本特征,本節(jié)首先簡要給出頻繁項(xiàng)集的基本概念,有關(guān)頻繁項(xiàng)集的更詳細(xì)介紹請參見文獻(xiàn)[16]。

定義1 設(shè) I={I1,I2,…,In}是n個(gè)不同項(xiàng)的集合。如果對一個(gè)集合X,有X?I且k=|X|,則X稱為k項(xiàng)集,或者簡單的稱為項(xiàng)集,X的長度為包含項(xiàng)的數(shù)目,即k。

定義2 記D={T1,T2,…,Tm}是m個(gè)不同事務(wù)的集合,其中Ti?I。對于給定事務(wù)集合D,定義X的支持度為D中出現(xiàn)X的事務(wù)的數(shù)目,記為Sup(X)。用戶可以自己定義一最小支持度計(jì)數(shù)m in_supp,可以是絕對計(jì)數(shù),也可以是相對計(jì)數(shù)。

定義3 給定事務(wù)集D和最小支持度計(jì)數(shù)m in_supp,對于項(xiàng)集X ?I,若Sup(X)>min_supp,則稱X為D中的頻繁項(xiàng)集,包含此頻繁項(xiàng)集的事務(wù)集合稱為頻繁項(xiàng)集覆蓋的事務(wù)集合。

定義4 給定事務(wù)集D和最小支持度計(jì)數(shù)m in_supp,對于項(xiàng)集X ?I,若Sup(X)>min_supp,且對?(Y?I∧X?Y),均有 Sup(Y)

在本文中,事務(wù)集即查詢返回結(jié)果的網(wǎng)頁集合,其中的每一篇網(wǎng)頁即一個(gè)事務(wù)。項(xiàng)集就是網(wǎng)頁中包含詞語的集合,網(wǎng)頁中的詞即事務(wù)中的項(xiàng)。

最大頻繁項(xiàng)集是本文聚類算法的基礎(chǔ),下面將介紹挖掘最大頻繁項(xiàng)集采用的方法。

3.2 最大頻繁項(xiàng)集挖掘算法

頻繁項(xiàng)集的挖掘常用的算法是FP-Grow th算法[17]。算法首先構(gòu)造一種稱為FP-Tree(Frequent Pattern Tree)的線索樹形結(jié)構(gòu)存儲(chǔ)集合中的事務(wù)。FP-Tree的構(gòu)造首先要統(tǒng)計(jì)所有項(xiàng)的支持度,將支持度超過最小支持度計(jì)數(shù)的項(xiàng)按其支持度的降序排列在FP-T ree的Header table中;然后算法每次讀進(jìn)一個(gè)事務(wù),將其映射到FP-T ree中的路徑中。圖1中給出了一個(gè)FP-Tree的例子(最小支持度為2),其中(a)為事務(wù)集合,(b)為構(gòu)造成的FP-Tree。圖中實(shí)線表示事務(wù)映射到樹中的路徑,虛線從Header Table開始指向項(xiàng)在樹中出現(xiàn)的位置,節(jié)點(diǎn)中的計(jì)數(shù)表示從root節(jié)點(diǎn)開始到當(dāng)前節(jié)點(diǎn)結(jié)束的路徑對應(yīng)項(xiàng)集的支持度,比如節(jié)點(diǎn)“品牌：2”表示{汽車,吉利,品牌}這一項(xiàng)集的支持度為2。

構(gòu)造完 FP-Tree之后,FP-Grow th算法從Header table中最后一個(gè)項(xiàng)開始對每一個(gè)項(xiàng),計(jì)算它的條件狀態(tài)基(Conditionalpattern base),再由條件狀態(tài)基構(gòu)造新的FP-Tree,遞歸地挖掘頻繁項(xiàng)集,直到樹中只包含一條路徑,判斷當(dāng)前項(xiàng)集的支持度是否大于最小支持度。圖2就是圖1樹中項(xiàng)“電影”的條件狀態(tài)基以及生成的新的FP-Tree,下一步再計(jì)算“變形,電影”的條件狀態(tài)基等等。詳細(xì)挖掘過程請參考文獻(xiàn)[17]。

圖1 一個(gè)FP-Tree的例子(m in_supp=2)

圖2 項(xiàng)“變形”的條件狀態(tài)基及對應(yīng)的FP-Tree

最大頻繁項(xiàng)集的挖掘,要對挖掘出來的頻繁項(xiàng)集進(jìn)行最大頻繁項(xiàng)集的判斷。比如現(xiàn)在已挖掘出最大頻繁項(xiàng)集{電影,變形,戰(zhàn)爭},而頻繁項(xiàng)集{電影,變形}是{電影,變形,戰(zhàn)爭}的子集,則不是最大頻繁項(xiàng)集。這種子集判斷的計(jì)算復(fù)雜度較高。為解決該問題,我們借鑒了Gosta等人提出的FPMax算法的基本思想[18]。FPMax算法的核心在于提出了一種M FI-Tree(Maximal Frequent Item-Tree)的數(shù)據(jù)結(jié)構(gòu),用來記錄以挖掘出的最大頻繁項(xiàng)集,降低了子集判斷的時(shí)間。

3.3 面向查詢結(jié)果聚類應(yīng)用的改進(jìn)

上述最大頻繁項(xiàng)集的挖掘算法應(yīng)用到查詢結(jié)果聚類中的不足在于,對于某一給定的最小支持度計(jì)數(shù)(絕對計(jì)數(shù)10或者相對計(jì)數(shù)5%),不同的查詢詞的挖掘時(shí)間有較大差異。降低支持度計(jì)數(shù)會(huì)造成部分查詢詞的頻繁項(xiàng)集規(guī)模較小,提高支持度計(jì)數(shù)則造成部分查詢詞挖掘時(shí)間過長不能滿足用戶在線查詢的需要。本文通過取支持度最高的前N個(gè)詞,然后將第N個(gè)詞的支持度設(shè)為最小支持度計(jì)數(shù),使得不同查詢詞挖掘時(shí)間的差異顯著降低,更好地適用于查詢結(jié)果聚類。另一方面,不同于經(jīng)典聚類應(yīng)用中的標(biāo)準(zhǔn)數(shù)據(jù),網(wǎng)頁集合中包含的詞是語言學(xué)的基本單位,不同詞性的詞在表征文本的時(shí)候其貢獻(xiàn)不同[19]。本算法中為了提高聚類速度,我們只選擇名詞,動(dòng)詞,形容詞等實(shí)詞,而將連詞,代詞,助詞等去掉。我們進(jìn)行實(shí)驗(yàn)發(fā)現(xiàn),進(jìn)行詞性選擇后網(wǎng)頁平均長度降到之前的50%左右,聚類精度保持在95%左右。

4 基于最大頻繁項(xiàng)集的查詢結(jié)果聚類算法

在挖掘出頻繁項(xiàng)集之后,聚類途徑有兩種選擇：第一,用頻繁項(xiàng)集替代詞構(gòu)造網(wǎng)頁的特征向量,使用傳統(tǒng)的基于向量空間模型的聚類算法;第二,通過頻繁項(xiàng)集覆蓋網(wǎng)頁集合的關(guān)系進(jìn)行聚類。前者的時(shí)間復(fù)雜度已被證明不能滿足在線聚類的需要,同時(shí)受限于傳統(tǒng)聚類算法的缺陷,聚類效果不理想。本文采用第二種途徑。

算法[13]也采用了第二種聚類途徑,但它基于所有頻繁項(xiàng)集生成簇,然后依據(jù)統(tǒng)計(jì)信息對生成的簇進(jìn)行評價(jià),選擇出來最后的簇集合。一方面,由于頻繁項(xiàng)集的規(guī)模較大,相比于最大頻繁項(xiàng)集需要更多的挖掘時(shí)間。另一方面,相比于頻繁項(xiàng)集,最大頻繁項(xiàng)集是緊湊的表示,且長度較大,對聚類更有意義。例如,查詢詞“金剛”的一個(gè)最大頻繁項(xiàng)集{變形,電影,戰(zhàn)爭,汽車,擎天柱},表述了《變形金剛》電影這個(gè)方面的主題,其覆蓋的網(wǎng)頁集合相關(guān)性較大。顯然,這個(gè)最大頻繁項(xiàng)集的所有非空子集都是頻繁項(xiàng)集(共31個(gè)),比如{戰(zhàn)爭,汽車},其覆蓋的網(wǎng)頁集合的主題過于寬泛,可能包含多個(gè)類別的網(wǎng)頁。

本文的聚類算法正是基于上面的想法,利用網(wǎng)頁共享最大頻繁項(xiàng)集的關(guān)系進(jìn)行聚類。

為后文描述方便,我們定義如下：記D={T1,T2,…,Tm}為所有事務(wù)的集合,在本文中即查詢網(wǎng)頁的集合。記I={I1,I2,…,In}為所有項(xiàng)的集合,即網(wǎng)頁集合中包含詞的集合。記Sm={M 1,M 2,…,Mn}為挖掘得到的所有最大頻繁項(xiàng)集的集合,一個(gè)最大頻繁項(xiàng)集Mi覆蓋的網(wǎng)頁集合(即包含這個(gè)頻繁項(xiàng)集的網(wǎng)頁集合)記做Pi,Pi?D。聚類的過程就是把網(wǎng)頁集合分成若干個(gè)簇,記C={C1,C2,…,Cl}為簇的集合,一個(gè)簇Ci包含的網(wǎng)頁集合記做CPi,CPi?D,包含的最大頻繁項(xiàng)集的集合記做CMi,CMi?Sm,包含的頻繁項(xiàng)的集合CIi,CIi?I(注：簇包含頻繁項(xiàng)的集合不是頻繁項(xiàng)集,是簇中所有最大頻繁項(xiàng)集包含頻繁項(xiàng)的并集,本身不是頻繁項(xiàng)集)。記Dc={T1,T2,…,Tk}為D中已被簇覆蓋的網(wǎng)頁集合。

下面介紹聚類算法的核心步驟：Step 1 簇的生成

頻繁項(xiàng)集的長度越長,其包含的詞越多,越能表達(dá)一個(gè)具體的話題,因此我們優(yōu)先選擇長的頻繁項(xiàng)集生成簇。

將Sm中的頻繁項(xiàng)集按其長度排序,依次選擇最長的頻繁項(xiàng)集M i生成簇Ci,Ci包含的網(wǎng)頁集合CPi即Mi覆蓋的網(wǎng)頁集合Pi,記錄已被簇覆蓋的網(wǎng)頁集合D c=Dc∪Pi。為了提高簇生成的速度,減少后續(xù)合并過程中的傳遞效應(yīng),要對Sm中的頻繁項(xiàng)集做一步過濾。如果一個(gè)頻繁項(xiàng)集Mk覆蓋的網(wǎng)頁集合P k?Dc,說明Pk中所有網(wǎng)頁已被簇覆蓋過,不生成Mk對應(yīng)的簇Ck。

Step 2 簇的合并

初始生成的簇?cái)?shù)量過多,且有很多重疊,需要進(jìn)行合并生成最后的簇。簇的合并即把相似度較高的簇合并為一個(gè),通常簇的相似度通過包含網(wǎng)頁集合的相似度來判斷?；陬l繁項(xiàng)集的聚類算法中簇包含的頻繁項(xiàng)是簇的重要特征,我們可以結(jié)合包含頻繁項(xiàng)的相似度進(jìn)行簇的相似度計(jì)算,提高精確度。本文提出公式(1)進(jìn)行簇相似度的計(jì)算：

簇Ci與Cj的相似度記做Sim(Ci,Cj),包含網(wǎng)頁的相似度記為SimPij,包含頻繁項(xiàng)的相似度記為Sim Iij。

Sim(Ci,Cj)越大,簇Ci與Cj相似度越高,越傾向于合并。

這種依據(jù)集合的關(guān)系運(yùn)算計(jì)算簇能夠?qū)Χ鄶?shù)簇正確合并,但仍有不足：第一,參數(shù)敏感,闕值的設(shè)定對不同的數(shù)據(jù)集有很大偏差;第二,傳遞效應(yīng),比如A與B相似,B與C相似,會(huì)把A,B,C三者合并,然而A和C可能不相似 。針對這一問題,算法深入結(jié)合簇中包含頻繁項(xiàng)的特征就行判斷。利用簇中頻繁項(xiàng)在另一簇中出現(xiàn)的頻率指導(dǎo)簇合并的判斷。

共現(xiàn)率是指簇Ci中的頻繁項(xiàng)在簇包含的網(wǎng)頁中的平均出現(xiàn)次數(shù)。通過對方簇中網(wǎng)頁對自己簇中的頻繁項(xiàng)的“認(rèn)可度”指導(dǎo)簇的合并。本文引入公式(2),定義簇Ci在簇Cj中的共現(xiàn)率cf ij(簇 Cj在簇Ci中的共現(xiàn)率同理)：

其中t f(I,P)為項(xiàng)I在網(wǎng)頁P(yáng)中出現(xiàn)的次數(shù)。

共現(xiàn)率高說明簇之間包含網(wǎng)頁內(nèi)容上相近。

結(jié)合共現(xiàn)率的概念,本文設(shè)計(jì)簇合并的判斷算法,在算法實(shí)現(xiàn)中,對于簇的相似度設(shè)定兩個(gè)闕值,強(qiáng)約束闕值Ts比如(比如1.1),弱約束闕值Tw(比如0.8),對共現(xiàn)率設(shè)定一個(gè)闕值Tc f(比如3)。算法如下：

·如果Sim(Ci,Cj)大于Ts,合并簇;

·如果Sim(Ci,Cj)小于Tw,不合并簇;

·如果Sim(Ci,Cj)在 Ts與Tw 之間,計(jì)算簇之間的共現(xiàn)率c fij,如果cfij大于Tc f,合并簇,否則不合并。

合并過程將滿足上面條件的簇進(jìn)行合并,生成最終簇的集合。對于可以合并的簇,將簇Cj對應(yīng)的CPj,CMj,CIj合并到簇Ci對應(yīng)的CPi,CMi,CIi中,然后將從簇Cj集合中刪除。

Step 3 簇的凈化

聚類可以分為硬聚類和軟聚類,硬聚類要求一個(gè)網(wǎng)頁只能屬于一個(gè)類別,軟聚類允許一個(gè)網(wǎng)頁屬于多個(gè)類別,相對于硬聚類能更好地反映現(xiàn)實(shí)情況。但由于簇合并過程的傳遞效應(yīng),簇中會(huì)包含一些不相關(guān)的網(wǎng)頁。如何識別簇中的網(wǎng)頁是無關(guān)網(wǎng)頁還是多類別網(wǎng)頁是關(guān)鍵問題。本文中無關(guān)網(wǎng)頁的識別是通過網(wǎng)頁相對簇的支持度判斷的。為此本文定義網(wǎng)頁P(yáng)相對簇Ci的支持度如下：

根據(jù)實(shí)驗(yàn)我們可以獲得一個(gè)經(jīng)驗(yàn)值,當(dāng)Supp(P,Ci)小于這一值時(shí),認(rèn)為是簇?zé)o關(guān)網(wǎng)頁,將其從簇中刪除。

基于頻繁項(xiàng)集的聚類,會(huì)有部分網(wǎng)頁因?yàn)槲窗魏晤l繁項(xiàng)集,而沒有被簇覆蓋,需要將這部分網(wǎng)頁分類到已有的簇中。

5 簇標(biāo)簽的生成

查詢返回網(wǎng)頁聚類的應(yīng)用中簇的標(biāo)簽詞是對簇內(nèi)容的標(biāo)示,指導(dǎo)用戶瀏覽結(jié)果和進(jìn)一步查詢,有著非常重要的意義。

基于頻繁項(xiàng)集的聚類算法生成的簇中,頻繁項(xiàng)是標(biāo)簽詞的候選。例如對于查詢詞“金剛”,生成的一個(gè)簇包含的頻繁項(xiàng)集{價(jià)格汽車 上市 吉利自主圖片轎車售價(jià)對比車型最低報(bào)價(jià)}。一方面具有較高的描述能力和可讀性的項(xiàng)(即詞)適合做簇的標(biāo)簽詞語,比如上面例子中“汽車”;另一方面,短語相對單個(gè)詞有更好的描述能力,為用戶查詢提供更好的提示,比如“吉利汽車”,“變形金剛”。

本文的標(biāo)簽生成算法就從這兩個(gè)方面挖掘標(biāo)簽詞或短語,

第一,選擇對簇內(nèi)容最有代表性的項(xiàng)?？紤]的因素有：

a.項(xiàng)的詞性。名詞比動(dòng)詞,形容詞更適合做標(biāo)簽,同時(shí)動(dòng)詞性名詞,形容詞性名詞也有較好的描述能力。根據(jù)項(xiàng)的詞性,選擇名詞,動(dòng)詞性名詞及形容詞性名詞做標(biāo)簽候選;

b.項(xiàng)在簇包含頻繁項(xiàng)集中的支持度。即有多少個(gè)頻繁項(xiàng)集包含這個(gè)項(xiàng)。項(xiàng)被越多的頻繁項(xiàng)集包含就越能表達(dá)簇的內(nèi)容;

c.項(xiàng)在簇中包含網(wǎng)頁集合的統(tǒng)計(jì)數(shù)據(jù),即項(xiàng)在網(wǎng)頁集合的出現(xiàn)的頻率(TF)及項(xiàng)的逆文檔頻率(IDF)。這是借鑒傳統(tǒng)文本表征模型統(tǒng)計(jì)詞權(quán)重時(shí)采用的方法。

綜上所述,本文引入公式(5)定義簇Ci中項(xiàng)Ij的標(biāo)簽得分：

其中 posScore(W j)為項(xiàng) W j詞性的得分,t fid f(Wj,Pk)為項(xiàng)Wj在網(wǎng)頁P(yáng)k中TFIDF值。

第二,通過詞語間的順序關(guān)系,挖掘短語性標(biāo)簽。網(wǎng)頁不僅是詞的組合,詞語間順序出現(xiàn)的關(guān)系也是表達(dá)網(wǎng)頁內(nèi)容的重要特征,比如說“金剛”這個(gè)詞進(jìn)行聚類后,其中一個(gè)簇是變形金剛動(dòng)畫片相關(guān)的網(wǎng)頁,“變形”是其中一個(gè)很重要的標(biāo)簽詞,直接用“變形”做標(biāo)簽比較生硬。通過挖掘標(biāo)簽詞與查詢詞緊鄰出現(xiàn)的關(guān)系,可以生成可讀性更好的標(biāo)簽,比如“變形金剛”。短語標(biāo)簽的挖掘是通過統(tǒng)計(jì)的方法獲得的,具體做法：如果兩個(gè)詞的順序組合在簇中半數(shù)以上的網(wǎng)頁摘要中出現(xiàn),則可做為短語標(biāo)簽。

綜上所述,本文算法標(biāo)簽詞生成算法步驟如下：

1)選擇詞性為名詞,動(dòng)詞性名詞,形容詞性名詞的項(xiàng)做標(biāo)簽候選;

2)根據(jù)公式(7)計(jì)算項(xiàng)對于簇的標(biāo)簽得分;

3)從標(biāo)簽候選中選擇得分最高的項(xiàng)開始,檢查是否可與查詢詞組成短語標(biāo)簽。如果可以,則以此短語標(biāo)簽做簇的標(biāo)簽;否則把項(xiàng)從標(biāo)簽候選中刪除,重復(fù)步驟3),如果標(biāo)簽候選為空,轉(zhuǎn)到步驟4);

4)如果所有項(xiàng)都不能與查詢詞組成短語,選擇得分最高的兩個(gè)項(xiàng)做類別標(biāo)簽。

這里采用的簇標(biāo)簽生成算法不僅有效地利用了全文挖掘的深層次內(nèi)容,還借鑒了后綴樹算法生成標(biāo)簽的思想,生成質(zhì)量更高的標(biāo)簽,對基于頻繁項(xiàng)集的文本聚類標(biāo)簽生成算法是一個(gè)重要改進(jìn)。

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

6.1 實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)所用機(jī)器配置為Intel(R)Pentium D CPU 3.00GH z,2G內(nèi)存,操作系統(tǒng)為 Linux Fedora Core 4。

實(shí)驗(yàn)所用數(shù)據(jù)是選擇8個(gè)有查詢歧義的查詢詞對應(yīng)的數(shù)據(jù)集。對每個(gè)查詢詞取得相應(yīng)的百度以及Google返回結(jié)果的前100條,取并集,然后對網(wǎng)頁進(jìn)行分詞和詞性標(biāo)注,建立索引后保留網(wǎng)頁的分詞結(jié)果以備后面算法需要。上述工作離線完成,為在線查詢聚類準(zhǔn)備數(shù)據(jù)。

我們對網(wǎng)頁集合進(jìn)行人工的類別標(biāo)注,每個(gè)查詢詞網(wǎng)頁集合標(biāo)注了若干類別。

由于K-M eans算法需要設(shè)定k值,我們分別設(shè)定4次K值(5,6,7,8)進(jìn)行實(shí)驗(yàn),對每個(gè)查詢?nèi)?次實(shí)驗(yàn)結(jié)果中F值最高的做為最終結(jié)果。STC算法,Lingo算法,MFIC算法自動(dòng)生成不定數(shù)目的類別,同時(shí)會(huì)有一些只包含2,3篇網(wǎng)頁的簇,而實(shí)際應(yīng)用中通常會(huì)只顯示包含網(wǎng)頁較多的簇,結(jié)合實(shí)際應(yīng)用我們把包含網(wǎng)頁數(shù)目小于5的類歸為其他類。實(shí)驗(yàn)中我們通過調(diào)整參數(shù)使得這三種算法的類別數(shù)目分布在5～10范圍內(nèi)。

6.2 聚類算法時(shí)間

本文實(shí)驗(yàn)比較了基于全文的M FIC算法和K-Means算法,同時(shí)比較了基于摘要的后綴樹聚類算法(STC)的聚類時(shí)間(圖3)。由于STC對網(wǎng)頁全文聚類時(shí)間太長(實(shí)驗(yàn)數(shù)據(jù)顯示在10秒以上)不能用做在線聚類,在此不做詳細(xì)展示。另外由于Lingo算法使用的是開源的Java實(shí)驗(yàn),其他算法是C++實(shí)現(xiàn),這里沒做比較。

從圖中看出M FIC聚類時(shí)間優(yōu)于K-Means聚類的時(shí)間。由于M FIC聚類是基于網(wǎng)頁全文,聚類時(shí)間長于基于摘要的STC在預(yù)料之中。實(shí)驗(yàn)結(jié)果表明MFIC聚類時(shí)間基本控制在2秒左右,可以滿足在線聚類需要。為了進(jìn)一步提高系統(tǒng)反應(yīng),在具體應(yīng)用中可以通過設(shè)置聚類結(jié)果緩存,減少用戶等待時(shí)間。

圖3 聚類算法時(shí)間對比

6.3 聚類評測標(biāo)準(zhǔn)

檢索結(jié)果聚類系統(tǒng)的評價(jià)不同于一般的文本聚類評價(jià),除了對文檔在類別中的分布進(jìn)行評價(jià)外,還需要對類別標(biāo)簽進(jìn)行評價(jià)。其中對文檔在類別中的分布進(jìn)行評價(jià),常用的兩個(gè)指標(biāo)為：純度[20]與F值[6]。

對于聚類后形成的任意類別r,聚類的純度定義為：

整個(gè)聚類結(jié)果的純度定義為：

其中n是預(yù)定義類別的個(gè)數(shù),k是聚類類別的個(gè)數(shù),nr為聚類類別r中的文檔個(gè)數(shù),是屬于預(yù)定義類別i且被分配到聚類類別r的文檔個(gè)數(shù)。

F值的定義則參照信息檢索的評測方法,將每個(gè)聚類結(jié)果看作是搜索的結(jié)果,從而對于最終的某一個(gè)聚類類別r和原來的預(yù)定類別i有：

其中ni是預(yù)定義類別i的文檔個(gè)數(shù),其他定義同前。則聚類r和類別i之間的FMeasure值計(jì)算如下：

聚類結(jié)果總的F值為：

對類別標(biāo)簽進(jìn)行評價(jià)常用的方法是P@N[20],P@N定義為前N個(gè)結(jié)果中的精度,即：

其中R是聚類算法返回的前N個(gè)標(biāo)簽詞集合,C是人工標(biāo)注的標(biāo)簽詞集合。

6.4 聚類評測結(jié)果

在純度的比較方面,M FIC算法純度明顯優(yōu)于其他算法(見圖4(a))。這跟MFIC算法的特點(diǎn)有關(guān)：第一,MFIC算法通過最大頻繁項(xiàng)集確定簇,最大頻繁項(xiàng)集包含較多的頻繁項(xiàng)(比如,金剛這個(gè)查詢詞對應(yīng)的一個(gè)最大頻繁項(xiàng)集{電影導(dǎo)演上映 全球票房}),對網(wǎng)頁集合具有較高的區(qū)分度,共同包含一較長頻繁項(xiàng)集的網(wǎng)頁基本都屬于一個(gè)類別;第二,通過共現(xiàn)率概念的引入,提高了簇合并過程的精度。這一特點(diǎn),使得M FIC算法能給用戶帶來更好的搜索體驗(yàn)。比如金剛這一查詢詞生成了四個(gè)類別“變形金剛”,“吉利金剛”,“電影 劇情”,“金剛石”等,其中少數(shù)“電影 劇情”方面的網(wǎng)頁錯(cuò)分到了“變形金剛”類中,其他類別包含的網(wǎng)頁幾乎全是類別相關(guān)的。

STC通過將共享同一字串的網(wǎng)頁歸為一個(gè)類別,也能生成純度較高的類別,不過可能會(huì)產(chǎn)生較多的類別,類別的合并可依據(jù)的內(nèi)容較少,聚類精度會(huì)受影響[9]。Lingo算法首先尋找重復(fù)出現(xiàn)的,描述性強(qiáng)的標(biāo)簽,依據(jù)這些標(biāo)簽生成簇,然后通過奇異值分解將網(wǎng)頁劃分到簇中[4]。Lingo算法的純度值優(yōu)于STC算法,但由于效果較依賴于第一步中尋找出的標(biāo)簽,如果標(biāo)簽本身區(qū)分度差,該標(biāo)簽生成的簇的純度就會(huì)受影響。K-M eans算法因?yàn)閷Τ跏紖?shù)和噪音較為敏感,有時(shí)會(huì)造成聚類結(jié)果失衡,即生成的簇的大小差異很大,所以其聚類的純度明顯差于其他算法[22]。

圖4 聚類算法純度和F值對比

在F-M easure的比較上MFIC算法明顯優(yōu)于其他算法(見圖4(b))。K-M eans算法受初始參數(shù)影響較大,且對噪音敏感。查詢結(jié)果的聚類難以準(zhǔn)確的設(shè)置初始參數(shù),同時(shí)噪音信息較多,影響了K-Means的聚類效果,使得K-Means算法不適合用來做查詢結(jié)果的聚類,實(shí)驗(yàn)數(shù)據(jù)也說明了這一點(diǎn)。

STC算法和 Lingo算法因?yàn)橹桓鶕?jù)搜索引擎查詢結(jié)果中的摘要進(jìn)行聚類,可靠性差,且受限于摘要的質(zhì)量,精確度不如MFIC算法。另外相對于Lingo算法,STC算法F值較差,原因在于僅僅根據(jù)摘要中的共享字符串來聚集查詢結(jié)果,會(huì)造成很多網(wǎng)頁未被任何挖掘出來的共享字符串覆蓋,使得這些網(wǎng)頁不能被正確的聚類;而Lingo算法,通過奇異值分解方法,即使網(wǎng)頁不包含相同詞,也可能被聚集到一起。

MFIC算法相對與STC算法與Lingo算法的優(yōu)勢還在于算法的可改進(jìn)性,因?yàn)槠湟罁?jù)的是網(wǎng)頁全文內(nèi)容,在頻繁項(xiàng)集的選擇和類別的合并,凈化等過程可以采用嘗試很多算法來優(yōu)化整體效果。

6.5 聚類標(biāo)簽效果

聚類標(biāo)簽的評測我們采用的P@N方法。表1是對查詢詞標(biāo)注的類別：

表1 人工標(biāo)注的類別標(biāo)簽詞

我們分別對所選聚類算法的每次查詢計(jì)算P@3,P@5,P@8值,取8個(gè)查詢詞的平均值做為評價(jià)標(biāo)簽質(zhì)量的依據(jù),最終結(jié)果見下表。

表2 聚類算法類別標(biāo)簽P@10值比較

由于M FIC算法基于全文且考慮了多種因素,挖掘出的標(biāo)簽更能表征網(wǎng)頁集合的內(nèi)容與主題,比如“歷史” 、“電腦” 、“小說”等,這是STC 算法和Lingo算法較難挖掘的。

STC和Lingo算法擅長挖掘頻繁出現(xiàn)的字串,即短語標(biāo)簽,比如“霸王條款”、“變形金剛”、“詹姆斯”,而本文的算法也借鑒這種思想進(jìn)行了改進(jìn),挖掘標(biāo)簽詞和查詢詞之間的順序關(guān)系,可以生成短語性標(biāo)簽,改進(jìn)了基于頻繁項(xiàng)集聚類的標(biāo)簽生成。改進(jìn)后的標(biāo)簽挖掘算法可以挖掘出“變形金剛”、“霸王條款”形式的標(biāo)簽,然而由于M FIC算法依賴分詞結(jié)果,對于詞典中不存在的詞(比如“詹姆斯”)無法生成標(biāo)簽。

7 結(jié)論

本文提出了一種基于全文最大頻繁項(xiàng)集的搜索引擎返回結(jié)果聚類算法。首先我們研究了頻繁項(xiàng)集的挖掘算法,結(jié)合FPMax算法對最大頻繁項(xiàng)集的挖掘進(jìn)行了改進(jìn),提高了最大頻繁項(xiàng)集的挖掘速度。然后提出了一種基于最大頻繁項(xiàng)集聚類的算法M FIC。M FIC主要包括三步,(1)由挖掘出的最大頻繁項(xiàng)集生成簇;(2)結(jié)合頻繁項(xiàng)集的相似度和簇包含文檔集合的相似度進(jìn)行簇的合并判斷;(3)最后對生成的簇提出了一種結(jié)合頻繁項(xiàng)集與詞語順序的標(biāo)簽生成算法。

實(shí)驗(yàn)結(jié)果表明MFIC算法聚類效果優(yōu)于其他算法,聚類時(shí)間優(yōu)于同樣基于全文的K-M eans算法,且能滿足在線聚類的需要。

通過本文研究發(fā)現(xiàn),基于頻繁項(xiàng)集的聚類算法在全文聚類方面有較大優(yōu)勢,不僅能對網(wǎng)頁很好的降維,同時(shí)產(chǎn)生的頻繁項(xiàng)集可以做為標(biāo)簽的候選。另一方面基于頻繁項(xiàng)集的聚類算法還有許多可以改進(jìn)的地方：第一,中間簇的合并過程,線性的合并不能很好的代表網(wǎng)頁之間的類別聯(lián)系,可以嘗試通過圖的模型進(jìn)行簇的合并;第二,標(biāo)簽詞的生成,如何判斷識別較高概念層次的詞,生成更智能的標(biāo)簽也是一項(xiàng)有研究價(jià)值的課題。

[1] Lan H uang.A Survey on Web Information Retrieval Technologies[EB/OL].ECSL Technical Report,State University of New York,2000.

[2] C.J van Rijsbergen.In formation Retrieval[M].London：Butterw orths,1979.

[3] Oren Zamir,O ren Etzioni.Web document clustering：A Feasibility Demonstration[C]//Research and Development in In formation Retrieval,1998：46-54.

[4] Stanislaw Osinski,Jerzy Stefanowski,and Dawid Weiss.Lingo：Search Results Clustering A lgorithm Based on Singular Value Decomposition[C]//Proceedings o f the International IIS：Intelligent In formation Processing and Web M ining Conference,Advances in SoftCom puting,2004：359-368.

[5] Liping Jing,Michael K.Ng,and Joshua Zhexue H uang.An Entropy Weighting k-M eans A lgorithm for Subspace Clustering of H igh-Dimensional Sparse Data[J].IEEE Transactions on Know ledge and Data Engineering,2007,19(8)：1026-1040.

[6] M ichael Steinbach,George Karypis,Vipin Kumar.A Comparison of Document Clustering Techniques[EB/OL].Technical Report,University of M innesota,2000.

[7] Wei Song;Soon Cheol Park.Genetic algorithm-based tex t clustering technique：Automatic evolution of clustes with high efficientcy[C]//Seventh International Conference on Web-Age Information Management Workshops.H ong Kong 2006：17-17.

[8] Richard Freeman,Hu jun Yin.Self-Organising M aps for Hierarchical Tree V iew DocumentClustering Using Contextual In formation[C]//Proceedings o f the IEEE International Joint Con ference on Neural Networks.2002：123-128.

[9] Daniel Crabtree,Xiaoying Gao,Peter Andreae.Imp roving Web Clustering by Cluster Selection[C]//The 2005 IEEE/WIC/ACM International Conference on Web Intelligence.2005：172-178.

[10] Hung Chim,Xiaotie Deng.A New Suffix T ree Sim ilarity Measure for Document Clustering[C]//World W ide Web Conference Comm ittee.2007：121-129.

[11] Florian Beil,Martin Ester,Xiaow ei Xu,Frequent Term-Based Text Clustering[C]//Proceedings of ACM SIGKDD International Con ference on Know ledge Discovery and Data M ining.2002：436-442.

[12] Ling Zhuang,Honghua Dai.A Maximal Frequent Itemset Approach For Web Document Clustering[C]//Proceedings of the Fourth International Conference on Computer and Information Technology.2004：970-977.

[13] Benjam in C.M.Fung,Ke Wang,Martin Ester.H ierarchical Document Clustering Using Frequent Itemsets[C]//Proceedings of SIAM Internationa l Conference on Data M ining.2003：59-69.

[14] Daniel Crabtree,Peter And reae,X iaoying Gao.Query Directed W eb Page Clustering[C]//Proceedings of the IEEE/W IC/ACM International Con ference on W eb Intelligence.2006：202-210.

[15] O ren Zamir.Clustering Web Documents：A Phrase-Based Method for Grouping Search Engine Resu lts[D].PhD Thesis,University of Washington,1999.

[16] Jiawei H an,H ong Cheng,Dong Xin,Xifeng Yan.Frequent pattern m ining：Current status and future directions.Data M ining and Know ledge Discovery[J].10th Anniversary Issue,2007,15(1)：55-86.

[17] Jiawei H an,Jian Pei,Yiwen Yin,Runying Mao.M ining Frequent PatternsW ithout Candidate Generation[C]//Proceeding o f Special Interest G roup on Management of Data.2000：1-12.

[18] Gosta Grahne,Jianfei Zhu.High Performance M ining of M aximal Frequent Itemsets[C]//Proceedings of the 6th SIAM International Workshop on H igh Performance Data M ining.2003：311-337.

[19] K rishna Kummamuru,Rohit Lotlikar,Shourya Roy.A H ierarchical Monothetic Document Clustering A lgorithm for Summarization and Brow sing Search Resu lts[C]//Proceedings of the 13th Internationa l Conference on W or ld Wide Web.2004：658-665.

[20] Ying Zhao,George Karypis.Criterion Functions for Document Clustering：Experiments and Analysis[EB/OL].TechnicalReport,Department of ComputerScience,University of M innesota,2001,01-40.

[21] Huajun Zeng,Qicai He,Zheng Chen,et al.Learn to cluster web search resu lts[C]//Proceedings of Sheffield SIGIR.2004：210-217.

[22] Zhe Zhang,Junxi Zhang,H uifeng Xue.Imp roved K-means Clustering A lgorithm[J].Journal of Southeast University.2007,23(3)：435-438.

[23] 劉遠(yuǎn)超,王曉龍,等.文檔聚類綜述[J].中文信息學(xué)報(bào),2006,20(3)：55-62.

[24] 趙世奇,劉挺,李生.一種基于主題的文本聚類方法[J].中文信息學(xué)報(bào),2007,21(2)：58-62.

[25] 邱志宏,宮雷光.利用上下文提高文本聚類的效果[J].中文信息學(xué)報(bào),2007,21(6)：109-113.

[26] 李紅梅,丁振國,周水生,等.搜索引擎中的聚類瀏覽技術(shù)[J].中文信息學(xué)報(bào),2008,22(3)：56-63

[27] 駱雄武,萬小軍,楊建武,等.基于后綴樹的W eb檢索結(jié)果聚類標(biāo)簽生成方法[J].中文信息學(xué)報(bào),2009,23(2)：83-88.