基于改進(jìn)粒子群優(yōu)化的文本聚類算法研究

王永貴,林 琳,劉憲國(guó)

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

基于改進(jìn)粒子群優(yōu)化的文本聚類算法研究

王永貴,林 琳,劉憲國(guó)

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

針對(duì)k-means算法的聚類結(jié)果高度依賴初始聚類中心選取的問題,提出一種基于改進(jìn)粒子群優(yōu)化的文本聚類算法。分析粒子群算法和k-means算法的特點(diǎn),針對(duì)粒子群算法搜索精度不高、易陷入局部最優(yōu)且早熟收斂的缺點(diǎn),設(shè)計(jì)自調(diào)節(jié)慣性權(quán)重機(jī)制及云變異算子以改進(jìn)粒子群算法。自調(diào)節(jié)慣性權(quán)重機(jī)制根據(jù)種群進(jìn)化程度,動(dòng)態(tài)地調(diào)節(jié)慣性權(quán)重,云變異算子基于云模型的隨機(jī)性和穩(wěn)定性,采用全局最優(yōu)值實(shí)現(xiàn)粒子的變異。該算法結(jié)合了粒子群算法較強(qiáng)的全局搜索能力與k-means算法較強(qiáng)的局部搜索能力。每個(gè)粒子是一組聚類中心,類內(nèi)離散度之和的倒數(shù)是適應(yīng)度函數(shù)。實(shí)驗(yàn)結(jié)果表明,該算法是一種精確而又穩(wěn)定的文本聚類算法。

粒子群優(yōu)化;自調(diào)節(jié)慣性權(quán)重機(jī)制;進(jìn)化程度;云變異算子;k-means算法;文本聚類

1 概述

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

文本聚類的方法多種多樣,其中,k-means算法簡(jiǎn)單、高效,是一種重要的文本聚類算法。但其對(duì)初始聚類中心選擇敏感,許多學(xué)者對(duì)k-means算法進(jìn)行改進(jìn)。文獻(xiàn)［2］通過對(duì)數(shù)據(jù)集進(jìn)行多次采樣和kmeans預(yù)聚類以產(chǎn)生多組不同的聚類結(jié)果,利用不同聚類結(jié)果的子簇之間存在的交集構(gòu)造出關(guān)于子簇的加權(quán)連通圖,并根據(jù)連通性合并子簇,提高聚類結(jié)果的質(zhì)量。文獻(xiàn)［3］利用混合Hausdorff距離作為相似測(cè)度實(shí)現(xiàn)數(shù)據(jù)聚類。文獻(xiàn)［4］運(yùn)用譜方法估計(jì)特征中心來(lái)初始化聚類中心。

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

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

2 文本表示

在聚類之前通常將文本轉(zhuǎn)化成易被計(jì)算機(jī)識(shí)別的形式,然后計(jì)算文本間的相似性,根據(jù)相似性將文本劃分成各個(gè)簇。

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

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

其中,ωki與ωkj分別為第k個(gè)文本特征在文本xi與xj的特征權(quán)值。

3 云理論

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

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

生成云滴的算法或硬件稱為云發(fā)生器［11］。下面對(duì)本文用到的基本云發(fā)生器的算法［12］進(jìn)行介紹。

基本云發(fā)生器算法的具體步驟:

Step 1 生成期望為En,標(biāo)準(zhǔn)差為He的正態(tài)隨機(jī)數(shù)En′。

Step 2 生成期望為Ex,標(biāo)準(zhǔn)差為En′的正態(tài)隨機(jī)數(shù)x。x為論域空間中的一個(gè)云滴。

Step 4 重復(fù)Step1～Step3,產(chǎn)生n個(gè)云滴。

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

PSO算法最初是受到鳥類捕食行為的啟發(fā),進(jìn)而利用群體智能建立的一個(gè)簡(jiǎn)化模型。該算法將每個(gè)個(gè)體抽象成解空間中的點(diǎn),具有位置和速度屬性。所有的粒子都有一個(gè)適應(yīng)度值,該值由目標(biāo)函數(shù)決定,以評(píng)價(jià)粒子位置的優(yōu)劣性。粒子通過跟蹤個(gè)體極值和全局極值來(lái)更新自己的速度和位置,其更新公式如式(3)和式(4)所示。

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

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

5 改進(jìn)的文本聚類算法設(shè)計(jì)

5.1 改進(jìn)的粒子群算法

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

5.1.1 自調(diào)節(jié)慣性權(quán)重機(jī)制

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

5.1.2 云變異算子

