杜洪波，白阿珍，朱立軍

（1.沈陽工業(yè)大學(xué) 理學(xué)院，沈陽 110870；2.北方民族大學(xué) 信息與計(jì)算科學(xué)學(xué)院，銀川 750021）

0 引言

數(shù)據(jù)的爆炸式增長是大數(shù)據(jù)時(shí)代到來的一個(gè)顯著性的標(biāo)志。雖然，數(shù)據(jù)量是大的，但是，數(shù)據(jù)中蘊(yùn)含的知識只是其中很小的一部分。如果能將數(shù)據(jù)中蘊(yùn)含的知識提取出來加以利用會(huì)帶來重大價(jià)值。傳統(tǒng)的工具和軟件技術(shù)在處理大規(guī)模數(shù)據(jù)時(shí)已經(jīng)顯得力不從心，因此，為了找出數(shù)據(jù)中有價(jià)值的知識，人們經(jīng)過不懈地探索，發(fā)現(xiàn)了數(shù)據(jù)挖掘技術(shù)。而聚類分析是該技術(shù)的一個(gè)研究熱點(diǎn)，并且，往往用來做分類工作。

聚類分析(ClusterAnalysis)又被稱為群分析，為無監(jiān)督學(xué)習(xí)，并且，它無需任何先驗(yàn)知識就可以發(fā)現(xiàn)數(shù)據(jù)的分布模式[1，2]?！拔镆灶惥邸睘樗年P(guān)鍵特征。自聚類出現(xiàn)以來，出現(xiàn)了許多不同類型的算法來滿足聚類的不同需求和挑戰(zhàn)，其中包括基于劃分的聚類算法[3]、基于層次的聚類算法[4]、基于密度的聚類算法[5]、基于網(wǎng)格的聚類算法[6]和基于模型的聚類算法[7]以及近幾年提出的新的聚類算法[8]。

K-means算法是典型的基于劃分的聚類算法。由于其優(yōu)點(diǎn)而在實(shí)際中被廣泛應(yīng)用[9]，但是，其也存在著一些缺點(diǎn)。學(xué)者們根據(jù)應(yīng)用環(huán)境不同以及實(shí)際要求，以經(jīng)典的K-means算法為基礎(chǔ)，針對其存在的多種缺陷，提出很多改進(jìn)算法。

針對算法對初始聚類中心敏感的不足之處，薛衛(wèi)等[10]提出一種空間密度相似性度量K-means算法，該算法利用可伸縮空間密度的相似性距離來度量數(shù)據(jù)點(diǎn)之間的相似度，并將密度和距離一起當(dāng)作選擇初始聚類中心的相關(guān)因子，以及根據(jù)類內(nèi)距離進(jìn)行迭代的一種新的類中心迭代模型，實(shí)驗(yàn)證明，該算法可得到更加合理的初始聚類中心。賈瑞玉等[11]基于密度的原理，通過對數(shù)據(jù)對象密度計(jì)算方式的再定義，并利用殘差分析從決策圖中自動(dòng)確定K值和初始聚類中心?？紤]到K值選擇的盲目性，張承暢等[12]提出一種基于密度的K-means改進(jìn)算法，此算法定義了權(quán)值積，它是樣本密度、簇內(nèi)樣本平均距離的倒數(shù)以及簇間距離三者的乘積，并通過最大權(quán)值積法解決最佳K值確定以及初始聚類中心問題。陳書會(huì)等[13]基于人工魚群原理提出了一種人工魚群和K-means相結(jié)合的IAFSA-KA算法[13]。為了解決運(yùn)用歐式距離度量相似性而導(dǎo)致只能發(fā)現(xiàn)球狀簇的問題，肖琦[14]利用GSAGSA肘形判據(jù)、距離代價(jià)函數(shù)等算法優(yōu)化確定最優(yōu)聚類K值，并依據(jù)密度參數(shù)來提取合理的初始聚類中心。

DPC算法是2014年由AlexRodriguez和Alessandro在Laio Science上發(fā)表的一篇名為《Clusteringby fast searchandfindofdensitypeaks》的核心算法，文章一經(jīng)發(fā)表就引起了眾多學(xué)者的關(guān)注。該算法簡潔而優(yōu)美，并且其能夠快速發(fā)現(xiàn)任意形狀數(shù)據(jù)集的密度峰值點(diǎn)（即聚類中心），并且，能夠?qū)颖军c(diǎn)進(jìn)行高效率地分配以及有效地剔除離群點(diǎn)，容易確定參數(shù)，適用于大量數(shù)據(jù)的聚類算法。

