劉典型等

摘 要：針對(duì)Web數(shù)據(jù)挖掘的搜索過(guò)程，其準(zhǔn)確度很大程度取決于用戶輸入的關(guān)鍵詞的數(shù)量，以及搜索引擎對(duì)關(guān)鍵詞的語(yǔ)義的解析與用戶原意的吻合度，而搜索引擎對(duì)關(guān)鍵詞的解析，包括基于鏈接的聚類方法和基于概念的聚類方法。本文克服基于鏈接的聚類方法的缺陷，采用基于概念聚類的方法，從二分圖的概念和存儲(chǔ)方法入手，設(shè)計(jì)和實(shí)現(xiàn)了個(gè)性化的Web數(shù)據(jù)挖掘搜索引擎，并驗(yàn)證了其優(yōu)越性。

關(guān)鍵詞：二分圖；鄰接矩陣；聚類；數(shù)據(jù)挖掘；搜索引擎

中圖分類號(hào)：TP311.1 文獻(xiàn)標(biāo)識(shí)碼：A

1 引言（Introduction）

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

聚類就是將一個(gè)對(duì)象的集合通過(guò)某種算法分成幾個(gè)類，分類后不同的類中的對(duì)象是不相似的，同一個(gè)類中的對(duì)象是相似的[1]。查詢聚類是為了將相似需求的查詢表達(dá)式聚為一類，從中選取關(guān)鍵詞個(gè)數(shù)較多的作為這一類需求的表達(dá)，這樣對(duì)查詢表達(dá)式進(jìn)行擴(kuò)充，從而提高搜索的準(zhǔn)確率[2]。

2 二分圖及其存儲(chǔ)（Bipartite graph and its storage）

設(shè)計(jì)中，聯(lián)合考慮關(guān)鍵詞和對(duì)應(yīng)文本，即根據(jù)關(guān)鍵詞所形成的詞簇信息對(duì)文本進(jìn)行聚類，聚類過(guò)程的數(shù)據(jù)結(jié)構(gòu)定義如下：

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

對(duì)G采用實(shí)現(xiàn)存儲(chǔ)，設(shè)eij為邊[i，j]的權(quán)值，則記

（1）

為G的鄰接矩陣。

3 聚類算法（Clustering algorithm）

使用中的很多搜索引擎在計(jì)算查詢關(guān)鍵詞與網(wǎng)頁(yè)的相關(guān)度時(shí)，是根據(jù)網(wǎng)頁(yè)內(nèi)包含關(guān)鍵詞的個(gè)數(shù)來(lái)定的，由于用戶輸入的關(guān)鍵詞比較短，且一般不超過(guò)三個(gè)，加上有的關(guān)鍵詞有歧義，而且由于網(wǎng)頁(yè)內(nèi)容的多樣性，導(dǎo)致查詢到的網(wǎng)頁(yè)與用戶的需求存在較大的差距。除了可以采用錨文本來(lái)對(duì)網(wǎng)頁(yè)內(nèi)容進(jìn)行補(bǔ)充和描述的方法來(lái)提高查詢準(zhǔn)確率外，另一種有效的方法就是利用用戶的點(diǎn)擊率作為網(wǎng)頁(yè)內(nèi)容的補(bǔ)充了。從搜索引擎的日志中獲取的用戶點(diǎn)擊數(shù)據(jù)可以在一定程度上反應(yīng)關(guān)鍵詞與頁(yè)面之間聯(lián)系，可以作為相關(guān)度計(jì)算的加權(quán)參數(shù)。

基于二分圖的聚類算法有兩種：基于超鏈接的聚類算法和基于概念的聚類算法?；诔溄拥乃惴ㄖ校慨?dāng)用戶點(diǎn)擊一個(gè)鏈接，就認(rèn)為該鏈接和關(guān)鍵詞是相關(guān)的，認(rèn)為只要兩個(gè)不同的關(guān)鍵詞有相同的鏈接就將兩個(gè)關(guān)鍵詞聚類在一起，這樣，由于關(guān)鍵詞的語(yǔ)義多樣性，很可能將語(yǔ)義不同的關(guān)鍵詞進(jìn)行聚類，加上Internet上很少有相同的鏈接，兩個(gè)隨機(jī)關(guān)鍵詞被用戶選擇相同鏈接的概率僅為6.38*10-5，所以基于超鏈接的算法存在很大的缺陷[3]。

