基于粒子群的三支聚類(lèi)算法

高艷龍,萬(wàn)仁霞,,陳瑞典

(1.寧夏智能信息與大數(shù)據(jù)處理重點(diǎn)實(shí)驗(yàn)室，寧夏 銀川 750021； 2.福建弘揚(yáng)軟件有限公司健康大數(shù)據(jù)研究院，福建 福州 350002)

0 引言

近幾年,隨著5G技術(shù)、物聯(lián)網(wǎng)、云技術(shù)、區(qū)塊鏈、人工智能產(chǎn)業(yè)的快速發(fā)展，這些技術(shù)時(shí)刻都在產(chǎn)生大量的數(shù)據(jù)，如何從復(fù)雜數(shù)據(jù)中提取有用的信息，這是數(shù)據(jù)挖掘的范疇.聚類(lèi)是數(shù)據(jù)挖掘中的一個(gè)重要分支，其為一種無(wú)監(jiān)督的學(xué)習(xí)方法.其中K-means算法是Macqueen[1]提出的一種基于劃分聚類(lèi)算法，能夠從雜亂無(wú)章的數(shù)據(jù)中挖掘出有價(jià)值的信息，對(duì)這些信息進(jìn)行聚類(lèi)，同一類(lèi)中的信息相似度高，不同類(lèi)中的信息相似度低.

K-means算法對(duì)聚類(lèi)中心的選擇比較敏感，而且易陷入局部最優(yōu)解[2-3].針對(duì)K-means算法的不足，有許多學(xué)者嘗試用群體智能算法對(duì)K-means進(jìn)行改進(jìn)，粒子群優(yōu)化算法作為群體智能算法典型，被廣泛用于改進(jìn)聚類(lèi)算法[4-5].文獻(xiàn)[6]首次將粒子群與K-means算法相結(jié)合，該算法的思路是用K-means方法得到的聚類(lèi)中心，作為粒子群初始粒子.文獻(xiàn)[7]提出了粒子群與模糊K-means結(jié)合的算法，該算法將k個(gè)初始數(shù)據(jù)作為初始粒子，調(diào)用粒子群優(yōu)化算法尋優(yōu)求得最優(yōu)的聚類(lèi)中心，最后再對(duì)得到的聚類(lèi)中心數(shù)據(jù)進(jìn)行模糊劃分.文獻(xiàn)[8]提出一種改進(jìn)的粒子群和K-means混合聚類(lèi)算法，該算法引入小概率隨機(jī)變異操作,增加了粒子多樣性，提高了算法全局搜索能力，粒子群的適應(yīng)度函數(shù)采用方差來(lái)比較粒子好壞.

經(jīng)典K-means算法是一種硬劃分算法，也是一種典型的二支聚類(lèi)算法，即對(duì)象只能屬于某一類(lèi)，這在相對(duì)離散的數(shù)據(jù)集中沒(méi)有什么問(wèn)題，但數(shù)據(jù)集中有不確定數(shù)據(jù)時(shí)，將數(shù)據(jù)強(qiáng)制劃分，會(huì)帶來(lái)很大決策風(fēng)險(xiǎn).由此，文獻(xiàn)[9]將類(lèi)數(shù)據(jù)劃分為核心域、邊界域和瑣碎域3部分，類(lèi)由核心域和邊界域兩個(gè)域組成，提出了一種三支聚類(lèi)算法.文獻(xiàn)[10]用三支決策理論研究類(lèi)與類(lèi)的重疊部分，提出了一種處理重疊部分?jǐn)?shù)據(jù)的三支決策聚類(lèi)算法，把重疊部分?jǐn)?shù)據(jù)劃分到類(lèi)的邊界域.文獻(xiàn)[11]提出了一種使用樣本鄰域?qū)⒍Ь垲?lèi)轉(zhuǎn)化為三支聚類(lèi)的方法，該方法利用二支聚類(lèi)的結(jié)果和每個(gè)類(lèi)中元素的鄰域收縮和擴(kuò)張來(lái)刻畫(huà)類(lèi)組成.針對(duì)K-means算法易陷入局部最優(yōu)解和聚類(lèi)結(jié)果準(zhǔn)確率低等問(wèn)題，本研究引入粒子群優(yōu)化算法和三支聚類(lèi)，提出一種基于粒子群的三支聚類(lèi)算法，來(lái)提高聚類(lèi)算法的聚類(lèi)質(zhì)量.

1 相關(guān)概念

1.1 粒子群優(yōu)化算法

