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

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

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

?

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

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

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

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

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

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

1 相關(guān)定義

定義1 截?cái)嗑嚯xdc,一個(gè)距離閾值,用于計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的局部密度。

定義2 局部密度ρi,表示數(shù)據(jù)點(diǎn)集中與xi的距離小于截?cái)嗑嚯xdc的其他數(shù)據(jù)點(diǎn)個(gè)數(shù)。

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

(1)

(2)

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

(3)

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

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

(4)

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

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

(5)

2 自動(dòng)聚類算法原理

2.1 聚類個(gè)數(shù)的自動(dòng)確定

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

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

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

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

3 自動(dòng)聚類算法實(shí)現(xiàn)過程

對(duì)于包含N個(gè)數(shù)據(jù)點(diǎn)的集合S,聚類步驟為:

1) 初始化截?cái)嗑嚯x參數(shù)dc。

2) 根據(jù)截?cái)嗑嚯x參數(shù)dc計(jì)算集合S中每個(gè)數(shù)據(jù)點(diǎn)的局部密度ρi。

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

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

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

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

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

4 實(shí)驗(yàn)驗(yàn)證分析

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

4.1 自動(dòng)聚類算法驗(yàn)證

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

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

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

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

5 結(jié) 論

本文提出了一種基于數(shù)據(jù)包含度的自動(dòng)聚類算法。該算法基于數(shù)據(jù)包含度的計(jì)算實(shí)現(xiàn)了自動(dòng)確定聚類個(gè)數(shù)和聚類中心點(diǎn)，并進(jìn)一步采用跟隨策略實(shí)現(xiàn)數(shù)據(jù)點(diǎn)集合聚類。自動(dòng)聚類算法的實(shí)現(xiàn)過程簡單，不需迭代和考慮收斂，計(jì)算量小，計(jì)算速度快。大量數(shù)據(jù)樣例的聚類實(shí)驗(yàn)證明自動(dòng)聚類算法有效可靠。與經(jīng)典K-means的仿真比較結(jié)果也證明了自動(dòng)聚類算法能夠理想地聚類，具有很好的適應(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é)報(bào),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é)基金青年基金項(xiàng)目(61401363)資助

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

TP311.5

A

1000-2758(2016)05-0863-04