一種基于局部密度的k-means算法

黎 凡，王 新，和曉萍，馬曉敏，黎吾鑫

（云南民族大學數學與計算機科學學院，云南昆明650500）

一種基于局部密度的k-means算法

黎 凡，王 新，和曉萍，馬曉敏，黎吾鑫

（云南民族大學數學與計算機科學學院，云南昆明650500）

摘要：針對k-means算法必須事先指定初始聚類數k，并且對初始聚類中心點比較敏感，聚類準則函數對求解的最優聚類數評價不理想，提出一種基于局部密度的啟發式生成初始聚類中心方法，在此基礎上設計一種準則函數自動生成聚類數目，改進了傳統k-means算法.實驗表明改進的算法比傳統k-means算法提高了聚類效率.

關鍵詞：k-means算法；局部密度；初始中心點；聚類準則函數

聚類是一種無指導的機器學習方法，是數據挖掘中一個重要分支，主要用于發現相似類別的數據以及從數據中識別特定的分布或模式，被廣泛地應用于人臉圖像識別、股票分析預測、搜索引擎、生物信息學、醫學及社會學等多種領域［1-4］.它基于“物以類聚”的原理，把一組個體按照相似性歸成若干類別（簇），使得同一類別的個體之間差異較小，不同類別的個體之間差別較大.目前已出現大量的聚類算法，總體來說可以分為5類：基于劃分的方法、基于層次的方法、基于密度的方法、基于網格的方法和基于模型的方法.

k-means算法作為目前應用最廣泛的一種基于劃分的方法，只適用于數值型屬性，對非球形簇處理效果不佳，具有簡單、高效的特性，它的聚類思想比較簡單，容易理解［2］.但是算法本身具有局限性，不能預測簇的個數，聚類結果易受初始中心點影響，聚類質量依賴準則函數的選取等.本文針對k-means算法存在的不足，提出一種基于局部密度的啟發式生成初始聚類中心方法，在此基礎上設計一種準則函數自動生成聚類數目，改進了傳統k-means算法，以提高聚類的質量和效果.

1 k-means算法

1.1 k-means算法基本思想

假設第Cj類中的樣本為｛xj1，xj2，...，xjnj｝，即包含nj個樣本，則聚類中心cj＝（，，...，，...，），其中為類中心cj的第p個屬性分量，則聚類中心的第p個屬性分量為：

輸入：聚類的數目k和包含n個對象的數據集；

輸出：滿足目標函數最小的k個簇；

Step 1從n個數據對象中任意選擇k個作為初始聚類中心；

Step 2計算每個對象與這些中心的距離，并且根據最小距離對相應的對象進行劃分；

Step 3計算每個類的均值作為新的中心，執行Step2；

Step 4循環執行Step 3和Step 2，直到準則函數E不再發生變化為止.

1.2 k-means算法的優缺點

k_means算法核心思想，主要通過計算點與點距離，找出使目標函數值最小的類，方法簡便，易于實現.其次，算法時間復雜度為O（tkn），其中t為迭代次數，k為聚類數目，n為聚類對象數目，通常k?t，t?n，比較有效.

然而，聚類個數需要事先給定，在對于數據對象分布不了解且不能估計的情況下，聚類數目的給出就有了主觀和盲目性，不適合的簇個數會造成不合理的硬性劃分，影響聚類質量；其次，初始中心點的選取具有隨機性，對噪聲比較敏感且很容易陷入局部最優，而不同的初始點得到的聚類結果有很大差異性.好的初始點會適當減少迭代次數，加快聚類收斂速度，提高聚類質量；壞的初始點會增加迭代次數，使聚類效果變差；最后，當簇之間大小不均，密度不均又相鄰較近時，處于稀疏的大簇邊界上的點很容易被錯分到與之相鄰的高密度的小簇中，從而影響聚類的質量［2-3］.

2 基于密度的初始中心點算法

