馬云紅, 王成汗, 江騰蛟, 張堃

(西北工業(yè)大學(xué) 電子信息學(xué)院, 陜西 西安 710072)

?

一種基于數(shù)據(jù)包含度的自動聚類算法

馬云紅, 王成汗, 江騰蛟, 張堃

(西北工業(yè)大學(xué) 電子信息學(xué)院, 陜西 西安 710072)

聚類分析是機器學(xué)習(xí)和模式識別領(lǐng)域的一個重要問題，聚類算法常用于解決這類問題。針對傳統(tǒng)聚類算法運算量大、不適應(yīng)任意分布數(shù)據(jù)聚類的不足，提出了一種基于數(shù)據(jù)包含度的自動聚類算法。該算法引入數(shù)據(jù)包含度的概念，能夠自動確定聚類個數(shù)和聚類中心，并進(jìn)一步采用跟隨策略實現(xiàn)聚類。多組數(shù)據(jù)的實驗驗證了自動聚類算法的有效性。對不同分布的數(shù)據(jù)進(jìn)行了自動聚類算法與K-means聚類算法的聚類結(jié)果比較，實驗結(jié)果表明自動聚類算法具有很好的聚類性能。

聚類算法；數(shù)據(jù)包含度；數(shù)據(jù)局部密度

聚類分析是機器學(xué)習(xí)和模式識別領(lǐng)域的一個非?；钴S又極具挑戰(zhàn)性的研究方向。它是根據(jù)數(shù)據(jù)樣本間的相似性將樣本劃分到不同的類簇，使同類簇中數(shù)據(jù)樣本之間相似度高，異類簇中數(shù)據(jù)樣本之間相似度低。典型的算法有K-means聚類算法[1]、譜聚類算法[2]、DBSCAN算法[3]以及CFSFDP算法[4]等。K-means聚類算法是找出K個聚類中心，按照最鄰近原則將數(shù)據(jù)集合中的數(shù)據(jù)劃分到K個聚類中，然后根據(jù)判定函數(shù)調(diào)整數(shù)據(jù)歸屬。譜聚類算法的思想以圖論、相似性為基礎(chǔ)，將聚類問題轉(zhuǎn)化為無向圖的多路劃分問題。譜聚類算法計算較耗時。DBSCAN算法是基于密度的聚類算法，算法可以進(jìn)行任意數(shù)據(jù)分布的聚類。Alex Rodriguez和Alessandro Laio提出一種CFSFDP算法[4]，基于密度峰值和距離的計算，將數(shù)據(jù)點自身的密度較大且相互距離較遠(yuǎn)的數(shù)據(jù)點作為聚類中心點。該算法能夠識別任意分布的聚類簇，并且計算簡單快速，但需要人工介入對聚類個數(shù)進(jìn)行確定。本文在CFSFDP算法的基礎(chǔ)上，提出一種基于數(shù)據(jù)包含度的自動聚類算法ACA(automatic clustering algorithm)。該算法通過計算數(shù)據(jù)點的綜合考慮量，并據(jù)此降序排序。對排序后的數(shù)據(jù)序列依次計算數(shù)據(jù)包含度。根據(jù)數(shù)據(jù)包含度的值自動確定聚類個數(shù)，同時確定聚類中心，最后結(jié)合跟隨策略實現(xiàn)自動聚類。

1 相關(guān)定義

定義1 截斷距離dc,一個距離閾值,用于計算每個數(shù)據(jù)點的局部密度。

定義2 局部密度ρi,表示數(shù)據(jù)點集中與xi的距離小于截斷距離dc的其他數(shù)據(jù)點個數(shù)。

對于包含N個數(shù)據(jù)點的數(shù)據(jù)點集合S,集合S中數(shù)據(jù)點xi的局部密度ρi定義為S中與xi的距離小于截斷距離dc的其他數(shù)據(jù)點的個數(shù),表示為(1)式:式中dij是數(shù)據(jù)點xj和xi間的歐氏距離;χ(dij-dc)函數(shù)用以判斷xj距xi是否小于距離閾值dc,表達(dá)式如(2)式所示。根據(jù)定義,可以計算出數(shù)據(jù)集中每個點的局部密度。

(1)

(2)

定義3 距離δi表示數(shù)據(jù)點xi到比它局部密度高的其他數(shù)據(jù)點的最小距離。定義為(3)式。

(3)

定義4 綜合考慮量γi,表示每個數(shù)據(jù)點的局部密度與距離的乘積。局部密度大說明聚在這個點周圍的數(shù)據(jù)點多;距離大說明該點距離其他潛在中心的距離遠(yuǎn)。綜合考慮量越大,則越容易成為聚類中心。

對于N個數(shù)據(jù)點集合S中第i個數(shù)據(jù)點的綜合考慮量γi由(4)式計算。

(4)

