基于min-max準則與區域劃分的I-k-means-+聚類算法

曲福恒, 宋劍飛, 楊 勇,2, 胡雅婷, 潘曰濤

(1. 長春理工大學 計算機科學技術學院, 長春 130022;2. 長春師范大學 教育學院, 長春 130032; 3. 吉林農業大學 信息技術學院, 長春 130118)

聚類分析是一種將數據集按相似性進行分組的方法, 其目的是為使組內的數據更相似, 同時使組間的數據差異更大[1]. 聚類常用于數據挖掘、 模式識別、 決策支持、 機器學習和圖像分割等領域[2].k-means是最流行的聚類算法之一, 具有實現簡單、 執行效率高等優點, 但易陷入局部最優解[3], 導致聚類性能不佳.

針對上述問題, 目前已提出了多種改進方案. Likas等[4]提出了全局k-means算法, 首先使用數據集的質心作為第一個簇中心, 然后逐個增加簇中心并使用k-means算法找到收斂位置, 以提高算法的聚類精度; Nayak等[5]提出了一種基于粒子群優化的k-means聚類算法, 以獲得最優的聚類中心; 為選取合適的聚類中心, Erisoglu等[6]提出了一種根據變異系數和相關系數計算k-means初始聚類中心的算法; Rahman等[7]提出了一種基于遺傳算法的聚類技術, 通過改進初始種群的選擇方法產生高質量的聚類中心; 邢長征等[8]提出了一種基于平均密度優化初始聚類中心的k-means算法, 有效提高了算法的聚類精度; Tzortzis等[9]提出了根據方差為簇分配權重的方法, 限制了大方差簇的出現, 并且提高了求解精度; Malinen等[10]在k-means算法分配階段通過匈牙利算法解決各簇分配問題, 使簇之間達到平衡; Pham等[11]提出了一種增量式搜索策略減少算法對初始中心的依賴性; Bagirov[12]通過最小化提出的輔助聚類函數計算新增聚類中心的起點, 有效提升了全局k-means算法的精度.

上述算法雖然精度提升明顯, 但與k-means算法相比時間復雜度較高. Ismkhan[13]以k-means為基礎提出了一種新的迭代聚類(I-k-means-+)算法. I-k-means-+算法時間復雜度較低, 與k-means算法基本相當, 且在一定程度上提高了k-means算法的聚類精度. I-k-means-+算法利用數據點到有用中心的距離選擇k個初始中心, 然后通過不斷地劃分、 刪除簇優化k-means算法的目標函數值. 但因隨機劃分方式導致聚類結果不穩定, 聚類精度仍有較大提升空間. 針對I-k-means-+算法存在的問題, 本文提出一種基于min-max準則與區域劃分的I-k-means-+聚類算法. 該算法在選擇初始中心時, 計算數據到最近中心的距離, 優先選擇距離較遠的數據點作為新的聚類中心, 以避免初始中心過于密集的情況; 采用多區域劃分的策略增加候選中心的多樣性; 通過重新選擇分裂簇, 并與原刪除簇再次配對提高配對成功率.

1 I-k-means-+算法

假設給定一組具有N個樣本的數據集X={x1,x2,…,xN},xi∈D(i=1,2,…,N), 聚類的目的是將數據集劃分為k個互不相交的子集(簇){S1,S2,…,Sk}, 聚類中心集合為C={C1,C2,…,Ck}.

k-means算法使用誤差平方和(SSE)作為衡量聚類效果的指標. 對于給定的解S=(S1,S2,…,Sk), SSE的計算公式為

(1)

(2)

其中dis(p,Ci)為樣本點p到所屬聚類中心Ci的歐氏距離.I-k-means-+算法首先計算每個數據點的有用中心.

定義1如果不存在中心Cy滿足如下條件:

