一種基于密度的增量k－means 聚類算法研究

司福明

（安徽機電職業技術學院信息工程系，安徽蕪湖241002）

一種基于密度的增量k－means 聚類算法研究

司福明

（安徽機電職業技術學院信息工程系，安徽蕪湖241002）

介紹了k－means和DBSCAN聚類算法的基本原理和優缺點，針對傳統聚類算法無法有效處理高維混合屬性數據集的問題，對原有的數據歸一化方法進行改進，在k－means和DBSCAN聚類算法的基礎之上，結合增量聚類的思想和數據之間相異度的計算方法，提出了基于密度的增量k－means聚類算法，有效處理具有高維混合屬性的數據集，改進了數據相異度的計算方法。

k－means聚類算法；改進；數據相異度

0 引言

k－means算法是1967年由MacQueen首次提出的一種經典算法［1］，經常用于數據挖掘和模式識別中，是一種無監督式的學習算法，其使用目的是對幾何進行等價類的劃分，即對一組具有相同數據結構的記錄按某種分類準則進行分類，以獲取若干個同類記錄集［2］。k－means聚類是近年來數據挖掘學科的一個研究熱點和重點，這主要是因為它廣泛應用于地球科學、信息技術、決策科學、醫學、行為學和商業智能等領域。迄今為止，很多聚類任務都選擇該算法［3］。

1 k－means聚類算法

1．1 k－means基本思想

k－means聚類算法是經典的基于劃分的聚類算法，它的目標是將數據集劃分成k個簇，使每個簇中數據之間的相異度盡可能的小，而簇間數據之間的相異度盡可能的大［4］。由于k－means聚類算法思想較為簡單，因此k－means聚類算法得到了廣泛的應用。例如，基于距離的差異性函數，使得根據數據集的屬性，在同一個簇中的對象是“相似的”，而不同簇中的對象是“相異的”［5］。

劃分聚類算法需要預先指定簇數目或簇中心，通過反復迭代運算，逐步降低目標函數的誤差值，當目標函數收斂時，得到最終聚類結果［6］。這類方法分為基于質心的（Centroid－based）劃分方法和基于中心的（Medoid－based）劃分方法，而基于質心的劃分方法是研究最多的算法，其中k－means算法是最具代表和知名的［7］。

k－means算法基本思想：1）隨機的選k個點作為聚類中心；2）劃分剩余的點；3）迭代過程需要一個收斂準則，此次采用平均誤差準則；4）求質心（作為中心）；5）不斷求質心，直到不再發生變化時，就得到最終的聚類結果。

k－means聚類算法是一種廣泛應用的聚類算法［8］，計算速度快，資源消耗少，但是k－means算法與初始選擇有關系，初始聚類中心選擇的隨機性決定了算法的有效性和聚類的精度，初始選擇不一樣，結果也不一樣。其缺陷是會陷于局部最優［9］。

1．2 k－means算法實現步驟

k－means聚類算法的處理流程如下［10］：首先，隨機選擇k個對象，每個對象代表一個簇的初始均值或中心；對剩余的每個對象，根據其與各簇中心的距離，將它指派到最近（或最相似）的簇，然后計算每個簇的新均值，得到更新后的簇中心；不斷重復，直到準則函數收斂。通常采用平方誤差準則，即對于每個簇中的每個對象，求對象到其中心距離的平方和，這個準則試圖使生成的k個結果簇盡可能地緊湊和獨立。

1．3 k－means聚類算法的優缺點分析

k－means聚類算法自從被提出之后，在不同的科學研究領域得到了廣泛的研究與應用，并提出了大量不同的改進的k－means算法。究其原因，主要是因為k－means聚類算法具有思想簡單、易于實現以及可用于大規模數據集的并行聚類挖掘的優點。

k－means聚類算法的優點突出，然而其缺點也很明顯，k－means聚類算法主要有以下幾個方面的不足：

