熊開玲，彭俊杰，楊曉飛，黃 俊

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

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

熊開玲1，彭俊杰1，楊曉飛2，黃 俊2

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

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

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

0 引 言

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

1 K-means聚類算法

K-means算法流程如下：

Step1：隨機指定k個點作為初始化類中心點；

Step2：對每一個樣本x，將其分配到離它最近的聚類中心；

Step3：重新計算各類中心；

Step4：使用新的類中心，進行Step2并計算偏差J；

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

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

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

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

(3)K-means聚類算法不適用于大數(shù)據(jù)集的聚類問題。K-means聚類算法迭代過程中每次都需對所有的數(shù)據(jù)點進行計算，因此面對大數(shù)據(jù)集時算法的計算開銷巨大。

2 密度偏差抽樣

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

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

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

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

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

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

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

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

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

圖1 DBS與SRS的實驗對比

3 核密度估計

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

核密度估計定義如下：

(1)

(2)

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

(3)

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

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

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

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

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

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

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

圖2 窗寬h值的選擇對核密度估計的影響

曲線與實際曲線十分接近。

(4)

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

圖3 核密度估計

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

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

步驟如下：

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

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

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

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

(5)對樣本集進行K-means聚類。

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

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

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

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

由于兩次聚類結(jié)果一定會有差異，所以無法將兩次結(jié)果中的類一一對應(yīng)，因此為了方便對比實驗結(jié)果，引入如下定義：

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

5 結(jié)束語

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

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

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

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

[4] 盛開元,錢雪忠,吳 秦.基于可變網(wǎng)格劃分的密度偏差抽樣算法[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] 李存華,孫志揮,陳 耿,等.核密度估計及其在聚類算法構(gòu)造中的應(yīng)用[J].計算機研究與發(fā)展,2004,41(10):1712-1719.

[8] 倪巍偉,陳 耿,吳英杰,等.一種基于局部密度的分布式聚類挖掘算法[J].軟件學(xué)報,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ù)在聚類算法中的應(yīng)用研究[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

時間：2017-01-04

國家自然科學(xué)基金資助項目(61201446)

熊開玲(1992-)，男，碩士研究生，研究方向為數(shù)據(jù)挖掘；彭俊杰，博士，副教授，碩士生導(dǎo)師，CCF高級會員，研究方向為云計算。

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