單聚類演算法

A. 聚類的計算方法

傳統的聚類分析計算方法主要有如下幾種：
1、劃分方法(partitioning methods)
給定一個有N個元組或者紀錄的數據集，分裂法將構造K個分組，每一個分組就代表一個聚類，K<N。而且這K個分組滿足下列條件：（1） 每一個分組至少包含一個數據紀錄；（2）每一個數據紀錄屬於且僅屬於一個分組（注意：這個要求在某些模糊聚類演算法中可以放寬）；對於給定的K，演算法首先給出一個初始的分組方法，以後通過反復迭代的方法改變分組，使得每一次改進之後的分組方案都較前一次好，而所謂好的標准就是：同一分組中的記錄越近越好，而不同分組中的紀錄越遠越好。使用這個基本思想的演算法有：K-MEANS演算法、K-MEDOIDS演算法、CLARANS演算法；
大部分劃分方法是基於距離的。給定要構建的分區數k，劃分方法首先創建一個初始化劃分。然後，它採用一種迭代的重定位技術，通過把對象從一個組移動到另一個組來進行劃分。一個好的劃分的一般准備是：同一個簇中的對象盡可能相互接近或相關，而不同的簇中的對象盡可能遠離或不同。還有許多評判劃分質量的其他准則。傳統的劃分方法可以擴展到子空間聚類，而不是搜索整個數據空間。當存在很多屬性並且數據稀疏時，這是有用的。為了達到全局最優，基於劃分的聚類可能需要窮舉所有可能的劃分，計算量極大。實際上，大多數應用都採用了流行的啟發式方法，如k-均值和k-中心演算法，漸近的提高聚類質量，逼近局部最優解。這些啟發式聚類方法很適合發現中小規模的資料庫中小規模的資料庫中的球狀簇。為了發現具有復雜形狀的簇和對超大型數據集進行聚類，需要進一步擴展基於劃分的方法。
2、層次方法(hierarchical methods)
這種方法對給定的數據集進行層次似的分解，直到某種條件滿足為止。具體又可分為「自底向上」和「自頂向下」兩種方案。例如在「自底向上」方案中，初始時每一個數據紀錄都組成一個單獨的組，在接下來的迭代中，它把那些相互鄰近的組合並成一個組，直到所有的記錄組成一個分組或者某個條件滿足為止。代表演算法有：BIRCH演算法、CURE演算法、CHAMELEON演算法等；
層次聚類方法可以是基於距離的或基於密度或連通性的。層次聚類方法的一些擴展也考慮了子空間聚類。層次方法的缺陷在於，一旦一個步驟（合並或分裂）完成，它就不能被撤銷。這個嚴格規定是有用的，因為不用擔心不同選擇的組合數目，它將產生較小的計算開銷。然而這種技術不能更正錯誤的決定。已經提出了一些提高層次聚類質量的方法。
3、基於密度的方法(density-based methods)
基於密度的方法與其它方法的一個根本區別是：它不是基於各種各樣的距離的，而是基於密度的。這樣就能克服基於距離的演算法只能發現「類圓形」的聚類的缺點。這個方法的指導思想就是，只要一個區域中的點的密度大過某個閥值，就把它加到與之相近的聚類中去。代表演算法有：DBSCAN演算法、OPTICS演算法、DENCLUE演算法等；
4、基於網格的方法(grid-based methods)
這種方法首先將數據空間劃分成為有限個單元（cell）的網格結構,所有的處理都是以單個的單元為對象的。這么處理的一個突出的優點就是處理速度很快，通常這是與目標資料庫中記錄的個數無關的，它只與把數據空間分為多少個單元有關。代表演算法有：STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法；
很多空間數據挖掘問題，使用網格通常都是一種有效的方法。因此，基於網格的方法可以和其他聚類方法集成。
5、基於模型的方法(model-based methods)
基於模型的方法給每一個聚類假定一個模型，然後去尋找能夠很好的滿足這個模型的數據集。這樣一個模型可能是數據點在空間中的密度分布函數或者其它。它的一個潛在的假定就是：目標數據集是由一系列的概率分布所決定的。通常有兩種嘗試方向：統計的方案和神經網路的方案。
當然聚類方法還有：傳遞閉包法，布爾矩陣法，直接聚類法，相關性分析聚類，基於統計的聚類方法等。