隨著迭代次數(shù)的增加,種群多樣性會(huì)逐漸減小,有可能發(fā)生早熟現(xiàn)象。因此,當(dāng)種群進(jìn)化到一定程度時(shí)對(duì)種群進(jìn)行變異操作以提高種群多樣性,從而避免陷入局部最優(yōu)?；谠频哪：院碗S機(jī)性,利用云的3個(gè)數(shù)字特征,即期望Ex,熵En,超熵He實(shí)現(xiàn)變異過程。

5.1.3 改進(jìn)的粒子群算法描述

下面給出改進(jìn)的粒子群算法的基本步驟。

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

Step 2 計(jì)算粒子適應(yīng)度值,比較各粒子適應(yīng)度值,更新個(gè)體極值與全局極值。

Step 3 判斷全局極值是否在規(guī)定代數(shù)內(nèi)沒有發(fā)生變化或達(dá)到變異閾值。如果是,則產(chǎn)生云變異算子,利用基本云發(fā)生器完成對(duì)所有粒子的云變異操作。否則,跳轉(zhuǎn)到Step4。

Step 4 采用自調(diào)節(jié)慣性權(quán)重機(jī)制,即按式(5)計(jì)算慣性權(quán)重ω。

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

Step 6 若達(dá)到最大進(jìn)化代數(shù),輸出全局最優(yōu)值,算法結(jié)束。否則,跳轉(zhuǎn)到Step2。

5.2 改進(jìn)的文本聚類算法原理

5.2.1 粒子編碼

現(xiàn)在大多數(shù)的粒子群聚類算法都采用實(shí)數(shù)或者浮點(diǎn)數(shù)的編碼方式,即維數(shù)為d的若干個(gè)文本組成的文本集合聚成k個(gè)類,每個(gè)粒子的位置是k×d維的向量,速度跟位置具有同樣的數(shù)據(jù)結(jié)構(gòu),所以粒子的速度也是k×d維的向量。其編碼方式如圖1所示。這種編碼方式相對(duì)復(fù)雜,個(gè)體結(jié)構(gòu)較長(zhǎng),必然會(huì)增加算法搜索的時(shí)間。

圖1 多數(shù)粒子群聚類算法的個(gè)體編碼結(jié)構(gòu)

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

圖2 本文算法的編碼結(jié)構(gòu)

5.2.2 適應(yīng)值函數(shù)

文本聚類的目標(biāo)是使各類內(nèi)文本距離之和的總值最小,本文使用歐氏距離進(jìn)行文本間相似性度量,將適應(yīng)度函數(shù)定義如下:

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

5.2.3 算法描述

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

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

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

Step 3 觀察全局極值是否在規(guī)定代數(shù)內(nèi)沒有發(fā)生變化,如果是,則生成云變異算子,對(duì)所有粒子進(jìn)行變異操作。否則,跳轉(zhuǎn)到Step4。

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

Step 5 判斷算法是否達(dá)到停止標(biāo)準(zhǔn),如果是,則跳轉(zhuǎn)到Step6,否則跳轉(zhuǎn)到Step2。

Step 6 輸出適應(yīng)度最大的粒子作為初始聚類中心,其對(duì)應(yīng)的k-means聚類結(jié)果為最終聚類結(jié)果。

該算法的基本原理是:將文本聚類中心按文本編號(hào)編碼成粒子個(gè)體,利用改進(jìn)的粒子群算法產(chǎn)生新的粒子,即新的聚類中心,再用k-means算法進(jìn)行優(yōu)化,如果種群陷入停滯狀態(tài),則生成云變異算子對(duì)種群進(jìn)行變異,重復(fù)此過程,直至結(jié)束,最終得到的最優(yōu)個(gè)體所對(duì)應(yīng)的k-means聚類結(jié)果為最終結(jié)果。該算法將改進(jìn)的粒子群算法的全局優(yōu)化能力與kmeans算法的高效性與局部搜索能力充分結(jié)合,從而快速準(zhǔn)確地找到初始聚類中心。

6 仿真實(shí)驗(yàn)與結(jié)果分析

6.1 實(shí)驗(yàn)參數(shù)設(shè)置

在自調(diào)節(jié)慣性權(quán)重機(jī)制中,k=0.3,控制參數(shù)i= 1。文獻(xiàn)［13］發(fā)現(xiàn)當(dāng)ωmax=0.95,ωmin=0.4時(shí),算法的性能會(huì)顯著提高,因此,取ωmax=0.95,ωmin=0.4。c1=c2=2.0。改進(jìn)的粒子群算法對(duì)比實(shí)驗(yàn)中,算法的終止條件是進(jìn)化代數(shù)達(dá)到50次。聚類實(shí)驗(yàn)中,算法的終止條件是整個(gè)種群平均適應(yīng)度值連續(xù)多代無(wú)明顯變化。

