朱正國(guó)

摘 要： 搜索引擎針對(duì)某個(gè)查詢(xún)條件返回給用戶的查詢(xún)結(jié)果可能數(shù)量非常巨大，要從這么多的返回信息中找到所需要的信息是很困難的。研究聚類(lèi)算法是為了幫助用戶更好地查詢(xún)到自己所需要的和感興趣的信息。提出采用基于K-means與FCA的網(wǎng)頁(yè)文本聚類(lèi)算法，并分析了兩種算法各自的優(yōu)勢(shì)與缺點(diǎn)，為研究更優(yōu)的網(wǎng)頁(yè)文本聚類(lèi)算法提供依據(jù)。

關(guān)鍵詞： 聚類(lèi)算法； 搜索引擎； K-means； FCA

中圖分類(lèi)號(hào)：TP312 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2013）09-43-02

0 引言

隨著互聯(lián)網(wǎng)的普及，人們對(duì)互聯(lián)網(wǎng)的依賴(lài)程度提高，網(wǎng)絡(luò)成為人們獲取信息的一個(gè)重要的途徑。當(dāng)我們想查閱資料的時(shí)候就可以打開(kāi)搜索引擎輸入所要搜索的關(guān)鍵字。但是目前很多信息是保存在文本文件中的，這就降低了搜索查詢(xún)的速度。由此，人們開(kāi)始對(duì)文本聚類(lèi)、信息過(guò)濾和信息檢索等算法進(jìn)行大量的研究。文本聚類(lèi)技術(shù)可以將大量文本信息組成少數(shù)有意義的簇，能夠提供導(dǎo)航/瀏覽機(jī)制，進(jìn)而來(lái)改善檢索性能，因此，聚類(lèi)技術(shù)已成為搜索引擎中信息檢索過(guò)程中對(duì)文本信息檢索的核心技術(shù)。本文針對(duì)當(dāng)前兩種重要聚類(lèi)算法K-means和FCA的進(jìn)行研究，并將其用于網(wǎng)頁(yè)的聚類(lèi)中。

1 網(wǎng)頁(yè)文本聚類(lèi)系統(tǒng)的研究現(xiàn)狀

文本聚類(lèi)（Text clustering）文檔聚類(lèi)主要是依據(jù)著名的聚類(lèi)假設(shè)：同類(lèi)的文檔相似度較大，而不同類(lèi)的文檔相似度較小。作為一種無(wú)監(jiān)督的機(jī)器學(xué)習(xí)方法，聚類(lèi)由于不需要訓(xùn)練過(guò)程，以及不需要預(yù)先對(duì)文檔手工標(biāo)注類(lèi)別，因此具有一定的靈活性和較高的自動(dòng)化處理能力，已經(jīng)成為對(duì)文本信息進(jìn)行有效地組織、摘要和導(dǎo)航的重要手段，為越來(lái)越多的研究人員所關(guān)注。

目前，應(yīng)用較多的聚類(lèi)算法主要有劃分法、層次法、基于密度的方法、基于網(wǎng)格的方法、基于模型的方法。

2 基于K-means網(wǎng)頁(yè)文本聚類(lèi)算法研究

K-means算法是比較典型的聚類(lèi)算法[4-5]，它的主要特點(diǎn)就是基于距離聚類(lèi)，它是基于劃分的思想。

K-means算法的思想如下：

給定一個(gè)有N個(gè)元組或者記錄的數(shù)據(jù)集，分裂法將構(gòu)造K個(gè)分組，每一個(gè)分組就代表一個(gè)聚類(lèi)，K

3 K-means算法實(shí)現(xiàn)

實(shí)現(xiàn)聚類(lèi)的詳細(xì)步驟如下：

⑴ 處理文本集，隨機(jī)得到K值，從n個(gè)數(shù)據(jù)對(duì)象任意選擇k個(gè)對(duì)象作為初始聚類(lèi)中心；

⑵ 根據(jù)每個(gè)聚類(lèi)對(duì)象的均值（中心對(duì)象），計(jì)算每個(gè)對(duì)象與這些中心對(duì)象的距離，并根據(jù)最小距離重新對(duì)相應(yīng)對(duì)象進(jìn)行劃分；

