基于改進粒子群優化的文本聚類算法研究

王永貴,林 琳,劉憲國

(遼寧工程技術大學軟件學院,遼寧葫蘆島125105)

基于改進粒子群優化的文本聚類算法研究

王永貴,林 琳,劉憲國

(遼寧工程技術大學軟件學院,遼寧葫蘆島125105)

針對k-means算法的聚類結果高度依賴初始聚類中心選取的問題,提出一種基于改進粒子群優化的文本聚類算法。分析粒子群算法和k-means算法的特點,針對粒子群算法搜索精度不高、易陷入局部最優且早熟收斂的缺點,設計自調節慣性權重機制及云變異算子以改進粒子群算法。自調節慣性權重機制根據種群進化程度,動態地調節慣性權重,云變異算子基于云模型的隨機性和穩定性,采用全局最優值實現粒子的變異。該算法結合了粒子群算法較強的全局搜索能力與k-means算法較強的局部搜索能力。每個粒子是一組聚類中心,類內離散度之和的倒數是適應度函數。實驗結果表明,該算法是一種精確而又穩定的文本聚類算法。

粒子群優化;自調節慣性權重機制;進化程度;云變異算子;k-means算法;文本聚類

1 概述

文本信息量隨著互聯網不斷的發展日益膨脹,人們亟需對這些龐大而又復雜的文本信息進行高效的組織和整理,以便能有效地定位滿足用戶需求的信息,文本挖掘是解決這類問題的主要技術。聚類是數據挖掘、模式識別研究的重要內容之一［1］。文本聚類的目標是將文本劃分成若干個簇,使相同簇之間的內容相似度盡可能大,而不同簇之間的內容相似度盡可能小。

文本聚類的方法多種多樣,其中,k-means算法簡單、高效,是一種重要的文本聚類算法。但其對初始聚類中心選擇敏感,許多學者對k-means算法進行改進。文獻［2］通過對數據集進行多次采樣和kmeans預聚類以產生多組不同的聚類結果,利用不同聚類結果的子簇之間存在的交集構造出關于子簇的加權連通圖,并根據連通性合并子簇,提高聚類結果的質量。文獻［3］利用混合Hausdorff距離作為相似測度實現數據聚類。文獻［4］運用譜方法估計特征中心來初始化聚類中心。

粒子群優化 (Particle Swarm Optimization, PSO)［5］是一種源于對鳥類捕食行為模擬的重要群體智能算法。PSO初始化一群隨機粒子,即隨機解,然后通過迭代找到最優解。在每一次迭代中,粒子通過跟蹤個體極值和全局極值來更新自己的速度與位置。該算法具有較強的全局搜索能力且概念簡單,易于實現,作為一種有效的優化工具己被成功地應用到諸多工程領城［6］。但它自身也存在缺陷,在遇到局部極值時,粒子的速度迅速降低直到停滯,且很難跳出局部極值點,出現早熟現象,而慣性權重是粒子群算法一個重要參數,用以調節粒子群的搜索能力。

通過對k-means算法和粒子群優化的分析,本文提出一種基于改進粒子群優化的文本聚類算法。改進粒子群優化算法,增強其全局搜索能力、避免早熟收斂,并將改進后的粒子群算法與局部搜索能力較強的k-means算法相結合,以解決k-means算法對初始聚類中心選擇過分依賴的問題。

2 文本表示

在聚類之前通常將文本轉化成易被計算機識別的形式,然后計算文本間的相似性,根據相似性將文本劃分成各個簇。

文本聚類問題中常采用向量空間模型(Vector Space Model,VSM)［7］進行文本表示。該模型將每個文本表示成空間向量,特征詞作為文本的表示單位,向量的每一維是對應特征詞在該文本中的權值。即把文本集x表示成(x1,x2,…,xn),xi的向量空間表示為(ω1(xi),ω2(xi),…,ωm(xi))。其中,m表示特征項的數目;ωj(xi)表示第j個特征項在文本xi中的權值。計算特征項權值的方法有很多,一般選用TF*IDF算法［8］。

其中,tfij表示第 i個文本特征在文本 xj出現的次數;N為文檔總數;Ni為文本集合中出現第i個特征詞的文本數;分母為歸一化因子。文本相似度是衡量文本間相似程度大小的一個統計量,是文本聚類的一個主要依據,計算方法有余弦法、內積法、距離函數法等。本文選用距離函數法中的歐氏距離法:

其中,ωki與ωkj分別為第k個文本特征在文本xi與xj的特征權值。

3 云理論

