大數據聚類演算法知多少？如何無需編程快速實踐？演算法乾貨
歡迎關注數據超市微信公眾號
最近做的項目中用到了這幾個演算法（實際上是調用了大數據機器學習演算法的開源介面spark的ml庫）我也總結一下。
先說說聚類相關的內容：
（一）k-means演算法
k-means演算法是聚類分析中使用最廣泛的演算法之一
首先是k-means演算法，k-means演算法是聚類分析中使用最廣泛的演算法之一。
它把n個樣本根據它們的屬性特徵分為k個聚類，也常被稱作k個簇，以便使得所獲得的聚類滿足：同一聚類（同一個簇）中的樣本相似度較高；而不同聚類（不同簇）中的樣本相似度較小。
1、k-means演算法的基本過程如下所示：
（1）任意選擇k個初始中心c_,c_,...,c_ 。
（2）計算X中的每個樣本與這些中心的距離；並根據最小距離重新對相應樣本進行劃分。
（3）重新計算每個中心對象 C_ 的值。
（4）計算標準測度函數，當滿足一定條件，如函數收斂時，則演算法終止；如果條件不滿足則重複步驟（2），（3）。
2、k-means演算法的缺點，k-means演算法雖然簡單快速，但是存在下面的缺點：
（1） 聚類中心的個數K需要事先給定，但在實際中K值的選定是非常困難的，很多時候我們並不知道給定的數據集應該分成多少個類別才最合適。
（2） k-means演算法需要隨機地確定初始聚類中心，不同的初始聚類中心可能導致完全不同的聚類結果。
（3） 第一個缺陷我們很難在k-means演算法以及其改進演算法中解決，但是我們可以通過k-means++演算法來解決第二個缺陷。
（二）k-means++演算法
初始的聚類中心之間的相互距離要儘可能的遠
1、k-means++演算法選擇初始聚類中心的基本原則是：
初始的聚類中心之間的相互距離要儘可能的遠。它選擇初始聚類中心的步驟是：
（1）從輸入的數據點集合中隨機選擇一個點作為第一個聚類中心 c_ 。
（2）對於數據集中的每一個點x，計算它與最近聚類中心(指已選擇的聚類中心)的距離D(x)，並根據概率選擇新的聚類中心 c_ 。
（3）重複過程（2）直到找到k個聚類中心。
注意：第(2)步中，依次計算每個數據點與最近的種子點（聚類中心）的距離，依次得到D(1)、D(2)、...、D(n)構成的集合D，其中n表示數據集的大小。在D中，為了避免雜訊，不能直接選取值最大的元素，應該選擇值較大的元素，然後將其對應的數據點作為種子點（聚類中心）。
2、那麼如何選擇值較大的元素呢，下面是spark中實現的思路：
求所有的距離和Sum(D(x)) ，取一個隨機值，用權重的方式來取計算下一個「種子點」。這個演算法的實現是，先用Sum(D(x))乘以隨機值Random得到值r，然後用currSum += D(x)，直到其currSum > r，此時的點就是下一個「種子點」。
為什麼用這樣的方式呢？我們換一種比較好理解的方式來說明。把集合D中的每個元素D(x)想像為一根線L(x)，線的長度就是元素的值。將這些線依次按照L(1)、L(2)、...、L(n)的順序連接起來，組成長線L。L(1)、L(2)、…、L(n)稱為L的子線。 根據概率的相關知識，如果我們在L上隨機選擇一個點，那麼這個點所在的子線很有可能是比較長的子線，而這個子線對應的數據點就可以作為種子點。
(三）二分k-means演算法
二分k-means演算法是分層聚類（Hierarchical clustering）的一種
1、二分k-means演算法是分層聚類（Hierarchical clustering）的一種，分層聚類是聚類分析中常用的方法。
分層聚類的策略一般有兩種：
（1）聚合：這是一種自底向上的方法，每一個觀察者初始化本身為一類，然後兩兩結合分。
（2）分裂：這是一種自頂向下的方法，所有觀察者初始化為一類，然後遞歸地分裂它們二分k-means演算法是分裂法的一種。
2、二分k-means演算法是k-means演算法的改進演算法，相比k-means演算法，它有如下優點：
二分k-means演算法可以加速k-means演算法的執行速度，因為它的相似度計算少了能夠克服k-means收斂於局部最小的缺點。
二分k-means演算法的一般流程如下所示：
（1）把所有數據初始化為一個簇，將這個簇分為兩個簇。
（2）選擇滿足條件的可以分解的簇。選擇條件綜合考慮簇的元素個數以及聚類代價（也就是誤差平方和SSE）
（3）使用k-means演算法將可分裂的簇分為兩簇。
（4）一直重複（2）（3）步，直到滿足迭代結束條件。
以上過程隱含著一個原則是：因為聚類的誤差平方和能夠衡量聚類性能，該值越小表示數據點越接近於它們的質心，聚類效果就越好。 所以我們就需要對誤差平方和最大的簇進行再一次的劃分，因為誤差平方和越大，表示該簇聚類越不好，越有可能是多個簇被當成一個簇了，所以我們首先需要對這個簇進行劃分。
(四）高斯混合模型
數據可以看作是從多個高斯分布中生成出來
顧名思義，就是數據可以看作是從多個高斯分布中生成出來的。
從中心極限定理可以看出，高斯分布這個假設其實是比較合理的。 為什麼我們要假設數據是由若干個高斯分布組合而成的，而不假設是其他分布呢？實際上不管是什麼分布，只K取得足夠大，這個XX Mixture Model就會變得足夠複雜，就可以用來逼近任意連續的概率密度分布。只是因為高斯函數具有良好的計算性能，所GMM被廣泛地應用。
每個GMM由K個高斯分布組成，每個高斯分布稱為一個組件（Component），這些組件線性加成在一起就組成了GMM的概率密度函數。
如果我們要從GMM分布中隨機地取一個點，需要兩步：
1、隨機地在這K個組件之中選一個，每個組件被選中的概率實際上就是它的係數pi_k；選中了組件之後，再單獨地考慮從這個組件的分布中選取一個點。
2、怎樣用GMM來做聚類呢？其實很簡單，現在我們有了數據，假定它們是由GMM生成出來的，那麼我們只要根據數據推出GMM的概率分布來就可以了，然後GMM的K個組件實際上就對應了K個聚類了。
看了以上演算法，是否能夠快速的對數據做一個驗證呢？這裡有一個無需編程即可調用演算法組件的方式，谷歌瀏覽器打開www.BigData711.com註冊使用即可。先總結這麼多，希望對大家有幫助。