DPC算法[8]對初始聚類中心的確定很有針對性，因此，該算法作為一個(gè)關(guān)鍵步驟而應(yīng)用到數(shù)據(jù)挖掘中[15]。但是，該算法也存在一定的缺陷。謝娟英等[15]基于K近鄰思想提出的K-CBFSAFODP算法能夠很好地解決DPC算法密度度量準(zhǔn)則不統(tǒng)一、一步分配策略的缺陷。Wang等[16]提出了一種通過使用原數(shù)據(jù)集潛在的熵的新方法來自動(dòng)提取截?cái)嗑嚯xdc的最佳值，通過實(shí)驗(yàn)證明，利用數(shù)據(jù)場獲得的截?cái)嗑嚯xdc比人工經(jīng)驗(yàn)獲得的聚類效果更好。關(guān)曉惠等[17]基于密度原理來確定聚類中心及其樣本點(diǎn)分配，彌補(bǔ)其需人為操作的缺陷。褚睿鴻等[18]在原有的DPC算法中引進(jìn)一個(gè)合理的參數(shù)K，并將改進(jìn)的DPC算法進(jìn)行集成，從而自動(dòng)完成聚類中心的選取，從而獲得最后的聚類結(jié)果。

實(shí)際上，每種聚類算法各有其適用范圍，并有其獨(dú)特的優(yōu)勢以及一定的不足之處，通過眾多學(xué)者的研究發(fā)現(xiàn)，將某些聚類算法結(jié)合起來使用可以有效地提高聚類效率或準(zhǔn)確率。

因此，為了克服K-means算法隨機(jī)選取初始聚類中心的不足之處，本文提出一種基于改進(jìn)的DPC算法的K-means聚類算法。首先，運(yùn)用改進(jìn)的DPC算法來選取初始聚類中心；然后，運(yùn)用K-means算法進(jìn)行迭代得到聚類結(jié)果，從而，彌補(bǔ)了K-means算法隨機(jī)選取初始聚類中心可能導(dǎo)致易陷入局部最優(yōu)解的缺陷；并且引入熵值法[19]計(jì)算距離優(yōu)化聚類。

1 熵值法計(jì)算賦權(quán)歐式距離

為了更好地分析各個(gè)數(shù)據(jù)對象之間的差異，本文利用信息熵來計(jì)算各數(shù)據(jù)對象的賦權(quán)歐式距離。

在信息論中，信息熵是對不確定性的一種度量。信息量越大，不確定性越小，熵越小，權(quán)重越大；信息量越小，不確定性越大，熵越大，離散程度越小，權(quán)重越小[20]。它可以計(jì)算指標(biāo)的離散程度。如果計(jì)算出的結(jié)果越大就說明該指標(biāo)對綜合評價(jià)的影響（即權(quán)重）越大[21]。故，可運(yùn)用信息熵計(jì)算各指標(biāo)的權(quán)重，為綜合評價(jià)提供理論依據(jù)。算法的實(shí)現(xiàn)步驟如下：

假設(shè)數(shù)據(jù)集X有m個(gè)對象和n維屬性：

其中，xij是屬性值，Mij是數(shù)據(jù)對象xi第j維屬性所占比重值。

步驟2：按照等式（2）和式（3）分別計(jì)算第j維屬性的熵值與權(quán)值：

熵值：

步驟1：首先標(biāo)準(zhǔn)化數(shù)據(jù)對象的屬性：

權(quán)值：

用賦權(quán)歐式距離度量相似度，可以精確得出各數(shù)據(jù)對象彼此間的差異程度，進(jìn)而提高聚類精確度。

步驟3：計(jì)算賦權(quán)歐氏距離的公式如下：

2 K-means算法

K-means算法是由MacQueenJB在1967年首次提出的，是硬聚類算法。它的評價(jià)指標(biāo)是距離，距離越小越相似，而最終目標(biāo)是獲得緊湊并且獨(dú)立的集群[22]。

