一種基于改進(jìn)差分進(jìn)化的K?Means聚類算法研究

摘 "要： 為改進(jìn)傳統(tǒng)K?Means聚類算法中因隨機(jī)選取初始聚類中心而導(dǎo)致聚類結(jié)果不穩(wěn)定且效率低的缺點(diǎn)，提出一種基于改進(jìn)差分進(jìn)化的K?Means聚類算法（AGDE?KM）。首先，設(shè)計(jì)自適應(yīng)操作算子來(lái)提升算法前期的全局搜索能力和后期的收斂速度；其次，設(shè)計(jì)多變異策略并引入權(quán)重系數(shù)，在算法的不同進(jìn)化階段發(fā)揮不同變異策略的優(yōu)勢(shì)，平衡算法的全局和局部搜索能力，加快算法的收斂速度；最后，提出一種基于當(dāng)前種群最佳個(gè)體的高斯擾動(dòng)交叉操作，為個(gè)體提供更優(yōu)進(jìn)化方向的同時(shí)保持種群在“維”上的多樣性，避免算法陷入局部最優(yōu)。將算法停止執(zhí)行時(shí)輸出的最優(yōu)解作為初始聚類中心替代傳統(tǒng)K?Means隨機(jī)選取的聚類中心。將提出算法在UCI公共數(shù)據(jù)庫(kù)中的Vowel、Iris、Glass數(shù)據(jù)集和合成數(shù)據(jù)集Jcdx上進(jìn)行對(duì)比實(shí)驗(yàn)，誤差平方和（SSE）相對(duì)于傳統(tǒng)K?Means分別減小5.65%、19.59%、13.31%、6.1%，聚類時(shí)間分別減少83.03%、81.33%、77.47%、92.63%。實(shí)驗(yàn)結(jié)果表明，提出的改進(jìn)算法具有更快的收斂速度和更好的尋優(yōu)能力，顯著提升了聚類的效果、效率和穩(wěn)定性。

關(guān)鍵詞： K?Means聚類算法； 差分進(jìn)化算法； 多變異策略； 高斯擾動(dòng)； UCI數(shù)據(jù)庫(kù)； 聚類中心優(yōu)化

中圖分類號(hào)： TN911.1?34； TP301.6 " " " " " " " " " 文獻(xiàn)標(biāo)識(shí)碼： A " " " " " " " " "文章編號(hào)： 1004?373X（2024）18?0156?07

Research on K?Means clustering algorithm based on AGDE

LIU Hongda1， 2， WANG Fushun1， 2， SUN Xiaohua3， ZHANG Guanghui1， 2， WANG Bin1， 2， HE Zhenxue1， 2

（1. School of Information Science and Technology， Hebei Agricultural University， Baoding 071000， China;

2. Hebei Key Laboratory of Agricultural Big Data， Baoding 071000， China; 3. Hebei Software Institute， Baoding 071000， China）

Abstract： In order to improve the instability and low efficiency of clustering results caused by randomly selecting initial cluster centers in traditional K?Means clustering algorithms， a K?Means clustering algorithm based on adaptive guided differential evolution （AGDE?KM） is proposed. The adaptive operation operator is designed to improve the global search capability of the algorithm in the early stage and the convergence speed in the later stage. The multi?variation strategy is designed and the weight coefficient is introduced to play the advantages of different variation strategies in different evolutionary stages of the algorithm， balance the global and local search ability of the algorithm， and accelerate the convergence speed of the algorithm. A Gaussian perturbation crossover operation based on the best individual of the current population is proposed to provide a better evolutionary direction for the individual while maintaining the population diversity in \"dimension\"， so as to avoid the algorithm from falling into local optimal. The optimal solution when the algorithm stops execution is used as the initial cluster center to replace the randomly selected cluster center of traditional K?Means. The comparative experiment of the proposed algorithm on the Vowel， Iris， and Glass datasets and the synthetic dataset Jcdx in the UCI public database are conducted. The results show that， in comparison with traditional K?Means， the sum of squared errors （SSE） is reduced by 5.65%， 19.59%， 13.31%， and 6.1%， respectively， and the clustering time is reduced by 83.03%， 76.48%， 77.47%， and 92.63%， respectively. The experimental results show that the proposed improved algorithm has faster convergence speed and better optimization finding ability， which can significantly improve the effectiveness， efficiency and stability of clustering.

