李 群，袁津生

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

0 引 言

目前大多數(shù)的搜索引擎使用的是基于關(guān)鍵詞匹配的全文檢索技術(shù)，國內(nèi)著名的百度和國外著名的Google等就是采用這種檢索方式，它的特點(diǎn)是查全率較高。隨著互聯(lián)網(wǎng)上承載信息量的日益加大，它的缺點(diǎn)也越來越明顯：

（1）全文檢索搜索引擎當(dāng)用戶輸入關(guān)鍵詞后，通常在返回用戶需要網(wǎng)頁的同時(shí)，還會(huì)返回大量冗余的信息，其主要原因是在通常情況下很多的網(wǎng)頁描述的都是一個(gè)內(nèi)容。例如當(dāng)日的新聞就有很多的網(wǎng)站都進(jìn)行轉(zhuǎn)載，結(jié)果導(dǎo)致出現(xiàn)大量的網(wǎng)頁重復(fù)，因此在查詢時(shí)也就出現(xiàn)很多相同的結(jié)果。

（2）全文檢索搜索引擎是通過關(guān)鍵詞條對全文的內(nèi)容進(jìn)行匹配來達(dá)到查詢目的。這種檢索方式的主要的缺點(diǎn)是參與匹配的關(guān)鍵詞條有時(shí)候可能出現(xiàn)二義性，導(dǎo)致查詢的結(jié)果只有具體字面的意思，而不一定是詞條本身所要表達(dá)的含義。因此這樣的檢索就會(huì)出現(xiàn)查非所查、檢非所檢的結(jié)果。

（3）全文檢索搜索引擎缺乏人性化方面的設(shè)計(jì)，信息的查詢僅由用戶輸入的關(guān)鍵詞來決定，而沒有更進(jìn)一步的“人機(jī)交流”，這也是導(dǎo)致檢索效果不盡人意的一個(gè)原因。

我們希望在使用搜索引擎查詢信息的時(shí)，可通過人機(jī)交互的方法，使得搜索引擎逐漸接近于人的思維，以此來提高檢索的有效性和查詢精度。

通過文本聚類技術(shù)能挖掘詞條間相互聯(lián)系的諸多信息，這些信息對于考察用戶的查詢意圖，為用戶提供更加準(zhǔn)確更加全面的查詢結(jié)果有很大幫助。通過聚類對同主題文檔進(jìn)行合并、冗余消除、信息融合、消除詞義二義性等。

本文提出了一種動(dòng)態(tài)求解的最優(yōu)密度聚類算法并加以實(shí)現(xiàn)。該算法采用密度聚類算法DBSCAN與層次聚類算法BIRCH（balanced iterative reducing and clustering using hierarchies）相結(jié)合的方法，構(gòu)建了一顆簇關(guān)系樹，同時(shí)對聚類參數(shù)ε進(jìn)行動(dòng)態(tài)求解，以達(dá)到參數(shù)ε的最優(yōu)。該算法與其它文本聚類算法相比最大的區(qū)別就是查詢的結(jié)果與用戶感興趣的主題具有很大的相關(guān)度，對于二義性的詞條有較高的查準(zhǔn)率。這樣可以用戶的搜索范圍相對縮小，有利于快速搜索信息。

1 算法比較

1.1 聚類原理分析

聚類方法的設(shè)計(jì)思路是對一組給定的具體的或抽象的對象或數(shù)據(jù)集進(jìn)行分組，每一個(gè)獨(dú)立的分組叫簇，分組要達(dá)到的目的是在同一個(gè)簇內(nèi)的對象是相似的，而在不同簇中的對象是不同的。我們可以用 “物以類聚”來形容這種劃分。目前已有多種傳統(tǒng)的聚類分析算法，本文的討論僅涉及3種：基于劃分的方法、層次聚類方法、基于密度的方法。

1.2 聚類方法介紹

（1）劃分方法：基于劃分的方法具體細(xì)分為K中值算法和K均值算法。K均值算法是一種基于質(zhì)心的聚類技術(shù)，詳細(xì)的介紹可參見文獻(xiàn) ［1］。在需要聚類的數(shù)據(jù)集非常巨大的情況下，K均值算法處理的聚類效果較好，但該算法的對極端值很敏感，比如一個(gè)集合中有一個(gè)特別偏離和分散的對象，就會(huì)對整個(gè)結(jié)果造成很大影響。K中值算法對于極端值不敏感，但它的計(jì)算量與K均值算法比起來要大得多，更加適用于數(shù)據(jù)量小的集合。

