胡雅婷, 陳營(yíng)華, 寶音巴特, 曲福恒, 李卓識(shí)

(1. 吉林農(nóng)業(yè)大學(xué) 信息技術(shù)學(xué)院, 長(zhǎng)春 130118； 2. 吉林省科學(xué)技術(shù)工作者服務(wù)中心, 長(zhǎng)春 130021；3. 長(zhǎng)春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院, 長(zhǎng)春 130022)

聚類(lèi)分析[1-4]是數(shù)據(jù)分析的一種基本方法, 既可作為一種無(wú)監(jiān)督機(jī)器學(xué)習(xí)方法獨(dú)立發(fā)現(xiàn)未標(biāo)簽數(shù)據(jù)結(jié)構(gòu), 完成數(shù)據(jù)分類(lèi)、 壓縮等工作, 也可與其他方法相結(jié)合以提高其性能.k-means算法是一種經(jīng)典的劃分聚類(lèi)算法, 通過(guò)最小化類(lèi)內(nèi)方差之和獲得硬聚類(lèi)劃分, 因其計(jì)算簡(jiǎn)單、 聚類(lèi)效率高等優(yōu)點(diǎn)廣泛應(yīng)用于模式識(shí)別、 機(jī)器學(xué)習(xí)、 圖像處理及故障診斷等領(lǐng)域[5-8]. 但k-means聚類(lèi)結(jié)果對(duì)初始聚類(lèi)中心依賴較大, 導(dǎo)致算法易陷入局部極小值[9]. 為改善該問(wèn)題, 可通過(guò)改進(jìn)中心初始化方法降低初始化對(duì)算法的影響, 以獲得目標(biāo)函數(shù)的更優(yōu)解[10-12].k-means++算法[13]通過(guò)隨機(jī)選擇程序?qū)崿F(xiàn)初始化中心對(duì)整個(gè)數(shù)據(jù)空間的全覆蓋, 在理論上保證了獲得聚類(lèi)劃分可達(dá)到近似最優(yōu). 該類(lèi)算法計(jì)算效率相對(duì)較高, 但對(duì)目標(biāo)函數(shù)解的改善程度有待提高. 全局k-means聚類(lèi)算法[14-17]作為一種增量式k-means聚類(lèi)算法, 以每次迭代增加一個(gè)聚類(lèi)中心的方式完成聚類(lèi)數(shù)目的遞增, 通過(guò)在數(shù)據(jù)中選擇使目標(biāo)函數(shù)值減少最多的數(shù)據(jù)點(diǎn)作為新增的聚類(lèi)中心. 該算法明顯提升了目標(biāo)函數(shù)解的質(zhì)量, 但計(jì)算效率較低.

