融合最近鄰矩陣與局部密度的自適應(yīng)K-means聚類算法

艾力米努爾·庫(kù)爾班，謝娟英，姚若俠

陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，西安710119

聚類（cluster）是數(shù)據(jù)挖掘進(jìn)行數(shù)據(jù)分析時(shí)常用的方法之一，與對(duì)已知樣本屬性的數(shù)據(jù)構(gòu)造劃分的監(jiān)督學(xué)習(xí)（supervised learning）不同的是，聚類分析屬于無(wú)監(jiān)督學(xué)習(xí)（unsupervised learning），即在數(shù)據(jù)數(shù)量、數(shù)據(jù)屬性和數(shù)據(jù)類別個(gè)數(shù)等信息未知的情況下進(jìn)行自主學(xué)習(xí)，最后構(gòu)造劃分的過程[1]。傳統(tǒng)Kmeans 算法[2]適用范圍較廣，在處理大數(shù)據(jù)時(shí)具有較高的相對(duì)伸縮性，其典型的特點(diǎn)是，當(dāng)數(shù)據(jù)樣本集接近正態(tài)分布，且不同聚類的界限劃分較為明顯時(shí)，傳統(tǒng)K-means 聚類效果能夠達(dá)到最優(yōu)，因此被廣泛地應(yīng)用于各個(gè)領(lǐng)域中[3-5]。但是使用傳統(tǒng)K-means 聚類算法也會(huì)受到一定的限制。由于傳統(tǒng)K-means 算法隨機(jī)選取初始聚類中心點(diǎn)，易收斂于局部最優(yōu)解，在聚類過程中也容易受到離群孤立點(diǎn)的影響，同時(shí)傳統(tǒng)K-means 算法需要預(yù)先人工輸入聚類數(shù)目K值，導(dǎo)致聚類效果不穩(wěn)定且算法自適應(yīng)能力較弱。近年來，大量學(xué)者主要從以下三方面針對(duì)傳統(tǒng)K-means 聚類算法的缺陷和不足提出了一系列改進(jìn)：

其一，針對(duì)離群孤立點(diǎn)在一定程度上使聚類結(jié)果出現(xiàn)偏差的問題，文獻(xiàn)[6-7]將基于距離的離群點(diǎn)檢測(cè)（local outlier factor，LOF）引入傳統(tǒng)K-means 聚類算法，根據(jù)LOF 算法中計(jì)算異常因子的方法計(jì)算數(shù)據(jù)對(duì)象的局部異常程度。在此基礎(chǔ)上，文獻(xiàn)[8]通過計(jì)算數(shù)據(jù)對(duì)象的K 近鄰，預(yù)先對(duì)數(shù)據(jù)集構(gòu)建平分樹,然后通過剪枝檢測(cè)數(shù)據(jù)集中的全局離群點(diǎn)。這雖然在一定程度上提高了聚類結(jié)果的準(zhǔn)確性和時(shí)效性，但在聚類過程中仍然需要人工輸入聚類數(shù)目K值，對(duì)數(shù)據(jù)集分布的研究不夠深入和透徹時(shí)，聚類效果依舊不穩(wěn)定。

其二，針對(duì)傳統(tǒng)K-means 算法對(duì)初始聚類中心敏感的缺點(diǎn)，文獻(xiàn)[9]用余弦相似度替換文本聚類的距離度量標(biāo)準(zhǔn)，文獻(xiàn)[10]選取數(shù)據(jù)樣本集中方差最小且處于不同區(qū)域的數(shù)據(jù)對(duì)象作為初始聚類中心，文獻(xiàn)[11]采用Pearson 相關(guān)系數(shù)統(tǒng)計(jì)數(shù)據(jù)對(duì)象間的相關(guān)性。雖然這幾種方法都提出選取初始聚類中心的有效方案，但是在聚類過程中不僅需要人工預(yù)先指定聚類中心數(shù)目K值，還需進(jìn)行大量計(jì)算，增加了算法的時(shí)間開銷。

其三，針對(duì)傳統(tǒng)K-means 算法需要人工輸入聚類數(shù)目K值的問題，文獻(xiàn)[12]首次將密度峰值原則應(yīng)用到聚類算法中，提出快速搜索密度峰值聚類算法。該聚類算法以數(shù)據(jù)樣本集中的密度峰值點(diǎn)作為初始聚類中心，從而確定聚類數(shù)目K值。盡管如此，密度峰值聚類算法還是需要人為主觀選擇參數(shù)。文獻(xiàn)[13]通過構(gòu)造樣本距離相對(duì)于樣本密度的決策圖，自適應(yīng)確定聚類個(gè)數(shù)K值。文獻(xiàn)[14]預(yù)先對(duì)數(shù)據(jù)集用密度權(quán)重Canopy 算法進(jìn)行聚類,目的在于為傳統(tǒng)Kmeans 算法提供初始聚類中心和最優(yōu)聚類數(shù)目K值，但Canopy 算法初始閾值人為指定的問題仍然存在。文獻(xiàn)[15]定義了數(shù)據(jù)對(duì)象K 近鄰內(nèi)的局部密度，提出了模糊加權(quán)的K 近鄰密度峰值聚類算法（fuzzy weighted K-nearest neighbors density peak clustering，F(xiàn)KNNDPC），該算法先后使用兩種分配策略對(duì)聚類中心點(diǎn)、非中心點(diǎn)和離群點(diǎn)構(gòu)造劃分。這些算法在聚類過程中有效避免了傳統(tǒng)K-means 算法易陷入局部最優(yōu)解的問題，倘若在聚類過程中沒有把握好閾值，則會(huì)直接造成獲得的初始聚類中心點(diǎn)與實(shí)際中心發(fā)生較大偏差，極大程度降低聚類精確度。