Keywords： K?Means clustering algorithm; differential evolution algorithm; multiple mutation strategy; Gaussian perturbation; UCI database; cluster center optimization

0 "引 "言

聚類算法作為數(shù)據(jù)挖掘中的一種無(wú)監(jiān)督算法[1]，能夠在無(wú)先驗(yàn)知識(shí)的情況下，揭示數(shù)據(jù)中存在的內(nèi)在關(guān)聯(lián)和潛在規(guī)律[2]；并根據(jù)數(shù)據(jù)的特征按照“相似度”或者“緊密度”將數(shù)據(jù)劃分為不同的類別[3]。但不同的算法或相同的算法采用不同的參數(shù)會(huì)產(chǎn)生不同的數(shù)據(jù)劃分或揭示不同的聚類結(jié)構(gòu)[4]。目前已有的聚類算法主要包括：基于劃分的聚類算法[5]，如K?Means、K?Medios；基于密度的聚類算法[6]，如DBSCAN、OPTICS；基于網(wǎng)格的聚類算法[7]，如WaveCluster、STING。K?Means聚類算法[8]是由J. B. MacQueen在1967年提出的，因其計(jì)算簡(jiǎn)單、線性時(shí)間復(fù)雜度低[9]，被廣泛應(yīng)用于數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)等領(lǐng)域。但傳統(tǒng)的K?Means聚類算法通常使用隨機(jī)選取的初始聚類中心[7]，這種聚類中心選取的隨機(jī)性[10]可能會(huì)導(dǎo)致初始聚類中心偏離數(shù)據(jù)集或過(guò)于集中等問題，從而影響聚類的效果。

為了解決傳統(tǒng)K?Means聚類算法中存在的問題，提升聚類效果及效率，諸多學(xué)者在算法改進(jìn)方面進(jìn)行了大量研究。白麗麗等人通過(guò)動(dòng)態(tài)更新量子旋轉(zhuǎn)門的旋轉(zhuǎn)角和將變異策略從非門改為H門來(lái)改進(jìn)人工魚群算法，并利用改進(jìn)人工魚群算法選取K?Means的初始聚類中心，提升了算法的收斂速度和聚類效果[11]。孫林等人對(duì)粒子群算法的速度慣性權(quán)重和位置更新公式進(jìn)行改進(jìn)并在傳統(tǒng)的歐氏距離中引入屬性權(quán)值，并使用改進(jìn)的粒子群算法優(yōu)化K?Means，有效地提高了聚類性能并降低了算法迭代次數(shù)[12]。王日宏等人針對(duì)布谷鳥優(yōu)化算法收斂速度慢、缺少活力的問題，在布谷鳥優(yōu)化算法中融入粒子群算法的思想，并將改進(jìn)算法應(yīng)用于優(yōu)化K?Means，提升了聚類的準(zhǔn)確性且算法穩(wěn)定性較好[13]。王絲絲等人通過(guò)樣本方差的多元統(tǒng)計(jì)距離算法，并引入改進(jìn)人工蜂群算法來(lái)確定初始聚類中心，克服了K?Means易陷入局部最優(yōu)解的缺陷[14]。陳小雪等人將一種加權(quán)的歐氏距離引入到螢火蟲優(yōu)化算法中，并對(duì)初始聚類中心進(jìn)行優(yōu)化，減少異常數(shù)據(jù)等不確定因素帶來(lái)的影響，提升聚類性能的同時(shí)，有效加快了算法的收斂速度[15]。胡嘯等人將獅群優(yōu)化算法引入到K?Means中，將算法停止執(zhí)行時(shí)的獅王最優(yōu)解作為聚類中心，有效降低了K?Means對(duì)初始聚類中心選取的依賴性[16]。綜上，使用智能優(yōu)化算法優(yōu)化K?Means的初始聚類中心對(duì)聚類效果有一定的提升作用。