粒子群優(yōu)化算法(particle swarm optimization,PSO)[12]是兩位學(xué)者從大自然中觀察鳥(niǎo)類(lèi)族群尋找食物信息傳遞中受到的啟示而開(kāi)發(fā)設(shè)計(jì)的群體智能算法.粒子群中的單一粒子對(duì)應(yīng)于鳥(niǎo)類(lèi)族群中的單一個(gè)體，算法賦予粒子擁有記憶，就像鳥(niǎo)類(lèi)通過(guò)個(gè)體之間的合作與競(jìng)爭(zhēng)來(lái)實(shí)現(xiàn)全局搜索食物，從而得到粒子個(gè)體最優(yōu)值和全局最優(yōu)值.

在PSO算法中，粒子群由n個(gè)粒子組成，由于粒子沒(méi)有質(zhì)量和體積，可以延伸到d維空間，Xi={Xi1,Xi2,…,Xid}，1≤i≤n.每個(gè)粒子通過(guò)調(diào)整自己的位置求得新解，通過(guò)比較并存儲(chǔ)最優(yōu)值，稱(chēng)為Pid；在d維空間里粒子種群尋找到最優(yōu)值所對(duì)應(yīng)全局最好的位置，稱(chēng)為Pgd.

粒子有速度v和位置X兩個(gè)屬性，v代表粒子移動(dòng)的速率，X代表粒子移動(dòng)的方位.速度v按下式更新：

(1)

其中：vid表示第i個(gè)粒子在第d維度空間里移動(dòng)的快慢；ω為慣性權(quán)重，一般取值在[0.1,0.9]之間[13]，其值越大，全局搜索能力較強(qiáng)，局部搜索能力較弱，其值越小，局部搜索能力較強(qiáng)，全局搜索能力較弱；η1、η2為學(xué)習(xí)因子，是調(diào)節(jié)Pid和Pgd相對(duì)重要性的參數(shù)，通常取值范圍是[0,4][14]；rand(0,1)表示區(qū)間(0,1)隨機(jī)數(shù)；Pid表示第i個(gè)變量個(gè)體極值的第d維；Pgd表示全局最優(yōu)解的第d維.

粒子移動(dòng)位置按下式更新：

(2)

其中：Xid表示第i個(gè)粒子在第d維度空間里的位置.

粒子群優(yōu)化算法有如下6個(gè)主要步驟.

步驟1粒子群初始化，設(shè)置粒子群規(guī)模，隨機(jī)初始化粒子速度和位置.

步驟2計(jì)算所有粒子的適應(yīng)度值.

步驟3對(duì)每個(gè)粒子的適應(yīng)度值與其經(jīng)歷過(guò)最優(yōu)位置適應(yīng)度值對(duì)比，如果優(yōu)于目前最好的，則更新粒子最優(yōu)位置為Pid.

步驟4對(duì)所有粒子的適應(yīng)度值比較，如果最好個(gè)體極值Pid優(yōu)于全局極值Pgd，則全局極值Pgd更新為Pid.

步驟5用式(1)～(2)更新粒子速度v的和位置X.

步驟6若終止條件(最大迭代次數(shù)或足夠好的位置等)達(dá)到，算法停止；否則,重復(fù)步驟2到步驟5.

1.2 三支聚類(lèi)

三支決策[15-17]是把一個(gè)整體分為3個(gè)域來(lái)表示，即正域、負(fù)域、邊界域.三支聚類(lèi)[18-20]就是把三支決策引入到聚類(lèi)算法中，重新定義對(duì)象和類(lèi)的關(guān)系有3種，第一種是對(duì)象肯定屬于某類(lèi)(正域)；第二種是可能屬于也可能不屬于某類(lèi)(邊界域)；第三種是肯定不屬于某類(lèi)(負(fù)域).

給定一個(gè)數(shù)據(jù)集U={x1,x2,…,xn}，聚類(lèi)結(jié)果為C={C1,C2,…,Ck}.三支決策聚類(lèi)是由三個(gè)互不相交的集合表示一個(gè)類(lèi)，即核心域、邊界域、瑣碎域，也稱(chēng)為CP、CB、CN.

CN=U-(CP∪CB)

(3)

其中：CP中的對(duì)象肯定屬于這個(gè)類(lèi);CB中的對(duì)象可能屬于這個(gè)類(lèi)，CN中的對(duì)象肯定不屬于這個(gè)類(lèi).

2 三支聚類(lèi)算法的設(shè)計(jì)