這些改進(jìn)K-means 的聚類算法在提高了傳統(tǒng)Kmeans 算法聚類效果的同時(shí)也優(yōu)化了聚類算法的性能，但依然存在對(duì)噪聲數(shù)據(jù)敏感、需要主觀確定一些參數(shù)和閾值的不足。針對(duì)以上現(xiàn)有問題，通過分析最鄰近吸收原則與密度峰值原則的優(yōu)缺點(diǎn)，改進(jìn)算法采用最近鄰矩陣與局部密度優(yōu)化的雙重策略，不需要人為干預(yù)與任何參數(shù)的選擇，進(jìn)而實(shí)現(xiàn)初始聚類中心及聚類數(shù)目的動(dòng)態(tài)確定。在聚類過程中，不僅考慮到離群孤立點(diǎn)對(duì)聚類效果的影響，同時(shí)也增強(qiáng)了聚類效果的穩(wěn)定性與客觀性。

1 基本原則介紹

1.1 最鄰近吸收原則基本原理

最鄰近吸收原則（nearest-neighbor absorbed first principle）[16]：在多維空間中，任意一點(diǎn)與它最鄰近的樣本點(diǎn)屬于同一類簇的可能性較大。在聚類算法中的典型應(yīng)用為K 鄰近吸收原則與ε鄰近吸收原則。其中，K 鄰近吸收原則的基本原理是目標(biāo)對(duì)象吸收與其屬性最相似或者距離最鄰近的K個(gè)鄰居，ε鄰近吸收原則的基本原理是目標(biāo)對(duì)象吸收以自身為中心，在ε為半徑的領(lǐng)域內(nèi)所包含的數(shù)據(jù)對(duì)象。當(dāng)數(shù)據(jù)樣本集呈正態(tài)分布時(shí)，利用最鄰近吸收原則構(gòu)造數(shù)據(jù)劃分的結(jié)果最為理想。

若將K 鄰近吸收原則直接應(yīng)用到聚類算法，參數(shù)K和ε值的大小直接影響聚類類簇的數(shù)目，且該原則只會(huì)考慮到樣本之間的相對(duì)位置，而無(wú)法考慮到樣本集整體的分布情況，會(huì)導(dǎo)致聚類算法不具有較高的魯棒性。

無(wú)論是K 鄰近吸收原則還是ε鄰近吸收原則都具有以下缺點(diǎn)：

（1）需要根據(jù)經(jīng)驗(yàn)預(yù)先確定K值或ε值，參數(shù)的取值直接影響聚類結(jié)果的好壞。

（2）不能有效測(cè)量數(shù)據(jù)對(duì)象之間的相關(guān)性或差異性，無(wú)法識(shí)別流形數(shù)據(jù)集。

1.2 密度峰值原則基本原理

密度峰值原則（density peak principle）[12]：在多維空間中，聚類中心點(diǎn)的局部密度大于在其余數(shù)據(jù)樣本點(diǎn)的局部密度，且在聚類算法中兩個(gè)聚類中心點(diǎn)的相互距離相對(duì)較遠(yuǎn)。此時(shí)，聚類中心點(diǎn)在數(shù)據(jù)樣本集中具有較優(yōu)的分布性。密度峰值原則利用截?cái)嗑嚯xdc計(jì)算當(dāng)前數(shù)據(jù)樣本集的局部密度與數(shù)據(jù)對(duì)象之間相對(duì)距離，當(dāng)數(shù)據(jù)樣本集密度分布較為平均時(shí)，聚類的效果最為理想。

與最鄰近吸收原則相反，密度峰值原則考慮的是全局分布特點(diǎn)，而忽略了數(shù)據(jù)對(duì)象局部領(lǐng)域內(nèi)的分布情況。該原則能夠識(shí)別各種形狀的數(shù)據(jù)樣本集，但是針對(duì)密度變化較大或類簇間差異較大的數(shù)據(jù)集，往往會(huì)降低容錯(cuò)性。若將密度峰值原則直接應(yīng)用到聚類算法中會(huì)導(dǎo)致算法具有較差的計(jì)算精度。同時(shí)，密度峰值原則具有以下缺點(diǎn)：