B. 常用的聚類方法有哪幾種

聚類分析的演算法可以分為劃分法、層次法、基於密度的方法、基於網格的方法、基於模型的方法。

1、劃分法，給定一個有N個元組或者紀錄的數據集，分裂法將構造K個分組，每一個分組就代表一個聚類，K<N。

2、層次法，這種方法對給定的數據集進行層次似的分解，直到某種條件滿足為止。

3、基於密度的方法，基於密度的方法與其它方法的一個根本區別是：它不是基於各種各樣的距離的，而是基於密度的。這樣就能克服基於距離的演算法只能發現「類圓形」的聚類的缺點。

4、圖論聚類方法解決的第一步是建立與問題相適應的圖，圖的節點對應於被分析數據的最小單元，圖的邊（或弧）對應於最小處理單元數據之間的相似性度量。

5、基於網格的方法，這種方法首先將數據空間劃分成為有限個單元的網格結構,所有的處理都是以單個的單元為對象的。

6、基於模型的方法，基於模型的方法給每一個聚類假定一個模型，然後去尋找能夠很好的滿足這個模型的數據集。

(2)單聚類演算法擴展閱讀：

在商業上，聚類可以幫助市場分析人員從消費者資料庫中區分出不同的消費群體來，並且概括出每一類消費者的消費模式或者說習慣。

它作為數據挖掘中的一個模塊，可以作為一個單獨的工具以發現資料庫中分布的一些深層的信息，並且概括出每一類的特點，或者把注意力放在某一個特定的類上以作進一步的分析；並且，聚類分析也可以作為數據挖掘演算法中其他分析演算法的一個預處理步驟。

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

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

C. 聚類演算法--DBSCAN

       DBSCAN(Density-Based Spatial Clustering of Applications with Noise，具有雜訊的基於密度的聚類方法)是一種很典型的密度聚類演算法，和K-Means，BIRCH這些一般只適用於凸樣本集的聚類相比，DBSCAN既可以適用於凸樣本集，也可以適用於非凸樣本集。 基於密度的帶有雜訊的空間聚類，可用於異常值監測，通俗來說就是基於密度的聚類演算法 ！

        聚類就是對大量未知標注的數據集，按數據的內在相似性將數據集劃分為多個類別，使類別內的數據相似度較大而類別間的數據相似度較小。聚類演算法是無監督的演算法。

DBSCAN演算法的目的： 是基於密度尋找被低密度區域分離的高密度樣本分為三類： 

稠密區域內部的點（核心點）： 在半徑Eps內含有超過MinPts數目的點 

稠密區域邊緣上的點（邊緣點）： 在半徑Eps內點的數量小於MinPts（即不是核心點），但是其鄰域內至少包含一個核心點 

稀疏區域中的點（雜訊或者背景點）： 任何不是核心點或者邊界點的點