差分進(jìn)化算法（DE）作為一種全局優(yōu)化算法，在處理數(shù)據(jù)時(shí)表現(xiàn)出了高效性和較強(qiáng)的魯棒性，并且具有設(shè)置參數(shù)較少、易于實(shí)現(xiàn)與調(diào)整等優(yōu)點(diǎn)。但差分進(jìn)化算法也存在同很多進(jìn)化算法一樣的問題，如進(jìn)化策略單一、易陷入局部最優(yōu)解、收斂速度較差等。針對(duì)差分進(jìn)化算法和K?Means聚類算法中存在的問題，本文提出一種基于改進(jìn)差分進(jìn)化的K?Means聚類算法，并探討其對(duì)于K?Means的改進(jìn)效果。首先，在差分進(jìn)化算法中設(shè)計(jì)自適應(yīng)操作算子，提升算法前期的全局搜索能力和后期的收斂速度；其次，設(shè)計(jì)多變異策略并引入權(quán)重系數(shù)，在不同的進(jìn)化階段發(fā)揮不同變異策略的優(yōu)勢(shì)以平衡算法的全局和局部搜索能力，并加快算法的收斂速度；最后，提出一種基于當(dāng)前種群最佳個(gè)體的高斯擾動(dòng)交叉操作，為個(gè)體提供更優(yōu)進(jìn)化方向的同時(shí)保持“維”上的種群多樣性，避免算法陷入局部最優(yōu)。將改進(jìn)差分進(jìn)化算法停止執(zhí)行時(shí)輸出的最優(yōu)解替代傳統(tǒng)K?Means隨機(jī)選取的初始聚類中心，并使用UCI公共數(shù)據(jù)集和合成數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn)。結(jié)果表明，基于改進(jìn)差分進(jìn)化的K?Means聚類算法降低了K?Means對(duì)初始聚類中心選取的依賴性，能夠更好地捕捉數(shù)據(jù)的內(nèi)在結(jié)構(gòu)，從而提高聚類的質(zhì)量和效率。

1 "基于改進(jìn)差分進(jìn)化的K?Means聚類算法

1.1 "改進(jìn)的差分進(jìn)化算法

1.1.1 "自適應(yīng)操作算子

差分進(jìn)化算法中的變異和交叉操作是整個(gè)算法的中心環(huán)節(jié)，變異因子[F]和交叉因子[CR]對(duì)算法有著極其重要的影響。在傳統(tǒng)的差分進(jìn)化算法中，變異因子[F]和交叉因子[CR]都是固定值，這會(huì)導(dǎo)致算法的尋優(yōu)能力和收斂性能受到限制，不利于算法優(yōu)化性能的提升[17]。在算法進(jìn)化的前期應(yīng)該保持種群個(gè)體的多樣性，提升算法的全局尋優(yōu)能力，而在算法中后期應(yīng)加強(qiáng)算法的局部搜索能力，提升算法的收斂速度。

為了使[F]和[CR]能夠適應(yīng)算法在不同進(jìn)化階段的尋優(yōu)需求，本文使用自適應(yīng)操作算子進(jìn)行改進(jìn)，隨著算法的進(jìn)化自適應(yīng)平衡算法的全局搜索能力和局部搜索能力。操作算子自適應(yīng)策略如下：

[F=Fmax-（Fmax-Fmin）（GGmax）2] （1）

[CR=CR max-（CR max-CR min）（GGmax）2] （2）

式中：[Fmin]表示[F]的下限，[Fmin]=0.3；[Fmax]表示[F]的上限，[Fmax]=0.9；[CR min]表示[CR]的下限，[CR min]=0.3；[CR max]表示[CR]的上限，[CR max]=0.9；[G]代表當(dāng)前算法的迭代次數(shù)；[Gmax]表示算法規(guī)定的最大迭代次數(shù)。

根據(jù)式（1）、式（2）實(shí)現(xiàn)[F]和[CR]的自適應(yīng)調(diào)整，可以確保隨著算法進(jìn)化次數(shù)的增加，變異因子[F]和交叉因子[CR]線性減小。這樣不但可以使算法在進(jìn)化的前期擁有較大的搜索空間和較好的全局尋優(yōu)能力，又可以在進(jìn)化的中后期擁有較好的局部搜索能力，從而加快算法的收斂速度。

