kmeans改進演算法

❶ K-means的演算法缺點

① 在 K-means 演算法中 K 是事先給定的，這個 K 值的選定是非常難以估計的。很多時候，事先並不知道給定的數據集應該分成多少個類別才最合適。這也是 K-means 演算法的一個不足。有的演算法是通過類的自動合並和分裂，得到較為合理的類型數目 K，例如 ISODATA 演算法。關於 K-means 演算法中聚類數目K 值的確定在文獻中，是根據方差分析理論，應用混合 F統計量來確定最佳分類數，並應用了模糊劃分熵來驗證最佳分類數的正確性。在文獻中，使用了一種結合全協方差矩陣的 RPCL 演算法，並逐步刪除那些只包含少量訓練數據的類。而文獻中使用的是一種稱為次勝者受罰的競爭學習規則，來自動決定類的適當數目。它的思想是：對每個輸入而言，不僅競爭獲勝單元的權值被修正以適應輸入值，而且對次勝單元採用懲罰的方法使之遠離輸入值。
② 在 K-means 演算法中，首先需要根據初始聚類中心來確定一個初始劃分，然後對初始劃分進行優化。這個初始聚類中心的選擇對聚類結果有較大的影響，一旦初始值選擇的不好，可能無法得到有效的聚類結果，這也成為 K-means演算法的一個主要問題。對於該問題的解決，許多演算法採用遺傳演算法（GA），例如文獻 中採用遺傳演算法（GA）進行初始化，以內部聚類准則作為評價指標。
③ 從 K-means 演算法框架可以看出，該演算法需要不斷地進行樣本分類調整，不斷地計算調整後的新的聚類中心，因此當數據量非常大時，演算法的時間開銷是非常大的。所以需要對演算法的時間復雜度進行分析、改進，提高演算法應用范圍。在文獻中從該演算法的時間復雜度進行分析考慮，通過一定的相似性准則來去掉聚類中心的侯選集。而在文獻中，使用的 K-means 演算法是對樣本數據進行聚類，無論是初始點的選擇還是一次迭代完成時對數據的調整，都是建立在隨機選取的樣本數據的基礎之上，這樣可以提高演算法的收斂速度。

❷ 聚類演算法--KMeans

    與分類、序列標注等任務不同，聚類是在事先並不知道任何樣本標簽的情況下，通過數據之間的內在關系把樣本劃分為若干類別，使得同類別樣本之間的相似度高，不同類別之間的樣本相似度低(即增大類內聚，減少類間距)。    

    聚類屬於非監督學習，K均值聚類是最基礎常用的聚類演算法。它的基本思想是，通過迭代尋找K個簇(Cluster)的一種劃分方案，使得聚類結果對應的損失函數最小。其中，損失函數可以定義為各個樣本距離所屬簇中心點的誤差平方和。

其中 代表第i個樣本， 是 所屬的簇，  代表簇對應的中心點，M是樣本總數。

相關概念：

    K值： 要得到的簇的個數。

    質心： 每個簇的均值向量。即向量各維取平均即可。

    距離量度： 常用歐幾里得距離和餘弦相似度(先標准化)。

    KMeans的主要思想是：在給定K值和K個初始類簇中心點的情況下，把每個點(亦即數據記錄)分到離其最近的類簇中心點所代表的類簇中，所有點分配完畢之後，根據一個類簇內的所有點重新計算該類簇的中心點(取平均值)，然後再迭代的進行分配點和更新類簇中心點的步驟，直至類簇中心點的變化很小，或者達到指定的迭代次數。

    KMeans的核心目標是將給定的數據集劃分成K個簇(K是超餐)，並給出每個樣本數據對應的中心點。具體步驟非常簡單：

    （1）首先確定一個K值，即我們希望將數據集經過聚類得到k個集合。

    （2）從數據集中隨機選擇K個數據點作為質心。

    （3）對數據集中每一個點，計算其與每一個質心的距離(如歐式距離)，離哪個質心近，就劃分到哪個質心所屬的集合。

    （4）把所有數據歸好集合後，一共有K個集合。然後重新計算每個集合的質心。

    （5）如果新計算出來的質心和原來的質心之間的距離小於某一個設置的閾值(表示重新計算的質心的位置變化不大，趨於穩定，或者說收斂)，我們可以認為聚類已經達到期望的結果，演算法終止。

    （6）如果新質心和原質心距離變化很大，需要迭代3-5步驟。

KMeans最核心的部分是先固定中心點，調整每個樣本所屬的類別來減少J；再固定每個樣本的類別，調整中心點繼續減小J。兩個過程交替循環，J單調遞減直到極小值，中心點和樣本劃分的類別同時收斂。

KMeans的優點 ：

 高效可伸縮，計算復雜度為O(NKt)接近於線性(N是數據量，K是聚類總數，t是迭代輪數)。

 收斂速度快，原理相對通俗易懂，可解釋性強。

當結果簇是密集的，而簇與簇之間區別是明顯時，他的效果較好。主要需要調參的參數僅僅是簇數K。

缺點 ：

 受初始值和異常點影響，聚類結果可能不是全局最優而是局部最優。K-Means演算法對初始選取的質心點是敏感的，不同的隨機種子點得到的聚類結果完全不同，對結果影響很大。

 K是超參數，一般需要按經驗選擇。

 對噪音和異常點比較的敏感，用來檢測異常值。

 只能發現球狀的簇。在K-Means中，我們用單個點對cluster進行建模，這實際上假設各個cluster的數據是呈高維球型分布的，但是在生活中出現這種情況的概率並不算高。例如，每一個cluster是一個一個的長條狀的，K-Means的則根本識別不出來這種類別( 這種情況可以用GMM )。實際上，K-Means是在做凸優化，因此處理不了非凸的分布。

根據以上特點，我們可以從下面幾個角度對演算法做調優。

（1）數據預處理：歸一化和異常點過濾

    KMeans本質是一種基於歐式距離度量的數據劃分方法，均值和方差大的維度將對數據的聚類結果產生決定性影響 。所以在聚類前對數據( 具體的說是每一個維度的特徵 )做歸一化和單位統一至關重要。此外，異常值會對均值計算產生較大影響，導致 中心偏移 ，這些雜訊點最好能提前過濾。

（2）合理選擇K值

    K值的選擇一般基於實驗和多次實驗結果。例如採用 手肘法 ，嘗試不同K值並將對應的損失函數畫成折線。手肘法認為圖上的 拐點就是K的最佳值 (k=3)。

為了將尋找最佳K值的過程自動化，研究人員提出了Gap Statistic方法。不需要人們用肉眼判斷，只需要找到最大的Gap Statistic對應的K即可。

       損失函數記為  ，當分為K類時，Gap Statistic定義為：  。 是 的期望 ，一般由蒙特卡洛模擬產生。我們在樣本所在的區域內按照均勻分布隨機地產生和原始樣本數一樣多的隨機樣本，並對這個隨機樣本做KMeans，得到一個 ，重復多次就可以計算出 的近似值。

       的物理含義是隨機樣本的損失與實際樣本的損失之差。Gap越大說明聚類的效果越好 。一種極端情況是，隨著K的變化 幾乎維持一條直線保持不變。說明這些樣本間沒有明顯的類別關系，數據分布幾乎和均勻分布一致，近似隨機。此時做聚類沒有意義。

（3）改進初始值的選擇

    之前我們採用隨機選擇K個中心的做法，可能導致不同的中心點距離很近，就需要更多的迭代次數才能收斂。如果在選擇初始中心點時能 讓不同的中心盡可能遠離 ，效果往往更好。這類演算法中，以K-Means++演算法最具影響力。