粒子群優(yōu)化算法可以整體上反映群體的簇群劃分分布趨勢(shì)，而三支聚類(lèi)算法則可以有效地刻畫(huà)類(lèi)的邊界點(diǎn)的分布細(xì)節(jié).基于以上認(rèn)識(shí)，設(shè)計(jì)一種聚類(lèi)算法，以期吸收上述兩算法的優(yōu)點(diǎn)，達(dá)到更好的聚類(lèi)質(zhì)量.

2.1 公式計(jì)算

1) 粒子的編碼結(jié)構(gòu)如下：

X11X12…X1dX21…X2d…X3d.…Xkd|v1v2…vk×d|f(x)

(4)

其中：Xkd表示粒子的位置;vk×d表示粒子的速度.

2) 當(dāng)聚類(lèi)中心確定后，根據(jù)最近鄰距離把數(shù)據(jù)劃分到最近的類(lèi)：

(5)

其中：xj表示第j個(gè)對(duì)象，1≤j≤n；Ci表示第i個(gè)聚類(lèi)中心，1≤i≤k；xjt表示第j個(gè)對(duì)象的第t個(gè)屬性；Cit表示第i個(gè)聚類(lèi)中心的第t個(gè)屬性.

3) 聚類(lèi)中心的計(jì)算(均值)：

(6)

其中：xj為數(shù)據(jù)對(duì)象，1≤j≤n；|Ci|屬于該類(lèi)的樣本個(gè)數(shù).

4) 粒子群采用的適應(yīng)度函數(shù)(誤差平方和)：

(7)

其中：d(xj,Ci)是樣本xj到聚類(lèi)中心Ci距離；函數(shù)f(x)是數(shù)據(jù)到相對(duì)應(yīng)聚類(lèi)中心的距離總和，要達(dá)到最小.

5) 為了平衡粒子的局部尋優(yōu)能力和全局尋優(yōu)能力，本研究中慣性權(quán)重ω采用線性遞減策略：

(8)

其中：ω是慣性權(quán)重,ω∈(0.3,0.8);ωmax是慣性權(quán)重的最大值;ωmin是慣性權(quán)重的最小值;T是迭代總次數(shù);i是迭代次數(shù)變量.

慣性權(quán)重采用線性遞減有效地控制粒子的局部尋優(yōu)能力和全局尋優(yōu)能力強(qiáng)弱上的切換.

6) 選擇合適的學(xué)習(xí)因子，能保證算法的收斂速度和搜索能力的均衡.本研究中學(xué)習(xí)因子采用下式更新：

(9)

(10)

其中：η1、η2是學(xué)習(xí)因子，η1、η2∈[0.50,2.05]，ηmax是學(xué)習(xí)因子的最大值，ηmin是學(xué)習(xí)因子的最小值，T是迭代總次數(shù)，i是迭代次數(shù)變量.

學(xué)習(xí)因子采用單調(diào)遞減、單調(diào)遞增的方式，避免了粒子在局部最優(yōu)范圍徘徊和過(guò)早收斂到最優(yōu)值，同時(shí)保證了算法的收斂速度和搜索能力的均衡.

7) 粒子群速度的上界和下界.粒子群中速度的上界和下界能維護(hù)粒子的探索能力平衡.速度選擇過(guò)大，其探索能力強(qiáng)，但易于飛過(guò)最優(yōu)解；速度選擇過(guò)小，其探索能力變?nèi)酰紫萑刖植孔顑?yōu).所以速度取值在速度的上界vmax和下界vmin之間.

8) 差值排序法[9].遍歷類(lèi)內(nèi)所有數(shù)據(jù)到聚類(lèi)中心的歐式距離，把距離按照從小到大的順序排列disk(x1,Ci),disk(x2,Ci),…,disk(xn,Ci);然后依次計(jì)算disk(x2,Ci)-disk(x1,Ci),…,disk(xj,Ci)-disk(xj-1,Ci),…,disk(xn,Ci)-disk(xn-1,Ci)；最后找出第一個(gè)歐式距離最大的差值對(duì)，把x1,x2,…,xj-1對(duì)象放入Ci的核心域，xj,xj+1，…,xn對(duì)象放入Ci的邊界域中.

2.2 算法步驟

輸入：數(shù)據(jù)集U，聚類(lèi)數(shù)目k，近鄰數(shù)q，慣性因子ω，學(xué)習(xí)因子η1、η2.

步驟1初始化粒子群.在數(shù)據(jù)集中隨機(jī)選取k個(gè)數(shù)據(jù)對(duì)象作為初始聚類(lèi)中心，初始聚類(lèi)中心值賦值給初始粒子，通過(guò)m次選取，形成m個(gè)粒子，初始化粒子的速度與位置.

