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

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

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

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

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

分析上述優(yōu)化K-means聚類中心算法發(fā)現(xiàn)：① 基于密度和距離的優(yōu)化算法，對(duì)初始聚類的選擇具有很好的效果，但對(duì)每個(gè)樣本進(jìn)行密度計(jì)算，算法時(shí)間消耗較大；② 基于網(wǎng)格劃分的算法能夠大大減少計(jì)算時(shí)間消耗，但未對(duì)網(wǎng)格進(jìn)行篩選，導(dǎo)致利用距離計(jì)算時(shí)聚類中心的選擇出現(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)格思想劃分?jǐn)?shù)據(jù)集，并通過定義網(wǎng)格鄰域描述網(wǎng)格與其鄰域密度關(guān)系，實(shí)現(xiàn)較高密度網(wǎng)格的篩選；為進(jìn)一步縮小候選集，擴(kuò)大網(wǎng)格步長，合并候選集中的相鄰中心點(diǎn)；最后基于距離選取K個(gè)初始聚類中心。在UCI數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)驗(yàn)證了算法的聚類效果和收斂速度。

1 問題分析

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

圖1 文獻(xiàn)[19]聚類中心圖

2 NDK-means算法

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

2.1 相關(guān)定義

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

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

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

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

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

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

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

定義4(高密度網(wǎng)格)對(duì)任意一個(gè)網(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è)定很難同時(shí)滿足密集簇、稀疏簇。對(duì)此，采取網(wǎng)格與其周圍鄰域密度關(guān)系確定高密度網(wǎng)格，減輕閾值設(shè)定的復(fù)雜度。

2.2 算法描述

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

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

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

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

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

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

(3)

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

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

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

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

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

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

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

(4)

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

α=2×k

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

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

2.2.3確定初始聚類中心

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

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

Output：k個(gè)初始聚類中心

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

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

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

步驟4 輸出k個(gè)初始聚類中心。

2.2.4算法流程

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

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

Output：k個(gè)簇

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

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

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

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

圖3 NDK-means算法流程框圖

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

本文算法優(yōu)化K-means初始聚類中心的選取分為3個(gè)步驟：① 劃分多維網(wǎng)格空間，將每個(gè)數(shù)據(jù)點(diǎn)映射到空間網(wǎng)格中復(fù)雜度為O(n)；② 首先計(jì)算每個(gè)網(wǎng)格的鄰域密度，復(fù)雜度為O((3F-1)·M)，然后判斷每個(gè)網(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 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

3.2.1準(zhǔn)確率

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

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

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

3.2.2迭代次數(shù)

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

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

4 結(jié)論

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