摘要：Web 2.0信息時(shí)代，信息量迅速增加，信息檢索速率卻顯著降低，如何提高信息的自動(dòng)分類管理水平，從海量數(shù)據(jù)中高效、準(zhǔn)確、快速獲取有價(jià)值的信息與知識(shí)成為智慧圖書館亟待研究與解決的問(wèn)題。文章提出了在數(shù)字圖書館服務(wù)中運(yùn)用新型文本聚類群智能分析方法。該算法通過(guò)改進(jìn)文本間的語(yǔ)義相似度計(jì)算，融合K-means聚類算法與蟻群聚類算法（Ant Colony Optimization， ACO）的優(yōu)點(diǎn)，在初始分類時(shí)將K-means聚類算法用作快速分類，用分類結(jié)果指導(dǎo)更新螞蟻各途徑信息素，指導(dǎo)螞蟻后續(xù)聚類途徑選擇，提高聚類運(yùn)行效率。該分析方法因?yàn)椴恍枰悇e的信息，能自動(dòng)完成文本分組，所以可以更好地應(yīng)用到圖書館資源的推薦與檢索服務(wù)中。圖書館數(shù)字文本數(shù)據(jù)庫(kù)實(shí)驗(yàn)證明，混合蟻群聚類算法比單獨(dú)的K-means、ACO都具有更好的聚類效果，可以看出該算法的有效性。

關(guān)鍵詞：文本聚類；K-means聚類；混合蟻群聚類算法；個(gè)性化推薦；語(yǔ)義相似度

中圖分類號(hào)：TP181；G251.4" 文獻(xiàn)標(biāo)志碼：A

0 引言

信息技術(shù)快速發(fā)展，信息與知識(shí)越來(lái)越多地以數(shù)字化形式如數(shù)字圖書館、新聞、信息倉(cāng)庫(kù)等，展現(xiàn)在人們面前。如何在大量信息中尋找到真正所需的信息成為亟待解決的問(wèn)題。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)應(yīng)運(yùn)而生，它是一種從大量數(shù)據(jù)中發(fā)現(xiàn)隱含在其中的知識(shí)或者聯(lián)系的過(guò)程與技術(shù)［1］。

文本挖掘［2］是數(shù)據(jù)挖掘的一個(gè)分支。通過(guò)對(duì)文本數(shù)據(jù)的挖掘與分析，發(fā)現(xiàn)文本數(shù)據(jù)倉(cāng)庫(kù)中某些文字的語(yǔ)法與描述內(nèi)容出現(xiàn)的規(guī)律與關(guān)聯(lián)。文本挖掘包括文本信息提取、文本分類、文本聚類、自動(dòng)文摘等技術(shù)［3］。

現(xiàn)實(shí)生活中為達(dá)到更好的分類聚類效果，人們可以借助各種聚類方法進(jìn)行文本分析。目前，模式識(shí)別研究領(lǐng)域常用的聚類算法有群智能聚類方法和K-means聚類方法等。K-means聚類算法速度快但精確度較低，初始聚類中心的準(zhǔn)確確定非常難，從而會(huì)過(guò)早地陷入局部最優(yōu)。群智能聚類方法中的ACO速度相對(duì)比較慢，但收斂精度較高。為此，本文將K-means聚類與ACO混合應(yīng)用于文本聚類中，初始化快速分類采用K-means聚類算法，重新更新各選擇路徑上的信息素，指導(dǎo)螞蟻后續(xù)歸屬類別的選擇。這樣操作，不僅能提高算法的精確度，還能進(jìn)一步提升整個(gè)算法的運(yùn)行效率。

1 K-means聚類和ACO

1.1 K-means聚類分析

K-means算法將一個(gè)特征空間分成k個(gè)簇 ［4］。此算法是通過(guò)設(shè)定的N次迭代運(yùn)行后，將數(shù)據(jù)對(duì)象歸類到它所屬的簇中。聚類運(yùn)算后，不同對(duì)象只要聚類在同一簇中，相似度非常高， 而在不同簇里的不同對(duì)象，相似度非常低。

