熊開(kāi)玲，彭俊杰，楊曉飛，黃 俊

(1.上海大學(xué) 計(jì)算機(jī)工程與科學(xué)學(xué)院，上海 200444；2.中國(guó)科學(xué)院 上海高等研究院 公共安全中心，上海 201210)

基于核密度估計(jì)的K-means聚類(lèi)優(yōu)化

熊開(kāi)玲1，彭俊杰1，楊曉飛2，黃 俊2

(1.上海大學(xué) 計(jì)算機(jī)工程與科學(xué)學(xué)院，上海 200444；2.中國(guó)科學(xué)院 上海高等研究院 公共安全中心，上海 201210)

K-means聚類(lèi)算法作為一種經(jīng)典的聚類(lèi)算法，應(yīng)用領(lǐng)域十分廣泛；但是K-means在處理高維及大數(shù)據(jù)集的情況下性能較差。核密度估計(jì)是一種用來(lái)估計(jì)未知分布密度函數(shù)的非參數(shù)估計(jì)方法，能夠有效地獲取數(shù)據(jù)集的分布情況。抽樣是針對(duì)大數(shù)據(jù)集的數(shù)據(jù)挖掘的常用手段。密度偏差抽樣是一種針對(duì)簡(jiǎn)單隨機(jī)抽樣在分布不均勻的數(shù)據(jù)集下容易丟失重要信息問(wèn)題的改進(jìn)方法。提出一種利用核密度估計(jì)結(jié)果的方法，選取數(shù)據(jù)集中密度分布函數(shù)極值點(diǎn)附近的樣本點(diǎn)作為K-means初始中心參數(shù)，并使用核密度估計(jì)的分布結(jié)果，對(duì)數(shù)據(jù)集進(jìn)行密度偏差抽樣，然后對(duì)抽樣的樣本集進(jìn)行K-means聚類(lèi)。實(shí)驗(yàn)結(jié)果表明，使用核密度估計(jì)進(jìn)行初始參數(shù)選擇和密度偏差抽樣能夠有效加速K-means聚類(lèi)過(guò)程。

K-means聚類(lèi)；密度偏差抽樣；核密度估計(jì)；數(shù)據(jù)挖掘

0 引 言

隨著互聯(lián)網(wǎng)、物聯(lián)網(wǎng)等產(chǎn)業(yè)的發(fā)展，各種各樣包含高維和海量的大規(guī)模數(shù)據(jù)集被生成。針對(duì)大規(guī)模數(shù)據(jù)的數(shù)據(jù)分析也變得越來(lái)越普遍[1]。K-means聚類(lèi)算法作為一種應(yīng)用廣泛的經(jīng)典聚類(lèi)算法，在面對(duì)大規(guī)模結(jié)構(gòu)復(fù)雜的數(shù)據(jù)時(shí)，與其他數(shù)據(jù)挖掘方法一樣，表現(xiàn)得不太理想，主要集中在面對(duì)大數(shù)據(jù)時(shí)計(jì)算開(kāi)銷(xiāo)和時(shí)間開(kāi)銷(xiāo)成倍的增長(zhǎng)和選擇初始參數(shù)時(shí)變得極為困難兩個(gè)問(wèn)題上[2]。針對(duì)這樣的情況，通常在應(yīng)用特定的數(shù)據(jù)挖掘方法時(shí)(如聚類(lèi)、關(guān)聯(lián)規(guī)則等)，往往引入抽樣技術(shù)先從數(shù)據(jù)集抽取出一個(gè)樣本，然后在這個(gè)樣本數(shù)據(jù)集上進(jìn)行處理，最后將處理結(jié)果推廣到整個(gè)數(shù)據(jù)集[3]。簡(jiǎn)單隨機(jī)抽樣(SimpleRandomSampling,SRS)是一種簡(jiǎn)單高效的抽樣方法。SRS應(yīng)用廣泛但在不均勻或者傾斜嚴(yán)重的數(shù)據(jù)集中效果得不到保證[4]。由于許多自然現(xiàn)象都遵循如Zipf定律、二八定律等不均勻分布，因此簡(jiǎn)單隨機(jī)抽樣在許多數(shù)據(jù)集中并不適用。為此Palmer等提出了密度偏差抽樣方法(DensityBiasSampling,DBS)[5-6]。該方法被證明在分布不均勻的數(shù)據(jù)集中有較好的適應(yīng)性，數(shù)據(jù)簡(jiǎn)約性能較好[7]，但DBS需要預(yù)知數(shù)據(jù)集的分布。核密度估計(jì)(KernelDensityEstimation,KDE)是一種非參數(shù)估計(jì)方法，不需要有關(guān)數(shù)據(jù)分布的先驗(yàn)知識(shí)，是一種獲取數(shù)據(jù)集未知分布的有效方法。因此可以使用核密度估計(jì)解決密度偏差抽樣需要知道數(shù)據(jù)分布的問(wèn)題。此外，針對(duì)數(shù)據(jù)集較稠密區(qū)域更容易成為類(lèi)簇中心的特點(diǎn)[8]，使用核密度估計(jì)的結(jié)果選擇K-means的初始中心參數(shù)，并在大數(shù)據(jù)集時(shí)使用核密度估計(jì)的結(jié)果進(jìn)行密度偏差抽樣，然后使用抽樣樣本集進(jìn)行聚類(lèi)分析。實(shí)驗(yàn)結(jié)果表明，該方法可以在不影響聚類(lèi)結(jié)果的情況下有效減少聚類(lèi)過(guò)程的時(shí)間。

