一種基于數據包含度的自動聚類算法

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

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

?

一種基于數據包含度的自動聚類算法

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

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

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

聚類算法；數據包含度；數據局部密度

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

1 相關定義

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

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

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

(1)

(2)

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

(3)

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

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

(4)

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

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

(5)

2 自動聚類算法原理

2.1 聚類個數的自動確定

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

2.2 基于跟隨策略實現非聚類中心數據點劃分

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

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

3 自動聚類算法實現過程

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

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

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

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

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

5) 依次計算數據點集合S′中下標為βi的數據點的綜合考慮量γβi。

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

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

4 實驗驗證分析

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

4.1 自動聚類算法驗證

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

圖1 Aggregation數據的分布 圖2 Aggregation數據的數據包含度

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

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

圖3 ACA算法進行Flame數據聚類 圖4 K-Means算法進行Flame數據聚類 圖5 ACA算法進行Spiral數據聚類

圖6 K-Means算法進行Spiral數據聚類

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

5 結 論

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

[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]. 中國礦業大學學報,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

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

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

TP311.5

A

1000-2758(2016)05-0863-04