摘 要： 隨著互聯(lián)網(wǎng)的普及和web上網(wǎng)頁(yè)數(shù)量的迅猛增長(zhǎng)，搜索引擎已經(jīng)成為從網(wǎng)上獲取信息的首選工具。然而，目前主流的搜索引擎利用關(guān)鍵詞建立索引，根據(jù)檢索結(jié)果和查詢?cè)~的相關(guān)性從高到低排成一個(gè)很長(zhǎng)的線性列表，而且檢索結(jié)果中包含了大量的無用信息，因此對(duì)檢索結(jié)果進(jìn)行重新組織和挖掘成為了研究熱點(diǎn)。本文介紹了檢索結(jié)果聚類的應(yīng)用背景，然后介紹了檢索結(jié)果聚類的算法，最后介紹了檢索結(jié)果聚類質(zhì)量評(píng)測(cè)標(biāo)準(zhǔn)。

關(guān)鍵詞：檢索結(jié)果，；聚類，；簇，；標(biāo)簽

中圖分類號(hào)：TP391

1. 引言

目前的搜索引擎的檢索器是用關(guān)鍵詞建立索引，查詢含有關(guān)鍵詞的網(wǎng)頁(yè)的鏈接。檢索器根據(jù)檢索結(jié)果和查詢?cè)~的相關(guān)性從高到低排成一個(gè)線性列表。但是一個(gè)檢索結(jié)果往往包含成千上萬的網(wǎng)頁(yè)信息，所以搜索引擎的檢索結(jié)果的線性列表很長(zhǎng)。同時(shí)其檢索的結(jié)果仍然包含了很多與用戶無關(guān)的信息，其比例高達(dá)75%以上[1]，用戶不得不逐個(gè)瀏覽，這導(dǎo)致要找到自己真正需要的信息很困難。目前有很多算法在改進(jìn)檢索的排序算法，但是光改進(jìn)算法是不夠的。因?yàn)楹芏鄷r(shí)候用戶在輸入的查詢?cè)~根本就不能完全表達(dá)用戶的需要，查詢的效果就比較差。

針對(duì)查詢結(jié)果不能令人滿意的情況下，很多研究學(xué)者開始在搜索結(jié)果的基礎(chǔ)上進(jìn)行了聚類的研究。將文檔分成若干個(gè)簇（cluster），使同一簇類文檔相關(guān)度盡可能大，不同簇之間文檔相關(guān)度盡可能小，而用戶在自己感興趣的簇內(nèi)查看檢索結(jié)果，就可以縮小用戶瀏覽的結(jié)果，方便用戶的查詢。對(duì)檢索結(jié)果的網(wǎng)頁(yè)摘要（Snippet）聚類，實(shí)質(zhì)是根據(jù)摘要的主題相似性劃分成不同的簇。每一個(gè)簇的主題可以看成是查詢的子主題，這樣整個(gè)檢索結(jié)果集就可以以層次的形式呈現(xiàn)給用戶，最頂層為用戶查詢?cè)~，下層為聚類得到的子主題和標(biāo)簽及每個(gè)子主題下的對(duì)應(yīng)的網(wǎng)頁(yè)摘要。

檢索結(jié)果聚類不同于傳統(tǒng)的文本聚類和網(wǎng)頁(yè)聚類，主要體現(xiàn)在[22]：

（1）檢索結(jié)果聚類既要得到高質(zhì)量的簇，同時(shí)還需要確定每個(gè)簇的主題描述，或稱簇標(biāo)簽，而傳統(tǒng)的聚類一般無需得到簇的標(biāo)簽。簇的描述標(biāo)簽非常重要，不僅需要完整的包含一定意義的短語(yǔ)，同時(shí)還需要能夠?qū)υ摯剡M(jìn)行主題描述， 并且有較強(qiáng)的可讀性；

（2）檢索結(jié)果的聚類對(duì)象為網(wǎng)頁(yè)片斷，信息有限，而傳統(tǒng)的聚類對(duì)象為文本或網(wǎng)頁(yè)的全文，包含了豐富的信息；

（3）檢索結(jié)果聚類屬于在線聚類（Online Clustering），檢索對(duì)象動(dòng)態(tài)變化，實(shí)時(shí)性要求高。而傳統(tǒng)的聚類對(duì)象一般比較穩(wěn)定，對(duì)算法的效率沒有實(shí)時(shí)性要求。根據(jù)上述特點(diǎn)傳統(tǒng)的聚類不能直接適用于檢索結(jié)果聚類。

2.1 檢索結(jié)果聚類算法