（2）層次方法：層次聚類方法就是對給定的對象或數(shù)據(jù)集合進(jìn)行層次上的分解。詳細(xì)介紹可參見文獻(xiàn) ［2］。該算法可細(xì)分為凝聚法和分裂法兩種，這兩種算法的代表分別是AGNES（agglomerative nesting）算法和DIANA （divisive analysis）算法。它們的分解過程是一個(gè)互逆的過程。

凝聚的層次聚類與分裂的層次聚類算法過程如圖1所示。

圖1 層次聚類

層次方法中有一種典型算法 （BIRCH），是把集合中的對象構(gòu)造成層次樹，用樹的結(jié)構(gòu)劃分聚類，并根據(jù)設(shè)定的閾值構(gòu)建一個(gè)聚類特征樹，然后在以后的階段對構(gòu)建的聚類特征樹進(jìn)行重建，以此來達(dá)到更好的聚類目的。

（3）基于密度聚類方法

前面兩種算法都是基于對象間距離的考察，適用于發(fā)現(xiàn)圓形簇。密度方法可以適用于任意形狀的簇。典型的算法是DBSCAN密度聚類算法，該算法是先檢索數(shù)據(jù)集中的核心對象，并建立新簇，然后迭代地聚合其直接密度可達(dá)對象，不斷重復(fù)這個(gè)過程到?jīng)]有新對象加到任何簇完成聚類過程。

DBSCAN算法需要設(shè)定兩個(gè)重要參數(shù)：一個(gè)是對象半徑ε內(nèi)的鄰域；另一個(gè)是最小數(shù)目的核心對象MinPts［2］。本文將在后面詳細(xì)討論關(guān)于參數(shù)的設(shè)定。

1.3 算法比較測試

本文選取了以 “北京林業(yè)大學(xué)”為關(guān)鍵詞并具有不同主題的10個(gè)網(wǎng)頁進(jìn)行聚類測試，在本測試中選取了3種算法：K均值法、AGENES算法和DBSCAN算法。測試的網(wǎng)頁及其主題如表1所示。

表1 選取的測試網(wǎng)頁

我們對這3種算法在相同的條件下進(jìn)行對比，經(jīng)過實(shí)驗(yàn)測試，得到表2。

表2 聚類結(jié)果對比

表2顯示的對3種算法的運(yùn)行時(shí)間和準(zhǔn)確率進(jìn)行了統(tǒng)計(jì)，聚類結(jié)果對比明顯，我們看出K均值算法運(yùn)行的時(shí)間最長，而準(zhǔn)確率居中；AGENES聚類算法運(yùn)行的時(shí)間居中，但準(zhǔn)確率最低；DBSCAN聚類算法準(zhǔn)確率最高，運(yùn)行時(shí)間最短。前兩種聚類算法為之所運(yùn)算的時(shí)間較長，是因?yàn)樗鼈冊谶\(yùn)算過程中使用大量的時(shí)間進(jìn)行迭代，復(fù)雜度為O （k（n－k）2），最后一種聚類算法DBSCAN的計(jì)算復(fù)雜度是O（nlogn）。通過上述實(shí)驗(yàn)我們得出結(jié)論DBSCAN聚類算法優(yōu)于基于劃分和基于層次的聚類算法。

2 最優(yōu)化密度聚類算法

在上述實(shí)驗(yàn)的基礎(chǔ)上我們提出一種改進(jìn)的DBSCAN算法，叫最優(yōu)化密度聚類算法。DBSCAN聚類算法需要有兩個(gè)參數(shù)ε鄰域和MinPts。其中MinPts可選擇3、4或者5。而參數(shù)ε在對網(wǎng)頁進(jìn)行聚類時(shí)是很難確定的。若ε值設(shè)定的較大，其結(jié)果是得到高密度的簇，也就是說得到的網(wǎng)頁相關(guān)性就會(huì)很高，甚至是完全相同的網(wǎng)頁。若ε值設(shè)定的較小，其結(jié)果是形成低密度的簇，得到的網(wǎng)頁相關(guān)性就會(huì)很低，甚至是完全不相關(guān)的網(wǎng)頁也聚到了一起。參照以往的經(jīng)驗(yàn)，ε是在 ［0.3，0.9］之間的區(qū)間進(jìn)行變化，變化方向?yàn)橛纱蟮叫。兓葹?.1。

