基于K—means與FCA的網(wǎng)頁文本聚類算法的研究

朱正國

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

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

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

0 引言

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

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

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

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

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

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

K-means算法的思想如下：

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

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

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

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

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

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

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

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

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

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

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

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

4.1 FCA算法

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

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

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

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

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

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

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

6 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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

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

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

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