K-means系列

K-means 的缺點，及後續的改進方案。

• 依賴初始化，不同的初始化對應結果可能不同——k-means++；
• 可能收斂局部最小——二分kmeans（或者多次運作，合并結果）
• 需要制定K值，即聚類中心的個數——iosdata；
• 異常值敏感——k-medium；
• 聚類結果為超球體——kernel、GMMs。
• 海量資料——minibachk-means

原始k-means

• 1 初始選擇K個類别中心。
• 2 将每個樣本标記為距離類别中心最近的那個類别。
• 3 将每個類别中心更新為隸屬該類别所有點的中心。
• 4 重複2,3兩步若幹次直至終止條件（疊代步數，簇中心變化率，MSE等等）

k-means++

        嘗試解決初始化聚類中心的問題。

二分K-均值(bisecting K-means)

為了克服K-Means算法收斂于局部最小值的問題

算法的僞代碼如下：

    将所有的點看成是一個簇

    當簇小于數目k時

        對于每一個簇

            計算總誤差

            在給定的簇上進行K-均值聚類,k值為2

            計算将該簇劃分成兩個簇後總誤差

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

注意：其中誤差可以選擇歐式距離等度量名額

IOSDATA

     該算法能夠在聚類過程中根據各個類所包含樣本的實際情況動态調整聚類中心的數目。如果某個類中樣本分散程度較大（通過方差進行衡量）并且樣本數量較大，則對其進行分裂操作；如果某兩個類别靠得比較近（通過聚類中心的距離衡量），則對它們進行合并操作。

     該方法并不是真的不限制類别數，最終的類别數為輸入類别數的1/2-2倍之間，而且該算法需要：預期的聚類中心數目Ko、每個類所要求的最少樣本數目Nmin最大方差Sigma、兩個類别對應聚類中心之間所允許最小距離dmin，四個參數，是以并不常用。

k-means,k-medians和k-medoids

    差別在于如何計算一個中心點代表整個cluster（讓N對N的計算變為N對1）：

    k-means： 算中心點時，每個屬性（attribute）單獨算，距離函數是L2norm。每個屬性可能是資料中沒出現過的值。

    k-medians： 算中心點時，每個屬性單獨算，距離函數是L1norm。每個屬性是資料中出現過的值，但可能來至于不同資料點，是以中心點可能在資料中沒出現過。這是attribute意義上的median。

    k-medoids： 算中心點時，所有屬性一起算，距離函數是自定。中心點在資料中出現過。這是資料點意義上的median。用處是處理非歐式空間的資料，比如分類問題。

Mini batch k-means

    與K均值算法相比，資料的更新是在每一個小的樣本集上。對于每一個小批量，通過計算平均值得到更新質心，并把小批量裡的資料配置設定給該質心，随着疊代次數的增加，這些質心的變化是逐漸減小的，直到質心穩定或者達到指定的疊代次數，停止計算。

    1：從資料集中随機抽取一些資料形成小批量，把他們配置設定給最近的質心

    2：更新質心

    Mini Batch K-Means比K-Means有更快的收斂速度，但同時也降低了聚類的效果，但是在實際項目中卻表現得不明顯。

（例子中時間并沒有減少，待驗證。）

一趟聚類（Onepass K-means）

簡介

一趟聚類算法是由蔣盛益教授提出的無監督聚類算法，該算法具有高效，簡單的特點。資料集隻需要周遊一遍即可完成聚類。算法對超球狀分布的資料有良好的識别，對凸型資料分布識别較差。 一趟聚類可以在大規模資料，或者二次聚類中，或者聚類與其他算法結合的情況下，發揮其高效，簡單的特點；

算法流程

1. 初始時從資料集讀入一個新的對象
2. 以這個對象建構一個新的簇
3. 若達到資料集末尾,則轉6,否則讀入一個新的對象;計算它與每個已有簇之間的距離，并選擇與它距離最小的簇
4. 若最小距離超過給定的門檻值r,轉2
5. 否則将對象并入該簇，并更新簇心，轉3
6. 結束

GMMs

    使用 GMMs 有兩個關鍵的優勢。首先，GMMs 比 K-Means 在簇協方差方面更靈活；因為标準差參數，簇可以呈現任何橢圓形狀，而不是被限制為圓形。K-Means 實際上是 GMM 的一個特殊情況，這種情況下每個簇的協方差在所有次元都接近 0。第二，因為 GMMs 使用機率，是以每個資料點可以有很多簇。是以如果一個資料點在兩個重疊的簇的中間，我們可以簡單地通過說它百分之 X 屬于類 1，百分之 Y 屬于類 2 來定義它的類。即 GMMs 支援混合資格。

EM法求解高斯混合模型參數：

1、初始化

2、估計步驟（E-step）

       E就是Expectation的意思，就是假設模型參數已知的情況下，求隐含變量Z分别取z1,z2,...的期望，亦即Z分别取z1,z2,...的機率。在GMM中就是求資料點由各個 component生成的機率。

3、最大化步驟（M-step）

4、收斂條件

    為了用可視化的方式解釋它，我們可以看一下上面的圖，特别是黃色的簇，我們以它來作為例子。分布在第一次疊代時随即開始，但是我們可以看到大部分的黃點都在分布的右側。當我們計算一個機率權重和時，即使中心附近有一些點，但它們大部分都在右側。是以，分布的均值自然會接近這些點。我們也可以看到大部分的點分布在「從右上到左下」。是以改變标準差來建立更适合這些點的橢圓，以便最大化機率權重和。

參考連結：

https://www.cnblogs.com/yixuan-xu/p/6272208.html

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

http://blog.pluskid.org/?p=40

https://www.jiqizhixin.com/articles/the-6-clustering-algorithms-data-scientists-need-to-know

https://blog.csdn.net/u011574296/article/details/52986943

http://hareric.com/2016/07/06/%E4%B8%80%E8%B6%9F%E8%81%9A%E7%B1%BB(One-Pass%20Cluster)%E5%8F%8Apython%E5%AE%9E%E7%8E%B0/