聚類算法綜述

章永來(lái) 周耀鑒

摘 要：大數(shù)據(jù)時(shí)代，聚類這種無(wú)監(jiān)督學(xué)習(xí)算法的地位尤為突出。近年來(lái)，對(duì)聚類算法的研究取得了長(zhǎng)足的進(jìn)步。首先，總結(jié)了聚類分析的全過(guò)程、相似性度量、聚類算法的新分類及其結(jié)果的評(píng)價(jià)等內(nèi)容，將聚類算法重新劃分為大數(shù)據(jù)聚類與小數(shù)據(jù)聚類兩個(gè)大類，并特別對(duì)大數(shù)據(jù)聚類作了較為系統(tǒng)的分析與總結(jié)。此外，概述并分析了各類聚類算法的研究進(jìn)展及其應(yīng)用概況，并結(jié)合研究課題討論了算法的發(fā)展趨勢(shì)。

關(guān)鍵詞：聚類;相似性度量;大數(shù)據(jù)聚類;小數(shù)據(jù)聚類;聚類評(píng)價(jià)

Abstract： Clustering is very important as an unsupervised learning algorithm in the age of big data. Recently， considerable progress has been made in the analysis of clustering algorithm. Firstly， the whole process of clustering， similarity measurement， new classification of clustering algorithms and evaluation on their results were summarized. Clustering algorithms were divided into two categories： big data clustering and small data clustering， and the systematic analysis and summary of big data clustering were carried out particularly. Moreover， the research progress and application of various clustering algorithms were summarized and analyzed， and the development trend of clustering algorithms was discussed in combination with the research topics.

Key words： clustering; similarity measurement; big data clustering; small data clustering; clustering evaluation

0 引言

把具有相似特性的實(shí)物放到一起是人類最原始的活動(dòng)之一。這也是聚類的最初目的。早在1984年，Aldenderfer等[1]就已經(jīng)提出了聚類分析的四大功能：一是數(shù)據(jù)分類的進(jìn)一步擴(kuò)展;二是對(duì)實(shí)體歸類的概念性探索;三是通過(guò)數(shù)據(jù)探索而生成假說(shuō);四是一種基于實(shí)際數(shù)據(jù)集歸類假說(shuō)的測(cè)試方式。在很多情況下，樣本數(shù)據(jù)集并沒(méi)有分類，即每一個(gè)數(shù)據(jù)樣本都沒(méi)有分類標(biāo)簽。一般而言，聚類指將沒(méi)有分類標(biāo)簽的數(shù)據(jù)集，分為若干個(gè)簇的過(guò)程，是一種無(wú)監(jiān)督的分類方法[2]。實(shí)際上，很難對(duì)聚類下一個(gè)明確的定義。2001年，Everitt等[3]甚至指出提出聚類的正式定義不僅困難而且也沒(méi)有必要，因?yàn)榫垲惙治霰旧硎且环N建立在主觀判斷基礎(chǔ)上的相對(duì)行之有效的方法[4-5]。盡管如此，聚類分析還是表達(dá)了一般認(rèn)為的“類內(nèi)的相似性與類間的排他性”的目標(biāo)。Hansen等[6]也已經(jīng)作了數(shù)學(xué)上的闡述。給定一個(gè)數(shù)據(jù)樣本集：

聚類分析是伴隨著統(tǒng)計(jì)學(xué)、計(jì)算機(jī)學(xué)與人工智能等領(lǐng)域科學(xué)的發(fā)展而逐步發(fā)展起來(lái)的，為此，這些領(lǐng)域若有較大的研究進(jìn)展，必然促進(jìn)聚類分析算法的快速發(fā)展。比如機(jī)器學(xué)習(xí)領(lǐng)域的人工神經(jīng)網(wǎng)絡(luò)與支持向量機(jī)的發(fā)展就出現(xiàn)促生了基于神經(jīng)網(wǎng)絡(luò)的聚類方法與核聚類方法。目前，基于人工神經(jīng)網(wǎng)絡(luò)的深度學(xué)習(xí)（如：AlphaGo圍棋系統(tǒng)）也必將推動(dòng)聚類分析方法的進(jìn)一步發(fā)展。到目前為止，聚類研究及其應(yīng)用領(lǐng)域已經(jīng)非常廣泛，因此，本文主要以聚類分析算法為主要分析對(duì)象，兼論聚類分析的全過(guò)程。