步驟2用式(5)計(jì)算每個(gè)粒子中的所有數(shù)據(jù)對(duì)象到聚類(lèi)中心的距離，根據(jù)最近鄰距離原則對(duì)數(shù)據(jù)進(jìn)行類(lèi)劃分.

步驟3用式(7)計(jì)算每個(gè)粒子適應(yīng)度值.

步驟4對(duì)每個(gè)粒子的適應(yīng)度值與其經(jīng)歷過(guò)最優(yōu)位置適應(yīng)度值對(duì)比，如果優(yōu)于目前的位置，則更新粒子最優(yōu)的位置為Pid.

步驟5對(duì)所有粒子的適應(yīng)度值比較，如果最好個(gè)體極值Pid優(yōu)于全局極值Pgd，則全局極值更新為Pid.

步驟6用式(1)～(2)分別更新粒子的速度和位置.

步驟7重復(fù)步驟2到步驟6，達(dá)到足夠好的位置(或最大迭代次數(shù))停止.

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集

該實(shí)驗(yàn)環(huán)境為：Intel Core i7 2.8 GHz CPU；8 GB 內(nèi)存；1 000 GB 硬盤(pán)；Windows 10 操作系統(tǒng).采用 Matlab 語(yǔ)言編程實(shí)現(xiàn).實(shí)驗(yàn)采用人工數(shù)據(jù)集和UCI數(shù)據(jù)集，如表1所示，其中D1、D2為人工數(shù)據(jù)集，其余7個(gè)數(shù)據(jù)集來(lái)自UCI數(shù)據(jù)庫(kù).人工數(shù)據(jù)集主要用以直觀展示本研究算法PTWC(基于粒子群的三支聚類(lèi))和對(duì)比算法KM(K-means)、PSOC(粒子群聚類(lèi))的聚類(lèi)效果，UCI數(shù)據(jù)集用以測(cè)試評(píng)價(jià)指標(biāo).

表1 實(shí)驗(yàn)數(shù)據(jù)集Tab.1 Experimental data set

3.2 聚類(lèi)人工數(shù)據(jù)集

為了區(qū)別KM算法、PSOC算法與PTWC算法聚類(lèi)結(jié)果，選取人工數(shù)據(jù)D1和D2做了實(shí)驗(yàn)，如圖1～6所示(圖中x、y為二維笛卡爾坐標(biāo)系的坐標(biāo)軸).

圖1 數(shù)據(jù)集D1Fig.1 D1 data set

圖1是未分類(lèi)的D1數(shù)據(jù)集;圖2是KM和PSOC算法在D1數(shù)據(jù)集上的聚類(lèi)情況，可以看出兩個(gè)算法具有相同聚類(lèi)效果；圖3是PTWC算法是在D1數(shù)據(jù)集上聚類(lèi)情況，可以看出，算法不僅具有KM和PSOC的聚類(lèi)效果，而且類(lèi)的邊界細(xì)節(jié)(“+”和“x”)也得到了刻畫(huà).邊界細(xì)節(jié)的刻畫(huà)為聚類(lèi)的噪聲分析提供了重要研究依據(jù).

圖2 KM和PSOC在D1上的聚類(lèi)效果Fig.2 Clustering results of KM and PSOC on D1

圖3 PTWC在D1上的聚類(lèi)效果Fig.3 Clustering results of PTWC on D1

圖4是未分類(lèi)的D2數(shù)據(jù)集；圖5是KM和PSOC算法在D2數(shù)據(jù)集上的聚類(lèi)情況，可以看出兩個(gè)算法仍然可以得到正確的聚類(lèi)結(jié)果；圖6是PTWC算法在D2數(shù)據(jù)集上的聚類(lèi)結(jié)果，算法不僅具有KM和PSOC的聚類(lèi)效果，而且每個(gè)類(lèi)的邊界細(xì)節(jié)也得到了刻畫(huà)，處于上邊區(qū)域的兩個(gè)類(lèi)存在交疊，即兩個(gè)類(lèi)的邊界域(“+”和“◇”)存在重疊部分，類(lèi)間對(duì)象的關(guān)系得到了更真實(shí)的展現(xiàn).

圖4 數(shù)據(jù)集D2Fig.4 D2 data set

圖6 PTWC在D2上的聚類(lèi)效果Fig.6 Clustering results of PTWC on D2

3.3 聚類(lèi)UCI數(shù)據(jù)集

3.3.1 聚類(lèi)準(zhǔn)確率與誤差平方和

采用評(píng)價(jià)指標(biāo)準(zhǔn)確率ACC和誤差平方和SSE來(lái)對(duì)比分析算法的優(yōu)劣.