（1）在實(shí)際聚類應(yīng)用中離群點(diǎn)會(huì)直接導(dǎo)致數(shù)據(jù)樣本集的平均密度變大，從而影響聚類效果。

（2）過度依賴參數(shù)截?cái)嗑嚯xdc的設(shè)置，參數(shù)的取值直接影響聚類結(jié)果的好壞，如果缺乏經(jīng)驗(yàn)，也會(huì)降低聚類效率。

2 基本概念

針對(duì)上述最鄰近吸收原則以及密度峰值原則存在的明顯缺點(diǎn)，改進(jìn)算法融合距離矩陣與局部密度的思想，動(dòng)態(tài)確定聚類中心點(diǎn)數(shù)目以及位置，完成剩余數(shù)據(jù)對(duì)象的初分配。為了方便后續(xù)算法的說明與描述，給出以下定義。

對(duì)于給定的含有n個(gè)樣本的數(shù)據(jù)集Dn={X1,X2,…,Xn}，其中樣本數(shù)據(jù)集Dn含有p個(gè)屬性{A1,A2,…,Ap}，即n為數(shù)據(jù)樣本集所含樣本總數(shù)，p為樣本數(shù)據(jù)集Dn的維度。

對(duì)于數(shù)據(jù)集Dn中的任意兩個(gè)樣本Xi={Xi1,Xi2,…,Xip}和Xj={Xj1,Xj2,…,Xjp}（1≤i≤n，1≤j≤n，i≠j），其中Xir和Xjr（1≤r≤n）分別對(duì)應(yīng)樣本Di和樣本Dj的第r個(gè)屬性的具體數(shù)值。記K個(gè)聚類中心分別為C={C1,C2,…,Ck}。

定義1（歐氏距離[14]）任意兩個(gè)數(shù)據(jù)對(duì)象Xi和Xj之間的歐氏距離：

定義2（平均距離[17]）數(shù)據(jù)樣本集Dn的平均樣本距離：

定義3（距離差異）任意兩個(gè)數(shù)據(jù)對(duì)象Xi和Xj之間的距離差異值：

z(Xi,Xj)表示數(shù)據(jù)樣本集中第i個(gè)數(shù)據(jù)對(duì)象Xi與第j個(gè)數(shù)據(jù)對(duì)象Xj之間的距離差異值。z(Xi,Xj)的數(shù)值越小，則代表數(shù)據(jù)對(duì)象Xj成為初始聚類中心的可能性越大，該值的大小直接反映了第j個(gè)數(shù)據(jù)對(duì)象Xj是否適合作為第i個(gè)數(shù)據(jù)對(duì)象Xi的聚類中心。

定義4（近鄰矩陣）數(shù)據(jù)對(duì)象之間的兩兩距離差異值構(gòu)成近鄰矩陣，它是如下形式的對(duì)稱矩陣：

3 改進(jìn)算法整體介紹

輸入：目標(biāo)數(shù)據(jù)集Dn。

輸出：二維數(shù)據(jù)集可視化動(dòng)態(tài)聚類視圖。多維數(shù)據(jù)集K個(gè)聚類集以及相應(yīng)的評(píng)價(jià)指標(biāo)。

本章從數(shù)據(jù)預(yù)處理、局部密度峰點(diǎn)、數(shù)據(jù)對(duì)象分配策略以及聚類中心點(diǎn)的更新四方面對(duì)改進(jìn)算法進(jìn)行闡述。

3.1 數(shù)據(jù)樣本集預(yù)處理

3.1.1 數(shù)據(jù)歸一化處理

數(shù)據(jù)樣本集由多個(gè)維度或多個(gè)屬性構(gòu)成，不同的屬性變量具有不同的表示單位和不同的密度分布，十分不利于數(shù)據(jù)解釋。數(shù)據(jù)歸一化不僅方便后續(xù)的數(shù)據(jù)處理，也能保證算法迭代時(shí)的收斂速度，在涉及到距離計(jì)算的聚類算法中有顯著效果。

改進(jìn)算法采用Min-Max 標(biāo)準(zhǔn)化方法對(duì)多維數(shù)據(jù)進(jìn)行歸一化處理，即將數(shù)據(jù)樣本集中屬性Ai的原始數(shù)值x通過Min-Max 標(biāo)準(zhǔn)化公式映射到區(qū)間[0,1]中的值x′，設(shè)minAi和maxAi分別為屬性Ai的最小值與最大值，則Min-Max 標(biāo)準(zhǔn)化公式為[17]：

3.1.2 離群孤立點(diǎn)檢測(cè)