（4）採用核函數

    主要思想是通過一個非線性映射，將輸入空間中的數據點映射到高維的特徵空間中，並在新的空間進行聚類。非線性映射增加了數據點線性可分的概率(與SVM中使用核函數思想類似)對於非凸的數據分布可以達到更為准確的聚類結果。

 (1）初始的K個質心怎麼選？

    最常用的方法是隨機選，初始質心的選取對最終聚類結果有影響，因此演算法一定要多執行幾次，哪個結果更合理，就用哪個結果。當然也有一些優化的方法，第一種是選擇彼此距離最遠的點，具體來說就是先選第一個點，然後選離第一個點最遠的當第二個點，然後選第三個點，第三個點到第一、第二兩點的距離之和最小，以此類推。第二種是先根據其他聚類演算法(如層次聚類)得到聚類結果，從結果中每個分類選一個點

（2）關於離群值？

    離群值就是遠離整體的，非常異常、非常特殊的數據點，在聚類之前應該將這些"極大""極小"之類的離群數據都去掉，否則會對於聚類的結果有影響。但是，離散值往往自身就很有分析的價值，可以把離群值單獨作為一類來分析。

（3）單位要一致！

（4）標准化

    數據中X整體都比較小，比如都是1到10之間的數，Y很大，比如都是1000以上的數，那麼在計算距離的時候Y起到的作用就比X大很多，X對於距離的影響幾乎可以忽略，這也有問題。因此，如果K-Means聚類中選擇歐幾里得距離計算距離，數據集又出現了上面所述的情況，就一定要進行數據的標准化(normalization)，即將數據按比例縮放，使之落入一個小的特定區間。

    K-Means是無監督學習的聚類演算法，沒有樣本輸出；而KNN是監督學習的分類演算法，有對應的類別輸出 。KNN基本不需要訓練，對測試集裡面的點，只需要找到在訓練集中最近的K個點，用這最近的K個點的類別來決定測試點的類別。而K-Means則有明顯的訓練過程，找到K個類別的最佳質心，從而決定樣本的簇類別。當然，兩者也有一些相似點，兩個演算法都包含一個過程，即找出和某一個點最近的點。 兩周都利用了最近鄰的思想 。

❸ 「聚類分析」16聚類分析之KMeans演算法與K中心點演算法

1.聚類

    聚類屬於無監督式學習。在無監督式學習中，訓練樣本的標記信息是未知的，演算法通過對 無標記樣本 的學習來揭示蘊含於數據中的性質和規律。聚類演算法的任務是根據數據特徵將數據集相似的數據劃分到同一簇。

2.聚類分析

    聚類分析是將物理的或者抽象的數據集合劃分為多個類別的過程，聚類之後的每個類別中任意兩個數據樣本之間具有較高的相似度，而不同類別的數據樣本之間具有較低的相似度。

3.聚類演算法常用分類

①劃分聚類方法

②層次聚類方法

③基於密度的聚類方法

④基於網格的聚類方法

4.聚類分析中相似度的計算方法

（1）連續型屬性的相似度計算方法：歐式距離

（2）二值離散型屬性的相似度計算方法

數據樣本的二值離散型屬性的取值情況：

（3）多值離散型屬性的相似度計算方法：多值離散型屬性轉化為二值離散型屬性  

（4）混合類型屬性的相似度計算方法

    將屬性按照類型分組，每個新的數據集中只包含一種類型的屬性，然後對每個數據集進行單獨的聚類分析，隨後把混合類型的屬性放在一起處理，進行一次聚類分析。

5.KMeans演算法（劃分法）

    KMeans也稱為K均值，是一種聚類演算法。它可以根據數據特徵將數據集分成K個不同的簇，簇的個數K是由用戶指定的。KMeans演算法基於 距離 來度量實例間的相似程度（與KNN演算法一樣，大多數問題採用歐氏距離），然後把較為相似的實例劃分到同一簇。

（1）聚類的性能度量大致有以下兩類：

①外部指標：將聚類結果與某個「參考模型」進行比較。

②內部指標：直接考察聚類結果而不利於參考模型。

（2）聚類演算法的過程：

①隨機選擇k個點作為聚類中心；

②計算各個點到這k個點的距離；

③將對應的點聚到與它最近的這個聚類中心；

④重新計算聚類中心；

⑤比較當前聚類中心與前一次聚類中心，如果是同一個點，得到聚類結果，如果不是，則重復②③④⑤。

（3）聚類演算法的實現：

【注】 模型效果評估指標說明：

1）inertias_：是K-Means模型對象的屬性，它作為沒有真實分類結果標簽下的非監督式評估指標。表示樣本到最近的聚類中心的距離總和。 值越小越好，越小表示樣本在類間的分布越集中。

2）蘭德指數（Rand index）:需要給定實際類別信息C，假設n是聚類結果，a表示在C與K中都是同類別的元素對數，b表示在C與K中都是不同類別的元素對數，則蘭德指數為：

RI取值范圍為[0,1]， 值越大意味著聚類結果與真實情況越吻合。

對於隨機結果，RI並不能保證分數接近零。為了實現「在聚類結果隨機產生的情況下，指標應該接近零」，調整蘭德系數（Adjusted rand index）被提出，它具有更高的區分度：

ARI取值范圍為[−1,1]， 值越大意味著聚類結果與真實情況越吻合。 從廣義的角度來講，ARI衡量的是兩個數據分布的吻合程度。

3）同質化得分（Homogeneity）：如果所有的聚類都只包含屬於單個類的成員的數據點，則聚類結果滿足同質性。取值范圍[0,1]， 值越大意味著聚類結果與真實情況越符合。

4）完整性得分（Complenteness）：如果作為給定類的成員的所有數據點是相同集群的元素，則聚類結果滿足完整性。取值范圍[0,1]， 值越大意味著聚類結果與真實情況越符合。

5）v_meansure_score：同質化和完整性之間的諧波平均值，v=2*（同質化*完整性）/（同質化+完整性），取值范圍[0,1]， 值越大意味著聚類結果與真實情況越符合。

6.k中心點演算法

（1）原理

①隨機選取k個中心點；

②遍歷所有數據，將每個數據劃分到最近的中心點中；

③計算每個聚類的平均值，並作為新的中心點；

④重復②③，直到這k個中線點不再變化（收斂了），或執行了足夠多的迭代。

（2）與KMeans演算法對比

    K-中心點聚類的 基本思想 和K-Means的思想相同，實質上是對K-means演算法的優化和改進。在K-means中， 異常數據對其的演算法過程會有較大的影響 。在K-means演算法執行過程中，可以通過隨機的方式選擇初始質心，也只有初始時通過隨機方式產生的質心才是實際需要聚簇集合的中心點，而後面通過不斷迭代產生的新的質心很可能並不是在聚簇中的點。如果某些異常點距離質心相對較大時，很可能導致重新計算得到的質心偏離了聚簇的真實中心。

❹ K-means改進演算法(一)：K-means++

在普通的K-means演算法中，會存在以下的缺點：

1). 只能收斂到局部最優，受到初始值較大；
2). K不確定，需自己確定；
3). 受noise影響較大。

為了改進k-means演算法，出現了K-means++，ISODATA和Kernel K-means等方法。

其中K-means++演算法是對初始值選擇進行了改進。
普通k-means演算法的步驟大概如下所示（假設k=3）：

普通的K均值演算法是隨機選取K個點作為聚類的中心，而K-means++按照如下的思想選取K個聚類中心，其基本的思想是，K個初始聚類中心相互之間應該分得越開、離得越遠越好（圖片來自 https://www.cnblogs.com/yixuan-xu/p/6272208.html ）：

❺ K-means原理、優化、應用

K-Means演算法是無監督的聚類演算法，它實現起來比較簡單，聚類效果也不錯，因此應用很廣泛。K-Means演算法有大量的變體，本文就從最傳統的K-Means演算法講起，在其基礎上講述K-Means的優化變體方法。包括初始化優化K-Means++, 距離計算優化elkan K-Means演算法和大數據情況下的優化Mini Batch K-Means演算法。

    K-Means演算法的思想很簡單，對於給定的樣本集，按照樣本之間的距離大小，將樣本集劃分為K個簇。讓簇內的點盡量緊密的連在一起，而讓簇間的距離盡量的大。

1、隨機選擇K個聚類的初始中心。

2、對任意一個樣本點，求其到K個聚類中心的距離，將樣本點歸類到距離最小的中心的聚類。

3、每次迭代過程中，利用均值等方法更新各個聚類的中心點（質心）。

