高艷龍,萬仁霞,,陳瑞典

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

0 引言

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

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

經典K-means算法是一種硬劃分算法，也是一種典型的二支聚類算法，即對象只能屬于某一類，這在相對離散的數據集中沒有什么問題，但數據集中有不確定數據時，將數據強制劃分，會帶來很大決策風險.由此，文獻[9]將類數據劃分為核心域、邊界域和瑣碎域3部分，類由核心域和邊界域兩個域組成，提出了一種三支聚類算法.文獻[10]用三支決策理論研究類與類的重疊部分，提出了一種處理重疊部分數據的三支決策聚類算法，把重疊部分數據劃分到類的邊界域.文獻[11]提出了一種使用樣本鄰域將二支聚類轉化為三支聚類的方法，該方法利用二支聚類的結果和每個類中元素的鄰域收縮和擴張來刻畫類組成.針對K-means算法易陷入局部最優(yōu)解和聚類結果準確率低等問題，本研究引入粒子群優(yōu)化算法和三支聚類，提出一種基于粒子群的三支聚類算法，來提高聚類算法的聚類質量.

1 相關概念

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

粒子群優(yōu)化算法(particle swarm optimization,PSO)[12]是兩位學者從大自然中觀察鳥類族群尋找食物信息傳遞中受到的啟示而開發(fā)設計的群體智能算法.粒子群中的單一粒子對應于鳥類族群中的單一個體，算法賦予粒子擁有記憶，就像鳥類通過個體之間的合作與競爭來實現全局搜索食物，從而得到粒子個體最優(yōu)值和全局最優(yōu)值.

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

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

(1)

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

粒子移動位置按下式更新：

(2)

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

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

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

步驟2計算所有粒子的適應度值.

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

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

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

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

1.2 三支聚類

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

給定一個數據集U={x1,x2,…,xn}，聚類結果為C={C1,C2,…,Ck}.三支決策聚類是由三個互不相交的集合表示一個類，即核心域、邊界域、瑣碎域，也稱為CP、CB、CN.

CN=U-(CP∪CB)

(3)

其中：CP中的對象肯定屬于這個類;CB中的對象可能屬于這個類，CN中的對象肯定不屬于這個類.

2 三支聚類算法的設計

粒子群優(yōu)化算法可以整體上反映群體的簇群劃分分布趨勢，而三支聚類算法則可以有效地刻畫類的邊界點的分布細節(jié).基于以上認識，設計一種聚類算法，以期吸收上述兩算法的優(yōu)點，達到更好的聚類質量.

2.1 公式計算

1) 粒子的編碼結構如下：

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

(4)

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

2) 當聚類中心確定后，根據最近鄰距離把數據劃分到最近的類：

(5)

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

3) 聚類中心的計算(均值)：

(6)

其中：xj為數據對象，1≤j≤n；|Ci|屬于該類的樣本個數.

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

(7)

其中：d(xj,Ci)是樣本xj到聚類中心Ci距離；函數f(x)是數據到相對應聚類中心的距離總和，要達到最小.

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

(8)

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

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

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

(9)

(10)

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

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

7) 粒子群速度的上界和下界.粒子群中速度的上界和下界能維護粒子的探索能力平衡.速度選擇過大，其探索能力強，但易于飛過最優(yōu)解；速度選擇過小，其探索能力變弱，易陷入局部最優(yōu).所以速度取值在速度的上界vmax和下界vmin之間.

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

2.2 算法步驟

輸入：數據集U，聚類數目k，近鄰數q，慣性因子ω，學習因子η1、η2.

步驟1初始化粒子群.在數據集中隨機選取k個數據對象作為初始聚類中心，初始聚類中心值賦值給初始粒子，通過m次選取，形成m個粒子，初始化粒子的速度與位置.

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

步驟3用式(7)計算每個粒子適應度值.

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

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

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

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

3 實驗結果與分析

3.1 實驗數據集

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

表1 實驗數據集Tab.1 Experimental data set

3.2 聚類人工數據集

為了區(qū)別KM算法、PSOC算法與PTWC算法聚類結果，選取人工數據D1和D2做了實驗，如圖1～6所示(圖中x、y為二維笛卡爾坐標系的坐標軸).

圖1 數據集D1Fig.1 D1 data set

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

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

圖3 PTWC在D1上的聚類效果Fig.3 Clustering results of PTWC on D1

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

圖4 數據集D2Fig.4 D2 data set

圖6 PTWC在D2上的聚類效果Fig.6 Clustering results of PTWC on D2

3.3 聚類UCI數據集

3.3.1 聚類準確率與誤差平方和

采用評價指標準確率ACC和誤差平方和SSE來對比分析算法的優(yōu)劣.

準確率(ACC)是一種類外部衡量指標，其值越高說明聚類效果越好.其計算式為：

(11)

其中：|Ci|表示正確劃分到類i的數據個數，n為數據的總數，k為聚類的數目.

在本研究PTWC、KM、PSOC 3種算法聚類的目標函數采用誤差平方和函數(SSE).其計算式為：

(12)

其中:d(xj,Ci)是類內數據對象到聚類中心點的距離;SSE的值是所有數據對象到其所在聚類中心的距離平方和，在相同的迭代次數下，SSE值越小，說明算法越好.

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

表2 UCI數據集上的實驗結果Tab.2 Experimental results on UCI data set

從表2中可以看出，在7個數據集上，PTWC算法的ACC的值高于KM算法和PSOC算法的ACC值，PTWC算法的SSE值低于另外兩個算法的SSE值，表明PTWC具有更好的聚類質量.這是因為通過粒子尋優(yōu)，PTWC獲得了最優(yōu)的簇中心，確保了算法在劃分數據集時的聚類結構質量，而通過邊界域的最小鄰居處理技術來進一步細化類間重疊部分和孤立點部分的歸屬，從而提高聚類的準確率.

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

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

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

(a) Wine data set

4 結語

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