1 K-means聚類(lèi)算法

K-means算法流程如下：

Step1：隨機(jī)指定k個(gè)點(diǎn)作為初始化類(lèi)中心點(diǎn)；

Step2：對(duì)每一個(gè)樣本x，將其分配到離它最近的聚類(lèi)中心；

Step3：重新計(jì)算各類(lèi)中心；

Step4：使用新的類(lèi)中心，進(jìn)行Step2并計(jì)算偏差J；

Step5：如果J值收斂，則返回類(lèi)中心C并終止算法，否則回到Step2。

作為一種基于劃分的聚類(lèi)算法，由于算法簡(jiǎn)單，容易理解，所以K-means算法應(yīng)用廣泛。但是，K-means聚類(lèi)算法也有自身的局限性。主要缺陷表現(xiàn)如下[10]：

(1)K-means聚類(lèi)算法需要預(yù)先給出簇的數(shù)目K。而在實(shí)際應(yīng)用中，聚類(lèi)數(shù)據(jù)集究竟需要分成多少類(lèi)往往是未知的。

(2)K-means聚類(lèi)算法的聚類(lèi)結(jié)果受初始中心點(diǎn)選取的影響較大，初始中心點(diǎn)選取不當(dāng)很容易造成聚類(lèi)結(jié)果陷入局部最優(yōu)解甚至導(dǎo)致錯(cuò)誤的聚類(lèi)結(jié)果。

(3)K-means聚類(lèi)算法不適用于大數(shù)據(jù)集的聚類(lèi)問(wèn)題。K-means聚類(lèi)算法迭代過(guò)程中每次都需對(duì)所有的數(shù)據(jù)點(diǎn)進(jìn)行計(jì)算，因此面對(duì)大數(shù)據(jù)集時(shí)算法的計(jì)算開(kāi)銷(xiāo)巨大。

2 密度偏差抽樣

隨著互聯(lián)網(wǎng)、物聯(lián)網(wǎng)、大數(shù)據(jù)等領(lǐng)域的發(fā)展，大規(guī)模數(shù)據(jù)集越來(lái)越普遍，這些數(shù)據(jù)集的數(shù)據(jù)量對(duì)K-means算法所帶來(lái)的計(jì)算復(fù)雜度可以說(shuō)是災(zāi)難級(jí)的。由于K-means聚類(lèi)算法在處理大數(shù)據(jù)集時(shí)的效果不能令人滿(mǎn)意，并且該算法的計(jì)算開(kāi)銷(xiāo)較大。另一方面，由于大規(guī)模數(shù)據(jù)集本身的復(fù)雜度較高，因此對(duì)給定的大數(shù)據(jù)集進(jìn)行數(shù)據(jù)挖掘時(shí)，通常都是先抽取一個(gè)樣本數(shù)據(jù)集，然后在該樣本數(shù)據(jù)集上進(jìn)行處理，最后將樣本集處理的結(jié)果推廣到整個(gè)數(shù)據(jù)集。