1）需要事先確定聚類個數k的大小。由于很多應用事先是無法確定k的大小的，如網絡社團的劃分，因此，k－means聚類算法的應用受到一定的限制。

2）k個初始聚類中心是隨機選擇的。由于隨機選擇k個初始聚類中心，導致算法對異常數據敏感，同時算法運行時間增加。

3）k－means聚類算法無法處理高維混合屬性數據。k－means聚類算法無法有效處理維度大于20的數據集合，同時k－means聚類算法只能處理屬性是數值型的數據，無法處理含有離散型、分類型和文本型屬性的數據。

（4）k－means聚類算法只能發現超球狀的簇。由于采用歐式距離的方式計算數據點之間的相異度，導致k－means聚類算法只能發現超球狀的簇，不能發現其他類型的簇。

2 DBSCAN聚類算法

2．1 DBSCAN聚類算法的基本思想

DBSCAN（Density－Based Spatial Clustering of Applications with Noise）聚類算法是經典的基于密度的聚類算法，它的目的是尋找數據集合中被密度低的區域分隔開的密度大于給定閾值的高密度區域，并將每個獨立的高密度區域組合成簇［11］。

對包含N個點的d維數據集合X＝｛x1，…，xi，…，xn｝，其中xi∈Rd，DBSCAN聚類算法中的相關定義如下：1）Eps鄰域：數據點xi的Eps鄰域，即以xi為圓心，Eps為半徑的超球狀區域內數據點的集合，記為（x）Eps i N；2）點的密度：任意一點xi的密度是以該點為圓心，Eps為半徑的區域內包含點的個數，記為density（xi），大小等于（x）Eps i N；3）核心點：將點的密度不小于給定閾值minPts的點稱為核心點，否則稱為邊界點；4）直接密度可達：如果點xi處于點xj的Eps鄰域內，且xj為核心點，則稱xi從xj直接密度可達；5）密度可達：若數據點集｛x1，…，x2，…，xm｝，其中x1＝xi，xm＝xj，且有xk從xk＋1直接密度可達，則稱xi從xj密度可達；6）密度連接：若存在點x0，使得xi和xj都從x0密度可達，則稱xi和xj密度連接。

DBSCAN聚類算法的基本思想是：依次計算數據集X中每個數據點的密度，將密度不小于給定閾值minPts的點標記為核心點；對任意一個核心點x，找出所有從x密度連接的數據點，與x一起組成一個簇；直到數據都處理完為止。

2．2 DBSCAN聚類算法的優缺點

DBSCAN聚類算法將簇定義為密度相連的數據點的最大集合，與k－means聚類算法相比，DBSCAN聚類算法的主要優點如下：1）DBSCAN算法不需要事先確定簇的個數以及選擇初始聚類中心，且可以發現任意形狀的簇；2）DBSCAN算法能夠識別噪聲數據點，且對數據點的輸入順序不敏感。

DBSCAN聚類算法的缺點主要有以下幾個方面：1）DBSCAN算法需要事先確定Eps和minPts 2個參數，而這2個參數的確定無規律可循。因此，DBSCAN算法對Eps和minPts參數比較敏感，參數稍微的變化就可能得到2個差別較大的聚類結果。2）DBSCAN聚類算法不能夠有效地處理數據分布比較均勻的數據集，DBSCAN算法無法有效處理維度較大的數據集。3）與k－means算法相比，DBSCAN算法在進行大規模數據聚類時的時間復雜度較高。

針對傳統聚類算法的缺點進行改進，并將其并行化是目前研究的熱點。本文的主要研究內容是在k－means以及DBSCAN聚類算法的基礎上提出改進的聚類算法，并對改進的聚類算法進行并行化，最后將改進的聚類算法應用到實際場景中。

3 DBIK－means聚類算法設計

綜合DBSCAN和k－means聚類算法的優點，結合增量的基本思想，提出了基于密度的增量kmeans聚類算法［12］。