⑶ 對(duì)于每一個(gè)文本對(duì)象向量，重新計(jì)算該文本對(duì)象與K個(gè)簇中心的相似度，選擇相似度最大的簇將該對(duì)象文本加入該簇，同時(shí)，將該文本對(duì)象從其他簇中去除，達(dá)到對(duì)簇的整體調(diào)整；

⑷ 重新計(jì)算每個(gè)（有變化）聚類(lèi)的均值（中心對(duì)象）；重新計(jì)算調(diào)整后的K個(gè)簇的中心，而不是使用簇內(nèi)所有文本對(duì)象向量的簡(jiǎn)單算術(shù)平均；

⑸ 計(jì)算標(biāo)準(zhǔn)測(cè)度函數(shù)，當(dāng)滿足一定條件，如函數(shù)收斂時(shí)，則算法終止；如果條件不滿足則回到步驟⑵；若文本集合中的文本對(duì)象都被聚類(lèi)完畢，則進(jìn)入⑹，否則返回到⑵繼續(xù)執(zhí)行計(jì)算中心；

⑹ 按照預(yù)定規(guī)則輸出聚類(lèi)結(jié)果，算法結(jié)束。

根據(jù)上述算法進(jìn)行了程序設(shè)計(jì)，K-means算法系統(tǒng)數(shù)據(jù)實(shí)現(xiàn)如圖1所示。

本系統(tǒng)采用了K=12的聚類(lèi)，根據(jù)K-means算法聚成了12個(gè)類(lèi)，這個(gè)聚類(lèi)是以攀枝花的詞頻“0.002892637”為中心點(diǎn)分散開(kāi)的。本程序?qū)?2個(gè)文本數(shù)據(jù)進(jìn)行聚類(lèi)，當(dāng)K=12的時(shí)候，平均分為12個(gè)類(lèi)，每個(gè)類(lèi)分別由6個(gè)文檔構(gòu)成。

4 基于FCA 網(wǎng)頁(yè)文本聚類(lèi)算法研究

4.1 FCA算法

形式概念分析（Formal Concept Analysis，F(xiàn)CA）是Wille提出的一種從形式背景進(jìn)行數(shù)據(jù)分析和規(guī)則提取的強(qiáng)有力工具，形式概念分析建立在數(shù)學(xué)基礎(chǔ)之上，對(duì)組成本體的概念、屬性以及關(guān)系等用形式化的語(yǔ)境表述出來(lái)，然后根據(jù)語(yǔ)境，構(gòu)造出概念格（concept lattice），即本體，從而清楚地表達(dá)出本體的結(jié)構(gòu)。在形式概念分析中，概念的外延被理解為屬于這個(gè)概念的對(duì)象的集合，而內(nèi)涵則被認(rèn)為是所有這些對(duì)象所共有的特征或?qū)傩约?，這實(shí)現(xiàn)了對(duì)概念的哲學(xué)理解的形式化。所有的概念連同它們之間的泛化/例化關(guān)系構(gòu)成一個(gè)概念格。

定義1 一個(gè)形式背景K=（G，M，I）由兩個(gè)集合G和M以及G，M之間的關(guān)系I?GXM組成，G中的元素被稱(chēng)為形式背景的對(duì)象，M中的元素被稱(chēng)為形式背景的屬性，若gIm或者（g，m）∈I，則表示“對(duì)象g有屬性m”。

定義2 假定給定一個(gè)形式背景一個(gè)形式背景K=（G，M，I），其中G為對(duì)象集合，M為屬性集合，I為它們之間的一個(gè)二元關(guān)系，則存在一個(gè)偏序集合與之對(duì)應(yīng)，并且這個(gè)偏序集合產(chǎn)生一種格結(jié)構(gòu)，這種由形式背景（G，M，I）所誘導(dǎo)的格L就稱(chēng)為一個(gè)概念格。格L中的每一個(gè)節(jié)點(diǎn)是一個(gè)序偶（即概念）記為（X，X'），其中X∈G稱(chēng)為概念的外延，X'∈M稱(chēng)為概念的內(nèi)涵。序偶（X，X'）關(guān)于關(guān)系R是完備的，即有性質(zhì)：

