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

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

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

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

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

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

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

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

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

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

1 k-means算法

1.1 k-means算法基本思想

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

輸入：聚類的數(shù)目k和包含n個對象的數(shù)據(jù)集；

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

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

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

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

Step 4循環(huán)執(zhí)行Step 3和Step 2，直到準則函數(shù)E不再發(fā)生變化為止.

1.2 k-means算法的優(yōu)缺點

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

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

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

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

2.1 基本定義

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

對于一個正整數(shù)k，數(shù)據(jù)對象p的k距離記作k-dist（p）.在數(shù)據(jù)集D中，存在一個數(shù)據(jù)對象o，該數(shù)據(jù)對象與數(shù)據(jù)對象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 數(shù)據(jù)對象p的k距離鄰域

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

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

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

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

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

Step 1根據(jù)定義3計算所有樣本對象的密度density（xi），根據(jù)密度參數(shù)σ刪除孤立點（個數(shù)為n0），此時樣本對象的個數(shù)變?yōu)閚＝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-距離值給定和密度參數(shù)σ給定上和DBSCAN（基于密度算法）或LOF（孤立點檢測算法）等一樣，都需要憑經驗給出.在實際應用中我們可以多取幾組k-距離值，觀察算法結果輸出的密度值后，再確定密度參數(shù)值σ.

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

3.1 加權準則函數(shù)

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

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

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

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

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

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

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

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

同上，J（c，k）最大時，聚類效果最好，用max（J（c，k））表示，此處k為最優(yōu)聚類數(shù)目.

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

輸入：具有n個對象的樣本數(shù)據(jù)及k；

輸出：使準則函數(shù)最小的最優(yōu)的聚類數(shù)k；

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

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

Step 1.3 更新簇的平均值；

Step 1.4 根據(jù)式（3）來計算準則函數(shù)J（c，k），循環(huán)執(zhí)行Step 1.2和Step 1.3，直到其收斂為止；

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

Step 3 結束.

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

4 實驗結果和分析

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

表1 傳統(tǒng)k-means算法分成4類的40次試驗

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

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

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

5 結語

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

參考文獻：

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

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

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

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

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

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

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

［8］胡彩平，秦小麟.一種基于密度的局部離群點檢測算法DLOF［J］.計算機研究與發(fā)展.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-），男，碩士研究生.主要研究方向：數(shù)據(jù)挖掘.

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

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