針對(duì)上述改進(jìn)算法存在的問(wèn)題, Tzortzis等[18]提出了MinMaxk-means聚類(lèi)算法. MinMaxk-means 算法以最小化最大的方差為聚類(lèi)準(zhǔn)則確定目標(biāo)函數(shù), 該準(zhǔn)則能改善k-means算法迭代中產(chǎn)生過(guò)大方差類(lèi)的問(wèn)題, 從而得到目標(biāo)函數(shù)更優(yōu)的解. 由于直接優(yōu)化最小化最大的方差準(zhǔn)則函數(shù)對(duì)應(yīng)一個(gè)非連續(xù)可微的優(yōu)化問(wèn)題, 因此MinMax算法通過(guò)優(yōu)化加權(quán)k-means目標(biāo)函數(shù)得到該問(wèn)題的近似解. 與k-means及其初始化中心改進(jìn)算法相比, MinMaxk-means算法能顯著改善k-means算法目標(biāo)函數(shù)解的質(zhì)量, 計(jì)算效率比全局k-means及其改進(jìn)算法更高. 但為了避免產(chǎn)生空類(lèi)或單點(diǎn)類(lèi), MinMaxk-means算法采用自適應(yīng)機(jī)制動(dòng)態(tài)地調(diào)整參數(shù)p, 而參數(shù)p的合理取值區(qū)間為[0,1), 自適應(yīng)調(diào)整不能保證其取值始終位于該區(qū)間內(nèi), 使算法存在產(chǎn)生空解的可能性.而且實(shí)驗(yàn)結(jié)果表明, 初始化中心對(duì)MinMaxk-means聚類(lèi)結(jié)果影響較大, 初始化不當(dāng)可導(dǎo)致迭代次數(shù)多、 迭代時(shí)間長(zhǎng)、 目標(biāo)函數(shù)解的質(zhì)量差等問(wèn)題. 為進(jìn)一步改進(jìn)MinMaxk-means算法性能, 受全局k-means增量式算法啟發(fā), 本文通過(guò)引入增量式聚類(lèi)思想改進(jìn)MinMaxk-means算法存在的上述問(wèn)題. 對(duì)于給定的聚類(lèi)數(shù)目k, 首先以較小的kmin值作為起始聚類(lèi)數(shù)目, 通過(guò)對(duì)一個(gè)或多個(gè)聚類(lèi)劃分進(jìn)行分裂, 以增加聚類(lèi)數(shù)目直至達(dá)到指定的k值.與現(xiàn)有的增量式全局k-means算法每次迭代都需從數(shù)據(jù)集中篩選出新增的聚類(lèi)中心不同, 本文算法通過(guò)分裂已有聚類(lèi)劃分完成增量式聚類(lèi), 并引入均衡化準(zhǔn)則確定分裂對(duì)象, 其增量式過(guò)程計(jì)算效率更高, 同時(shí)能明顯改善MinMaxk-means算法目標(biāo)函數(shù)解的質(zhì)量.

1 MinMax k-means聚類(lèi)算法

MinMaxk-means聚類(lèi)[18]是k-means聚類(lèi)的一種改進(jìn)算法, 通過(guò)改進(jìn)k-means算法的目標(biāo)函數(shù)改善其在迭代過(guò)程中易陷入局部最小值問(wèn)題, MinMaxk-means的目標(biāo)函數(shù)建立在最小化最大的類(lèi)內(nèi)方差準(zhǔn)則上. 假設(shè)X是給定的數(shù)據(jù)集合,k是聚類(lèi)數(shù)目, 則其目標(biāo)函數(shù)為

(1)

其中V={v1,v2,…,vk}為聚類(lèi)中心集合,Xi(1≤i≤k)為第i個(gè)聚類(lèi)劃分, 存儲(chǔ)數(shù)據(jù)X中所有距離中心vi最近的數(shù)據(jù)點(diǎn).目標(biāo)函數(shù)等于X中所有距離中心vi最近的數(shù)據(jù)點(diǎn)與中心vi之間距離的平方和.

由于直接優(yōu)化目標(biāo)函數(shù)(1)對(duì)應(yīng)一個(gè)非連續(xù)可微的優(yōu)化問(wèn)題, 無(wú)法直接利用迭代算法進(jìn)行求解, 因此, Tzortzis等[18]對(duì)目標(biāo)函數(shù)(1)進(jìn)行了近似處理, 改寫(xiě)后的近似目標(biāo)函數(shù)為

(2)

為了抑制某類(lèi)方差之和的值過(guò)大, 式(2)將參數(shù)p的取值范圍限定為區(qū)間[0,1).在迭代過(guò)程中, 為避免空類(lèi)問(wèn)題, 采用自適應(yīng)策略更新迭代過(guò)程中的參數(shù)p, 設(shè)參數(shù)p的最大取值pmax并更新步長(zhǎng)pstep, 參數(shù)p更新過(guò)程為

p=pmax-pstep.

(3)

(4)

MinMaxk-means聚類(lèi)算法流程如下：

步驟1) 初始化參數(shù)pstep,pmax,β及聚類(lèi)數(shù)目k、 迭代最大次數(shù)tmax和收斂精度δ；

