基于鄰域密度的K-means初始聚類中心優選方法

雒明雪，苑迎春，陳江薇，王克儉

(河北農業大學 a.信息科學與技術學院； b.教務處，河北 保定 071000)

大數據時代，對海量數據進行聚類分析是目前研究的重要方向，已被廣泛應用于教育、電商、交通等領域[1-2]。聚類是根據物以類聚的思想，將數據對象分為不同簇，使簇內數據相似度高，而簇間數據相似度低。聚類算法通常有劃分法、密度法、模型法、圖論法等[3-9]。

K-means是劃分法中的經典算法，因其效率高、便于理解而被廣泛應用。但傳統K-means算法的初始聚類中心采用隨機選取方式，容易導致聚類結果陷入局部最優。同時，隨機方式還會導致初始聚類中心選擇具有不穩定性，使得聚類結果也不穩定。

針對K-means算法初始聚類中心選擇問題，許多學者做了大量研究。例如，通過引入群智能算法，采用自適應布谷鳥、引力搜索算法等優化初始簇中心，但由于算法計算復雜沒有得到應用[10-14]。一些學者從樣本數據密度和距離角度出發優化初始聚類中心。例如，馮勇等[15]、王子龍等[16]同時考慮局部密度和距離進行算法優化。唐澤坤等[17]、唐東凱等[18]則是分步考慮密度和距離，首先根據局部密度構建聚類候選中心集，再利用基于距離的算法選取初始聚類中心。唐澤坤等[17]權衡密度和距離對聚類的影響，對數據進行局部加權處理，利用最大最小原則選取初始中心點，但計算數據權重增加了時間消耗。唐東凱等[18]從局部密度角度提出LOF算法計算樣本點離群因子，并對離群因子進行排序，截取密度較高的樣本點，再從距離角度出發利用最大最小距離算法選出聚類中心，確保高密度簇中心的選取，但忽略了低密度簇被作為離群點，造成聚類中心選取不準確。同樣，由于對每個樣本進行LOF計算增加時間消耗，邵倫等[19]引入網格思想，根據聚類種類數K，將樣本數據映射到K維網格，然后將網格內樣本數較多且距離滿足定義距離的K個子網格作為初始聚類中心，以網格為最小單位進行計算，減少計算復雜度。但只考慮了單個網格密度，且候選網格集數目過多，算法后期基于距離進行選擇時未考慮離散數據集對聚類中心選擇的影響。

分析上述優化K-means聚類中心算法發現：① 基于密度和距離的優化算法，對初始聚類的選擇具有很好的效果，但對每個樣本進行密度計算，算法時間消耗較大；② 基于網格劃分的算法能夠大大減少計算時間消耗，但未對網格進行篩選，導致利用距離計算時聚類中心的選擇出現偏差。綜合上述問題，提出基于鄰域密度的K-means初始聚類中心優選方法，即NDK-means算法(optimization method ofk-means initial clustering center based on neighborhood density)，優化傳統初始聚類中心選取。NDK-means算法基于網格思想劃分數據集，并通過定義網格鄰域描述網格與其鄰域密度關系，實現較高密度網格的篩選；為進一步縮小候選集，擴大網格步長，合并候選集中的相鄰中心點；最后基于距離選取K個初始聚類中心。在UCI數據集上進行的實驗驗證了算法的聚類效果和收斂速度。

1 問題分析

邵倫等[19]的算法通過多維網格劃分，利用網格中數據點的數量代表網格密度，簡化了樣本點密度計算，但其在計算密度過程中僅計算網格密度，未考慮網格與其周圍網格的關系，同時未對網格進行篩選，導致數據點稀疏的網格也在候選中心集。另外，基于距離選擇聚類中心可能造成稀疏密度網格被選為初始聚類中心，如圖1所示，數據集中1個簇中含有分布較為稀疏的樣本點。邵倫等[19]的算法在選取時沒有剔除稀疏樣本點，致使稀疏區域被選中，影響聚類效果。圖1為邵倫等[19]算法的聚類中心圖。其中，三角形為真實聚類中心，十字形為初始聚類中心。

圖1 文獻[19]聚類中心圖

