優(yōu)化初始聚類中心選擇的K-means算法

楊一帆 賀國先 李永定

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

關(guān)鍵詞：聚類;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

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

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

1 K-means算法的一般步驟

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

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

2.1 算法的思想

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

（1）網(wǎng)格化去除孤立點

Step1：根據(jù)數(shù)據(jù)集的分布情況設(shè)置坐標(biāo)軸的刻度，畫出數(shù)據(jù)集的網(wǎng)格散點圖，并對散點圖上的每個點進(jìn)行標(biāo)號;

Step2：記錄網(wǎng)格中數(shù)據(jù)點的數(shù)量為1的樣本的標(biāo)號，作為孤立點從數(shù)據(jù)集中刪除;

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

（2）最近鄰點的查找

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

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

Step 3：按照Step 2的方式對distance矩陣的其他行進(jìn)行操作，找到所有點對應(yīng)的最近鄰點。

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

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

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

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

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

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

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

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

Step5：使用低密度點和核心點的數(shù)據(jù)，調(diào)用K-means算法進(jìn)行聚類。

（5）孤立點的分配

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

3 實驗及結(jié)果分析

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

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

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

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

4 結(jié)語

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

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

參考文獻(xiàn)：

[1] 李曉瑜，俞麗穎，雷航，等.一種K-means改進(jìn)算法的并行化實現(xiàn)與應(yīng)用[J].電子科技大學(xué)學(xué)報，2017，46（1）：61-68

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

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

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

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

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

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

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

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

[10] 王振武.數(shù)據(jù)挖掘算法原理與實現(xiàn)[M].北京：清華大學(xué)出版社，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] 何熊熊，管俊軼，葉宣佐，等.一種基于密度和網(wǎng)格的簇心可確定聚類算法[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] 賈瑞玉，李玉功.類簇數(shù)目和初始中心點自確定的K-means算法[J].計算機(jī)工程與應(yīng)用，2018，54（7）：152-158.

【通聯(lián)編輯：王力】