1.1.2 "引入權(quán)重系數(shù)的多變異策略

為提升差分進(jìn)化算法的尋優(yōu)能力，在算法進(jìn)化的初期，應(yīng)保持種群的多樣性，以提高算法的全局尋優(yōu)能力。DE/rand/1變異策略具有較大的尋優(yōu)范圍，適合于算法初期進(jìn)行全局搜索。在算法進(jìn)化的中后期，因前期已經(jīng)完成了全局搜索，此時(shí)應(yīng)重點(diǎn)關(guān)注最優(yōu)個(gè)體及其附近區(qū)域的局部尋優(yōu)。而DE/current?to?best/2變異策略的局部搜索能力較強(qiáng)，尋優(yōu)速度較快，比較適合在算法中后期進(jìn)行局部搜索。

根據(jù)不同變異策略的特點(diǎn)，將DE/rand/1變異策略與DE/current?to?best/2變異策略相結(jié)合，提出基于多變異策略改進(jìn)的差分進(jìn)化算法，并通過(guò)引入權(quán)重系數(shù)[W]來(lái)實(shí)現(xiàn)隨算法的進(jìn)化次數(shù)自適應(yīng)調(diào)整不同變異策略所占的比重，在算法的不同進(jìn)化階段，發(fā)揮不同變異策略的優(yōu)勢(shì)。

[W=Wmin+（Wmax-Wmin）（GGmax）] （3）

[Vi，G+1=（1-W）Xr1，G+F（Xr2，G-Xr3，G）+ " " " " " " " W[Xi，G+F（Xbest，G-Xi，G）+ " " " " " " " F（Xr4，G-Xr5，G）+F（Xr6，G-Xr7，G）]] （4）

式中：[W]為權(quán)重因子，[Wmin]=0，[Wmax]=1；[G]為當(dāng)前迭代次數(shù)；[Gmax]為算法設(shè)定的最大迭代次數(shù)；[Vi，G+1]表示第[G+1]代的變異個(gè)體；[Xbest，G]代表當(dāng)前種群中適應(yīng)度值最佳的個(gè)體；[r1，r2，r3，r4，r5，r6，r7]表示從[[1，NP]]中取值的7個(gè)不等于[i]且互不相等的隨機(jī)數(shù)。

[W]會(huì)隨著算法進(jìn)化次數(shù)的增加而不斷變化，以平衡兩種變異策略在算法不同進(jìn)化階段所占的比重。在算法進(jìn)化的初期，[W]值較小，此時(shí)DE/rand/1變異策略在算法進(jìn)化過(guò)程中起主導(dǎo)作用，有利于算法在較大的搜索空間里進(jìn)行全局尋優(yōu)；在算法進(jìn)化中后期，[W]值逐漸增大，DE/current?to?best/2變異策略占據(jù)主導(dǎo)地位，能為個(gè)體提供更優(yōu)的進(jìn)化方向，提升算法的局部搜索能力，加快算法的收斂速度。

1.1.3 "高斯擾動(dòng)交叉操作

差分進(jìn)化算法通過(guò)變異和交叉操作來(lái)開發(fā)和探索新的解空間，雖然可以自適應(yīng)調(diào)整變異因子和交叉因子，但都是在個(gè)體的“維”上進(jìn)行操作。如果種群在某一維上的值接近相等，或逐漸趨向于一個(gè)固定值，那么差分進(jìn)化算法就在這一維上失去了尋優(yōu)能力。為保持種群在“維”上的多樣性，避免算法陷入局部最優(yōu)，本文在差分進(jìn)化算法的交叉操作中引入基于當(dāng)前種群最佳個(gè)體的高斯擾動(dòng)機(jī)制，使用當(dāng)前種群的最佳個(gè)體引導(dǎo)其余個(gè)體的進(jìn)化方向；同時(shí)使用高斯擾動(dòng)有概率地隨機(jī)產(chǎn)生每一維上的新值，保持種群在“維”上的多樣性，具體操作如下。