2 NDK-means算法

NDK-means算法以K-means算法為基礎，基于局部密度和距離因素對初始聚類中心選取進行改進。算法通過將數據集映射到不同網格實現樣本數據的初步分類，以網格為最小單元進行聚類，避免每個樣本參與復雜計算，減少資源消耗。在進行候選集的選擇時，計算網格與其鄰域網格的密度關系，篩選出多個局部高密度網格區域，避免稀疏簇被誤判為離群點，真實的聚類中心應處于簇中密度較高的區域。在同一簇中可能存在多個高密度網格，因此本文算法利用迭代的思想，通過不斷擴大網格步長將同一簇中的高密度網格中心合并，進一步縮小候選中心集。NDK-means算法聚類中心的選取思想與真實聚類相似，聚類中心應具有一定的距離。為避免選擇同一簇的高密度網格作為初始聚類中心，利用最大最小距離算法和網格密度選取初始聚類中心。

2.1 相關定義

NDK-means算法基于網格思想對數據集進行劃分，通過空間鄰域進行候選網格的篩選，確定候選中心集，相關定義如下：

定義1(網格鄰域)對任意一個網格Si，其相鄰網格集合稱為Si的網格鄰域，記作Fe(Si)。圖2所示是一個二維網格劃分示意圖，圖中Si的網格鄰域為Fe(Si)={Si1，Si2，Si3，Si4，Si5，Si6，Si7，Si8}，共8個相鄰網格單元。

圖2 網格劃分示意圖

定義2(網格密度)網格Si中樣本點的個數稱為網格密度，記作DSi。

定義3(鄰域密度)對任意一個網格Si，其網格鄰域中所有網格密度的均值稱為鄰域密度，記作SKi。公式如下：

其中：DSij為網格Si的第j個鄰域的網格密度；n為鄰域的個數。

聚類中心出于簇的高密度區域， 但不一定出于最高密度區域，因此采用均值的方式篩選高密度網格，而不是選擇網格密度大于鄰域任一網格密度的方式。鄰域密度反映了一個網格其相鄰網格的樣本聚集程度。通過對比該網格密度與其鄰域密度，可判定該網格是否是高密度網格，并確定是否為初始聚類中心點候選網格。

定義4(高密度網格)對任意一個網格Si，若其網格密度大于其網格鄰域密度，則網格Si稱為高密度網格。

令SRKi記作Si的網格密度與其網格鄰域密度的比值，則：

若SRKi>1，則網格Si屬于高密度網格。

高密度網格固定閾值的設定很難同時滿足密集簇、稀疏簇。對此，采取網格與其周圍鄰域密度關系確定高密度網格，減輕閾值設定的復雜度。

2.2 算法描述

NDK-means算法初始聚類中心選擇主要分為3步：

步驟1依據數據集屬性劃分多維網格空間；

步驟2確定初始聚類中心點候選網格集；

步驟3基于最大最小距離算法確定初始聚類中心點。

2.2.1劃分多維網格空間

數據集映射到多維網格的過程實際是解決網格劃分的大小問題，確定網格大小是問題的關鍵所在。網格劃分較大會使不同類別數據集劃分到同一網格中，無法正常選取聚類中心；反之，網格劃分較小則會導致網格過多，網格密度相似，無法根據密度剔除離群數據且計算量增大。基于王立英等[20]提出的網格劃分函數，考慮數據集大小和屬性個數，結合本文算法得到最終劃分函數，如式(3)所示。

(3)

其中：N為數據集大小;F為屬性個數;M為多維網格的各個維度網格數。

2.2.2確定初始聚類中心點候選網格集

完成多維網格劃分后，通過計算得到候選網格集。此時，在候選網格集中，同一簇中可能存在多個候選網格。為了進一步縮小候選網格集數量，采取合并思想，通過改變網格劃分、調整網格步長、擴大網格使同簇中相鄰網格合并，直到滿足數量公式。由此確定初始聚類中心點候選集的步驟如下：

步驟1根據式(3)劃分多維網格，計算網格DSi。

步驟2根據式(1)(2)計算得到高密度網格和候選網格集。

步驟3計算候選集網格的中心，形成候選中心集DR。網格中心計算方法如下：