設U是一個用精確數值表示的論域,A為U上對應著的定性概念,對于U中的任意一個元素x,都存在一個有穩定傾向的隨機數μA(x),記做y,y∈［0,1］,y就叫作x對概念A的確定度,x在U上的分布稱為云,記為 A(x,μ)。每一個 x稱為一個云滴［9］。

云的數字特征——期望Ex,熵En和超熵He,用于反映云要表達的定性概念A的整體特性。其中,期望Ex表示論域空間U中最能夠代表定性概念A的點,即這個概念量化的最典型樣本點;熵En表示熵是定性概念隨機性的度量,既反映了代表定性概念A的云滴出現的隨機程度,又反映了在論域空間U中可以被語言值A接受的云滴值范圍。超熵He表示超熵是熵的不確定性的度量,即熵的熵［10］。

生成云滴的算法或硬件稱為云發生器［11］。下面對本文用到的基本云發生器的算法［12］進行介紹。

基本云發生器算法的具體步驟:

Step 1 生成期望為En,標準差為He的正態隨機數En′。

Step 2 生成期望為Ex,標準差為En′的正態隨機數x。x為論域空間中的一個云滴。

Step 4 重復Step1～Step3,產生n個云滴。

4 粒子群算法與k-means算法

PSO算法最初是受到鳥類捕食行為的啟發,進而利用群體智能建立的一個簡化模型。該算法將每個個體抽象成解空間中的點,具有位置和速度屬性。所有的粒子都有一個適應度值,該值由目標函數決定,以評價粒子位置的優劣性。粒子通過跟蹤個體極值和全局極值來更新自己的速度和位置,其更新公式如式(3)和式(4)所示。

其中,zid為i個粒子的d維位置矢量;vid為粒子的飛行速度;pid為粒子迄今為止搜索的最優位置;pgd為整個粒子群迄今為止搜索的最優位置;ω為慣性權重,表示先前粒子的速度對當前速度的影響程度;r1和r2為［0,1］之間的隨機數;c1和c2為學習因子,也稱加速因子。粒子群算法具有較強的全局搜索能力,但它在優化過程初期收斂速度較快,易陷入局部極值,過早收斂。

k-means算法是一種典型的聚類算法,具有較強的局部搜索能力。假設將文本集合X中的n個文本分為m類。計算步驟為:選取m個文本作為初始聚類中心,計算每個文本到聚類中心的距離,將其劃分到離其最近的類中,計算每個類中文本的均值作為新的聚類中心,重復該過程直到聚類中心不發生變化。從上述步驟可以看出聚類中心的選取對結果有很大的影響。因此,合理選擇初始聚類中心是 kmeans算法的關鍵步驟。

5 改進的文本聚類算法設計

5.1 改進的粒子群算法

粒子群算法雖然簡單、易于實現,但它自身也存在缺陷,其局部搜索能力較差,搜索精度不高,后期容易陷入局部最優,失去粒子的多樣性,從而難以保證搜索到全局最優解。為優化粒子群算法,設計了自調節慣性權重機制和云變異算子,提高了算法的精度和收斂速度,保證能夠有效地搜索到全局最優值。

5.1.1 自調節慣性權重機制

慣性權重ω是粒子群算法中一個重要的參數。從粒子速度更新公式中可以看出,當ω較小時,vid接近全局極值與局部極值的可能性較大,有利于全局極值的收斂。這在后期是非常有利的,能夠加快算法的收斂性,快速向全局極值靠攏。但是在初期卻不然,因為初期應大力探索新的解空間,尋找更好的全局極值。ω較大時情況與之相反。因此,較大的ω值有利于全局搜索,較小的ω值有利于局部搜索。現在最常用的方法是線性遞減ω值,即先設置較大的ω值,增強粒子的全局搜索能力,隨著迭代次數的增加ω值線性遞減,最后局部搜索,得到精確極值。這樣做從一定程度上可以改善粒子的搜索能力,但還存在一定的缺陷:首先,ω減小的速度較快,可能極值點所在的解空間還沒搜索,就進行局部搜索了。其次,尋優初期可能找到極值點了,由于ω較大而跳過極值點。因此對ω值的調節不僅要依賴于迭代次數,還應依據整個群體的進化程度。為此,本文提出一種自調節慣性權重機制。

5.1.2 云變異算子

隨著迭代次數的增加,種群多樣性會逐漸減小,有可能發生早熟現象。因此,當種群進化到一定程度時對種群進行變異操作以提高種群多樣性,從而避免陷入局部最優。基于云的模糊性和隨機性,利用云的3個數字特征,即期望Ex,熵En,超熵He實現變異過程。

