戚后林，顧 磊

(南京郵電大學(xué) 計算機學(xué)院，江蘇 南京 210003)

基于密度與最小距離的K-means算法初始中心方法

戚后林，顧 磊

(南京郵電大學(xué) 計算機學(xué)院，江蘇 南京 210003)

為了克服在傳統(tǒng)K-means聚類算法過程中因初始類簇中心的隨機性指定所帶來的聚類結(jié)果波動較大的缺陷，提出了一種基于密度與最小距離作為參數(shù)來確定初始類簇中心的算法。該算法根據(jù)一定的規(guī)則計算數(shù)據(jù)對象的密度參數(shù)，在計算完數(shù)據(jù)集中每條數(shù)據(jù)的單點密度之后，計算每個數(shù)據(jù)對象與較其密度大的其他數(shù)據(jù)對象的最小距離，以密度和最小距離作為參數(shù)，選取密度和最小距離同時較大的點作為K-means聚類過程的初始類簇中心。實驗結(jié)果表明，在類簇數(shù)目確定的情況下，應(yīng)用該算法確定的初始K-means類簇中心，在標(biāo)準(zhǔn)的UCI數(shù)據(jù)集上能夠進行K-means聚類，且與隨機選擇類簇中心和其他使用密度作為參數(shù)的算法相比，基于改進后的初始中心方法的K-means聚類算法具有較高的準(zhǔn)確率和更快的收斂速度。

K-means算法；類簇中心；密度；最小距離；迭代次數(shù)

1 概 述

近年來，隨著大數(shù)據(jù)的興起，如何從中總結(jié)出有價值的數(shù)據(jù)規(guī)律是一個重要任務(wù)。聚類作為一種數(shù)據(jù)分析法，在數(shù)據(jù)挖掘、圖像處理等方面都有重要應(yīng)用。聚類算法包括基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法。聚類分析的目的是數(shù)據(jù)集合應(yīng)用不同的策略劃分成相似的類簇的過程，從而使同一個類簇具有較高的相似度，而不同的類簇之間盡可能不同。同時聚類分析作為一種數(shù)據(jù)劃分的方法，也可以作為其他數(shù)據(jù)挖掘方法的一個預(yù)處理步驟。

K-means算法[1]是MacQueen提出的一種聚類方法。作為一種典型的基于劃分的聚類算法，其特點為：幾何意義直觀，收斂速度快，資源消耗較少等。但缺點也顯而易見：由于算法的初始點通常在算法開始時隨機給出，算法的結(jié)果很不穩(wěn)定；同時，算法對于初始類簇中心較為敏感，容易陷入局部最優(yōu)，類簇中心的數(shù)目需要事先給定。

假設(shè)在n個數(shù)據(jù)點中找到k個聚類中心c1,c2,…,ck,使得每個數(shù)據(jù)xi與其最近的聚類中心cv的平方距離和最小化(該距離和稱為偏差Δ)，也即Δ收斂。

輸入：類簇的數(shù)目k以及n個記錄的數(shù)據(jù)集；

輸出：k個類簇，Δ最小或者收斂。

(1)初始化。指定k個類簇中心c1,c2,…,ck。

(2)分配xi。找到距離xi最近的類簇中心cv,并將其分配到其最近的類簇中心cv。

(3)修正cv。通過不斷地計算簇的平均值，找到更加合適的聚類中心cv。

(4)計算偏差：

(1)

(5)Δ收斂。如果收斂，返回c1,c2,…,ck，并終止算法，否則返回步驟(2)。