簡(jiǎn)單隨機(jī)抽樣作為所有抽樣方法的基礎(chǔ)是目前應(yīng)用最廣泛的抽樣方法，該方法雖然原理簡(jiǎn)單但效率較高。不過(guò)在不均勻或者傾斜嚴(yán)重的數(shù)據(jù)集中效果得不到保證。Palmer等提出的密度偏差抽樣方法被證明在分布不均勻的數(shù)據(jù)集中有較好的適應(yīng)性，數(shù)據(jù)簡(jiǎn)約性能較好。

密度偏差抽樣是一種相對(duì)較新的抽樣策略。其主要流程是，先將原始數(shù)據(jù)集分成不同的組，各組大小(所含數(shù)據(jù)點(diǎn)的數(shù)量)表示該組的密度，然后按以下原則進(jìn)行抽樣[11]：

(1)一個(gè)分組內(nèi)各個(gè)數(shù)據(jù)點(diǎn)被抽到的概率相同；

(2)最終獲取的數(shù)據(jù)樣本集的分布特征與原始數(shù)據(jù)集的分布一致；

(3)各組抽樣概率的偏差依據(jù)各組大小的偏差；

(4)期望的樣本集的大小值已知。

綜合上述原則，當(dāng)數(shù)據(jù)集的分布為均勻分布時(shí)，各個(gè)分組的密度也應(yīng)該是一致的，這時(shí)密度偏差抽樣的結(jié)果與簡(jiǎn)單隨機(jī)抽樣的結(jié)果應(yīng)該是一樣的，因此，簡(jiǎn)單隨機(jī)抽樣可視為數(shù)據(jù)集在均勻分布密度偏差抽樣的特例。相對(duì)于簡(jiǎn)單隨機(jī)抽樣，密度偏差抽樣的優(yōu)勢(shì)主要是簡(jiǎn)約效果好、適應(yīng)性強(qiáng)[12]。

圖1中的原始數(shù)據(jù)是有20 000個(gè)數(shù)據(jù)點(diǎn)(x,y)的數(shù)據(jù)集，其中4個(gè)組都使用高斯分布生成。當(dāng)對(duì)其進(jìn)行2%的抽樣時(shí)，發(fā)現(xiàn)進(jìn)行DBS抽樣兩個(gè)較小的數(shù)據(jù)集能夠保留在抽樣結(jié)果中，但是使用SRS抽樣時(shí)，較小的數(shù)據(jù)集完全消失了。通過(guò)結(jié)果對(duì)比可知，當(dāng)數(shù)據(jù)集屬于不均勻分布時(shí)，使用密度偏差抽樣的結(jié)果較使用簡(jiǎn)單隨機(jī)抽樣時(shí)的結(jié)果更優(yōu)。因此為了更好地保證抽樣所得的樣本集能夠反映整個(gè)數(shù)據(jù)集的特征，需要知道數(shù)據(jù)集的密度分布。

圖1 DBS與SRS的實(shí)驗(yàn)對(duì)比

3 核密度估計(jì)

核密度估計(jì)是求解給定的隨機(jī)變量集合分布密度問(wèn)題的非參數(shù)估計(jì)方法之一，用來(lái)解決與之相對(duì)的參數(shù)估計(jì)方法所獲得結(jié)果性能較差的缺陷問(wèn)題。在參數(shù)估計(jì)方法中需要先對(duì)數(shù)據(jù)集做相關(guān)假定數(shù)據(jù)集的分布，然后求解假定函數(shù)中的未知參數(shù)。但是通常假定的密度函數(shù)模型與實(shí)際密度函數(shù)之間相差較大。由于核密度估計(jì)不需要對(duì)數(shù)據(jù)集做相關(guān)假設(shè)，只是從數(shù)據(jù)集本身出發(fā)研究數(shù)據(jù)集的分布特征，所以KDE自提出以來(lái)就在各個(gè)領(lǐng)域廣泛應(yīng)用。

