改進后綴樹的中文檢索結果聚類研究

袁津生，榮元媛

北京林業大學信息學院，北京 100083

改進后綴樹的中文檢索結果聚類研究

袁津生，榮元媛

北京林業大學信息學院，北京 100083

檢索結果聚類能夠幫助用戶快速定位需要查找的信息。注重進行中文文本聚類的同時生成高質量的標簽，獲取搜索引擎返回的網頁標題和摘要，利用分詞工具對文本分詞，去除停用詞；統一構建一棵后綴樹，以詞語為單位插入后綴樹各節點，通過詞頻、詞長、詞性和位置幾項約束條件計算各節點詞語得分；合并基類取得分高的節點詞作標簽。實驗結果顯示該方法的聚類簇純度較高，提取的標簽準確且區分性較強，方便用戶使用。

檢索結果聚類；后綴樹；聚類標簽；中文檢索；聚類

1 引言

隨著網絡信息的爆炸式增長，人們在網上使用搜索引擎查找信息時，搜索引擎會按照一定的方法將所有相關網頁排序后呈現給用戶。目前，大家經常使用的Google（http：//www.google.com.hk/）、百度（http：//www.baidu. com/）都是將結果以一定方式排列后呈現給用戶[1]。如果查詢詞的詞義唯一且明確，查詢結果能夠滿足用戶要求；如果查詢詞有歧義則會存在問題，例如當搜索模糊詞“蘋果”時，它的意思包括電子公司、電子產品、電影或水果，從Google和百度查找的結果統計發現前三頁中電影和水果類蘋果的相關信息各不超過三條，如果用戶需要大量相關信息就需繼續向后查找，十分麻煩。

目前已有一些將檢索結果進行聚類的系統，用戶根據自己的需求來定位到分類[2]，但這些都是針對英文的，根本無法滿足中文用戶的需求。因此本文提出專門針對中文的檢索結果聚類系統，具體方法為：用戶輸入關鍵詞，抓取Google搜索返回的前一百條結果項的標題和摘要內容，利用中科院的分詞系統ICTCLAS對各結果項內容進行分詞、標注詞性，去除停用詞；然后，統計各個詞語的詞頻、位置和詞長，保留下來的詞構成關鍵詞集，以詞語為單位插入后綴樹各節點；最后，構建一棵統一的后綴樹，計算節點得分、合并節點、提取標簽。

與傳統后綴樹聚類算法相比，本方法的不同之處在于，將已經分詞標注好的中文詞語插入到后綴樹各節點中，避免了后綴樹算法對中文分詞存在的不足；對于提取的標簽根據詞性、詞頻、位置和詞長來綜合考慮，不僅僅是提取高質量的標簽，還強調了標簽的描述性、可讀性和區分性。本方法的優點是解決模糊詞中同義主題的聚類，能夠快速產生可讀性較強且較為準確的標簽，幫助用戶提高檢索效率。

2 相關工作

后綴樹聚類算法（STC）[3]通過識別文檔集中的共同短語建立類。與傳統算法相比，后綴樹把文檔看成短語的有序集，短語是一個或多個詞的序列，比單個詞具有更好的描述性。STC算法是一種線性時間聚類算法，它定義包含相同短語的文檔為一個“短語簇”。Lingo算法[4]著重于類別標簽的提取，期望通過描述有意義的標簽來表達查詢返回結果中包含的核心概念，然后通過奇異值分解將網頁指派到不同標簽對應的集合中。Lingo算法和STC算法在標簽提取上都有一定優勢[5]，同時也取得較高的聚類精度。但由于中文語言的特點，它們均不適用。

文獻[6]則是利用檢索日志來進行檢索結果的聚類，對于用戶的查詢，首先搜集以前與之相關的信息和點擊學習用戶感興趣的方面；然后根據用戶感興趣的方面組織檢索結果并且用過去最有代表性的查詢作為聚類標簽，這樣的聚類結果較好，但是如果用戶查找的信息在日志中沒有相關記錄，就無法得到令人滿意的結果。

文獻[7]對于搜索引擎返回的結果統一建立后綴樹，然后計算后綴樹中各個短語的得分，選取得分最高的若干短語作為候選標簽。將搜索引擎返回的各個結果項分配到它所包含的標簽對應的分類中，形成最后的聚類。此方法生成的標簽可讀性較強，但是用于中文查詢標簽質量就很糟糕。

Vivisimo（http：//yippy.com/）是一個商業化的搜索引擎，也是目前最為成熟的進行檢索結果聚類的搜索引擎，整體表現不錯，但也無法用于中文查詢的情況。

3 本文方法

3.1 構建后綴樹

獲取Google搜索結果頁面的源代碼，利用HTML分析器從結果頁面中抽取出一個個的結果項，每個結果項包含標題和摘要。利用中科院的中文分詞系統ICTCLAS對各結果項進行分詞，標注詞性（pos）去除停用詞，另外還需標注詞語出現的位置（addr）、出現頻率（freq）和詞長（length），各結果項中保留下來的關鍵詞組成關鍵詞集進行后續計算。