步驟2) 初始化聚類(lèi)中心V(0)；

步驟3) 利用V(0)與給定的參數(shù), 優(yōu)化目標(biāo)函數(shù)(2)得到聚類(lèi)中心V′[18]；

步驟4) 以V′作為k-means聚類(lèi)的初始化中心, 運(yùn)行k-means聚類(lèi)算法直至收斂, 得到聚類(lèi)中心V.

由于k-means與MinMaxk-means聚類(lèi)算法的目標(biāo)函數(shù)不同, 因此算法流程中前三步得到的聚類(lèi)中心是最優(yōu)化MinMaxk-means目標(biāo)函數(shù)的結(jié)果. 而MinMaxk-means聚類(lèi)的最終目標(biāo)是優(yōu)化k-means的目標(biāo)函數(shù), 因而在其最后一步需要運(yùn)行k-means算法以獲得優(yōu)化k-means目標(biāo)函數(shù)對(duì)應(yīng)的最終聚類(lèi)結(jié)果. 本文將完整的4個(gè)步驟稱為“MinMaxk-means”聚類(lèi)或者簡(jiǎn)稱為“MinMax”聚類(lèi), 而文獻(xiàn)[18]將前三步稱為“MinMax”聚類(lèi), 將完整的四步稱為“MinMax+k-means”聚類(lèi), 本質(zhì)相同.

在MinMaxk-means算法的迭代過(guò)程中, 通過(guò)動(dòng)態(tài)調(diào)整參數(shù)p處理空類(lèi)與單點(diǎn)類(lèi)問(wèn)題. 但參數(shù)p的合理取值區(qū)間為[0,1), 自適應(yīng)地調(diào)整不能保證其取值始終位于該區(qū)間內(nèi), 使得算法可能產(chǎn)生空解. 且通過(guò)實(shí)驗(yàn)發(fā)現(xiàn), 初始化中心對(duì)MinMaxk-means聚類(lèi)結(jié)果與效率均有較大影響, 初始化不當(dāng)可導(dǎo)致迭代次數(shù)多、 迭代時(shí)間長(zhǎng)的問(wèn)題, 空解的產(chǎn)生也與算法初始化聚類(lèi)中心的選擇有關(guān). 在UCI機(jī)器學(xué)習(xí)典型數(shù)據(jù)集Iris上分別運(yùn)行MinMaxk-means和k-means算法. 圖1為MinMaxk-means算法在不同聚類(lèi)數(shù)目下的運(yùn)行結(jié)果(算法參數(shù)設(shè)置與文獻(xiàn)[18]一致, 運(yùn)行50次取平均值). 由圖1可見(jiàn), MinMaxk-means算法存在如下問(wèn)題： 1) 算法有空解產(chǎn)生, 且隨著聚類(lèi)數(shù)目的增加, 空解產(chǎn)生比例呈逐漸增大的趨勢(shì)； 2) 算法并不能保證在給定的迭代次數(shù)內(nèi)收斂. 圖2為不同聚類(lèi)數(shù)目下MinMaxk-means與k-means算法聚類(lèi)迭代次數(shù)與運(yùn)行時(shí)間的比值. 由圖2可見(jiàn), MinMaxk-means算法平均迭代次數(shù)明顯高于k-means算法, 從而導(dǎo)致MinMaxk-means算法計(jì)算效率較低, 運(yùn)行時(shí)間明顯比k-means算法長(zhǎng).

圖1 MinMax k-means算法在不同 聚類(lèi)數(shù)目下的運(yùn)行結(jié)果Fig.1 Running results of MinMax k-means algorithms for different clustering numbers

圖2 不同聚類(lèi)數(shù)目下MinMax k-means 與k-means算法的比值Fig.2 Ratios of MinMax k-means and k-means algorithms for different clustering numbers