特點 ： 發現任意形狀的簇、對雜訊數據不敏感、一次掃描、需要密度參數作為停止條件，計算量大和復雜度高 。

    DBSCAN是一種基於密度的聚類演算法，這類密度聚類演算法一般假定類別可以通過樣本分布的緊密程度決定。同一類別的樣本，他們之間的緊密相連的，也就是說，在該類別任意樣本周圍不遠處一定有同類別的樣本存在。

    通過將緊密相連的樣本劃為一類，這樣就得到了一個聚類類別。通過將所有各組緊密相連的樣本劃為各個不同的類別，則我們就得到了最終的所有聚類類別結果。

    前面我們定性描述了密度聚類的基本思想，在這里我們就看看DBSCAN是如何描述密度聚類的。DBSCAN是基於一組鄰域來描述樣本集的緊密程度的，參數(ϵϵ, MinPts)用來描述鄰域的樣本分布緊密程度。其中，ϵϵ描述了某一樣本的鄰域距離閾值，MinPts描述了某一樣本的距離為ϵϵ的鄰域中樣本個數的閾值。

    假設我們的樣本集是D=(x1,x2,...,xm)(x1,x2,...,xm)，則DBSCAN具體的密度描述定義如下：

        1） ϵϵ-鄰域：對於xj∈Dxj∈D，其ϵϵ-鄰域包含樣本集D中與xjxj的距離不大於ϵϵ的子樣本集，即Nϵ(xj)={xi∈D|distance(xi,xj)≤ϵ}Nϵ(xj)={xi∈D|distance(xi,xj)≤ϵ}, 這個子樣本集的個數記為|Nϵ(xj)||Nϵ(xj)|

        2）核心對象：對於任一樣本xj∈Dxj∈D，如果其ϵϵ-鄰域對應的Nϵ(xj)Nϵ(xj)至少包含MinPts個樣本，即如果|Nϵ(xj)|≥MinPts|Nϵ(xj)|≥MinPts，則xjxj是核心對象。

        3）密度直達：如果xixi位於xjxj的ϵϵ-鄰域中，且xjxj是核心對象，則稱xixi由xjxj密度直達。注意反之不一定成立，即此時不能說xjxj由xixi密度直達, 除非且xixi也是核心對象。

        4）密度可達：對於xixi和xjxj,如果存在樣本樣本序列p1,p2,...,pTp1,p2,...,pT,滿p1=xi,pT=xjp1=xi,pT=xj, 且pt+1pt+1由ptpt密度直達，則稱xjxj由xixi密度可達。也就是說，密度可達滿足傳遞性。此時序列中的傳遞樣本p1,p2,...,pT−1p1,p2,...,pT−1均為核心對象，因為只有核心對象才能使其他樣本密度直達。注意密度可達也不滿足對稱性，這個可以由密度直達的不對稱性得出。

       5）密度相連：對於xixi和xjxj,如果存在核心對象樣本xkxk，使xixi和xjxj均由xkxk密度可達，則稱xixi和xjxj密度相連。注意密度相連關系是滿足對稱性的。

從下圖可以很容易看出理解上述定義，圖中MinPts=5，紅色的點都是核心對象，因為其ϵϵ-鄰域至少有5個樣本。黑色的樣本是非核心對象。所有核心對象密度直達的樣本在以紅色核心對象為中心的超球體內，如果不在超球體內，則不能密度直達。圖中用綠色箭頭連起來的核心對象組成了密度可達的樣本序列。在這些密度可達的樣本序列的ϵϵ-鄰域內所有的樣本相互都是密度相連的。

    DBSCAN的聚類定義很簡單： 由密度可達關系導出的最大密度相連的樣本集合，即為我們最終聚類的一個類別，或者說一個簇 。

    這個DBSCAN的簇裡面可以有一個或者多個核心對象。如果只有一個核心對象，則簇裡面其他的非核心對象樣本都在這個核心對象的ϵϵ-鄰域里；如果有多個核心對象，則簇里的任意一個核心對象的ϵϵ-鄰域中一定有一個其他的核心對象，否則這個核心對象無法密度可達。這些核心對象的ϵϵ-鄰域里所有的樣本的集合組成的一個DBSCAN聚類簇。

       那麼怎麼才能找到這樣的簇樣本集合呢？DBSCAN使用的方法很簡單，它任意選擇一個沒有類別的核心對象作為種子，然後找到所有這個核心對象能夠密度可達的樣本集合，即為一個聚類簇。接著繼續選擇另一個沒有類別的核心對象去尋找密度可達的樣本集合，這樣就得到另一個聚類簇。一直運行到所有核心對象都有類別為止。基本上這就是DBSCAN演算法的主要內容了，但是我們還有三個問題沒有考慮。

    1）一些異常樣本點或者說少量游離於簇外的樣本點，這些點不在任何一個核心對象的周圍，在DBSCAN中，我們一般將這些樣本點標記為噪音點。

    2）距離的度量問題，即如何計算某樣本和核心對象樣本的距離。在DBSCAN中，一般採用最近鄰思想，採用某一種距離度量來衡量樣本距離，比如歐式距離。這和KNN分類演算法的最近鄰思想完全相同。對應少量的樣本，尋找最近鄰可以直接去計算所有樣本的距離，比如樣本量較大，則一般採用KD樹或者球樹來快速的搜索最近鄰。

    3）某些樣本可能到兩個核心對象的距離都小於ϵϵ，但是這兩個核心對象由於不是密度直達，又不屬於同一個聚類簇，那麼如何界定這個樣本的類別呢？一般來說，此時DBSCAN採用先來後到，先進行聚類的類別簇會標記這個樣本為它的類別。也就是說DBSCAN的演算法不是完全穩定的演算法。