為了克服K-means算法的缺陷，學(xué)者們試圖從不同角度去改進K-means算法。文獻[2]研究了確定K的算法，該算法假設(shè)數(shù)據(jù)集的子集服從高斯分布，然后在K-means聚類過程中不斷增加K的大小，直到數(shù)據(jù)集滿足假設(shè)，但是對于不服從高斯分布的數(shù)據(jù)集，該算法仍然存在缺陷。文獻[3]通過K-d樹來劃分數(shù)據(jù)集，然后利用多個局部區(qū)域密度選擇初始中心的方法，該算法依賴樹節(jié)點的數(shù)量，當(dāng)數(shù)據(jù)集的維度較大時，該算法的運行時間較長。文獻[4]提出一種基于平均密度優(yōu)化初始類簇中心的算法(adk-means)，該算法首先找到數(shù)據(jù)集中的噪點，在算法執(zhí)行過程中，噪點不參與聚類過程，但是該算法需要人為指出噪點，當(dāng)數(shù)據(jù)集較大時，算法的主觀性較強。文獻[5]提出一種基于密度的算法，該算法通過縮小維度來加快初始化的過程，不斷把可能的類簇中心移向高密度點，直到得到最大的K個最高密度點作為初始的類簇中心，但是該算法的運行迭代次數(shù)太高，運行時間較長。文獻[6]提出利用二分搜索方法來尋找最佳的K個初始類簇中心。文獻[7]提出一種基于密度的網(wǎng)格算法，該算法在Map-Reduce框架中確定K值的大小以及噪點的位置。文獻[8]提出了密度峰值進行快速搜索的聚類方法，算法假設(shè)類簇中心主要有兩個特征，一是具有較高的密度，二是距離比其密度大的類簇中心的最小距離較大。在計算出密度與最小距離決策圖時，可以很直觀地看到類簇中心和噪點，與文獻[4]一樣，該算法同樣需要人為指出數(shù)據(jù)集中的噪點，同時，對于截斷距離也有很大的主觀性。文獻[9]提出一種基于最小方差優(yōu)化初始中心的算法，避免了重復(fù)計算數(shù)據(jù)集到類簇中心的距離，減少了迭代次數(shù)，縮短了聚類時間。文獻[10]提出一種基于密度與特定閾值的改進K-means算法，該算法首先計算數(shù)據(jù)集中每個點的密度，然后利用閾值不斷迭代較小的密度點加入到類簇中心集合，直到集合中的元素個數(shù)到達K為止。文獻[11]提出一種基于數(shù)據(jù)集平均密度與最小距離的聚類算法，該算法計算密度較小的點距離較大點的最小距離，然后將最小距離與平均密度做乘積，由此來計算出離群點，反復(fù)迭代，不斷剔除離群點，直到剩下K個點來作為初始的類簇中心。文獻[12]為了減少K-means算法在數(shù)據(jù)量較大時運行時間較長的問題，提出在MapReduce平臺下運行多路K-means(Mux-Kmeans)算法。文獻[13]提出一種基于K-means的聚類算法，該算法包括兩個過程:利用K-means算法分割較為稀疏的子數(shù)據(jù)集，然后利用平均距離對已經(jīng)分割好的子數(shù)據(jù)集進行合并。文獻[14]提出一種基于密度與最佳距離的K-means初始中心選擇方法，該算法利用配置函數(shù)的最優(yōu)值選擇初始的類簇中心，同時也可以減小迭代次數(shù)。文獻[15]為了解決高維數(shù)據(jù)集聚類，提出了基于K-means算法的K-String算法。

為了解決傳統(tǒng)K-means算法在聚類過程中初始中心隨機選擇的缺陷，在研究基于密度與最小距離的K-means初始中心選擇算法原理和步驟分折的基礎(chǔ)上，提出了改進的K-means初始中心算法，并進行了驗證實驗和對比分析。

2 基于密度與最小距離的K-means算法聚類

傳統(tǒng)的K-means算法對于初始中心的選取比較敏感，因此，隨機性地選取初始中心可能會影響聚類結(jié)果的速度和穩(wěn)定性。而基于密度選取的初始中心則具有主觀性，例如，當(dāng)數(shù)據(jù)集中兩個數(shù)據(jù)點的密度一樣時，如何取舍會直接影響到聚類的結(jié)果。提出的算法綜合數(shù)據(jù)集中數(shù)據(jù)點的密度參數(shù)和最小距離參數(shù)，引入其他參數(shù)作為初始類簇中心的選取指標(biāo)。

2.1基本定義

設(shè)數(shù)據(jù)集中含有M個樣本數(shù)據(jù)，每個樣本有N個屬性，則任意數(shù)據(jù)可以表示為x=(x1,x2,…,xm)。

定義1：數(shù)據(jù)點x與y之間的距離為歐氏距離d(i,j):

d(i,j)=

