基于花粉算法的K均值聚類算法

張 姣,王曉東,薛 紅

(西安工程大學(xué) 理學(xué)院,陜西 西安 710048)

基于花粉算法的K均值聚類算法

張 姣,王曉東,薛 紅

(西安工程大學(xué) 理學(xué)院,陜西 西安 710048)

針對(duì)原始花粉算法尋優(yōu)精度低,后期收斂速度慢等問(wèn)題,提出加入高斯白噪聲擾動(dòng)改進(jìn)花粉算法．利用改進(jìn)后花粉算法強(qiáng)大的全局搜索能力優(yōu)化K-means算法的初始聚類中心,通過(guò)基于距離的方法消弱孤立點(diǎn)對(duì)聚類的影響,并對(duì)該算法的性能進(jìn)行驗(yàn)證和測(cè)試.實(shí)驗(yàn)結(jié)果表明該算法有效地避免了其陷入局部最優(yōu),改善了聚類性能．

K均值聚類;花粉算法;初始聚類中心

0 引 言

聚類分析是數(shù)據(jù)挖掘的一種非常重要的方法,K-means算法是一個(gè)基于劃分且應(yīng)用非常廣泛的聚類算法[1],但它的初始聚類中心的選擇決定了K-means算法的劃分結(jié)果,若選取不當(dāng),可能會(huì)導(dǎo)致算法陷入局部最優(yōu)解．很多學(xué)者對(duì)該問(wèn)題進(jìn)行了研究與改進(jìn),如文獻(xiàn)[2]利用云模型云滴的隨機(jī)性和穩(wěn)定趨向性設(shè)計(jì)遺傳算法的交叉和變異概率,并與K均值結(jié)合,有效提高收斂速度和聚類能力;文獻(xiàn)[3]通過(guò)動(dòng)態(tài)調(diào)整粒子的慣性權(quán)重系數(shù)及飛行時(shí)間增強(qiáng)了粒子群的全局搜索能力,消除K-means算法聚類結(jié)果對(duì)初始聚類中心的依賴性;文獻(xiàn)[4]利用改進(jìn)后的人工蜂群算法與K均值算法結(jié)合改善聚類性能;文獻(xiàn)[5]提出基于最優(yōu)類中心擾動(dòng)的螢火蟲(chóng)聚類算法,提高算法的聚類效果;文獻(xiàn)[6]將改進(jìn)的差分進(jìn)化算法和K-means聚類算法相結(jié)合,有效提高聚類結(jié)果的質(zhì)量和穩(wěn)定性;文獻(xiàn)[7]將自適應(yīng)策略用于人工魚(yú)群算法的改進(jìn)中,與K均值算法融合,避免陷入局部最優(yōu),提高收斂速度．但數(shù)據(jù)集中常常會(huì)因一些人為因素或固有數(shù)據(jù)變異而存在孤立點(diǎn),孤立點(diǎn)有時(shí)會(huì)隱藏一些重要的信息,上述文獻(xiàn)雖然都有效地提高了算法的聚類能力,但均未考慮孤立點(diǎn)對(duì)聚類結(jié)果的影響.本文考慮用最近鄰距離差的檢測(cè)算法[8]檢測(cè)孤立點(diǎn),用馬氏距離再將孤立點(diǎn)重新歸類的方法減弱孤立點(diǎn)對(duì)聚類的影響．另外,為了避免K-means算法陷入局部最優(yōu)解,用花粉算法(FPA)搜尋K-means算法的初始聚類中心,但花粉算法的花粉配子在過(guò)于集中時(shí),算法易陷入局部極值,收斂速度緩慢,因此為了使得花粉算法在陷入局部最優(yōu)時(shí)能重新獲得解的多樣性,跳出局部極值,考慮將高斯白噪聲擾動(dòng)加入到花粉算法中．而且高斯白噪聲擾動(dòng)已被成功地加入到粒子群[9]、布谷鳥(niǎo)[10]、蝙蝠[11]等優(yōu)化算法中,有效提高了算法的全局搜索能力．最后驗(yàn)證了改進(jìn)后K-means算法的有效性．