從上世紀(jì)九十年代中期開始，Pedersen[2，3] 等人提出基于結(jié)果的聚類算法。目前，很多研究者已經(jīng)研究并提出了一系列的基于檢索結(jié)果聚類算法，也出現(xiàn)了幾個(gè)投入運(yùn)營(yíng)的、具有聚類功能的搜索引擎。然而，聚類的效果還遠(yuǎn)未達(dá)到令人滿意的程度，聚類質(zhì)量還有待提高，尤其是簇標(biāo)簽的可讀性還有必要進(jìn)行大的改進(jìn)。否則，聚類功能不但對(duì)用戶的幫助有限，而且還會(huì)誤導(dǎo)用戶。但是由于聚類是具有實(shí)時(shí)性的，所以對(duì)采用算法的復(fù)雜性也提出了要求。例如，元搜索引擎Metacrawler利用后綴樹聚類算法，過濾了由多個(gè)搜索引擎返回的不相關(guān)的重復(fù)的檢索結(jié)果，然后對(duì)返回結(jié)果的片段進(jìn)行聚類，但是它并不支持中文查詢?cè)~。國(guó)內(nèi)最著名的基于聚類的中文元搜索引擎比比貓www.bbmao.com，遺憾的是它只存在了非常短暫的時(shí)間。

目前基于檢索結(jié)果摘要聚類的算法主要分為兩大類[4]。第一類是先對(duì)檢索結(jié)果集進(jìn)行聚類，然后再針對(duì)每個(gè)簇提取簇標(biāo)簽，這種方法稱為基于文檔（Document-based）的聚類方法；第二類是先提取簇的標(biāo)簽，再根據(jù)標(biāo)簽在網(wǎng)頁(yè)片斷中的出現(xiàn)情況，利用聚類算法進(jìn)行聚類，這種方法被稱為基于標(biāo)簽（Label-based）的聚類方法。盡管研究者們?yōu)榱颂岣邫z索結(jié)果的聚類質(zhì)量進(jìn)行了卓有成效的努力，然而，在目前搜索引擎的應(yīng)用背景下，如果沒有好的簇標(biāo)簽，用戶仍然難以快速準(zhǔn)確地找到自己感興趣的信息，差的標(biāo)簽甚至對(duì)用戶具有誤導(dǎo)作用。因此，近年來，基于標(biāo)簽的檢索結(jié)果聚類逐漸成為研究的主流和熱點(diǎn)，這類方法更加強(qiáng)調(diào)標(biāo)簽的可讀性和對(duì)簇的概括性，不太注重每個(gè)簇的連貫性（Coherence）。

21.1 基于文檔的聚類算法

基于文檔的聚類算法主要的目標(biāo)是提高檢索結(jié)果聚類的質(zhì)量，在聚類完成以后再提取對(duì)應(yīng)類別的標(biāo)簽。Steven Schockaert[5]提出基于模糊蟻群算法對(duì)檢索結(jié)果進(jìn)行聚類的基本思想，然后提取簇的標(biāo)簽，其目的主要是為解決傳統(tǒng)聚類需要指定簇個(gè)數(shù)且質(zhì)量不高的問題，而標(biāo)簽的提取不是重點(diǎn)，重點(diǎn)在于聚類的質(zhì)量。

Fatih Gelgi [6]為了準(zhǔn)確提取文檔特征和對(duì)特征進(jìn)行加權(quán)，使用關(guān)系圖表示特征詞與查詢?cè)~之間的關(guān)聯(lián)，再用Term Rank進(jìn)行關(guān)聯(lián)度分析，根據(jù)關(guān)聯(lián)度分析結(jié)果將特征詞劃分為區(qū)分性詞項(xiàng)、歧義性詞項(xiàng)和公共詞項(xiàng)，并對(duì)三種不同類型的詞項(xiàng)采用不同的加權(quán)方式。在文檔聚類的時(shí)候采用K-Means和SCuBa兩種算法，但文中未涉及標(biāo)簽的提取問題，主要目標(biāo)是通過新的特征提取和加權(quán)方法提高檢索結(jié)果的聚類質(zhì)量。

Ngo，C.L.[7]針對(duì)向量空間模型用于網(wǎng)頁(yè)片斷聚類的缺陷，提出了基于容錯(cuò)粗糙集模型（Tolerance Rough Set Model）的算法，聚類后再提取簇標(biāo)簽。

國(guó)內(nèi)為提高檢索結(jié)果的聚類質(zhì)量也開展了一系列的研究工作，也提出了若干比較有效的算法。沙蕓在文獻(xiàn)[8]提出了的是一種線聚類再提出簇描述標(biāo)簽的算法。該算法根據(jù)詞間的語(yǔ)義相關(guān)度進(jìn)行聚類，把詞看作是聚類的核心，詞所在的文檔作為詞的屬性，根據(jù)詞在文檔中的共現(xiàn)的情況來劃分簇，最后給簇確定其標(biāo)簽。