5.1.3 改進的粒子群算法描述

下面給出改進的粒子群算法的基本步驟。

Step 1 初始化種群。粒子的速度、位置、個體極值、全局極值等。

Step 2 計算粒子適應度值,比較各粒子適應度值,更新個體極值與全局極值。

Step 3 判斷全局極值是否在規定代數內沒有發生變化或達到變異閾值。如果是,則產生云變異算子,利用基本云發生器完成對所有粒子的云變異操作。否則,跳轉到Step4。

Step 4 采用自調節慣性權重機制,即按式(5)計算慣性權重ω。

Step 5 按式(3)、式(4)更新粒子的速度和位置。

Step 6 若達到最大進化代數,輸出全局最優值,算法結束。否則,跳轉到Step2。

5.2 改進的文本聚類算法原理

5.2.1 粒子編碼

現在大多數的粒子群聚類算法都采用實數或者浮點數的編碼方式,即維數為d的若干個文本組成的文本集合聚成k個類,每個粒子的位置是k×d維的向量,速度跟位置具有同樣的數據結構,所以粒子的速度也是k×d維的向量。其編碼方式如圖1所示。這種編碼方式相對復雜,個體結構較長,必然會增加算法搜索的時間。

圖1 多數粒子群聚類算法的個體編碼結構

本文提出了一種新的個體編碼方式,將文本集中N個文本編號,即1～N,用K個聚類中心在文本集中的編號代替聚類中心,其編碼結構如圖2所示。其中,Zi(i=1,2,…,K)是第i個聚類中心在文本集中對應的編號;Vi(i=1,2,…,K)是粒子的飛行速度。這種編碼方式不僅使粒子長度大大減小,還能保證聚類中心的搜索空間不會隨著粒子迭代次數的增加而增大,提高了算法的效率,是一種簡單、有效且易于理解的編碼方式。

圖2 本文算法的編碼結構

5.2.2 適應值函數

文本聚類的目標是使各類內文本距離之和的總值最小,本文使用歐氏距離進行文本間相似性度量,將適應度函數定義如下:

其中,K為聚類數目;Xi為類Cj中的文本;Bj為聚類中心,其實際意義是各類文本到其聚類中心距離的總和(即離散度之和)加1后求倒數,即為粒子的適應度值。這樣,粒子的適應度與離散度之和成負相關,離散度之和越小,粒子的適應度值越大。

5.2.3 算法描述

基于改進粒子群算法的文本聚類算法可以描述為:

Step 1 種群初始化。將文本集合中N個文本編碼為1～N,隨機選擇K個文本作為初始聚類中心,用文本編號作為粒子的位置編碼,并初始化粒子的速度。重復M次,生成種群數量為M的粒子群。

Step 2M個粒子采用 k-means算法分別對N個文本進行聚類劃分,并按式(6)計算粒子的適應度值。更新個體極值、全局極值。

Step 3 觀察全局極值是否在規定代數內沒有發生變化,如果是,則生成云變異算子,對所有粒子進行變異操作。否則,跳轉到Step4。

Step 4 按式(5)更新慣性權重。按式(3)、式(4)更新粒子的速度和位置。

Step 5 判斷算法是否達到停止標準,如果是,則跳轉到Step6,否則跳轉到Step2。

Step 6 輸出適應度最大的粒子作為初始聚類中心,其對應的k-means聚類結果為最終聚類結果。

該算法的基本原理是:將文本聚類中心按文本編號編碼成粒子個體,利用改進的粒子群算法產生新的粒子,即新的聚類中心,再用k-means算法進行優化,如果種群陷入停滯狀態,則生成云變異算子對種群進行變異,重復此過程,直至結束,最終得到的最優個體所對應的k-means聚類結果為最終結果。該算法將改進的粒子群算法的全局優化能力與kmeans算法的高效性與局部搜索能力充分結合,從而快速準確地找到初始聚類中心。

6 仿真實驗與結果分析

6.1 實驗參數設置

在自調節慣性權重機制中,k=0.3,控制參數i= 1。文獻［13］發現當ωmax=0.95,ωmin=0.4時,算法的性能會顯著提高,因此,取ωmax=0.95,ωmin=0.4。c1=c2=2.0。改進的粒子群算法對比實驗中,算法的終止條件是進化代數達到50次。聚類實驗中,算法的終止條件是整個種群平均適應度值連續多代無明顯變化。

6.2 改進的粒子群算法對比實驗