參數(shù)ε幅度均勻變化并逐漸降低的算法有可能會(huì)出現(xiàn)在某個(gè)ε鄰域內(nèi)，合并的網(wǎng)頁數(shù)量太多，即合并了許多噪聲對象，也可能會(huì)出現(xiàn)在某個(gè)ε鄰域內(nèi)網(wǎng)頁的數(shù)量極少的現(xiàn)象，即僅合并了完全相似的對象。因此，按照固定值的參數(shù)ε進(jìn)行聚類的做法并不可取。針對輸入?yún)?shù)ε的設(shè)定，本文在此提出一種對參數(shù)ε進(jìn)行動(dòng)態(tài)求解的方法。

2.1 輸入?yún)?shù)ε的求解

對輸入?yún)?shù)ε的計(jì)算需要設(shè)定兩個(gè)參數(shù)P和N，其中：P＝＃ （εN）表示人們在通常情況下在點(diǎn)擊到最后希望得到的網(wǎng)頁的數(shù)量；N表示人們在通常情況下能忍受的點(diǎn)擊“相關(guān)查看”的次數(shù)。如圖2所示。

圖2 參數(shù)求解曲線

在圖2中，我們假設(shè)用i來表示用戶點(diǎn)擊相關(guān)查看的次數(shù)，那么有

根據(jù)上面的公式可以得到

在點(diǎn)擊到第N次相關(guān)查看后，可以得到公式

一般來說，用戶在點(diǎn)擊N次之后，期望看到的剩余網(wǎng)頁的數(shù)量為P，N和P是兩個(gè)常量，則根據(jù)式 （2）有：αN＝于是得到公式

如果出現(xiàn)：＃ （ε0）＜P時(shí)，就不需要對網(wǎng)頁進(jìn)行聚類運(yùn)算了。在通常情況下，＃ （ε0）＞P的。

由式 （3）得到了α，根據(jù)α可以求出：＃（εi）＝ ＃（ε0）·α－i，設(shè)ε0＝0.3，就可以解出ε1，ε2，……，εi。

使用數(shù)據(jù)擬合的方法來求解參數(shù)ε，在很小的范圍內(nèi)將參數(shù)ε的變化用一條下降的直線來代替，這樣處理后對參數(shù)ε的求解就簡化成對這條直線方程的求解，如圖3所示。

圖3 參數(shù)求解方程

由圖3的曲線可以得到連接ε0和εN的直線方程為

可以求出：y＝ ＃（εi）＝ ＃（ε0）α－i，對應(yīng)的x為

這樣，就求解出了xi也就是ε1，ε2，……，εi。

2.2 算法流程

DBSCAN算法中涉及的兩個(gè)參數(shù)ε和MinPts，我們可以將參數(shù)ε理解為半徑，MinPts是一個(gè)限制條件。該算法的目的就是在ε這個(gè)半徑內(nèi)查找樣本數(shù)n，當(dāng)滿足條件n＞＝MinPts時(shí)，就是核心樣本點(diǎn)。算法步驟描述：

（1）設(shè)定MinPts的值和計(jì)算出參數(shù)ε的值；

（2）對集合內(nèi)所有對象依次遍歷，確定目標(biāo)對象result－Object；

（3）查詢目標(biāo)對象的鄰域n，對訪問過的對象做標(biāo)記；

（4）如果n是核心對象，就做標(biāo)記為Key＿Object；

（5）如果n是非核心對象，就做標(biāo)記為Noise＿Object；

（6）對核心對象Key＿Object進(jìn)行遞歸，直到滿足設(shè)定的初始條件。

對于參數(shù)ε的設(shè)定，我們可以使用式 （5）來得到；對于聚類方法，我們采用將密度聚類算法DBSCAN與層次聚類算法BIRCH相結(jié)合的方法，形成一棵聚類的簇關(guān)系樹。如圖4所示。

由簇關(guān)系數(shù)圖看出，簇2的分枝里包含了簇3、簇4和簇5，但并不一定簇2就完全由簇3、簇4、簇5構(gòu)成。通常還有一部分在這一層次被定義為噪聲的對象。通過關(guān)系樹，就可以ε的值返回到高層次的聚類，或進(jìn)一步深入的查詢，比如在聚類結(jié)果中再進(jìn)行更深入的查詢等，我們將這種簇關(guān)系樹應(yīng)用在搜索引擎中可完成不同層次的聚類。增加ε的值就可以得到較高層次的聚類；減少ε的值就可以進(jìn)入更深層次的聚類。