2 增量式MinMax k-means聚類(lèi)算法設(shè)計(jì)

2.1 全局k-means算法

為避免k-means算法對(duì)初始化中心敏感的問(wèn)題, Likas等[17]提出了一種全局k-means聚類(lèi)算法, 該算法通過(guò)增量式增加聚類(lèi)中心獲取更優(yōu)的目標(biāo)函數(shù)解, 降低了k-means算法對(duì)初始化的依賴程度. 全局k-means算法流程如下：

步驟1) 初始化聚類(lèi)數(shù)目k*=1, 初始化中心V為所有數(shù)據(jù)的均值；

步驟3) 以V′作為初始化中心, 運(yùn)行k-means算法至收斂, 收斂后中心賦值給V；

步驟4) 如果k*=k, 則算法停止； 否則, 轉(zhuǎn)步驟2).

全局k-means聚類(lèi)算法降低了k-means算法對(duì)初始化的依賴程度, 但計(jì)算效率較低, 原因如下：

1) 在步驟2)中, 遞增式增加一個(gè)中心, 全局k-means算法需要遍歷所有數(shù)據(jù)點(diǎn), 并選擇其中對(duì)應(yīng)的目標(biāo)函數(shù)值最小的數(shù)據(jù)點(diǎn)作為下一個(gè)中心, 這一原則基于k-means算法的目標(biāo)函數(shù)最小化; 增量式選擇聚類(lèi)中心時(shí)需計(jì)算各數(shù)據(jù)點(diǎn)之間的距離, 其計(jì)算量是O(N2s), 其中N為數(shù)據(jù)個(gè)數(shù),s為數(shù)據(jù)維數(shù), 而k-means每次迭代的計(jì)算量為O(Nsk).一般情況下k?N, 使得全局k-means算法中心選擇的計(jì)算量過(guò)大.

2) 在步驟3)中, 對(duì)每個(gè)單獨(dú)的聚類(lèi)數(shù)目k*(1

2.2 改進(jìn)算法

本文采用全局k-means算法的增量式聚類(lèi)思想降低MinMaxk-means算法對(duì)初始化敏感的問(wèn)題. 盡管全局k-means算法的增量式聚類(lèi)改善了聚類(lèi)結(jié)果對(duì)初始化的敏感性, 但與原始k-means算法相比, 其增加了計(jì)算量, 計(jì)算效率非常低. 因此, 不能直接套用全局k-means算法的增量模式. 本文采用完全不同的增量式過(guò)程完成聚類(lèi)數(shù)目的遞增, 從而提升其計(jì)算效率.

針對(duì)全局k-means算法選擇增量中心的過(guò)程計(jì)算量過(guò)大問(wèn)題, 本文進(jìn)行如下改進(jìn)以提升其計(jì)算效率：

1) 針對(duì)已有的聚類(lèi)劃分進(jìn)行操作, 并非針對(duì)數(shù)據(jù)點(diǎn)進(jìn)行操作, 由于聚類(lèi)劃分?jǐn)?shù)目遠(yuǎn)小于數(shù)據(jù)點(diǎn)的個(gè)數(shù), 因此從遍歷選擇的角度具有優(yōu)勢(shì)；

2) 對(duì)每個(gè)劃分采用分裂方式完成聚類(lèi)數(shù)目的增加, 分裂可保證目標(biāo)函數(shù)值是下降的, 這與優(yōu)化k-means算法目標(biāo)函數(shù)一致；

3) 借鑒MinMaxk-means算法的目標(biāo)函數(shù)原則, 并在其基礎(chǔ)上進(jìn)行改進(jìn), 以快速確定被分裂的聚類(lèi)劃分.