李紅梅等在文獻(xiàn)[9]中提出了提出了基于概念分組的聚類算法。根據(jù)概念分組技術(shù)找出特征詞之間的語(yǔ)義關(guān)聯(lián)并形成概念類，再計(jì)算文檔與概念類的距離以此進(jìn)行聚類。最后根據(jù)特征詞在文檔中的重要性提取簇描述標(biāo)簽。

Hua-Jun Zeng在文獻(xiàn)[10]中將檢索結(jié)果聚類看成是顯著短語(yǔ)排序（Salience Phrase Ranking）問題。首先對(duì)候選短語(yǔ)進(jìn)行綜合評(píng)估并排序，得到潛在簇的標(biāo)簽。將包含潛在標(biāo)簽的文檔即被認(rèn)為屬于相應(yīng)的簇，最后經(jīng)過合并等后處理得到最后的輸出結(jié)果。

黃健斌在文獻(xiàn)[11]提出了一種在格的拓?fù)湫蛄猩线M(jìn)行概念聚類的快速聚類算法。該方法利用格理論解決了概念聚類中概念間的多重繼承關(guān)系的問題，并應(yīng)用在Web搜索結(jié)果聚類上，取得了較好的結(jié)果。

張輝等在文獻(xiàn)[12]提出基于關(guān)鍵特征的聚類算法（KFC）。首先從檢索結(jié)果的關(guān)鍵詞中選擇重要的詞作為關(guān)鍵特征，然后通過分析關(guān)鍵特征之間的關(guān)系，并對(duì)特征聚類，最后通過對(duì)特征的聚類達(dá)到對(duì)檢索結(jié)果聚類的目的。

21.2 基于標(biāo)簽的聚類算法

最近兩年，國(guó)內(nèi)出現(xiàn)了很多基于標(biāo)簽的聚類算法研究。駱雄武等在文獻(xiàn)[9]將搜索引擎返回的結(jié)果建立后綴樹，然后計(jì)算后綴樹中各個(gè)短語(yǔ)的得分，將得分最高的短語(yǔ)作為候選標(biāo)簽。將包含標(biāo)簽的文檔分配到標(biāo)簽所對(duì)應(yīng)的類中，最后形成聚類結(jié)果。

陳毅恒在文獻(xiàn)[13]對(duì)檢索結(jié)果中的句子進(jìn)行依存句法分析，利用同義詞詞林為Ontology提取與查詢?cè)~強(qiáng)關(guān)聯(lián)的短語(yǔ)作為候選標(biāo)簽和簇的質(zhì)心，通過K-均值算法對(duì)檢索結(jié)果進(jìn)行聚類。該算法存在的缺點(diǎn)是大量使用了外部資源，需要句法知識(shí)和概念語(yǔ)義方面的知識(shí)作為支撐，對(duì)檢索結(jié)果進(jìn)行句法分析的時(shí)候效率比較低，而且無法保證句法分析的正確。張?jiān)圃谖墨I(xiàn)[14]中提出了一種對(duì)檢索結(jié)果層次化的聚類方法。根據(jù)詞之間的共現(xiàn)特性找出頻繁的2元短語(yǔ)，再以此進(jìn)行擴(kuò)展成多元短語(yǔ)產(chǎn)生候選標(biāo)簽。最后，將文檔分配到標(biāo)簽對(duì)應(yīng)的簇，形成層次化聚類結(jié)果。陳永超等在文獻(xiàn)[15]提出一種基于命名實(shí)體的搜索結(jié)果聚類算法NEC。該算法將命名實(shí)體作為類的候選標(biāo)簽，再根據(jù)標(biāo)簽確定聚類內(nèi)容的方法，有效地保證了標(biāo)簽的可讀性及標(biāo)簽與內(nèi)容之間的主題相關(guān)性。張剛在文[16]提出基于文檔頻率（DF）、查詢?nèi)罩尽⒉樵冊(cè)~上下文來抽取標(biāo)簽，在此基礎(chǔ)上利用基于圖的聚類算法對(duì)檢索結(jié)果進(jìn)行聚類。肖欣延在文[17]考慮了標(biāo)簽與查詢?cè)~之間的相關(guān)性，查詢?cè)~出現(xiàn)的位置，將共現(xiàn)足夠頻繁的候選短語(yǔ)抽取出來作為潛在標(biāo)簽，利用知網(wǎng)計(jì)算的詞匯之間的語(yǔ)義距離來實(shí)現(xiàn)聚類和簇的合并等后處理。