核密度估計(jì)定義如下：

(1)

(2)

理論上，任何函數(shù)均可以做核函數(shù)，但是為了密度函數(shù)估計(jì)的方便性與合理性，通常要求核函數(shù)滿(mǎn)足以下條件[14]：

(3)

常用的核函數(shù)有：

(1)高斯核函數(shù)(Gaussiankernel)：

(2)矩形窗核函數(shù)(boxcar)：

(3)Epanechnikov核函數(shù)：

(4)BiWeight核函數(shù)：

另外，窗寬參數(shù)h控制了在求點(diǎn)h處的近似密度時(shí)不同距離樣本點(diǎn)對(duì)點(diǎn)密度的影響程度。當(dāng)h選擇過(guò)大時(shí)會(huì)出現(xiàn)過(guò)光滑情況(OverSmoothed)，當(dāng)h選擇過(guò)小時(shí)會(huì)出現(xiàn)不夠光滑(UnderSmoothed)的情況[15]。

如圖2所示，使用正太分布隨機(jī)產(chǎn)生100個(gè)隨機(jī)數(shù)，虛線是其實(shí)際概率密度函數(shù)曲線，使用不同窗寬h進(jìn)行核密度估計(jì)時(shí)，得出如圖所示結(jié)果。當(dāng)h=0.05時(shí)的KDE密度函數(shù)曲線波動(dòng)頻繁，當(dāng)h=2時(shí)，曲線較為光滑但與實(shí)際相差甚遠(yuǎn)。在實(shí)際概率密度曲線與h=2之間的是h=0.337時(shí)的KDE密度函數(shù)曲線，該

圖2 窗寬h值的選擇對(duì)核密度估計(jì)的影響

曲線與實(shí)際曲線十分接近。

(4)

當(dāng)對(duì)圖1中的原始數(shù)據(jù)集進(jìn)行高斯核估計(jì)時(shí)，可以得到如圖3所示的密度分布。

圖3 核密度估計(jì)

4 基于核密度估計(jì)的K-means聚類(lèi)優(yōu)化

由圖3顯示，原始數(shù)據(jù)集中數(shù)據(jù)點(diǎn)越稠密的地方密度函數(shù)值越大，而密度函數(shù)的極大值點(diǎn)也與原始數(shù)據(jù)集的稠密區(qū)域中心十分接近。因此為了減少K-means聚類(lèi)的迭代次數(shù)，可以選擇核密度函數(shù)的極大值點(diǎn)作為K-means初始迭代中心。另外，可以通過(guò)設(shè)置半徑閾值，將距離小于半徑閾值的極大值點(diǎn)歸并到一個(gè)類(lèi)；設(shè)置密度閾值，將密度小于密度閾值的極大值區(qū)域作為噪聲去除，因?yàn)檫@些區(qū)域在整個(gè)數(shù)據(jù)集中所占的權(quán)重過(guò)低。通過(guò)半徑閾值和密度閾值的過(guò)濾，就可以確定一個(gè)聚類(lèi)數(shù)目K。當(dāng)數(shù)據(jù)集較大時(shí)，可以使用核密度估計(jì)函數(shù)對(duì)數(shù)據(jù)集進(jìn)行密度偏差抽樣，以此來(lái)約簡(jiǎn)數(shù)據(jù)集。

步驟如下：

(1)對(duì)數(shù)據(jù)集進(jìn)行高斯核密度估計(jì)獲取數(shù)據(jù)集密度分布；

(2)根據(jù)密度分布設(shè)定半徑閾值和密度閾值；

(3)根據(jù)半徑閾值和密度閾值獲取K-means算法的參數(shù)K和初始聚類(lèi)中心；