現實世界中噪聲是永遠存在的，尤其是在大規模數據集中，將算法用在含有噪聲的數據中，肯定對算法質量產生影響，對數據進行去噪處理，消弱噪聲對算法的影響就很有必要.噪聲本身就是孤立點，根據孤立點本身特性，采用基于局部密度的方法，對于密度很小的點直接刪除掉，在剩余數據對象上進行聚類.下面介紹依據LOF算法［7-8］產生的基本概念.

2.1 基本定義

定義1 對象p的k距離（k-dist（p））.

對于一個正整數k，數據對象p的k距離記作k-dist（p）.在數據集D中，存在一個數據對象o，該數據對象與數據對象p之間的距離記作d（p，o）.滿足條件：

1）至少存在k個點o∈｛D／p｝，滿足d（p，o）≤k-dist（p）；

2）至多存在k-1個點o∈｛D／p｝，滿足d（p，o）＜k-dist（p）.

定義2 數據對象p的k距離鄰域

定義3 點p的密度記作density（p）），

其中q（i）表示Nk（p）中元素的個數.

定義3密度公式不同于LOF算法中定義，不需要計算p的可達距離，或者p的第k距離鄰域內所有數據對象到p的可達距離之和亦或平均距離之和，只需找出p的k距離，統計出p的k距離鄰域內對象的個數，密度值即為后者比前者，思想更為簡單，且計算量減少.

2.2 基于密度的初始化中心點算法

我們選取密度較高的點作為初始聚類中心，因為密度高的點不可能是孤立點且是聚類中心的可能性比較大，這樣可以減少聚類迭代次數，增進聚類收斂速度.對于初始聚類中心的選取采取最遠最優先策略［2］，即先從整個數據集中隨機選擇1個數據點作為第1個聚類初始點，然后從剩下的數據集中選擇離第1個中心最遠的數據點作為第2個中心，然后再從剩下的數據集中選擇離前2個中心所組成的集合最遠的數據點作為第3個中心，以此類推，直到選擇的中心數達到所要求的簇數為止.這一策略與聚類定義相呼應：不同類之間差別比較大，所以類中心點選取應盡可能遠.算法描述如下：

Step 1根據定義3計算所有樣本對象的密度density（xi），根據密度參數σ刪除孤立點（個數為n0），此時樣本對象的個數變為n＝n-n0（去除屬性噪聲），初始化中心點集M＝｛｝；

Step 2選擇密度最大的樣本對象記為m1，將m1從點集X剔除，存放到M中，利用公式（1）計算X剩下的點與m1距離最遠的點，記為m2，將m2從點擊X剔除，存放到M中；

Step 3重復Step 2直到M中有k個點，即M＝｛m1，m2，...，mk｝；

Step 4輸出初始中心點集M，算法結束.

該算法使用重新定義的密度公式，在Step 1直接去除屬性噪聲，算法時間上稍有縮減.但是在k-距離值給定和密度參數σ給定上和DBSCAN（基于密度算法）或LOF（孤立點檢測算法）等一樣，都需要憑經驗給出.在實際應用中我們可以多取幾組k-距離值，觀察算法結果輸出的密度值后，再確定密度參數值σ.

3 基于初始化中心點和加權準則函數的k-means算法

3.1 加權準則函數

一般準則函數的設計都注重兩方面，每個簇的內部應該是緊湊的，即類內距離盡可能小，各個簇之間應該盡可能遠，即類間距離盡可能大.所以就產生類內差異w（c）和類間差異b（c）2個概念［1］.

類內差異可以用多種距離函數來定義，最簡單的就是計算類的每一點到它的所屬類中心的距離平方和：

類間差異度量也有多種：min距離（2類中最為靠近的2個樣品點間的距離）、max距離（2類中最遠的2個樣品點間的距離）、類平均距離（分別位于2個類中任意2個點的平均距離）、類中心距離（2個類的聚類中心之間的距離），這里我們采取類中心距離：

聚類質量與類內差異和類間差異都有關系，類內差異越小，類間差異越大，聚類效果越好.而類的數目越多，類內差異就越小，類間差異就越大，所以應盡可能使聚類數目更大，但這與最初聚類的目的相違背，我們希望把盡可能多的點集中到較少類中.