1 相關(guān)算法

1.1 K-means算法

K-means 算法是由McQueen在 1967 年提出的,它是聚類分析中最常用一種典型的劃分算法,其目標(biāo)是將數(shù)據(jù)根據(jù)某種相似性度量方法進(jìn)行劃分,使每個(gè)數(shù)據(jù)到所屬簇類中心的距離盡可能小,不同簇類間的距離盡可能大．由于該算法具有簡(jiǎn)單、容易理解、效率較高,并且適用于大數(shù)據(jù)集的優(yōu)點(diǎn)而被廣泛應(yīng)用.其算法的步驟為:(1) 從待操作的數(shù)據(jù)集里面隨機(jī)選擇k個(gè)初始聚類中心點(diǎn)；(2) 逐個(gè)計(jì)算每個(gè)數(shù)據(jù)對(duì)象到各個(gè)聚類中心點(diǎn)的距離,然后分配給距離最短的集合；(3) 重新計(jì)算每個(gè)劃分的中心點(diǎn)坐標(biāo)并更新產(chǎn)生新的劃分；(4) 判斷是否滿足停止條件,若滿足則輸出聚類結(jié)果,否則轉(zhuǎn)至步驟(2)．其中,相似性度量采用歐幾里得距離計(jì)算方法,聚類中心為類內(nèi)所有數(shù)據(jù)對(duì)象的均值．

1.2 花粉算法

花粉算法是英國(guó)劍橋大學(xué)學(xué)者Yang于2012年提出一種新型元啟發(fā)式群智能優(yōu)化算法[12-13]．由于該算法實(shí)現(xiàn)簡(jiǎn)單、參數(shù)少、易調(diào)節(jié),能較好地解決全局搜索和局部搜索的平衡問(wèn)題,且同時(shí)采用了Levy飛行機(jī)制,使其具有良好的全局尋優(yōu)能力．花粉算法使用有四條規(guī)則[14-15]:

(1) 生物異花授粉是帶花粉的傳粉者以式(1)進(jìn)行全局授粉過(guò)程,其中L服從式(2);

(2) 非生物自花授粉是按照式(3)進(jìn)行局部授粉過(guò)程;

(3) 花恒?？梢员徽J(rèn)為是正比于某兩朵相似性的繁殖概率；

(4) 轉(zhuǎn)換概率p∈[0，1]控制全局授粉和局部授粉之間的轉(zhuǎn)換,p對(duì)局部授粉影響大．

(1)

(2)

(3)

1.3 改進(jìn)的花粉算法

花粉算法雖已在函數(shù)優(yōu)化[16]、文本聚類[17]、電力系統(tǒng)[18]等應(yīng)用領(lǐng)域取得了較好的成效,但也存在易陷入局部極值且后期收斂速度慢等缺陷,使其應(yīng)用范圍受到限制．為了保證算法跳出局部最優(yōu),考慮在花粉配子過(guò)分集中的時(shí)候?qū)⒎N群分散,在當(dāng)前最優(yōu)解gbest附近進(jìn)行高斯白噪聲擾動(dòng)以增加解的多樣性,即作以下改進(jìn):

gbestd=gbestd+0.1randn(1,S).

(4)

其中,randn(1,S)為產(chǎn)生正態(tài)分布的高斯白噪聲;S=size(gbestd,1),gbestd表示全局最優(yōu)解的第d維．

為了檢驗(yàn)高斯白噪聲擾動(dòng)改進(jìn)花粉算法(GFPA)的全局搜索能力,用4個(gè)測(cè)試函數(shù)對(duì)FPA和GFPA算法進(jìn)行對(duì)比實(shí)驗(yàn),測(cè)試函數(shù)見(jiàn)表1,測(cè)試函數(shù)最優(yōu)解位置與2種算法搜索到的最優(yōu)解的位置見(jiàn)表2，測(cè)試函數(shù)電優(yōu)解與算法搜索到的最優(yōu)解間的距離見(jiàn)表3.其中D1和D2分別表示FPA算法和GFPA算法搜索到的最優(yōu)解的位置與測(cè)試函數(shù)最優(yōu)解的位置的距離．