對任意網格Si包含樣本x={xi1，xi2，…，xip}，其中p為網格中樣本點數量。網格內所有樣本屬性均值為網格中心，記作sci公式：

(4)

步驟4計算候選集合中元素數量，若不小于迭代因子則減少網格數量M=M-1，得到新的網格劃分。按網格密度排序，計算網格中心形成新的候選中心集。迭代因子為：

α=2×k

其中k為聚類種類數。

步驟5重復步驟4直到滿足迭代因子。得到最終候選中心集DR。

2.2.3確定初始聚類中心

由于距離較近的高密度網格可能來自于同一個簇，故選取相距較遠的高密度網格作為初始聚類中心。本文中根據最大最小距離算法思想，利用網格密度值，首先選擇密度最高網格的中心作為第1個初始聚類中心，鎖定高密度簇中心；然后依據最大最小距離算法選取剩余聚類中心點，排除了初始聚類中心的隨機性，具有穩定的準確性。算法描述如下：

Input：候選數據集DR，聚類個數k

Output：k個初始聚類中心

步驟1 選取DR中第1個元素作為初始聚類中心C1，加入聚類中心集合，則C={C1}。同時刪除DR中的第1個元素。

步驟2 根據最大最小距離原則，計算第i個初始中心Ci，加入聚類中心C={C1，…，Ci}，刪除中心；

步驟3 當集合C長度小于聚類個數k時，返回步驟2；

步驟4 輸出k個初始聚類中心。

2.2.4算法流程

綜合上述3個過程，NDK-means算法整體流程如下：

Input：數據集D，聚類個數k

Output：k個簇

步驟1對數據集D中數據對象，根據網格劃分公式劃分多維網格，計算網格密度；

步驟2根據網格密度，計算網格鄰域密度，確定初次候選初始聚類中心候選集，經過迭代，不斷合并網格，得到最終候選集。

步驟3在候選數據集上，利用最大最小距離算法，選出k個初始聚類中心。

步驟4根據步驟3得到初始聚類中心，繼續執行K-means算法，得出聚類結果。流程如圖3所示。

圖3 NDK-means算法流程框圖

2.2.5算法復雜度分析

本文算法優化K-means初始聚類中心的選取分為3個步驟：① 劃分多維網格空間，將每個數據點映射到空間網格中復雜度為O(n)；② 首先計算每個網格的鄰域密度，復雜度為O((3F-1)·M)，然后判斷每個網格是否為高密度網格，復雜度為O(M)，該步驟的算法復雜度為O(3F·M)；③ 基于距離選取初始聚類中心，該步驟的復雜度與網格候選集大小有關為常數。綜合以上步驟，NDK-means算法復雜度為MAX(O(n)，O(3F·M))。

3 實驗結果與分析

為充分驗證本文算法的效果，實驗分為2個部分：第1部分采用計算機模擬數據，將傳統K-means算法與本文NDK-means算法進行可視化對比；第2部分采用來自UCI實驗室的3個真實數據集，對傳統K-means算法、基于局部密度和距離的文獻[18]算法、基于網格劃分思想的文獻[19]算法和本文算法進行對比。實驗環境為PC機，具體配置：CPU為Intel Core i7-4510U，內存為8 G，硬盤為1T，Windows10操作系統。所有算法均使用Python3.2實現。

3.1 模擬數據集

使用python中make_blobs模塊生成數據集。數據集具有4個類別，包含100個二維數據點。通過此數據集對K-means算法和本文算法進行聚類實驗。各算法經過50次實驗，在聚類結果中隨機選取2組，如圖4所示是傳統K-means算法兩組實驗結果，圖5所示是本文改進算法兩組實驗結果，其中三角形代表實際聚類中心，十字形表示初始聚類中心。對比實驗結果可以發現：傳統K-means算法采取隨機方式選取初始聚類中心，迭代次數分別為7次、4次，迭代次數和聚類結果不穩定。改進算法迭代次數均為2次，這是由于改進算法選取的聚類中心與實際聚類中心接近，迭代次數較少且聚類結果穩定。

圖4 K-means聚類結果