DBSCAN通過檢查數據集中的每個對象的ε-鄰域來尋找聚類，如果一個點p的ε-鄰域包含對於m個對象，則創建一個p作為核心對象的新簇。然後，DBSCAN反復地定址這些核心對象直接密度可達的對象，這個過程可能涉及密度可達簇的合並。當沒有新的點可以被添加到任何簇時，該過程結束。演算法中的ε和m是根據先驗只是來給出的。

DBSCAN聚類演算法原理的基本要點：

    1.DBSCAN演算法需要選擇一種距離度量，對於待聚類的數據集中，任意兩個點之間的距離，反應了點之間的密度，說明了點與點是否能夠聚到同一類中。由於DBSCAN演算法對高維數據定義密度很困難，所以對於二維空間中的點，可以使用歐幾里得距離來進行度量。

    2.DBSCAN演算法需要用戶輸入2個參數： 一個參數是半徑(Eps)，表示以給定點P為中心的圓形鄰域的范圍；另一個參數是以點P為中心的鄰域內最少點的數量(MinPts)。如果滿足：以點P為中心、半徑為Eps的鄰域內的點的個數不少於MinPts，則稱點P為核心點 。

    3.DBSCAN聚類聚類使用到一個 k-距離 的概念，k-距離是指：給定數據集P={p(i); i=0,1,……n},對於任意點P(i)，計算點P(i)到集合D的子集S={p(1), p(2), …, p(i-1), p(i+1), …, p(n)}中 所有點之間的距離 ， 距離按照從小到大的順序排序 ，假設排序後的距離集合為D={d(1), d(2), …, d(k-1), d(k), d(k+1), …,d(n)}， 則d(k)就被稱為k-距離 。也就是說， k-距離是點p(i)到所有點(除了p(i)點)之間距離第K近的距離 。對待聚類集合中 每個點p(i)都計算k-距離，最後得到所有點的k-距離集合E={e(1), e(2), …, e(n)} 。

    4.根據經驗計算半徑Eps：根據得到的所有點的 k-距離集合E ，對集合E進行 升序排序 後得到k-距離集合 E' ，需要擬合一條排序後的E'集合中k-距離的變化曲線圖，然後繪出曲線，通過觀察， 將急劇發生變化的位置所對應的k-距離的值，確定為半徑Eps的值 。

    5.根據經驗計算最少點的數量MinPts： 確定MinPts的大小，實際上也是確定k-距離中k的值 ，DBSCAN演算法中取k=4，則MinPts=4。

    6.另外，如果覺得經驗值聚類的結果不滿意，可以適當調整Eps和MinPts的值，經過多次迭代計算對比，選擇最合適的參數值。可以看出，如果MinPts不變。Eps取得值過大，會導致大多數點都聚到同一個簇中，Eps過小，會導致一個簇的分裂；如果Eps不變，MinPts的值取得過大，會導致同一個簇中點被標記為離群點，MinPts過小，會導致發現大量的核心點。

我們需要知道的是，DBSCAN演算法，需要輸入2個參數，這兩個參數的計算都來自經驗知識。半徑Eps的計算依賴於計算k-距離，DBSCAN取k=4，也就是設置MinPts=4，然後需要根據k-距離曲線，根據經驗觀察找到合適的半徑Eps的值，下面的演算法實現過程中，我們會詳細說明。

