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、循環叠代第二步和第三步操作，直到中心點穩定或者達到叠代次數，停止計算操作。
/p/f0727880c9c0