基于概念聚類的Web數據挖掘搜索引擎的設計與實現

劉典型等

摘 要：針對Web數據挖掘的搜索過程，其準確度很大程度取決于用戶輸入的關鍵詞的數量，以及搜索引擎對關鍵詞的語義的解析與用戶原意的吻合度，而搜索引擎對關鍵詞的解析，包括基于鏈接的聚類方法和基于概念的聚類方法。本文克服基于鏈接的聚類方法的缺陷，采用基于概念聚類的方法，從二分圖的概念和存儲方法入手，設計和實現了個性化的Web數據挖掘搜索引擎，并驗證了其優越性。

關鍵詞：二分圖；鄰接矩陣；聚類；數據挖掘；搜索引擎

中圖分類號：TP311.1 文獻標識碼：A

1 引言（Introduction）

眾所周知，關鍵詞數量越多，單個詞越能清晰表達查詢需求，搜索引擎就越能準確計算網頁相關度，用戶就越能準確得到所希望的查詢結果。然而絕大多數用戶在使用搜索引擎時，輸入的關鍵詞都少于三個，且很多情況下，關鍵詞不能正確表達用戶的查詢需求，使得查詢結果不盡如人意。本文采用概念聚類的方法，設計個性化搜索引擎，針對Web數據挖掘，能很大程度地提高搜索的準確率。

聚類就是將一個對象的集合通過某種算法分成幾個類，分類后不同的類中的對象是不相似的，同一個類中的對象是相似的[1]。查詢聚類是為了將相似需求的查詢表達式聚為一類，從中選取關鍵詞個數較多的作為這一類需求的表達，這樣對查詢表達式進行擴充，從而提高搜索的準確率[2]。

2 二分圖及其存儲（Bipartite graph and its storage）

設計中，聯合考慮關鍵詞和對應文本，即根據關鍵詞所形成的詞簇信息對文本進行聚類，聚類過程的數據結構定義如下：

定義1：設G=是一個無向圖，若存在V1∪V2=V，且V1∩V2=Φ使得E（V1，V2）=V1×V2，即E中每條邊的兩個端點都是一個屬于V1，另一個屬于V2，且對V1中任意x和V2中任意y，有一條邊e∈E，使e=（x，y），則稱G為完全二分圖。當|V1|=m，|V2|=n時，G記為Km，n。

對G采用實現存儲，設eij為邊[i，j]的權值，則記

（1）

為G的鄰接矩陣。

3 聚類算法（Clustering algorithm）

使用中的很多搜索引擎在計算查詢關鍵詞與網頁的相關度時，是根據網頁內包含關鍵詞的個數來定的，由于用戶輸入的關鍵詞比較短，且一般不超過三個，加上有的關鍵詞有歧義，而且由于網頁內容的多樣性，導致查詢到的網頁與用戶的需求存在較大的差距。除了可以采用錨文本來對網頁內容進行補充和描述的方法來提高查詢準確率外，另一種有效的方法就是利用用戶的點擊率作為網頁內容的補充了。從搜索引擎的日志中獲取的用戶點擊數據可以在一定程度上反應關鍵詞與頁面之間聯系，可以作為相關度計算的加權參數。

基于二分圖的聚類算法有兩種：基于超鏈接的聚類算法和基于概念的聚類算法。基于超鏈接的算法中，每當用戶點擊一個鏈接，就認為該鏈接和關鍵詞是相關的，認為只要兩個不同的關鍵詞有相同的鏈接就將兩個關鍵詞聚類在一起，這樣，由于關鍵詞的語義多樣性，很可能將語義不同的關鍵詞進行聚類，加上Internet上很少有相同的鏈接，兩個隨機關鍵詞被用戶選擇相同鏈接的概率僅為6.38*10-5，所以基于超鏈接的算法存在很大的缺陷[3]。

選擇采用基于概念的聚類算法，對于設計一個高準確率的Web數據挖掘的個性化的搜索引擎系統，能達到更好的效果。構造概念聚類的二分圖模型如下：

把所有的查詢構造成頂點向量集合Q，關鍵詞涉及的概念構造成頂點向量集合C，關鍵詞與概念之間的關系構造成邊集，即可得到概念聚類的二分圖模型如圖1所示。

例如當關鍵詞為apple ipad、apple、apple iphone時，涉及的概念則包括ipad、fruit、iphone、product，構造的概念二分圖如圖2所示。

conceptual clustering

根據二分圖，如果關鍵詞涉及的概念相互重疊得越多，則關鍵詞的相似度越高。設N（x）是節點x的鄰節點的集合，N（y）是節點y的鄰節點的集合，關鍵詞的相似度按如下公式計算：

（2）

由式（2）可以看出，兩個關鍵詞涉及的概念集的交集越大，則查詢的相似度越高。下面是構造二分圖算法的偽代碼：

4 系統模塊設計（The system module design）

本系統的設計目的，是設計和實現一個為用戶提供使用搜索引擎的平臺，為用戶提供搜索界面，并將用戶輸入的關鍵詞提交給搜索引擎，再將搜索引擎的搜索結果反饋給用戶。整個交互過程的數據比如查詢關鍵詞、搜索結果、用戶點擊的鏈接等數據都由該中間件收集起來并存儲，為下一步的用戶建模、查詢聚類做準備[4]。

系統由四個主要模塊組成：數據收集模塊、數據庫及管理模塊、用戶興趣模塊和查詢聚類模塊。系統流程分五步：數據收集、概念提取、用戶建模、查詢概念聚類、查詢優化。系統各個模塊的劃分和模塊之間數據傳遞方向如圖3所示。

5 結論（Conclusion）

模擬五個用戶，分別按表1輸入查詢關鍵詞。其中第一二用戶輸入的關鍵詞相同，但第一用戶的興趣點是apple數碼產品，而第二用戶的興趣點是apple水果。

實驗聚類結果如表2。結果表明，第一二用戶雖然查詢關鍵詞相同，但由于興趣點不同而被分到不同的類型中。類型0中的查詢結果都與數碼產品相關，而類型1中的結果都與水果相關，說明聚類結果能較好地按概念區分關鍵詞。

實驗表明，當聚類參數為0時，概念聚類的二分圖中，低相關度的關鍵詞被聚到一類，導致查準率比鏈接聚類查準率低；而當聚類參數較大時，概念聚類的查準率明顯高于鏈接聚類的查準率，平衡保持在較高的范圍內。

參考文獻（References）

[1] 吳湖，等.兩階段聯合聚類協同過濾算法[J].軟件學報，2010，

21（5）：1042-1054.

[2] 馬恩穹.基于Web數據挖掘的個性化搜索引擎研究[D].南京

理工大學，2012.

[3] Guandong Xu，Yanchun Zhang，LinLi.Web Content Mining[J].

Web Information Systems Engineering and Internet

Teehnologies，2011，6（2）：65-69.

[4] 王和勇，等.基于聚類和改進距離的LLE方法在數據降維中的

應用[J].計算機研究與發展，2006，43（8）：1485-1490.

作者簡介：

劉典型（1973-），男，碩士，副教授.研究領域：軟件，網絡

技術.

劉完芳（1972-），男，碩士，副教授.研究領域：數據庫.

鐘 鋼（1975-），男，本科，高級實驗師.研究領域：軟件

開發.