1） 針對(duì)聚類問題來(lái)說(shuō)，對(duì)于它的某一維[n]，取隨機(jī)數(shù)[rand（0，1）]，若[rand（0，1）][≤CR]，則[Uni，G=Vni，G]，然后結(jié)束該維的交叉操作；反之，進(jìn)入步驟2）。

2）再次取隨機(jī)數(shù)[rand（0，1）]，若[rand（0，1）≤0.7]，則[Uni，G=Xnbest，G]；若[rand（0，1）gt;0.7]，則通過(guò)高斯擾動(dòng)生成在該維上的一個(gè)隨機(jī)值，生成公式為：

[Uni，G=Xnbest，G·1+C·N（0，1）] （5）

式中：[C]為高斯擾動(dòng)的控制參數(shù)，[C]=0.1；隨機(jī)值[N（0，1）]表示滿足均值為0、標(biāo)準(zhǔn)差為1的正態(tài)分布。

新的交叉操作能夠使產(chǎn)生的個(gè)體向當(dāng)前種群中適應(yīng)度值最優(yōu)的個(gè)體移動(dòng)，同時(shí)高斯擾動(dòng)可以防止種群在某一維上趨于固定值，從而失去在該維上的尋優(yōu)能力，避免算法陷入局部最優(yōu)。結(jié)合前文提出的自適應(yīng)操作算子[CR]，在算法進(jìn)化的前期依然能夠保持算法的全局尋優(yōu)能力，在算法進(jìn)化的中后期能夠增強(qiáng)算法的局部搜索能力，加快算法的收斂速度。

1.2 "基于改進(jìn)差分進(jìn)化的K?Means聚類算法

將改進(jìn)的差分進(jìn)化算法與K?Means聚類算法相融合，利用式（6）的適應(yīng)度函數(shù)計(jì)算每個(gè)個(gè)體的適應(yīng)度函數(shù)值，使用改進(jìn)的差分進(jìn)化算法進(jìn)行迭代尋優(yōu)，將算法結(jié)束時(shí)輸出的最優(yōu)個(gè)體替代傳統(tǒng)K?Means聚類算法隨機(jī)選取的初始聚類中心。

[fitness=SSE=i，k（xi，k-ck）2] （6）

式中：[xi，k]表示一個(gè)數(shù)據(jù)點(diǎn)；[ck]表示該數(shù)據(jù)點(diǎn)所屬簇的中心。SSE越小，表示聚類效果越好；反之，則表示聚類效果越差。

1.2.1 "適應(yīng)度函數(shù)

在聚類算法中，最終目的是使類內(nèi)的數(shù)據(jù)點(diǎn)緊密度盡可能得小，而類間的緊密度盡可能得大。因此使用誤差平方和（SSE）[18]作為改進(jìn)差分進(jìn)化算法的適應(yīng)度函數(shù)，見公式（6）。

1.2.2 "算法流程

1） 設(shè)置種群規(guī)模[NP]為解維度[D]的10倍，變異因子[F]和交叉因子[CR]根據(jù)式（1）和式（2）進(jìn)行自適應(yīng)取值，[Fmin]=0.3，[Fmax]=0.9，[CR min]=0.3，[CR max]=0.9，當(dāng)前進(jìn)化次數(shù)為[G]，算法最大進(jìn)化次數(shù)[Gmax]=1 200，高斯擾動(dòng)系數(shù)[C]=0.1。

2） 對(duì)規(guī)模為[NP]的種群進(jìn)行初始化。

3） 對(duì)種群中的個(gè)體[Xi，G]，根據(jù)1.1.2節(jié)執(zhí)行改進(jìn)的變異操作，得到變異個(gè)體[Vi，G]。

4） 對(duì)父代個(gè)體[Xi，G]和變異個(gè)體[Vi，G]，根據(jù)1.1.3節(jié)執(zhí)行改進(jìn)的交叉操作，得到中間實(shí)驗(yàn)個(gè)體[Ui，G]。