K-means聚類算法是先從待檢集合中任選k個(gè)聚類中心。然后按照約定設(shè)計(jì)的計(jì)算方法，計(jì)算集合中的每個(gè)考察對(duì)象與每個(gè)聚類中心的相似度，找到與對(duì)象相似度值最高的聚類中心，將對(duì)象歸屬于其中。最后根據(jù)聚類結(jié)果，重新計(jì)算出新一輪聚類中心，若k個(gè)聚類中心都沒(méi)有變化，說(shuō)明算法收斂，可輸出聚類結(jié)果。

K-means聚類算法簡(jiǎn)單并且時(shí)間復(fù)雜度小，但對(duì)于類別數(shù)量k值的選定非常難以估計(jì)，k個(gè)聚類中心的初始劃分不同，結(jié)果也不一樣［5］。因此，K-means聚類算法的精度就會(huì)下降。

1.2 ACO聚類分析

ACO是一種進(jìn)化算法。ACO經(jīng)常在應(yīng)用組合優(yōu)化問(wèn)題中。算法模擬每只螞蟻在候選解空間中獨(dú)立地搜索解，在整個(gè)協(xié)作過(guò)程中，留下選擇的信息素，后續(xù)螞蟻依照信息素值越高就越容易被選中的原則進(jìn)行類別選擇。蟻群聚類不僅更容易找到數(shù)據(jù)的本質(zhì)信息，而且具有良好的抗噪聲能力。因此，如果想解決更貼近現(xiàn)實(shí)的聚類問(wèn)題，使用蟻群模型更適合［6］。

全局優(yōu)化啟發(fā)式蟻群算法是根據(jù)各個(gè)聚類中心的信息數(shù)值，融合歸并周圍的文本數(shù)據(jù)，實(shí)現(xiàn)聚類［7］。本文將待聚類的數(shù)據(jù)看作不同屬性的螞蟻，將螞蟻要尋覓的食物來(lái)源視作每一個(gè)聚類中心。假設(shè)輸入樣本為X={ Xi i =1， 2， ...，m} ， Xi =（ xi1 ， xi2 ， ...， xin）。算法中將蟻群從蟻巢出發(fā)去尋找食物的過(guò)程，就定為聚類中心確定的過(guò)程。

1.3 混合聚類

初始時(shí)，各路徑的信息素取值是相同的，這樣就可以在等概率的情況下進(jìn)行類別選擇。但是ACO很難在短時(shí)間內(nèi)從大量類別中找出更好的歸屬。針對(duì)此問(wèn)題，本文結(jié)合K-means算法的收斂速度快、ACO的準(zhǔn)確率高等特點(diǎn)，混合2種算法并對(duì)其進(jìn)行改進(jìn)［8-10］ 。

2 新型混合群智能文本聚類

2.1 文本聚類

文本聚類是指無(wú)需額外的類別信息，就可以完成文本分組。它是典型的無(wú)指導(dǎo)學(xué)習(xí)過(guò)程。文本聚類可以幫助找到最相似的文本集，提高信息檢索系統(tǒng)的查全率與查準(zhǔn)率。文本檢索系統(tǒng)聚類的評(píng)判準(zhǔn)則是：同一文本組里的文本相似度要盡可能大，不同文本組里的文本相似度要盡可能小。文本聚類處理過(guò)程如圖1所示。

用戶進(jìn)行信息查詢與檢索時(shí)，如果信息管理系統(tǒng)能夠自動(dòng)聚類分類處理檢索到的文本信息，用戶就可以對(duì)自己所需的信息實(shí)現(xiàn)快速定位，從而極大地提升信息檢索的查準(zhǔn)率和查全率。智能管理系統(tǒng)可以對(duì)用戶曾經(jīng)檢索的感興趣的文本進(jìn)行自動(dòng)智能聚類，從而挖掘用戶的興趣模式，主動(dòng)將用戶需要的資源與信息推薦給用戶，實(shí)現(xiàn)個(gè)性化服務(wù)。

