kmeans聚類演算法類標簽

① K-Means 聚類演算法

問題導入

    假如有這樣一種情況，在一天你想去某個城市旅遊，這個城市裡你想去的有70個地方，現在你只有每一個地方的地址，這個地址列表很長，有70個位置。事先肯定要做好攻略，你要把一些比較接近的地方放在一起組成一組，這樣就可以安排交通工具抵達這些組的「某個地址」，然後步行到每個組內的地址。那麼，如何確定這些組，如何確定這些組的「某個地址」？答案就是聚類。而本文所提供的k-means聚類分析方法就可以用於解決這類問題。

一，聚類思想

        所謂聚類演算法是指將一堆沒有標簽的數據自動劃分成幾類的方法，屬於無監督學習方法，這個方法要保證同一類的數據有相似的特徵，如下圖：

        根據樣本之間的距離或者說相似性，把越相似，差異越小的樣本聚成一類（簇），最後形成多個簇，使同一個簇內部的樣本相似度高，不同簇之間差異性高。

二，K-Means聚類分析演算法

        K-Means是一種基於自下而上的聚類分析方法，基本概念就是空間中有N個點，初始選擇K個點作為中心聚類點，將N個點分別與K個點計算距離，選擇自己最近的點作為自己的中心點，不斷地更新中心聚集點。

相關概念：

        K值：要得到的簇的個數

        質心：每個簇的均值向量，即向量各維取品軍即可

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

        兩點之間的距離：

演算法流程：

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

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

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

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

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

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

K-means實現過程

K-means 聚類演算法是一種非監督學習演算法，被用於非標簽數據（data without defined categories or groups）。該演算法使用迭代細化來產生最終結果。演算法輸入的是集群的數量 K 和數據集。數據集是每個數據點的一組功能。

演算法從 Κ 質心的初始估計開始，其可以隨機生成或從數據集中隨機選擇 。然後演算法在下面兩個步驟之間迭代：

1.數據分配：

每個質心定義一個集群。在此步驟中，基於平方歐氏距離將每個數據點分配到其最近的質心。更正式一點， ci 屬於質心集合 C ，然後每個數據點 x 基於下面的公式被分配到一個集群中。

其中 dist（·）是標准（L2）歐氏距離。讓指向第 i 個集群質心的數據點集合定為 Si 。

2. 質心更新：

在此步驟中，重新計算質心。這是通過獲取分配給該質心集群的所有數據點的平均值來完成的。公式如下：

K-means 演算法在步驟 1 和步驟 2 之間迭代，直到滿足停止條件（即，沒有數據點改變集群，距離的總和最小化，或者達到一些最大迭代次數）。

K 值的選擇

上述演算法找到特定預選 K 值和數據集標簽。為了找到數據中的集群數，用戶需要針對一系列 K 值運行 K-means 聚類演算法並比較結果。通常，沒有用於確定 K 的精確值的方法，但是可以使用以下技術獲得准確的估計。

Elbow point 拐點方法

通常用於比較不同 K 值的結果的度量之一是數據點與其聚類質心之間的平均距離。由於增加集群的數量將總是減少到數據點的距離，因此當 K 與數據點的數量相同時，增加 K 將總是減小該度量，達到零的極值。因此，該指標不能用作唯一目標。相反，繪制了作為 K 到質心的平均距離的函數，並且可以使用減小率急劇變化的「拐點」來粗略地確定 K 。

DBI（Davies-Bouldin Index）

DBI 是一種評估度量的聚類演算法的指標，通常用於評估 K-means 演算法中 k 的取值。簡單的理解就是：DBI 是聚類內的距離與聚類外的距離的比值。所以，DBI 的數值越小，表示分散程度越低，聚類效果越好。

還存在許多用於驗證 K 的其他技術，包括交叉驗證，信息標准，信息理論跳躍方法，輪廓方法和 G 均值演算法等等。

三，數學原理

K-Means採用的啟發式很簡單，可以用下面一組圖來形象的描述：

