一種改進(jìn)的PSO-Means聚類優(yōu)化算法

魏新紅，張 凱

(河南城建學(xué)院計(jì)算機(jī)科學(xué)與工程系，河南平頂山467036)

0 前言

基于粒子群的K均值聚類［1］(PSO-Means)算法是將粒子群算法［2－3］與傳統(tǒng)的K均值算法［4］相結(jié)合，可以避免K均值算法的聚類個(gè)數(shù)K需指定的缺陷，對(duì)于線性可分的數(shù)據(jù)利用PSO能夠比較精確地找到聚類的個(gè)數(shù)。但傳統(tǒng)的PSO-Means算法在線性不可分情況下找到的聚類個(gè)數(shù)和初始聚類中心往往是不理想的［5］。在實(shí)際應(yīng)用中，即使PSO算法找到了精確的聚類個(gè)數(shù)和理想的聚類質(zhì)心，利用K均值算法對(duì)線性不可分問(wèn)題進(jìn)行聚類也不會(huì)有好的效果。

在此將核方法用在聚類研究中，對(duì)粒子的位置更新進(jìn)行一些改進(jìn)，即在線性空間中一個(gè)粒子的周圍探測(cè)，找到在核空間中更接近最優(yōu)粒子的一個(gè)點(diǎn)，使得這個(gè)點(diǎn)和該粒子之間的向量作為近似的最優(yōu)方向。實(shí)驗(yàn)表明:這種改進(jìn)具有相對(duì)較高的準(zhǔn)確率［6］和穩(wěn)定性。

1 改進(jìn)的KPSO-Means算法的基本思想

核方法的主要思想是把線性空間中關(guān)于距離的計(jì)算變換成核函數(shù)的計(jì)算，即:

其中，Φ(·)為向量函數(shù)，其具體形式是不確定的;k(·，·)是滿足Mercer條件的核函數(shù)。原始粒子的位置移動(dòng)是由自身速度、自身最優(yōu)位置和群體最優(yōu)位置所決定的，由于Φ(·)不能確定，粒子在核空間中的位置和自身速度都是無(wú)法確定的。原始粒子群算法中，粒子通過(guò)式(2)更新其位置，而在核空間中，xid，vid，pid，pgd都是找不到的。

在式(2)中，最重要的是(pid－x)和(pgd－x)兩個(gè)部分，分別是粒子自身的最優(yōu)方向和群體最優(yōu)方向。由于pid和pgd在核空間中連維數(shù)都不能確定，只能通過(guò)試探的方法找到核空間中兩個(gè)最優(yōu)方向在線性空間中的反映。

上面的分析說(shuō)明PSO算法中最為重要的過(guò)程是粒子的移動(dòng)，這個(gè)過(guò)程如果在核空間中進(jìn)行就必須要求出Φ(x)的具體形式。本文提出利用模矢法的思想，依舊在線性空間中改變粒子的位置，但是最優(yōu)方向的標(biāo)準(zhǔn)卻來(lái)自核空間，這樣就可以避免求出Φ(x)的具體形式，經(jīng)過(guò)模矢法改進(jìn)的PSO算法則可以用于核空間計(jì)算。具體方法是利用KPSO算法找到數(shù)據(jù)聚類的個(gè)數(shù)和初始質(zhì)心，然后利用基于核函數(shù)的K均值算法在核空間中聚類。這樣不但能大大的提高K均值算法的聚類能力，而且能夠找到相對(duì)合適的初始質(zhì)心，同時(shí)也確定了聚類個(gè)數(shù)。

2 改進(jìn)的KPSO-Means算法描述

改進(jìn)的算法過(guò)程如下:

①在數(shù)據(jù)空間中初始化粒子，使粒子的影響范圍能夠基本覆蓋所有數(shù)據(jù)，并確定合適的粒子影響范圍r及粒子攝動(dòng)的初始步長(zhǎng)δ1。

