圖書館數(shù)字文本智能聚類個性化推薦應用研究

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

關鍵詞：文本聚類；K-means聚類；混合蟻群聚類算法；個性化推薦；語義相似度

中圖分類號：TP181；G251.4" 文獻標志碼：A

0 引言

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

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

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

1 K-means聚類和ACO

1.1 K-means聚類分析

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

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

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

1.2 ACO聚類分析

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

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

1.3 混合聚類

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

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

2.1 文本聚類

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

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

2.2 文本預處理

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

2.2.1 分詞

分詞是文本預處理的第一步。中文文本和英文文本不同，詞之間是沒有空格的，常用的表示方法是基于字、詞的特征表示。基于字特征的表示方法，其所需的存儲空間與運算速度遠遠優(yōu)于基于詞的特征表示 ［11］。

2.2.2 去停用詞

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

2.2.3 文本特征提取與特征項權重計算

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

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

Aii=1.3 名詞1.0 動詞

0.9 形容詞

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

文本i 的特征詞j的權重wij按照下式計算：

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

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

2.3 語義相似度計算方法

2.3.1 關鍵詞語義相似度計算

假如關鍵詞W1有n個義項，關鍵詞W2有m個義項，那它們的相似度Sim（W1，W2）公式如下：

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

這個義項的相似度就成為這2個關鍵詞的語義相似度［13］。

2.3.2 文本語義相似度的計算

利用文本提供的語義信息來計算文本相似度，就可以使在同一類中的文本相似度相對較高，不同類中的文本相似度相對較低，這樣就提升了文本聚類準確度。

例如，計算2篇文本：D1 （W11，W12，…，W1x）、 D2 （W21，W22，…，W2y）的語義相似度Sim（D1，D2），D1有x 個關鍵詞，D2有y個關鍵詞。計算時要以關鍵詞語義相似度為基礎，計算公式如下：

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

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

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

新算法運行步驟 ［14-15］如下。

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

（2）按照算法約定的計算規(guī)則，計算每個文本對象與聚類中心的語義相似度，找到語義相似度最大的聚類中心時，即對此文本進行歸類標識。

（3）對每個類中已標識的的文本重新計算新的聚類中心Cj （j=1，2，…，k）。即如果類內(nèi)某個文本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個聚類代表點。

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

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

（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）重新計算每個文本類中的新聚類中心。

（10）計算各個文本聚類的誤差偏離。

（11）計算ε總體誤差。

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

3 實驗測試

從知網(wǎng)、萬方等數(shù)據(jù)庫中下載1000篇數(shù)字文獻作為測試數(shù)據(jù)，將主題預先分為 5類，分別為經(jīng)濟類（200篇）、計算機類（200篇）、文學類（200篇）、政治類（200篇）、教育類（200篇）。利用查全率R、查準率P來評價算法的性能。

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

查準率P=（檢出的相關文獻數(shù)量/檢出的文獻總量）×100%

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

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

4 結(jié)語

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

參考文獻

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

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

［3］蔡坤.基于特證詞的文本聚類算法研究［D］.鄭州：河南大學，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］.長春：吉林大學，2009.

［6］楊新斌.孫京誥.黃道.一種進化聚類學習新方法［J］.計算機工程與應用，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］.計算機與數(shù)字工程，2011（6）：138-141.

［9］蔡元龍.模式識別［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］黃營.大規(guī)模中文文檔的檢索、分類于摘要研究［D］.上海：復旦大學，1999.

［12］顧益軍，樊孝忠，王建華，等.中文停用詞表的自動選?。跩］.北京理工大學學報，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］樓華峰.面向文本聚類的語義加權研究［D］.上海：上海交通大學，2010.

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

［16］高尚，楊靜宇.群智能算法及其應用［M］.北京：中國水利水電出版社，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