對K-means聚類算法初始值的研究

蔣林岑 樊曉唯 劉向東

摘要：傳統(tǒng)的K-means聚類算法屬于典型的基于劃分聚類算法，算法的實(shí)現(xiàn)過程簡單易懂，聚類效果不錯(cuò)，因此被廣泛使用。但是，因?yàn)閭鹘y(tǒng)K-means的初始值是隨機(jī)選定的，使得聚類結(jié)果不穩(wěn)定，受初始值影響較大。針對上述問題，該文對傳統(tǒng)的K-means算法中隨機(jī)選取初始值改進(jìn)，對樣本值增加進(jìn)行預(yù)處理，首先對樣本值多次取數(shù)，對采樣數(shù)據(jù)集進(jìn)行初次K-means運(yùn)算后獲得聚類結(jié)果，從聚類結(jié)果中取距離最大的[k]個(gè)聚類中心作為初始值。通過Iris數(shù)據(jù)集對改進(jìn)算法進(jìn)行驗(yàn)證，聚類效果有較好的提高。

關(guān)鍵詞：聚類分析;K-means算法;初始值優(yōu)化

中圖分類號：TP391? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號：1009-3044（2022）11-0095-03

隨著人工智能的發(fā)展，海量數(shù)據(jù)的涌現(xiàn)，如何從大量樣本數(shù)據(jù)集中發(fā)現(xiàn)有效的信息，并利用這些信息成為人們研究的重點(diǎn)，數(shù)據(jù)挖掘?yàn)楂@取有效信息提供了方法和手段。

聚類分析對具有相似特征的一組對象進(jìn)行分組，根據(jù)組中的數(shù)據(jù)特征自動(dòng)分類[1]。在對數(shù)據(jù)進(jìn)行分組前，不需要預(yù)先給出分類目標(biāo)，根據(jù)對象之間的關(guān)聯(lián)特征自動(dòng)分組[2]。這樣的分類結(jié)果，將具有相同特性的數(shù)據(jù)分為一組，不同分組之間的區(qū)別也顯而易見，聚類分析是一種無監(jiān)督學(xué)習(xí)的方法，不會(huì)給出學(xué)習(xí)目標(biāo)[3]。組間的差別越大，聚類效果越好。聚類算法可以分為劃分的、密度的、層次的聚類算法。K-means聚類算法，是一種基于劃分的聚類算法，具有易懂、實(shí)現(xiàn)簡單、收斂快速的優(yōu)點(diǎn)[4]，在需要對對象進(jìn)行快速分類時(shí)，常用到K-means聚類算法。為了證明改進(jìn)算法的聚類效果，本文首先闡述K-means算法的基本思想和實(shí)現(xiàn)流程，接著詳細(xì)描述根據(jù)傳統(tǒng)K-means算法的局限性進(jìn)行優(yōu)化后的K-means算法，說明其思想和算法步驟。

1 K-means聚類算法

1.1 K-means聚類算法基本思想

傳統(tǒng)的K-means算法是應(yīng)用較早的聚類算法，它的核心是對需要聚類分析的數(shù)據(jù)集隨機(jī)選出k個(gè)數(shù)據(jù)點(diǎn)作為初始值[5]，這些初始值作為分簇的中心點(diǎn)，其他樣本對象根據(jù)離中心點(diǎn)的最近距離進(jìn)行劃分，和最近的中心點(diǎn)劃分為一個(gè)簇即實(shí)現(xiàn)分組。設(shè)有數(shù)據(jù)集[X=xi|i=1，2…n，cjj=1，2…k]，k用來表示聚類的類別，聚類的初始中心值用[cjj=1，2，…k]來表示，任意對象之間的距離用歐式距離來表示，如下：

[dxi，xj=xi-xjTxi-xj]? （1）

聚類中心。

[cj=1njx∈Cjx]? ? （2）

