kmeans演算法實現
K-MEANS演算法:
k-means 演算法接受輸入量 k ；然後將n個數據對象劃分為 k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個「中心對象」（引力中心）來進行計算的。
k-means 演算法的工作過程說明如下：首先從n個數據對象任意選擇 k 個對象作為初始聚類中心；而對於所剩下其它對象，則根據它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；然後再計算每個所獲新聚類的聚類中心（該聚類中所有對象的均值）；不斷重復這一過程直到標准測度函數開始收斂為止。一般都採用均方差作為標准測度函數. k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。
具體如下：
輸入：k, data[n];
（1） 選擇k個初始中心點，例如c[0]=data[0],…c[k-1]=data[k-1];
（2） 對於data[0]….data[n], 分別與c[0]…c[n-1]比較，假定與c[i]差值最少，就標記為i;
（3） 對於所有標記為i點，重新計算c[i]=/標記為i的個數；
（4） 重復(2)(3),直到所有c[i]值的變化小於給定閾值。
演算法實現起來應該很容易，就不幫你編寫代碼了。
B. 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
C. 如何編寫求K-均值聚類演算法的Matlab程序
在聚類分析中，K-均值聚類演算法(k-means
algorithm)是無監督分類中的一種基本方法，其也稱為C-均值演算法，其基本思想是:通過迭代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結果。
假設要把樣本集分為c個類別，演算法如下:
(1)適當選擇c個類的初始中心;
(2)在第k次迭代中，對任意一個樣本，求其到c個中心的距離，將該樣本歸到距離最短的中心所在的類，
(3)利用均值等方法更新該類的中心值;
(4)對於所有的c個聚類中心，如果利用(2)(3)的迭代法更新後，值保持不變，則迭代結束，否則繼續迭代。
下面介紹作者編寫的一個分兩類的程序，可以把其作為函數調用。
%%
function
[samp1,samp2]=kmeans(samp);
作為調用函數時去掉注釋符
samp=[11.1506
6.7222
2.3139
5.9018
11.0827
5.7459
13.2174
13.8243
4.8005
0.9370
12.3576];
%樣本集
[l0
l]=size(samp);
%%利用均值把樣本分為兩類，再將每類的均值作為聚類中心
th0=mean(samp);n1=0;n2=0;c1=0.0;c1=double(c1);c2=c1;for
i=1:lif
samp(i)<th0
c1=c1+samp(i);n1=n1+1;elsec2=c2+samp(i);n2=n2+1;endendc1=c1/n1;c2=c2/n2;
%初始聚類中心t=0;cl1=c1;cl2=c2;
c11=c1;c22=c2;
%聚類中心while
t==0samp1=zeros(1,l);
samp2=samp1;n1=1;n2=1;for
i=1:lif
abs(samp(i)-c11)<abs(samp(i)-c22)
samp1(n1)=samp(i);
cl1=cl1+samp(i);n1=n1+1;
c11=cl1/n1;elsesamp2(n2)=samp(i);
cl2=cl2+samp(i);n2=n2+1;
c22=cl2/n2;endendif
c11==c1
&&
c22==c2t=1;endcl1=c11;cl2=c22;
c1=c11;c2=c22;
end
%samp1,samp2為聚類的結果。
初始中心值這里採用均值的辦法，也可以根據問題的性質，用經驗的方法來確定，或者將樣本集隨機分成c類，計算每類的均值。
k-均值演算法需要事先知道分類的數量，這是其不足之處。
D. K-Means聚類演算法
所謂聚類演算法是指將一堆沒有標簽的數據自動劃分成幾類的方法，屬於無監督學習方法，這個方法要保證同一類的數據有相似的特徵，如下圖所示：
根據樣本之間的距離或者說是相似性（親疏性），把越相似、差異越小的樣本聚成一類（簇），最後形成多個簇，使同一個簇內部的樣本相似度高，不同簇之間差異性高。
相關概念：
K值 ：要得到的簇的個數
質心 ：每個簇的均值向量，即向量各維取平均即可
距離量度 ：常用歐幾里得距離和餘弦相似度（先標准化）
演算法流程：
1、首先確定一個k值，即我們希望將數據集經過聚類得到k個集合。
2、從數據集中隨機選擇k個數據點作為質心。
3、對數據集中每一個點，計算其與每一個質心的距離（如歐式距離），離哪個質心近，就劃分到那個質心所屬的集合。
4、把所有數據歸好集合後，一共有k個集合。然後重新計算每個集合的質心。
5、如果新計算出來的質心和原來的質心之間的距離小於某一個設置的閾值（表示重新計算的質心的位置變化不大，趨於穩定，或者說收斂），我們可以認為聚類已經達到期望的結果，演算法終止。
6、如果新質心和原質心距離變化很大，需要迭代3~5步驟。
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
可以發現，第三次分組結果和第二次分組結果一致，說明已經收斂，聚類結束。
優點：
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、例子、細節