(dis(p,Cy)

則稱中心Cx為數據點p的有用中心.

先通過

(3)

計算每個數據點p的權重, 即V1(p,C), 根據權重選擇k個初始聚類中心, 并使用k-means算法收斂為解S, 其中Hp是數據點p的有用中心集合; 然后選擇增益較大的簇Si與損失較小的簇Sj, 刪除簇Sj并劃分簇Si, 使用t-k-means[13]收斂為解S′; 最后保留S和S′中精度最高的解.增益(Gain)和損失(Cost)的計算公式分別為

(4)

(5)

其中Zp是數據點p的次近中心。在實際應用中, 各中心之間的分布并非絕對均勻, 不同區域的聚類中心密集程度不同.由I-k-means-+算法過程可知, 該算法的初始中心選擇方法僅考慮有用中心對數據點權重的影響, 當有用中心與所有中心的數量差距較大時, 有用中心很難反應出所有中心的分布情況.從而導致算法選擇的多個初始中心在同一個簇中, 而有的簇沒有聚類中心, 如圖1所示.I-k-means-+算法的聚類精度易受初始中心影響, 圖1的初始解較差更易使算法陷入局部最優解, 降低算法的求解精度.

圖1 I-k-means-+算法在k=8時選擇的初始中心Fig.1 Initial center chosen by I-k-means-+ algorithm when k=8

此外, I-k-means-+算法中只有分裂簇與刪除簇配對成功時, 才能提高聚類精度, 而I-k-means-+算法中每次迭代僅進行一次分裂簇與刪除簇的配對, 且易出現配對失敗的情況, 影響算法收斂精度. I-k-means-+算法的劃分與刪除簇步驟中通過隨機選擇分裂簇中的一個數據點作為新中心, 該方法的隨機性較大且選擇不同的新中心其解的收斂結果不同, 從而導致聚類結果的穩定性變差.

2 I-k-means-+算法的優化改進

針對I-k-means-+算法聚類精度有待優化與聚類結果不穩定的問題, 本文提出一種基于min-max準則與區域劃分的I-k-means-+聚類算法, 即MR-k-means-+算法(I-k-means-+clustering algorithm based on min-max criterion and region division). 算法提出min-max準則, 在式(3)中引入數據到最近中心的距離并計算數據點的權重, 選擇權重最大的作為新的聚類中心, 以此避免初始聚類中心密集的情況. 當配對失敗時重新選擇分裂簇與原刪除簇再次配對, 以提高配對成功率, 進一步提高聚類精度. 針對I-k-means-+聚類結果不穩定的情況, 本文算法通過多區域劃分的策略選擇多個候選中心, 以增加解的多樣性, 從而提高聚類的精度與穩定性.

2.1 基于min-max準則的中心選擇策略

I-k-means-+聚類算法的中心選擇策略可能會導致初始聚類中心分布不均, 即存在多個中心聚集在同一簇中, 而有的簇沒有聚類中心的問題. 從而降低初始解的精度, 導致算法的聚類精度較差. 為避免初始聚類中心分布不均的問題, 本文算法在新中心的選擇中考慮了其他中心的分布情況. 若參與計算的中心數量過多, 雖能改善聚類中心的分布效果, 但極大降低了算法的效率. 本文提出min-max準則, 該準則選擇新的聚類中心時, 會先計算每個數據點到最近中心的距離(minimum distance), 然后優先選擇距離最大(maximum distance)的數據點作為新的聚類中心. 令Q(p,C)表示數據點p與中心集合C中各中心距離的最小值計算公式為

(6)

將Q(p,C)代入式(3)得到本文的中心評價公式為

V2(p,C)=V1(p,C)×α+Q(p,C)×β.

(7)

如圖2所示, 利用式(7)可較大程度地避免兩個中心在同一個簇中的情況, 保證中心分布更均勻.與I-k-means-+初始化方法相比, 本文初始化方法在圖1數據集上, 避免了多個中心聚集在同一個簇的情況, 選擇的中心分布更均勻, 且初始解的精度較前者有較大提升. 此外, I-k-means-+初始化方法提出有用中心的概念是為減少初始化部分的計算量, 本文利用I-k-means-+算法已有的距離信息, 在不增加初始化方法時間復雜度的前提下改進其初始中心的選擇策略, 并提高聚類精度.

在式(7)中通過參數α和β分別調整有用中心和最近中心在最終結果中所占的比例,α和β都在[0,1]內.當β=0時, 式(7)等價于式(3); 當α=0時, 式(7)等價于式(6).

2.2 多區域劃分刪除策略

為避免只選擇一個隨機數據點作為候選中心導致的聚類結果不穩定與精度較低的問題, 本文提出多區域劃分的策略獲取更多的候選中心, 通過增加解的多樣性提高聚類精度與穩定性.

該策略將分裂簇Si中的數據點分割到不同的區域, 從每個區域挑選一個候選中心.分割區域的數量對本文算法的效率和精度有重要影響, 分割的區域過多, 會增加距離計算次數, 導致算法的時間復雜度過高; 分割的區域過少, 會降低算法的精度.因此, 需要在精度與時間復雜度之間做一個平衡.本文將分裂簇Si的數據點分割到兩個不同的區域中, 第一個區域以中心Ci為圓心, 以Ci到簇內最遠點距離的1/2為半徑, 劃分成一個圓形區域.在簇Si中, 除第一區域外的其他數據點作為第二區域的數據點, 然后分別在第一和第二區域中選擇距離Ci最遠的點作為候選中心M1和M2, 如圖3所示.最后隨機從Si中選擇一個數據點作為第三個候選中心M3.與原算法只有一個候選中心相比, 該策略增加了解的多樣性.

本文將Ci作為第一個中心, 依次從候選中心集中選出一個候選中心作為第二個中心, 然后使用簇Si中包含的所有數據點, 運行2-k-means(k=2的k-means算法)迭代一次, 選擇分裂后SSE值最小的中心, 替換原來簇中心Ci和Cj.此時, SSE的下降幅度和迭代次數呈衰減趨勢, 本文為節省迭代時間且能找到收斂效果較好的中心, 故2-k-means只迭代一次.

2.3 基于SSE的簇對再匹配方法

I-k-means-+算法中僅進行一次分裂簇與刪除簇的配對, 而配對的成功率對聚類精度有較大影響. 本文提出基于SSE的簇對再匹配方法, 當配對失敗時重新選擇分裂簇與原刪除簇再次配對, 以提高配對成功率, 進而提高聚類精度.

本文在簇Si和Sj配對失敗后, 即SSE(X,S′)>SSE(X,S), 重新選擇增益最大的簇Sm(Sm≠Si), 再次執行劃分Sm與刪除Sj的操作, 并使用Hamerly[14]的方法收斂為解S″.若SSE(X,S″)

2.4 算法流程

MR-k-means-+算法整體流程如下.

輸入: 數據集X, 聚類個數k;

輸出: 解S;

步驟1) 簇的初始狀態均設為允許劃分與刪除, 在數據集X中選擇第一維度最小的數據點作為中心C1;

