聚類演算法指南

02-02

Clustering: Introduction

什麼是聚類（Clustering）？
聚類可以被認為是無監督學習中最重要的問題。對於聚類中的每個其他問題，它在一個無標籤的集合中找出某種結構。對聚類的一個寬鬆一點的定義是「將在某些方面相似的成員對象那個組織到一組中的過程」。
由此可以看出，一個聚類是內部對象之間相似，不同聚類之間不同的對象集合。
我們可以通過下圖，清楚地表明這一點：

在上圖中，我們可以輕鬆地分辨出可以分為四類。相似度的度量標準在這裡是兩點之間的距離。兩個或更多的點在它們距離接近的時候被分為一類，這叫做「基於距離的聚類」。
另一種聚類方法是「概念聚類」：將兩個或以上概念相同的對象分為一類。換句話說，對象是根據它們是否符合某個描述性的概念來分類的，而不是其他簡單地相似性度量。
聚類的目標是什麼？
聚類的目標是確定一個無標籤集合的內在分組。但是應該怎樣產出一個好的聚類效果呢？實驗表明，沒有絕對意義的獨立於聚類的最終目標的最好的評判標準。因此，一般是用戶來決定那個判斷標準最符合他們的需要。
例如，我們想從同質的分組中選擇具有代表性的分組（data reduction），或者想找出「自然聚類natural clusters」並描述它們未知的屬性（「natural」 data types），或者想找到有用併合適的分組（「useful」 data classes），或者想找出不尋常的數據對象（異類檢測outlier detection）

可以應用在哪些方面？
聚類演算法可以被應用在很多方面，比如：
- Marketing：從一個包含用戶的屬性、購買記錄等信息的大的用戶資料庫中找到行為相似的一組顧客
- Biology：給定動植物的特徵，據此對它們進行分類
- Libraries：書籍分組
- Insurance：識別詐騙、確定具有較高平均理賠費用的汽車保險單的持有人群體
- City-Planning：根據房屋類型、價值、地理位置對房屋進行分組
- Earthquake studies：對已觀測到的地震進行分組，用於識別危險區域
- WWW：文檔分類、網頁日誌數據自動聚類用以發現相似獲取模式的分組

對聚類演算法的要求有哪些？
- scalability(可擴展性)
- dealing with different types of attributes
- discovering clusters with arbitrary shape
- minimal requirements for domain knowledge to determine input parameters
- ability to deal with noise and outliers
- high dimensionality
- interpretability and usability

聚類演算法目前存在哪些問題：？
- 目前的聚類演算法還沒能同時合適的滿足上述要求
- 由於時間複雜度，處理大量或者高維數據會非常棘手
- 對於基於距離的分類演算法來說，分類效果很大程度上依賴於我們如何定義「距離」
- 如果不存現明顯的「距離」度量，我們必須自己定義一個，這並不不是很容易的一件事，尤其是在高維空間中
- 聚類演算法的結果（在很多情況下結果會波動）能以不同的方式進行解釋

Clustering Algorithms

聚類演算法的分類有哪些？
- Exclusive Clustering
- Overlapping Clustering
- Hierarchical Clustering
- Probabilistic Clustering
在第一類中，數據被分成互斥的分組，因此如果某個數據屬於分組A，那它就不可能再被分為其他分組。下圖是一個簡單地例子，下圖在一個二維平面中用一根直線將數據分為了兩組。
與此對比，第二類「重疊聚類」使用冗餘的數據集來對數據進行分組，因此某個數據點可能給予不同的程度既屬於A又屬於B，在這種情況下，數據會被關聯上一個合適的「成員程度值」（membership value）

第三類：層次聚類演算法是基於兩個最接近的集群的union的。開始條件是將所有的數據點都看作是一個cluster，迭代一定次數之後，我們就會得到我們想要的結果了。
最後一類聚類方法使用的是完全的概率方法。

在本文中，我會介紹四中最常用的聚類演算法：

K-Means
Fuzzy C-Means
Hierarchical Clustering
Mixture of Gaussians

上面的四個演算法每一個都屬於上面介紹的四類中的一個，按順序一一對應。

距離度量
聚類演算法的一個重要部分是數據點之間的距離測量方法。如果數據實例向量的哥哥component都在同一個物理單位下，使用歐氏距離就足夠正確的對它們進行聚類了。然而，即使在這種情況下，歐氏距離也可能會產生誤導。下圖揭示了這種case：下圖表示的是一個object的width和height，儘管他們的單位相同，對於相關的比例，我們還需要做出正確的決定。如下如所示，不同的scaling會產生不同的聚類效果。

但是請注意，這不僅是一個圖形的問題：這個問題由用於所述數據的特徵向量的單一組件之間的距離結合成可用於群集目的的唯一距離量度的數學公式產生：不同的公式導致不同的聚類。

再次，針對每一特定應用，領域知識必須用於引導一個合適的距離度量。

tMinkowski Metric

t對於高維數據來說，一種流行的度量是Minkowski metric：

td表示數據的維度，p=2是，公式退化為歐氏距離。p=1時，退化為Manhattan metric。需要指出的是，如何針對一個具體應用選擇度量標準並沒有一個統一的準則。一切取決於你的需要。

t在很多情況下，數據特徵向量的哥哥成分之間並不是直接可比的。它們可能是不連續的值而是標稱值，比如長度或者一周的某一天。在這些情況下，我們就需要相應的domain knowledge來制定一個合適的measure。

Biography

Tariq Rashid: 「Clustering」http://www.cs.bris.ac.uk/home/tr1690/documentation/fuzzy_clustering_initial_report/node11.html
Osmar R. Za?ane: 「Principles of Knowledge Discovery in Databases - Chapter 8: Data Clustering」http://www.cs.ualberta.ca/~zaiane/courses/cmput690/slides/Chapter8/index.html
Pier Luca Lanzi: 「Ingegneria della Conoscenza e Sistemi Esperti – Lezione 2: Apprendimento non supervisionato」Redirect