基于 Chameleon算法和譜平分法的聚類新方法

張 友,趙鳳霞

(1.大連民族學院理學院,遼寧大連 116605;

2.秦皇島職業技術學院信息工程系,河北秦皇島 066100)

基于 Chameleon算法和譜平分法的聚類新方法

張 友1,趙鳳霞2

(1.大連民族學院理學院,遼寧大連 116605;

2.秦皇島職業技術學院信息工程系,河北秦皇島 066100)

在分析傳統的聚類算法優越性和存在不足的基礎上,基于 Chameleon算法和譜平分法的思想提出了一種新的聚類方法。相比傳統聚類算法而言此算法克服了如 k-means算法、E M算法等傳統聚類算法在聚類不為凸的樣本空間時容易陷入局部最優的缺點,能在任意形狀的樣本空間上聚類,且收斂于全局最優解,并且可以降低噪聲和離群點的影響,提高了算法的有效性。在 UCI數據集和 5個特殊的二維數據點組成的數據集上進行了實驗,證明了本方法的有效性。

聚類算法;Chameleon算法;譜平分法;k-mean算法;EM算法;不為凸的樣本空間

聚類分析是機器學習領域中的一個重要分支,是人們認識和探索事物之間內在聯系的有效手段。所謂聚類(clustering)就是將數據對象分組成為多個類或簇 (cluster),使得在同一簇中的對象之間具有較高的相似度,而不同簇中的對象差別較大。聚類算法有很多種,需要根據應用所涉及的數據類型、聚類的目的以及具體應用要求來選擇合適的聚類算法。如果利用聚類分析作為描述性或探索性的工具,那么就可以使用若干聚類算法對同一個數據集進行處理以觀察可能獲得的有關 (數據特征)描述[1]。傳統的聚類算法,如k-means算法、EM算法等都是建立在凸球形的樣本空間上,但當樣本空間不為凸時,算法會陷入局部最優。為了能在任意形狀的樣本空間上聚類,且收斂于全局最優解,本文結合 Chameleon算法和譜平分法提出了一類新型的聚類算法 (以下簡稱 C-譜平算法)。該算法首先根據給定的樣本數據集定義一個描述成對數據點相似度的親合矩陣,然后構造稀疏圖矩陣 (K-最近鄰圖矩陣),并計算該稀疏矩陣的特征值和特征向量,然后選擇合適的特征向量聚類不同的數據點。此算法能夠有效地聚類存在噪聲和離群點的空間數據,而且對簇的大小、形狀和密度沒有要求,能在任意形狀的樣本空間上聚類,且收斂于全局最優解。

1 Chameleon算法與譜平分法

通常聚類分析算法可以劃分為以下幾類:劃分方法 (partitioning method)、層次方法 (hierarchical method)、基于密度的方法 (density-based method)、基于網格的方法 (grid-based method)、基于模型的方法(model-based memod)。

Chameleon算法[2]是使用動態建模的層次聚類方法,Chameleon力求合并這樣的一對簇,合并后產生的簇,用接近性和互連性度量,與原來的一對簇最相似。因為這種方法依賴簇對而不是全局模型,Chameleon能夠處理包含具有各種不同特性簇的數據。

譜平分法[3]建立在圖論中的譜圖理論基礎上,其基本思想是一個有 n個節點的無向圖 G的Laplace矩陣是一個 n×n維的對稱矩陣 L。L的對角線上的元素 Lii是節點 i的度,而其他非對角線上的元素Lij則表示節點 i和節點 j的連接關系。如果這兩個節點之間有邊連接,則 Lij值為 -1,否則為 0。我們可以將矩陣 L表示成 L=K-A,其中 K是一個對角矩陣。矩陣 L有一個特征值為0,且其對應的特征向量為 l=(1,1,...,1)。可以從理論上證明,不為零的特征值所對應的特征向量的各元素中,同一個社團內的節點對應的元素是近似相等的。

2 C-譜平算法步驟

