優化初始聚類中心選擇的K-means算法

楊一帆 賀國先 李永定

摘要：K-means算法的聚類效果與初始聚類中心的選擇以及數據中的孤立點有很大關聯，具有很強的不確定性。針對這個缺點，提出了一種優化初始聚類中心選擇的K-means算法。該算法考慮數據集的分布情況，將樣本點分為孤立點、低密度點和核心點，之后剔除孤立點與低密度點，在核心點中選取初始聚類中心，孤立點不參與聚類過程中各類樣本均值的計算。按照距離最近原則將孤立點分配到相應類中完成整個算法。實驗結果表明，改進的K-means算法能提高聚類的準確率，減少迭代次數，得到更好的聚類結果。

關鍵詞：聚類;K-means;最近鄰點密度;初始聚類中心;孤立點

Abstract：The clustering effect of K-means algorithm is closely related to the selection of initial clustering center and the isolated points in the data， so it has strong uncertainty.In order to solve this problem， a novel K-means algorithm based on nearest neighbor density is proposed. In this algorithm， considering the distribution of the data set， the sample points are divided into isolated points， low density points and core points， and then the isolated points and low density points are eliminated， and the initial clustering center is selected in the core points. Isolated points do not participate in the calculation of the mean value of all kinds of samples in the process of clustering. The outlier is assigned to the corresponding class according to the nearest principle to complete the whole algorithm. The experimental results show that the improved K-means algorithm can improve the clustering accuracy， reduce the number of iterations， and get better clustering results.

Key words： clustering; k-means; nearest neighbor density; initial clustering center; isolated points

聚類就是按一定的標準把物理或抽象對象的集合分成若干類別的過程，聚類后得到的每一個簇中的對象要盡可能的相似，不同簇中的對象盡量的相異[1-2]。聚類分析是一種無指導的學習方式，作為數據挖掘的一個重要研究方向，被廣泛應用到商務智能、圖像識別、Web搜索等領域。到目前為止，已經形成了很多聚類分析的方法，例如：基于劃分的方法、基于層次的方法、基于密度的方法、基于網格的方法等等[3]。

K-means聚類算法是數據挖掘中應用最廣泛的算法之一[4]。該算法易于實現，收斂速度快，處理數據集時有較好的伸縮性。但是該算法在開始運行時初始聚類中心的選取是隨機的，如果初始聚類中心隨機選在了數據中的孤立點，那么最后的聚類效果就不會很理想。因此如何選取合適的聚類中心從而避免孤立點的影響一直以來都是K-means算法的一個重要研究方向。很多學者都針對K-means算法的缺點提出了改進策略，例如：馮波等人把最小生成樹算法與K-means算法相結合，改進了初始聚類中心的選擇方法，提高了聚類的精度[5];邢長征等人提出了基于平均密度優化初始聚類中心的K-means算法[6]，利用事先定義的密度參數與平均密度刪除孤立點然后從剩余的點中挑選初始的聚類中心，縮小了聚類中心選取的范圍，節省了時間;金曉民等人結合層次聚類與最小生成樹的思想提出了一種基于最小生成樹的多層次k-Means聚類算法[7]，并將其運用到了數據挖掘中，提高了挖掘的效率;趙文聰等人提出了一種新的基于影響空間的快速K-means算法[8]，在保證聚類精度的同時提高了聚類的效率;胡偉[9]結合空間層次結構，提出一種改進的層次 K均值聚類算法，最后的聚類效果較好，但是算法消耗的時間較長。本文在前人研究的基礎上，圍繞K-means算法受初始聚類中心的選取與孤立點影響較大的缺點進行研究。結合最近鄰的思想，提出了一種優化初始聚類中心選擇的K-means算法，實驗結果表明，改進的算法迭代次數更少，準確率更高。

1 K-means算法的一般步驟

K-means聚類算法首先隨機選取k個樣本點作為初始聚類中心，計算各個數據與所選聚類中心的距離[10]，按距離最近的原則將各個樣本點分配到相應的簇中，通過計算每個簇的均值，找到新的聚類中心，進行迭代，直到滿足收斂條件，算法結束。

2 基于最近鄰點密度的K-means算法

2.1 算法的思想