表 1 測(cè)試函數(shù)

表 2 測(cè)試函數(shù)最優(yōu)解位置與2種算法搜索到的最優(yōu)解位置

表 3 2種算法搜索到的最優(yōu)解位置與測(cè)試函數(shù)最優(yōu)解位置的距離

由表2和3可知對(duì)于測(cè)試函數(shù)1,(1,3)為測(cè)試函數(shù)全局最優(yōu)解的位置,FPA算法搜索到的全局最優(yōu)解的位置為(1.8,2),而GFPA算法搜索到全局最優(yōu)解的位置為(1.7,2.4),(1.7,2.4) 到(1,3)之間的距離為1.280 6,比 (1.8,2) 到(1,3)之間的距離小,說(shuō)明GFPA算法搜索到最優(yōu)解位置更接近于測(cè)試函數(shù)全局最優(yōu)解位置;同理對(duì)于測(cè)試函數(shù)2,3,4,從D1-D2這項(xiàng)都大于0說(shuō)明對(duì)于有單個(gè)或多個(gè)最優(yōu)解的測(cè)試函數(shù),GFPA算法搜索到最優(yōu)解位置更接近于測(cè)試函數(shù)全局最優(yōu)解位置,說(shuō)明GFPA算法優(yōu)于FPA算法,有更強(qiáng)大的全局搜索能力．

2 基于改進(jìn)FPA的K-means聚類算法

2.1 基于距離的孤立點(diǎn)檢測(cè)與處理

數(shù)據(jù)集中常常會(huì)因一些人為因素或固有數(shù)據(jù)變異而存在孤立點(diǎn),且孤立點(diǎn)有時(shí)會(huì)隱藏一些重要的信息,若直接排除,會(huì)造成重要信息的丟失．為了使K均值算法免受孤立點(diǎn)的影響,考慮用最近鄰距離差的檢測(cè)算法[8]檢測(cè)孤立點(diǎn),計(jì)算數(shù)據(jù)集中所有數(shù)據(jù)對(duì)象兩兩之間的歐氏距離的平方,按升序排列得N*N的矩陣D,選取第k個(gè)最近鄰距離完成對(duì)所有數(shù)據(jù)對(duì)象的降序排列和排在前n0位數(shù)據(jù)對(duì)象的選取,計(jì)算選出對(duì)象的相鄰距離差得到閾半徑maxΔD;并取得計(jì)算D矩陣的每一行小于閾半徑的距離數(shù)目和其位置各為一列,按降序組成N*2矩陣Num,將Num矩陣相鄰兩行第一列元素兩兩相除,得到最大比值的除數(shù)C,作為密集度閾值;找出Num矩陣中第一列元素小于C的所有數(shù)據(jù)對(duì)象,即強(qiáng)孤立點(diǎn)．根據(jù)需要再設(shè)置較大的密集度閾值可找出弱孤立點(diǎn)．

利用該方法對(duì)本文的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行孤立點(diǎn)檢測(cè),兩組數(shù)據(jù)檢測(cè)出來(lái)的孤立點(diǎn)為:(-0.516 5,2.609 5),(-0.679 1,-1.257 8),(2.377 5,1.805 1),(0.608 4,2.533 4),(0.712 6,2.208 3),(-0.088 1,1.242 9),(-1.143 3,0.132 1),(0.738 3,1.265 2,0.785 1),(0.912 0,1.580 2,1.805 0),(0.619 9,1.457 7,1.151 8),(2.254 5,1.040 3,1.235 0),(-0.379 4,2.749 1,-0.421 1),(2.059 7,1.568 2,1.660 8). 再將孤立點(diǎn)到聚類中心以馬氏距離最小原則重新歸類,消弱聚類對(duì)孤立點(diǎn)的敏感,改善無(wú)監(jiān)督聚類的結(jié)果．

