張 友,趙鳳霞

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

2.秦皇島職業(yè)技術(shù)學(xué)院信息工程系,河北秦皇島 066100)

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

張 友1,趙鳳霞2

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

2.秦皇島職業(yè)技術(shù)學(xué)院信息工程系,河北秦皇島 066100)

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

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

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

1 Chameleon算法與譜平分法

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

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

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

2 C-譜平算法步驟

步驟流程如圖 1。

圖 1 算法步驟圖

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

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

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

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

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

(2)將矩陣 X的行向量轉(zhuǎn)變?yōu)閱挝幌蛄?得到矩陣 Y,即

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

(4)將數(shù)據(jù)點(diǎn)yi劃分到聚類 j中,當(dāng)且僅當(dāng)Y的第 i行被劃分到聚類 j中。

3 實(shí)驗(yàn)結(jié)果

3.1 UCI數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

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

表 1 數(shù)據(jù)說明

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

3.2 二維數(shù)據(jù)點(diǎn)組成的數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

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

圖 3 實(shí)驗(yàn)數(shù)據(jù)集

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

4 結(jié) 語

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

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

[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]楊久俊,鄧輝文,滕姿.基于混合粒子群優(yōu)化算法的聚類分析[J].計(jì)算機(jī)工程與設(shè)計(jì),2008,29(22):5820-5823.

[8]郭維維,韓萌.基于最小描述長度和遺傳算法的屬性選擇方法[J].大連民族學(xué)院學(xué)報(bào),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-),男,吉林四平人,教授,主要從事粗糙集、代數(shù)學(xué)研究。

(責(zé)任編輯 劉敏)