4、對K個聚類中心，利用2、3步迭代更新後，如果位置點變化很小(可以設置閾值)，則認為達到穩定狀態，迭代結束。（畫圖時，可以對不同的聚類塊和聚類中心可選擇不同的顏色標注）

1、原理比較簡單，實現也是很容易，收斂速度快。 

2、聚類效果較優。 

3、演算法的可解釋度比較強。 

4、主要需要調參的參數僅僅是簇數k。

1、K值的選取不好把握 

2、對於不是凸的數據集比較難收斂 

3、如果各隱含類別的數據不平衡，比如各隱含類別的數據量嚴重失衡，或者各隱含類別的方差不同，則聚類效果不佳。 

4、 最終結果和初始點的選擇有關，容易陷入局部最優。

5、對噪音和異常點比較的敏感。

    解決K-Means演算法對 初始簇心 比較敏感的問題，二分K-Means演算法是一種弱化初始質心的一種演算法。

1、將所有樣本數據作為一個簇放到一個隊列中。

2、從隊列中選擇一個簇進行K-Means演算法劃分，劃分為兩個子簇，並將子簇添加到隊列中。

3、循環迭代步驟2操作，直到中止條件達到(聚簇數量、最小平方誤差、迭代次數等)。

4、隊列中的簇就是最終的分類簇集合。

從隊列中選擇劃分聚簇的規則一般有兩種方式；分別如下：

1、對所有簇計算誤差和SSE(SSE也可以認為是距離函數的一種變種)，選擇SSE最大的聚簇進行劃分操作(優選這種策略)。

2、選擇樣本數據量最多的簇進行劃分操作：

    由於 K-means 演算法的分類結果會受到初始點的選取而有所區別，因此有提出這種演算法的改進: K-means++ 。

    其實這個演算法也只是對初始點的選擇有改進而已，其他步驟都一樣。初始質心選取的基本思路就是， 初始的聚類中心之間的相互距離要盡可能的遠 。

1、隨機選取一個樣本作為第一個聚類中心 c1；

2、計算每個樣本與當前已有類聚中心最短距離（即與最近一個聚類中心的距離），用 D(x)表示；這個值越大，表示被選取作為聚類中心的概率較大；最後，用輪盤法選出下一個聚類中心。

3、重復步驟2，知道選出 k 個聚類中心。

4、選出初始點（聚類中心），就繼續使用標準的 k-means 演算法了。

盡管K-Means++在聚類中心的計算上浪費了很多時間，但是在迭代過程中，k-mean 本身能快速收斂，因此演算法實際上降低了計算時間。

      解決K-Means++演算法缺點而產生的一種演算法；主要思路是改變每次遍歷時候的取樣規則，並非按照K-Means++演算法每次遍歷只獲取一個樣本，而是每次獲取K個樣本，重復該取樣操作O(logn)次 (n是樣本的個數) ，然後再將這些抽樣出來的樣本聚類出K個點，最後使用這K個點作為K-Means演算法的初始聚簇中心點。實踐證明：一般5次重復採用就可以保證一個比較好的聚簇中心點。

1、在N個樣本中抽K個樣本，一共抽logn次，形成一個新的樣本集，一共有Klogn個數據。

2、在新數據集中使用K-Means演算法，找到K個聚簇中心。

3、把這K個聚簇中心放到最初的樣本集中，作為初始聚簇中心。

4、原數據集根據上述初始聚簇中心，再用K-Means演算法計算出最終的聚簇。

        Canopy屬於一種『粗』聚類演算法，即使用一種簡單、快捷的距離計算方法將數據集分為若干可重疊的子集canopy，這種演算法不需要指定k值、但精度較低，可以結合K-means演算法一起使用：先由Canopy演算法進行粗聚類得到k個質心，再使用K-means演算法進行聚類。

 1、將原始樣本集隨機排列成樣本列表L=[x1,x2,...,xm]（排列好後不再更改），根據先驗知識或交叉驗證調參設定初始距離閾值T1、T2，且T1>T2 。

2、從列表L中隨機選取一個樣本P作為第一個canopy的質心，並將P從列表中刪除。

3、從列表L中隨機選取一個樣本Q，計算Q到所有質心的距離，考察其中最小的距離D：

如果D≤T1，則給Q一個弱標記，表示Q屬於該canopy，並將Q加入其中；

如果D≤T2，則給Q一個強標記，表示Q屬於該canopy，且和質心非常接近，所以將該canopy的質心設為所有強標記樣本的中心位置，並將Q從列表L中刪除；

 如果D>T1，則Q形成一個新的聚簇，並將Q從列表L中刪除。

4、重復第三步直到列表L中元素個數為零。

1、『粗』距離計算的選擇對canopy的分布非常重要，如選擇其中某個屬性、其他外部屬性、歐式距離等。

2、當T2<D≤T1時，樣本不會從列表中被刪除，而是繼續參與下一輪迭代，直到成為新的質心或者某個canopy的強標記成員。

3、T1、T2的取值影響canopy的重疊率及粒度：當T1過大時，會使樣本屬於多個canopy，各個canopy間區別不明顯；當T2過大時，會減少canopy個數，而當T2過小時，會增加canopy個數，同時增加計算時間。

4、canopy之間可能存在重疊的情況，但是不會存在某個樣本不屬於任何canopy的情況。

5、Canopy演算法可以消除孤立點，即刪除包含樣本數目較少的canopy，往往這些canopy包含的是孤立點或噪音點。

    由於K-Means演算法存在初始聚簇中心點敏感的問題，常用使用Canopy+K-Means演算法混合形式進行模型構建。

1、先使用canopy演算法進行「粗」聚類得到K個聚類中心點。

2、K-Means演算法使用Canopy演算法得到的K個聚類中心點作為初始中心點，進行「細」聚類。

1、執行速度快(先進行了一次聚簇中心點選擇的預處理)；

2、不需要給定K值，應用場景多。

3、能夠緩解K-Means演算法對於初始聚類中心點敏感的問題。

    Mini Batch K-Means演算法是K-Means演算法的一種優化變種，採用 小規模的數據子集 (每次訓練使用的數據集是在訓練演算法的時候隨機抽取的數據子集) 減少計算時間 ，同時試圖優化目標函數；Mini Batch K-Means演算法可以減少K-Means演算法的收斂時間，而且產生的結果效果只是略差於標准K-Means演算法。

1、首先抽取部分數據集，使用K-Means演算法構建出K個聚簇點的模型。

2、繼續抽取訓練數據集中的部分數據集樣本數據，並將其添加到模型中，分配給距離最近的聚簇中心點。

3、更新聚簇的中心點值。

4、循環迭代第二步和第三步操作，直到中心點穩定或者達到迭代次數，停止計算操作。

https://www.jianshu.com/p/f0727880c9c0

❻ EM演算法和K-Means演算法

在實際工作中，會遇到這樣的問題，給機器輸入大量的特徵數據，並希望機器希望學習找到某種共同的特徵或者結構，亦或是數據之間存在的某種關聯，例如，視頻網站根據用戶的觀看行為進行分組，從而建立不同的推薦策略，或是找到視頻是否流暢與用戶是否退訂之間的關系等。屬於無監督學習演算法。

包括兩大類，一：數據聚類，此類方案往往是通過數次迭代找到數據的最優分割。二：特徵變數的關聯規則，此類方法利用各種相關性分析找到變數之間的關系。

Kmeans的 核心 是將給定的數據集劃分成K個簇，並給出每個數據對應的中心點。演算法具體步驟如下：

1：數據預處理，如歸一化、離散點處理等

2：隨機選取K個簇中心，記為 。

3：定義代價函數： 。

4：令 為迭代步數，重復下面過程直到 收斂

4.1 對於每一個樣本將其分到距離最近的簇

4.2 對於每一個類簇k，重新計算類簇的中心

K均值在迭代時，交替方向法求解，假設當前 沒有達到最小值，那麼首先固定簇中心 ,調整樣本 所屬的類別 來讓 函數減小，然後再固定 ,調整中心 使 減小，這兩個過程交替循環， 單調遞減，當 遞減到最小時， 和 同時收斂。

缺點：

1：受初始值的影響

2：異常值的影響

3：當簇分布相差很大時，不適合