構建一棵只有一個根節點的后綴樹，后綴樹內部各節點的標識為第一步中提取的關鍵詞。構建過程如下：假設長度為m的字符串S生成一棵后綴樹，首先要為樹添加一條表示后綴S[1，m]的邊，然后連續遞歸地為樹添加表示后綴S[i，m]的邊，其中i=2，3，…，m。通過上一步的提取結果，以各關鍵詞集為單位，每個節點的邊代表一個關鍵詞，它的內容是從樹的根節點到其本身所經過的邊的連接。例如，有這樣3篇文檔，從結果項中提取的關鍵詞集分別為：“汽車、品牌、型號”，“汽車、越野、排量”，“車展、汽車”，可以將它們建成一棵如圖1所示的后綴樹。其中，每個內部節點都附著一個矩形框，矩形框內記錄了經過該節點的所有文檔編號。

圖1 后綴樹示例

后綴樹的各個節點即為基類。在形成基類的過程中，用聚類內部相似度（Intra-Cluster Similarity，ICS）來驗證每個基類內部的文檔之間的相似性[8]。w為關鍵詞，D(w)為包含該關鍵詞的基類，對于每一個基類，首先將每一篇文檔轉化為向量空間模型：di=(xi1，xi2，…)，然后計算該基類的中心向量：

再計算每篇文檔和向量中心的平均相似度得到ICS：

所有文檔的ICS值從大到小排序，對于那些ICS值過小的文檔，將它剔除該基類。

正如上面我們所論述的那樣，大學生“蟻族”是內外因素綜合作用下的產物，而在這些因素中，內部因素和部分的外部因素是內在推動力，該推動力的作用對象是尚未就業的大學生，也就是大學生“蟻族”的源頭，推動的結果是使大學生在沒有對自身及外部環境充分了解的情況下做出不符合實際的就業選擇。大學生職業生涯規劃就是大學生在對內外環境進行綜合分析的情況下針對自身條件制定學習、實踐、就業計劃的一個過程，它主要針對的群體就是尚未就業的大學生，能在最開始削弱促使大學生“蟻族”產生的推動力，從而減少大學生“蟻族”的產生，起到一個“治本”的作用。

3.2 標簽選擇

在所有的關鍵詞都插入后綴樹后，需要對每個節點的關鍵詞進行計算，為以后的標簽選取做準備，具體的計算將綜合以下幾項屬性來進行：

（1）詞頻：對于詞頻因子采用公式：

其中，fi表示詞語i在結果項中的詞頻。當詞頻因子逐漸增大時，說明詞語出現的次數越多，越能表達結果項的主題。

（2）詞長：對于詞長權重的處理函數為：

li表示詞語i的詞長，Max(li)表示結果項中所有詞語的最大長度。

（3）詞性：對于結果項中的詞i，從i的詞性考慮，可得到如下權值計算公式：

（4）位置：出現在標題的詞語比出現在摘要中的詞語在反映文獻主題方面更有價值，用以下公式計算：

此處詞語w在不同位置出現的次數賦予不同權值。w1為詞語在標題中出現的次數；w2為詞語在摘要中出現的次數。

將以上屬性歸并到下面的計算公式中：

Scorei為詞語i的分數，A、B、C、D為比例系數，表明各屬性在分數計算中的比重[9]。經過對文本聚類的分析和實驗，位置在各屬性中最為重要，賦值1.5，詞頻和詞性賦值1.1，將詞長賦值為0.8。

接下來就是合并基類。給定兩個基類Am和An，如果|Am∩An|/(|An|)＞k并且|Am∩An|/(|Am|)＞k，則Am和An的相似度為1，否則為0。其中，k是一個在0和1之間的常數，通常取0.5，|Am∩An|表示Am和An所代表的節點中相同的文檔數，|Am|表示Am所代表的節點中的文檔數。將相似度為1的節點關鍵詞合并[5]，合并后的類包含所有關鍵詞對應的文檔集合。把合并后的聚類簇各候選標簽關鍵詞按分數由高到低排列，得分高的關鍵詞有較好的可讀性、代表性和區分性，即選為標簽。

4 實驗及分析

本文使用Google搜索引擎進行實驗，在輸入任意中文查詢后獲取返回的前十頁大概100條列表信息，利用HTML分析器從頁面中抽取出每個結果項，再使用ICTCLAS對結果項的文本內容進行分詞，標注詞性，去除停用詞，同時還需統計每個詞語的位置、詞頻和詞長，接下來則可開始構建后綴樹。

4.1 聚類結果評價

檢索結果聚類系統的評價與一般的文本聚類評價不同，不僅要對聚類簇的純度即簇中文檔與聚類簇的相關性進行評價，還需對類別標簽進行評價[10]。本方法在檢索結果聚類過程中，通過聚類內部相似度將基類中文本相似度較低的文檔剔除，而合并的節點主要是通過文檔之間的覆蓋率[11]來考慮的，所以聚類簇純度基本讓人滿意。