3．1 DBIK－means聚類算法的基本思想

對含有n個節點的d維混合屬性數據集合X＝｛x1，…，xi，…，xn｝，其中xi∈Rd，DBIK－means聚類算法的基本思想如下［13］：首先，從集合X中任意選取一小部分數據集Y，Y X，且Y中數據個數遠小于n；對于任意一點yiY，計算yi的Eps鄰域，參數Eps大小為Y中所有點距離的均值。其次，對于任意一點yiY，如果yi的Eps鄰域內包含的數據點的個數不小于給定閾值minPts，即yi的密度不小于minPts，則將yi及其Eps半徑范圍內的點組合成一個基本簇；同時計算簇中離yi最遠的點與yi的距離Di。再次，對于任意兩個簇i和j，如果它們的中心點yi和yj之間的距離不大于2＊max（Di，Dj），則將兩個簇合并，同時計算新簇的中心點yk以及離中心點最遠的點與yk的距離Dk；重復本步，直到不再有簇被合并為止。

然后，對于集合Y中沒有劃分到任意簇的點ym，把ym劃分到與其相異度最小的簇中，同時更新簇的中心點。

最后，對于集合X中余下的任意點x，x∈XY，計算x與所有簇中心點距離的均值Dave以及離x最近的簇與x的距離Dmin。如果Dmin不大于Dave，則將x劃分到與其距離最近的簇中，否則以x為中心點生成一個新簇，更新簇中數據點個數有變化的簇的中心點。重復本步，直到所有的數據都被處理完［14－15］。

3．2 基于密度的增量的DBIK－means改進方法

改進的k－means算法以基于密度的k－means聚類結果為依據，對X－Y數據集合聚類。作為相異度的計算公式，DBIK－means聚類算法的偽代碼如下：

DBIK－means聚類算法可以發現若干任意形狀的簇，在準確率和時間復雜度方面，算法對數據的輸入順序和minPts參數不敏感，DBIK－means算法可以有效處理高維混合屬性的數據集［16］。

4 實驗與結果分析

為了檢驗DBIK－means聚類算法的準確度和時間復雜度，采用KDD CUP 99高維混合屬性數據集的子數據集kddcup．data＿10＿percent作為實驗數據，對DBIK－means算法進行仿真實驗。

實驗平臺：windows 7操作系統，Pentium（R）Dual－Core 2．0GCPU，eclipse編程軟件。

實驗分2個階段：第一階段主要為了檢驗算法的準確率，從kddcup．data＿10＿percent中選取12萬條記錄作為實驗數據；第二階段主要為了檢測算法的時間復雜度，從kddcup．data＿10＿percent中另外重新選取6個數據集，6個數據集的大小分別是從包含1萬條記錄遞增到包含6萬條記錄。

在試驗的第一階段中，12萬條記錄中各種入侵數據所占的比例與kddcup．data＿10＿percent中的基本一致，把12萬條記錄分為8個數據集然后進行測試，前4個經測試為訓練數據集，后4個經分析為測試數據集；訓練數據集內每個包含2．5萬條記錄，測試數據集每個則包含0．5萬條記錄；前3個訓練數據集分別只包含Dos、Probing和R2L類型異常的數據，第4個訓練數據集中包含了所有種類的異常數據。將DBIK－means聚類算法中的增量kmeans聚類算法在檢測率（TPR）和誤檢率（FPR）兩個方面進行比較，TPR和FPR的定義為［17－18］：TPR＝被正常識別的異常數據數／數據中異常數據總數，FPR＝被識別為異常數據的正常數據數／數據中正常數據總數。

在實驗的第二階段中，將DBIK－means聚類算法與IK－means聚類算法在時間復雜度方面進行比較，DBIK－means聚類算法的總體運行時間小于IK－means聚類算法；當數據集大小為1萬時，DBIK－means運行時間大于IK－means，主要是因為DBIK－means在確定簇的個數方面用時比較多，當數據集包含數據的個數逐漸增大時，DBIK－means算法在確定簇的個數用時所占整體運行時間的比例逐漸降低，此時其整體運行時間小于IK－means。