上述a表達了初始的數據集，假設 k=2 。在圖b中，我們隨機選擇了兩個 k 類所對應的類別質點，即圖中的紅色質點和藍色質點，然後分別求樣本中所有點到這兩個質心的距離，並標記每個樣本類別為和該樣本距離最小的質心的類別，如圖c所示，經過計算樣本和紅色質心和藍色質心的距離，我們得到了所有樣本點的第一輪迭代後的類別。此時我們對我們當前標記為紅色和藍色的點分別求其新的質心，如圖d所示，新的紅色質心和藍色質心大熱位置已經發生了變化。圖e和圖f重復了我們在圖c和圖d的過程，即將所有點的類別標記為距離最近的質心的類別並求出新的質心。最終我們得到的兩個類別如圖f.

四，實例

坐標系中有六個點：

1、我們分兩組，令K等於2，我們隨機選擇兩個點：P1和P2

2、通過勾股定理計算剩餘點分別到這兩個點的距離：

3、第一次分組後結果：

        組A：P1

        組B：P2、P3、P4、P5、P6

4、分別計算A組和B組的質心：

        A組質心還是P1=（0，0）

        B組新的質心坐標為：P哥=（（1+3+8+9+10）/5，（2+1+8+10+7）/5）=（6.2，5.6）

5、再次計算每個點到質心的距離：

6、第二次分組結果：

        組A：P1、P2、P3

        組B：P4、P5、P6

7、再次計算質心：

        P哥1=（1.33，1） 

        P哥2=（9，8.33）

8、再次計算每個點到質心的距離：

9、第三次分組結果：

        組A：P1、P2、P3

        組B：P4、P5、P6

可以發現，第三次分組結果和第二次分組結果一致，說明已經收斂，聚類結束。

五、K-Means的優缺點

優點：

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

2、當結果簇是密集的，而簇與簇之間區別明顯時, 它的效果較好。

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

缺點：

1、K值需要預先給定，很多情況下K值的估計是非常困難的。

2、K-Means演算法對初始選取的質心點是敏感的，不同的隨機種子點得到的聚類結果完全不同 ，對結果影響很大。

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

4、採用迭代方法， 可能只能得到局部的最優解，而無法得到全局的最優解 。

六、細節問題

1、K值怎麼定？

答：分幾類主要取決於個人的經驗與感覺，通常的做法是多嘗試幾個K值，看分成幾類的結果更好解釋，更符合分析目的等。或者可以把各種K值算出的 E 做比較，取最小的 E 的K值。

2、初始的K個質心怎麼選？

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

3、關於離群值？

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

4、單位要一致！

        答：比如X的單位是米，Y也是米，那麼距離算出來的單位還是米，是有意義的。但是如果X是米，Y是噸，用距離公式計算就會出現「米的平方」加上「噸的平方」再開平方，最後算出的東西沒有數學意義，這就有問題了。

5、標准化

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

② 八：聚類演算法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 》

③ K-means 與KNN 聚類演算法

        K-means 演算法屬於聚類演算法的一種。聚類演算法就是把相似的對象通過靜態分類方法分成不同的組別或者更多的子集（subset），這樣讓在同一個子集中的成員對象都有相似的一些屬性。聚類演算法的任務是將數據集劃分為多個集群。在相同集群中的數據彼此會比不同集群的數據相似。通常來說，聚類演算法的目標就是通過相似特徵將數據分組並分配進不同的集群中。

K-means 聚類演算法是一種非監督學習演算法，被用於非標簽數據（data without defined categories or groups）。該演算法使用迭代細化來產生最終結果。演算法輸入的是集群的數量 K 和數據集。數據集是每個數據點的一組功能。  演算法從 Κ 質心的初始估計開始，其可以隨機生成或從數據集中隨機選擇 。然後演算法在下面兩個步驟之間迭代：

每個質心定義一個集群。在此步驟中，基於平方歐氏距離將每個數據點分配到其最近的質心。更正式一點， ci  屬於質心集合  C  ，然後每個數據點  x  基於下面的公式被分配到一個集群中。

