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

戚后林，顧 磊

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

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

戚后林，顧 磊

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

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

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

1 概 述

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

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

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

輸入：類簇的數目k以及n個記錄的數據集；

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

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

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

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

(4)計算偏差：

(1)

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

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

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

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

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

2.1基本定義

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

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

d(i,j)=

(2)

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

(3)

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

(4)

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

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

(5)

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

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

θi=ρi×δi

(6)

2.2算法描述

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

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

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

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

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

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

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

圖1 二維數據的密度和最小距離表示

3 實 驗

3.1數據集描述

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

表1 UCI數據集描述

3.2實驗結果及分析

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

表2 Iris與Wine數據集的實驗結果

表3 Seeds與Balance-scale數據集的實驗結果

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

在實驗過程中發現，三種算法的類簇劃分個數相同，但實驗結果卻不同。傳統的隨機化初始中心算法無論是準確率還是迭代次數都不穩定，無法計算出θi較大者作為初始的類簇中心。

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

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

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

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

4 結束語

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

[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] 邢長征,谷 浩.基于平均密度優化初始聚類中心的k-means算法[J].計算機工程與應用,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] 張曉倩,曲福恒,楊 勇,等.一種高效的基于初始聚類中心優化的K-means算法[J].長春理工大學學報:自然科學版,2015(4):154-158.

[10] 何佳知,謝穎華.基于密度的優化初始聚類中心K-means算法研究[J].微型機與應用,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">網絡出版時間

時間：2017-07-11

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

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

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