5） 分別計(jì)算父代個(gè)體[Xi，G]和中間實(shí)驗(yàn)個(gè)體[Ui，G]的適應(yīng)度值，并進(jìn)行適應(yīng)度值的比較，適應(yīng)度較優(yōu)的個(gè)體會(huì)進(jìn)入到下一代種群中繼續(xù)參與進(jìn)化。循環(huán)執(zhí)行步驟3）～步驟5），直到達(dá)到算法的最大進(jìn)化次數(shù)為止。

6） 將算法輸出的最優(yōu)個(gè)體作為K?Means的初始聚類中心進(jìn)行聚類，循環(huán)迭代直到滿足聚類的停止要求或最大迭代次數(shù)，算法結(jié)束，輸出聚類結(jié)果。

基于改進(jìn)差分進(jìn)化的K?Means聚類算法流程如圖1所示。

2 "實(shí)驗(yàn)結(jié)果與對(duì)比分析

為驗(yàn)證本文提出算法的有效性，將本文算法在UCI公共數(shù)據(jù)庫(kù)中常用的聚類數(shù)據(jù)集Vowel、Iris和Glass與合成數(shù)據(jù)集Jcdx上進(jìn)行了多次實(shí)驗(yàn)。數(shù)據(jù)集的具體信息如表1所示，并將實(shí)驗(yàn)結(jié)果與K?Means聚類算法、基于離散粒子群的K?Means聚類算法（DPSO?KM）、基于灰狼優(yōu)化的K?Means聚類算法（GWO?KM）、基于鯨魚優(yōu)化的K?Means聚類算法（WOA?KM）和基于差分進(jìn)化的K?Means聚類算法（DE?KM）作對(duì)比。

實(shí)驗(yàn)環(huán)境：操作系統(tǒng)為Windows 10，處理器為Intel Core i5?8300h，內(nèi)存為16.0 GB，使用PyCharm 2021.3.3進(jìn)行編程。

2.1 "評(píng)價(jià)指標(biāo)

為衡量聚類算法的性能，選取輪廓系數(shù)、誤差平方和、DB指數(shù)、CH指數(shù)和聚類時(shí)間共5個(gè)評(píng)價(jià)指標(biāo)。具體可參考文獻(xiàn)[10，19]。

1） 輪廓系數(shù)（SC）

對(duì)于樣本[xi]，設(shè)[ai]是[xi]與同類中其他樣本的平均距離，[bi]是[xi]到其他簇的平均距離的最小值，則該樣本的輪廓系數(shù)為：

[si=bi-aimax（ai，bi）] （7）

所有樣本的[si]均值稱為聚類結(jié)果的輪廓系數(shù)，即：

[SC=1Ni=1Nsi] （8）

輪廓系數(shù)越大代表聚類效果越好。

2） 誤差平方和（SSE）

[SSE=i，k（xi，k-ck）2] （9）

式中：[xi，k]表示一個(gè)數(shù)據(jù)點(diǎn)；[ck]表示該數(shù)據(jù)點(diǎn)所屬的簇中心。誤差平方和越小代表聚類效果越好。

3） 戴維森堡丁指數(shù)（DB）

[DB=1ki=1kmaxj≠i，i，j∈[1，K]si+sjdi，j（ci，cj）] （10）

式中：[si]表示類[ci]內(nèi)數(shù)據(jù)距離中心[ci]的平均距離；[di，j]表示[ci]與[cj]類間的平均距離。DB值越小代表聚類效果越好。

4） 卡林斯基?哈拉巴斯指數(shù)（CH）

[CH=tr（BK）（K-1）tr（WK）（N-K）] （11）

式中：[tr]表示矩陣的跡；[BK]為類間的協(xié)方差矩陣；[WK]為類內(nèi)的協(xié)方差矩陣。[WK]、[BK]表示為：

[WK=k=1Kx∈Ck（x-ck）（x-ck）T] （12）

[BK=k=1Knk（ck-cx）（ck-cx）T] （13）

式中：[K]表示聚類數(shù)目；[ck]表示以[ck]為中心的簇集合；[nk]表示集合[ck]中的樣本數(shù)；[cx]表示數(shù)據(jù)集中心。CH值越大代表聚類效果越好。