在此步驟中，重新計算質心。這是通過獲取分配給該質心集群的所有數據點的平均值來完成的。公式如下：

K-means 演算法在步驟 1 和步驟 2 之間迭代，直到滿足停止條件（即，沒有數據點改變集群，距離的總和最小化，或者達到一些最大迭代次數）。

上述演算法找到特定預選 K 值和數據集標簽。為了找到數據中的集群數，用戶需要針對一系列 K 值運行 K-means 聚類演算法並比較結果。通常，沒有用於確定 K 的精確值的方法，但是可以使用以下技術獲得准確的估計。

Elbow point 拐點方法

通常用於比較不同 K 值的結果的度量之一是數據點與其聚類質心之間的平均距離。由於增加集群的數量將總是減少到數據點的距離，因此當 K 與數據點的數量相同時，增加 K 將總是減小該度量，達到零的極值。因此，該指標不能用作唯一目標。相反，繪制了作為 K 到質心的平均距離的函數，並且可以使用減小率急劇變化的「拐點」來粗略地確定 K 。

DBI（Davies-Bouldin Index）

DBI 是一種評估度量的聚類演算法的指標，通常用於評估 K-means 演算法中 k 的取值。簡單的理解就是：DBI 是聚類內的距離與聚類外的距離的比值。所以，DBI 的數值越小，表示分散程度越低，聚類效果越好。

還存在許多用於驗證 K 的其他技術，包括交叉驗證，信息標准，信息理論跳躍方法，輪廓方法和 G 均值演算法等等。

需要提前確定 K 的選值或者需嘗試很多 K 的取值

數據必須是數字的，可以通過歐氏距離比較

對特殊數據敏感，很容易受特殊數據影響

對初始選擇的質心/中心（centers）敏感

之前介紹了  KNN （K 鄰近）演算法 ，感覺這兩個演算法的名字很接近，下面做一個簡略對比。

K-means  ：

聚類演算法

用於非監督學習

使用無標簽數據

需要訓練過程

K-NN ：

分類演算法

用於監督學習

使用標簽數據

沒有明顯的訓練過程

鄰近演算法，或者說K最近鄰(kNN，k-NearestNeighbor)分類演算法是數據挖掘分類技術中最簡單的方法之一。所謂K最近鄰，就是k個最近的鄰居的意思，說的是每個樣本都可以用它最接近的k個鄰居來代表。Cover和Hart在1968年提出了最初的鄰近演算法。KNN是一種分類(classification)演算法，它輸入基於實例的學習（instance-based learning），屬於懶惰學習（lazy learning）即KNN沒有顯式的學習過程，也就是說沒有訓練階段，數據集事先已有了分類和特徵值，待收到新樣本後直接進行處理。與急切學習（eager learning）相對應。

KNN是通過測量不同特徵值之間的距離進行分類。 

思路是：如果一個樣本在特徵空間中的k個最鄰近的樣本中的大多數屬於某一個類別，則該樣本也劃分為這個類別。KNN演算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。

提到KNN，網上最常見的就是下面這個圖，可以幫助大家理解。

我們要確定綠點屬於哪個顏色（紅色或者藍色），要做的就是選出距離目標點距離最近的k個點，看這k個點的大多數顏色是什麼顏色。當k取3的時候，我們可以看出距離最近的三個，分別是紅色、紅色、藍色，因此得到目標點為紅色。

演算法的描述：

1）計算測試數據與各個訓練數據之間的距離；

2）按照距離的遞增關系進行排序；

3）選取距離最小的K個點；

4）確定前K個點所在類別的出現頻率；

5）返回前K個點中出現頻率最高的類別作為測試數據的預測分類

二、關於 K 的取值

K：臨近數，即在預測目標點時取幾個臨近的點來預測。

K值得選取非常重要，因為：

如果當K的取值過小時，一旦有雜訊得成分存在們將會對預測產生比較大影響，例如取K值為1時，一旦最近的一個點是雜訊，那麼就會出現偏差，K值的減小就意味著整體模型變得復雜，容易發生過擬合；