選擇采用基于概念的聚類算法，對(duì)于設(shè)計(jì)一個(gè)高準(zhǔn)確率的Web數(shù)據(jù)挖掘的個(gè)性化的搜索引擎系統(tǒng)，能達(dá)到更好的效果。構(gòu)造概念聚類的二分圖模型如下：

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

例如當(dāng)關(guān)鍵詞為apple ipad、apple、apple iphone時(shí)，涉及的概念則包括ipad、fruit、iphone、product，構(gòu)造的概念二分圖如圖2所示。

conceptual clustering

根據(jù)二分圖，如果關(guān)鍵詞涉及的概念相互重疊得越多，則關(guān)鍵詞的相似度越高。設(shè)N（x）是節(jié)點(diǎn)x的鄰節(jié)點(diǎn)的集合，N（y）是節(jié)點(diǎn)y的鄰節(jié)點(diǎn)的集合，關(guān)鍵詞的相似度按如下公式計(jì)算：

（2）

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

4 系統(tǒng)模塊設(shè)計(jì)（The system module design）

本系統(tǒng)的設(shè)計(jì)目的，是設(shè)計(jì)和實(shí)現(xiàn)一個(gè)為用戶提供使用搜索引擎的平臺(tái)，為用戶提供搜索界面，并將用戶輸入的關(guān)鍵詞提交給搜索引擎，再將搜索引擎的搜索結(jié)果反饋給用戶。整個(gè)交互過(guò)程的數(shù)據(jù)比如查詢關(guān)鍵詞、搜索結(jié)果、用戶點(diǎn)擊的鏈接等數(shù)據(jù)都由該中間件收集起來(lái)并存儲(chǔ)，為下一步的用戶建模、查詢聚類做準(zhǔn)備[4]。

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

5 結(jié)論（Conclusion）

模擬五個(gè)用戶，分別按表1輸入查詢關(guān)鍵詞。其中第一二用戶輸入的關(guān)鍵詞相同，但第一用戶的興趣點(diǎn)是apple數(shù)碼產(chǎn)品，而第二用戶的興趣點(diǎn)是apple水果。

實(shí)驗(yàn)聚類結(jié)果如表2。結(jié)果表明，第一二用戶雖然查詢關(guān)鍵詞相同，但由于興趣點(diǎn)不同而被分到不同的類型中。類型0中的查詢結(jié)果都與數(shù)碼產(chǎn)品相關(guān)，而類型1中的結(jié)果都與水果相關(guān)，說(shuō)明聚類結(jié)果能較好地按概念區(qū)分關(guān)鍵詞。

實(shí)驗(yàn)表明，當(dāng)聚類參數(shù)為0時(shí)，概念聚類的二分圖中，低相關(guān)度的關(guān)鍵詞被聚到一類，導(dǎo)致查準(zhǔn)率比鏈接聚類查準(zhǔn)率低；而當(dāng)聚類參數(shù)較大時(shí)，概念聚類的查準(zhǔn)率明顯高于鏈接聚類的查準(zhǔn)率，平衡保持在較高的范圍內(nèi)。

參考文獻(xiàn)（References）

[1] 吳湖，等.兩階段聯(lián)合聚類協(xié)同過(guò)濾算法[J].軟件學(xué)報(bào)，2010，

21（5）：1042-1054.

[2] 馬恩穹.基于Web數(shù)據(jù)挖掘的個(gè)性化搜索引擎研究[D].南京

理工大學(xué)，2012.

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

Web Information Systems Engineering and Internet

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

[4] 王和勇，等.基于聚類和改進(jìn)距離的LLE方法在數(shù)據(jù)降維中的

應(yīng)用[J].計(jì)算機(jī)研究與發(fā)展，2006，43（8）：1485-1490.

作者簡(jiǎn)介：

劉典型（1973-），男，碩士，副教授.研究領(lǐng)域：軟件，網(wǎng)絡(luò)

技術(shù).

劉完芳（1972-），男，碩士，副教授.研究領(lǐng)域：數(shù)據(jù)庫(kù).

鐘 鋼（1975-），男，本科，高級(jí)實(shí)驗(yàn)師.研究領(lǐng)域：軟件

開(kāi)發(fā).