對(duì)于離群孤立點(diǎn)的判定，改進(jìn)算法考慮全局離群孤立點(diǎn)，是因?yàn)槿绻麅H僅考慮基于密度的局部離群點(diǎn)檢測(cè)，時(shí)間復(fù)雜度高且不適用于大規(guī)模數(shù)據(jù)集和高位數(shù)據(jù)集。在樣本空間中，全局離群孤立點(diǎn)相比其他數(shù)據(jù)對(duì)象，具有不同的行為或不一致的特征，即它們是數(shù)據(jù)集中不與其他數(shù)據(jù)對(duì)象強(qiáng)相關(guān)的對(duì)象。離群點(diǎn)檢測(cè)在動(dòng)態(tài)算法中的應(yīng)用為：在數(shù)據(jù)歸一化之后，若數(shù)據(jù)對(duì)象鄰域內(nèi)的局部密度值小于樣本數(shù)據(jù)集的平均密度值，則標(biāo)識(shí)該數(shù)據(jù)樣本點(diǎn)為數(shù)據(jù)樣本集的離群孤立點(diǎn)。

在數(shù)據(jù)預(yù)處理中對(duì)離群孤立點(diǎn)進(jìn)行篩選的必要性在于，避免離群孤立點(diǎn)對(duì)聚類中心點(diǎn)和聚類結(jié)果的負(fù)面影響，從而提高聚類算法效率。

3.2 確定初始聚類中心

文獻(xiàn)[18]定理1 已證實(shí)，基于密度峰值原則的聚類算法所得到的聚類中心，其局部密度往往大于其鄰居的局部密度。在排除離群孤立點(diǎn)之后，稀疏區(qū)域的低密度數(shù)據(jù)對(duì)象成為初始聚類中心的可能性較小。因此，聚類中心往往出現(xiàn)在密度較大的區(qū)域。

定義5（局部密度）數(shù)據(jù)對(duì)象Xj的局部密度：

其中，num是在考察目標(biāo)點(diǎn)最近鄰的近鄰的過程中，滿足近鄰條件的樣本點(diǎn)數(shù)量，即目標(biāo)點(diǎn)最近鄰的最近鄰也是目標(biāo)點(diǎn)的近鄰，C(j)是對(duì)于目標(biāo)點(diǎn)Xj滿足近鄰條件的集合。數(shù)據(jù)對(duì)象的局部密度不僅直接反映了目標(biāo)點(diǎn)近鄰的數(shù)量，也反映了目標(biāo)點(diǎn)近鄰的分布情況。

定義6（平均密度）數(shù)據(jù)樣本集Dn的整體密度均值：

分析式（7）可知，數(shù)據(jù)樣本集Dn的整體密度均值與數(shù)據(jù)的分布密不可分，體現(xiàn)了數(shù)據(jù)樣本集Dn在空間中的緊密程度。

從直觀上解釋，為了確保初始聚類中心具有良好的連通性，改進(jìn)算法利用目標(biāo)點(diǎn)的近鄰數(shù)目計(jì)算數(shù)據(jù)對(duì)象的局部密度，對(duì)數(shù)據(jù)對(duì)象采取距離差異值和局部密度相結(jié)合的方式選取初始聚類中心，根據(jù)式（6）標(biāo)記局部密度峰點(diǎn)作為一個(gè)初始聚類中心，從而有效解決了密度峰值聚類算法在計(jì)算數(shù)據(jù)對(duì)象密度時(shí)，對(duì)截?cái)嗑嚯x等參數(shù)敏感的問題。

3.3 分配數(shù)據(jù)對(duì)象

3.3.1 左、右最近鄰

定義7（左、右最近鄰）對(duì)于任意一個(gè)數(shù)據(jù)對(duì)象Xj，在滿足與其距離小于平均樣本距離的限制條件下，數(shù)據(jù)對(duì)象表示與其最鄰近的右近鄰，數(shù)據(jù)對(duì)象表示與其最鄰近的左近鄰：

數(shù)據(jù)對(duì)象的最近鄰個(gè)數(shù)包含以下三種情況：

（1）若考察的數(shù)據(jù)對(duì)象既有左最近鄰，也有右最近鄰，則該數(shù)據(jù)對(duì)象最近鄰個(gè)數(shù)為2。

（2）若考察的數(shù)據(jù)對(duì)象只有左最近鄰或者只有右最近鄰，則該數(shù)據(jù)對(duì)象最近鄰個(gè)數(shù)為1。

（3）若考察的數(shù)據(jù)對(duì)象既沒有左最近鄰，也沒有右最近鄰，則該數(shù)據(jù)對(duì)象最近鄰個(gè)數(shù)為0。

數(shù)據(jù)對(duì)象與其最鄰近歸屬為同一類簇的可能性最大，在聚類過程中，若一個(gè)數(shù)據(jù)對(duì)象含有兩個(gè)最近鄰或只含有其中一個(gè)最近鄰，可以繼續(xù)考察其最近鄰的近鄰情況，直到數(shù)據(jù)對(duì)象無(wú)近鄰或數(shù)據(jù)對(duì)象的近鄰全部被標(biāo)記。

3.3.2 最鄰近矩陣與局部密度結(jié)合的雙重策略

基于密度峰值原則的聚類算法在得到的聚類中心后，直接依據(jù)最短歐幾里德距離原則進(jìn)行數(shù)據(jù)分配，而改進(jìn)算法引入最鄰近矩陣與局部密度結(jié)合的雙重策略對(duì)剩余數(shù)據(jù)對(duì)象進(jìn)行類簇分配，具體步驟如下。