關(guān)于聚類分析，《數(shù)據(jù)挖掘概念與技術(shù)（第二版）》一書(shū)中已經(jīng)有了經(jīng)典的論述。然而，聚類算法又有了長(zhǎng)足的發(fā)展與進(jìn)步。本文首先簡(jiǎn)要介紹了聚類分析的主要過(guò)程，然后分析并總結(jié)了樣本點(diǎn)之間的相似性度量方法，提出了聚類算法的新分類方式，并總結(jié)與分析了各種聚類算法，還對(duì)如何評(píng)價(jià)聚類結(jié)果作了過(guò)程分析。最后，依靠課題組承擔(dān)的醫(yī)療與海洋大數(shù)據(jù)的聚類分析研究[7-11]，展望了聚類算法的發(fā)展趨勢(shì)，作為本文的結(jié)語(yǔ)。

1 聚類分析過(guò)程

聚類分析是一個(gè)較為嚴(yán)密的數(shù)據(jù)分析過(guò)程。聚類分析的全過(guò)程如圖1所示，從聚類對(duì)象數(shù)據(jù)源開(kāi)始到得到聚類結(jié)果的知識(shí)存檔為止，其中主要包括四個(gè)部分研究?jī)?nèi)容，即特征選擇或變換、聚類算法選擇或設(shè)計(jì)、聚類結(jié)果評(píng)價(jià)與聚類結(jié)果物理解析等。

1.1 特征選擇或變換

一般情況下，樣本數(shù)據(jù)是雜亂無(wú)章的（特別是大數(shù)據(jù)時(shí)代），聚類分析首先需要進(jìn)行數(shù)據(jù)集的特征選擇或變換。實(shí)際上，特征選擇與特征變換是降維技術(shù)的兩大分類。特征選擇指的是從數(shù)據(jù)樣本集的所有特征（或稱屬性）中選擇更有利于達(dá)到某種目標(biāo)的若干屬性，即原始屬性集的一個(gè)子集，同時(shí)也達(dá)到了降低維度的目的;而特征變換則是指通過(guò)某種變換將原始輸入空間的屬性映射到一個(gè)新的特征空間，然后在特征空間中根據(jù)規(guī)則選擇某些較為重要的變換后的特征。由于特征選擇并不改變其原有屬性，所以結(jié)果只是一個(gè)原始屬性的優(yōu)化特征子集，保留了原屬性的物理意義，方便用戶理解;而特征變換的結(jié)果失去了原始特征的物理意義，但能夠提取其隱含的特征信息，移除原特征集屬性之間的相關(guān)性與冗余性。特征選擇或變換在聚類分析過(guò)程中占據(jù)極其重要的地位，結(jié)果的優(yōu)劣將直接影響最后的聚類效果，應(yīng)該引起足夠的重視。有時(shí)，特征選擇或變換后得到的有效模式（或稱子集）的作用甚至超過(guò)聚類算法本身的效用。

1.2 聚類算法選擇或設(shè)計(jì)

依據(jù)特征選擇或變換后的數(shù)據(jù)集特性，選擇或設(shè)計(jì)聚類算法，是聚類分析的第二部分研究?jī)?nèi)容。如果樣本集數(shù)據(jù)都是數(shù)值型數(shù)據(jù)，在選擇或者設(shè)計(jì)聚類算法時(shí)需要注意量綱不同的問(wèn)題。一般情況下，樣本集數(shù)據(jù)不一定都是數(shù)值型數(shù)據(jù)，因此，聚類算法需要有處理非數(shù)值型數(shù)據(jù)的能力。各個(gè)樣本點(diǎn)之間的相似性度量是聚類算法中的首要問(wèn)題。相似性度量與經(jīng)常提到的樣本間“距離”有著相同的意義，但是，它們的取值卻正好相反，即相似性度量值越大，“距離”越近。同樣，相似性度量也是聚類分析全過(guò)程中的關(guān)鍵問(wèn)題之一，將在后文進(jìn)行詳細(xì)的介紹與分析。