對於演算法的實現，我們概要地描述一下實現的過程：

    1.解析樣本數據文件。

    2.計算每個點與其他所有點之間的歐幾里得距離。

    3.計算每個點的k-距離值，並對所有點的k-距離集合進行升序排序，輸出的排序後的k-距離值。

    4.將所有點的k-距離值，在Excel中用散點圖顯示k-距離變化趨勢

    5.根據散點圖確定半徑Eps的值

    6.根據給定MinPts=4，以及半徑Eps的值，計算所有核心點，並建立核心點與核心點距離小於半徑Eps的點映射。

    7.根據得到的核心點集合，以及半徑Eps的值，計算能夠連通的核心點，並得到離群點。

    8.將能夠連通的每一組核心點，以及到核心點距離小於半徑Eps的點，都放到一起，形成一個簇。

    9.選擇不同的半徑Eps，使用DBSCAN演算法聚類得到的一組簇及其離群點，使用散點圖對比聚類效果。

    和傳統的K-Means演算法相比，DBSCAN最大的不同就是不需要輸入類別數K，當然它最大的優勢是可以發現任意形狀的聚類簇，而不是像K-Means，一般僅僅使用於凸的樣本集聚類。同時它在聚類的同時還可以找出異常點，這點和BIRCH演算法類似。

    那麼我們什麼時候需要用DBSCAN來聚類呢？一般來說，如果數據集是稠密的，並且數據集不是凸的，那麼用DBSCAN會比K-Means聚類效果好很多。 如果數據集不是稠密的，則不推薦用DBSCAN來聚類 。

    優點：

        1）可以對任意形狀的稠密數據集進行聚類，相對的，K-Means之類的聚類演算法一般只適用於凸數據集。不用指明類別的數量，能靈活找到並分離各種形狀和大小的類。能很好地處理雜訊和離群點。

        2）可以在聚類的同時發現異常點，對數據集中的異常點不敏感。

        3）聚類結果沒有偏倚，相對的，K-Means之類的聚類演算法初始值對聚類結果有很大影響。

    缺點：

         1）在不同密度的類方面有一定難度。如果樣本集的密度不均勻、聚類間距差相差很大時，聚類質量較差，這時用DBSCAN聚類一般不適合( HDBSCAN適合密度不均勻問題 )。

        2）如果樣本集較大時，聚類收斂時間較長，此時可以對搜索最近鄰近時建立的KD樹或者球樹進行規模限制來改進。當數據量增大時，要求較大的內存支持I/O消耗也很大；演算法聚類效果依賴與距離公式選取，實際應用中常用歐式距離，對於高維數據，存在「維數災難」。

        3）調參相對於傳統的K-Means之類的聚類演算法稍復雜，主要需要對距離閾值ϵϵ，鄰域樣本數閾值MinPts聯合調參，不同的參數組合對最後的聚類效果有較大影響。

        4）對於從兩類均可達的邊界點，由於各個點是被隨機訪問的，因此DBSCAN不能保證每次都返回相同的聚類。

    DBSCAN類的重要參數分為兩類，一類是DBSCAN演算法本身的參數，一類是最近鄰度量的參數，下面我們對這些參數做一個總結。

    1） eps： DBSCAN演算法參數，即我們的ϵ-鄰域的距離閾值，和樣本距離超過ϵ的樣本點不在ϵ-鄰域內。 默認值是0.5 ，一般需要通過在多組值裡面選擇一個合適的閾值。eps過大，則更多的點會落在核心對象的ϵ-鄰域，此時我們的類別數可能會減少，本來不應該是一類的樣本也會被劃分為一類。反之則類別數可能會增大，本來是一類的樣本卻被劃分開。

   2） min_samples： DBSCAN演算法參數，即樣本點要成為核心對象所需要的ϵ-鄰域的樣本數閾值。默認值是5。一般需要通過在多組值裡面選擇一個合適的閾值。通常和eps一起調參。在eps一定的情況下，min_samples過大，則核心對象會過少，此時簇內部分本來是一類的樣本可能會被標為噪音點，類別數也會變多。反之min_samples過小的話，則會產生大量的核心對象，可能會導致類別數過少。

    3） metric： 最近鄰距離度量參數。可以使用的距離度量比較多，一般來說DBSCAN使用默認的歐式距離(即p=2的閔可夫斯基距離)就可以滿足我們的需求。可以使用的距離量度參數有：歐式距離、曼哈頓距離、切比雪夫距離、閔可夫斯基距離、帶權重閔可夫斯基距離、標准化歐式距離、馬氏距離。