步驟1根據(jù)式（1）～（3）和式（6），計(jì)算數(shù)據(jù)樣本集所有數(shù)據(jù)對(duì)象的局部密度，標(biāo)記局部密度峰點(diǎn)作為第一個(gè)初始聚類中心。

步驟2根據(jù)式（3）和式（8），選擇與局部密度峰點(diǎn)距離小于平均樣本距離的數(shù)據(jù)對(duì)象，確定局部密度峰點(diǎn)左、右最近鄰。若局部密度峰點(diǎn)包含左、右最近鄰或者其一，轉(zhuǎn)步驟3。若局部密度峰點(diǎn)不含有左、右最近鄰，轉(zhuǎn)步驟5。

步驟3根據(jù)式（4），參考n個(gè)數(shù)據(jù)對(duì)象之間的最近鄰矩陣Z，分別掃描左、右最近鄰所在的行，再根據(jù)式（5），確定左、右最近鄰的近鄰。

步驟4考察左右最近鄰的近鄰與密度峰值的距離是否小于平均樣本距離，若滿足條件，將左右最近鄰的近鄰劃分到局部密度峰點(diǎn)的近鄰集合中，轉(zhuǎn)步驟3 繼續(xù)考察其最近鄰的近鄰情況，若不滿足轉(zhuǎn)下一步。

步驟5將該聚類中心與其近鄰從數(shù)據(jù)集中刪除，更新數(shù)據(jù)集。

步驟6檢查數(shù)據(jù)集是否為空，若數(shù)據(jù)集不為空，繼續(xù)標(biāo)記局部密度峰點(diǎn)的數(shù)據(jù)對(duì)象將其作為下一個(gè)初始聚類中心，繼而轉(zhuǎn)步驟2 并重復(fù)上述過程；若數(shù)據(jù)集為空，代表經(jīng)過步驟1 到步驟4 已經(jīng)確定密度峰值點(diǎn)的所有近鄰，完成所有數(shù)據(jù)對(duì)象之間的歸屬關(guān)系劃分并確定K個(gè)聚類中心。

圖1（a）是關(guān)于原始數(shù)據(jù)的散點(diǎn)圖，圖1（b）是對(duì)含有19 個(gè)樣本的數(shù)據(jù)集基于雙重策略構(gòu)造數(shù)據(jù)劃分后的表現(xiàn)。其中，數(shù)據(jù)樣本集中數(shù)據(jù)對(duì)象1 至數(shù)據(jù)對(duì)象9 所在的空間分布密度較大，數(shù)據(jù)對(duì)象10 至數(shù)據(jù)對(duì)象19 所在的空間分布密度較小，適合考驗(yàn)基于不同種度量的聚類結(jié)果。

考慮圖1 數(shù)據(jù)對(duì)象9 和數(shù)據(jù)對(duì)象16 的位置，如果僅僅考慮全局分布特點(diǎn)，這兩個(gè)數(shù)據(jù)對(duì)象周圍的密度遠(yuǎn)遠(yuǎn)小于其余數(shù)據(jù)對(duì)象的密度，可能在劃分過程被單獨(dú)劃分為一類；如果僅僅考慮局部分布特點(diǎn)，數(shù)據(jù)對(duì)象16 與數(shù)據(jù)對(duì)象13 的距離較近，數(shù)據(jù)對(duì)象9 與數(shù)據(jù)對(duì)象8 的距離較近，在劃分過程中若誤將其歸為一類，會(huì)導(dǎo)致簇間差異性增大，聚類結(jié)果不理想。然而，在綜合考慮距離差異值和局部密度的情況下，數(shù)據(jù)對(duì)象16 會(huì)對(duì)局部密度峰點(diǎn)即數(shù)據(jù)對(duì)象10 影響較大，而數(shù)據(jù)對(duì)象9 對(duì)局部密度峰點(diǎn)即數(shù)據(jù)對(duì)象1 影響較小，如圖1（b）所示。

圖1 基于雙重策略構(gòu)造數(shù)據(jù)劃分Fig.1 Partition of data under double strategies

3.4 構(gòu)造最優(yōu)劃分

構(gòu)造最優(yōu)劃分即通過動(dòng)態(tài)迭代確定最優(yōu)初始聚類中心，直到聚類中心的位置不再變化，這也標(biāo)志著改進(jìn)算法對(duì)于這組數(shù)據(jù)樣本點(diǎn)具有收斂性。

定義8（距離均值[14]）數(shù)據(jù)對(duì)象Xi到數(shù)據(jù)樣本集中所有樣本點(diǎn)之間的距離均值：

定義9（誤差平方和[7]）數(shù)據(jù)樣本集Dn聚類誤差平方和：

其中，數(shù)據(jù)對(duì)象Xl是屬于類簇Ci的樣本，SSE表示該數(shù)據(jù)樣本點(diǎn)Xl到聚類中心點(diǎn)Ci的距離平方和。SSE值越小說明聚類效果越優(yōu)。