5） 聚類時(shí)間（Time）

記錄算法在同一環(huán)境下運(yùn)行的時(shí)間（單位為s）。

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

分別用3個(gè)公共數(shù)據(jù)集和合成數(shù)據(jù)集對(duì)K?Means、DPSO?KM、GWO?KM、WOA?KM、DE?KM以及本文提出的AGDE?KM進(jìn)行實(shí)驗(yàn)。

算法參數(shù)設(shè)置如表2所示。

2.2.1 "聚類結(jié)果對(duì)比

每個(gè)算法獨(dú)立運(yùn)行30次，各數(shù)據(jù)集實(shí)驗(yàn)結(jié)果如表3～表6所示。

通過(guò)表3～表6的聚類結(jié)果對(duì)比可以看出，在Iris數(shù)據(jù)集上，因?yàn)闃颖緮?shù)據(jù)分布較為均勻，所以AGDE?KM相較于其他算法帶來(lái)的聚類效果提升并不明顯，但是聚類效率獲得了顯著提高。綜合Vowel、Iris、Glass和Jcdx 4個(gè)數(shù)據(jù)集的聚類結(jié)果來(lái)看，AGDE?KM的輪廓系數(shù)相對(duì)傳統(tǒng)K?Means分別提升1.57%、1.61%、24.94%、11.92%，誤差平方和分別降低5.65%、19.59%、13.31%、6.1%，DB值分別降低4.35%、11.49%、12.64%、6.93%，CH值分別提升6.36%、17.94%、18.8%、12.76%，聚類時(shí)間分別減少83.03%、81.33%、77.47%、92.63%。結(jié)合以上實(shí)驗(yàn)結(jié)果，充分證明了AGDE?KM在多樣化數(shù)據(jù)環(huán)境下具有更卓越的聚類性能和更高的適用性。

2.2.2 "算法收斂性對(duì)比

算法收斂曲線如圖2～圖5所示。

通過(guò)圖2～圖5的收斂曲線對(duì)算法的收斂性能進(jìn)行驗(yàn)證，其中橫坐標(biāo)代表算法迭代次數(shù)，縱坐標(biāo)代表算法搜索到的最優(yōu)解的適應(yīng)度值。從圖中可以看出，在相同的迭代次數(shù)下，AGDE?KM在Vowel、Glass、Jcdx數(shù)據(jù)集上的收斂速度和尋優(yōu)精度要明顯優(yōu)于其他4種算法；而在Iris數(shù)據(jù)集上因?yàn)槠錁颖痉植驾^為均勻，而導(dǎo)致尋優(yōu)精度相差不大。但是，AGDE?KM的收斂速度要明顯優(yōu)于其他4種算法。

3 "結(jié) "語(yǔ)

為了解決傳統(tǒng)K?Means聚類算法使用隨機(jī)選取的初始聚類中心，聚類的穩(wěn)定性差且效率低的問題，本文提出了一種基于改進(jìn)差分進(jìn)化的K?Means聚類算法（AGDE?KM）。AGDE?KM通過(guò)設(shè)計(jì)自適應(yīng)操作算子，在變異階段設(shè)計(jì)多變異策略并引入權(quán)重系數(shù)，平衡算法的全局和局部搜索能力，加快算法的收斂速度。

針對(duì)算法易陷入局部最優(yōu)解的問題，引入基于當(dāng)前種群最佳個(gè)體的高斯擾動(dòng)交叉操作。區(qū)別于原算法的交叉操作，本文算法能夠?yàn)閭€(gè)體提供更優(yōu)的進(jìn)化方向，并保持種群在“維”上的多樣性，增強(qiáng)算法局部搜索能力的同時(shí)避免算法陷入局部最優(yōu)。將改進(jìn)差分進(jìn)化算法輸出的最優(yōu)解作為聚類中心替代傳統(tǒng)K?Means隨機(jī)選取的初始聚類中心，有效解決了K?Means因隨機(jī)選取初始聚類中心而導(dǎo)致的聚類穩(wěn)定性差、聚類效果不佳和效率低的問題。