K-means算法中的K值表示要聚類數(shù)據(jù)集的聚類數(shù)，而means代表類簇均值。也就是說，該算法使用一個(gè)均值代表一個(gè)類簇的聚類中心。并且，該算法用歐式距離來度量數(shù)據(jù)對象之間的相似性，采用誤差平方和來評聚類效果。

K-means算法的目標(biāo)函數(shù)為：

其中，E是數(shù)據(jù)集中的所有數(shù)據(jù)對象的平方誤差之和，p是數(shù)據(jù)集中的數(shù)據(jù)對象，mi是集群Ci的中心。

K-means算法描述如下：

輸入：包含n個(gè)對象的數(shù)據(jù)集和簇的數(shù)目K。

輸出：滿足目標(biāo)函數(shù)E最小值的K個(gè)簇。

步驟1：從n個(gè)數(shù)據(jù)對象中隨機(jī)選擇K個(gè)對象作為初始聚類中心；

步驟2：對于剩余對象，按照其與聚類中心之間的距離，依據(jù)就近原則分配到相應(yīng)的類簇；

步驟3：計(jì)算每個(gè)類簇的新均值，即新的類簇中心；

步驟4：回到步驟2，循環(huán)，直到不再發(fā)生變化。

由以上可知，K-means算法的特點(diǎn)是兩階段迭代循環(huán)、將數(shù)據(jù)對象的劃分不再發(fā)生變化作為循環(huán)終止條件。

3 改進(jìn)的DPC算法

3.1 DPC算法

DPC算法是以聚類中心點(diǎn)由一些局部密度較低的數(shù)據(jù)對象所包圍，并且與任何具有較高局部密度的數(shù)據(jù)對象之間的距離相對較大為假設(shè)基礎(chǔ)。此外，為了防止一些分散的離群點(diǎn)被強(qiáng)制分配到類簇當(dāng)中，從而造成聚類后類簇的邊界不清晰，進(jìn)而影響聚類的效果，本文為每個(gè)類簇確定了一個(gè)邊界區(qū)域，再把數(shù)據(jù)對象進(jìn)一步劃分為核心部分和光環(huán)部分（也就是噪聲）[8]。該算法首先定義了兩個(gè)量：局部密度ρi和距離δi。

對于數(shù)據(jù)對象i局部密度ρi：有cut-offkernel和Gaussiankernel兩種定義方法。

（1）cut-offkernel（對于較大規(guī)模數(shù)據(jù)集）：

其中，dij為數(shù)據(jù)對象i和j之間的歐式距離，dc為截?cái)嗑嚯x，由人工確定，通常將所有數(shù)據(jù)對象兩兩之間的距離按升序排列后前2%位置的數(shù)值距離作為截?cái)嗑嚯x。

數(shù)據(jù)對象i的距離：

其中：

（2）Gaussiankernel（對于較小規(guī)模數(shù)據(jù)集）：）

對于每個(gè)數(shù)據(jù)對象i，首先，需要計(jì)算局部密度ρi和距離δi，然后，根據(jù)計(jì)算得到的這兩個(gè)值畫出一個(gè)二維平面決策圖。

構(gòu)造決策圖：

將γi進(jìn)行降序排序，并以數(shù)據(jù)對象的下標(biāo)為橫坐標(biāo)，γ值為縱坐標(biāo)構(gòu)造決策圖，如圖1。可以發(fā)現(xiàn)，γ的值越大則數(shù)據(jù)對象是聚類中心的可能性就越大。而且，從圖1中可以發(fā)現(xiàn)，不是聚類中心的數(shù)據(jù)對象的γ值比較平滑，而在聚類中心的γ值轉(zhuǎn)換到非聚類中心的γ值時(shí)有一個(gè)非常明顯的跳躍，并且，無論是肉眼還是數(shù)值的檢測這個(gè)跳躍都能很容易判斷出來。從而，這個(gè)跳躍就是聚類中心與非聚類中心的分界線。

圖1 γ決策圖

當(dāng)聚類中心選定后，對于剩余的數(shù)據(jù)對象則采用一種“跟隨”策略，歸屬到密度比其密度大的最近鄰所屬的類簇中，得到最終的聚類結(jié)果。

3.2 改進(jìn)的DPC算法