(4)對(duì)數(shù)據(jù)集進(jìn)行密度偏差抽樣獲取樣本集；

(5)對(duì)樣本集進(jìn)行K-means聚類(lèi)。

實(shí)驗(yàn)1使用來(lái)自UCIKDDArchive中的SyntheticControlChartTimeSeries的數(shù)據(jù)集(600條、維度為60維)，數(shù)據(jù)樣本較小，但維度較高。使用核密度估計(jì)選擇的初始聚類(lèi)中心和使用隨機(jī)選擇的初始聚類(lèi)中心的K-means，在未使用密度偏差抽樣的情況下進(jìn)行多次實(shí)驗(yàn)。表1是兩種情況下迭代次數(shù)對(duì)比以及樣本點(diǎn)的類(lèi)內(nèi)總距離的對(duì)比，其結(jié)果表明，在聚類(lèi)效果差不多的情況下，核密度估計(jì)初始參數(shù)選擇的迭代次數(shù)較隨機(jī)初始參數(shù)更少。

表1 利用核密度估計(jì)選擇迭代初始參數(shù)與隨機(jī)初始參數(shù)聚類(lèi)對(duì)比

對(duì)圖1所示的數(shù)據(jù)集，進(jìn)行K-means和使用了核密度估計(jì)優(yōu)化的K-means聚類(lèi)分析。實(shí)驗(yàn)結(jié)果如表2所示。

表2 使用了核密度估計(jì)初始參數(shù)選擇和密度偏差抽樣的K-means結(jié)果對(duì)比

由于兩次聚類(lèi)結(jié)果一定會(huì)有差異，所以無(wú)法將兩次結(jié)果中的類(lèi)一一對(duì)應(yīng)，因此為了方便對(duì)比實(shí)驗(yàn)結(jié)果，引入如下定義：

表2中的結(jié)果表明，使用核密度估計(jì)優(yōu)化后的K-means迭代次數(shù)較少，結(jié)果與直接使用K-means的相差不大，并且迭代次數(shù)較為穩(wěn)定，相比隨機(jī)參數(shù)初始化的K-means受初始參數(shù)的影響較小。如第6組實(shí)驗(yàn)中，使用隨機(jī)參數(shù)初始化的K-means就陷入了局部最優(yōu)解，因此結(jié)果差距較大。

5 結(jié)束語(yǔ)

提出了一種利用核密度估計(jì)結(jié)果的方法。通過(guò)實(shí)驗(yàn)結(jié)果表明，使用核函數(shù)密度估計(jì)所選取的K-means初始參數(shù)，可以在盡量不影響聚類(lèi)效果的基礎(chǔ)上有效減少K-means的迭代次數(shù)，同時(shí)在數(shù)據(jù)集較大時(shí)，可以使用核密度估計(jì)的結(jié)果對(duì)數(shù)據(jù)集進(jìn)行密度偏差抽樣，有效地簡(jiǎn)約數(shù)據(jù)量，從而加速聚類(lèi)過(guò)程。

[1] 程學(xué)旗,靳小龍,王元卓,等.大數(shù)據(jù)系統(tǒng)和分析技術(shù)綜述[J].軟件學(xué)報(bào),2014,25(9):1889-1908.

[2] 孫吉貴,劉 杰,趙連宇.聚類(lèi)算法研究[J].軟件學(xué)報(bào),2008,19(1):48-61.

[3] 張春陽(yáng),周繼恩,錢(qián) 權(quán),等.抽樣在數(shù)據(jù)挖掘中的應(yīng)用研究[J].計(jì)算機(jī)科學(xué),2004,31(2):126-128.

[4] 盛開(kāi)元,錢(qián)雪忠,吳 秦.基于可變網(wǎng)格劃分的密度偏差抽樣算法[J].計(jì)算機(jī)應(yīng)用,2013,33(9):2419-2422.

[5]PalmerCR,FaloutsosC.Densitybiasedsampling:animprovedmethodfordataminingandclustering[J].ACMSIGMODRecord,2000,29(2):82-92.