優點：

大數據集， 均值聚類相對是可伸縮和高效的，計算復雜度 ,其中 是數據對象的數目， 是聚類簇數， 是迭代的輪數。盡管演算法經常局部最優結束，一般情況下局部最優已經滿足要求

調優方向

1：數據歸一化和離散點處理

2：合理選擇 值

一：手肘法：選擇若干個K畫均方誤差的折線圖肉眼查看拐點 二：Gap Statistic方法的基本思路是：引入參考的測度值，其可以通過Monte Carlo采樣的方法獲得。 

3：採用核函數

利用kmeans假設各個數據簇的數據具有一樣的先驗概率，並呈現高緯球形分布，但是實際生活中是不常見的。面對非凸的數據分布時，引入核函數來優化。核心：利用非線性核函數將樣本映射到高緯空間，並在新的特徵空間中進行聚類。非線性映射增加了數據的線性可分的概率。

針對對初始值敏感的改進

K-means++演算法：

起步

由於 K-means 演算法的分類結果會受到初始點的選取而有所區別，因此有提出這種演算法的改進: K-means++ 。

演算法步驟

其實這個演算法也只是對初始點的選擇有改進而已，其他步驟都一樣。初始質心選取的基本思路就是，初始的聚類中心之間的相互距離要盡可能的遠。

演算法描述如下：

步驟一： 隨機選取一個樣本作為第一個聚類中心；

步驟二：

計算每個樣本與當前已有類聚中心最短距離（即與最近一個聚類中心的距離） 這個值越大，表示被選取作為聚類中心的概率較大；

最後，用輪盤法選出下一個聚類中心；

步驟三： 重復步驟二，知道選出 k 個聚類中心 。

選出初始點後，就繼續使用標準的 k-means 演算法了。

      ISODATA的聚類個數是可變的，因為在聚類的過程中，對類別數有一個「合並」和「分裂」的操作。合並是當聚類結果某一類中樣本數太少，或兩個類間的距離太近時，將這兩個類別合並成一個類別；分裂是當聚類結果中某一類的類內方差太大，將該類進行分裂，分裂成兩個類別。

ISODATA分類的過程和K-Means一樣，用的也是迭代的思想：先隨意給定初始的類別中心，然後做聚類，通過迭代，不斷調整這些類別中心，直到得到最好的聚類中心為止。

註：

初始簇個數 ，最終簇大小范圍

分裂和合並的標准

每個簇的樣本數最小 ，小於這個值不進行分裂

每個簇樣本的最大方差 ，大於這個則進行分裂

兩個簇之間的最小距離圍 ，小於這個則進行合並

EM演算法是一種迭代演算法，用於含有隱變數的概率模型的極大似然估計，或者說是極大後驗概率估計。

演算法步驟

輸入：觀測變數數據Y，隱變數Z，聯合分布 ，條件分布

輸出：模型參數

1：選擇參數的初始值

2：E步：記 為第 次迭代參數 的估計值，在第 次迭代的E步，計算 函數 ，其中， 是再幫給定Y和 下隱變數數據Z的條件概率分布；

3：M步：求使 極大化的 ，確定第 次迭代的參數的估計值 ,

4：重復2，3步，直到收斂

EM演算法推導

通過不斷求解下界的極大化逼近求解對數似然函數的極大化的演算法

含有隱變數的概率模型的極大似然估計

下面證明

利用Jensen不等式

令

則 即函數 增大 ，也可以使得 有盡可能的增大，選擇 使得 達到極大，即 現在求 的表達式 = = = =

假設有m個觀察樣本，模型的參數 ，最大化對數似然函數可以寫成如下的形式

當概率模型含有無法觀測的隱變數時，參數的最大似然估計

因為含有不可觀測的隱變數，無法通過極大似然估計求解參數，這時可以通過EM演算法求解。假設 對應的分布 ，並滿足 。利用Jensen不等式，可以得到，

。不等式右側，即為 。當等式成立時，我們相當於優化的函數找到了一個逼近的下界，然後最大化這個下界

EM演算法和k-means關系

1：E步驟

2：M步驟：最大化

K均值演算法等價於以下隱變數求最大似然問題

相當於E步找到x當前最近的簇

在M步驟 來更新簇中心

#####引用葫蘆書和李航機器學習

❼ 大數據十大經典演算法之k-means

大數據十大經典演算法之k-means
k均值演算法基本思想：
K均值演算法是基於質心的技術。它以K為輸入參數，把n個對象集合分為k個簇，使得簇內的相似度高，簇間的相似度低。
處理流程：
1、為每個聚類確定一個初始聚類中心，這樣就有k個初始聚類中心；
2、將樣本按照最小距離原則分配到最鄰近聚類
3、使用每個聚類中的樣本均值作為新的聚類中心
4、重復步驟2直到聚類中心不再變化
5、結束，得到K個聚類
劃分聚類方法對數據集進行聚類時的要點：
1、選定某種距離作為數據樣本間的相似性度量，通常選擇歐氏距離。
2、選擇平價聚類性能的准則函數
用誤差平方和准則函數來評價聚類性能。
3、相似度的計算分局一個簇中對象的平均值來進行
K均值演算法的優點：
如果變數很大，K均值比層次聚類的計算速度較快（如果K很小）；
與層次聚類相比，K均值可以得到更緊密的簇，尤其是對於球狀簇；
對於大數據集，是可伸縮和高效率的；
演算法嘗試找出使平方誤差函數值最小的k個劃分。當結果簇是密集的，而簇與簇之間區別明顯的時候，效果較好。
K均值演算法缺點：
最後結果受初始值的影響。解決辦法是多次嘗試取不同的初始值。
可能發生距離簇中心m最近的樣本集為空的情況，因此m得不到更新。這是一個必須處理的問題，但我們忽略該問題。
不適合發現非凸面形狀的簇，並對雜訊和離群點數據較敏感，因為少量的這類數據能夠對均值產生較大的影響。
K均值演算法的改進：
樣本預處理。計算樣本對象量量之間的距離，篩掉與其他所有樣本那的距離和最大的m個對象。
初始聚類中心的選擇。選用簇中位置最靠近中心的對象，這樣可以避免孤立點的影響。
K均值演算法的變種：
K眾數（k-modes）演算法，針對分類屬性的度量和更新質心的問題而改進。
EM（期望最大化）演算法
k-prototype演算法
這種演算法不適合處理離散型屬性，但是對於連續型具有較好的聚類效果。
k均值演算法用途：
圖像分割；
衡量足球隊的水平；
下面給出代碼：
#include <iostream>
#include <vector>
//auther archersc
//JLU
namespace CS_LIB
{
using namespace std;
class Kmean
{
public:
//輸入格式
//數據數量N 維度D
//以下N行，每行D個數據
istream& loadData(istream& in);
//輸出格式
//聚類的數量CN
//中心維度CD
//CN行，每行CD個數據
//數據數量DN
//數據維度DD
//以下DN組，每組的第一行兩個數值DB, DDis
//第二行DD個數值
//DB表示改數據屬於一類，DDis表示距離改類的中心的距離
ostream& saveData(ostream& out);
//設置中心的數量
void setCenterCount(const size_t count);
size_t getCenterCount() const;
//times最大迭代次數， maxE ,E(t)表示第t次迭代後的平方誤差和，當|E(t+1) - E(t)| < maxE時終止
void clustering(size_t times, double maxE);

private:
double calDistance(vector<double>& v1, vector<double>& v2);

private:
vector< vector<double> > m_Data;
vector< vector<double> > m_Center;
vector<double> m_Distance;
vector<size_t> m_DataBelong;
vector<size_t> m_DataBelongCount;
};
}
#include "kmean.h"

#include <ctime>
#include <cmath>
#include <cstdlib>
//auther archersc
//JLU