圖5 NDK-means算法聚類結果

3.2 標準數據集

為了對NDK-means算法進行驗證，選取專門用于測試聚類算法性能的UCI數據庫。UCI數據庫是加州大學提出的用于機器學習的數據庫，是一個常用的標準測試數據集，每個數據集都有明確的分類，可以直接得到聚類效果。實驗對Iris、Seeds、New_thy這3個數據集進行測試，與傳統K-means 算法、文獻[18]算法和文獻[19]算法進行實驗對比。在3個測試集上分別運行20次，記錄每次結果。實驗數據集具體信息如表1所示。

表1 測試數據集信息

3.2.1準確率

表2是4種算法在不同數據集上的準確率。首先可以得到，NDK-means算法在測試數據集上的平均準確率均高于對比算法。本文算法在Iris、Seeds、New_thy數據集上準確率比原始K-means算法分別提升了10.63%、10.71%、13.01%，這是由于新算法采用網格鄰域密度篩選中心候選集，選出的聚類中心出于高密度區域，避免了數據集中離群點成為初始聚類中心的問題，使初始聚類中心更接近真實聚類中心。同時，采用最大最小距離算法在候選集中選取最終的聚類中心，避免了初始聚類中心相似的問題。還可以發現，因為傳統K-means算法隨機選取初始聚類中心，最好結果與最壞結果相差10%～27%，聚類結果不穩定。

表2 4種算法在不同數據集上準確率 %

本文算法在3個數據集上準確率比基于局部密度和距離的文獻[18]算法平均高出3.6%，且聚類結果穩定。文獻[18]算法雖然也采用局部密度的方式進行候選集選取，但其直接剔除局部密度較低的樣本點，導致無法識別低密度簇中心。文獻[18]算法在利用最大最小距離原則進行初始聚類中心選取時，采取隨機的方式，導致聚類結果不穩定。同時可以看到，本文算法在3個數據集上準確率比文獻[19]算法平均高出4.3%，其中在數據集New_thy上比文獻[19]高出10%。這是因為New_thy數據集中存在個別離群點，與其他數據點距離較遠。文獻[19]算法雖然同樣基于網格劃分進行初始聚類的優化，但其在網格劃分時，每一維網格數量由聚類數K決定，對離群數據敏感，導致影響最終聚類效果。而本文算法基于局部密度，避免了離群點的影響。

3.2.2迭代次數

本文算法、文獻[18]和文獻[19]算法均分為2個部分：第1部分為初始聚類中心的選取，第2部分基于初始聚類中心進行聚類。第2部分的3種算法的實現流程相同，本文針對后一部分進行迭代次數對比。圖6是4種算法在不同數據集上平均迭代次數比對。迭代次數表明了算法收斂的速度，收斂速度越快表明算法初始聚類中心的選擇越靠近真實聚類中心。從圖6可以看出：本文算法在3個數據集上迭代次數均遠遠小于其他算法，在3個數據集上平均迭代速度是文獻[18]算法的2倍，在New_thy數據集上迭代速度是文獻[19]的3倍。這是由于本文算法在選取初始聚類中心時采用鄰域密度思想，同時考慮到緊密簇和稀疏簇，進而減少了聚類部分的迭代次數，體現了本文算法對存在稀疏樣本點數據集的優勢，在提高準確率的同時，加速了聚類迭代過程。

圖6 4種算法在不同數據集上迭代次數直方圖

4 結論

針對傳統K-means算法初始聚類中心隨機選取易導致陷入局部最優、聚類結果不穩定，且對離群點敏感的問題，提出基于鄰域密度的改進K-means算法。借鑒文獻[19]中網格思想劃分樣本空間，基于網格相對密度進行候選集篩選，排除離群點干擾，使候選集范圍更加準確，同時利用合并思想，通過不斷迭代縮小聚類中心范圍，避免忽略稀疏簇中心；然后利用最大最小距離算法，選取聚類初始中心點，避免因相鄰高密度區域重復而陷入局部最優。在UCI數據集上實驗結果表明，本文算法較傳統K-means算法減少了迭代次數，聚類結果具有較好的準確率和穩定性，并且對噪聲數據不敏感。