K-means算法是當(dāng)所有對象到相應(yīng)初值中心值誤差平方和最小時(shí)[6]，如公式（3） ，使得不同的迭代計(jì)算把具有不同特征的對象劃分到不同的分組中，生成的簇盡可能地靠近收斂。

[E=i=1kj=1njd（xj，ci）] （3）

K-means算法的具體實(shí)現(xiàn)過程如下：

輸入：數(shù)據(jù)集中包含n個(gè)對象和隨機(jī)[k]個(gè)簇。

輸出：迭代求得的[k]值和最終簇。

方法：

（1） 在包含n個(gè)對象的數(shù)據(jù)集中隨機(jī)設(shè)置[k]個(gè)特征空間內(nèi)的點(diǎn)為初始值，作為初始的聚類中心;

（2） 計(jì)算樣本集中的其他對象到[k]個(gè)初始值之間的距離，選擇最近的初始中心點(diǎn)所屬類別，作為其他對象的類別標(biāo)記;

（3） 將所有對象完成分類標(biāo)記后，根據(jù)劃分的分組對象，重新計(jì)算出每個(gè)分組新的初始值（中心點(diǎn)） ;

（4） 如果計(jì)算得出的新中心點(diǎn)與原中心點(diǎn)一樣，那么計(jì)算結(jié)束，否則重新進(jìn)行第二步過程。

1.2 K-means聚類算法分析

通過K-means聚類算法的實(shí)現(xiàn)過程可以發(fā)現(xiàn)：由于傳統(tǒng)的K-means算法在選取初始值是隨機(jī)選擇的，每次得到的分類結(jié)果都不一樣，每次對象分組的差異較大，由于算法要求終止在范圍內(nèi)的最佳狀態(tài)，所以初始中心點(diǎn)對整個(gè)分組計(jì)算的過程有著重要影響，聚類的結(jié)果會(huì)隨著初始值的不同而改變[7]。

K-means算法實(shí)例說明初始值對聚類結(jié)果的影響，由于每次隨機(jī)選定的初始值不同，因此每次聚類的結(jié)果也會(huì)有差異。給定數(shù)據(jù)集：{隨機(jī)生成1500個(gè)對象樣本集合，初始默認(rèn)[k]=3}，通過兩次K-means算法計(jì)算結(jié)果可以觀察發(fā)現(xiàn)：原始數(shù)據(jù)有4類數(shù)據(jù)分布如圖1所示，通過K-means算法運(yùn)行一次結(jié)果如圖2，隨機(jī)產(chǎn)生3個(gè)中心點(diǎn)并分組得到3個(gè)簇，第二次計(jì)算聚類如圖3，結(jié)果也是3組簇，可以發(fā)現(xiàn)2次分類結(jié)果有部分差異。并且當(dāng)數(shù)據(jù)集越大，遇到極端初始值時(shí)，需要運(yùn)算的時(shí)間更長，聚類的結(jié)果反正難以收斂，因此無法得到聚類結(jié)果。

2 K-means改進(jìn)算法

2.1 改進(jìn)的K-means算法思想

算法思想：針對上述初始中心點(diǎn)隨機(jī)的問題，本文提出在開始階段對數(shù)據(jù)集進(jìn)行預(yù)處理，找到最佳初始值，產(chǎn)生一個(gè)比較穩(wěn)定的聚類結(jié)果，從而不依賴初始中心值。改進(jìn)的K-means算法分為兩步：（1） 預(yù)處理階段：對樣本數(shù)據(jù)集首先進(jìn)行m次隨機(jī)采樣，對每次采樣的數(shù)據(jù)隨機(jī)取n（n3k） 個(gè)初始中心值進(jìn)行K-means運(yùn)算，每次得到n個(gè)簇中心的聚類結(jié)果，得到隨機(jī)樣本的m組數(shù)據(jù)，一共m′n個(gè)簇[8]。（2） 接著選取確定初始值：在第一步中獲取到的m′n個(gè)簇中心，依次選擇其中距離相差最大的點(diǎn)作為初始中心[9]。具體處理流程如圖4所示。