在此，與Vivisimo設計的Yippy檢索結果聚類元搜索引擎進行對比，由于Yippy對英文查詢有更好的效果，分別在本系統中輸入中文關鍵詞并在Yippy中輸入對應的英文關鍵詞，實驗中對5個歧義詞進行查詢，在兩個系統中的輸入如表1所示。

表1 實驗用的查詢詞

人工統計分析兩個系統的聚類簇純度，Yippy作為一個比較成熟的搜索引擎純度平均達到88%，本方法中的簇純度也達到81%，如圖2所示。

圖2 聚類簇純度對比

4.2 聚類標簽評價

同時還測試了表1中輸入的查詢詞返回的結果標簽集。將得到的結果分給4個不同的測試者，讓他們獨立標注出他們認為的其中比較好的標簽，據此可以計算出系統產生的標簽的正確率。

對于系統生成的前N個標簽，n個測試者參與評估，定義其正確率P@N如下：

其中，Pi@N指的是第i個測試者標注出的系統產生標簽的正確率，即

實驗中4個測試者對系統關于查詢詞生成的標簽評價如表2所示。從上述結果可以大致看出，該方法生成的標簽正確率，相應的總有P@3＞P@5＞P@10，如表2所示。

表2 標簽評價結果

根據實驗結果，得知聚類簇中越靠前的標簽越準確，這也和標簽的分數有關。

5 結語

本文主要針對檢索結果進行聚類，幫助用戶更快地定位需要查找的信息。方法中用到后綴樹聚類（STC）算法，考慮到此算法對中文分詞的不足，首先根據搜索引擎返回的結果獲取各結果項中的標簽和文本摘要，利用中科院ICTCLAS分詞工具對文本進行分詞，去除停用詞。然后，記錄保留下來的詞語的詞頻、詞長、詞性和位置，保留下來的詞構成關鍵詞集插入后綴樹。最后，構建后綴樹計算各節點得分，合并基類后取得分高的節點關鍵詞作為標簽。本方法提取的標簽簡潔、易讀且較為準確，方便用戶的使用。但是，由于對文本的處理過程相對復雜，消耗了一定的時間，以后還需要對此過程不斷優化。

[1]Croft W B，Metzler D，Strohman T.搜索引擎：信息檢索實踐[M].北京：機械工業出版社，2010.

[2]Grossman D A，Frieder O.信息檢索：算法與啟發式方法[M].北京：人民郵電出版社，2010.

[3]Zamir O，Etzioni O.Web document clustering：a feasibility demonstration[C]//Proceedings of the 19th International ACM SIGIR Conference on Research and Development of Information Retrieval（SIGIR’98），1998：46-54.

[4]Osinski S，Stefanowski J，Weiss D.Lingo：search results clustering algorithm based on singular value decomposition[C]//Proceedings of the International IIS：Intelligent Information Processing and Web Mining Conference，Advances in Soft Computing，2004：359-368.

[5]劉文婷，滕奇志.后綴樹聚類在專用搜索引擎中的應用研究與改進[J].成都信息工程學院學報，2010（3）.

[6]Wang Xuanhui，Zhai Chengxiang.Learn from Web search logs to organize search results[C]//SIGIR 2007 Proceedings，Amsterdam，The Netherlands，2007.

[7]駱雄武，萬小軍，楊建武，等.基于后綴樹的Web檢索結果聚類標簽生成方法[J].中文信息學報，2009（2）.

[8]Zeng H，He Q，Chen Z，et al.Learning to cluster web search results[C]//SIGIR，2004：210-217.

[9]張紅鷹.基于模糊處理的中文文本關鍵詞的提取算法[J].現代圖書情報技術，2009（5）.

[10]史天藝.基于維基百科的搜索引擎檢索結果聚類[D].上海：上海交通大學，2009.

[11]蘆立華.基于后綴樹的中文文本聚類算法研究[D].上海：上海海事大學，2005.

YUAN Jinsheng,RONG Yuanyuan

College of Information,Beijing Forestry University,Beijing 100083,China

The search result clustering can help users quickly find the information needed.This paper focuses on Chinese text clustering and how to generate high quality tags.The search engine returns the webpage title and abstract.It uses text segmentation tool to segment text,and removes stop words;it constructs a suffix tree,with words put into the suffix tree nodes.By several constraint conditions such as word frequency,word length,word and location,it calculates each node score;it combines base clusters and makes node word with high score as the label.The experimental results show this method’s clusters have high purity.The extracted labels are accurate and distinguish strongly.It’s user-friendly.

search results clustering;suffix tree;cluster label;Chinese search;clustering

A

TP391.1

10.3778/j.issn.1002-8331.1211-0355

YUAN Jinsheng,RONG Yuanyuan.Chinese search results cluster research based on improved STC.Computer Engineering and Applications,2014,50（21）：143-146.

袁津生（1957—），男，教授，主要研究方向：搜索引擎、計算機網絡；榮元媛（1986—），女，碩士，主要研究方向：搜索引擎。E-mail：rongyy1107@gmail.com

2012-11-29

2013-04-03

1002-8331（2014）21-0143-04

CNKI出版日期：2013-04-18，http://www.cnki.net/kcms/detail/11.2127.TP.20130418.1618.023.html