基于這一思想提出一個聚類準則函數：J（c，k）＝w（c，k）*b（c，k），其中k為聚類數目，w（c，k）即w（c），b（c，k）即b（c）.實驗表明：w（c，k）會越變越小，趨于穩定的一個很小的值接近0，尤其從1個類至2個類，急劇減小，2個類至3個類次之；b（c，k）相比較b（c，k-1）一般呈現1～2倍增長.用w（c，k）來約束b（c，k），給b（c，k）一個減小的系數，來限制聚類數目的變大；用b（c，k）乘以w（c，k）來促使類的數目變多，類內差異縮小.由于b（c，k）的增長較顯著，起主要作用，所以J（c，k）越大，聚類質量越高.

J（c，k）仍有可改善之處，前面我們提到當簇之間大小不均且密度不均而相鄰較近時，處于稀疏的大簇邊界上的點很容易被錯分到與之相鄰的高密度的小簇中［3］，從而影響聚類的質量.簇一般情況是不同的，大小相同且密度相同的2個簇是很難出現的，所以，我們的準則函數在定義差異時，不應該只做簡單的簇間累加平方和，而應考慮簇本身的不同之處.

從k-means算法執行過程中我們發現，只要開始執行Step 2就會對所有的點進行一個分類，會把相應的點分配到對應的類中，從整體來看，數據集中不同數目的點分配到不同的簇中，數目多的點的簇當然會對準則函數的值貢獻比較大，數目少的點的簇對準則函數的值貢獻比較小，即使在Step 4重復計算均值中心直到算法結束為止，每一次迭代截止或者下一輪重復計算均值中心即將開始這一靜態點，都是不同數目的點分配到不同的簇中.鑒于此，我們采用概率中“期望—方差”思想，對于每一個簇做加權處理，加權系數為簇中點的數目除以數據集總數目；所以有：

mj為Cj中元素個數，n為數據集元素總個數.如文獻［3］經過加權重mj／n后，會使得簇中數目多的點對準則函數值貢獻較大，這樣在k_means算法的每一次迭代過程中，數據對象就會更傾向于被分配給數據對象數目較小的簇.于是當不同大小、不同密度的簇相鄰較近時，處于稀疏大簇邊界上的點被錯分到與之相鄰的高密度小簇中的可能性就會減少，從而改善聚類效果.

同上，J（c，k）最大時，聚類效果最好，用max（J（c，k））表示，此處k為最優聚類數目.

3.2 基于初始化中心點和加權準則函數的k_means算法

輸入：具有n個對象的樣本數據及k；

輸出：使準則函數最小的最優的聚類數k；

Step 1.1 調用基于密度的初始值中心算法來確定i個對象作為初始中心；

Step 1.2 計算每個對象與這些中心的距離，并且根據最小距離對相應的對象進行劃分，并記錄每一簇中元素的數目mj；

Step 1.3 更新簇的平均值；

Step 1.4 根據式（3）來計算準則函數J（c，k），循環執行Step 1.2和Step 1.3，直到其收斂為止；

Step 2 根據max（J（c，k））來搜索準則函數J（c，k）值最大的，記下相應的k值；

Step 3 結束.

本文算法的時間復雜度分析：首先在計算初始化中心點為O（n log（n））（用R-tree），當n很大時，計算量就會比較大；其次在自動生成聚類數目的時候，由于k≤，只需進行次循環，所以算法的總共時間復雜度為.算法一開始運用基于局部密度的方法消除初始值對聚類結果的影響，并對噪聲起到抑制作用.然后采用加權準則函數，對簇大小不一、密度差異較大情形，能做出較好區分.

4 實驗結果和分析

本文是在Matlab 7.0平臺上選擇UCI中Iris數據和Breast cancer數據，其中Iris為150行4個屬性的數據，Breast cancer為699行9個屬性的數據.圖2改進算法中k距離值為3，輸出結果后，得出密度參數σ＝3.849 1，用以刪除小于σ的10%孤立點14個后，在剩余136個點上的聚類.從圖上就可以看出，圖2的初始中心點（“cszxd”）比圖1更分散，更科學，比起隨機初始點的任意性，可以減少算法迭代次數.

表1 傳統k-means算法分成4類的40次試驗