由于在DPC算法中，局部密度ρi和距離δi的計(jì)算依賴于截?cái)嗑嚯xdc，而文中的截?cái)嗑嚯xdc是通過人工設(shè)置的，它是人工經(jīng)驗(yàn)方法，即使dc的選擇具有魯棒性，但是依舊缺乏理論依據(jù)。因此，本文介紹了一種選擇最優(yōu)dc值的方法[23]。

步驟如下[23]：

對于數(shù)據(jù)對象i，令向量：

其中，dij(i，j=1，2，…，n;i≠j)為數(shù)據(jù)對象i到數(shù)據(jù)對象j之間的賦權(quán)歐式距離。將向量li按從小到大的順序進(jìn)行排序，從而得到向量ci，即則數(shù)據(jù)對象i的截?cái)嗑嚯xdci就可以定義為：

其中，max(ai(j+1)-aij)是向量ci中相鄰的兩個(gè)元素之差的最大值。

由圖2可以看出，同一類簇的數(shù)據(jù)對象之間的距離差距比較小，而不同類簇的數(shù)據(jù)對象之間的距離差距比較大，所以，在向量ci中，有兩個(gè)相鄰元素的差距會(huì)較大[23]，即：

其中，aij=a，ai(j+1)=b。由圖2可認(rèn)為數(shù)據(jù)對象是從一個(gè)簇跳躍到了另一個(gè)簇中，如果找到最大的差值則可找到理想的截?cái)嗑嚯xdci，即：

圖2 截?cái)嗑嚯x決策圖

本算法對于存在離群點(diǎn)的情形也適用，如圖3所示。

圖3 有離群點(diǎn)的情況

由圖3可知，在升序排序后獲得的向量ci中，相鄰兩個(gè)元素之差的最大值為：

即aij=a，ai(j+1)=c。由式（9）可知，數(shù)據(jù)對象i的截?cái)嗑嚯x為：

各數(shù)據(jù)對象i均分別有dci與其照應(yīng)，因此，它們組成了一個(gè)集合Dc：

為了減少集群邊界上點(diǎn)和離群點(diǎn)的影響及避免dc過大，dc應(yīng)取集合Dc的最小值，即：

這種確定截?cái)嗑嚯xdc的方法與密度指標(biāo)和距離指標(biāo)相同，是基于數(shù)據(jù)對象之間的距離得到的，所以，不會(huì)增加額外的計(jì)算負(fù)擔(dān)。將式（10）帶入求各數(shù)據(jù)對象i的局部密度ρi的等式（5）或（6）和距離δi的等式（7），然后，求得ρi和δi，從而完成數(shù)據(jù)對象聚類過程。這種改進(jìn)的方法為dc的選擇提供了依據(jù)，而且算法簡單、易實(shí)現(xiàn)。

4 改進(jìn)的K-means聚類算法

針對K-means算法隨機(jī)選擇初始聚類中心進(jìn)行迭代可能導(dǎo)致不穩(wěn)定的聚類結(jié)果，本文提出一種改進(jìn)的K-means算法，本文首先通過改進(jìn)的DPC算法來選取聚類中心作為K-means算法的初始聚類中心；然后，使用K-means算法進(jìn)行迭代，并且引入信息熵計(jì)算賦權(quán)歐氏距離[19]，以便更準(zhǔn)確地規(guī)范各對象之間的差異程度，從而更好地聚類。

本文算法描述：

輸入：含有n個(gè)數(shù)據(jù)對象的數(shù)據(jù)集合。

輸出：滿足目標(biāo)函數(shù)最小值的K個(gè)簇。

步驟1：使用熵值法計(jì)算各數(shù)據(jù)對象之間的賦權(quán)歐氏距離dij，并令dij=dji，i＜j，使其成為一個(gè)完整的矩陣；

步驟2：確定截?cái)嗑嚯xdc；

步驟3：根據(jù)確定的截?cái)嗑嚯xdc，并利用DPC算法中的方法計(jì)算每個(gè)數(shù)據(jù)對象i的ρi和δi；

步驟4：根據(jù)γi=ρi×δi，i=1，2，…，n，選擇聚類中心，γ越大越可能是聚類中心；

步驟5：確定聚類中心cj，j=1，2，…，K與K的值；

步驟6：計(jì)算剩余每個(gè)數(shù)據(jù)對象與各類簇的中心的距離，并將每個(gè)數(shù)據(jù)對象賦給距其最近的類簇，進(jìn)行劃分；