1.3 聚類結(jié)果評(píng)價(jià)與物理解析

聚類簇只能依靠聚類結(jié)束準(zhǔn)則函數(shù)得到[12]，需要特別指出的是，這種準(zhǔn)則函數(shù)一般由人為設(shè)定的終止條件實(shí)現(xiàn)，而這些終止條件并沒(méi)有統(tǒng)一的標(biāo)準(zhǔn)。由此可見(jiàn)聚類分析是一個(gè)主觀的歸類過(guò)程，所以在聚類簇生成以后，必須對(duì)聚類結(jié)果進(jìn)行綜合評(píng)價(jià)。聚類分析的本來(lái)目標(biāo)是得到特定數(shù)據(jù)集中隱含的數(shù)據(jù)結(jié)構(gòu)。更何況，對(duì)于同樣一個(gè)數(shù)據(jù)集，不同的聚類算法一般會(huì)得到不同的聚類簇。然而，對(duì)聚類結(jié)果作了評(píng)價(jià)之后，仍然不能改變聚類分析是“通過(guò)數(shù)據(jù)探索而生成假說(shuō)”的實(shí)質(zhì)，因此，最后需要對(duì)聚類結(jié)果作物理上的解析。

在聚類結(jié)果評(píng)價(jià)后一段較長(zhǎng)的時(shí)間內(nèi)，需要對(duì)一種或者幾種聚類結(jié)果假說(shuō)，總結(jié)出實(shí)際的物理意義。聚類簇的物理解析應(yīng)該與具有實(shí)際工作經(jīng)驗(yàn)的專家作深入的探討與分析。最后才可以將探討的結(jié)果加入到知識(shí)庫(kù)，作為進(jìn)一步研究的依據(jù)?？梢?jiàn)，聚類物理解析并不屬于學(xué)術(shù)研究的范疇，而是一個(gè)長(zhǎng)期的驗(yàn)證過(guò)程。

2 相似性度量

聚類分析是將數(shù)據(jù)集的相似性樣本歸為若干類的方法，因此，如何度量樣本之間的相似性是聚類算法的關(guān)鍵問(wèn)題。假設(shè)樣本間的相似性滿足對(duì)稱性、非負(fù)性和反身性，則稱樣本間的相似性具有可度量性（Metric）。另外，需要注意的是，三角不等式的半度量（SemiMetric）和超度量（UltraMetric）這兩種非可度量方式不在本文的探討范圍內(nèi)。數(shù)據(jù)集的特征一般分為三種：連續(xù)性變量（或稱定量型變量）、離散性變量（或稱定性型變量）和混合變量。相應(yīng)的，有三種相似性度量方法。

2.1 連續(xù)性變量的相似性度量

其中：D表示樣本之間的距離;l是樣本特征的維數(shù);d表示樣本的總維數(shù)（以下同），即樣本特征的總數(shù)量。D表示樣本之間的距離;Xi與Xj表示一個(gè)向量，或稱為樣本點(diǎn)或者樣本;l是樣本特征的維數(shù);xil與xjl表示一個(gè)變量，或稱為屬性;d表示樣本的總維數(shù)，即樣本特征的總數(shù)量（以下同）。歐氏距離是一種二范數(shù)形式，具有在特征空間中轉(zhuǎn)化和旋轉(zhuǎn)的不變性，一般趨向于構(gòu)建球形聚類簇。然而，屬性值相差較大或線性變換都會(huì)使相關(guān)性產(chǎn)生形變[13-14]。

為了解決這個(gè)問(wèn)題，需要標(biāo)準(zhǔn)化處理目標(biāo)數(shù)據(jù)集，使每一個(gè)屬性對(duì)距離的貢獻(xiàn)率相同，這也是消除特征之間量綱差異的常規(guī)方式。在進(jìn)行數(shù)據(jù)分析之前，需要對(duì)樣本集在均值與方差上作標(biāo)準(zhǔn)化處理[15]。標(biāo)準(zhǔn)化計(jì)算公式如下：

