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

袁津生，榮元媛

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

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

袁津生，榮元媛

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

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

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

1 引言

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

目前已有一些將檢索結(jié)果進(jìn)行聚類(lèi)的系統(tǒng)，用戶(hù)根據(jù)自己的需求來(lái)定位到分類(lèi)[2]，但這些都是針對(duì)英文的，根本無(wú)法滿(mǎn)足中文用戶(hù)的需求。因此本文提出專(zhuān)門(mén)針對(duì)中文的檢索結(jié)果聚類(lèi)系統(tǒng)，具體方法為：用戶(hù)輸入關(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è)詞語(yǔ)的詞頻、位置和詞長(zhǎng)，保留下來(lái)的詞構(gòu)成關(guān)鍵詞集，以詞語(yǔ)為單位插入后綴樹(shù)各節(jié)點(diǎn)；最后，構(gòu)建一棵統(tǒng)一的后綴樹(shù)，計(jì)算節(jié)點(diǎn)得分、合并節(jié)點(diǎn)、提取標(biāo)簽。

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

2 相關(guān)工作

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

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

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

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

3 本文方法

3.1 構(gòu)建后綴樹(shù)

獲取Google搜索結(jié)果頁(yè)面的源代碼，利用HTML分析器從結(jié)果頁(yè)面中抽取出一個(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)注詞語(yǔ)出現(xiàn)的位置（addr）、出現(xiàn)頻率（freq）和詞長(zhǎng)（length），各結(jié)果項(xiàng)中保留下來(lái)的關(guān)鍵詞組成關(guān)鍵詞集進(jìn)行后續(xù)計(jì)算。

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

圖1 后綴樹(shù)示例

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

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

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

正如上面我們所論述的那樣，大學(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é)生在沒(méi)有對(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è)過(guò)程，它主要針對(duì)的群體就是尚未就業(yè)的大學(xué)生，能在最開(kāi)始削弱促使大學(xué)生“蟻?zhàn)濉碑a(chǎn)生的推動(dòng)力，從而減少大學(xué)生“蟻?zhàn)濉钡漠a(chǎn)生，起到一個(gè)“治本”的作用。

3.2 標(biāo)簽選擇

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

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

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

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

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

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

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

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

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

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

接下來(lái)就是合并基類(lèi)。給定兩個(gè)基類(lèi)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]，合并后的類(lèi)包含所有關(guān)鍵詞對(duì)應(yīng)的文檔集合。把合并后的聚類(lèi)簇各候選標(biāo)簽關(guān)鍵詞按分?jǐn)?shù)由高到低排列，得分高的關(guān)鍵詞有較好的可讀性、代表性和區(qū)分性，即選為標(biāo)簽。

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

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

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

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

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

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

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

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

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

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

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

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

實(shí)驗(yàn)中4個(gè)測(cè)試者對(duì)系統(tǒng)關(guān)于查詢(xú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é)果，得知聚類(lèi)簇中越靠前的標(biāo)簽越準(zhǔn)確，這也和標(biāo)簽的分?jǐn)?shù)有關(guān)。

5 結(jié)語(yǔ)

本文主要針對(duì)檢索結(jié)果進(jìn)行聚類(lèi)，幫助用戶(hù)更快地定位需要查找的信息。方法中用到后綴樹(shù)聚類(lèi)（STC）算法，考慮到此算法對(duì)中文分詞的不足，首先根據(jù)搜索引擎返回的結(jié)果獲取各結(jié)果項(xiàng)中的標(biāo)簽和文本摘要，利用中科院ICTCLAS分詞工具對(duì)文本進(jìn)行分詞，去除停用詞。然后，記錄保留下來(lái)的詞語(yǔ)的詞頻、詞長(zhǎng)、詞性和位置，保留下來(lái)的詞構(gòu)成關(guān)鍵詞集插入后綴樹(shù)。最后，構(gòu)建后綴樹(shù)計(jì)算各節(jié)點(diǎn)得分，合并基類(lèi)后取得分高的節(jié)點(diǎn)關(guān)鍵詞作為標(biāo)簽。本方法提取的標(biāo)簽簡(jiǎn)潔、易讀且較為準(zhǔn)確，方便用戶(hù)的使用。但是，由于對(duì)文本的處理過(guò)程相對(duì)復(fù)雜，消耗了一定的時(shí)間，以后還需要對(duì)此過(guò)程不斷優(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]劉文婷，滕奇志.后綴樹(shù)聚類(lèi)在專(zhuān)用搜索引擎中的應(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]駱雄武，萬(wàn)小軍，楊建武，等.基于后綴樹(shù)的Web檢索結(jié)果聚類(lèi)標(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)代圖書(shū)情報(bào)技術(shù)，2009（5）.

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

[11]蘆立華.基于后綴樹(shù)的中文文本聚類(lèi)算法研究[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