步驟流程如圖 1。

圖 1 算法步驟圖

步驟1:將數據集按照給定的相似度公式構造相似度矩陣 Sn×n(其中 n為數據集中數據的個數,Lij表示第 i個數據與第 j個數據的相似度)。

步驟2:根據相似度矩陣構造稀疏圖,從而產生 k-最近鄰圖。把相似度矩陣中每個數據和它的 k個最近鄰 (即最相似的數據)用 1表示,其余用 0表示。產生的 k-最近鄰圖的鄰接矩陣用 SK表示。

步驟3:求 k-最近鄰圖的 Laplace矩陣 L。

步驟4:用譜平分法進行聚類。計算矩陣 L的前 x個最大特征值對應的特征向量,使其在 Rx空間中構成與原數據一一對應的表述,然后在 Rz空間中進行聚類。具體步驟如下:

(1)計算矩陣 L的前x個最大特征值所對應的特征向量x1,...,xx(必要時需作正交化處理),構造矩陣 X=[x1,…,xx]∈Rn×k;選取矩陣 L的前x個最大的特征值所對應的特征向量的原因在于:對于存在 k個理想的彼此分離簇的有限數據集,可以證明矩陣 L的前x個最大特征值為 1,第x+1個特征值則嚴格小于 1,二者之間的差距取決于這x個聚類的分布情況。當聚類內部分布得越密,各聚類間分布得越開時,第x+1個特征值就越小,此時,以矩陣 X中的每行作為 x維空間中的一個點所形成的 x聚類。它們將彼此正交地分布于x維空間中的單位球上,并且在單位球上形成這x聚類對應著原空間中所有點形成的x個聚類。

(2)將矩陣 X的行向量轉變為單位向量,得到矩陣 Y,即

(3)將矩陣 Y的每一行看作是 Rx空間中的一個點,對其使用 k均值算法或任意其他經典聚類算法,得到 k個聚類。

(4)將數據點yi劃分到聚類 j中,當且僅當Y的第 i行被劃分到聚類 j中。

3 實驗結果

3.1 UCI數據集實驗結果

為了證明 C-譜平算法的有效性,本文首先在UCI上選取了若干數據集,并通過與其他方法比較,證明了 C-譜平算法的有效性。數據集的說明見表 1。與其他 3種方法在聚類精度上的比較如圖 2。

表 1 數據說明

圖 2 各種算法在表 1所列數據集上的聚類精度比較

3.2 二維數據點組成的數據集實驗結果

為了進一步說明 C-譜平算法能在任意形狀的樣本空間上聚類,且收斂于全局最優解,在 5個由二維數據點組成的數據集上進行了實驗,數據集的幾何形狀如圖 3。DS1包含 5個大小、形狀、密度各不相同的聚類,此外還包含有異常點;DS2由兩個相鄰的聚類組成,每個聚類中不同區域的密度各不相同;DS3由 6個形狀、大小、方向各不相同的聚類組成,與此同時這些聚類還包含了異常點,彼此交錯在一起;DS4,由 8個不同形狀、大小、方向的聚類組成,從空間上看有的聚類包含在另一個聚類中間,DS4同樣包含一些隨機點和人為的異常點 (如一些匯集成垂直條紋的點);DS5包括了 8個不同形狀、不同大小、不同密度和不同方向的聚類,同時也含有噪聲數據點。這些數據集有一個挑戰性的特征,即聚類之間彼此距離太近,而且聚類密度彼此不同。數據集的大小從6 000到 10 000數據點,精確的大小如圖 3。圖 4為某些經典傳統聚類算法與 C-譜平算法在這些數據集上的聚類精度比較,從結果可以看出 C-譜平算法的聚類精度遠遠高于傳統的聚類方法,從而證明了 C-譜平算法的有效性。

圖 3 實驗數據集

圖 4 不同方法的聚類精度比較

4 結 語