namespace CS_LIB
{
template<class T>
void swap(T& a, T& b)
{
T c = a;
a = b;
b = c;
}

istream& Kmean::loadData(istream& in)
{
if (!in){
cout << "input error" << endl;
return in;
}
size_t dCount, dDim;
in >> dCount >> dDim;
m_Data.resize(dCount);
m_DataBelong.resize(dCount);
m_Distance.resize(dCount);
for (size_t i = 0; i < dCount; ++i){
m_Data[i].resize(dDim);
for (size_t j = 0; j < dDim; ++j){
in >> m_Data[i][j];
}
}
return in;
}
ostream& Kmean::saveData(ostream& out)
{
if (!out){
cout << "output error" << endl;
return out;
}
out << m_Center.size();
if (m_Center.size() > 0)
out << << m_Center[0].size();
else
out << << 0;
out << endl << endl;
for (size_t i = 0; i < m_Center.size(); ++i){
for (size_t j = 0; j < m_Center[i].size(); ++j){
out << m_Center[i][j] << ;
}
out << endl;
}
out << endl;
out << m_Data.size();
if (m_Data.size() > 0)
out << << m_Data[0].size();
else
out << << 0;
out << endl << endl;
for (size_t i = 0; i < m_Data.size(); ++i){
out << m_DataBelong[i] << << m_Distance[i] << endl;
for (size_t j = 0; j < m_Data[i].size(); ++j){
out << m_Data[i][j] << ;
}
out << endl << endl;
}
return out;
}
void Kmean::setCenterCount(const size_t count)
{
m_Center.resize(count);
m_DataBelongCount.resize(count);
}
size_t Kmean::getCenterCount() const
{
return m_Center.size();
}
void Kmean::clustering(size_t times, double maxE)
{
srand((unsigned int)time(NULL));
//隨機從m_Data中選取m_Center.size()個不同的樣本點作為初始中心。
size_t *pos = new size_t[m_Data.size()];
size_t i, j, t;
for (i = 0; i < m_Data.size(); ++i){
pos[i] = i;
}
for (i = 0; i < (m_Data.size() << 1); ++i){
size_t s1 = rand() % m_Data.size();
size_t s2 = rand() % m_Data.size();
swap(pos[s1], pos[s2]);
}
for (i = 0; i < m_Center.size(); ++i){
m_Center[i].resize(m_Data[pos[i]].size());
for (j = 0; j < m_Data[pos[i]].size(); ++j){
m_Center[i][j] = m_Data[pos[i]][j];
}
}
delete []pos;
double currE, lastE;
for (t = 0; t < times; ++t){
for (i = 0; i < m_Distance.size(); ++i)
m_Distance[i] = LONG_MAX;
for (i = 0; i < m_DataBelongCount.size(); ++i)
m_DataBelongCount[i] = 0;
currE = 0.0;
for (i = 0; i < m_Data.size(); ++i){
for (j = 0; j < m_Center.size(); ++j){
double dis = calDistance(m_Data[i], m_Center[j]);
if (dis < m_Distance[i]){
m_Distance[i] = dis;
m_DataBelong[i] = j;
}
}
currE += m_Distance[i];
m_DataBelongCount[m_DataBelong[i]]++;
}
cout << currE << endl;
if (t == 0 || fabs(currE - lastE) > maxE)
lastE = currE;
else
break;
for (i = 0; i < m_Center.size(); ++i){
for (j = 0; j < m_Center[i].size(); ++j)
m_Center[i][j] = 0.0;

}
for (i = 0; i < m_DataBelong.size(); ++i){
for (j = 0; j < m_Data[i].size(); ++j){
m_Center[m_DataBelong[i]][j] += m_Data[i][j] / m_DataBelongCount[m_DataBelong[i]];
}
}
}
}
double Kmean::calDistance(vector<double>& v1, vector<double>& v2)
{
double result = 0.0;
for (size_t i = 0; i < v1.size(); ++i){
result += (v1[i] - v2[i]) * (v1[i] - v2[i]);
}
return pow(result, 1.0 / v1.size());
//return sqrt(result);
}
}
#include <iostream>
#include <fstream>
#include "kmean.h"
using namespace std;
using namespace CS_LIB;

int main()
{
ifstream in("in.txt");
ofstream out("out.txt");
Kmean kmean;
kmean.loadData(in);
kmean.setCenterCount(4);
kmean.clustering(1000, 0.000001);
kmean.saveData(out);

return 0;
}

❽ K均值演算法

代價函數可以定義為各個樣本距離所屬簇中心點的誤差平方和

K均值演算法有一些缺點，例如受初值和離群點的影響每次的結果不穩定、結果 通常不是全局最優而是局部最優解、無法很好地解決數據簇分布差別比較大的情 況(比如一類是另一類樣本數量的100倍)、不太適用於離散分類等。但是瑕不掩 瑜，K均值聚類的優點也是很明顯和突出的，主要體現在:對於大數據集，K均值 聚類演算法相對是可伸縮和高效的，它的計算復雜度是O(NKt)接近於線性，其中N是 數據對象的數目，K是聚類的簇數，t是迭代的輪數。盡管演算法經常以局部最優結 束，但一般情況下達到的局部最優已經可以滿足聚類的需求。
其實書中也少講了缺點，那就是關於k的選擇，當維度很高的時候，你很難判斷選擇k多少比較合適。
不過書中在演算法調優中說了。所謂的調優其是也是變相的說那些缺點。

K均值演算法的調優一般可以從以下幾個角度出發。

(1)數據歸一化和離群點處理。
K均值聚類本質上是一種基於歐式距離度量的數據劃分方法，均值和方差大的 維度將對數據的聚類結果產生決定性的影響，所以未做歸一化處理和統一單位的 數據是無法直接參與運算和比較的。同時，離群點或者少量的雜訊數據就會對均 值產生較大的影響，導致中心偏移，因此使用K均值聚類演算法之前通常需要對數據 做預處理。

（2)合理選擇K值。
K值的選擇是K均值聚類最大的問題之一，這也是K均值聚類演算法的主要缺 點。實際上，我們希望能夠找到一些可行的辦法來彌補這一缺點，或者說找到K值 的合理估計方法。但是，K值的選擇一般基於經驗和多次實驗結果。例如採用手肘 法，我們可以嘗試不同的K值，並將不同K值所對應的損失函數畫成折線，橫軸 為K的取值，縱軸為誤差平方和所定義的損失函數，如圖5.3所示

由圖可見，K值越大，距離和越小;並且，當K=3時，存在一個拐點，就像人 的肘部一樣;當K (1,3)時，曲線急速下降;當K>3時，曲線趨於平穩。手肘法認 為拐點就是K的最佳值。
手肘法是一個經驗方法，缺點就是不夠自動化，因此研究員們又提出了一些 更先進的方法，其中包括比較有名的Gap Statistic方法[5]。Gap Statistic方法的優點 是，不再需要肉眼判斷，而只需要找到最大的Gap statistic所對應的K即可，因此該 方法也適用於批量化作業。在這里我們繼續使用上面的損失函數，當分為K簇時， 對應的損失函數記為Dk。Gap Statistic定義為
Gap(K)=E(logDk)−logDk

內按照均勻分布隨機地產生和原始樣本數一樣多的隨機樣本，並對這個隨機樣本
做K均值，得到一個Dk;重復多次就可以計算出E(logDk)的近似值。那麼Gap(K)有
什麼物理含義呢?它可以視為隨機樣本的損失與實際樣本的損失之差。試想實際 樣本對應的最佳簇數為K，那麼實際樣本的損失應該相對較小，隨機樣本損失與實 際樣本損失之差也相應地達到最小值，從而Gap(K)取得最大值所對應的K值就是最 佳的簇數。根據式(5.4)計算K =1,2,...,9所對應的Gap Statistic

(3)採用核函數。
採用核函數是另一種可以嘗試的改進方向。傳統的歐式距離度量方式，使得K 均值演算法本質上假設了各個數據簇的數據具有一樣的先驗概率，並呈現球形或者 高維球形分布，這種分布在實際生活中並不常見。面對非凸的數據分布形狀時， 可能需要引入核函數來優化，這時演算法又稱為核K均值演算法，是核聚類方法的一種 [6]。核聚類方法的主要思想是通過一個非線性映射，將輸入空間中的數據點映射到 高位的特徵空間中，並在新的特徵空間中進行聚類。非線性映射增加了數據點線 性可分的概率，從而在經典的聚類演算法失效的情況下，通過引入核函數可以達到 更為准確的聚類結果。