K-means算法由于自身的限制，聚類效果受初始聚類中心的選擇與孤立點的影響很大。但是K-means算法初始聚類中心的選取是隨機的，這無疑又給最后的聚類效果增加了不確定性。從相關文獻中了解到[11-12]，如果考慮數據集中樣本點的分布情況，將初始的聚類中心選在數據點分布較密集的地方，聚類的效果會更好。本文的算法在設計時借鑒了密度和最近鄰的思想，提出了最近鄰點密度的概念，將樣本點分為孤立點、低密度點和核心點。首先利用網格化的方法[13]去除孤立點，計算出低密度點和核心點的最近鄰點密度，設置閾值，將最近鄰點密度小于閾值的低密度點刪除。在核心點中選取初始聚類中心，以最近鄰點密度最大的點作為第一個初始的聚類中心;按照類間距離最大原則，選取與第一個聚類中心距離最遠的點作為第二個聚類中心;然后將與第一和第二個聚類中心距離之和最大的點作為第三個聚類中心，以此方式直到找到所有初始聚類中心。在這個過程中，每選取一個聚類中心，就把該聚類中心所在網格內的所有點刪除。最后利用核心點和低密度點進行聚類，聚類完成之后按照距離最近的原則將孤立點分配到相應的類中，完成整個算法。因為基于最近鄰的思想對算法做出的改進，因此本文將改進的算法記做Near-K-means算法。

（1）網格化去除孤立點

Step1：根據數據集的分布情況設置坐標軸的刻度，畫出數據集的網格散點圖，并對散點圖上的每個點進行標號;

Step2：記錄網格中數據點的數量為1的樣本的標號，作為孤立點從數據集中刪除;

如圖2所示，從圖中可以清楚地看到0號，14號和31號所在的網格只有一個樣本點，因此這三個點為孤立點，從數據集中找到相應點刪除。

（2）最近鄰點的查找

Step 1：根據公式（1）計算數據集中所有數據對象之間的兩兩距離，得到距離矩陣distance;

Step 2：利用公式（4）計算樣本中每個樣本點的最近鄰點個數MinPts，對distance矩陣的第一行進行升序排序，然后從小到大挑選出MinPts+1列，則第二列到MinPts+1列所對應的點即為第一個點的最近鄰點;

Step 3：按照Step 2的方式對distance矩陣的其他行進行操作，找到所有點對應的最近鄰點。

（3）最近鄰點密度的計算

Step 1：利用公式（5）計算出每個點的最近鄰點密度dens;

Step 2：依據 dens的值將數據集D={[y1，y2，y3，...，yn]}降序排序，確定最近鄰點密度閾值[ρ0]的大小。

（4）查找初始聚類中心，聚類

Step 1：將集合D中dens小于[ρ0]的低密度點刪除，更新集合D，然后從集合D中找到dens值最大的點[di]，作為第一個初始的聚類中心;

Step 2：記錄點[di]所在網格中所有樣本點的標號，從集合D中刪除這些點，更新集合D。從distance矩陣中找到點[di]與集合D中其他所有點的歐氏距離，選擇與點[di]距離最遠的點[dj]作為第二個初始的聚類中心，記錄點[dj]所在網格中樣本點的標號，從集合D中刪除，更新集合D;

Step 3：從distance矩陣中分別找到點[di]，[dj]與集合D中其他樣本點的歐氏距離，按照距離之和最大的原則找到點[dl] 作為第三個初始的聚類中心，記錄點[dl]所在網格中其他點的標號，從集合D中刪除，更新集合D;

Step4：按照Step 3的方式查找，直到找到K個聚類中心為止;

Step5：使用低密度點和核心點的數據，調用K-means算法進行聚類。

（5）孤立點的分配

Step 1：計算每個孤立點與各個聚類中心的距離，把孤立點分配到與其距離最近的聚類中心所屬的類中，算法結束。

3 實驗及結果分析

為了驗證本文算法的有效性，采用UCI機器學習數據庫中的Iris，Wine，glass數據集進行實驗。實驗環境為：Intel CPU，8GB內存，500 GB硬盤，Windows7 操作系統。編程語言為Python，依據公式（7）將Near-K-means算法與傳統的K-means算法的準確率進行對比，除此之外，本文還對迭代次數做了對比。實驗所用的數據集描述如表1所示。

由于傳統的K-means算法隨機選取聚類中心，因此把傳統的K-means算法運行8次，取平均值作為最后的結果。本文改進的K-means算法初始的聚類中心是經過計算選定的，只運行一次作為最后結果。實驗結果如表2所示。