(2)

定義2：截斷距離dc，定義為整個數(shù)據(jù)集中點與點之間距離的平均值:

(3)

定義3：樣本數(shù)據(jù)點pi的密度ρi。表示以pi為圓心，dc為半徑的圓，包含在圓內(nèi)其他數(shù)據(jù)點的數(shù)量之和。ρi越大，pi成為初始中心的可能性越大。

(4)

定義4：點pi到其他更高密度點之間的最小距離為δi，代表數(shù)據(jù)點pi與pj的不相似度，δi越大，說明該點距離其他較大的類簇中心越遠，即該點成為類簇中心的可能性較大。

δi=min(d(i,j)),j:ρj>ρi

(5)

對于密度ρi最大的點pi，其最小距離定義為：δi=minj(d(i,j))。

定義5：最終決定樣本點pi能否成為類簇中心的決定性參數(shù)θi，綜合點pi的密度與最小距離，其值直接決定此點是否能成為類簇中心。θi值越大，說明此點在擁有較大密度的同時，距離其他較高的類簇中心也較遠，即此點成為初始中心的可能性較大:

θi=ρi×δi

(6)

2.2算法描述

在K-means算法中，數(shù)據(jù)集中點的距離可以使用歐氏距離來衡量，選取數(shù)據(jù)集的平均距離dc作為截斷距離，有利于算法收斂。兩點之間的距離越小，說明兩點越相似,但是在初始類簇數(shù)目一定的情況下，選取一點作為初始的類簇中心關(guān)系到聚類結(jié)果的準(zhǔn)確性和迭代次數(shù)。假設(shè)類簇中心被其他較低密度的中心所包圍，在計算出每個點pi的密度ρi之后，同時計算pi距離較高密度類簇中心的最小距離θi,最后計算出pi點的參數(shù)θi。算法的詳細描述如下：

(1)根據(jù)定義1計算出數(shù)據(jù)集中任意兩點pi與pj的距離d(i,j),并根據(jù)定義2計算出數(shù)據(jù)集最大平均距離作為截斷距離dc。

(2)通過定義2及定義3計算出數(shù)據(jù)集中每個點的密度ρi及距較高密度類簇中心的最小距離δi。對于密度最大的點，δi定義為其他點到此點的最大距離。

(3)根據(jù)定義5計算出θi。

(4)選取K個具有較大θi的點作為K-means算法的初始類簇中心。

(5)利用K-means算法進行聚類。

如圖1所示，假設(shè)數(shù)據(jù)集最終被劃分為兩個類簇。截斷距離dc由數(shù)據(jù)集的平均距離確定后，以任意一點pi為中心，dc為半徑的圓所包含其他數(shù)據(jù)點的個數(shù)為pi點的密度ρi。圖中，密度較大的三點p1,p2,p3的密度分別為ρ1=4,ρ2=5,ρ3=6。在計算出每個點的密度后，可以看出p1距離密度較大的點為p2,p3，但是與p2的距離最小。密度較p2較大的點只有p3，由于p3是整個數(shù)據(jù)集中密度最大的點，所以在計算p3點的最小距離時，只需在數(shù)據(jù)集中計算距離p3最遠的點。計算出p1,p2,p3距離其他較高密度點的最小距離分別為δ1,δ2,δ3。選取θi=ρi×δi較大者作為初始類簇中心，在圖1的二維數(shù)據(jù)集中，假設(shè)要選取兩個類簇中心，由于p2,p3的θi較大，故選取p2,p3為初始的類簇中心。

圖1 二維數(shù)據(jù)的密度和最小距離表示

3 實 驗

3.1數(shù)據(jù)集描述

為了驗證上述算法選取初始類簇中心的有效性，選取了專用于測試聚類算法性能的UCI數(shù)據(jù)集。UCI是一個專門用于測試機器學(xué)習(xí)與數(shù)據(jù)挖掘算法的數(shù)據(jù)庫，庫中的每個數(shù)據(jù)集都有明確的分類，因此可以直觀表示聚類結(jié)果的質(zhì)量。對Iris,Wines,Seeds,Banlance-scale四個數(shù)據(jù)集進行了測試，按照準(zhǔn)確率、迭代次數(shù)來評價算法的性能。表1簡單介紹了實驗所用數(shù)據(jù)集的情況。