K均值演算法的主要缺點如下。
(1)需要人工預先確定初始K值，且該值和真實的數據分布未必吻合。
(2)K均值只能收斂到局部最優，效果受到初始值很大。
(3)易受到噪點的影響。
(4)樣本點只能被劃分到單一的類中。

■ K-means++演算法
K均值的改進演算法中，對初始值選擇的改進是很重要的一部分。而這類演算法 中，最具影響力的當屬K-means++演算法。原始K均值演算法最開始隨機選取數據集中 K個點作為聚類中心，而K-means++按照如下的思想選取K個聚類中心。假設已經 選取了n個初始聚類中心(0<n<K)，則在選取第n+1個聚類中心時，距離當前n個 聚類中心越遠的點會有更高的概率被選為第n+1個聚類中心。在選取第一個聚類中 心(n=1)時同樣通過隨機的方法。可以說這也符合我們的直覺，聚類中心當然是 互相離得越遠越好。當選擇完初始點後，K-means++後續的執行和經典K均值演算法 相同，這也是對初始值選擇進行改進的方法等共同點。

■ ISODATA演算法
當K值的大小不確定時，可以使用ISODATA演算法。ISODATA的全稱是迭代自 組織數據分析法。在K均值演算法中，聚類個數K的值需要預先人為地確定，並且在 整個演算法過程中無法更改。而當遇到高維度、海量的數據集時，人們往往很難准 確地估計出K的大小。ISODATA演算法就是針對這個問題進行了改進，它的思想也 很直觀。當屬於某個類別的樣本數過少時，把該類別去除;當屬於某個類別的樣 本數過多、分散程度較大時，把該類別分為兩個子類別。ISODATA演算法在K均值 演算法的基礎之上增加了兩個操作，一是分裂操作，對應著增加聚類中心數;二是 合並操作，對應著減少聚類中心數。ISODATA演算法是一個比較常見的演算法，其缺 點是需要指定的參數比較多，不僅僅需要一個參考的聚類數量Ko，還需要制定3個
閾值。下面介紹ISODATA演算法的各個輸入參數。
(1)預期的聚類中心數目Ko。在ISODATA運行過程中聚類中心數可以變 化，Ko是一個用戶指定的參考值，該演算法的聚類中心數目變動范圍也由其決定。 具體地，最終輸出的聚類中心數目常見范圍是從Ko的一半，到兩倍Ko。
(2)每個類所要求的最少樣本數目Nmin。如果分裂後會導致某個子類別所包 含樣本數目小於該閾值，就不會對該類別進行分裂操作。
(3)最大方差Sigma。用於控制某個類別中樣本的分散程度。當樣本的分散 程度超過這個閾值時，且分裂後滿足(1)，進行分裂操作。
(4)兩個聚類中心之間所允許最小距離Dmin。如果兩個類靠得非常近(即這 兩個類別對應聚類中心之間的距離非常小)，小於該閾值時，則對這兩個類進行
合並操作。
如果希望樣本不劃分到單一的類中，可以使用模糊C均值或者高斯混合模型， 高斯混合模型會在下一節中詳細講述。

K均值聚類的迭代演算法實際上是一種最大期望演算法 (Expectation-Maximization algorithm)，簡稱EM演算法。EM演算法解決的是在概率模 型中含有無法觀測的隱含變數情況下的參數估計問題。
EM演算法只保證收斂到局部最優解

❾ 八：聚類演算法K-means（20191223-29)

學習內容：無監督聚類演算法K-Means

k-means：模型原理、收斂過程、超參數的選擇

聚類分析是在數據中發現數據對象之間的關系，將數據進行分組，組內的相似性越大，組間的差別越大，則聚類效果越好。

不同的簇類型： 聚類旨在發現有用的對象簇，在現實中我們用到很多的簇的類型，使用不同的簇類型劃分數據的結果是不同的。

基於原型的： 簇是對象的集合，其中每個對象到定義該簇的 原型 的距離比其他簇的原型距離更近，如(b)所示的原型即為中心點，在一個簇中的數據到其中心點比到另一個簇的中心點更近。這是一種常見的 基於中心的簇 ，最常用的K-Means就是這樣的一種簇類型。 這樣的簇趨向於球形。

基於密度的 ：簇是對象的密度區域，(d)所示的是基於密度的簇，當簇不規則或相互盤繞，並且有早上和離群點事，常常使用基於密度的簇定義。

關於更多的簇介紹參考《數據挖掘導論》。

基本的聚類分析演算法

     1. K均值： 基於原型的、劃分的距離技術，它試圖發現用戶指定個數(K)的簇。

     2. 凝聚的層次距離： 思想是開始時，每個點都作為一個單點簇，然後，重復的合並兩個最靠近的簇，直到嘗試單個、包含所有點的簇。

     3. DBSCAN: 一種基於密度的劃分距離的演算法，簇的個數有演算法自動的確定，低密度中的點被視為雜訊而忽略，因此其不產生完全聚類。

不同的距離量度會對距離的結果產生影響，常見的距離量度如下所示：

優點：易於實現 

缺點：可能收斂於局部最小值，在大規模數據收斂慢

演算法思想：

選擇K個點作為初始質心 

repeat

    將每個點指派到最近的質心，形成K個簇 

    重新計算每個簇的質心  

until 簇不發生變化或達到最大迭代次數

這里的「重新計算每個簇的質心」，是根據目標函數來計算的，因此在開始時要考慮 距離度量和目標函數。

考慮歐幾里得距離的數據，使用 誤差平方和（Sum of the Squared Error,SSE） 作為聚類的目標函數，兩次運行K均值產生的兩個不同的簇集，使用SSE最小的那個。

k表示k個聚類中心，ci表示第幾個中心，dist表示的是歐幾里得距離。 

這里有一個問題就是為什麼，我們更新質心是讓所有的點的平均值，這里就是SSE所決定的。

k均值演算法非常簡單且使用廣泛，但是其有主要的兩個缺陷：

1. K值需要預先給定 ，屬於預先知識，很多情況下K值的估計是非常困難的，對於像計算全部微信用戶的交往圈這樣的場景就完全的沒辦法用K-Means進行。對於可以確定K值不會太大但不明確精確的K值的場景，可以進行迭代運算，然後找出Cost Function最小時所對應的K值，這個值往往能較好的描述有多少個簇類。

2. K-Means演算法對初始選取的聚類中心點是敏感的 ，不同的隨機種子點得到的聚類結果完全不同

3. K均值演算法並不是很所有的數據類型。 它不能處理非球形簇、不同尺寸和不同密度的簇，銀冠指定足夠大的簇的個數是他通常可以發現純子簇。

4. 對離群點的數據進行聚類時，K均值也有問題 ，這種情況下，離群點檢測和刪除有很大的幫助。

下面對初始質心的選擇進行討論：

當初始質心是隨機的進行初始化的時候，K均值的每次運行將會產生不同的SSE,而且隨機的選擇初始質心結果可能很糟糕，可能只能得到局部的最優解，而無法得到全局的最優解。

多次運行，每次使用一組不同的隨機初始質心，然後選擇一個具有最小的SSE的簇集。該策略非常的簡單，但是效果可能不是很好，這取決於數據集合尋找的簇的個數。

關於更多，參考《數據挖掘導論》

為了克服K-Means演算法收斂於局部最小值的問題，提出了一種 二分K-均值(bisecting K-means)

將所有的點看成是一個簇

當簇小於數目k時

    對於每一個簇

        計算總誤差

        在給定的簇上進行K-均值聚類,k值為2        計算將該簇劃分成兩個簇後總誤差

    選擇是的誤差最小的那個簇進行劃分

在原始的K-means演算法中，每一次的劃分所有的樣本都要參與運算，如果數據量非常大的話，這個時間是非常高的，因此有了一種分批處理的改進演算法。

使用Mini Batch（分批處理）的方法對數據點之間的距離進行計算。

Mini Batch的好處：不必使用所有的數據樣本，而是從不同類別的樣本中抽取一部分樣本來代表各自類型進行計算。n 由於計算樣本量少，所以會相應的減少運行時間n 但另一方面抽樣也必然會帶來准確度的下降。