本次實驗采用以下3個經典函數優化問題(求解最小值)來測試算法性能。其中,Sphere函數是一個簡單的單峰函數,用以測試函數的精度;Griewank函數與Schaffer函數的全局極值點周圍包圍著很多局部極值點,容易陷入局部最優,是難度較大的復雜優化問題。

(1)Sphere函數:

對于上述測試函數分別采用標準的粒子群算法(PSO)、混沌慣性權值調整策略的粒子群優化算法(CIWPSO)［14］及本文改進的粒子群算法進行求解,種群規模為50。其中,PSO算法與本文改進的粒子群算法參數按6.1節設置,CIWPSO采用文獻［14］的設置,c1=c2=1.5。實驗結果如表1所示。

表1 3種算法的實驗結果對比

從表1可以看出,對于所有測試函數,改進的粒子群算法均表現出良好的性能。在Sphere函數上,本文改進的粒子群算法的平均值為0,即為精確的最優解,且方差也為0,表示本文改進的粒子群算法每次都能搜索到精確最優解。而在Griewank函數與Schaffer函數上,本文改進的粒子群算法則表現出更高的精確性和穩定性。以上數據表明,該算法具有良好的精確性和魯棒性。

6.3 實驗與分析

實驗1 算法穩定性測試

在本次實驗中,分別采用k-means算法、基本的PSO聚類算法、優化的 PSO聚類算法、PSO+K-means算法與本文算法對源自騰訊網的150篇文檔(共5類,每類30篇)進行聚類測試,每種運行50次。測試結果如表2所示。

表2 算法穩定性測試結果

從上述實驗結果可以看出,k-means算法的穩定性較差,原因在于其對初始聚類中心的依賴性較強。基本的PSO聚類算法和優化的PSO聚類算法在穩定性上有較大的提高且平均迭代次數也相對減小。PSO+k-means算法將兩者結合,雖然在穩定性和迭代次數上有較大的提高,但因其只是單純地將兩者結合,而沒有優化,其性能仍不如本文算法。本文將全局搜索能力較強的粒子群算法進行優化,防止其早熟收斂,再與局部搜索能力較強的k-means算法結合,無論是在迭代次數還是穩定性上都有著顯著的提高。在收斂概率上,本文算法達到了100%,即50次實驗中,每次都能得到最優解。

實驗2 算法精確度測試

本實驗的數據集都來自于騰訊網,每組數據集分別是關于娛樂、體育、時尚、新聞方面,其具體情況如表3所示。

表3 測試數據集

目前大多數聚類結果評價通常用F-measure來衡量,它是信息搜索領域中測試系統性能的常用指標,綜合了2個重要的概念——查準率(precision)與查全率(recall),分別考察的是精確性與完備性。對于一個聚類i和主題類別j:

其中,N1為在聚類i中但屬于主題類別j的文本數量;N2為聚類i中的文本數量;N3為主題類別j中的文本數量。主題類別j的F-measure定義為:

對于聚類結果來說,總的F-measure則由主題類別j的F-measure加權平均值得到:

其中,表示主題類j中所有文本的數量。

基于實驗1的實驗結果,本次實驗選擇各性能僅次于本文算法的PSO+k-means算法作比較。通過對數據集測試10次的總F-measure值的平均值評價聚類效果,實驗結果如圖3所示。

圖3 2種算法的F-measure值

觀察圖3,縱向來看,對于各數據集,本文算法的F-measure值都要高于PSO+k-means算法,約高出5個百分點 ～6個百分點。例如對數據集D4,用PSO+k-means算法聚類的F-measure值是0.577,但采用本文算法聚類后,F-measure值提高到了0.631。橫向來看,除了數據集D4,本文算法在其他3個數據集上的F-measure值都超過了0.67,而PSO+k-means算法在數據集D2上的F-measure值最高,為0.662。對于在數據集D4上F-measure值較低可能是因為數據集的選取引起的。整體來看,本文算法在聚類效果上有著顯著的優勢。

7 結束語

本文改進了粒子群優化算法,并將改進后的粒子群算法與k-means算法結合,充分發揮粒子群算法的全局優化能力與k-means算法的高效性和局部尋優能力,提出了基于改進粒子群算法的文本聚類算法。實驗結果證明,該算法具有較強的穩定性和較高的準確性,能夠產生較好的聚類效果。在改進的粒子群算法中,i的選取能有效地控制慣性權重ω的增加或減小的速度,合理的i值既能加快收斂速度,又能防止算法早熟。在基于改進粒子群算法的文本聚類算法中聚類算法是在聚類數確定的前提下執行的,而實際聚類問題中,聚類數是未知的。因此,對于控制參數i的選取以及如何優化聚類數目是下一步研究的重點。