2.2 GFPA-Kmeans算法

利用改進(jìn)后的花粉算法搜索K-means全局最優(yōu)的初始聚類中心,再用基于距離的方法檢測(cè)并將孤立點(diǎn)歸類．由均值-標(biāo)準(zhǔn)差來(lái)決定初始聚類中心,即初始解．

假設(shè)所有數(shù)據(jù)的均值為μ,標(biāo)準(zhǔn)差為σ,分類個(gè)數(shù)為K,設(shè)第i類的初始分類中心為mi,則

(5)

若參與分類的是d維數(shù)據(jù),設(shè)第i類聚類初始中心值為(mi1,mi2,…,mid),則

(6)

GFPA-Kmeans聚類算法的步驟如下:

Step 1 對(duì)種群的n個(gè)花粉配子進(jìn)行初始化,定義轉(zhuǎn)移概率p∈[0,1],最大迭代次數(shù)Tmax.從數(shù)據(jù)集X中隨機(jī)選擇K個(gè)中心點(diǎn),將其作為花粉配子xi的初值,找出此時(shí)目標(biāo)函數(shù)最優(yōu)解g.

Step 2 執(zhí)行FPA算法進(jìn)行迭代搜索對(duì)FPA中的每個(gè)花粉配子進(jìn)行以下操作:

(1) 隨機(jī)產(chǎn)生一個(gè)隨機(jī)數(shù)rand,若rand

(2) 若全局最優(yōu)解連續(xù)若干代沒(méi)有得到提升,按照式(4)對(duì)其進(jìn)行高斯白噪聲擾動(dòng)以產(chǎn)生新的全局最優(yōu)解,計(jì)算花粉配子的適應(yīng)度值．

(3) 由均值-標(biāo)準(zhǔn)差決定初始聚類中心,按照式(5)或式(6)計(jì)算更新聚類中心．

(4) pre-u是上一次求得的聚類中心位置,u為當(dāng)前得到的聚類中心位置,規(guī)定‖pre-u-u‖<0.001為判斷準(zhǔn)則．

Step 3 若通過(guò)準(zhǔn)則判斷花粉配子已趨向收斂或者循環(huán)達(dá)到最大迭代次數(shù)Tmax,終止花粉算法的迭代并將gbest對(duì)應(yīng)的花粉配子作為K個(gè)初始聚類中心,否則轉(zhuǎn)Step 2繼續(xù)迭代執(zhí)行．

Step 4 執(zhí)行K-means算法,指定閾半徑maxΔD和密集度閾值C,找出Num矩陣中第一列元素小于C的所有數(shù)據(jù)對(duì)象,即強(qiáng)孤立點(diǎn),根據(jù)需要設(shè)置較大的密集度閾值可找出弱孤立點(diǎn),并存儲(chǔ)．否則依照最近鄰原則劃分?jǐn)?shù)據(jù)集．

Step 5 以馬氏距離最小原則重新歸類孤立點(diǎn)到聚類中心,按類輸出最終的聚類結(jié)果．

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

為了驗(yàn)證GFPA-Kmeans算法的有效性,隨機(jī)100次取樣,運(yùn)算后取平均值．實(shí)驗(yàn)環(huán)境為:操作系統(tǒng)Windows 7,Intel Core3CPU 2.20GHz,內(nèi)存2GB,編譯軟件為Matlab 7.11.0.實(shí)驗(yàn)中算法的各個(gè)參數(shù)分別為:花粉的種群規(guī)模大小m=20,最大迭代次Tmax=100,轉(zhuǎn)移概率p=0.8,K=3．每組由3個(gè)小數(shù)據(jù)集組合而成,其中每個(gè)小數(shù)據(jù)集服從不同均值和協(xié)方差的高斯分布．第一組為300個(gè)二維數(shù)據(jù),聚類中心為3×2的矩陣;第二組為300個(gè)三維數(shù)據(jù),聚類中心為3×3的矩陣．兩組實(shí)驗(yàn)數(shù)據(jù)原始分類:1～100為類別1,101～200為類別2,201～300為類別3．得到聚類結(jié)果如圖1～4所示.