聚類試圖將數據集中的樣本劃分為若干個通常是不相交的子集，每個子集成為一個「簇」。通過這樣的劃分，每個簇可能對應於一些潛在的概念（也就是類別）；需說明的是，這些概念對聚類演算法而言事先是未知的，聚類過程僅能自動形成簇結構，簇對應的概念語義由使用者來把握和命名。

聚類是無監督的學習演算法，分類是有監督的學習演算法。所謂有監督就是有已知標簽的訓練集（也就是說提前知道訓練集里的數據屬於哪個類別），機器學習演算法在訓練集上學習到相應的參數，構建模型，然後應用到測試集上。而聚類演算法是沒有標簽的，聚類的時候，需要實現的目標只是把相似的東西聚到一起。

聚類的目的是把相似的樣本聚到一起，而將不相似的樣本分開，類似於「物以類聚」，很直觀的想法是同一個簇中的相似度要盡可能高，而簇與簇之間的相似度要盡可能的低。

性能度量大概可分為兩類： 一是外部指標， 二是內部指標 。

外部指標：將聚類結果和某個「參考模型」進行比較。

內部指標：不利用任何參考模型，直接考察聚類結果。

對於給定的樣本集，按照樣本之間的距離大小，將樣本集劃分為K個簇。讓簇內的點盡量緊密的連在一起，而讓簇間的距離盡量的大

初學者會很容易就把K-Means和KNN搞混，其實兩者的差別還是很大的。

K-Means是無監督學習的聚類演算法，沒有樣本輸出；而KNN是監督學習的分類演算法，有對應的類別輸出。KNN基本不需要訓練，對測試集裡面的點，只需要找到在訓練集中最近的k個點，用這最近的k個點的類別來決定測試點的類別。而K-Means則有明顯的訓練過程，找到k個類別的最佳質心，從而決定樣本的簇類別。

當然，兩者也有一些相似點，兩個演算法都包含一個過程，即找出和某一個點最近的點。兩者都利用了最近鄰(nearest neighbors)的思想。

優點：

簡單， 易於理解和實現 ；收斂快，一般僅需5-10次迭代即可，高效

缺點：

    1，對K值得選取把握不同對結果有很大的不同

    2，對於初始點的選取敏感，不同的隨機初始點得到的聚類結果可能完全不同

    3，對於不是凸的數據集比較難收斂

    4，對噪點過於敏感，因為演算法是根據基於均值的

    5，結果不一定是全局最優，只能保證局部最優

    6，對球形簇的分組效果較好，對非球型簇、不同尺寸、不同密度的簇分組效果不好。

K-means演算法簡單理解，易於實現（局部最優），卻會有對初始點、雜訊點敏感等問題；還容易和監督學習的分類演算法KNN混淆。

參考閱讀：

1.《 深入理解K-Means聚類演算法 》

2.《 K-Means 》

❿ Kmeans聚類演算法簡介

由於具有出色的速度和良好的可擴展性，Kmeans聚類演算法算得上是最著名的聚類方法。Kmeans演算法是一個重復移動類中心點的過程，把類的中心點，也稱重心(centroids)，移動到其包含成員的平均位置，然後重新劃分其內部成員。k是演算法計算出的超參數，表示類的數量；Kmeans可以自動分配樣本到不同的類，但是不能決定究竟要分幾個類。k必須是一個比訓練集樣本數小的正整數。有時，類的數量是由問題內容指定的。例如，一個鞋廠有三種新款式，它想知道每種新款式都有哪些潛在客戶，於是它調研客戶，然後從數據里找出三類。也有一些問題沒有指定聚類的數量，最優的聚類數量是不確定的。後面我將會詳細介紹一些方法來估計最優聚類數量。

Kmeans的參數是類的重心位置和其內部觀測值的位置。與廣義線性模型和決策樹類似，Kmeans參數的最優解也是以成本函數最小化為目標。Kmeans成本函數公式如下：

μiμi是第kk個類的重心位置。成本函數是各個類畸變程度(distortions)之和。每個類的畸變程度等於該類重心與其內部成員位置距離的平方和。若類內部的成員彼此間越緊湊則類的畸變程度越小，反之，若類內部的成員彼此間越分散則類的畸變程度越大。求解成本函數最小化的參數就是一個重復配置每個類包含的觀測值，並不斷移動類重心的過程。首先，類的重心是隨機確定的位置。實際上，重心位置等於隨機選擇的觀測值的位置。每次迭代的時候，Kmeans會把觀測值分配到離它們最近的類，然後把重心移動到該類全部成員位置的平均值那裡。

2.1 根據問題內容確定

這種方法就不多講了，文章開篇就舉了一個例子。

2.2 肘部法則

如果問題中沒有指定kk的值，可以通過肘部法則這一技術來估計聚類數量。肘部法則會把不同kk值的成本函數值畫出來。隨著kk值的增大，平均畸變程度會減小；每個類包含的樣本數會減少，於是樣本離其重心會更近。但是，隨著kk值繼續增大，平均畸變程度的改善效果會不斷減低。kk值增大過程中，畸變程度的改善效果下降幅度最大的位置對應的kk值就是肘部。為了讓讀者看的更加明白，下面讓我們通過一張圖用肘部法則來確定最佳的kk值。下圖數據明顯可分成兩類：

從圖中可以看出，k值從1到2時，平均畸變程度變化最大。超過2以後，平均畸變程度變化顯著降低。因此最佳的k是2。

2.3 與層次聚類結合

經常會產生較好的聚類結果的一個有趣策略是，首先採用層次凝聚演算法決定結果粗的數目，並找到一個初始聚類，然後用迭代重定位來改進該聚類。

2.4 穩定性方法

穩定性方法對一個數據集進行2次重采樣產生2個數據子集，再用相同的聚類演算法對2個數據子集進行聚類，產生2個具有kk個聚類的聚類結果，計算2個聚類結果的相似度的分布情況。2個聚類結果具有高的相似度說明kk個聚類反映了穩定的聚類結構，其相似度可以用來估計聚類個數。採用次方法試探多個kk，找到合適的k值。

2.5 系統演化方法

系統演化方法將一個數據集視為偽熱力學系統，當數據集被劃分為kk個聚類時稱系統處於狀態kk。系統由初始狀態k=1k=1出發，經過分裂過程和合並過程，系統將演化到它的穩定平衡狀態 kiki ，其所對應的聚類結構決定了最優類數 kiki 。系統演化方法能提供關於所有聚類之間的相對邊界距離或可分程度，它適用於明顯分離的聚類結構和輕微重疊的聚類結構。

2.6 使用canopy演算法進行初始劃分

基於Canopy Method的聚類演算法將聚類過程分為兩個階段

(1) 聚類最耗費計算的地方是計算對象相似性的時候，Canopy Method在第一階段選擇簡單、計算代價較低的方法計算對象相似性，將相似的對象放在一個子集中，這個子集被叫做Canopy，通過一系列計算得到若干Canopy，Canopy之間可以是重疊的，但不會存在某個對象不屬於任何Canopy的情況，可以把這一階段看做數據預處理；

(2) 在各個Canopy內使用傳統的聚類方法(如Kmeans)，不屬於同一Canopy的對象之間不進行相似性計算。

從這個方法起碼可以看出兩點好處：首先，Canopy不要太大且Canopy之間重疊的不要太多的話會大大減少後續需要計算相似性的對象的個數；其次，類似於Kmeans這樣的聚類方法是需要人為指出K的值的，通過(1)得到的Canopy個數完全可以作為這個k值，一定程度上減少了選擇k的盲目性。

其他方法如貝葉斯信息准則方法(BIC)可參看文獻[4]。

選擇適當的初始質心是基本kmeans演算法的關鍵步驟。常見的方法是隨機的選取初始中心，但是這樣簇的質量常常很差。處理選取初始質心問題的一種常用技術是：多次運行，每次使用一組不同的隨機初始質心，然後選取具有最小SSE(誤差的平方和)的簇集。這種策略簡單，但是效果可能不好，這取決於數據集和尋找的簇的個數。

