李 群，袁津生

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

0 引 言

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

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

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

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

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

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

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

1 算法比較

1.1 聚類原理分析

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

1.2 聚類方法介紹

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

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

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

圖1 層次聚類

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

（3）基于密度聚類方法

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

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

1.3 算法比較測試

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

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

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

表2 聚類結果對比

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

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

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

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

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

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

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

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

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

在點擊到第N次相關查看后，可以得到公式

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

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

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

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

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

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

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

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

2.2 算法流程

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

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

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

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

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

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

（6）對核心對象Key＿Object進行遞歸，直到滿足設定的初始條件。

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

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

圖4 簇關系樹

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

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

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

式 （7）是查找找比當前層次更高密度的對象，也就是擴大查詢范圍；式 （8）是查找比當前層次更低密度的對象，也就是更深入準確定位查詢信息。

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

3 性能評價

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

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

表3 測試結果比較

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

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

4 結束語

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

［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］.計算機工程與應用，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）.［段明秀.層次聚類算法的研究及應用 ［D］.長沙：中南大學，2009：15－16.］

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

［4］LI Xinliang.Improved research of hierarchical clustering algorithm ［J］.Software Guide，2007，6 （10）：141－142 （in Chinese）.［李新良.基于層次聚類算法的改進研究 ［J］.軟件導刊，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］.計算機工程，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］.計算機應用與軟件，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］.計算機工程，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.