2.2 文本預(yù)處理

文本預(yù)處理過(guò)程包括分詞、去停用詞和特征提取。文本預(yù)處理可以將人類自然語(yǔ)言轉(zhuǎn)化成特征信息，使計(jì)算機(jī)能夠理解。每次預(yù)處理后，每篇文本都將由多個(gè)特征詞來(lái)表示。

2.2.1 分詞

分詞是文本預(yù)處理的第一步。中文文本和英文文本不同，詞之間是沒(méi)有空格的，常用的表示方法是基于字、詞的特征表示?；谧痔卣鞯谋硎痉椒?，其所需的存儲(chǔ)空間與運(yùn)算速度遠(yuǎn)遠(yuǎn)優(yōu)于基于詞的特征表示 ［11］。

2.2.2 去停用詞

停用詞是指在文本中頻繁出現(xiàn)，但對(duì)文本識(shí)別影響不大的單詞。如中文的“我、你、他、的、了、呀”等。這些詞是出于語(yǔ)法的需要，對(duì)文本的內(nèi)容貢獻(xiàn)不大。通過(guò)建立停用詞表來(lái)過(guò)濾掉干擾文本聚類分類的無(wú)用詞［12］。

2.2.3 文本特征提取與特征項(xiàng)權(quán)重計(jì)算

文本特征提取是指在文本聚類精度不降低的條件下，通過(guò)壓縮待處理的特征項(xiàng)，來(lái)降低空間維數(shù)，提高聚類速度和整體效率，同時(shí)減少算法計(jì)算量。在聚類精度方面，通過(guò)數(shù)學(xué)算法提取出最具類別信息的特征，更適合文本聚類系統(tǒng)的應(yīng)用。

在漢語(yǔ)語(yǔ)法中，由主、謂、賓、定、補(bǔ)、狀等組成一個(gè)句子。主語(yǔ)和賓語(yǔ)主要為名詞，謂語(yǔ)一般為動(dòng)詞，定語(yǔ)更多為形容詞和副詞。如果為不同的詞性標(biāo)識(shí)合理的權(quán)重值來(lái)參與計(jì)算，可以幫助文本特征提取。假設(shè)Aii為詞性的權(quán)重系數(shù)，Bii為不同位置詞語(yǔ)的權(quán)重系數(shù) ［13］：

Aii=1.3 名詞1.0 動(dòng)詞

0.9 形容詞

