檢索結果聚類算法研究綜述

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

關鍵詞：檢索結果，；聚類，；簇，；標簽

中圖分類號：TP391

1. 引言

目前的搜索引擎的檢索器是用關鍵詞建立索引，查詢含有關鍵詞的網頁的鏈接。檢索器根據檢索結果和查詢詞的相關性從高到低排成一個線性列表。但是一個檢索結果往往包含成千上萬的網頁信息，所以搜索引擎的檢索結果的線性列表很長。同時其檢索的結果仍然包含了很多與用戶無關的信息，其比例高達75%以上[1]，用戶不得不逐個瀏覽，這導致要找到自己真正需要的信息很困難。目前有很多算法在改進檢索的排序算法，但是光改進算法是不夠的。因為很多時候用戶在輸入的查詢詞根本就不能完全表達用戶的需要，查詢的效果就比較差。

針對查詢結果不能令人滿意的情況下，很多研究學者開始在搜索結果的基礎上進行了聚類的研究。將文檔分成若干個簇（cluster），使同一簇類文檔相關度盡可能大，不同簇之間文檔相關度盡可能小，而用戶在自己感興趣的簇內查看檢索結果，就可以縮小用戶瀏覽的結果，方便用戶的查詢。對檢索結果的網頁摘要（Snippet）聚類，實質是根據摘要的主題相似性劃分成不同的簇。每一個簇的主題可以看成是查詢的子主題，這樣整個檢索結果集就可以以層次的形式呈現給用戶，最頂層為用戶查詢詞，下層為聚類得到的子主題和標簽及每個子主題下的對應的網頁摘要。

檢索結果聚類不同于傳統(tǒng)的文本聚類和網頁聚類，主要體現在[22]：

（1）檢索結果聚類既要得到高質量的簇，同時還需要確定每個簇的主題描述，或稱簇標簽，而傳統(tǒng)的聚類一般無需得到簇的標簽。簇的描述標簽非常重要，不僅需要完整的包含一定意義的短語，同時還需要能夠對該簇進行主題描述， 并且有較強的可讀性；

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

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

2.1 檢索結果聚類算法

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

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

21.1 基于文檔的聚類算法

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

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

Ngo，C.L.[7]針對向量空間模型用于網頁片斷聚類的缺陷，提出了基于容錯粗糙集模型（Tolerance Rough Set Model）的算法，聚類后再提取簇標簽。

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

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

Hua-Jun Zeng在文獻[10]中將檢索結果聚類看成是顯著短語排序（Salience Phrase Ranking）問題。首先對候選短語進行綜合評估并排序，得到潛在簇的標簽。將包含潛在標簽的文檔即被認為屬于相應的簇，最后經過合并等后處理得到最后的輸出結果。

黃健斌在文獻[11]提出了一種在格的拓撲序列上進行概念聚類的快速聚類算法。該方法利用格理論解決了概念聚類中概念間的多重繼承關系的問題，并應用在Web搜索結果聚類上，取得了較好的結果。

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

21.2 基于標簽的聚類算法

最近兩年，國內出現了很多基于標簽的聚類算法研究。駱雄武等在文獻[9]將搜索引擎返回的結果建立后綴樹，然后計算后綴樹中各個短語的得分，將得分最高的短語作為候選標簽。將包含標簽的文檔分配到標簽所對應的類中，最后形成聚類結果。

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

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

3.2 度量指標

關于搜索引擎聚類瀏覽技術，由于缺乏標準評價數據集和性能衡量標準，評價一直是一個難題，尤其是對聚類標簽的評價，主觀性很強。因此，本章對標簽的評價主要是和其他中文聚類搜索引擎進行對比。

文獻[21]采用了文檔聚類中的F 值評分作為搜索結果聚類的評價標準，該方法需要采用聚類基準，但是對于檢索結果來說，基準往往是未知的。針對搜索結果聚類的特點，人們提出了一些新的評價方法。

Wang[20]提出使用平均信息熵的評價方法。信息熵用來衡量聚類的純度，旨在判定同類中的網頁是否真正是關于同一個主題的，而本章的實驗主要采用該評價方法對簇的質量進行評估。聚類后形成的任一類別j的信息熵定義如式1所示[20]：

E（j）=-∑Pijlog（Pij）

（1）

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

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

（2）

其中，nj是類別j的大小，m是聚類的類別總數，n是聚類的網頁總數。

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

3 結束語總結

本文論述了對檢索結果聚類的重要意思，同時對基于文檔的聚類算法以及基于標簽的聚類算法進行了綜述，并且介紹了檢索結果聚類質量的評價問題。隨著web服務的廣泛應用，檢索結果聚類將越來越多的被應用在搜索引擎中，以此幫助用戶快速查找所需要的信息。

參考文獻：

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

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

[3] 陳永超， 劉貴全. 一種基于命名實體的搜索結果聚類算法[J]. 計算機工程， 2009.

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

作者簡介：盧仁猛（1980-），男，高級工程師，研究方向：數據庫及網絡安全。

作者單位：貴州電網公司，貴陽 550002