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

(河北農(nóng)業(yè)大學(xué) a.信息科學(xué)與技術(shù)學(xué)院； b.教務(wù)處，河北 保定 071000)

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

K-means是劃分法中的經(jīng)典算法，因其效率高、便于理解而被廣泛應(yīng)用。但傳統(tǒng)K-means算法的初始聚類中心采用隨機選取方式，容易導(dǎo)致聚類結(jié)果陷入局部最優(yōu)。同時，隨機方式還會導(dǎo)致初始聚類中心選擇具有不穩(wěn)定性，使得聚類結(jié)果也不穩(wěn)定。

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

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

1 問題分析

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

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

2 NDK-means算法

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

2.1 相關(guān)定義

NDK-means算法基于網(wǎng)格思想對數(shù)據(jù)集進行劃分，通過空間鄰域進行候選網(wǎng)格的篩選，確定候選中心集，相關(guān)定義如下：

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

圖2 網(wǎng)格劃分示意圖

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

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

其中：DSij為網(wǎng)格Si的第j個鄰域的網(wǎng)格密度；n為鄰域的個數(shù)。

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

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

令SRKi記作Si的網(wǎng)格密度與其網(wǎng)格鄰域密度的比值，則：

若SRKi>1，則網(wǎng)格Si屬于高密度網(wǎng)格。

高密度網(wǎng)格固定閾值的設(shè)定很難同時滿足密集簇、稀疏簇。對此，采取網(wǎng)格與其周圍鄰域密度關(guān)系確定高密度網(wǎng)格，減輕閾值設(shè)定的復(fù)雜度。

2.2 算法描述

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

步驟1依據(jù)數(shù)據(jù)集屬性劃分多維網(wǎng)格空間；

步驟2確定初始聚類中心點候選網(wǎng)格集；

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

2.2.1劃分多維網(wǎng)格空間

數(shù)據(jù)集映射到多維網(wǎng)格的過程實際是解決網(wǎng)格劃分的大小問題，確定網(wǎng)格大小是問題的關(guān)鍵所在。網(wǎng)格劃分較大會使不同類別數(shù)據(jù)集劃分到同一網(wǎng)格中，無法正常選取聚類中心；反之，網(wǎng)格劃分較小則會導(dǎo)致網(wǎng)格過多，網(wǎng)格密度相似，無法根據(jù)密度剔除離群數(shù)據(jù)且計算量增大?；谕趿⒂⒌萚20]提出的網(wǎng)格劃分函數(shù)，考慮數(shù)據(jù)集大小和屬性個數(shù)，結(jié)合本文算法得到最終劃分函數(shù)，如式(3)所示。

(3)

其中：N為數(shù)據(jù)集大小;F為屬性個數(shù);M為多維網(wǎng)格的各個維度網(wǎng)格數(shù)。

2.2.2確定初始聚類中心點候選網(wǎng)格集

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

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

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

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

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

(4)

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

α=2×k

其中k為聚類種類數(shù)。

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

2.2.3確定初始聚類中心

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

Input：候選數(shù)據(jù)集DR，聚類個數(shù)k

Output：k個初始聚類中心

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

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

步驟3 當(dāng)集合C長度小于聚類個數(shù)k時，返回步驟2；

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

2.2.4算法流程

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

Input：數(shù)據(jù)集D，聚類個數(shù)k

Output：k個簇

步驟1對數(shù)據(jù)集D中數(shù)據(jù)對象，根據(jù)網(wǎng)格劃分公式劃分多維網(wǎng)格，計算網(wǎng)格密度；

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

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

步驟4根據(jù)步驟3得到初始聚類中心，繼續(xù)執(zhí)行K-means算法，得出聚類結(jié)果。流程如圖3所示。

圖3 NDK-means算法流程框圖

2.2.5算法復(fù)雜度分析

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

3 實驗結(jié)果與分析

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

3.1 模擬數(shù)據(jù)集

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

圖4 K-means聚類結(jié)果

圖5 NDK-means算法聚類結(jié)果

3.2 標(biāo)準(zhǔn)數(shù)據(jù)集

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

表1 測試數(shù)據(jù)集信息

3.2.1準(zhǔn)確率

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

表2 4種算法在不同數(shù)據(jù)集上準(zhǔn)確率 %

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

3.2.2迭代次數(shù)

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

圖6 4種算法在不同數(shù)據(jù)集上迭代次數(shù)直方圖

4 結(jié)論

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