聚類算法

俗話説：“物以類聚，人以羣分”，在自然科學和社會科學中，存在着大量的分類問題。所謂類，通俗地説，就是指相似元素的集合。

聚類分析起源於分類學，在古老的分類學中，人們主要依靠經驗和專業知識來實現分類，很少利用數學工具進行定量的分類。隨着人類科學技術的發展，對分類的要求越來越高，以致有時僅憑經驗和專業知識難以確切地進行分類，於是人們逐漸地把數學工具引用到了分類學中，形成了數值分類學，之後又將多元分析的技術引入到數值分類學形成了聚類分析。聚類分析內容非常豐富，有系統聚類法、有序樣品聚類法、動態聚類法、模糊聚類法、圖論聚類法、聚類預報法等。

聚類的用途是很廣泛的。

在商業上，聚類可以幫助市場分析人員從消費者數據庫中區分出不同的消費羣體來，並且概括出每一類消費者的消費模式或者説習慣。它作為數據挖掘中的一個模塊，可以作為一個單獨的工具以發現數據庫中分佈的一些深層的信息，並且概括出每一類的特點，或者把注意力放在某一個特定的類上以作進一步的分析；並且，聚類分析也可以作為數據挖掘算法中其他分析算法的一個預處理步驟。

聚類分析的算法可以分為劃分法（Partitioning Methods）、層次法（Hierarchical Methods）、基於密度的方法（density-based methods）、基於網格的方法（grid-based methods）、基於模型的方法（Model-Based Methods）。

許多聚類算法在小於 200 個數據對象的小數據集合上工作得很好；但是，一個大規模數據庫可能包含幾百萬個對象，在這樣的大數據集合樣本上進行聚類可能會導致有偏的結果。

我們需要具有高度可伸縮性的聚類算法。

許多算法被設計用來聚類數值類型的數據。但是，應用可能要求聚類其他類型的數據，如二元類型(binary)，分類/標稱類型（categorical/nominal），序數型（ordinal）數據，或者這些數據類型的混合。

許多聚類算法基於歐幾里得或者曼哈頓距離度量來決定聚類。基於這樣的距離度量的算法趨向於發現具有相近尺度和密度的球狀簇。但是，一個簇可能是任意形狀的。提出能發現任意形狀簇的算法是很重要的。

許多聚類算法在聚類分析中要求用户輸入一定的參數，例如希望產生的簇的數目。聚類結果對於輸入參數十分敏感。參數通常很難確定，特別是對於包含高維對象的數據集來説。這樣不僅加重了用户的負擔，也使得聚類的質量難以控制。

絕大多數現實中的數據庫都包含了孤立點，缺失，或者錯誤的數據。一些聚類算法對於這樣的數據敏感，可能導致低質量的聚類結果。

一些聚類算法對於輸入數據的順序是敏感的。例如，同一個數據集合，當以不同的順序交給同一個算法時，可能生成差別很大的聚類結果。開發對數據輸入順序不敏感的算法具有重要的意義。

一個數據庫或者數據倉庫可能包含若干維或者屬性。許多聚類算法擅長處理低維的數據，可能只涉及兩到三維。人類的眼睛在最多三維的情況下能夠很好地判斷聚類的質量。在高維空間中聚類數據對象是非常有挑戰性的，特別是考慮到這樣的數據可能分佈非常稀疏，而且高度偏斜。

現實世界的應用可能需要在各種約束條件下進行聚類。假設你的工作是在一個城市中為給定數目的自動提款機選擇安放位置，為了作出決定，你可以對住宅區進行聚類，同時考慮如城市的河流和公路網，每個地區的客户要求等情況。要找到既滿足特定的約束，又具有良好聚類特性的數據分組是一項具有挑戰性的任務。

用户希望聚類結果是可解釋的，可理解的，和可用的。也就是説，聚類可能需要和特定的語義解釋和應用相聯繫。應用目標如何影響聚類方法的選擇也是一個重要的研究課題。

記住這些約束，我們對聚類分析的學習將按如下的步驟進行。首先，學習不同類型的數據，以及它們對聚類方法的影響。接着，給出了一個聚類方法的一般分類。然後我們詳細地討論了各種聚類方法，包括劃分方法，層次方法，基於密度的方法，基於網格的方法，以及基於模型的方法。最後我們探討在高維空間中的聚類和孤立點分析（outlier analysis）。

很難對聚類方法提出一個簡潔的分類，因為這些類別可能重疊，從而使得一種方法具有幾類的特徵，儘管如此，對於各種不同的聚類方法提供一個相對有組織的描述依然是有用的，為聚類分析計算方法主要有如下幾種：

劃分法(partitioning methods)，給定一個有N個元組或者紀錄的數據集，分裂法將構造K個分組，每一個分組就代表一個聚類，K<N。而且這K個分組滿足下列條件：

（1） 每一個分組至少包含一個數據紀錄；

（2）每一個數據紀錄屬於且僅屬於一個分組（注意：這個要求在某些模糊聚類算法中可以放寬）；

對於給定的K，算法首先給出一個初始的分組方法，以後通過反覆迭代的方法改變分組，使得每一次改進之後的分組方案都較前一次好，而所謂好的標準就是：同一分組中的記錄越近越好，而不同分組中的紀錄越遠越好。