圖4 簇關(guān)系樹

設(shè)C為全部簇的集合，則有公式Ci，ε∈C，其中Ci，ε簇指的是i的ε鄰域的簇，Oi為簇Ci，ε中包含的全部對象的集合。對于任意Ci，ε存在方法

假定當(dāng)前的層次為εi，若用戶查想看更深層次的內(nèi)容，我們有方法

假定當(dāng)前的層次為εi，若用戶查想看更多的內(nèi)容，我們有方法

式 （7）是查找找比當(dāng)前層次更高密度的對象，也就是擴(kuò)大查詢范圍；式 （8）是查找比當(dāng)前層次更低密度的對象，也就是更深入準(zhǔn)確定位查詢信息。

利用這棵關(guān)系樹，我們可以設(shè)計(jì)一個(gè)引導(dǎo)機(jī)制來完成搜索引擎與用戶之間的交互操作，使用戶進(jìn)行更深入、更廣泛的信息查詢。例如，當(dāng)用戶輸入關(guān)鍵詞 “日本”后，搜索引擎在返回的結(jié)果頁面上出現(xiàn)相關(guān)的引導(dǎo)按鈕，這時(shí)，用戶根據(jù)自己的需求點(diǎn)擊此按鈕進(jìn)入到相應(yīng)的頁面，來對查詢的信息更準(zhǔn)確的定位。

3 性能評價(jià)

為了測試算法的性能，本文構(gòu)建了一個(gè)搜索引擎，并選取了一些目前比較熱門，關(guān)注度比較高的詞條。為滿足測試的需要，我們抓取了新浪網(wǎng)站上面的國際新聞板塊里面的1259個(gè)網(wǎng)頁，在去掉網(wǎng)頁中包含的多媒體信息之后，我們選取兩類詞來進(jìn)行驗(yàn)證，一是具有新聞代表性的詞“利比亞”、“卡扎非”；另一個(gè)是中性詞 “土豆”。

我們選擇著名搜索引擎百度與在本算法基礎(chǔ)上實(shí)現(xiàn)的搜索系統(tǒng)進(jìn)行性能上的對比，主要是對輸入關(guān)鍵詞后返回的查詢結(jié)果進(jìn)行對比分析。由于百度搜索引擎返回的數(shù)據(jù)量巨大，我們僅選取其搜索結(jié)果的前5個(gè)頁面的數(shù)據(jù)，如表3所示。

表3 測試結(jié)果比較

在表3可以看出，當(dāng)輸入多個(gè)關(guān)鍵詞的情況下，百度的查準(zhǔn)率高些，但如果用戶僅輸入單一或較少關(guān)鍵詞的時(shí)候，準(zhǔn)確率就不高。實(shí)驗(yàn)中我們輸入 “利比亞”這個(gè)詞，目的是希望得到利比亞卡扎非的相關(guān)信息。在返回結(jié)果欄目下，百度的前50個(gè)結(jié)果中只有8條是關(guān)于卡扎非的信息，若輸入 “利比亞 卡扎非”則百度相關(guān)數(shù)欄目下就達(dá)可到50條信息。本算法在返回結(jié)果的35條記錄中，雖然只有3條，但可以使用 “相關(guān)查詢”的操作，就能準(zhǔn)確定位利比亞卡扎非的有關(guān)信息。再比如，我們在百度搜索中輸入關(guān)鍵詞 “土豆”，返回的前5頁中出現(xiàn)的都是土豆網(wǎng)中的內(nèi)容，有關(guān)土豆種植的信息就非常少了。但在本算法中，通過提示按鈕，用戶就可以得到土豆種植的相關(guān)信息了。

綜上所述，當(dāng)用戶在能對自己需要查詢的信息準(zhǔn)確定位，使用的關(guān)鍵詞描述精確全面的情況下，百度等搜索引擎查詢能得到較好的結(jié)果；當(dāng)用戶不能準(zhǔn)確定位詞條，或輸入的關(guān)鍵詞具有二義或歧義的情況下，本系統(tǒng)通過改進(jìn)聚類處理之后得到的結(jié)果比較理想。