還有一些其他不是實數的距離度量，一般在DBSCAN演算法用不上，這里也就不列了。

    4）algorithm：最近鄰搜索演算法參數，演算法一共有三種，第一種是蠻力實現，第二種是KD樹實現，第三種是球樹實現。這三種方法與K近鄰法(KNN)原理中演算法一致。對於這個參數，一共有4種可選輸入，"brute"對應第一種蠻力實現,"kd_tree"對應於第二種KD樹實現，"ball_tree"對應於第三種的球樹實現，"auto"則會在上面三種演算法中做權衡，選擇一個擬合最好的最優演算法。 需要注意的是，如果輸入樣本特徵是稀疏的時候，無論我們選擇哪種演算法，最後sklearn都會去用蠻力實現"brute" 。個人的經驗，一般情況使用默認的"auto"就夠了。如果數據量很大或者特徵也很多，用「auto」建樹時間可能會很長，效率不高，建議選擇KD樹實現「kd_tree」,此時如果發現"kd_tree"速度比較慢或者已經知道樣本分布不是很均勻時，可以嘗試用"ball_tree"。

    5） leaf_size ：最近鄰搜索演算法參數，為使用KD樹或者球樹時，停止建子樹的葉子節點數量的閾值。這個值越小，則生成的KD樹或者球樹就越大，層數越深，建樹時間越長，反之，則生成的KD樹或者球樹會小，層數較淺，建樹時間較短。默認是30，因為這個值一般隻影響演算法是運行速度和使用內存大小，因此一般情況下可以不管它。

    6） p ：最近鄰距離度量參數。只有用於閔可夫斯基距離和帶權重閔客服斯基距離中p值的選擇，p=1為曼哈頓距離，p=2為歐式距離。如果使用默認的歐式距離不需要管這個參數。

以上就是DBSCAN類的主要參數介紹，其實需要調參的就是兩個參數eps和min_samples，這兩個值的組合對最終的聚類效果有很大的影響。

D. 聚類（Clustering）

首先我們先來認識一下什麼是聚類任務。
聚類是「無監督學習（unsupervised learning）」中重要的一種。其目標是：通過對無標記的訓練樣本學習，來揭示數據內在的性質以及規律，為進一步的數據分析做基礎。聚類的結果是一個個的簇（Cluster）。所以來說，聚類通常作為其他學習演算法的先導，比如在分類問題中，常常先做聚類，基於聚類的不同簇來進行分類模型的訓練。
我們先來認識一下聚類演算法涉及到兩個基本問題：性能度量 & 距離計算。後面我們再具體講解聚類的經典演算法。

由於聚類演算法是無監督式學習，不依賴於樣本的真實標記。所以聚類並不能像監督學習例如分類那樣，通過計算對錯（精確度/錯誤率）來評價學習器的好壞或者作為學習器的優化目標。一般來說，聚類有兩類性能度量指標：外部指標和內部指標

所謂外部，是將聚類結果與某個參考模型的結果進行比較， 以參考模型的輸出作為標准，來評價聚類的好壞。 假設聚類給出的結果為 λ，參考模型給出的結果是λ*，則我們將樣本進行兩兩配對，定義：

內部指標不依賴任何外部模型，直接對聚類的結果進行評估。直觀來說： 簇內高內聚，簇間低耦合 。定義：

我們從小學的距離都是歐氏距離。這里介紹幾種其他的距離度量方法：

這里對於無需屬性我們用閔可夫斯基距離就不能做，需要用VDM距離進行計算，對於離散屬性的兩個取值a和b，定義：

所以在計算兩個樣本的距離時候，將兩種距離混合在一起進行計算：