因此，通過分析得出，DBIK－means聚類算法較IK－means聚類算法在準確度和效率方面都得到提高。但改進算法對于具有密集噪聲點等方面數據處理時仍然存在一定的局限性，需要進一步完善。

［1］王曉東．計算機算法設計與分析［M］．北京：電子工業出版社，2008：102－127．

［2］陳燕．數據挖掘技術與應用［M］．北京：清華大學出版社，2011．

［3］石偉．無線傳感網絡機器人定位導航在減災救災中的應用［D］．北京：北京郵電大學，2012．

［4］張石磊，武裝．一種基于Hadoop云計算平臺的聚類算法優化的研究［J］．計算機科學，2012，39（10）：115－118．

［5］張琳，陳燕，汲業，等．一種基于密度的K－means算法研究［J］．計算機應用研究，2011，28（11）：71－73．

［6］Chang F，Dean J，Ghemawat S，et al．Bigtable：A distributed storage system for structured data［J］．ACM Transactions on Computer Systems（TOCS），2008，26（2）：1－4．

［7］Selim S Z，Al－Sultan K S．Analysis of global K－means，an incremental heuristic for minimum sum－of－squares clustering［J］．Journal of Classification，2005（2）：287－310．

［8］Bellman R，Dreyfus S．Applied dynamic programming［M］．New Jersey：Princeton University Press，1962．

［9］蘇金樹，張博鋒，徐昕．基于機器學習的文本分類技術研究進展［J］．軟件學報，2006，17（9）：1848－1859．

［10］周昭濤．文本分析聚類分析效果評價及文本表示法［D］．北京：中國科學院技術研究所，2005．

［11］朱顥東，鐘勇，趙向輝．一種優化初始中心點的KMeans文本聚類算法［J］．鄭州大學學報：理學版，2009（2）：30．

［12］黃震華，向陽，張波，等．一種進行K－Means聚類的有效方法［J］．模式識別與人工智能，2010（4）：517－521．

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

［14］Anil K J．Data clustering：50years beyond K－Means［J］．Pattern Recognition Letters，2010，31（8）：651－666．

［15］席景科．時空孤立點檢測算法研究［D］．徐州：中國礦業大學，2010：48－51．

［16］步媛媛，關忠仁．基于K－means聚類算法的研究［J］．西南民族大學學報，2009，35（1）：198－200．

［17］孫吉貴，劉杰，趙連宇．聚類算法研究［J］．軟件學報，2008，19（1）：48－61．

［18］陳燕．數據挖掘技術與應用［M］．北京：清華大學出版社，2011．

The Research on Incremental k－means Clustering Algorithm Based on Density

SI Fu－ming
（Department of Information Engineering，Anhui Technical College of Mechanical and Electrical Engineering，Wuhu Anhui 241002，China）

The basic principle，advantages and disadvantages of the k－means and DBSCAN clustering algorithms are firstly introduced in this article．Due to the fact that the traditional clustering algorithm can not effectively deal with high dimensional mixed datasets，it improves the original data normalization method．Based on the k－means and DBSCAN clustering algorithms，and the combination of incremental clustering and data dissimilarity in data calculation，it also puts forward an incremental k－means clustering algorithm based on density，which has improved the data dissimilarity algorithm．

density based；k－means clustering algorithm；improvement；data dissimilarity

TP305

A

1009－8984（2016）02－0099－04

10．3969／j．issn．1009－8984．2016．02．025

2016－03－11

安徽省教育廳2016年度高校自然科學研究重點項目（KJ2016A134）

司福明（1982－），男（漢），安徽蕪湖，講師，碩士主要研究數據挖掘技術，網絡化應用系統。