②每個(gè)粒子在自己的影響范圍內(nèi)計(jì)算自己的數(shù)據(jù)密度。遍歷數(shù)據(jù)，計(jì)算粒子與數(shù)據(jù)在核空間中的距離，小于影響范圍的則增加該粒子的數(shù)據(jù)密度。

③尋找自己周圍的最優(yōu)粒子。計(jì)算粒子與其他所有粒子在核空間中的距離，影響范圍內(nèi)的數(shù)據(jù)密度最大的粒子為最優(yōu)粒子。

④確定兩個(gè)近似最優(yōu)方向p'i－xi和g'i－xi。

⑤粒子按式(2)更新位置。

⑥改變步長(zhǎng)，返回步驟②，直到滿足條件或達(dá)到最大循環(huán)次數(shù)。

⑦以KPSO算法最終得到的最優(yōu)粒子為初始質(zhì)心，然后進(jìn)行基于核函數(shù)的K均值聚類。如果最終得到的某個(gè)類中只有極少數(shù)數(shù)據(jù)，則該類數(shù)據(jù)可以看作是孤立點(diǎn)。

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

在某次數(shù)據(jù)實(shí)驗(yàn)中通過(guò)運(yùn)行PSO算法找到的聚類個(gè)數(shù)及初始質(zhì)心如圖1所示，然后利用KPSO算法對(duì)圖1所示的數(shù)據(jù)重新查找初始聚類質(zhì)心和聚類個(gè)數(shù)。粒子初始位置為在線性空間中的均勻分布。核函數(shù)采用多項(xiàng)式核函數(shù): k(x，y)=(xy+1)d，d=1，2，…，N，粒子的影響范圍)。最終，找到兩個(gè)初始質(zhì)心，一個(gè)位于外部環(huán)形中，一個(gè)位于中間接近圓心處。

4 改進(jìn)的KPSO-Means算法有效性驗(yàn)證

以上數(shù)據(jù)試驗(yàn)所應(yīng)用的都是二維的可視數(shù)據(jù)，為了進(jìn)一步驗(yàn)證改進(jìn)的KPSO-Means算法的有效性，在hd數(shù)據(jù)集上對(duì)算法進(jìn)行測(cè)試。

運(yùn)用手寫數(shù)字中提取到的20維特征數(shù)據(jù)進(jìn)行聚類，所用的數(shù)據(jù)集源于一項(xiàng)手寫數(shù)字識(shí)別研究所提取到的數(shù)據(jù)［7］。手寫數(shù)字識(shí)別建立在有監(jiān)督分類算法基礎(chǔ)之上，所用的hd數(shù)據(jù)集包含從0到9的10個(gè)數(shù)字。分別應(yīng)用K-Means算法［8］、核K-Means［9］、PSO-Means算法和改進(jìn)后的KPSO-Means算法對(duì)該數(shù)據(jù)集進(jìn)行不同類別個(gè)數(shù)的聚類試驗(yàn)。為保證數(shù)據(jù)源的多樣性，收集了多個(gè)人的筆跡。其中每個(gè)數(shù)字5 400個(gè)，共54 000個(gè)數(shù)字。手寫數(shù)字經(jīng)過(guò)二值化、去噪和平滑等數(shù)據(jù)處理后確定了數(shù)字的準(zhǔn)確位置和其大小。

4.1 特征提取

本文中特征提取包括兩部分的內(nèi)容:穿越次數(shù)和數(shù)字形體特征。

穿越次數(shù)特征:分別在豎方向和橫方向上取5條線，計(jì)算這10條線與數(shù)字交叉的次數(shù)，即穿越次數(shù)。計(jì)算方法為:穿越線上由白變黑的次數(shù)或由黑變白的次數(shù)。如圖3所示，豎線1～5的穿越次數(shù)分別為1，2，3，2，1，橫線1～5的穿越次數(shù)分別為2，2，1，1，1。

經(jīng)過(guò)特征提取，得到了數(shù)據(jù)的20維特征，其中10維為10條穿越線的穿插越次數(shù)，10維為10條線所穿越的數(shù)字的長(zhǎng)度與線長(zhǎng)度的比值。