4 結(jié)束語

本文提出了一種動(dòng)態(tài)求解的最優(yōu)密度聚類算法，并測試了該算法基礎(chǔ)上實(shí)現(xiàn)的搜索引擎的性能。該算法的關(guān)鍵是對參數(shù)ε進(jìn)行動(dòng)態(tài)求解，以達(dá)到參數(shù)ε的最優(yōu)化值，以及將密度聚類與層次聚類相結(jié)合形成簇關(guān)系樹。實(shí)驗(yàn)證明該算法可以有效的彌補(bǔ)全文檢索算法的不足，提高含義不同詞條的查準(zhǔn)率。該系統(tǒng)通過人性化的設(shè)計(jì)加入了 “用戶干預(yù)”，使得搜索引擎能進(jìn)一步明確用戶的查詢意圖，去除冗余，返回給用戶準(zhǔn)確有效的信息。

［1］LIU Yanli，LIU Xiyun.K－means clustering algorithm based on density ［J］.Computer Engineering and Applications，2007，43（32）：153－155 （in Chinese）.［劉艷麗，劉希云.一種基于密度的K－均值算法 ［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43 （32）：153－155.］

［2］DUAN Mingxiu.Hierarchical clustering algorithm of the researchand application ［D］.Changsha：Central South University，2009：15－16（in Chinese）.［段明秀.層次聚類算法的研究及應(yīng)用 ［D］.長沙：中南大學(xué)，2009：15－16.］

［3］CAI Yue.A feasible text clustering algorithm of search engine［D］.Beijing：Beijing Forestry University，2010：10－13 （in Chinese）.［蔡岳.一種應(yīng)用于搜索引擎的文本聚類算法 ［D］.北京：北京林業(yè)大學(xué)，2010：10－13.］

［4］LI Xinliang.Improved research of hierarchical clustering algorithm ［J］.Software Guide，2007，6 （10）：141－142 （in Chinese）.［李新良.基于層次聚類算法的改進(jìn)研究 ［J］.軟件導(dǎo)刊，2007，6 （10）：141－142.］

［5］Anagnostopoulos A，Broder A，Punera K.Effective and efficient classification on a search－engine model［J］.Knowl Inf Syst，2008，16（2）：129－154.

［6］Leung K Wai－Ting，Wilfred Ng，LEE D L.Personalized concept－based clustering of search engine queries ［J］.IEEE Transactions on Knowledge and Data Engineering，2008，20（11）：1505－1518.

［7］LI Xiaoguang. Text clustering approach based on content characteristic［J］.Computer Engineering，2007，33 （14）：24－26（in Chinese）. ［李曉光.一種基于內(nèi)容特性的文本聚類方法［J］.計(jì)算機(jī)工程，2007，33 （14）：24－26.］

［8］Mike Thelwall.Quantitative comparisons of search engine results［J］.Journal of the American Society for Information Science and Technology，2008，59 （11）：1702－1710.

［9］XIAO Zhuocheng，JING Jinhua.User interest based search engine ［J］.Computer Applications and Software，2007，24 （9）：134－136（in Chinese）.［肖卓程，荊金華.基于用戶興趣的搜索引擎 ［J］.計(jì)算機(jī)應(yīng)用與軟件，2007，24 （9）：134－136.］

［10］ZHANG Yulian.Clustering of search engine query log ［J］.Computer Engineering，2009，35 （1）：43－45 （in Chinese）.［張玉連.搜索引擎查詢?nèi)罩镜木垲?［J］.計(jì)算機(jī)工程，2009，35 （1）：43－45.］

［11］Mecca G，Raunich S，Pappalardo A.A new algorithm for clustering search results ［J］.Data ＆ Knowledge Engineering，2007，62 （3）：504－522.

［12］HE Xiaofei，Jhala P.Regularized query classification using search click information［J］.Pattern Recognition，2008，41（7）：2283－2288.

［13］RU Y，Horowitz E.Automated classification of HTML forms on E－commerce web site ［J］.Online Information Review，2007，31 （4）：451－466.

［14］LIAO Yichun.A weight－based approach to information retrieval and relevance feedback ［J］.Expert Systems with Applications，2008，35 （1－2）：254－261.

［15］LI Qun，HUANG Xinyuan.Research on text clustering algorithms［C］.Wuhan，China：Proc of 2nd International Workshop on Database Technology and Applications，2010：734－736.