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

楊一帆 賀國(guó)先 李永定

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

關(guān)鍵詞：聚類(lèi);K-means;最近鄰點(diǎn)密度;初始聚類(lèi)中心;孤立點(diǎn)

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

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

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

1 K-means算法的一般步驟

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

2 基于最近鄰點(diǎn)密度的K-means算法

2.1 算法的思想

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

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

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

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

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

（2）最近鄰點(diǎn)的查找

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

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

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

（3）最近鄰點(diǎn)密度的計(jì)算

Step 1：利用公式（5）計(jì)算出每個(gè)點(diǎn)的最近鄰點(diǎn)密度dens;

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

（4）查找初始聚類(lèi)中心，聚類(lèi)

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

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

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

Step4：按照Step 3的方式查找，直到找到K個(gè)聚類(lèi)中心為止;

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

（5）孤立點(diǎn)的分配

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

[10] 王振武.數(shù)據(jù)挖掘算法原理與實(shí)現(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)格的簇心可確定聚類(lèi)算法[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] 賈瑞玉，李玉功.類(lèi)簇?cái)?shù)目和初始中心點(diǎn)自確定的K-means算法[J].計(jì)算機(jī)工程與應(yīng)用，2018，54（7）：152-158.

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