表1 UCI數(shù)據(jù)集描述

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

用到的K-means初始中心選取算法不僅計算數(shù)據(jù)集中每個數(shù)據(jù)點的密度值ρi，還將計算距離密度較高的點的最小距離δi，然后將其與密度做乘積得到θi。在四個數(shù)據(jù)集上隨機選取10個點作為初始的類簇中心，對提出算法與其他初始中心選取算法進行了實驗。表2為在Iris與Wine數(shù)據(jù)集上的實驗結(jié)果，表3為在Seeds與Balance-scale數(shù)據(jù)集上的實驗結(jié)果。

表2 Iris與Wine數(shù)據(jù)集的實驗結(jié)果

表3 Seeds與Balance-scale數(shù)據(jù)集的實驗結(jié)果

為了驗證提出算法較其他初始中心選取算法具有較好的性能，分別選取了傳統(tǒng)的初始中心算法與文獻[10]算法進行對比。

在實驗過程中發(fā)現(xiàn)，三種算法的類簇劃分個數(shù)相同，但實驗結(jié)果卻不同。傳統(tǒng)的隨機化初始中心算法無論是準(zhǔn)確率還是迭代次數(shù)都不穩(wěn)定，無法計算出θi較大者作為初始的類簇中心。

Iris數(shù)據(jù)集中，傳統(tǒng)初始中心選擇算法的準(zhǔn)確率和迭代次數(shù)都波動較大，十次實驗的平均準(zhǔn)確率為0.772 6，平均迭代次數(shù)為6.5，文獻[10]算法選擇的初始中心準(zhǔn)確率為0.893 3,在迭代7次后算法收斂。在利用提出算法選取的類簇中心實驗中，θi較大的三個點為(50,16,123),對應(yīng)的θi值為(950,930,1 276)，算法的迭代次數(shù)為5，準(zhǔn)確率為0.906 6。

Wine數(shù)據(jù)集中，傳統(tǒng)初始中心選擇算法的準(zhǔn)確率為0.696 5，平均迭代次數(shù)為6.3，而文獻[10]算法選擇初始中心的準(zhǔn)確率為0.707 8，迭代次數(shù)為5。利用提出算法計算出的θi較大的點為(132,32,78),對應(yīng)的θi值為(8 320,10 952,12 300)，算法的準(zhǔn)確率為0.747 1，迭代次數(shù)為6。

Seeds數(shù)據(jù)集中，傳統(tǒng)初始中心算法得到的平均準(zhǔn)確率為0.742 8，平均迭代次數(shù)為7.9，文獻[10]算法的平均準(zhǔn)確率為0.833 3，迭代次數(shù)為6。而在提出的初始中心選取算法中，計算出θi較大的點為(22,184,53)，對應(yīng)的θi值分別為(693,396,440)。在選取了相應(yīng)類簇中心后，利用K-means算法得到的聚類結(jié)果準(zhǔn)確率為0.885 7，迭代次數(shù)為5。

Balance-scale數(shù)據(jù)集是維度較大的數(shù)據(jù)集，傳統(tǒng)初始中心選擇算法的平均準(zhǔn)確率為0.592，平均迭代次數(shù)為8.9，文獻[10]算法得到的準(zhǔn)確率為0.550 4，迭代次數(shù)為12。利用提出算法得到θi較大的三個點為(122,262,476),對應(yīng)的θi值為(680,710,578),算法在迭代7次后收斂，聚類準(zhǔn)確率為0.67，可見初始中心選擇算法對高維數(shù)據(jù)同樣也有較高的準(zhǔn)確率與迭代速度。

4 結(jié)束語

在分析傳統(tǒng)的K-means初始中心選取算法和改進初始中心選取算法不足的基礎(chǔ)上，提出了一種基于密度與最小距離優(yōu)化的初始中心選擇算法。該算法根據(jù)數(shù)據(jù)集中每個數(shù)據(jù)對象的密度與最小距離來確定數(shù)據(jù)集中類簇的位置。實驗結(jié)果表明，該算法在消除K-means算法對于初始中心依賴性的同時，減小了迭代次數(shù)，提高了運行效率。