6.2 改進(jìn)的粒子群算法對(duì)比實(shí)驗(yàn)

本次實(shí)驗(yàn)采用以下3個(gè)經(jīng)典函數(shù)優(yōu)化問題(求解最小值)來(lái)測(cè)試算法性能。其中,Sphere函數(shù)是一個(gè)簡(jiǎn)單的單峰函數(shù),用以測(cè)試函數(shù)的精度;Griewank函數(shù)與Schaffer函數(shù)的全局極值點(diǎn)周圍包圍著很多局部極值點(diǎn),容易陷入局部最優(yōu),是難度較大的復(fù)雜優(yōu)化問題。

(1)Sphere函數(shù):

對(duì)于上述測(cè)試函數(shù)分別采用標(biāo)準(zhǔn)的粒子群算法(PSO)、混沌慣性權(quán)值調(diào)整策略的粒子群優(yōu)化算法(CIWPSO)［14］及本文改進(jìn)的粒子群算法進(jìn)行求解,種群規(guī)模為50。其中,PSO算法與本文改進(jìn)的粒子群算法參數(shù)按6.1節(jié)設(shè)置,CIWPSO采用文獻(xiàn)［14］的設(shè)置,c1=c2=1.5。實(shí)驗(yàn)結(jié)果如表1所示。

表1 3種算法的實(shí)驗(yàn)結(jié)果對(duì)比

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

6.3 實(shí)驗(yàn)與分析

實(shí)驗(yàn)1 算法穩(wěn)定性測(cè)試

在本次實(shí)驗(yàn)中,分別采用k-means算法、基本的PSO聚類算法、優(yōu)化的 PSO聚類算法、PSO+K-means算法與本文算法對(duì)源自騰訊網(wǎng)的150篇文檔(共5類,每類30篇)進(jìn)行聚類測(cè)試,每種運(yùn)行50次。測(cè)試結(jié)果如表2所示。

表2 算法穩(wěn)定性測(cè)試結(jié)果

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

實(shí)驗(yàn)2 算法精確度測(cè)試

本實(shí)驗(yàn)的數(shù)據(jù)集都來(lái)自于騰訊網(wǎng),每組數(shù)據(jù)集分別是關(guān)于娛樂、體育、時(shí)尚、新聞方面,其具體情況如表3所示。

表3 測(cè)試數(shù)據(jù)集

目前大多數(shù)聚類結(jié)果評(píng)價(jià)通常用F-measure來(lái)衡量,它是信息搜索領(lǐng)域中測(cè)試系統(tǒng)性能的常用指標(biāo),綜合了2個(gè)重要的概念——查準(zhǔn)率(precision)與查全率(recall),分別考察的是精確性與完備性。對(duì)于一個(gè)聚類i和主題類別j:

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

對(duì)于聚類結(jié)果來(lái)說,總的F-measure則由主題類別j的F-measure加權(quán)平均值得到:

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

基于實(shí)驗(yàn)1的實(shí)驗(yàn)結(jié)果,本次實(shí)驗(yàn)選擇各性能僅次于本文算法的PSO+k-means算法作比較。通過對(duì)數(shù)據(jù)集測(cè)試10次的總F-measure值的平均值評(píng)價(jià)聚類效果,實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 2種算法的F-measure值

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

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

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

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

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

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

［4］ 錢 線,黃萱菁,吳立德.初始化K-means的譜方法［J］.自動(dòng)化學(xué)報(bào),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］ 倪慶劍,長(zhǎng)志政,王蓁蓁.一種基于可變多簇結(jié)構(gòu)的動(dòng)態(tài)概率粒子群優(yōu)化算法［J］.軟件學(xué)報(bào),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］ 王守信,張 莉,李鶴松.一種基于云模型的主觀信任評(píng)價(jià)方法［J］.軟件學(xué)報(bào),2010,21(6):1343-1344.

［10］ 李海林,郭崇慧,邱望仁.正態(tài)云模型相似度計(jì)算方法［J］.電子學(xué)報(bào),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］ 戴朝華,朱云芳,陳維榮.云遺傳算法及其應(yīng)用［J］.電子學(xué)報(bào),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］ 吳秋波,王允誠(chéng),趙秋亮,等.混沌慣性權(quán)值調(diào)整策略的粒子群優(yōu)化算法［J］.計(jì)算機(jī)工程與應(yīng)用,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

國(guó)家自然科學(xué)基金資助項(xiàng)目(60903082);遼寧省教育廳基金資助項(xiàng)目(L2012113)。

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

2013-10-29

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

中文引用格式:王永貴,林 琳,劉憲國(guó).基于改進(jìn)粒子群優(yōu)化的文本聚類算法研究［J］.計(jì)算機(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.