定義5 數(shù)據(jù)包含度μl,表示聚類后對數(shù)據(jù)點集合中的數(shù)據(jù)點的包含程度。

對于N個數(shù)據(jù)點集合S。根據(jù)每個數(shù)據(jù)點的綜合考慮量值進(jìn)行降序排序。綜合考慮量大的數(shù)據(jù)點更容易成為聚類中心。假設(shè)數(shù)據(jù)集合可以聚類成M個類,則必然是綜合考慮量排在前M個的數(shù)據(jù)點為聚類中心,如何確定聚類個數(shù)M,需要根據(jù)數(shù)據(jù)包含度來計算。數(shù)據(jù)包含度的計算公式如(5)式所示

(5)

2 自動聚類算法原理

2.1 聚類個數(shù)的自動確定

自動聚類算法可以自動確定聚類個數(shù)M并確定聚類中心。它是根據(jù)數(shù)據(jù)包含度μl的值確定的。如果μl=1,則說明聚類包含了所有的數(shù)據(jù)點。如果 μl>1,則說明包含的數(shù)據(jù)點數(shù)量大于原始數(shù)據(jù)的數(shù)量,也就意味著有部分?jǐn)?shù)據(jù)被重復(fù)分類到不同的類中。如果 μl<1,則說明有部分?jǐn)?shù)據(jù)沒有被分到聚類中。根據(jù)綜合考慮量的排序,從綜合考慮量最大的點開始,依次計算以這些點作為聚類中心時的數(shù)據(jù)包含度,直到發(fā)現(xiàn) μl=1,此時的l值作為聚類個數(shù)M,對應(yīng)的M個點即為聚類中心點。若不能滿足 μl=1，則尋找滿足 μl>1且 μl-1<1的l，取l-1為聚類個數(shù)。

2.2 基于跟隨策略實現(xiàn)非聚類中心數(shù)據(jù)點劃分

基于數(shù)據(jù)包含度的計算,確定了聚類個數(shù),并同時確定了聚類中心點,余下的工作就是將非聚類中心點的其他數(shù)據(jù)點劃分到聚類中。論文采用跟隨策略進(jìn)行非聚類中心數(shù)據(jù)點的劃分。

跟隨策略:對于非聚類中心的樣本數(shù)據(jù)i(i≥M+1),將點i劃分到比自身綜合考慮量大且距離自身最近的樣本點所屬的類簇。假設(shè)已經(jīng)確定的聚類個數(shù)為M,則前M個點為聚類中心,將第M+1個數(shù)據(jù)根據(jù)距離最近原則劃分到前M個聚類中心的一個類中;同理,將數(shù)據(jù)集合中第j(M+1

3 自動聚類算法實現(xiàn)過程

對于包含N個數(shù)據(jù)點的集合S,聚類步驟為:

1) 初始化截斷距離參數(shù)dc。

2) 根據(jù)截斷距離參數(shù)dc計算集合S中每個數(shù)據(jù)點的局部密度ρi。

3) 對集合S中數(shù)據(jù)點按局部密度ρi的值進(jìn)行降序排序得S′={xβ1,xβ2,…,xβN},βi記錄數(shù)據(jù)點的原始編號。

4) 根據(jù)(3)式順序計算集合S′中下標(biāo)為βi的數(shù)據(jù)點的距離δβi。

5) 依次計算數(shù)據(jù)點集合S′中下標(biāo)為βi的數(shù)據(jù)點的綜合考慮量γβi。

7) 順次計算數(shù)據(jù)包含度μl,(l=1,2…),并根據(jù)μl的值確定聚類個數(shù),進(jìn)而確定聚類中心。

8) 采用跟隨策略對非聚類中心的其他數(shù)據(jù)點進(jìn)行聚類劃分。

4 實驗驗證分析

為了驗證本文提出的自動聚類算法性能,本文采用Aggregation數(shù)據(jù)、Flame數(shù)據(jù)和Spiral數(shù)據(jù)作為測試樣本集,進(jìn)行聚類算法驗證,并與經(jīng)典的K-means聚類算法進(jìn)行了比較。

4.1 自動聚類算法驗證

以Aggregation數(shù)據(jù)進(jìn)行聚類個數(shù)確定的驗證。圖1為Aggregation數(shù)據(jù)分布圖。它含有788個數(shù)據(jù)點,數(shù)據(jù)點為二維無量綱數(shù)值。從直觀分析,數(shù)據(jù)應(yīng)分為7個聚類。實驗中,自動聚類算法計算出的數(shù)據(jù)包含度曲線如圖2所示。從圖2中可以看出,滿足μl>1且μl-1<1的l為8,則聚類個數(shù)選l-1為7。自動聚類個數(shù)選取正確。

圖1 Aggregation數(shù)據(jù)的分布 圖2 Aggregation數(shù)據(jù)的數(shù)據(jù)包含度

4.2 自動聚類(ACA)算法與K-means算法比較