其中：m為均值;S為方差;*表示特征的原值（以下同）。另外，為了去掉不同屬性值間在量綱上的差別，需要對(duì)樣本集作正則化處理。例如在[0，1]區(qū)間內(nèi)的正則化公式為：

在二維空間中，切比雪夫距離的典型應(yīng)用是解決國(guó)際象棋中的國(guó)王從一個(gè)格子走到另一個(gè)格子最少需要幾步的問(wèn)題。這種距離在模糊C-Means方法[16-17]中得到了有效應(yīng)用。切比雪夫距離的公式可以表示為：

回復(fù)：需要修改文字說(shuō)明。最好在式（4）后面的文字說(shuō)明中做統(tǒng)一地修改。

原內(nèi)容為"其中：D表示樣本之間的距離;l是樣本特征的維數(shù);d表示樣本的總維數(shù)（以下同），即樣本特征的總數(shù)量。"現(xiàn)修改為"其中：D表示樣本之間的距離;Xi與Xj表示一個(gè)向量或稱為樣本點(diǎn)或者樣本;l是樣本特征的維數(shù);xil與xjl表示一個(gè)變量或稱為屬性;d表示樣本的總維數(shù)，即樣本特征的總數(shù)量（以下同）。"

另外，我們還發(fā)現(xiàn)了一個(gè)公式中的問(wèn)題。請(qǐng)將式（4）與式（8）中根號(hào)里的逗號(hào)改為減號(hào)，即將 （xil ， xjl）2改為（xil - xjl）2

此公式的另外一種表示形式為：

3）曼哈頓距離（Manhattan Distance）。

在城市中生活，只能沿著街道從一個(gè)地方到另一個(gè)地方，為此，人們將生活中熟悉的城市街區(qū)距離（City Block Distance）形象地稱為曼哈頓距離。該距離的計(jì)算公式為：

曼哈頓距離在基于自適應(yīng)諧振理論（Adaptive Resonance Theory， ART）的同步聚類（SYnchronization Clustering， SYC）中有較好的應(yīng)用;但是，需要注意的是這種距離不再符合在特征空間中轉(zhuǎn)化和旋轉(zhuǎn)的不變性。

4）閔可夫斯基距離（Minkowski Distance）。

閔可夫斯基距離是一種p范數(shù)的形式，公式可以表示為：

從式（10）可見(jiàn)：若p為無(wú)窮大時(shí)，這種距離可以稱為切比雪夫距離;若p=2時(shí)就是歐幾里得距離;那么當(dāng)p=1時(shí)，就是曼哈頓距離。

5）馬氏距離（Mahalanobis Distance）。

馬氏距離是一種關(guān)于協(xié)方差矩陣的距離度量表示方法，其公式為：

回復(fù)：需要修改文字說(shuō)明。其中Xi和Xj的問(wèn)題已經(jīng)在問(wèn)題（2）中統(tǒng)一做了說(shuō)明。

原內(nèi)容為"馬氏距離的優(yōu)點(diǎn)是距離與屬性的量綱無(wú)關(guān)，"現(xiàn)修改為"其中：T表示轉(zhuǎn)置，S為樣本協(xié)方差矩陣。馬氏距離的優(yōu)點(diǎn)是距離與屬性的量綱無(wú)關(guān)，"。

其中：T表示轉(zhuǎn)置，S為樣本協(xié)方差矩陣。馬氏距離的優(yōu)點(diǎn)是距離與屬性的量綱無(wú)關(guān)，

馬氏距離的優(yōu)點(diǎn)是距離與屬性的量綱無(wú)關(guān)，并排除了屬性之間的相關(guān)性干擾。若各個(gè)屬性之間獨(dú)立同分布，則協(xié)方差矩陣為單位矩陣。這樣，平方馬氏距離也就轉(zhuǎn)化為了歐氏距離[18-19]。