MinMaxk-means聚類(lèi)準(zhǔn)則是最小化最大的類(lèi)內(nèi)方差, 以盡量保證各類(lèi)內(nèi)的方差均衡. 但對(duì)于不同聚類(lèi)中數(shù)據(jù)數(shù)目不一致、 具有嚴(yán)重差異的問(wèn)題, MinMaxk-means聚類(lèi)準(zhǔn)則并未考慮. 此時(shí), 對(duì)數(shù)據(jù)數(shù)目過(guò)大的劃分進(jìn)行分裂可得到更均衡的類(lèi)內(nèi)方差結(jié)果. 本文采用各類(lèi)數(shù)據(jù)均衡的思想確定被分裂的聚類(lèi)劃分, 避免不同聚類(lèi)劃分之間數(shù)據(jù)不平衡導(dǎo)致的類(lèi)內(nèi)方差差異過(guò)大問(wèn)題, 從而降低算法整體目標(biāo)函數(shù)值. 同時(shí), 由此產(chǎn)生的計(jì)算量極低, 幾乎可以忽略不計(jì), 只需要記錄各聚類(lèi)劃分的數(shù)據(jù)數(shù)目即可.

針對(duì)全局k-means算法時(shí)間復(fù)雜度較高的問(wèn)題, 本文進(jìn)行如下改進(jìn)：

軍功爵制是對(duì)五等爵制分封體制的一種繼承，然而它卻與五等爵制有著明顯的差異和不同。五等爵制規(guī)定，天子、諸侯、大夫、士農(nóng)工的世襲而定，“天子一位，公一位，侯一位，伯一位，子，男一位，凡五等也”[13]P782統(tǒng)治者內(nèi)部等級(jí)和被統(tǒng)治著的身份地位也是受到五爵制的限定?！疤熳诱?，爵稱也，爵所以稱天下者何？王者父天母地，為天之子也。所以名之為公候者何？公者，通也，公正無(wú)私意也。侯者，候也，候逆順也。伯者，白也。子者，孳也，孳孳無(wú)己也，男者，任也?！盵14]P2而軍功爵制則是春秋時(shí)期，諸侯根據(jù)當(dāng)時(shí)的政治形勢(shì)和社會(huì)環(huán)境對(duì)庶民做出的一種妥協(xié)。

1) 同時(shí)分裂多個(gè)劃分, 一次性遞增多個(gè)聚類(lèi)中心以快速增加聚類(lèi)數(shù)目, 從而不必對(duì)所有的聚類(lèi)數(shù)目k*(1

2) 對(duì)每個(gè)增量過(guò)程中限制算法迭代次數(shù)不超過(guò)某個(gè)給定的較小值, 以降低計(jì)算量. 由實(shí)驗(yàn)結(jié)果可知, 降低迭代次數(shù)并不會(huì)影響該算法獲取解的質(zhì)量. 這是因?yàn)楸疚乃惴ㄔ诘^(guò)程中采用了優(yōu)化能力更強(qiáng)的MinMaxk-means迭代算法, 其優(yōu)化能力優(yōu)于全局k-means所采用的原始k-means聚類(lèi)算法.

對(duì)于一個(gè)給定的數(shù)據(jù)集合X及給定的聚類(lèi)個(gè)數(shù)k, 本文算法流程如下：

步驟1) 參數(shù)設(shè)定.設(shè)置最小聚類(lèi)數(shù)目kmin、 聚類(lèi)數(shù)目遞增量kstep和最大迭代次數(shù)tmax；

步驟2) 計(jì)算初始聚類(lèi)劃分.令k*=kmin, 在保證迭代次數(shù)不超過(guò)tmax的前提下運(yùn)行MinMaxk-means算法對(duì)數(shù)據(jù)集X進(jìn)行聚類(lèi), 記錄聚類(lèi)結(jié)果中各聚類(lèi)劃分內(nèi)部數(shù)據(jù)數(shù)目；

步驟3) 分裂聚類(lèi)劃分.

① 計(jì)算分裂聚類(lèi)數(shù)目ksplit: 若kstep>k*, 則ksplit=k*, 否則,ksplit=kstep; 若k*+ksplit>k, 則令ksplit=k-k*；