準(zhǔn)確率(ACC)是一種類(lèi)外部衡量指標(biāo)，其值越高說(shuō)明聚類(lèi)效果越好.其計(jì)算式為：

(11)

其中：|Ci|表示正確劃分到類(lèi)i的數(shù)據(jù)個(gè)數(shù)，n為數(shù)據(jù)的總數(shù)，k為聚類(lèi)的數(shù)目.

在本研究PTWC、KM、PSOC 3種算法聚類(lèi)的目標(biāo)函數(shù)采用誤差平方和函數(shù)(SSE).其計(jì)算式為：

(12)

其中:d(xj,Ci)是類(lèi)內(nèi)數(shù)據(jù)對(duì)象到聚類(lèi)中心點(diǎn)的距離;SSE的值是所有數(shù)據(jù)對(duì)象到其所在聚類(lèi)中心的距離平方和，在相同的迭代次數(shù)下，SSE值越小，說(shuō)明算法越好.

在UCI數(shù)據(jù)集Iris、Wine、German、Heart、Breast、Pima、Spambase中，分別用KM算法、PSOC算法和PTWC算法每次迭代100次，共運(yùn)行100次取ACC的平均值和SSE的最小值做實(shí)驗(yàn)對(duì)比，實(shí)驗(yàn)結(jié)果如表2所示.

表2 UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Tab.2 Experimental results on UCI data set

從表2中可以看出，在7個(gè)數(shù)據(jù)集上，PTWC算法的ACC的值高于KM算法和PSOC算法的ACC值，PTWC算法的SSE值低于另外兩個(gè)算法的SSE值，表明PTWC具有更好的聚類(lèi)質(zhì)量.這是因?yàn)橥ㄟ^(guò)粒子尋優(yōu)，PTWC獲得了最優(yōu)的簇中心，確保了算法在劃分?jǐn)?shù)據(jù)集時(shí)的聚類(lèi)結(jié)構(gòu)質(zhì)量，而通過(guò)邊界域的最小鄰居處理技術(shù)來(lái)進(jìn)一步細(xì)化類(lèi)間重疊部分和孤立點(diǎn)部分的歸屬，從而提高聚類(lèi)的準(zhǔn)確率.

3.3.2 尋優(yōu)曲線變化

為進(jìn)一步展示算法性能，記錄了算法的尋優(yōu)曲線過(guò)程.3種算法在UCI數(shù)據(jù)集上的最優(yōu)值隨迭代次數(shù)的變化趨勢(shì)，如圖7所示.

圖7(a)～(g)分別記錄了3種算法在數(shù)據(jù)集Wine、Breast、Heart、German、Iris、Pima、Spamdase的最優(yōu)值在迭代100次的變化趨勢(shì).從7張圖整體情況來(lái)看，在相同的條件下，KM收斂速度快，但易于陷入局部最優(yōu)值；PSOC算法，在收斂時(shí)出現(xiàn)稍微震蕩；PTWC算法全局尋優(yōu)能力優(yōu)于KM，且不易陷入局部最優(yōu)解，收斂速度比PSOC算法快，而且PTWC比KM、PSOC更接近于最優(yōu)值.這是因?yàn)镵M依據(jù)最小距離原則劃分?jǐn)?shù)據(jù)，在一定數(shù)據(jù)規(guī)模下，能較快收斂，但易于陷入局部最小，而PSOC實(shí)際上是在KM的基礎(chǔ)上再進(jìn)行PSO尋優(yōu)，雙重迭代尋優(yōu)導(dǎo)致計(jì)算時(shí)間開(kāi)銷(xiāo)增大，而PTWC借助PSO獲得簇中心后，通過(guò)三支決策的方法來(lái)劃分?jǐn)?shù)據(jù)對(duì)象的歸屬，既確保了聚類(lèi)的質(zhì)量，又在時(shí)間開(kāi)銷(xiāo)方面避免了PSOC多重迭代的不足.

(a) Wine data set

4 結(jié)語(yǔ)

研究提出一種基于粒子群的三支聚類(lèi)算法，算法通過(guò)粒子群全局尋優(yōu)能力更新聚類(lèi)中心，有效避免因收斂速度過(guò)快而陷入局部最優(yōu)值，而在處理類(lèi)與類(lèi)的重疊數(shù)據(jù)和類(lèi)內(nèi)孤立數(shù)據(jù)時(shí)，采用了三支決策的方法，降低決策風(fēng)險(xiǎn)，從而提高了聚類(lèi)結(jié)果的準(zhǔn)確性.