通過很多研究者的努力，目前基于標(biāo)簽的聚類算法在標(biāo)簽和聚類質(zhì)量方面都有明顯的改善。然而絕大多數(shù)都使用了大量的外部信息資源，如Ontology[18]，知網(wǎng)的信息[19]，詞性的信息，句法知識(shí)，外部的錨文本信息等。這些信息的使用雖然可以提高質(zhì)量，但也會(huì)增加聚類的負(fù)擔(dān)，加大聚類的時(shí)間和空間消耗，特別對(duì)于實(shí)時(shí)的在線聚類，將非常影響查詢效率。

3.2 度量指標(biāo)

關(guān)于搜索引擎聚類瀏覽技術(shù)，由于缺乏標(biāo)準(zhǔn)評(píng)價(jià)數(shù)據(jù)集和性能衡量標(biāo)準(zhǔn)，評(píng)價(jià)一直是一個(gè)難題，尤其是對(duì)聚類標(biāo)簽的評(píng)價(jià)，主觀性很強(qiáng)。因此，本章對(duì)標(biāo)簽的評(píng)價(jià)主要是和其他中文聚類搜索引擎進(jìn)行對(duì)比。

文獻(xiàn)[21]采用了文檔聚類中的F 值評(píng)分作為搜索結(jié)果聚類的評(píng)價(jià)標(biāo)準(zhǔn)，該方法需要采用聚類基準(zhǔn)，但是對(duì)于檢索結(jié)果來說，基準(zhǔn)往往是未知的。針對(duì)搜索結(jié)果聚類的特點(diǎn)，人們提出了一些新的評(píng)價(jià)方法。

Wang[20]提出使用平均信息熵的評(píng)價(jià)方法。信息熵用來衡量聚類的純度，旨在判定同類中的網(wǎng)頁(yè)是否真正是關(guān)于同一個(gè)主題的，而本章的實(shí)驗(yàn)主要采用該評(píng)價(jià)方法對(duì)簇的質(zhì)量進(jìn)行評(píng)估。聚類后形成的任一類別j的信息熵定義如式1所示[20]：

E（j）=-∑Pijlog（Pij）

（1）

其中，pij是類別j屬于給定類i的概率。

聚類集的平均信息熵定義如式2所示[20]：

（2）

其中，nj是類別j的大小，m是聚類的類別總數(shù)，n是聚類的網(wǎng)頁(yè)總數(shù)。

4.用戶評(píng)價(jià)的方法包括系統(tǒng)日志分析和用戶主觀兩種評(píng)價(jià)方式。Grouper通過對(duì)系統(tǒng)的日志進(jìn)行分析，根據(jù)日志的統(tǒng)計(jì)結(jié)果對(duì)聚類的性能做出評(píng)價(jià)。LINGO則采用了用戶主觀評(píng)價(jià)的法，即通過問卷調(diào)查的方式，根據(jù)對(duì)測(cè)試用戶的反饋結(jié)果，對(duì)聚類系統(tǒng)性能進(jìn)行評(píng)價(jià)。這種人工評(píng)測(cè)的方法也是目前聚類系統(tǒng)評(píng)測(cè)中采用較多的一種評(píng)價(jià)方法。

3 結(jié)束語(yǔ)總結(jié)

本文論述了對(duì)檢索結(jié)果聚類的重要意思，同時(shí)對(duì)基于文檔的聚類算法以及基于標(biāo)簽的聚類算法進(jìn)行了綜述，并且介紹了檢索結(jié)果聚類質(zhì)量的評(píng)價(jià)問題。隨著web服務(wù)的廣泛應(yīng)用，檢索結(jié)果聚類將越來越多的被應(yīng)用在搜索引擎中，以此幫助用戶快速查找所需要的信息。

參考文獻(xiàn)：

[1]M.W.Berry，Z.Drrmac，E.R.Jessup.Matrices，Vector Spaces，and Information Retrieval[J].SIAM Review，2004（41）：335-362.

[2] 黃健斌，姬紅兵.基于模糊概念格的Web搜索結(jié)果聚類算法[J]. 西安電子科技大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2005.

[3] 陳永超， 劉貴全. 一種基于命名實(shí)體的搜索結(jié)果聚類算法[J]. 計(jì)算機(jī)工程， 2009.

[4] 張剛， 劉悅， 郭嘉豐. 一種層次化的檢索結(jié)果聚類方法[J]. 計(jì)算機(jī)研究與發(fā)展， 2008.

作者簡(jiǎn)介：盧仁猛（1980-），男，高級(jí)工程師，研究方向：數(shù)據(jù)庫(kù)及網(wǎng)絡(luò)安全。

作者單位：貴州電網(wǎng)公司，貴陽(yáng) 550002