② 確定被分裂的聚類(lèi)劃分: 對(duì)已有聚類(lèi)劃分按數(shù)據(jù)數(shù)目從大到小排序, 選取前ksplit個(gè)劃分標(biāo)記為待分裂劃分, 其余聚類(lèi)劃分標(biāo)記為穩(wěn)定劃分；

③ 確定新的初始化聚類(lèi)中心Vinit: 令Vinit=?, 對(duì)每個(gè)待分裂劃分, 從其數(shù)據(jù)集合中隨機(jī)選取兩個(gè)數(shù)據(jù)并入到Vinit； 對(duì)每個(gè)穩(wěn)定劃分直接選取其數(shù)據(jù)中心加入到Vinit；

④ 計(jì)算新聚類(lèi)數(shù)目k*=k*+ksplit；

⑤ 根據(jù)初始中心Vinit、 聚類(lèi)數(shù)目k*和最大迭代次數(shù)tmax, 運(yùn)行MinMaxk-means算法得到新的聚類(lèi)劃分, 記錄各聚類(lèi)劃分中的數(shù)據(jù)點(diǎn)個(gè)數(shù)；

⑥ 若k*

步驟4) 以上述步驟獲取的k個(gè)聚類(lèi)中心作為初始化中心, 運(yùn)行k-means算法直至收斂, 得到最終的聚類(lèi)結(jié)果, 算法結(jié)束.

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)置

為驗(yàn)證本文算法的有效性, 將其與k-means聚類(lèi)及其改進(jìn)算法進(jìn)行比較, 對(duì)比算法包括原始k-means聚類(lèi)算法、 MinMaxk-means聚類(lèi)算法[18]和目前常用的中心初始化改進(jìn)算法k-means++算法[13]. 實(shí)驗(yàn)數(shù)據(jù)集為UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的典型數(shù)據(jù)集Iris(N=150,s=4)和Abalone_new(N=4 177,s=48), 其中N為數(shù)據(jù)個(gè)數(shù),s為數(shù)據(jù)維數(shù)； 所有算法的最大迭代次數(shù)為1 000； MinMaxk-means算法中參數(shù)采用文獻(xiàn)[18]中的推薦設(shè)置, 其中pmax=0.5,pstep=0.01,ε= 10-6,β=0.3.本文算法的參數(shù)設(shè)置為kmin=2, 增量聚類(lèi)的最大迭代次數(shù)tmax=5.本文同時(shí)對(duì)比了kstep在不同取值下的聚類(lèi)結(jié)果.實(shí)驗(yàn)結(jié)果取每種算法運(yùn)行50次的平均值.實(shí)驗(yàn)代碼以MATLAB編寫(xiě), 硬件配置為CPU： Intel Core i3, 3.40 GHz; 內(nèi)存12 GB.

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

3.2.1 與不同算法的對(duì)比結(jié)果

圖3 不同數(shù)據(jù)集上MinMax k-means與 k-means算法運(yùn)行時(shí)間的比值Fig.3 Ratios of running time of MinMax k-means and k-means algorithms on different data sets

圖3為不同數(shù)據(jù)集上MinMaxk-means與k-means算法運(yùn)行時(shí)間的比值. 由圖3可見(jiàn), 在不同數(shù)據(jù)集上MinMaxk-means和k-means算法的運(yùn)行時(shí)間比值在10～90內(nèi)變動(dòng). 圖4為本文算法kstep取不同值時(shí)與k-means算法運(yùn)行時(shí)間的比值. 由圖4可見(jiàn), 本文算法在參數(shù)kstep的不同取值下, 與k-means++算法運(yùn)行時(shí)間的比值均小于7, 有些結(jié)果甚至快于k-means++算法. 因此, 本文算法的計(jì)算效率顯著優(yōu)于MinMaxk-means算法.