由圖1可知傳統(tǒng)的K-means聚類對(duì)二維數(shù)據(jù)的聚類圖不理想,易受孤立點(diǎn)和初值的影響,存在不穩(wěn)定性,其中第1類數(shù)據(jù)錯(cuò)誤歸為第2類,第2類數(shù)據(jù)和第3類數(shù)據(jù)歸類不明顯．而由圖2可知GFPA-Kmeans聚類結(jié)果比較理想,聚類效果圖更明顯且穩(wěn)定,能有效克服孤立點(diǎn)和初始聚類中心對(duì)聚類結(jié)果的影響．由表4可知相比K-means聚類,GFPA-Kmeans的準(zhǔn)確性有明顯的提高,結(jié)果更準(zhǔn)確．

算法第1類第2類第3類K-meansGFPA-Kmeans84.291.479.490.284.691.3

表 5 兩種算法的聚類結(jié)果準(zhǔn)確率比較

由圖3可知傳統(tǒng)的K-means聚類對(duì)三維數(shù)據(jù)的聚類結(jié)果存在缺陷,因初始聚類中心和孤立點(diǎn)的影響會(huì)出現(xiàn)偏差導(dǎo)致錯(cuò)誤分類,尤其在各類的邊界處聚類出錯(cuò)率比較大．而由圖4可知GFPA-Kmeans聚類結(jié)果比K-means更好并且穩(wěn)定,由表5可知相比K-means聚類,GFPA-Kmeans算法聚類的準(zhǔn)確性較高,有效地克服了傳統(tǒng)K-means聚類對(duì)初始聚類中心敏感的缺點(diǎn)．

為了進(jìn)一步驗(yàn)證GFPA-Kmeans算法的性能,通過(guò)UCI中的iris和wine數(shù)據(jù)集對(duì)算法進(jìn)行測(cè)試．iris數(shù)據(jù)集包括3類共150個(gè)樣本,每個(gè)樣本有4個(gè)屬性,wine數(shù)據(jù)集包括3類共178個(gè)樣本,每個(gè)樣本有13個(gè)屬性．對(duì)每個(gè)數(shù)據(jù)集分別用K-means算法,FPA-Kmeans算法、改進(jìn)PSO-Kmeans算法[3]、(IABC-Kmeans)算法[4]以及本文的GFPA-Kmeans算法進(jìn)行實(shí)驗(yàn),每個(gè)算法均隨機(jī)運(yùn)行50次．結(jié)果見(jiàn)表6～7．

從表6中可以看出,GFPA-Kmeans算法對(duì)于iris數(shù)據(jù)集平均耗時(shí)為0.261 2,準(zhǔn)確率為91.4%,迭代次數(shù)為100.從表7中可以看出,GFPA-Kmeans算法對(duì)于wine數(shù)據(jù)集平均耗時(shí)為0.270 1,準(zhǔn)確率為80.2%,迭代次數(shù)為110．在所有對(duì)比算法中耗時(shí)最短,準(zhǔn)確率最高,迭代次數(shù)最少.表6和表7均說(shuō)明GFPA-Kmeans算法能夠在最短的時(shí)間內(nèi)跳出局部極值,得到新的適應(yīng)度值,迭代次數(shù)減少,從而得到最優(yōu)的初始聚類中心,消弱了孤立點(diǎn)的影響,算法更穩(wěn)定,聚類結(jié)果更理想．

表 6 iris數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果

表 7 wine數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果

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