[6]HotiF.Onestimationofaprobabilitydensityfunctionandthemode[J].AnnalsofMathematicalStatistics,2003,33(3):1065-1076.

[7] 李存華,孫志揮,陳 耿,等.核密度估計(jì)及其在聚類(lèi)算法構(gòu)造中的應(yīng)用[J].計(jì)算機(jī)研究與發(fā)展,2004,41(10):1712-1719.

[8] 倪巍偉,陳 耿,吳英杰,等.一種基于局部密度的分布式聚類(lèi)挖掘算法[J].軟件學(xué)報(bào),2008,19(9):2339-2348.

[9]MacQueenJB.Somemethodsforclassificationandanalysisofmultivariateobservations[C]//Proceedingsof5thBerkeleysymposiumonmathematicalstatisticsandprobability.California:UniversityofCaliforniaPress,1967:281-297.

[10]RosenblattM.Remarksonsomenonparametricestimatesofadensityfunction[J].TheAnnalsofMathematicalStatistics,1956,27:832-837.

[11] 余 波,朱東華,劉 嵩,等.密度偏差抽樣技術(shù)在聚類(lèi)算法中的應(yīng)用研究[J].計(jì)算機(jī)科學(xué),2009,36(2):207-209.

[12]DudoitS,FridlyandJ.Aprediction-basedresamplingmethodforestimatingthenumberofclustersinadataset[J].GenomeBiology,2002,3(7):1-21.

[13]JonesMC,MarronJS,SheatherSJ.Abriefsurveyofbandwidthselectionfordensityestimation[J].JournaloftheAmericanStatisticalAssociation,1996,91(433):401-407.

[14]Buch-LarsenT，NielsenJP，GuillénM.Kerneldensityestimationforheavy-taileddistributionsusingthechampernownetransformation[J].Statistics,2005,39(6):503-518.

[15]ParkBU,MarronJS.Comparisonofdata-drivenbandwidthselectors[J].JournaloftheAmericanStatisticalAssociation,1990,85(409):66-72.

K-means Clustering Optimization Based on Kernel Density Estimation

XIONG Kai-ling1，PENG Jun-jie1，YANG Xiao-fei2，HUANG Jun2

(1.School of Computer Engineering and Science,Shanghai University,Shanghai 200444,China; 2.Public Security Center,Shanghai Advanced Research Institute,Chinese Academy of Sciences, Shanghai 201210,China)

K-meansclusteringalgorithmisclassicalandwidelyusedinmanyfields,butithaspoorperformanceinthecaseofprocessinghighdimensionalandlargedatasets.Kerneldensityestimationisanonparametricestimationmethodtoestimatethedensityfunctionofunknowndistribution,whichcaneffectivelyobtainthedistributionofthedataset.Samplingisacommonmethodfordatamininginlargedatasets.Densitybiasedsamplingisanimprovedmethodfortheproblemofeasylossofimportantinformationwhenusingthesimplerandomsamplingintheinclineddataset.Amethodisproposedusingresultofkerneldensityestimation,whichchoosessamplepointsfromneighborhoodofpeakofdensityfunctionofdatasetastheinitialcenterparametersofK-meansandusesresultofkerneldensityestimationtoperformdensitybiasedsamplingonthedataset,thenrunsK-meansclusteringonthesampleset.TheexperimentalresultsshowthatusingthekerneldensityestimationforselectionofinitialparametersanddensitybiassamplecaneffectivelyacceleratetheK-meansclusteringprocess.

K-meansclustering;densitybiassampling;kerneldensityestimation;datamining

2016-03-28

2016-07-05

時(shí)間：2017-01-04

國(guó)家自然科學(xué)基金資助項(xiàng)目(61201446)

熊開(kāi)玲(1992-)，男，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘；彭俊杰，博士，副教授，碩士生導(dǎo)師，CCF高級(jí)會(huì)員，研究方向?yàn)樵朴?jì)算。

http://www.cnki.net/kcms/detail/61.1450.TP.20170104.1039.074.html

TP

A

1673-629X(2017)02-0001-05

10.3969/j.issn.1673-629X.2017.02.001