步驟7：重新計(jì)算每個(gè)新簇的均值作為新的類簇中心；

步驟8：計(jì)算目標(biāo)函數(shù)值；

步驟9：直到目標(biāo)函數(shù)不再發(fā)生變化，算法終止；否則，轉(zhuǎn)步驟7。

5 實(shí)驗(yàn)分析

5.1 實(shí)驗(yàn)描述

為了驗(yàn)證本文算法的有效性，選取UCI數(shù)據(jù)庫的Iris和Wine作為實(shí)驗(yàn)數(shù)據(jù)集。實(shí)驗(yàn)數(shù)據(jù)集的構(gòu)成描述如表1：

表1 實(shí)驗(yàn)數(shù)據(jù)集的構(gòu)成描述

并與傳統(tǒng)的K-means算法以及文獻(xiàn)[16]中提出的算法K-CBFSAFODP進(jìn)行了對比。

5.2 實(shí)驗(yàn)結(jié)果分析

對于選擇的UCI中的數(shù)據(jù)集運(yùn)用K-means算法、K-CBFSAFODP算法以及本文提出的算法進(jìn)行聚類以后發(fā)現(xiàn)，本文提出的算法在聚類時(shí)間、聚類誤差平方和和聚類的準(zhǔn)確率方面有所提升。

將本文算法得到的實(shí)驗(yàn)結(jié)果與Iris數(shù)據(jù)集的實(shí)際中心進(jìn)行比較，如表2所示：

表2 本文算法實(shí)驗(yàn)結(jié)果與Iris數(shù)據(jù)實(shí)際中心比較

從表2可以看出，本文算法得到的聚類中心與Iris數(shù)據(jù)的實(shí)際中心非常接近，從而能夠說明該算法對Iris數(shù)據(jù)比較有效。同理，該算法對Wine數(shù)據(jù)也比較有效。

本文算法的誤差平方和優(yōu)于K-means、K-CBFSAF ODP算法，迭代次數(shù)優(yōu)于傳統(tǒng)的K-means算法，如表3所示。

表3 誤差平方和及迭代次數(shù)的比較

由表3可以看出，在選擇的數(shù)據(jù)上本文算法的誤差平方和、迭代次數(shù)明顯優(yōu)于傳統(tǒng)的K-means算法。而與K-CBFSAFODP算法相比，在Iris數(shù)據(jù)上，雖然兩算法迭代次數(shù)相等，但是誤差平方和稍微優(yōu)于K-CBFSAFODP算法的誤差平方和。在Wine數(shù)據(jù)上，本文算法的迭代次數(shù)雖然比K-CBFSAFODP算法的大，但是其誤差平方和卻明顯優(yōu)于K-CBFSAFODP算法。

聚類準(zhǔn)確率也是衡量聚類結(jié)果的重要性指標(biāo)。而三種聚類算法在UCI數(shù)據(jù)集上的聚類準(zhǔn)確率的比較，如表4所示：

表4 聚類準(zhǔn)確率的比較 （單位%）

從表4中可知，在聚類準(zhǔn)確率方面，本文算法明顯優(yōu)于傳統(tǒng)的K-means算法，同時(shí)，在Iris數(shù)據(jù)上本文算法優(yōu)于K-CBFSAFODP算法，但是，在Wine數(shù)據(jù)上卻明顯優(yōu)于K-CBFSAFODP算法。從而，能夠充分說明本文提出的算法具有較好的聚類效果。

6 結(jié)論

傳統(tǒng)的K-means算法隨機(jī)地選擇初始聚類中心進(jìn)行迭代，可能導(dǎo)致不穩(wěn)定的聚類結(jié)果，并且算法中的K值需要事先人為確定，因而導(dǎo)致限制了該算法的應(yīng)用。本文提出的基于改進(jìn)的密度峰值優(yōu)化初始聚類中心的K-means算法能夠很好地解決前文敘述的兩點(diǎn)不足之處。利用改進(jìn)的密度峰值算法選取初始聚類中心，并根據(jù)決策圖決定聚類個(gè)數(shù)K，這彌補(bǔ)了K-means算法的上述不足之處，接著利用K-means算法進(jìn)行循環(huán)迭代，進(jìn)而得到聚類結(jié)果。實(shí)驗(yàn)表明該算法能夠得到較好的聚類結(jié)果。