基于核密度估計的K-means聚類優化

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

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

基于核密度估計的K-means聚類優化

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

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

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

K-means聚類；密度偏差抽樣；核密度估計；數據挖掘

0 引 言

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

1 K-means聚類算法

K-means算法流程如下：

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

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

Step3：重新計算各類中心；

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

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

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

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

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

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

2 密度偏差抽樣

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

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

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

(1)一個分組內各個數據點被抽到的概率相同；

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

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

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

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

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

圖1 DBS與SRS的實驗對比

3 核密度估計

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

核密度估計定義如下：

(1)

(2)

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

(3)

常用的核函數有：

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

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

(3)Epanechnikov核函數：

(4)BiWeight核函數：

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

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

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

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

(4)

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

圖3 核密度估計

4 基于核密度估計的K-means聚類優化

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

步驟如下：

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

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

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

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

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

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

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

對圖1所示的數據集，進行K-means和使用了核密度估計優化的K-means聚類分析。實驗結果如表2所示。

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

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

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

5 結束語

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

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

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

[3] 張春陽,周繼恩,錢 權,等.抽樣在數據挖掘中的應用研究[J].計算機科學,2004,31(2):126-128.

[4] 盛開元,錢雪忠,吳 秦.基于可變網格劃分的密度偏差抽樣算法[J].計算機應用,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].計算機研究與發展,2004,41(10):1712-1719.

[8] 倪巍偉,陳 耿,吳英杰,等.一種基于局部密度的分布式聚類挖掘算法[J].軟件學報,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] 余 波,朱東華,劉 嵩,等.密度偏差抽樣技術在聚類算法中的應用研究[J].計算機科學,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

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

熊開玲(1992-)，男，碩士研究生，研究方向為數據挖掘；彭俊杰，博士，副教授，碩士生導師，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