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

蔣林岑 樊曉唯 劉向東

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

關鍵詞：聚類分析;K-means算法;初始值優化

中圖分類號：TP391? ? ? 文獻標識碼：A

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

隨著人工智能的發展，海量數據的涌現，如何從大量樣本數據集中發現有效的信息，并利用這些信息成為人們研究的重點，數據挖掘為獲取有效信息提供了方法和手段。

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

1 K-means聚類算法

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

傳統的K-means算法是應用較早的聚類算法，它的核心是對需要聚類分析的數據集隨機選出k個數據點作為初始值[5]，這些初始值作為分簇的中心點，其他樣本對象根據離中心點的最近距離進行劃分，和最近的中心點劃分為一個簇即實現分組。設有數據集[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算法是當所有對象到相應初值中心值誤差平方和最小時[6]，如公式（3） ，使得不同的迭代計算把具有不同特征的對象劃分到不同的分組中，生成的簇盡可能地靠近收斂。

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

K-means算法的具體實現過程如下：

輸入：數據集中包含n個對象和隨機[k]個簇。

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

方法：

（1） 在包含n個對象的數據集中隨機設置[k]個特征空間內的點為初始值，作為初始的聚類中心;

（2） 計算樣本集中的其他對象到[k]個初始值之間的距離，選擇最近的初始中心點所屬類別，作為其他對象的類別標記;

（3） 將所有對象完成分類標記后，根據劃分的分組對象，重新計算出每個分組新的初始值（中心點） ;

（4） 如果計算得出的新中心點與原中心點一樣，那么計算結束，否則重新進行第二步過程。

1.2 K-means聚類算法分析

通過K-means聚類算法的實現過程可以發現：由于傳統的K-means算法在選取初始值是隨機選擇的，每次得到的分類結果都不一樣，每次對象分組的差異較大，由于算法要求終止在范圍內的最佳狀態，所以初始中心點對整個分組計算的過程有著重要影響，聚類的結果會隨著初始值的不同而改變[7]。

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

2 K-means改進算法

2.1 改進的K-means算法思想

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

2.2 改進K-means算法的實現流程

輸入：待分類數據集D，[k]個聚類中心值。

輸出：滿足目標函數值最小的[k]和簇。

方法：

（1）? 對數據集[D]進行[?=1]次的采樣，得到采樣數據集[D']。

（2）? 在數據集[D']中隨機獲取n個初始簇中心[c1，c2，…cn]。

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

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

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

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

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

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

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

3 實驗結果與分析

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

通過表1可以看出，用傳統K-means算法隨機選取的中心值，給定聚類數k=3，通過5次隨機取數產生的初始值都不相同，計算得出準確率不同的花分類，由5次計算的準確率結果也發現，傳統方法中選取初始中心值得到聚類準確率也不穩定，平均準確率較低[9]。當數據集數量較大時，由初始值產生的對聚類結果的影響會越來越大。而對初始值進行改進后的算法每次的分類準確率有所提升，并且計算結果相對穩定，準確率有了明顯提升。

4 結束語

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

參考文獻：

[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] 劉文佳，張駿.一種改進的K-Means聚類算法[J].現代商貿工業，2018，30（19）：196-198.

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

[6] 齊曉娜，王佳，徐東升，等.基于改進的k-means差分隱私保護方法在位置隱私保護中的應用[J].河北大學學報（自然科學版），2018，38（3）：315-320.

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

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

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

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

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

收稿日期：2021-12-20

基金項目：2020 年度江蘇省工業軟件工程技術研究開發中心開放基金項目（ZK20-04-02）

作者簡介：蔣林岑，女，工程師，碩士，研究方向為人工智能、機器學習;樊曉唯，女，工程師，碩士，研究方向為人工智能、計算機視覺;劉向東，男，副教授，博士，研究方向為人工智能、知識圖譜。