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

袁津生，榮元媛

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

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

袁津生，榮元媛

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

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

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

1 引言

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

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

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

2 相關(guān)工作

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

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

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

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

3 本文方法

3.1 構(gòu)建后綴樹

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

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

圖1 后綴樹示例

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

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

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

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

3.2 標(biāo)簽選擇

在所有的關(guān)鍵詞都插入后綴樹后，需要對(duì)每個(gè)節(jié)點(diǎn)的關(guān)鍵詞進(jìn)行計(jì)算，為以后的標(biāo)簽選取做準(zhǔn)備，具體的計(jì)算將綜合以下幾項(xiàng)屬性來進(jìn)行：

（1）詞頻：對(duì)于詞頻因子采用公式：

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)及分析

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

4.1 聚類結(jié)果評(píng)價(jià)

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

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

表1 實(shí)驗(yàn)用的查詢?cè)~

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

圖2 聚類簇純度對(duì)比

4.2 聚類標(biāo)簽評(píng)價(jià)

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

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

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

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

表2 標(biāo)簽評(píng)價(jià)結(jié)果

根據(jù)實(shí)驗(yàn)結(jié)果，得知聚類簇中越靠前的標(biāo)簽越準(zhǔn)確，這也和標(biāo)簽的分?jǐn)?shù)有關(guān)。

5 結(jié)語

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

[1]Croft W B，Metzler D，Strohman T.搜索引擎：信息檢索實(shí)踐[M].北京：機(jī)械工業(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ìn)[J].成都信息工程學(xué)院學(xué)報(bào)，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é)果聚類標(biāo)簽生成方法[J].中文信息學(xué)報(bào)，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)代圖書情報(bào)技術(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—），男，教授，主要研究方向：搜索引擎、計(jì)算機(jī)網(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