改進(jìn)算法更新初始聚類中心的具體步驟如下：

步驟1根據(jù)式（9），分別計(jì)算每一個(gè)類簇中所有數(shù)據(jù)樣本集的距離均值，并將其更新為該類簇的新聚類中心。

步驟2根據(jù)式（10），重新計(jì)算當(dāng)前聚類類簇的誤差平方和SSE′，若SSE′＝SSE，表明聚類中心的位置趨于穩(wěn)定，聚類過程到此結(jié)束。否則，令SSE＝SSE′，轉(zhuǎn)向步驟1。

自適應(yīng)聚類算法流程圖見圖2。

圖2 自適應(yīng)聚類算法流程圖Fig.2 Flow chart of adaptive clustering algorithm

4 仿真實(shí)驗(yàn)

為了更加準(zhǔn)確地測(cè)試自適應(yīng)聚類算法聚類效果的穩(wěn)定性和有效性，分別在UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)常用的六個(gè)數(shù)據(jù)集以及人工模擬數(shù)據(jù)集中進(jìn)行測(cè)試，并把改進(jìn)算法（表示為算法4）與基于距離的傳統(tǒng)Kmeans 算法（表示為算法1）[2]、基于離群點(diǎn)改進(jìn)的Kmeans 算法（表示為算法2）[6]、基于密度改進(jìn)的DCCK-means算法（表示為算法3）[19]進(jìn)行比較。

所有算法的實(shí)驗(yàn)環(huán)境為：硬件環(huán)境為Intel?CoreTMi5-6600CPU，3.30 GHz，8 GB RAM；軟件環(huán)境為Windows 10 64 位，MATLAB R2016b。

4.1 人工數(shù)據(jù)集的仿真實(shí)驗(yàn)

4.1.1 實(shí)驗(yàn)數(shù)據(jù)

為了更直觀地展示改進(jìn)的動(dòng)態(tài)K-means 算法與其余三種算法的聚類效果，將聚類結(jié)果進(jìn)行可視化處理。本次實(shí)驗(yàn)隨機(jī)生成4 個(gè)數(shù)值型樣本集，它們分布在二維空間中，每個(gè)數(shù)據(jù)樣本值都含有兩個(gè)數(shù)據(jù)屬性，經(jīng)過歸一化處理后的數(shù)據(jù)樣本集特性如表1所示。

表1 人工模擬數(shù)據(jù)集特性Table 1 Features of artificial dataset

表1 中，數(shù)據(jù)集Dataset 1 由2 個(gè)團(tuán)狀類簇和1 個(gè)流形類簇構(gòu)成，數(shù)據(jù)集Dataset 2 由5 個(gè)橢圓狀的類簇構(gòu)成，數(shù)據(jù)集Dataset 3 由15 個(gè)團(tuán)狀類簇構(gòu)成，數(shù)據(jù)集Dataset 4 由7 個(gè)相互連接且形狀各異的團(tuán)簇構(gòu)成，這4 個(gè)數(shù)據(jù)集都含有約5%的離群孤立點(diǎn)，經(jīng)過歸一化處理后的數(shù)據(jù)樣本分布情況如圖3 所示，利用不同的顏色表示已知條件下的不同類簇。

圖3 人工數(shù)據(jù)集分布情況Fig.3 Distribution of artificial datasets

4.1.2 實(shí)驗(yàn)參數(shù)

對(duì)于傳統(tǒng)K-means 聚類算法，初始聚類中心的選取具有一定的隨機(jī)性，這導(dǎo)致準(zhǔn)確率與迭代次數(shù)的不穩(wěn)定。因此，對(duì)算法1 與算法2 分別運(yùn)行50 次，取實(shí)驗(yàn)結(jié)果的平均值進(jìn)行對(duì)比。對(duì)于算法3 要設(shè)置密度半徑與領(lǐng)域最小個(gè)數(shù)。對(duì)于數(shù)據(jù)集Dataset 1 密度半徑設(shè)置為0.14，領(lǐng)域最小個(gè)數(shù)設(shè)置為10；對(duì)于數(shù)據(jù)集Dataset 2 密度半徑設(shè)置為0.2，領(lǐng)域最小個(gè)數(shù)設(shè)置為20；對(duì)于數(shù)據(jù)集Dataset 3 密度半徑設(shè)置為0.045，領(lǐng)域最小個(gè)數(shù)設(shè)置為17；對(duì)于數(shù)據(jù)集Dataset 4 密度半徑設(shè)置為0.017，領(lǐng)域最小個(gè)數(shù)設(shè)置為10。改進(jìn)的自適應(yīng)聚類算法無(wú)需輸入任何參數(shù)且聚類結(jié)果穩(wěn)定，因此統(tǒng)計(jì)一次實(shí)驗(yàn)結(jié)果即可。

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