2.2 改進(jìn)K-means算法的實(shí)現(xiàn)流程

輸入：待分類數(shù)據(jù)集D，[k]個(gè)聚類中心值。

輸出：滿足目標(biāo)函數(shù)值最小的[k]和簇。

方法：

（1）? 對數(shù)據(jù)集[D]進(jìn)行[?=1]次的采樣，得到采樣數(shù)據(jù)集[D']。

（2）? 在數(shù)據(jù)集[D']中隨機(jī)獲取n個(gè)初始簇中心[c1，c2，…cn]。

（3）? 通過公式1計(jì)算數(shù)[D']中其余需要分類的對象[p]到n個(gè)初始中心距離[dp，ci]。

（4）? 計(jì)算對象[p]和簇中心的距離，若距離最小則將對象和[ci]分類到同一組，成為同一個(gè)簇。

（5）? 遍歷完所有對象后，利用公式2重新計(jì)算[ci]的值，得到n個(gè)新的簇中心。

（6）? 重復(fù)采樣次數(shù)當(dāng)[i?m]，獲取[m×n]個(gè)簇中心，記作[sm×n=x1，x2，..xm×n，]，選取距離最大的兩點(diǎn)[p，q]，滿足[dp，q=maxdij，i，j∈1，2，…n]，[xp，xq]作為初始的兩個(gè)聚類中心。

（7）? 將剩余的[m×n-2]個(gè)樣本按就近距離劃分到[p，q]的簇中。

（8）? 對[p]簇[q]簇中的對象進(jìn)行距離計(jì)算，將距離最大的對象定為新的第三個(gè)聚類中心。

（9）? 依次類推，輸出滿足均方誤差函數(shù)值最小的[k]個(gè)簇和[k]個(gè)初始值。

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

通過實(shí)驗(yàn)對改進(jìn)算法進(jìn)行聚類效果分析，Iris鳶尾花數(shù)據(jù)集是UCI數(shù)據(jù)集的一部分，這個(gè)數(shù)據(jù)集經(jīng)常被用作機(jī)器學(xué)習(xí)的分類場景[10]。Iris鳶尾花數(shù)據(jù)集被分為Iris-setosa、Iris-versicolor、Iris-virginica三類，數(shù)據(jù)集共包括150個(gè)樣本[11]。為了分析聚類效果，分別使用傳統(tǒng)K-means算法和改進(jìn)的K-means算法，前者是隨機(jī)取值作為初始值，后者是首先確定初始值和k簇值，再進(jìn)行計(jì)算。實(shí)驗(yàn)中，通過多次選取初始值取平均數(shù)從而均衡分類準(zhǔn)確率結(jié)果。用傳統(tǒng)算法和改進(jìn)后算法分別對Iris數(shù)據(jù)集各自進(jìn)行5次計(jì)算，傳統(tǒng)K-means算法隨機(jī)聚類中心位置分別是（45，78，101） ，（10，45，77） ，（45，66，89） ，（23，67，89） ，（34，56，121） ，該進(jìn)算法的初始化中心（35，56，111） ，（23，67，131） ，（9，35，103） ，（24，56，89） ，（45，67，129） ，實(shí)驗(yàn)結(jié)果如表1。

通過表1可以看出，用傳統(tǒng)K-means算法隨機(jī)選取的中心值，給定聚類數(shù)k=3，通過5次隨機(jī)取數(shù)產(chǎn)生的初始值都不相同，計(jì)算得出準(zhǔn)確率不同的花分類，由5次計(jì)算的準(zhǔn)確率結(jié)果也發(fā)現(xiàn)，傳統(tǒng)方法中選取初始中心值得到聚類準(zhǔn)確率也不穩(wěn)定，平均準(zhǔn)確率較低[9]。當(dāng)數(shù)據(jù)集數(shù)量較大時(shí)，由初始值產(chǎn)生的對聚類結(jié)果的影響會(huì)越來越大。而對初始值進(jìn)行改進(jìn)后的算法每次的分類準(zhǔn)確率有所提升，并且計(jì)算結(jié)果相對穩(wěn)定，準(zhǔn)確率有了明顯提升。

4 結(jié)束語

本文通過對K-means算法中隨機(jī)獲取的初始值的局限性進(jìn)行改進(jìn)，提出了一種優(yōu)化初始值的K-means算法。改進(jìn)的K-means從研究探索如何能獲取穩(wěn)定的初始值為目標(biāo)，增加對數(shù)據(jù)集多次采樣后的聚類中心點(diǎn)預(yù)處理，經(jīng)過多次迭代獲取的中心點(diǎn)中選取距離最大的點(diǎn)作為確定初始值。改進(jìn)后的算法雖然提升了準(zhǔn)確率，由于在選定初始值時(shí)進(jìn)行了預(yù)處理，因此增加了時(shí)間復(fù)雜度，下一步將對減少時(shí)間復(fù)雜度和提升聚類效果做進(jìn)一步研究。

參考文獻(xiàn)：

[1] Harmer P K，Williams P D，Gunsch G H，etal.Anartificial immune system architecture for computer security applications[J].IEEE Transactions on Evolutionary Computation，2002，6（3）：252-280.

[2] Hand D J，VinciottiV.Choosing k for two-class nearest neighbour classifiers with unbalanced classes[J].Pattern RecognitionLetters，2003，24（9/10）：1555-1562.

[3] Yang M S，Hu Y J，Lin K C R，etal.Segmentationtechniques for tissue differentiation in MRI of Ophthalmology using fuzzyclustering algorithms[J].Magnetic Resonance Imaging，2002，20（2）：173-179.

[4] 劉文佳，張駿.一種改進(jìn)的K-Means聚類算法[J].現(xiàn)代商貿(mào)工業(yè)，2018，30（19）：196-198.

[5] 初廣輝，王曉利.一種改進(jìn)的基于差分隱私的k-m eans聚類算法[J].軟件導(dǎo)刊，2019，18（8）：71-74.

[6] 齊曉娜，王佳，徐東升，等.基于改進(jìn)的k-means差分隱私保護(hù)方法在位置隱私保護(hù)中的應(yīng)用[J].河北大學(xué)學(xué)報(bào)（自然科學(xué)版），2018，38（3）：315-320.

[7] 常彤.K-means算法及其改進(jìn)研究現(xiàn)狀[J].通訊世界，2017（19）：289-290.

[8] 于夢馨，劉波，湯恩生.改進(jìn)粒子群算法優(yōu)化SVM參數(shù)的遙感圖像分類[J].航天返回與遙感，2018，39（2）：133-140.

[9] 周濤.具有自適應(yīng)參數(shù)的粗糙k-means聚類算法[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（26）：7-10.

[10] 任恒妮.大數(shù)據(jù)K-means聚類算法的研究與應(yīng)用[J].信息技術(shù)，2019，43（11）：20-23.

[11] 安計(jì)勇，閆子驥，翟靖軒.基于距離閾值及樣本加權(quán)的K-means聚類算法[J].微電子學(xué)與計(jì)算機(jī)，2015，32（8）：135-138.

收稿日期：2021-12-20

基金項(xiàng)目：2020 年度江蘇省工業(yè)軟件工程技術(shù)研究開發(fā)中心開放基金項(xiàng)目（ZK20-04-02）

作者簡介：蔣林岑，女，工程師，碩士，研究方向?yàn)槿斯ぶ悄堋C(jī)器學(xué)習(xí);樊曉唯，女，工程師，碩士，研究方向?yàn)槿斯ぶ悄堋⒂?jì)算機(jī)視覺;劉向東，男，副教授，博士，研究方向?yàn)槿斯ぶ悄堋⒅R(shí)圖譜。