原型聚類即「基於原型的聚類（prototype-based clustering）」，原型指的是樣本空間中具有代表性的點（類似於K-Means 選取的中心點）。通常情況下來說，演算法現對原型進行初始化，然後對原型進行迭代更新求解。而不同的初始化形式和不同的求解方法，最終會得到不同的演算法。常見的 K-Means 便是基於簇中心來實現聚類；混合高斯聚類則是基於簇分布來實現聚類。下面我們具體看一下幾種算聚類演算法：

K-Means 聚類的思想十分簡單， 首先隨機指定類中心，根據樣本與類中心的遠近劃分類簇；然後重新計算類中心，迭代直至收斂。 實際上，迭代的過程是通過計算得到的。其根本的優化目標是平方誤差函數E：

其中 u_i 是簇 C_i 的均值向量。直觀上來看，上式刻畫了簇內樣本圍繞簇均值向量（可以理解為簇中心）的緊密程度，E值越小，則簇內樣本的相似度越高。
具體的演算法流程如下：

書上還給出了基於具體西瓜樣本集的計算過程說明。可以看一下。

LVQ 也是基於原型的聚類演算法，與K-Means 不同的是， LVQ使用樣本的真實類標記來輔助聚類 。首先，LVQ根據樣本的類標記，從各類中分別隨機選出一個樣本作為該類簇的原型，從而形成了一個 原型特徵向量組 ，接著從樣本集中隨機挑選一個樣本，計算其與原型向量組中每個向量的距離，並選取距離最小的向量所在的類簇作為該樣本的劃分結果，再與真實類標比較：

可以看到，K-Means 和 LVQ 都是以類中心作為原型指導聚類，而高斯混合聚類則採用 高斯分布 來描述原型。現在假設每個類簇中的樣本都服從一個多維高斯分布，那麼空間中的樣本可以看做由K個多維高斯分布混合而成。
多維高斯的概密為：

密度聚類是基於密度的聚類，它從個樣本分布的角度來考察樣本之間的 可連接性 ，並基於可連接性（密度可達）不斷拓展疆域（類簇）。最著名的就是DBSCAN（Density-Based Spatial Clustering of Applications with Noise），首先我們需要明白以下概念：

層次聚類試圖在不同層次對數據集進行劃分，從而形成屬性的聚類結構。
這里介紹一種「自底向上」結合策略的 AGNES（AGglomerative NESting）演算法。假設有N個待聚類的樣本，AGNES演算法的基本步驟如下：

可以看出其中最關鍵的一步就是 計算兩個類簇的相似度 ，這里有幾種度量方法：
（1）單鏈接（singal-linkage）：取類間最小距離

E. 聚類演算法有哪些

聚類演算法有：劃分法、層次法、密度演算法、圖論聚類法、網格演算法、模型演算法。

1、劃分法

劃分法(partitioning methods)，給定一個有N個元組或者紀錄的數據集，分裂法將構造K個分組，每一個分組就代表一個聚類，K<N。使用這個基本思想的演算法有：K-MEANS演算法、K-MEDOIDS演算法、CLARANS演算法。

2、層次法

層次法(hierarchical methods)，這種方法對給定的數據集進行層次似的分解，直到某種條件滿足為止。具體又可分為「自底向上」和「自頂向下」兩種方案。代表演算法有：BIRCH演算法、CURE演算法、CHAMELEON演算法等。

3、密度演算法

基於密度的方法(density-based methods)，基於密度的方法與其它方法的一個根本區別是：它不是基於各種各樣的距離的，而是基於密度的。這樣就能克服基於距離的演算法只能發現「類圓形」的聚類的缺點。代表演算法有：DBSCAN演算法、OPTICS演算法、DENCLUE演算法等。

4、圖論聚類法

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

5、網格演算法

基於網格的方法(grid-based methods)，這種方法首先將數據空間劃分成為有限個單元（cell）的網格結構,所有的處理都是以單個的單元為對象的。代表演算法有：STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法。

6、模型演算法

基於模型的方法(model-based methods)，基於模型的方法給每一個聚類假定一個模型，然後去尋找能夠很好的滿足這個模型的數據集。通常有兩種嘗試方向：統計的方案和神經網路的方案。

(5)單聚類演算法擴展閱讀：

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

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