圖4 至圖7 分別對(duì)應(yīng)算法1 至算法4 在人工數(shù)據(jù)集上得到的聚類結(jié)果。需要說明的是，算法4 得到的聚類結(jié)果可以以動(dòng)態(tài)形式展示初始聚類中心的確定、數(shù)據(jù)樣本集的劃分、數(shù)據(jù)的迭代次數(shù)以及最終的聚類結(jié)果。

圖4 4 種算法在人工數(shù)據(jù)集Data1 的聚類效果Fig.4 Clustering results of 4 algorithms on artificial Data1

圖5 4 種算法在人工數(shù)據(jù)集Data2 的聚類效果Fig.5 Clustering results of 4 algorithms on artificial Data2

圖6 4 種算法在人工數(shù)據(jù)集Data3 的聚類效果Fig.6 Clustering results of 4 algorithms on artificial Data3

圖7 4 種算法在人工數(shù)據(jù)集Data4 的聚類效果Fig.7 Clustering results of 4 algorithms on artificial Data4

實(shí)驗(yàn)表明，算法1 在數(shù)據(jù)集Dataset 2 和Dataset 3的聚類效果最優(yōu)，在數(shù)據(jù)集Dataset 1 和Dataset 4 的聚類效果不太理想，原因是算法1 通過隨機(jī)選取確定初始聚類中心，離群孤立點(diǎn)對(duì)聚類結(jié)果的干擾較大，明顯降低了聚類結(jié)果的準(zhǔn)確性，對(duì)于分布不均勻的數(shù)據(jù)集Dataset 1 和Dataset 4 的影響尤其明顯。

算法2 對(duì)數(shù)據(jù)集Dataset 3 上的聚類效果最優(yōu)，在數(shù)據(jù)集Dataset 4 上的聚類效果最不理想。相比算法3 與算法4，算法2 還是存在隨機(jī)確定初始聚類中心、人工輸入聚類數(shù)目的弊端，導(dǎo)致聚類準(zhǔn)確率無(wú)法得到保障。

算法3 和算法4 整體聚類效果明顯優(yōu)于算法1 和算法2。算法3 在數(shù)據(jù)集Dataset 2 和Dataset 3 的聚類效果最優(yōu)，由于數(shù)據(jù)集Dataset 1 和Dataset 4 分布不均勻且簇類間距離相差較遠(yuǎn)，導(dǎo)致算法3 不能在聚類過程中有效識(shí)別相互連接的團(tuán)簇，誤把部分相鄰的兩個(gè)類簇歸為同一類。此外，在聚類過程中算法3 過度依賴于參數(shù)的取值，參數(shù)一旦設(shè)置過大或過小，都會(huì)直接影響聚類質(zhì)量。

從數(shù)據(jù)集Dataset 2 和Dataset 3 的聚類結(jié)果可以看出，由于算法4 充分考慮了距離和密度兩個(gè)度量因素，聚類效果明顯優(yōu)于單一考慮距離的算法1。從數(shù)據(jù)集Dataset 1 和Dataset 4 的聚類結(jié)果可以看出，算法4 相較于算法3 來說，更適用于處理密度分布不均勻的數(shù)據(jù)，且不需要依賴參數(shù)的取值。

4.2 UCI數(shù)據(jù)集的仿真實(shí)驗(yàn)

4.2.1 實(shí)驗(yàn)數(shù)據(jù)

相較于人工數(shù)據(jù)集，UCI 數(shù)據(jù)集[20]屬性較多、維數(shù)較高且分布不均，聚類難度更高。選擇UCI數(shù)據(jù)集進(jìn)行測(cè)試的優(yōu)點(diǎn)在于，對(duì)于它們的實(shí)際劃分是已知的，聚類算法的性能可以依據(jù)聚類算法得到聚類結(jié)果，與已知的真實(shí)劃分進(jìn)行比較，進(jìn)而進(jìn)行評(píng)估。實(shí)驗(yàn)所用UCI數(shù)據(jù)集如表2 所示。

表2 UCI數(shù)據(jù)集特性Table 2 Features of UCI dataset

4.2.2 聚類性能評(píng)價(jià)指標(biāo)

算法聚類效果的評(píng)價(jià)，除采用常用的聚類準(zhǔn)確率作為評(píng)價(jià)方法之外，選定蘭德指數(shù)（Rand index）[21]、杰爾德系數(shù)（Jaccard coefficient）[22]和調(diào)整蘭德參數(shù)（adjusted Rand index）[23]作為本次實(shí)驗(yàn)的評(píng)價(jià)指標(biāo)進(jìn)行比較分析，這三個(gè)評(píng)價(jià)聚類性能的指標(biāo)是在已知數(shù)據(jù)樣本集正確標(biāo)簽的條件下，對(duì)聚類算法得到的劃分結(jié)果進(jìn)行評(píng)價(jià)的有效標(biāo)準(zhǔn)。

由定義可知，蘭德指數(shù)代表聚類算法得到的聚類劃分結(jié)果與原始數(shù)據(jù)集已知的分布之間的匹配度，杰爾德系數(shù)代表聚類算法劃分的樣本對(duì)在已知的分布內(nèi)依然是同一類簇的比率，這三個(gè)指標(biāo)值的范圍都在[-1,1]。

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