本文結合 Chameleon算法和譜平分法的優點,提出了一種新的聚類算法,即 C-譜平算法。相比其他聚類算法而言本文算法克服了如 kmeans算法、EM算法等傳統聚類算法在聚類不為凸的樣本空間時容易陷入局部最優的缺點,能在任意形狀的樣本空間上聚類,且收斂于全局最優解。并且可以降低噪聲和離群點的影響,提高了計算的有效性。這種聚類算法可以用于圖像處理、數據挖掘等領域。

盡管 C-譜平算法在實驗中取得了很好的效果,但仍有許多還需研究和解決的問題。接下來的工作主要包括 3個方面:(1)如何構造相似矩陣S:相似矩陣的構造都依賴于領域知識,而沒有給出通用的規則,系統地研究本文聚類中相似矩陣的構造問題將是未來研究的一個方向。(2)如何處理特征向量:用多少個特征向量進行聚類,如何選取、計算及使用這些特征向量等問題均沒有得到很好的理論解釋,這些都是未來急需解決的問題。(3)如何選取 Laplacian矩陣:如何根據具體環境選擇合適的Laplace矩陣,還需要進行大量的理論研究和實驗工作。

[1]JA IN A,MURTY M,FLYNN P.Data clustering:A Review[J].ACM Computing Survey,1999,31(3):264-323.

[2]KARYPIS G,HAN E-H,KUMAR V.Chameleon:A hierarchical clustering algorithm using dynamic modeling[J].IEEE Computer,1999,32(8):68-75.

[3]ZHANG Shihua,WANG Ruisheng,ZHANG Xiangsun.Indentification of overlapping community structure in complex networks using fuzzy c-means clustering[J].Physica A,2007(374):483-490.

[4]H IGHAM D J,KALNAA G,M ILLA K.Spectral clustering and its use in bioinformaties[J].Journalof Computational and Applied mathematics,2007,20(4):25-27.

[5]KANUNGO T,MOUNTD M,NETANYAHU N,et al.An efficient k-means clustering algorithm.Analysis and implementation[J].IEEE Trans Pattern Analysis and Machine Intelligence,2002(24):881-892.

[6]KANUNGO T,MOUNT D M,NETANYAHU N,et al.A local search approximation algorithm for k-means clustering[J].Computational Geometry:Theory and Applications,2004(28):89-112.

[7]楊久俊,鄧輝文,滕姿.基于混合粒子群優化算法的聚類分析[J].計算機工程與設計,2008,29(22):5820-5823.

[8]郭維維,韓萌.基于最小描述長度和遺傳算法的屬性選擇方法[J].大連民族學院學報,2009,11(1):85-87.

A New ClusteringM ethod Based on the Chameleon Algorithm and the Spectral Bisection M ethod

ZHANG You1,ZHAO Feng-x ia2
(1.College of Science,Dalian NationalitiesUniversity,Dalian Liaoning 116605,China;2.Department of Infor mation Engineering,Qinhuangdao Institute of Technology,Qinhuangdao Hebei 066100,China)

W ith analysis of advantages and disadvantages of traditional clustering algorithms,we proposed a new clusteringmethod based on the Chameleon algorithm and the spectral bisection method.Unlike traditional clustering algorithms,this algorithm overcomes a disadvantage of some traditional clustering algorithms such as the k-means algorithm and the EM algorithm,that is,they are prone to local optimum when clustering on a nonconvex sample space.It is capable of clustering on a sample space of any shape and converging to the globaloptimal solution.It also reduces the influence of the noise and outliers,increasing its effectiveness.We carried out exper iments on the UCI data sets and five data sets of special two-dimensional data points and proved the effectiveness of the method.

clustering algorithm;the Chameleon algorithm;the spectral bisectionmethod;the k-means algorithm;the EM algorithm;nonconvex sample space

TP311

A

1009-315X(2010)01-0061-04

2009-07-08

張友 (1960-),男,吉林四平人,教授,主要從事粗糙集、代數學研究。

(責任編輯 劉敏)