步驟2) 用式(7)計算每個數據點的權重V1(p,C), 選擇權重最大的數據點為中心Cm(m=2,3,…,k-1), 并使用Hamerly收斂為解S;

步驟3) 選擇增益最大的簇Si且該簇應允許劃分, 若沒有該簇或有k/2個簇的增益大于Si, 則結束;

步驟4) 在滿足下列3個條件的簇中, 找到損失最小的簇Sj; 若沒有, 則結束:

①Si≠Sj且Cost(Sj)

②Si與Sj可以配對且Si與Sj互不為鄰簇[13];

③Sj應允許刪除;

步驟5) 若有k/2個簇的損失小于Sj, 則Si設為不可劃分的簇, 并轉步驟3);

步驟6) 設置C′=C后, 按多區域劃分刪除策略劃分簇Si, 并選擇候選中心M1,M2,M3, 將簇中心Ci作為第一中心, 分別將候選中心作為第二中心, 使用2-k-means迭代一次, 保留精度最高的一組替換Ci和Cj;

步驟7) 根據步驟6)的中心集C, 使用Hamerly將數據集X收斂為解S′, 若SSE(X,S)>SSE(X,S′), 則執行如下操作:

①Si和Sj標記為不可刪除且設置Sj的強鄰簇[13]為不可刪除;

②S=S′且設置Si和Sj的強鄰簇為不可刪除;

步驟8) 若SSE(X,S)

① 找到增益最大簇Sz(Sz≠Si),C=C′并選擇簇Sz中一個隨機點替換Cj, 使用Hamerly收斂為解S″;

② 若SSE(X,S″)

步驟9) 若成功配對的數量大于k/2, 則算法結束; 否則, 重復執行步驟3)～9).

2.5 計算復雜度分析

本文算法主要由三部分組成: 第一部分為基于min-max準則的中心選擇策略, 該部分通過式(7)計算數據點的權重并選擇初始聚類中心, 其時間復雜度為O(nkd+k2d); 第二部分為多區域劃分刪除策略, 其中劃分階段時間復雜度為O(lnd), 刪除階段時間復雜度為O(ld), 該部分時間復雜度為O(lnd); 第三部分為基于SSE的簇對再匹配方法, 該部分的時間復雜度為O(lkdn+lk2d).所以本文算法的時間復雜度為O(lkdn+lk2d), 其中l表示劃分刪除步驟的迭代次數,n表示樣本數,k表示聚類中心個數,d表示樣本維度.