Iris和Abalone_new數(shù)據(jù)集上各對(duì)比算法的目標(biāo)函數(shù)值分別列于表1和表2. 由表1和表2可見(jiàn), 不同數(shù)據(jù)集、 不同聚類(lèi)數(shù)目共計(jì)16組對(duì)比實(shí)驗(yàn)結(jié)果中, 其中15組實(shí)驗(yàn)結(jié)果本文算法優(yōu)于MinMaxk-means算法, 占比達(dá)93.75%, 表明本文算法對(duì)MinMax的求解精度有明顯優(yōu)化效果. 以Abalone_new數(shù)據(jù)集在參數(shù)設(shè)為kstep=1的情況為例, 其函數(shù)值的6次優(yōu)化結(jié)果百分?jǐn)?shù)為0.6%～21%, 其他數(shù)據(jù)集與參數(shù)設(shè)置下的優(yōu)化幅度也接近或高于該百分?jǐn)?shù). 在次于MinMaxk-means算法的一組實(shí)驗(yàn)數(shù)據(jù)上, 本文算法得到的仍是所有對(duì)比算法中的次優(yōu)結(jié)果. 這里未列出空解產(chǎn)生的比例以及算法未收斂的比例. 對(duì)于所有實(shí)驗(yàn)數(shù)據(jù)集, 本文算法都能正常收斂, 并無(wú)空解產(chǎn)生, 表明本文算法可避免MinMaxk-means收斂速度慢、 易產(chǎn)生空解的問(wèn)題. 對(duì)比實(shí)驗(yàn)結(jié)果表明, 無(wú)論在算法的運(yùn)行時(shí)間上, 還是在目標(biāo)函數(shù)值優(yōu)化上, 本文算法均明顯改善了MinMaxk-means算法存在的問(wèn)題.

在時(shí)間效率上, 如圖3和圖4所示, 在k-means算法的不同改進(jìn)算法中, 本文算法的計(jì)算效率最高, 其次是k-means++算法, MinMaxk-means算法的計(jì)算效率最低. 在聚類(lèi)算法目標(biāo)函數(shù)值上, 如表1和表2所示, 不同數(shù)據(jù)集、 不同聚類(lèi)數(shù)目共計(jì)16組對(duì)比實(shí)驗(yàn)結(jié)果中, 本文算法15次取得了最優(yōu)值, 12次取得了次優(yōu)值, 明顯優(yōu)于其他3種對(duì)比算法.

圖4 本文算法kstep取不同值時(shí)與k-means++算法運(yùn)行時(shí)間的比值Fig.4 Ratios of running time of proposed algorithm and k-means++ algorithm when kstep takes different values

表1 Iris數(shù)據(jù)集上各對(duì)比算法的目標(biāo)函數(shù)值

表2 Abalone_new數(shù)據(jù)集上各對(duì)比算法的目標(biāo)函數(shù)值

3.2.2 參數(shù)kstep對(duì)本文算法的影響

kstep的取值對(duì)本文算法的尋優(yōu)能力有一定影響.由表1和表2可見(jiàn), 當(dāng)k值較小(k<12),kstep取值為1,2時(shí)算法性能更好； 當(dāng)k值較大(k≥16),kstep取值為4,8時(shí)算法性能更好.由圖3和圖4可見(jiàn),kstep值越大, 本文算法的計(jì)算效率越高.這是因?yàn)殡S著kstep值的增加, 算法跳過(guò)的k值增多, 從而減少了迭代的總次數(shù).

綜上可見(jiàn), 本文算法改善了MinMaxk-means算法易產(chǎn)生空解、 收斂速度慢和計(jì)算效率較低的問(wèn)題, 并進(jìn)一步提升了MinMaxk-means算法目標(biāo)函數(shù)解的質(zhì)量. 對(duì)比實(shí)驗(yàn)結(jié)果表明, 本文算法具有較高的計(jì)算效率, 得到的目標(biāo)函數(shù)值明顯優(yōu)于其他對(duì)比算法.