[1] MacQueen J.Some methods for classification and analysis of multivariate observations[C]//Proceedings of the fifth Berkeley symposium on mathematical statistics and probability.[s.l.]:[s.n.],1967:281-297.

[2] Hamerly G,Elkan C.Learning the K in K-Means[C]//Advances in neural information processing systems.[s.l.]:[s.n.],2004.

[3] Zhang Xuanyi,Shen Qiang,Gao Haiyang,et al.A density-based method for initializing the k-means clustering algorithm[C]//International conference on network and computational intelligence.[s.l.]:[s.n.],2012:46-53.

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

[5] Qiao J,Lu Y.A new algorithm for choosing initial cluster cen-ters for k-means[C]//Proceedings of the 2nd international conference on computer science and electronics engineering.Paris,France:Atlantis Press,2013:527-530.

[6] Kumar Y,Sahoo G.A new initialization method to originate initial cluster centers for K-Means algorithm[J].International Journal of Advanced Science and Technology,2014,62:43-54.

[7] Ma L, Gu L, Li B,et al.An improved k-means algorithm based on MapReduce and grid[J].International Journal of Grid and Distributed Computing,2015,8(1):189-200.

[8] Rodriguez A,Laio A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.

[9] 張曉倩,曲福恒,楊 勇,等.一種高效的基于初始聚類中心優(yōu)化的K-means算法[J].長春理工大學(xué)學(xué)報:自然科學(xué)版,2015(4):154-158.

[10] 何佳知,謝穎華.基于密度的優(yōu)化初始聚類中心K-means算法研究[J].微型機與應(yīng)用,2015,34(19):17-19.

[11] Yuan Q,Shi H,Zhou X.An optimized initialization center K-means clustering algorithm based on density[C]//IEEE international conference on cyber technology in automation,control,and intelligent systems.[s.l.]:IEEE,2015:790-794.

[12] Li C,Zhang Y,Jiao M,et al.Mux-Kmeans:multiplex kmeans for clustering large-scale data set[C]//Proceedings of the 5th ACM workshop on scientific cloud computing.[s.l.]:ACM,2014:25-32.

[13] Lin Y,Luo T,Yao S,et al.An improved clustering method based on k-means[C]//9th international conference on fuzzy systems and knowledge discovery.[s.l.]:IEEE,2012:734-737.

[14] Chu S Y,Deng Y N,Tu L L.K-means algorithm based on fitting function[C]//International conference on applied science and engineering innovation.[s.l.]:[s.n.],2015:1940-1945.

[15] Le V H,Kim S R.K-strings algorithm,a new approach based on Kmeans[C]//Proceedings of the 2015 conference on research in adaptive and convergent systems.[s.l.]:ACM,2015:15-20.

An Initial Center Algorithm ofK-means Based on Density and Minimum Distance

QI Hou-lin，GU Lei

(College of Computer,Nanjing University of Posts and Telecommunication,Nanjing 210003,China)

In order to overcome a large fluctuation caused by the traditionalK-means algorithm clustering with assignment of the random initial cluster centers,an algorithm taken the density and minimum distance as the parameters to determine the initial cluster centers is proposed,which calculates the density parameter of the data object according to certain rules and minimum distance between each data object and other data objects after having calculated single point density of each data in the data set.The larger one among the densities and minimum distances has been chosen as initial cluster center in the process ofK-means clustering.Experimental results show that it has higher accuracy and faster convergence rate compared with ones using randomly selected cluster centers and using density as a parameter forK-means clustering on standard UCI data set.

K-means algorithm;cluster center;density;minimum distance;iteration number

2016-09-07

：2016-12-22 < class="emphasis_bold">網(wǎng)絡(luò)出版時間

時間：2017-07-11

國家自然科學(xué)基金資助項目(61302157)

戚后林(1990-)，男，碩士研究生，研究方向為中文文本分類；顧 磊，副教授，碩士生導(dǎo)師，研究方向為中文信息處理、機器學(xué)習(xí)。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170711.1454.028.html

TP301.6

:A

:1673-629X(2017)09-0060-04

10.3969/j.issn.1673-629X.2017.09.013