圖3 特征提取

4.2 聚類質(zhì)量分析

在聚類試驗(yàn)中，分別應(yīng)用四種算法對(duì)數(shù)字0和1兩類數(shù)據(jù)、2到5四類數(shù)據(jù)、0到5六類數(shù)據(jù)、0到9十類數(shù)據(jù)進(jìn)行聚類。圖4顯示了算法隨著數(shù)據(jù)集的復(fù)雜程度的增加，聚類效果的變化情況，以及在相同數(shù)據(jù)集下不同算法的聚類效果，其中橫坐標(biāo)表示所需聚類的手寫數(shù)字的范圍。

分析圖4可知:隨著所需聚類個(gè)數(shù)的增加，各算法的聚類正確率是減小的。在相同的數(shù)據(jù)集下，核K-Means算法和KPSO-Means算法的正確率要遠(yuǎn)高于K-Means算法和PSO-Means算法，這是由于數(shù)據(jù)集的維數(shù)較大，而且很可能是線性不可分的，因此，造成了K-Means算法和PSOMeans算法不能正確的發(fā)現(xiàn)數(shù)據(jù)的模式，使得聚類的正確率低下。

圖4 聚類算法在不同數(shù)據(jù)集下的結(jié)果

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

從聚類結(jié)果可知:基于核函數(shù)的K均值算法對(duì)非線性數(shù)據(jù)聚類有著較好的聚類效果。基于核函數(shù)的改進(jìn)PSO算法雖然具有一定的不適定性，但是絕大多數(shù)情況下都能找到正確的聚類個(gè)數(shù)，并且提供合適的聚類初始質(zhì)心。正是因?yàn)榛诤撕瘮?shù)的改進(jìn)PSO算法使得初始質(zhì)心的選取避免了一定的盲目性，使得KPSO-Means算法的結(jié)果更加合理一些。本文在基于核函數(shù)的PSO算法中，粒子實(shí)際上仍是在樣本空間中運(yùn)行，只是運(yùn)行的兩個(gè)最優(yōu)方向的尋找過(guò)程應(yīng)用了核函數(shù)進(jìn)行尋找，其收斂性還有待于進(jìn)一步的研究。

［1］ 金松河，錢慎一，張素智.基于Web日志的高精度聚類算法［J］.河南科技大學(xué)學(xué)報(bào):自然科學(xué)版，2006，27(4):49－51.

［2］ 王輝，張望，范明.基于集群環(huán)境的K-Means聚類算法的并行化［J］.河南科技大學(xué)學(xué)報(bào):自然科學(xué)版，2008，29(4): 42－45.

［3］ 吳昌友，王福林，馬力.一種新的改進(jìn)粒子群優(yōu)化算法［J］.控制工程，2010(5):359－362.

［4］ 但漢輝，張玉芳，張世勇.一種改進(jìn)的K-均值聚類算法［J］.重慶工商大學(xué)學(xué)報(bào):自然科學(xué)版，2009(2):144－147.

［5］ 韓凌波，王強(qiáng)，蔣正峰，等.一種改進(jìn)的K-means初始聚類中心選取算法［J］.計(jì)算機(jī)工程與應(yīng)用，2010(17):150－152.

［6］ 許建華，張學(xué)工.經(jīng)典線性算法的非線性核形式［J］.控制與決策，2006，21(1):1－6.

［7］ Xiao H M，Liu C，Song ZG.Handwritten Recognition Based on Support Vector Machine［C］//Proceedings of International Forum of Information Systems Frontiers.2006 Xian International Symposium.Xian:2006.

［8］ 王慧，申石磊.一種改進(jìn)的特征加權(quán)K-means聚類算法［J］.微電子學(xué)與計(jì)算機(jī)，2010，27(7):161－163.

［9］ 張莉，周偉達(dá)，焦李成.核聚類算法［J］.計(jì)算機(jī)學(xué)報(bào)，2002，25(6):587－590.