袁津生，榮元媛

北京林業(yè)大學(xué)信息學(xué)院，北京 100083

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

袁津生，榮元媛

北京林業(yè)大學(xué)信息學(xué)院，北京 100083

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

檢索結(jié)果聚類；后綴樹；聚類標簽；中文檢索；聚類

1 引言

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

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

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

2 相關(guān)工作

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

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

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

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

3 本文方法

3.1 構(gòu)建后綴樹

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

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

圖1 后綴樹示例

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

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

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

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

3.2 標簽選擇

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

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

其中，fi表示詞語i在結(jié)果項中的詞頻。當(dāng)詞頻因子逐漸增大時，說明詞語出現(xiàn)的次數(shù)越多，越能表達結(jié)果項的主題。

（2）詞長：對于詞長權(quán)重的處理函數(shù)為：

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

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

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

此處詞語w在不同位置出現(xiàn)的次數(shù)賦予不同權(quán)值。w1為詞語在標題中出現(xiàn)的次數(shù)；w2為詞語在摘要中出現(xiàn)的次數(shù)。

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

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

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

4 實驗及分析

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

4.1 聚類結(jié)果評價

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

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

表1 實驗用的查詢詞

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

圖2 聚類簇純度對比

4.2 聚類標簽評價

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

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

其中，Pi@N指的是第i個測試者標注出的系統(tǒng)產(chǎn)生標簽的正確率，即

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

表2 標簽評價結(jié)果

根據(jù)實驗結(jié)果，得知聚類簇中越靠前的標簽越準確，這也和標簽的分數(shù)有關(guān)。

5 結(jié)語

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

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

[2]Grossman D A，F(xiàn)rieder O.信息檢索：算法與啟發(fā)式方法[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]劉文婷，滕奇志.后綴樹聚類在專用搜索引擎中的應(yīng)用研究與改進[J].成都信息工程學(xué)院學(xué)報，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檢索結(jié)果聚類標簽生成方法[J].中文信息學(xué)報，2009（2）.

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

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

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

[11]蘆立華.基于后綴樹的中文文本聚類算法研究[D].上海：上海海事大學(xué)，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—），男，教授，主要研究方向：搜索引擎、計算機網(wǎng)絡(luò)；榮元媛（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