X'={x'∈M|?x∈X，xRx'} ⑴

X={x∈G|?x'∈X'，xRx'} ⑵

在概念格節(jié)點(diǎn)之間能夠建立一種偏序關(guān)系，給定C1=（X1，X'1）和C2（X2，X'2），那么C1

4.2 FCA算法實(shí)現(xiàn)

本文通過(guò)切詞分詞算法，計(jì)算出關(guān)鍵詞在文本中的權(quán)重，通過(guò)關(guān)鍵詞在文本中的權(quán)重得到了關(guān)鍵詞集，我們稱(chēng)作數(shù)據(jù)集。通過(guò)對(duì)已經(jīng)獲得的數(shù)據(jù)集里的詞集進(jìn)行分類(lèi)，獲得新的詞集，所得出的聚類(lèi)結(jié)果如圖2所示，結(jié)果前面的數(shù)字代表文本的編號(hào)。

5 K-means算法與FCA算法的實(shí)驗(yàn)對(duì)比

在實(shí)驗(yàn)過(guò)程中運(yùn)行的機(jī)器是一臺(tái)PC機(jī)，配有CPU Intel Pentium（雙核），內(nèi)存2GB，硬盤(pán)160G，所運(yùn)行的操作系統(tǒng)為Windows XP SP3。

在上述實(shí)驗(yàn)中發(fā)現(xiàn)，K-means算法程序運(yùn)行時(shí)間明顯比FCA算法運(yùn)行時(shí)間短，但是FCA算法準(zhǔn)確率高一些；使用概念格提高了準(zhǔn)確率，由于FCA算法較復(fù)雜，所以運(yùn)行時(shí)間明顯比K-means算法程序運(yùn)行時(shí)間長(zhǎng)；由于K-means算法較簡(jiǎn)單，所以節(jié)省了運(yùn)行時(shí)間。

6 結(jié)束語(yǔ)

目前越來(lái)越多的用戶喜歡用搜索引擎查詢(xún)資料，為了幫助用戶快速查找所需要的內(nèi)容，本文通過(guò)研究與分析認(rèn)為，K-means與FCA算法適合作為搜索引擎的算法，而且有各自的優(yōu)點(diǎn)和缺點(diǎn)，通過(guò)利用這兩種算法的優(yōu)點(diǎn)可以方便用戶獲得自己所需要的信息，為今后提供更優(yōu)的網(wǎng)頁(yè)文本聚類(lèi)算法提供依據(jù)。

參考文獻(xiàn)：

[1] 韓曉紅，胡彧.K-means聚類(lèi)算法的研究[J].太原理工大學(xué)學(xué)報(bào)，2009.40（3）：236-239

[2] 袁方，周志勇，宋鑫.初始聚類(lèi)中心優(yōu)化的k-means算法[J]. 計(jì)算機(jī)工程，2007.33（3）：65-66

[3] 毛韶陽(yáng)，李肯立.優(yōu)化K-means初始聚類(lèi)中心研究[J].計(jì)算機(jī)工程與應(yīng)用，2007.43（22）：179-181

[4] 孫吉貴，劉杰，趙連宇.聚類(lèi)算法研究[J].軟件學(xué)報(bào)，2008.19（1）：48-61

[5] 徐義峰，陳春明，徐云青.一種改進(jìn)的k-均值聚類(lèi)算法[J].計(jì)算機(jī)應(yīng)用與軟件，2008.25（3）：275-277

[6] 陳俊，吳紹春，盛春健.基于概念格的聚類(lèi)分析[J].上海大學(xué)學(xué)報(bào)（自然科學(xué)版），2008.14（4）：432-435

[7] 唐明珠，張遠(yuǎn)平，楊佳.概念相似度在文本模糊聚類(lèi)中的應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì)，2008.29（3）：745-747