第二種有效的方法是，取一個樣本，並使用層次聚類技術對它聚類。從層次聚類中提取kk個簇，並用這些簇的質心作為初始質心。該方法通常很有效，但僅對下列情況有效：(1)樣本相對較小，例如數百到數千(層次聚類開銷較大)；(2) kk相對於樣本大小較小。

第三種選擇初始質心的方法，隨機地選擇第一個點，或取所有點的質心作為第一個點。然後，對於每個後繼初始質心，選擇離已經選取過的初始質心最遠的點。使用這種方法，確保了選擇的初始質心不僅是隨機的，而且是散開的。但是，這種方法可能選中離群點。此外，求離當前初始質心集最遠的點開銷也非常大。為了克服這個問題，通常該方法用於點樣本。由於離群點很少(多了就不是離群點了)，它們多半不會在隨機樣本中出現。計算量也大幅減少。

第四種方法就是上面提到的canopy演算法。

常用的距離度量方法包括：歐幾里得距離和餘弦相似度。兩者都是評定個體間差異的大小的。

歐氏距離是最常見的距離度量，而餘弦相似度則是最常見的相似度度量，很多的距離度量和相似度度量都是基於這兩者的變形和衍生，所以下面重點比較下兩者在衡量個體差異時實現方式和應用環境上的區別。

藉助三維坐標系來看下歐氏距離和餘弦相似度的區別：

從圖上可以看出距離度量衡量的是空間各點間的絕對距離，跟各個點所在的位置坐標(即個體特徵維度的數值)直接相關；而餘弦相似度衡量的是空間向量的夾角，更加的是體現在方向上的差異，而不是位置。如果保持A點的位置不變，B點朝原方向遠離坐標軸原點，那麼這個時候餘弦相似cosθ是保持不變的，因為夾角不變，而A、B兩點的距離顯然在發生改變，這就是歐氏距離和餘弦相似度的不同之處。

根據歐氏距離和餘弦相似度各自的計算方式和衡量特徵，分別適用於不同的數據分析模型：歐氏距離能夠體現個體數值特徵的絕對差異，所以更多的用於需要從維度的數值大小中體現差異的分析，如使用用戶行為指標分析用戶價值的相似度或差異；而餘弦相似度更多的是從方向上區分差異，而對絕對的數值不敏感，更多的用於使用用戶對內容評分來區分用戶興趣的相似度和差異，同時修正了用戶間可能存在的度量標准不統一的問題(因為餘弦相似度對絕對數值不敏感)。

因為歐幾里得距離度量會受指標不同單位刻度的影響，所以一般需要先進行標准化，同時距離越大，個體間差異越大；空間向量餘弦夾角的相似度度量不會受指標刻度的影響，餘弦值落於區間[-1,1]，值越大，差異越小。但是針對具體應用，什麼情況下使用歐氏距離，什麼情況下使用餘弦相似度？

從幾何意義上來說，n維向量空間的一條線段作為底邊和原點組成的三角形，其頂角大小是不確定的。也就是說對於兩條空間向量，即使兩點距離一定，他們的夾角餘弦值也可以隨意變化。感性的認識，當兩用戶評分趨勢一致時，但是評分值差距很大，餘弦相似度傾向給出更優解。舉個極端的例子，兩用戶只對兩件商品評分，向量分別為(3,3)和(5,5)，這兩位用戶的認知其實是一樣的，但是歐式距離給出的解顯然沒有餘弦值合理。

我們把機器學習定義為對系統的設計和學習，通過對經驗數據的學習，將任務效果的不斷改善作為一個度量標准。Kmeans是一種非監督學習，沒有標簽和其他信息來比較聚類結果。但是，我們還是有一些指標可以評估演算法的性能。我們已經介紹過類的畸變程度的度量方法。本節為將介紹另一種聚類演算法效果評估方法稱為輪廓系數(Silhouette Coefficient)。輪廓系數是類的密集與分散程度的評價指標。它會隨著類的規模增大而增大。彼此相距很遠，本身很密集的類，其輪廓系數較大，彼此集中，本身很大的類，其輪廓系數較小。輪廓系數是通過所有樣本計算出來的，計算每個樣本分數的均值，計算公式如下：

aa是每一個類中樣本彼此距離的均值，bb是一個類中樣本與其最近的那個類的所有樣本的距離的均值。

輸入：聚類個數k，數據集XmxnXmxn。

輸出：滿足方差最小標準的k個聚類。

(1) 選擇k個初始中心點，例如c[0]=X[0] , … , c[k-1]=X[k-1]；

(2) 對於X[0]….X[n]，分別與c[0]…c[k-1]比較，假定與c[i]差值最少，就標記為i；

(3) 對於所有標記為i點，重新計算c[i]={ 所有標記為i的樣本的每個特徵的均值}；

(4) 重復(2)(3)，直到所有c[i]值的變化小於給定閾值或者達到最大迭代次數。

Kmeans的時間復雜度：O(tkmn)，空間復雜度：O((m+k)n)。其中，t為迭代次數，k為簇的數目，m為樣本數，n為特徵數。

7.1 優點

(1). 演算法原理簡單。需要調節的超參數就是一個k。

(2). 由具有出色的速度和良好的可擴展性。

7.2 缺點

(1). 在 Kmeans 演算法中 kk 需要事先確定，這個 kk 值的選定有時候是比較難確定。

(2). 在 Kmeans 演算法中，首先需要初始k個聚類中心，然後以此來確定一個初始劃分，然後對初始劃分進行優化。這個初始聚類中心的選擇對聚類結果有較大的影響，一旦初始值選擇的不好，可能無法得到有效的聚類結果。多設置一些不同的初值，對比最後的運算結果，一直到結果趨於穩定結束。

(3). 該演算法需要不斷地進行樣本分類調整，不斷地計算調整後的新的聚類中心，因此當數據量非常大時，演算法的時間開銷是非常大的。

(4). 對離群點很敏感。

(5). 從數據表示角度來說，在 Kmeans 中,我們用單個點來對 cluster 進行建模，這實際上是一種最簡化的數據建模形式。這種用點來對 cluster 進行建模實際上就已經假設了各 cluster的數據是呈圓形(或者高維球形)或者方形等分布的。不能發現非凸形狀的簇。但在實際生活中，很少能有這種情況。所以在 GMM 中，使用了一種更加一般的數據表示，也就是高斯分布。

(6). 從數據先驗的角度來說，在 Kmeans 中,我們假設各個 cluster 的先驗概率是一樣的,但是各個 cluster 的數據量可能是不均勻的。舉個例子,cluster A 中包含了10000個樣本,cluster B 中只包含了100個。那麼對於一個新的樣本,在不考慮其與A cluster、 B cluster 相似度的情況,其屬於 cluster A 的概率肯定是要大於 cluster B的。

(7). 在 Kmeans 中，通常採用歐氏距離來衡量樣本與各個 cluster 的相似度。這種距離實際上假設了數據的各個維度對於相似度的衡量作用是一樣的。但在 GMM 中，相似度的衡量使用的是後驗概率 αcG(x|μc,∑c)αcG(x|μc,∑c) ，通過引入協方差矩陣,我們就可以對各維度數據的不同重要性進行建模。

(8). 在 Kmeans 中，各個樣本點只屬於與其相似度最高的那個 cluster ，這實際上是一種 hard clustering 。

針對Kmeans演算法的缺點，很多前輩提出了一些改進的演算法。例如 K-modes 演算法，實現對離散數據的快速聚類，保留了Kmeans演算法的效率同時將Kmeans的應用范圍擴大到離散數據。還有K-Prototype演算法，可以對離散與數值屬性兩種混合的數據進行聚類，在K-prototype中定義了一個對數值與離散屬性都計算的相異性度量標准。當然還有其它的一些演算法，這里我 就不一一列舉了。

Kmeans 與 GMM 更像是一種 top-down 的思想，它們首先要解決的問題是，確定 cluster 數量，也就是 k 的取值。在確定了 k 後,再來進行數據的聚類。而 hierarchical clustering 則是一種 bottom-up 的形式，先有數據，然後通過不斷選取最相似的數據進行聚類。