比較表1，優化初始中心點后的k-means算法試驗恒分為4類，最大迭代次數恒為10次，比傳統kmeans算法（分成2或3類情況11次）更穩定，且除極少數情況，比傳統算法迭代次數更少，從而加快聚類收斂速度.

由圖3可以看出b（c，k）、w（c，k）、J（c，k）變化情況，在k＝3時，J（c，k）值最大，按照本文改進準則函數算法描述，經處理后Iris數據應該被劃分為3類.

用Breast cancer數據實驗，分成2類，傳統kmeans算法最大迭代次數為7次（最多出現），算法運行時間為0.062 s；改進的優化中心點算法依然刪除10%孤立點，在603個數據上為測試，最大迭代次數5次，算法運行時間為0.421 s.J（c，k）在k＝13時，取最大值，根據新的準則函數應劃分為13類.

5 結語

本文提出的算法能較好地選取初始中心點，加快算法收斂速度，且給出新的準則函數自生成聚類數目，不用事先給定聚類數目，取得與文獻［1］相當的效果；但在準則函數的構造方面也還有不足，應適當加系數，或限制b（c，k）過快增長.

參考文獻：

［1］汪中，劉桂全，陳恩紅.一種優化初始中心點的k-means算法［J］.模式識別與人工智能，2009，22（2）：299-304.

［2］苗潤華.基于聚類和孤立點檢測的數據預處理方法的研究［D］.北京：北京交通大學，2012.

［3］張雪鳳，張桂珍，劉鵬.基于聚類準則函數的改進kmeans算法［J］.計算機工程與應用，2011，47（11）：123-127.

［4］安愛芬.一種改進的k-means初始聚類中心選擇算法［J］.山西師范大學學報：自然科學版，2013，27（1）：30-34.

［5］李志.基于Web服務器日志挖掘的數據與處理研究［D］.成都：成都電子科技大學，2012.

［6］張琳，陳燕，汲業，等.一種基于密度的k-means算法研究［J］.計算機應用研究，2011，28（11）：4071-4074.

［7］任義麗，劉洪甫，吳俊杰，等.基于組合局部鼓勵點的噪聲處理算法［J］.中國科技論文，2013，8（7）：672-678.

［8］胡彩平，秦小麟.一種基于密度的局部離群點檢測算法DLOF［J］.計算機研究與發展.2010，47（12）：2110-2116.

［9］ZHANG Xuan-yi，SHEN Qiang，GAO Hai-yang，et al.A Density-Based Method for Initializing the k-means Clustering［C］／／Proceedings of 2012 International conference on Network and Computational Intelligence，IPCSIT.2012，46：46-53.

［10］FAHIM A M，SALEM A M，TORKEY F A，et al.An efficient enhanced k-means clustering algorithm［J］.Journal of Zhejiang University SCIENCE A，2006，7（10）：1626-1633.

（責任編輯 梁志茂）

中圖分類號：TP181

文獻標志碼：A

文章編號：1672-8513（2014）06-0439-04

收稿日期：2014-03-04.

基金項目：國家自然科學基金（61363022）；教育部人文社科基金（12YJA870019）.

作者簡介：黎凡（1990-），男，碩士研究生.主要研究方向：數據挖掘.

通信作者：王新（1963-），男，教授，碩士生導師.主要研究方向：數據挖掘.

An effective k-means algorithm based on local density

LI Fan，WANG Xin，HE Xiao-ping，MA Xiao-min，LI Wu-xin
（School of Mathematics and Computer Science，Yunnan Minzu University，Kunming 650500，China）

Abstract：In terms of the k-means algorithm，it must choose the initial clustering number，more sensitive to the initial cluster center but the evaluation is not ideal forclusteringcriterion function to solve the optimal number of clusters.This paper proposes a heuristic way based on the concept of local density to generate the initial cluster centers，and then designs a criterion function，which automatically generates the number of clusters.The traditional k-means algorithm is improved.The experiments show that this algorithm improves the efficiency of the traditional k-means algorithm.

Keywords：k-means algorithm；local density；initial cluster center；clustering criterion function