0.8 副詞"""" Bii=1.5 標(biāo)題1.0 內(nèi)容

文本i 的特征詞j的權(quán)重wij按照下式計(jì)算：

wij=TFij*IDFi*Aii*Bii（1）

其中，TFij為標(biāo)識(shí)詞語(yǔ)描述文本內(nèi)容的能力，表示特征詞 j 在文本 i 中的詞頻；IDFi為詞語(yǔ)區(qū)分文本的能力；TFij*IDFi是一種有效的詞重計(jì)算方法，當(dāng)一個(gè)詞IDF值很小并且TF值很大時(shí)，即標(biāo)識(shí)它對(duì)該文本內(nèi)容的描述能力大，如果該詞在其他文本中以非常小的概率出現(xiàn)時(shí)，則證明在文本區(qū)分識(shí)別上該詞具有較強(qiáng)的能力 ［12］。

2.3 語(yǔ)義相似度計(jì)算方法

2.3.1 關(guān)鍵詞語(yǔ)義相似度計(jì)算

假如關(guān)鍵詞W1有n個(gè)義項(xiàng)，關(guān)鍵詞W2有m個(gè)義項(xiàng)，那它們的相似度Sim（W1，W2）公式如下：

Sim（W1，W2）=maxi=1，2，...，n，j=1，2，...，mSim（W1i，W2j）（2）

這個(gè)義項(xiàng)的相似度就成為這2個(gè)關(guān)鍵詞的語(yǔ)義相似度［13］。

2.3.2 文本語(yǔ)義相似度的計(jì)算

利用文本提供的語(yǔ)義信息來(lái)計(jì)算文本相似度，就可以使在同一類中的文本相似度相對(duì)較高，不同類中的文本相似度相對(duì)較低，這樣就提升了文本聚類準(zhǔn)確度。

例如，計(jì)算2篇文本：D1 （W11，W12，…，W1x）、 D2 （W21，W22，…，W2y）的語(yǔ)義相似度Sim（D1，D2），D1有x 個(gè)關(guān)鍵詞，D2有y個(gè)關(guān)鍵詞。計(jì)算時(shí)要以關(guān)鍵詞語(yǔ)義相似度為基礎(chǔ)，計(jì)算公式如下：

Sim（D1，D2）=1xy∑i=1，2，...，x;j=1，2，...，ySim（W1i，W2j）（3）

2.4 新型群智能混合文本聚類算法

結(jié)合K-means與ACO算法的優(yōu)勢(shì)，本文提出一種融合2種算法的新算法。首先利用K-means對(duì)待檢文本集合進(jìn)行快速分類。待初步分類后，用ACO對(duì)初步分類結(jié)果進(jìn)行啟發(fā)式迭代，直至聚類結(jié)果的最終輸出。新算法中的K-means算法的分類容易收斂，所以聚類準(zhǔn)確率不是很高，但運(yùn)行速度較快。所以，對(duì)K-means的分類結(jié)果可以用ACO進(jìn)行迭代，K-means初始聚類中心極大地降低了ACO初始時(shí)定位聚類中心的隨機(jī)性，降低了算法的時(shí)間復(fù)雜度。

新算法運(yùn)行步驟 ［14-15］如下。

（1）在待檢文本集合中，隨機(jī)任選k個(gè)初始聚類中心C1， C2， …， Ck 。

（2）按照算法約定的計(jì)算規(guī)則，計(jì)算每個(gè)文本對(duì)象與聚類中心的語(yǔ)義相似度，找到語(yǔ)義相似度最大的聚類中心時(shí)，即對(duì)此文本進(jìn)行歸類標(biāo)識(shí)。

（3）對(duì)每個(gè)類中已標(biāo)識(shí)的的文本重新計(jì)算新的聚類中心Cj （j=1，2，…，k）。即如果類內(nèi)某個(gè)文本Di的AVE_C_Sim（Di， Sj），與類內(nèi)文本間的平均相似度AVE_Sim（Sj）之差最小，那么文本Di即為新的聚類中心。

AVE_C_Sim（Di，Sj）=1Nj-1∑Di，Dl∈Sj，Di≠DlSim（Di，Dl）（4）

其中，Nj為類Sj中的文本數(shù)量。

（4）若 C′j≠Cj （j = 1， 2， …，k ）， 轉(zhuǎn)至步驟（2）; 否則算法收斂， 輸出聚類結(jié)果。

（5）K-means文本聚類結(jié)果作為蟻群文本聚類初始的k個(gè)聚類代表點(diǎn)。

（6）設(shè)定參數(shù)，如信息素濃度初始化等。若Di文本歸于聚類中心Sj（j=1，2，…，k），則Di文本和Sj聚類中心歸屬選擇的信息素濃度τij為：τij=τij（0）+QSim（Di，Sj），

式中τij（0）（i， j=1，2，…，k）為信息素的初始濃度值，均設(shè)為Q（一個(gè)正的常數(shù)）， 迭代次數(shù)NC也為一個(gè)常數(shù) ，Sim（Di，Sj）即為文本對(duì)象Di與聚類中心Sj的語(yǔ)義相似度。

（7）蟻群文本聚類隨信息素的更新而不斷變化，信息素更新方程為：

τnewij=（1-ρ）τoldij+QSim（Di，Sj）

其中，ρ為信息素殘留系數(shù)，一般取0.50～0.99。

第i只螞蟻選擇聚類中心Sj的概率即為：

pij=τij∑Kj=1τij（5）

（8）如果 Pij （t）≥P0 ， 則Di 歸于Sj鄰域中。

（9）重新計(jì)算每個(gè)文本類中的新聚類中心。

（10）計(jì)算各個(gè)文本聚類的誤差偏離。

（11）計(jì)算ε總體誤差。

（12）計(jì)算ε≤ε0，判斷若成立則停止并輸出文本聚類結(jié)果；否則轉(zhuǎn)至步驟（6）繼續(xù)迭代。實(shí)現(xiàn)流程如圖2所示。

3 實(shí)驗(yàn)測(cè)試

從知網(wǎng)、萬(wàn)方等數(shù)據(jù)庫(kù)中下載1000篇數(shù)字文獻(xiàn)作為測(cè)試數(shù)據(jù)，將主題預(yù)先分為 5類，分別為經(jīng)濟(jì)類（200篇）、計(jì)算機(jī)類（200篇）、文學(xué)類（200篇）、政治類（200篇）、教育類（200篇）。利用查全率R、查準(zhǔn)率P來(lái)評(píng)價(jià)算法的性能。

查全率R=（檢出的相關(guān)文獻(xiàn)數(shù)量/系統(tǒng)中相關(guān)文獻(xiàn)總數(shù)）×100%

查準(zhǔn)率P=（檢出的相關(guān)文獻(xiàn)數(shù)量/檢出的文獻(xiàn)總量）×100%

分別用基于語(yǔ)義相似度的K-means 文本聚類算法、蟻群文本聚類算法和群智能混合文本聚類算法來(lái)檢測(cè)測(cè)試文檔的聚類查準(zhǔn)率P和查全率R，結(jié)果如表1和表2所示。本文算法參數(shù)為 ρ=0.9，Q=80，迭代次數(shù)NC=100，螞蟻數(shù)目R=30。

基于語(yǔ)義相似度的混合聚類算法的運(yùn)行性能之所以能高于2個(gè)單個(gè)聚類算法，在于混合算法中利用了ACO和K-means聚類2個(gè)算法的優(yōu)勢(shì)互補(bǔ)，ACO不斷優(yōu)化調(diào)整了K-means聚類算法的初步聚類結(jié)果，最終得到更好的聚類效果［16］。

4 結(jié)語(yǔ)

本文基于K-means聚類和ACO的聚類劃分思路，進(jìn)一步研究了文本聚類問(wèn)題，實(shí)現(xiàn)了新型的文本智能聚類。在算法實(shí)現(xiàn)過(guò)程中，先用K-means算法對(duì)初始聚類中心實(shí)現(xiàn)自動(dòng)快速確定，再利用ACO進(jìn)行文本精確搜索。蟻群混合聚類算法充分發(fā)揮了聚類準(zhǔn)確、收斂速度快的優(yōu)點(diǎn)。此算法可以用于高校圖書館讀者個(gè)性化推薦服務(wù)中。圖書館是高校師生的主要知識(shí)數(shù)據(jù)庫(kù)來(lái)源，資源相當(dāng)廣泛。為此，高校師生要在海量的信息資源中找到自己所需要的資源比較困難。準(zhǔn)確而高效的優(yōu)化資源結(jié)構(gòu)對(duì)師生的學(xué)習(xí)與研究變得相當(dāng)重要。本文的混合群智能文本聚類算法可以從讀者借閱與下載的頻率、類別和關(guān)鍵詞的智能分析中輔助圖書管理系統(tǒng)獲取讀者喜好的信息，個(gè)性化推薦相對(duì)應(yīng)的圖書與其他數(shù)字資源［17］。本文利用ACO對(duì)經(jīng)典的K-means算法進(jìn)行改進(jìn)，使得聚類算法結(jié)果更加合理有針對(duì)性。

參考文獻(xiàn)

［1］JIAWEI H. MICHELINE K.Data mining concepts and techniques［M］.北京：機(jī)械工業(yè)出版社，2007.

［2］鄭繼剛，王邊疆.數(shù)據(jù)挖掘研究的現(xiàn)狀與發(fā)展趨勢(shì)［J］.紅河學(xué)院學(xué)報(bào)，2010（2）：46-48.

［3］蔡坤.基于特證詞的文本聚類算法研究［D］.鄭州：河南大學(xué)，2011.

［4］KANUNGO T， MOUNT D M， NETANYAHU N S. An efficient K-means clustering algorithm; analysis and implementation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence， 2002（7）： 881-892.

［5］劉玉璽.群智能算法在分割聚類中的研究［D］.長(zhǎng)春：吉林大學(xué)，2009.

［6］楊新斌.孫京誥.黃道.一種進(jìn)化聚類學(xué)習(xí)新方法［J］.計(jì)算機(jī)工程與應(yīng)用，2003（15）：60-62.

［7］CHU S C， RODDICK J F， PAN J S.Ant colony system with communication strategies［J］. Information Science，2004 （1）：63-76.

［8］江新姿，高尚.基于K-均值與蟻群混合聚類的圖像分割［J］.計(jì)算機(jī)與數(shù)字工程，2011（6）：138-141.

［9］蔡元龍.模式識(shí)別［M］.西安：西北電訊工業(yè)出版社，1986.

［10］AGRAWAL R，SRIKANT R. Fast algorithms for mining association rules［C］// Proceedings of the Twentieth International Conference on Very Large Databases. Santiago，Chile，1994： 487-499.

［11］黃營(yíng).大規(guī)模中文文檔的檢索、分類于摘要研究［D］.上海：復(fù)旦大學(xué)，1999.

［12］顧益軍，樊孝忠，王建華，等.中文停用詞表的自動(dòng)選?。跩］.北京理工大學(xué)學(xué)報(bào)，2005（4）：337-340.

［13］YAAKOV H K， ZURIEL G， ASAF M. Automatic extraction and learning of keyphrases from scientific articles［C］// In Proc of 6th International Conference on Computational Linguistics and Intelligent Text Processing，2005，657-669.

［14］樓華峰.面向文本聚類的語(yǔ)義加權(quán)研究［D］.上海：上海交通大學(xué)，2010.

［15］陶紅.基于語(yǔ)義相似度的群智能文本聚類方法研究［D］.鎮(zhèn)江：江蘇科技大學(xué)，2012.

［16］高尚，楊靜宇.群智能算法及其應(yīng)用［M］.北京：中國(guó)水利水電出版社，2006.

［17］SALTON G. The transformation analysis and retrival of information by compute ［M］. Massachusetts：Addison-Wesley Reading，1989.

（編輯 王雪芬編輯）

Research on the application of intelligent clustering and personalized recommendation

of digital text in libraries

JIANG" Xinzi1， GAO" Shang2

（1.Library of Jiangsu University of Science and Technology， Zhenjiang 212004， China;

2.School of Computer Science， Jiangsu University of Science and Technology， Zhenjiang 212004， China）

Abstract：" In the era of Web 2.0 information， the amount of information is rapidly increasing， but the speed of information retrieval is significantly decreasing. How to improve the automatic classification management of information and efficiently， accurately， and quickly obtain valuable information and knowledge from massive data has become an urgent problem for smart libraries to research and solve. The article proposes the application of a new text clustering group intelligent analysis method in digital library services. This algorithm improves the calculation of semantic similarity between texts， integrates the advantages of K-means clustering algorithm and ant colony clustering algorithm， and uses K-means algorithm for fast classification in the initial classification. The classification results guide the updating of pheromones in various ant pathways， guide the selection of subsequent clustering paths for ants， and improve the efficiency of clustering operation. Due to the fact that this analysis method does not require category information and can automatically complete text grouping， it can be better applied to the recommendation and retrieval services of library resources. Through experiments on digital text databases in libraries， it has been proven that the hybrid ant colony clustering algorithm has better clustering performance than individual K-means and ACO， indicating the effectiveness of the algorithm.

Key words： text clustering; K-means clustering; hybrid ant colony clustering algorithm; personalized recommendations; semantic similarity