基于min-max準(zhǔn)則與區(qū)域劃分的I-k-means-+聚類算法

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

(1. 長春理工大學(xué) 計算機科學(xué)技術(shù)學(xué)院, 長春 130022;2. 長春師范大學(xué) 教育學(xué)院, 長春 130032; 3. 吉林農(nóng)業(yè)大學(xué) 信息技術(shù)學(xué)院, 長春 130118)

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

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

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

1 I-k-means-+算法

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

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

(1)

(2)

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

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

(dis(p,Cy)

則稱中心Cx為數(shù)據(jù)點p的有用中心.

先通過

(3)

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

(4)

(5)

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

圖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-+算法中每次迭代僅進行一次分裂簇與刪除簇的配對, 且易出現(xiàn)配對失敗的情況, 影響算法收斂精度. I-k-means-+算法的劃分與刪除簇步驟中通過隨機選擇分裂簇中的一個數(shù)據(jù)點作為新中心, 該方法的隨機性較大且選擇不同的新中心其解的收斂結(jié)果不同, 從而導(dǎo)致聚類結(jié)果的穩(wěn)定性變差.

2 I-k-means-+算法的優(yōu)化改進

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

2.1 基于min-max準(zhǔn)則的中心選擇策略

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

(6)

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

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

(7)

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

在式(7)中通過參數(shù)α和β分別調(diào)整有用中心和最近中心在最終結(jié)果中所占的比例,α和β都在[0,1]內(nèi).當(dāng)β=0時, 式(7)等價于式(3); 當(dāng)α=0時, 式(7)等價于式(6).

2.2 多區(qū)域劃分刪除策略

為避免只選擇一個隨機數(shù)據(jù)點作為候選中心導(dǎo)致的聚類結(jié)果不穩(wěn)定與精度較低的問題, 本文提出多區(qū)域劃分的策略獲取更多的候選中心, 通過增加解的多樣性提高聚類精度與穩(wěn)定性.

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

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

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

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

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

2.4 算法流程

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

輸入: 數(shù)據(jù)集X, 聚類個數(shù)k;

輸出: 解S;

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

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

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

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

①Si≠Sj且Cost(Sj)

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

③Sj應(yīng)允許刪除;

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

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

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

①Si和Sj標(biāo)記為不可刪除且設(shè)置Sj的強鄰簇[13]為不可刪除;

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

步驟8) 若SSE(X,S)

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

② 若SSE(X,S″)

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

2.5 計算復(fù)雜度分析

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

3 實 驗

3.1 實驗環(huán)境與數(shù)據(jù)

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

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

表1 5個UCI數(shù)據(jù)集信息Table 1 Information of five UCI datasets

3.2 實驗結(jié)果與分析

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

3.2.1 求解精度測試

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

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

(8)

其中E1表示IK-+算法的目標(biāo)函數(shù)值,E2表示對比算法的目標(biāo)函數(shù)值.

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

表2 不同算法在測試數(shù)據(jù)集上的運行結(jié)果Table 2 Running results of different algorithms on test datasets

表3 各優(yōu)化算法精度提升百分?jǐn)?shù)Table 3 Accuracy improvement percentage of each optimization algorithm %

3.2.2 穩(wěn)定性測試

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

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

3.2.3 運行效率對比

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

(9)

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

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

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