通過(guò)對(duì)陷入局部極值的花粉配子加入高斯白噪聲擾動(dòng),增加花粉算法的多樣性,克服早熟收斂的問(wèn)題．利用改進(jìn)后的花粉算法強(qiáng)大的全局搜索能力對(duì)K-means初始聚類中心優(yōu)化,以均值-標(biāo)準(zhǔn)差的方法選取初始聚類中心,并用基于距離的方法消弱孤立點(diǎn)對(duì)聚類的影響,使其更好地歸類．實(shí)驗(yàn)結(jié)果表明文中提出的改進(jìn)算法與傳統(tǒng)K-means算法相比具有更高的正確率,聚類效果更好．

[1] BRADLEY P S,FAYYAD U M.Refining initial points for K-Means clustering[C].Proceeding of the 15th International Conference on Machine Learning,Sam Francisco,1998:91-99.

[2] 許茂增,余國(guó)印.基于云自適應(yīng)遺傳算法的K-means聚類分析[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2015,45(17):48-55.

XU Maozeng,YU Guoyin.K-means clustering analysis based on cloud adaptive genetic algorithm[J].Mathematice in Practice and Theory,2015,45(17):48-55.

[3] 謝秀華,李陶深.一種基于改進(jìn)PSO的K-means優(yōu)化聚類算法[J].計(jì)算機(jī)技術(shù)與發(fā)展, 2014,24(2):34-38.

XIE Xiuhua,LI Taoshen.An optimized K-means clustering algorithm based on improved particle swarm optimization[J].Computer Technology and Development,2014,24(2):34-38.

[4] 喻金平,鄭杰,梅宏標(biāo).基于改進(jìn)人工蜂群算法的K均值聚類算法[J].計(jì)算機(jī)應(yīng)用,2014,34(4):1065-1069.

YU Jingping,ZHENG Jie,MEI Hongbiao.K-means clustering algorithm based on improved artificial bee colony algorithm[J].Journal of Computer Applications,2014,34(4):1065-1069.

[5] 趙杰,雷秀娟,吳振強(qiáng).基于最優(yōu)類中心擾動(dòng)的螢火蟲(chóng)聚類算法[J].計(jì)算機(jī)工程與科學(xué)及儀表,2015,37(2):342-347.

ZHAO Jie,LEI Xiujuan,WU Zhenqiang.An improved firefly clustering algorithm based on optimal class-center disturbance[J].Computer Engineering and Science,2015,37(2):342-347.

[6] 劉莉莉,曹寶香.基于差分進(jìn)化算法的K-means算法改進(jìn)[J].計(jì)算機(jī)技術(shù)與發(fā)展,2015,25(10):88-92.

LIU Lili,CAO Baoxiang.Improvement of K-means algorithm based on differential evolution algorithm[J].Computer Technology and Development,2015,25(10):88-92.

[7] 呂少娟,張桂珠.一種融合K-means算法和人工魚(yú)群算法的聚類方法[J].計(jì)算機(jī)應(yīng)用與軟件,2015,32(9):240-243.

LYU Shaojuan,ZHANG Guizhu.A new clustering method combining K-means and artificial fish swarm[J].Computer Applications and Software,2015,32(9):240-243.

[8] 侯曉晶,王會(huì)青,陳俊杰,等.基于最近鄰距離差的改進(jìn)孤立點(diǎn)檢測(cè)算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2013,34(4):1265-1268.

HOU Xiaojing,WANG Huiqing,CHEN Junjie,et al.Improved outlier detection algorithm based on difference between nearest neighbors distance[J].Computer Engineering and Design,2013,34(4):1265-1268.

[9] 劉衍民.一種求解約束優(yōu)化問(wèn)題的混合粒子群算法[J].清華大學(xué)學(xué)報(bào)：自然科學(xué)版,2013,53(2):242-246.

LIU Yanmin.Hybrid particle swarm optimizer for constrained optimization problems[J].Journal of Tsinghua University:Science & Technology,2013,53(2):242-246.

[10] 張毅,賀興時(shí),楊新社.基于模擬退火與高斯擾動(dòng)的布谷鳥(niǎo)算法[J].紡織高?；A(chǔ)科學(xué)學(xué)報(bào),2015,28(4):515-521.

ZHANG Yi,HE Xingshi,YANG Xinshe.A cuckoo search algorithm based on simulated annealing and Gaussian disturbance[J].Basic Science Journal of Textile Universities,2015,28(4):515-521.

[11] 賀興時(shí),丁文靜,楊新社.基于模擬退火高斯擾動(dòng)的蝙蝠優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究,2014,31(2):392-397.

HE Xingshi,DING Wenjing,YANG Xinshe.Bat algorithm based on simulated annealing and Gaussian perturbations[J].Application Research of Computers,2014,31(2):392-397.

[12] YANG Xinshe.Flower pollination algorithm for global optimization[C]//Proceeding of the 11th International Conference on Unconventional Computation and Natural Computation,Belin:Spring-Verlag,2012:240-249.

[13] YANG Xinshe,KARAMANOGLU Mehmet,HE Xingshi.Flower pollination algorithm:A novel approach for multiobjective optimization[C]//Engineering Optimization,London:Taylor & Francis,2013:1-16.

[14] 喬現(xiàn)偉,賀興時(shí),楊新社,等.基于混沌的花粉算法[J].紡織高?；A(chǔ)科學(xué)學(xué)報(bào),2015,28(3):330-334.

QIAO Xianwei,HE Xingshi,YANG Xinshe,et al.Chaos-based flower algorithm[J].Basic Science Journal of Textile Universities,2015,28(3):330-334.

[15] YANG Xinshe.Review of Meta-heuristics and generalised evolutionary walk algorithm[J].International Journal of Bio-Inspired Computation,2011,3(2):77-84.

[16] YANG Xinshe,KARAMANOGLU M,HE Xingshi.Multi-objective flower algorithm for optimization[J].Procedia Computer Science,2013,18(1):861-868.

[17] KAUR M,KAUR N.Text clustering using PBO algorithm for analysis and optimization[J].International Journal of Current Engineering and Technology,2014,4(6):3876-3878.

[18] PRATHIBA R,MOSES M B,SAKTHIVEL S.Flower pollination algorithm applied for different economic load dispatch problems[J].International Journal of Engineering and Technology,2014,6(2):1009-1016.

編輯:武 暉；校對(duì)：師 瑯

K-means clustering algorithm based on flower pollination algorithm

ZHANGJiao,WANGXiaodong,XUEHong

(School of Science，Xi′an Polytechnic University,Xi′an 710048,China)

In order to overcome the disadvantage of the flower pollination algorithm, such as low-accurancy computation, slow-speed convergence in later, the improved flower pollination algorithm is proposed by joining Gaussian white noise disturbance. The original clustering center of K-means algorithm is optimized by the improved flower pollination algorithm with strong global search ability, the outliers influence on clustering is weaken by the method based on distance,and the performance of the algorithm is verified and tested. Experimental results show that the algorithm is effectively avoids falling into local optimum, and improves the clustering performance.

K-means clustering; flower pollination algorithm; original clustering center

1006-8341(2016)04-0563-07

10.13338/j.issn.1006-8341.2016.04.025

2016-05-08

陜西省自然科學(xué)基金資助項(xiàng)目(2016JM1031)

王曉東(1974—),女,陜西省咸陽(yáng)市人,西安工程大學(xué)副教授，研究方向統(tǒng)計(jì)建模與仿真、智能算法等.

E-mail:591765847@qq.com

張姣,王曉東,薛紅.基于花粉算法的K均值聚類算法[J].紡織高?；A(chǔ)科學(xué)學(xué)報(bào),2016,29(4)：563-569.

ZHANG Jiao,WANG Xiaodong,XUE Hong.K-means clustering algorithm based on flower pollination algorithm[J].Basic Sciences Journal of Textile Universities,2016,29(4):563-569.

TP 181

A