［1］ 孫吉貴,劉 杰,趙連寧.聚類算法研究［J］.軟件學報,2008,19(1):48-61.

［2］ 雷小鋒,謝昆青,林 帆,等.一種基于K-means局部最優性的高效聚類算法［J］.軟件學報,2008,19(7): 1683-1692.

［3］ 謝紅薇,李曉亮.基于多示例的k-means聚類學習算法［J］.計算機工程,2010,36(17):179-181.

［4］ 錢 線,黃萱菁,吳立德.初始化K-means的譜方法［J］.自動化學報,2007,33(4):342-346.

［5］ Kennedy J,Eberhart R.Particle Swarm Optimization［C］//Proceedings of IEEE International Conference on Neural Networks.Piscataway,USA:IEEE Press,1995: 1942-1948.

［6］ 倪慶劍,長志政,王蓁蓁.一種基于可變多簇結構的動態概率粒子群優化算法［J］.軟件學報,2009,20(2): 339-349.

［7］ Salton G,Wong A,Yang C S.A Vector Space Model for Automatic Indexing［J］.Communications of the ACM, 1975,18(11):613-620.

［8］ Salton G,Buckley B.Term-weighting Approaches in Automatic Text Retrieval［J］.Information Processing and Management,1988,24(5):513-523.

［9］ 王守信,張 莉,李鶴松.一種基于云模型的主觀信任評價方法［J］.軟件學報,2010,21(6):1343-1344.

［10］ 李海林,郭崇慧,邱望仁.正態云模型相似度計算方法［J］.電子學報,2011,39(11):2561-2567.

［11］ Hu Changhua,SiXiaosheng,Yang Jianbo.System Reliability Prediction Model Based on Evidential Reasoning Algorithm with Nonlinear Optimization［J］.Expert Systems with Applications,2010,37(3):2550-2562.

［12］ 戴朝華,朱云芳,陳維榮.云遺傳算法及其應用［J］.電子學報,2007,35(7):1419-1424.

［13］ Shi Y,Eberhart R C.Empirical Study of Particle Swarm Optimization ［C］//Proceedings of Congress on Computational Intelligence.Washington D.C.,USA:［s.n.］,1999:1945-1950.

［14］ 吳秋波,王允誠,趙秋亮,等.混沌慣性權值調整策略的粒子群優化算法［J］.計算機工程與應用,2009, 45(7):49-51.

編輯 顧逸斐

Research on Text Clustering Algorithm Based on Improved Particle Swarm Optimization

WANG Yonggui,LIN Lin,LIU Xianguo
(College of Software,Liaoning Technical University,Huludao 125105,China)

Clustering result of k-means clustering algorithm is highly dependent on the choice of the initial cluster center.With regards to this,a text clustering algorithm based on improved Particle Swarm Optimization(PSO)is presented.Features of particle swarm algorithm and k-means algorithm are analysed.Considering the disadvantages of PSO including low solving precisions,high possibilities of being trapped in local optimization and premature convergence,self-regulating mechanism of inertia weight and cloud mutation operator are designed to improve PSO.Selfregulating mechanism of inertia weight adjusts the inertia weight dynamically according to the degree of the population evolution.Cloud mutation operator is based on stable tendency and randomness property of cloud model.The global best individual is used to complete mutation on particles.Those two algorithms are combined by taking advantages of power global search ability of PSO and strong capacity of local search of k-means.A particle is a group of clustering centers,and a sum of scatter within class is fitness function.Experimental results show that this algorithm is an accurate,efficient and stable text clustering algorithm.

Particle Swarm Optimization(PSO);self-regulating mechanism of inertia weight;degree of evolution; cloud mutation operator;k-means algorithm;text clustering

1000-3428(2014)11-0172-06

A

TP301.6

10.3969/j.issn.1000-3428.2014.11.034

國家自然科學基金資助項目(60903082);遼寧省教育廳基金資助項目(L2012113)。

王永貴(1967-),男,教授,主研方向:智能計算,云計算,數據挖掘;林 琳,碩士;劉憲國,講師。

2013-10-29

2013-12-19E-mail:lidypli@126.com

中文引用格式:王永貴,林 琳,劉憲國.基于改進粒子群優化的文本聚類算法研究［J］.計算機工程,2014,40(11):172-177.

英文引用格式:Wang Yonggui,Lin Lin,Liu Xianguo.Research on Text Clustering Algorithm Based on Improved Particle Swarm Optimization［J］.Computer Engineering,2014,40(11):172-177.