由表1的數據描述與表2的準確率對比顯示，Iris數據集共有150個樣本，含有4個屬性，分為3類，運用傳統的K-means算法進行聚類時，平均準確率只有72.40%。而運用本文改進的算法進行聚類時，準確率達到了88.67%;Wine數據集有178條數據，每條包含13個屬性，運用傳統K-means算法與Near-K-means算法分別進行聚類時，準確率分別為68.03%與74.16%，準確率也得到了提高;對于glass數據集，本身分類較多，為6類，一共214條數據。運用傳統K-means算法進行迭代時，準確率為51.04%，而運用Near-K-means算法時，準確率提高到了56.54%。

圖3、圖4、圖5的結果顯示，在三個數據集上，傳統的K-means算法每次實驗的迭代次數是不確定的，因為初始聚類中心是隨機選取的，這也說明傳統的K-means算法不穩定。Near-K-means算法的初始聚類中心是通過更加優化的方式選取的，在三個數據集上的迭代次數更少并且都很穩定，綜合表2和圖3、圖4、圖5，與傳統的K-means算法相比，本文提出的Near-K-means算法準確率更高，迭代次數更少，更穩定，聚類結果更具有參考價值。

4 結語

本文針對傳統的K-means算法聚類效果受初始聚類中心與孤立點影響較大的缺陷，結合密度與最近鄰的思想進行改進，提出了一種優化初始聚類中心選擇的K-means算法。改進的算法考慮數據集的分布情況，將樣本點分為孤立點、低密度點和核心點。在核心點中選取初始聚類中心，并利用類間距離最大原則進行選取，最后根據最小距離原則將孤立點分配到離它最近的聚類中心所屬的類中。改善了K-means 算法聚類效果受初始聚類中心與孤立點影響的缺點。經過實驗驗證 ，本文改良的算法聚類效果更好，準確率更高，更穩定。

但是改進的算法也有不足之處，本文采用網格化的方法刪除孤立點時需要設定坐標軸的刻度，在實驗中發現，坐標軸刻度的設置直接會影響最后聚類的準確率。如何更加準確的設置坐標軸的刻度，得到更好的聚類效果，將是接下來研究的方向之一。

參考文獻：

[1] 李曉瑜，俞麗穎，雷航，等.一種K-means改進算法的并行化實現與應用[J].電子科技大學學報，2017，46（1）：61-68

[2] 高詩瑩，周曉鋒，李帥.基于密度比例的密度峰值聚類算法[J].計算機工程與用，2017，53（16）：10-17.

[3] 邵倫，周新志，趙成萍，等.基于多維網格空間的改進K-means聚類算法[J].計算機應用，2018，38（10）：2850-2855.

[4] 羅軍鋒，鎖志海.一種基于密度的K-means聚類算法[J].微電子學與計算機，2014，31（10）：28-31.

[5] 馮波，郝文寧，陳剛，等.K-means算法初始聚類中心選擇的優化[J].計算機工程與應用，2013，49（14）：182-185+192.

[6] 邢長征，谷浩.基于平均密度優化初始聚類中心的K-means算法[J].計算機工程與應用，2014，50（20）：135-138.

[7] 金曉民，張麗萍.基于最小生成樹的多層次k-Means聚類算法及其在數據挖掘中的應用[J].吉林大學學報（理學版），2018，56（5）：1187-1192.

[8] 趙文沖，蔡江輝，趙旭俊，等.一種影響空間下的快速K-means聚類算法[J].小型微型計算機系統，2016，37（9）：2060-2064.

[9] 胡偉.改進的層次K均值聚類算法[J].計算機工程與應用，2013，49（2）：157-159.

[10] 王振武.數據挖掘算法原理與實現[M].北京：清華大學出版社，2016：159-161.

[11] Park H S， Jun C H. A simple and fast algorithm for K-medoids clustering[J].Expert systems with applications，2009，36（2）：3336-3341.

[12] Rodriguez A， Laio A. Clustering by fast search and find of density peaks[J]. Science， 2014，344（6191）：1492-1496.

[13] 何熊熊，管俊軼，葉宣佐，等.一種基于密度和網格的簇心可確定聚類算法[J].控制與決策，2017，32（5）：913-919.

[14] Daszykowski M， Walczak B，Massart D L.Looking for natural patterns in data： Part 1. Density-based approach[J].Chemometrics and Intelligent Laboratory Systems，2001，56（2）： 83-92.

[15] 賈瑞玉，李玉功.類簇數目和初始中心點自確定的K-means算法[J].計算機工程與應用，2018，54（7）：152-158.

【通聯編輯：王力】