圖8 是將UCI 數(shù)據(jù)集的已知分類結(jié)果（對(duì)應(yīng)數(shù)據(jù)集左邊的柱狀圖）與改進(jìn)的自適應(yīng)聚類算法的聚類結(jié)果（對(duì)應(yīng)數(shù)據(jù)集右邊的柱狀圖）進(jìn)行直觀比較。對(duì)同一數(shù)據(jù)集的一條柱狀圖進(jìn)行縱向觀察，可以反映數(shù)據(jù)對(duì)象與類簇之間的所屬關(guān)系。對(duì)同一數(shù)據(jù)集的兩條柱狀圖進(jìn)行橫向比較，如果數(shù)據(jù)對(duì)象在兩條柱狀圖對(duì)應(yīng)的顏色不同，則代表該數(shù)據(jù)對(duì)象通過聚類算法得到的結(jié)果與已知的分類結(jié)果不同，若數(shù)據(jù)對(duì)象在兩條柱狀圖對(duì)應(yīng)的顏色相同，則代表聚類正確。

圖8 UCI數(shù)據(jù)集聚類正確率比較Fig.8 Comparison of clustering accuracy of UCI dataset

實(shí)驗(yàn)表明，改進(jìn)算法的聚類效果在Iris、Wine、Ecoli、WBC 數(shù)據(jù)集上表現(xiàn)較佳，而在Glass、WDBC 數(shù)據(jù)集上的表現(xiàn)一般。原因在于數(shù)據(jù)集Glass、WDBC的樣本個(gè)數(shù)、屬性數(shù)目和類別數(shù)目明顯高于其他數(shù)據(jù)集，且這兩個(gè)數(shù)據(jù)集不同類簇之間的樣本差異較小。

需要說明的是，表3 括號(hào)內(nèi)的波動(dòng)值反映的是算法1 與算法2 平均準(zhǔn)確率的區(qū)間。表3 關(guān)于不同算法的聚類準(zhǔn)確率表明，算法1 和算法2 聚類結(jié)果的波動(dòng)較大，而算法3 與改進(jìn)的動(dòng)態(tài)算法結(jié)果穩(wěn)定，且改進(jìn)的動(dòng)態(tài)算法相較于其余三種算法在四個(gè)UCI 數(shù)據(jù)集上的準(zhǔn)確率最高，其中高出算法1 的平均準(zhǔn)確率約20.87 個(gè)百分點(diǎn)，高出算法2 的平均準(zhǔn)確率約17.66 個(gè)百分點(diǎn)。

表3 4 種聚類算法準(zhǔn)確率比較Table 3 Accuracy comparison of 4 clustering algorithms

由圖9 四種算法關(guān)于蘭德指數(shù)、杰爾德系數(shù)以及調(diào)整蘭德參數(shù)的比較顯示，算法1 與算法2 的聚類指標(biāo)值相近，算法3 和算法4 的聚類指標(biāo)值相近，原因在于算法1 與算法2 僅考慮了距離因素，而算法3 與改進(jìn)算法都融合了密度因素，且算法4 的蘭德指數(shù)明顯高于剩余三種算法。

圖9 UCI數(shù)據(jù)集聚類評(píng)價(jià)指標(biāo)比較Fig.9 Comparison of UCI dataset clustering evaluation indicators

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

通過選取含有離群孤立點(diǎn)且分布復(fù)雜的二維數(shù)據(jù)進(jìn)行動(dòng)態(tài)聚類，在多個(gè)維數(shù)互異且分布不均的UCI數(shù)據(jù)集上與基于距離的傳統(tǒng)K-means 聚類算法、基于離群點(diǎn)檢測(cè)改進(jìn)的K-means 聚類算法以及基于密度的改進(jìn)的K-means 聚類算法進(jìn)行對(duì)比實(shí)驗(yàn)的結(jié)果表明：融合最近鄰矩陣與局部密度優(yōu)化的自適應(yīng)Kmeans 聚類算法，采取最鄰近矩陣與局部密度結(jié)合的雙重策略，自適應(yīng)確定初始聚類中心的數(shù)目及位置的同時(shí)，也能對(duì)所有的數(shù)據(jù)對(duì)象標(biāo)記所屬類簇，完成數(shù)據(jù)的初分配。自適應(yīng)K-means 聚類算法不僅可以考慮全局分布特點(diǎn)，也不會(huì)忽略數(shù)據(jù)對(duì)象局部領(lǐng)域內(nèi)的分布情況。

改進(jìn)的自適應(yīng)聚類算法在交替迭代的過程中不僅不需要人工設(shè)置聚類數(shù)目K值以及其他參數(shù)，而且在處理密度分布不均勻數(shù)據(jù)集時(shí)準(zhǔn)確率有顯著提升。如何簡(jiǎn)化算法運(yùn)算以此來高效地處理多維數(shù)據(jù)將是后續(xù)研究的重點(diǎn)工作。