3 實 驗

3.1 實驗環境與數據

實驗環境配置為Intel(R) Core(TM) i5-6200U CPU @ 2.30 GHz 2.40 GHz, Windows10 64 位操作系統, 內存12 GB, VS 2013開發平臺, 所有算法均使用C++語言編程實現.

為驗證MR-k-means-+算法的有效性, 實驗選用5個UCI數據集(https://archive.ics.uci.edu/ml/index.php), 將本文算法與其他3種算法進行性能對比. 選取數據集的信息列于表1.

表1 5個UCI數據集信息Table 1 Information of five UCI datasets

3.2 實驗結果與分析

實驗中的對比算法為k-means算法、 聚類中心初始化算法k-means++[15]、 I-k-means-+(IK-+)算法及本文的MR-k-means-+(MRK-+)算法. 為避免聚類中心數量過大導致的無意義聚類, 本文對數據個數小于1 000的k值設置為5,10,15,20, 數據個數大于1 000的k值設置為5,10,20,50. 本文算法參數設置:α=0.5,β=0.5. 為避免算法中聚類精度與運行時間的隨機性, 所有算法均運行50次取平均值.

3.2.1 求解精度測試

算法的求解精度以收斂后的SSE衡量. 對于一個給定的算法, 為量化其相對于IK-+算法的精度提升效果, 其精度提升百分數U的計算公式可表示為

U=(E1-E2)/E1×100%,

(8)

其中E1表示IK-+算法的目標函數值,E2表示對比算法的目標函數值.

不同算法在測試數據集上的運行結果列于表2. 由表2可見, 在20次對比實驗中, 有16次本文算法是所有算法中精度最高的. 各優化算法精度提升百分數列于表3. 由表3可見, 與IK-+算法相比,k-means算法的精度平均下降了149.64%,k-means++算法下降了5.69%, 而本文算法的聚類精度與IK-+算法相比平均提升了6.47%, 當k=50時提升了18.6%, 本文算法有效提升了IK-+算法的聚類精度.

表2 不同算法在測試數據集上的運行結果Table 2 Running results of different algorithms on test datasets

表3 各優化算法精度提升百分數Table 3 Accuracy improvement percentage of each optimization algorithm %

3.2.2 穩定性測試

為測試聚類結果的穩定性, 本文采用方差進行衡量. 在不同數據集下, 將本文提出的MRK-+算法與IK-+算法使用不同k值分別運行50次, 并根據SSE計算不同k值下運行結果的方差, 其方差對比結果如圖4所示. 由圖4可見, 與IK-+算法相比, 除數據集Iris中k=10和k=20外, 本文算法的方差均可忽略不計. 在20次方差對比中, 其中有17次本文算法的方差優于IK-+算法, 并有2次方差相等, 表明本文算法與IK-+算法相比聚類結果更穩定.

圖4 本文算法與IK-+算法的方差對比結果Fig.4 Variance comparison results between proposed algorithm and IK-+ algorithm

3.2.3 運行效率對比

令T1表示IK-+算法的運行時間,T2表示某個給定算法的運行時間, 則該算法相對于IK-+算法的時間加速百分數L計算公式為

(9)

圖5為本文算法相對于IK-+算法的時間加速比結果. 由圖5可見, 本文算法在k較小時速度提升明顯,k較大時速度略有下降, 平均速度與I-k-means-+算法基本相當.

圖5 本文算法相對于IK-+算法的時間加速比Fig.5 Time speedup ratio of proposed algorithm compared to IK-+ algorithm

綜上所述, 針對I-k-means-+算法聚類結果不穩定, 并且求解精度有待提高的問題, 本文提出了一種基于min-max準則與區域劃分的I-k-means-+聚類算法. 提出min-max準則, 以避免初始化中心過度密集的情況, 提高初始解的精度; 將分裂簇分割為不同區域, 從中選擇多個候選中心, 增加解的多樣性, 提高聚類結果的穩定性; 當配對失敗后, 重新選擇分裂簇與原刪除簇再次配對, 以提高配對成功率, 進一步提高算法的求解精度. 實驗結果表明, 與I-k-means-+算法相比, 本文算法與前者的運行效率基本相當, 聚類精度平均提升6.47%, 多次運行結果的目標函數值波動更小、 聚類結果更穩定.