大部分劃分方法是基於距離的。給定要構建的分區數k，劃分方法首先創建一個初始化劃分。然後，它採用一種迭代的重定位技術，通過把對象從一個組移動到另一個組來進行劃分。一個好的劃分的一般準備是：同一個簇中的對象儘可能相互接近或相關，而不同的簇中的對象儘可能遠離或不同。還有許多評判劃分質量的其他準則。傳統的劃分方法可以擴展到子空間聚類，而不是搜索整個數據空間。當存在很多屬性並且數據稀疏時，這是有用的。為了達到全局最優，基於劃分的聚類可能需要窮舉所有可能的劃分，計算量極大。實際上，大多數應用都採用了流行的啓發式方法，如k-均值和k-中心算法，漸近的提高聚類質量，逼近局部最優解。這些啓發式聚類方法很適合發現中小規模的數據庫中小規模的數據庫中的球狀簇。為了發現具有複雜形狀的簇和對超大型數據集進行聚類，需要進一步擴展基於劃分的方法。 ^[1] 

使用這個基本思想的算法有：K-MEANS算法、K-MEDOIDS算法、CLARANS算法；

層次法(hierarchical methods)，這種方法對給定的數據集進行層次似的分解，直到某種條件滿足為止。具體又可分為“自底向上”和“自頂向下”兩種方案。

例如，在“自底向上”方案中，初始時每一個數據紀錄都組成一個單獨的組，在接下來的迭代中，它把那些相互鄰近的組合併成一個組，直到所有的記錄組成一個分組或者某個條件滿足為止。

層次聚類方法可以是基於距離的或基於密度或連通性的。層次聚類方法的一些擴展也考慮了子空間聚類。層次方法的缺陷在於，一旦一個步驟（合併或分裂）完成，它就不能被撤銷。這個嚴格規定是有用的，因為不用擔心不同選擇的組合數目，它將產生較小的計算開銷。然而這種技術不能更正錯誤的決定。已經提出了一些提高層次聚類質量的方法。 ^[1] 

代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等；

基於密度的方法(density-based methods)，基於密度的方法與其它方法的一個根本區別是：它不是基於各種各樣的距離的，而是基於密度的。這樣就能克服基於距離的算法只能發現“類圓形”的聚類的缺點。

這個方法的指導思想就是，只要一個區域中的點的密度大過某個閾值，就把它加到與之相近的聚類中去。

代表算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等；

圖論聚類方法解決的第一步是建立與問題相適應的圖，圖的節點對應於被分析數據的最小單元，圖的邊（或弧）對應於最小處理單元數據之間的相似性度量。因此，每一個最小處理單元數據之間都會有一個度量表達，這就確保了數據的局部特性比較易於處理。圖論聚類法是以樣本數據的局域連接特徵作為聚類的主要信息源，因而其主要優點是易於處理局部數據的特性。

基於網格的方法(grid-based methods)，這種方法首先將數據空間劃分成為有限個單元（cell）的網格結構,所有的處理都是以單個的單元為對象的。這麼處理的一個突出的優點就是處理速度很快，通常這是與目標數據庫中記錄的個數無關的，它只與把數據空間分為多少個單元有關。

代表算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法；

基於模型的方法(model-based methods)，基於模型的方法給每一個聚類假定一個模型，然後去尋找能夠很好的滿足這個模型的數據集。這樣一個模型可能是數據點在空間中的密度分佈函數或者其它。它的一個潛在的假定就是：目標數據集是由一系列的概率分佈所決定的。

通常有兩種嘗試方向：統計的方案和神經網絡的方案。

k-means 算法接受輸入量 k ；然後將n個數據對象劃分為 k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個“中心對象”（引力中心）來進行計算的。

k-means 算法的工作過程説明如下：

首先從n個數據對象任意選擇 k 個對象作為初始聚類中心；而對於所剩下其它對象，則根據它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；

然後再計算每個所獲新聚類的聚類中心（該聚類中所有對象的均值）；不斷重複這一過程直到標準測度函數開始收斂為止。

一般都採用均方差作為標準測度函數. k個聚類具有以下特點：各聚類本身儘可能的緊湊，而各聚類之間儘可能的分開。

K-MEANS有其缺點：產生類的大小相差不會很大，對於髒數據很敏感。

改進的算法：k—medoids 方法。這兒選取一個對象叫做mediod來代替上面的中心的作用，這樣的一個medoid就標識了這個類。K-medoids和K-means不一樣的地方在於中心點的選取，在K-means中，我們將中心點取為當前cluster中所有數據點的平均值，在 K-medoids算法中，我們將從當前cluster 中選取這樣一個點——它到其他所有（當前cluster中的）點的距離之和最小——作為中心點。 ^[2] 

步驟：

1，任意選取K個對象作為medoids（O1,O2,…Oi…Ok）。

以下是循環的：

2，將餘下的對象分到各個類中去（根據與medoid最相近的原則）；

3，對於每個類（Oi）中，順序選取一個Or，計算用Or代替Oi後的消耗—E（Or）。選擇E最小的那個Or來代替Oi。這樣K個medoids就改變了，下面就再轉到2。

4，這樣循環直到K個medoids固定下來。

這種算法對於髒數據和異常數據不敏感，但計算量顯然要比K均值要大，一般只適合小數據量。

上面提到K-medoids算法不適合於大數據量的計算。Clara算法，這是一種基於採樣的方法，它能夠處理大量的數據。

Clara算法的思想就是用實際數據的抽樣來代替整個數據，然後再在這些抽樣的數據上利用K-medoids算法得到最佳的medoids。Clara算法從實際數據中抽取多個採樣，在每個採樣上都用K-medoids算法得到相應的（O1, O2 … Oi … Ok），然後在這當中選取E最小的一個作為最終的結果。

Clara算法的效率取決於採樣的大小，一般不太可能得到最佳的結果。

在Clara算法的基礎上，又提出了Clarans的算法，與Clara算法不同的是：在Clara算法尋找最佳的medoids的過程中，採樣都是不變的。而Clarans算法在每一次循環的過程中所採用的採樣都是不一樣的。

與上面所講的尋找最佳medoids的過程不同的是，必須人為地來限定循環的次數。