章永來 周耀鑒

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

關鍵詞：聚類;相似性度量;大數據聚類;小數據聚類;聚類評價

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 引言

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

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

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

1 聚類分析過程

聚類分析是一個較為嚴密的數據分析過程。聚類分析的全過程如圖1所示，從聚類對象數據源開始到得到聚類結果的知識存檔為止，其中主要包括四個部分研究內容，即特征選擇或變換、聚類算法選擇或設計、聚類結果評價與聚類結果物理解析等。

1.1 特征選擇或變換

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

1.2 聚類算法選擇或設計

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

1.3 聚類結果評價與物理解析

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

在聚類結果評價后一段較長的時間內，需要對一種或者幾種聚類結果假說，總結出實際的物理意義。聚類簇的物理解析應該與具有實際工作經驗的專家作深入的探討與分析。最后才可以將探討的結果加入到知識庫，作為進一步研究的依據?？梢?，聚類物理解析并不屬于學術研究的范疇，而是一個長期的驗證過程。

2 相似性度量

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

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

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

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

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

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

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

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

另外，我們還發(fā)現了一個公式中的問題。請將式（4）與式（8）中根號里的逗號改為減號，即將 （xil ， xjl）2改為（xil - xjl）2

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

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

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

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

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

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

從式（10）可見：若p為無窮大時，這種距離可以稱為切比雪夫距離;若p=2時就是歐幾里得距離;那么當p=1時，就是曼哈頓距離。

5）馬氏距離（Mahalanobis Distance）。

馬氏距離是一種關于協方差矩陣的距離度量表示方法，其公式為：

回復：需要修改文字說明。其中Xi和Xj的問題已經在問題（2）中統(tǒng)一做了說明。

原內容為"馬氏距離的優(yōu)點是距離與屬性的量綱無關，"現修改為"其中：T表示轉置，S為樣本協方差矩陣。馬氏距離的優(yōu)點是距離與屬性的量綱無關，"。

其中：T表示轉置，S為樣本協方差矩陣。馬氏距離的優(yōu)點是距離與屬性的量綱無關，

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