如果K的值取的過大時，就相當於用較大鄰域中的訓練實例進行預測，學習的近似誤差會增大。這時與輸入目標點較遠實例也會對預測起作用，使預測發生錯誤。K值的增大就意味著整體的模型變得簡單；

如果K==N的時候，那麼就是取全部的實例，即為取實例中某分類下最多的點，就對預測沒有什麼實際的意義了；

K的取值盡量要取奇數，以保證在計算結果最後會產生一個較多的類別，如果取偶數可能會產生相等的情況，不利於預測。

K的取法：

 常用的方法是從k=1開始，使用檢驗集估計分類器的誤差率。重復該過程，每次K增值1，允許增加一個近鄰。選取產生最小誤差率的K。

一般k的取值不超過20，上限是n的開方，隨著數據集的增大，K的值也要增大。

三、關於距離的選取

距離就是平面上兩個點的直線距離

關於距離的度量方法，常用的有：歐幾里得距離、餘弦值（cos）, 相關度 （correlation）, 曼哈頓距離 （Manhattan distance）或其他。

Euclidean Distance 定義：

兩個點或元組P1=（x1，y1）和P2=（x2，y2）的歐幾里得距離是

距離公式為：（多個維度的時候是多個維度各自求差）

四、總結

KNN演算法是最簡單有效的分類演算法，簡單且容易實現。當訓練數據集很大時，需要大量的存儲空間，而且需要計算待測樣本和訓練數據集中所有樣本的距離，所以非常耗時

KNN對於隨機分布的數據集分類效果較差，對於類內間距小，類間間距大的數據集分類效果好，而且對於邊界不規則的數據效果好於線性分類器。

KNN對於樣本不均衡的數據效果不好，需要進行改進。改進的方法時對k個近鄰數據賦予權重，比如距離測試樣本越近，權重越大。

KNN很耗時，時間復雜度為O(n)，一般適用於樣本數較少的數據集，當數據量大時，可以將數據以樹的形式呈現，能提高速度，常用的有kd-tree和ball-tree。

④ 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 的形式，先有數據，然後通過不斷選取最相似的數據進行聚類。

⑤ kmeans聚類演算法是什麼

kmeans聚類演算法是將樣本聚類成k個簇（cluster）。

K-Means演算法的思想很簡單，對於給定的樣本集，按照樣本之間的距離大小，將樣本集劃分為K個簇。讓簇內的點盡量緊密的連在一起，而讓簇間的距離盡量的大。在實際K-Mean演算法中，我們一般會多次運行圖c和圖d，才能達到最終的比較優的類別。

用數據表達式表示

假設簇劃分為$(C_1,C_2,...C_k)$，則我們的目標是最小化平方誤差E：$$ E = sumlimits_{i=1}^ksumlimits_{x in C_i} ||x-mu_i||_2^2$$。

其中$mu_i$是簇$C_i$的均值向量，有時也稱為質心，表達式為：$$mu_i = frac{1}{|C_i|}sumlimits_{x in C_i}x$$。

⑥ 聚類演算法 - kmeans

kmeans即k均值演算法。k均值聚類是最著名的劃分聚類演算法，由於簡潔和效率使得他成為所有聚類演算法中最廣泛使用的。給定一個數據點集合和需要的聚類數目k，k由用戶指定，k均值演算法根據某個距離函數反復把數據分入k個聚類中。

簡易動畫過程在這， 傳送門
第一步 ，輸入k的值，即我們希望將數據集經過聚類得到k類，分為k組
第二步 ，從數據集中隨機選擇k個數據點作為初識的聚類中心（質心，Centroid）
第三步 ，對集合中每一個數據點，計算與每一個聚類中心的距離，離哪個中心距離近，就標記為哪個中心。待分配完全時，就有第一次分類。
第四步 ，每一個分類根據現有的數據重新計算，並重新選取每個分類的中心（質心）
第五至N步 ，重復第三至四步，直至符合條件結束迭代步驟。條件是如果新中心和舊中心之間的距離小於某一個設置的閾值（表示重新計算的質心的位置變化不大，趨於穩定，或者說收斂），可以認為我們進行的聚類已經達到期望的結果，終止迭代過程。

