宋坤

（重慶交通大學(xué) 信息科學(xué)與工程學(xué)院，重慶 400074）

聚類算法綜述

宋坤

（重慶交通大學(xué) 信息科學(xué)與工程學(xué)院，重慶 400074）

聚類是將物理或抽象對(duì)象的集合組成為由類似的對(duì)象組成的多個(gè)類的過程，是研究數(shù)據(jù)間邏輯上或物理上的相互關(guān)系的技術(shù)，是數(shù)據(jù)挖掘技術(shù)中的重要組成部分。結(jié)合國(guó)內(nèi)研究現(xiàn)狀，論文介紹各類主要的聚類算法及其應(yīng)用領(lǐng)域。

數(shù)據(jù)挖掘；相互關(guān)系；聚類

1　背景及意義

數(shù)據(jù)挖掘中聚類算法的應(yīng)用很廣泛。在商務(wù)上，聚類能幫助市場(chǎng)分析人員從客戶基本庫中發(fā)現(xiàn)不同的客戶群。 在生物學(xué)上，聚類能用于基因和蛋白質(zhì)的分類，獲得對(duì)種群中固定結(jié)構(gòu)的認(rèn)識(shí)［1］。聚類在地球觀測(cè)數(shù)據(jù)中相似地區(qū)的確定發(fā)揮作用。聚類也能用來對(duì)web上的文檔進(jìn)行分類，以發(fā)現(xiàn)有用的信息。聚類分析能作為一種獨(dú)立的工具來獲得數(shù)據(jù)分布的情況，觀察每個(gè)簇的特點(diǎn)，并對(duì)某些特定的節(jié)點(diǎn)進(jìn)一步分析。此外，聚類還可以作為其他方法的預(yù)處理步驟。

作為統(tǒng)計(jì)學(xué)的一個(gè)分支，聚類分析已經(jīng)被廣泛地研究若干年，主要集中在基于距離的聚類分析。

2　聚類算法簡(jiǎn)介

聚類是一個(gè)將數(shù)據(jù)集劃分為若干組或簇的過程，使得同一類的數(shù)據(jù)對(duì)象之間的相似度較高，而不同類的數(shù)據(jù)對(duì)象之間的相似度較低。聚類問題的關(guān)鍵是把相似的事物聚集在一起。

2.1傳統(tǒng)聚類算法

2.1.1層次方法

層次法對(duì)給定的數(shù)據(jù)對(duì)象集合進(jìn)行層次似的分解。按層次分解的形成方式，層次法可分為凝聚和分裂兩大類。凝聚的方法，也稱為自底向上的方法，一開始將每個(gè)對(duì)象作為單獨(dú)的一個(gè)類，然后相繼地合并相近的類，直到所有的類合并為一個(gè)（層次的最上層），或者達(dá)到一個(gè)終止條件為止。層次方法 （Hierarchical Method）中代表算法BIRCH、CURE、ROCK、CHAMELEON 算法等［2］。

2.1.2劃分方法

給定一個(gè)包含n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集，劃分法構(gòu)建數(shù)據(jù)的k個(gè)劃分，每個(gè)劃分表示一個(gè)類，并且k ≤ n。同時(shí)滿足如下的要求：①每個(gè)組至少包含一個(gè)對(duì)象；②每個(gè)對(duì)象屬于且僅屬于一個(gè)組。其代表算法有K-MEANS、K-MEDOIDS、大型數(shù)據(jù)庫劃分方法（CLARANS）等。

2.1.3密度方法

該方法主要思想是：只要鄰近區(qū)域的密度（對(duì)象或數(shù)據(jù)點(diǎn)的數(shù)目）超過某個(gè)閾值，就繼續(xù)聚類。也就是說，對(duì)給定類中的每個(gè)數(shù)據(jù)點(diǎn)，在一個(gè)給定范圍的區(qū)域內(nèi)必須至少包含某個(gè)數(shù)目的點(diǎn)。其代表算法有DBSCAN、OPTICS和DE NCLUE等［3］。

2.2新發(fā)展的聚類算法

2.2.1基于模糊的聚類方法