這一改進(jìn)使得聚類過(guò)程更加穩(wěn)定，能夠更好地捕捉數(shù)據(jù)的內(nèi)在結(jié)構(gòu)，從而提高聚類的質(zhì)量和效率，為多樣化數(shù)據(jù)環(huán)境下的聚類問題提供了一個(gè)更加有效的解決方案。

注：本文通訊作者為王福順。

參考文獻(xiàn)

[1] SINAGA K P， YANG M?S. Unsupervised K?means clustering algorithm [J]. IEEE access， 2020， 8： 80716?80727.

[2] SUN L， ZHANG J， DING W， et al. Feature reduction for imbalanced data classification using similarity?based feature clustering with adaptive weighted K?nearest neighbors [J]. Information sciences， 2022， 593： 591?613.

[3] 薛鋒，劉泳博，陳逸飛.新型群智能算法在求解聚類問題上的對(duì)比研究[J].計(jì)算機(jī)仿真，2023，40（3）：370?376.

[4] 何選森，何帆，徐麗，等.K?Means算法最優(yōu)聚類數(shù)量的確定[J].電子科技大學(xué)學(xué)報(bào)，2022，51（6）：904?912.

[5] AHMAD A， KHAN S S. initKmix?a novel initial partition generation algorithm for clustering mixed data using k?means?based clustering [J]. Expert systems with applications， 2021， 167： 114149.

[6] GUO W， WANG W， ZHAO S， et al. Density peak clustering with connectivity estimation [J]. Knowledge?based systems， 2022， 243： 108501.

[7] 廖紀(jì)勇，吳晟，劉愛蓮.基于相異性度量選取初始聚類中心改進(jìn)的K?means聚類算法[J].控制與決策，2021，36（12）：3083?3090.

[8] DUBEY A， CHOUBEY A. A systematic review on K?means clustering techniques [J]. International journal of scientific research and engineering trends， 2017， 6（6）： 12043.

[9] 孫林，劉夢(mèng)含.基于自適應(yīng)布谷鳥優(yōu)化特征選擇的K?means聚類[J].計(jì)算機(jī)應(yīng)用，2024，44（3）：831?841.

[10] AY M， ?ZBAK?R L， KULLUK S， et al. FC?Kmeans： fixed?centered K?means algorithm [J]. Expert systems with applications， 2023， 211： 118656.

[11] 白麗麗，宋初一，許麗艷，等.基于改進(jìn)量子旋轉(zhuǎn)門人工魚群算法的K?means聚類算法及其應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究，2022，39（3）：797?801.

[12] 孫林，張一曼，張辰珂，等.基于改進(jìn)粒子群和K?means聚類的優(yōu)化算法[J].江蘇科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2023，37（3）：81?90.

[13] 王日宏，崔興梅，李永珺.自適應(yīng)調(diào)整的布谷鳥搜索K?均值聚類算法[J].計(jì)算機(jī)應(yīng)用研究，2018，35（12）：3593?3597.

[14] 王絲絲，張敬磊，陳慈，等.基于方差與改進(jìn)群智能算法的K?means聚類優(yōu)化[J].系統(tǒng)科學(xué)與數(shù)學(xué)，2018，38（10）：1117?1127.

[15] 陳小雪，尉永清，任敏，等.基于螢火蟲優(yōu)化的加權(quán)K?means算法[J].計(jì)算機(jī)應(yīng)用研究，2018，35（2）：466?470.

[16] 胡嘯，王玲燕，張浩宇，等.基于獅群優(yōu)化的改進(jìn)K?Means聚類算法研究[J].控制工程，2022，29（11）：1996?2002.

[17] 楊啟文，蔡亮，薛云燦.差分進(jìn)化算法綜述[J].模式識(shí)別與人工智能，2008，21（4）：506?513.

[18] MOODI F， SAADATFAR H. An improved K?means algorithm for big data [J]. IET software， 2022， 16（1）： 48?59.

[19] 王藝霖，肖媛媛，左鵬飛，等.基于改進(jìn)聚類算法的交通事故多發(fā)點(diǎn)識(shí)別方法[J].計(jì)算機(jī)應(yīng)用研究，2023，40（10）：2993?2999.