該演算法的核心就是選擇合適的k值，不同的k值出來有不同的結果。

手肘法的核心指標是SSE(sum of the squared errors，誤差平方和)，

其中，Ci是第i個簇，p是Ci中的樣本點，mi是Ci的質心（Ci中所有樣本的均值），SSE是所有樣本的聚類誤差，代表了聚類效果的好壞。

手肘法的核心思想是：隨著聚類數k的增大，樣本劃分會更加精細，每個簇的聚合程度會逐漸提高，那麼誤差平方和SSE自然會逐漸變小。並且，當k小於真實聚類數時，由於k的增大會大幅增加每個簇的聚合程度，故SSE的下降幅度會很大，而當k到達真實聚類數時，再增加k所得到的聚合程度回報會迅速變小，所以SSE的下降幅度會驟減，然後隨著k值的繼續增大而趨於平緩，也就是說SSE和k的關系圖是一個手肘的形狀，而這個肘部對應的k值就是數據的真實聚類數。當然，這也是該方法被稱為手肘法的原因。

該方法的核心指標是輪廓系數（Silhouette Coefficient），某個樣本點Xi的輪廓系數定義如下：

其中，a是Xi與同簇的其他樣本的平均距離，稱為凝聚度，b是Xi與最近簇中所有樣本的平均距離，稱為分離度。而最近簇的定義是

其中p是某個簇Ck中的樣本。事實上，簡單點講，就是用Xi到某個簇所有樣本平均距離作為衡量該點到該簇的距離後，選擇離Xi最近的一個簇作為最近簇。

求出所有樣本的輪廓系數後再求平均值就得到了 平均輪廓系數 。平均輪廓系數的取值范圍為[-1,1]，且簇內樣本的距離越近，簇間樣本距離越遠，平均輪廓系數越大，聚類效果越好。那麼，很自然地，平均輪廓系數最大的k便是最佳聚類數。

（1）容易理解，聚類效果不錯，雖然是局部最優， 但往往局部最優就夠了
（2）處理大數據集的時候，該演算法可以保證較好的伸縮性
（3）當簇近似高斯分布的時候，效果非常不錯
（4）演算法復雜度低

（1）K 值需要人為設定，不同 K 值得到的結果不一樣
（2）對初始的簇中心敏感，不同選取方式會得到不同結果
（3）對異常值敏感
（4）樣本只能歸為一類，不適合多分類任務
（5）不適合太離散的分類、樣本類別不平衡的分類、非凸形狀的分類

⑦ kmeans聚類演算法是什麼

K-means演算法是最為經典的基於劃分的聚類方法，是十大經典數據挖掘演算法之一。K-means演算法的基本思想是：以空間中k個點為中心進行聚類，對最靠近他們的對象歸類。通過迭代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結果。

聚類屬於無監督學習，以往的回歸、樸素貝葉斯、SVM等都是有類別標簽y的，也就是說樣例中已經給出了樣例的分類。而聚類的樣本中卻沒有給定y，只有特徵x，比如假設宇宙中的星星可以表示成三維空間中的點集。

(7)kmeans聚類演算法類標簽擴展閱讀：

k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個「中心對象」（引力中心）來進行計算的。

（1）適當選擇c個類的初始中心；

（2）在第k次迭代中，對任意一個樣本，求其到c個中心的距離，將該樣本歸到距離最短的中心所在的類；

（3）利用均值等方法更新該類的中心值；

（4）對於所有的c個聚類中心，如果利用（2）（3）的迭代法更新後，值保持不變，則迭代結束，否則繼續迭代。

⑧ 聚類演算法--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個類別的最佳質心，從而決定樣本的簇類別。當然，兩者也有一些相似點，兩個演算法都包含一個過程，即找出和某一個點最近的點。 兩周都利用了最近鄰的思想 。