為了驗證自動聚類算法的廣泛有效，本文進(jìn)行了大量的標(biāo)準(zhǔn)數(shù)據(jù)驗證，并與傳統(tǒng)聚類算法進(jìn)行了比較分析。圖3是ACA算法對Flame數(shù)據(jù)的聚類結(jié)果，將Flame分成了焰心和外焰兩部分。圖4是K-means算法對Flame數(shù)據(jù)的聚類結(jié)果，將部分外焰數(shù)據(jù)誤分到了焰心部分。圖5是ACA算法對Spiral數(shù)據(jù)的聚類結(jié)果，圖中正確分出了3個螺旋線。圖6是K-means算法對Spiral數(shù)據(jù)的聚類結(jié)果，將螺旋線數(shù)據(jù)分成了三等分扇形空間，沒有分出螺旋線。從分類結(jié)果圖中可以看出，自動聚類算法對實驗數(shù)據(jù)的聚類效果比較理想，而K-means聚類算法的分類結(jié)果不合理。表1列出了2種算法對于2組數(shù)據(jù)誤分率的數(shù)值比較。實驗數(shù)據(jù)說明K-means聚類算法具有一定的局限性，自動聚類算法的聚類結(jié)果理想。

圖3 ACA算法進(jìn)行Flame數(shù)據(jù)聚類 圖4 K-Means算法進(jìn)行Flame數(shù)據(jù)聚類 圖5 ACA算法進(jìn)行Spiral數(shù)據(jù)聚類

圖6 K-Means算法進(jìn)行Spiral數(shù)據(jù)聚類

數(shù)據(jù)名稱數(shù)據(jù)總個數(shù)聚類個數(shù)K?means誤分率/%ACA誤分率/%Flame數(shù)據(jù)240218．330Spiral數(shù)據(jù)312335．260

5 結(jié) 論

本文提出了一種基于數(shù)據(jù)包含度的自動聚類算法。該算法基于數(shù)據(jù)包含度的計算實現(xiàn)了自動確定聚類個數(shù)和聚類中心點，并進(jìn)一步采用跟隨策略實現(xiàn)數(shù)據(jù)點集合聚類。自動聚類算法的實現(xiàn)過程簡單，不需迭代和考慮收斂，計算量小，計算速度快。大量數(shù)據(jù)樣例的聚類實驗證明自動聚類算法有效可靠。與經(jīng)典K-means的仿真比較結(jié)果也證明了自動聚類算法能夠理想地聚類，具有很好的適應(yīng)性和魯棒性。

[1] Zhang Z, Zhang J, Xue H. Improved K-Means Clustering Algorithm[C]∥Image and Signal Processing CISP′08 Congress on IEEE, 2008, 5: 169-172

[2] Wu J, Cui Z M, Shi Y J, Gong S R. Local Density-Based Similarity Matrix Construction for Spectral Clustering[J]. Journal of China Institute of Communications, 2013, 34(3): 14-22

[3] 馮少榮, 肖文俊. DBSCAN聚類算法的研究與改進(jìn)[J]. 中國礦業(yè)大學(xué)學(xué)報,2008, 37(1): 105-110

Feng Shaorong, Xiao Wenjun. An Improved DBSCAN Clustering Algorithm[J]. Journal China University of Mining and Technology, 2008, 37(1): 105-110 (in Chinese)

[4] Rodriguez A, Laio A. Clustering by Fast Search and Find of Density Peaks[J]. Science, 2014, 344(6191): 1492-1496

An Automatic Clustering Algorithm Based on Data Contained Ratio

Ma Yunhong, Wang Chenghan, Jiang Tengjiao, Zhang Kun

School of Electronics and Information, Northwestern Polytechnic University, Xi′an 710072, China

Cluster analysis is an important issue for machine learning and pattern recognition. Clustering algorithm is usually used in solving these problems. A novel automatic clustering algorithm is developed based on data contained ratio. In automatic clustering algorithm which is presented in this paper, the concept of data contained ratio is proposed, the cluster number can be determined automatically based on the data contained ratio, and the relative cluster centers are found similarly Several groups data are used to testify and demonstrate the validity and effectiveness of the cluster algorithm. In addition, the comparison between the traditional K-means cluster algorithm and automatic cluster algorithm is processed. The results demonstrate that the automatic cluster algorithm has high performance in clustering random distribution data set.

clustering algorithm; data contained ratio; data local density

2016-03-05

西北工業(yè)大學(xué)研究生創(chuàng)意創(chuàng)新種子基金(G2015KY0407)與國家自然科學(xué)基金青年基金項目(61401363)資助

馬云紅(1972—),女,西北工業(yè)大學(xué)副教授、博士，主要從事人工智能優(yōu)化算法、飛行器任務(wù)規(guī)劃和智能控制、復(fù)雜系統(tǒng)建模與仿真的研究。

TP311.5

A

1000-2758(2016)05-0863-04