基于目標(biāo)函數(shù)的模糊聚類方法，該方法把聚類歸結(jié)成一個(gè)帶約束的非線性規(guī)劃問題，通過優(yōu)化求解獲得數(shù)據(jù)集的模糊劃分和聚類。該方法設(shè)計(jì)簡(jiǎn)單，解決問題的范圍廣，還可以轉(zhuǎn)化為優(yōu)化問題而借助經(jīng)典數(shù)學(xué)的非線性規(guī)劃理論求解，并易于在計(jì)算機(jī)上實(shí)現(xiàn)。因此，隨著計(jì)算機(jī)的應(yīng)用和發(fā)展，基于目標(biāo)函數(shù)的模糊聚類算法成為新的研究熱點(diǎn)。在基于目標(biāo)函數(shù)的聚類算法中，F(xiàn)CM 類型算法的理論最為完善、應(yīng)用最為廣泛。

2.2.2基于粒度的聚類方法

如果從信息粒度的角度來看，就會(huì)發(fā)現(xiàn)聚類和分類的相通之處：聚類操作實(shí)際上是在一個(gè)統(tǒng)一粒度下進(jìn)行計(jì)算的；分類操作是在不同粒度下進(jìn)行計(jì)算的。在粒度原理下，聚類和分類的相通使得很多分類的方法也可以用在聚類方法中。作為一個(gè)新的研究方向，雖然目前粒度計(jì)算還不成熟，尤其是對(duì)粒度計(jì)算語義的研究還相當(dāng)少，但是相信隨著粒度計(jì)算理論本身的不斷完善和發(fā)展。

2.2.3量子聚類

該方法把聚類問題看作一個(gè)物理系統(tǒng)，其很好的例子就是基于相關(guān)點(diǎn)的 Pott 自旋和統(tǒng)計(jì)機(jī)理提出的量子聚類模型。并且許多算例表明，對(duì)于傳統(tǒng)聚類算法無能為力的幾種聚類問題，該算法都得到了比較滿意的結(jié)果［4］。

2.2.4譜聚類

為了能在任意形狀的樣本空間上聚類，且收斂于全局最優(yōu)解，學(xué)者們開始研究一類新型的聚類算法，稱為譜聚類算法（Spectral Clustering Algorithm）。譜聚類算法最初用于計(jì)算機(jī)視覺、VLSI設(shè)計(jì)等領(lǐng)域，最近才開始用于機(jī)器學(xué)習(xí)中，并迅速成為國(guó)際上機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn)［5］。

3　結(jié)語

數(shù)據(jù)聚類正在蓬勃的發(fā)展，有貢獻(xiàn)的領(lǐng)域包括數(shù)據(jù)挖掘，統(tǒng)計(jì)學(xué)，機(jī)器學(xué)習(xí)，空間數(shù)據(jù)庫技術(shù)，生物學(xué)以及市場(chǎng)營(yíng)銷?，F(xiàn)在數(shù)據(jù)聚類分析已經(jīng)成為一個(gè)非常活躍的研究課題。

［1］田野，劉大有，楊博. 復(fù)雜網(wǎng)絡(luò)聚類算法在生物網(wǎng)絡(luò)中的應(yīng)用［J］. 計(jì)算機(jī)科學(xué)與探索，2010，04:330-337.

［2］Amineh Amini，Teh Ying Wah，Hadi Saboohi. On Density-Based Data Streams Clustering Algorithms: A Survey［J］. Journal of Computer Science & Technology，2014，01:116-141.

［3］Local and global approaches of affinity propagation clustering for large scale data［J］. Journal of Zhejiang University（Science A:An International Applied Physics & Engineering Journal），2008，10:1373-1381.

［4］王玉瑛. 量子聚類及其在社團(tuán)檢測(cè)中的應(yīng)用［D］.西安電子科技大學(xué)，2014.

［5］蔡曉妍，戴冠中，楊黎斌. 譜聚類算法綜述［J］. 計(jì)算機(jī)科學(xué)，2008，07:14-18.

TP311.13

A

1003-5168（2015）11-254-01

宋坤（1989.07- ），男，河南新鄉(xiāng)人，重慶交通大學(xué)信息科學(xué)與工程學(xué)院2013級(jí)碩士研究生，軟件工程專業(yè)，研究方向：數(shù)據(jù)挖掘。