K-Means
K-Means算法的思想很簡單，對于給定的樣本集，按照樣本之間的距離大小，將樣本集劃分為K個簇。讓簇內(nèi)的點盡量緊密的連在一起，而讓簇間的距離盡量的大。
目標函數(shù)：
其中是簇
的均值向量，也叫質(zhì)心
利用啟發(fā)式方法，首先隨機選取K個點，計算其他點和k個點的距離，進而得到K個類，計算K個類的質(zhì)心，然后再次迭代聚類，知道質(zhì)心不在發(fā)生明顯變化或者迭代到一定次數(shù)結(jié)束。
參數(shù)選取
K-Means 算法需要根據(jù)數(shù)據(jù)的先驗經(jīng)驗來選擇一個合適的K值，對于不確定性的數(shù)據(jù)集或者流式數(shù)據(jù)集，則不適合使用該種方法
算法流程
輸入是樣本集D={x1,x2,...xm},聚類的簇樹k,最大迭代次數(shù)N
輸出是簇劃分C={C1,C2,...Ck}
1) 從數(shù)據(jù)集D中隨機選擇k個樣本作為初始的k個質(zhì)心向量： {μ1,μ2,...,μk}
2）對于n=1,2,...,N
a) 將簇劃分C初始化為Ct=?t=1,2...k
b) 對于i=1,2...m,計算樣本xi和各個質(zhì)心向量μj(j=1,2,...k)的距離：dij=||xi?μj||22，將xi標記最小的為dij所對應的類別λi。此時更新Cλi=Cλi∪{xi}
c) 對于j=1,2,...,k,對Cj中所有的樣本點重新計算新的質(zhì)心μj=1|Cj|∑x∈Cjx
e) 如果所有的k個質(zhì)心向量都沒有發(fā)生變化，則轉(zhuǎn)到步驟3）
3） 輸出簇劃分C={C1,C2,...Ck}
衍生算法
（1）K-Means++
初始化質(zhì)心的優(yōu)化
在上節(jié)我們提到，k個初始化的質(zhì)心的位置選擇對最后的聚類結(jié)果和運行時間都有很大的影響，因此需要選擇合適的k個質(zhì)心。如果僅僅是完全隨機的選擇，有可能導致算法收斂很慢。K-Means++算法就是對K-Means隨機初始化質(zhì)心的方法的優(yōu)化。
K-Means++的對于初始化質(zhì)心的優(yōu)化策略也很簡單，如下：
a) 從輸入的數(shù)據(jù)點集合中隨機選擇一個點作為第一個聚類中心μ1
b) 對于數(shù)據(jù)集中的每一個點xi，計算它與已選擇的聚類中心中最近聚類中心的距離D(xi)=argmin||xi?μr||22r=1,2,...kselected
c) 選擇一個新的數(shù)據(jù)點作為新的聚類中心，選擇的原則是：D(x)較大的點，被選取作為聚類中心的概率較大
d) 重復b和c直到選擇出k個聚類質(zhì)心
e) 利用這k個質(zhì)心來作為初始化質(zhì)心去運行標準的K-Means算法
（2）elkan K-Means
距離計算優(yōu)化
在傳統(tǒng)的K-Means算法中，我們在每輪迭代時，要計算所有的樣本點到所有的質(zhì)心的距離，這樣會比較的耗時。那么，對于距離的計算有沒有能夠簡化的地方呢？elkan K-Means算法就是從這塊入手加以改進。它的目標是減少不必要的距離的計算。那么哪些距離不需要計算呢？
elkan K-Means利用了兩邊之和大于等于第三邊,以及兩邊之差小于第三邊的三角形性質(zhì)，來減少距離的計算。
第一種規(guī)律是對于一個樣本點x和兩個質(zhì)心,
。如果我們預先計算出了這兩個質(zhì)心之間的距離
，則如果計算發(fā)現(xiàn)
,我們立即就可以知道
。此時我們不需要再計算
,也就是說省了一步距離計算。
第二種規(guī)律是對于一個樣本點x和兩個質(zhì)心。我們可以得到
。這個從三角形的性質(zhì)也很容易得到。
利用上邊的兩個規(guī)律，elkan K-Means比起傳統(tǒng)的K-Means迭代速度有很大的提高。但是如果我們的樣本的特征是稀疏的，有缺失值的話，這個方法就不使用了，此時某些距離無法計算，則不能使用該算法。
（3）Mini Batch K-Means
大樣本優(yōu)化
在統(tǒng)的K-Means算法中，要計算所有的樣本點到所有的質(zhì)心的距離。如果樣本量非常大，比如達到10萬以上，特征有100以上，此時用傳統(tǒng)的K-Means算法非常的耗時，就算加上elkan K-Means優(yōu)化也依舊。在大數(shù)據(jù)時代，這樣的場景越來越多。此時Mini Batch K-Means應運而生。
顧名思義，Mini Batch，也就是用樣本集中的一部分的樣本來做傳統(tǒng)的K-Means，這樣可以避免樣本量太大時的計算難題，算法收斂速度大大加快。當然此時的代價就是我們的聚類的精確度也會有一些降低。一般來說這個降低的幅度在可以接受的范圍之內(nèi)。
在Mini Batch K-Means中，我們會選擇一個合適的批樣本大小batch size，我們僅僅用batch size個樣本來做K-Means聚類。那么這batch size個樣本怎么來的？一般是通過無放回的隨機采樣得到的。
為了增加算法的準確性，我們一般會多跑幾次Mini Batch K-Means算法，用得到不同的隨機采樣集來得到聚類簇，選擇其中最優(yōu)的聚類簇。
小結(jié)
K-Means是個簡單實用的聚類算法，這里對K-Means的優(yōu)缺點做一個總結(jié)。
K-Means的主要優(yōu)點有：
1）原理比較簡單，實現(xiàn)也是很容易，收斂速度快。
2）聚類效果較優(yōu)。
3）算法的可解釋度比較強。
4）主要需要調(diào)參的參數(shù)僅僅是簇數(shù)k。
K-Means的主要缺點有：
1）K值的選取不好把握
2）對于不是凸的數(shù)據(jù)集比較難收斂
3）如果各隱含類別的數(shù)據(jù)不平衡，比如各隱含類別的數(shù)據(jù)量嚴重失衡，或者各隱含類別的方差不同，則聚類效果不佳。
4） 采用迭代方法，得到的結(jié)果只是局部最優(yōu)。
5） 對噪音和異常點比較的敏感。
BIRCH
BIRCH(Balanced Iterative Reducing and Clustering Using Hierarchies, 利用層次方法的平衡迭代規(guī)約和聚類)算法提供了一種類似B樹的數(shù)據(jù)結(jié)構(gòu)，能夠在單次掃描完所有的數(shù)據(jù)就能實現(xiàn)聚類。
聚類特征CF(cluster feature)
每一個CF是一個三元組，可以用（N，LS，SS）表示。其中N代表了這個CF中擁有的樣本點的數(shù)量，這個好理解；LS代表了這個CF中擁有的樣本點各特征維度的和向量，SS代表了這個CF中擁有的樣本點各特征維度的平方和。
CF滿足線性性，即:
聚類特征樹CFT（cluster feature tree）
生成過程參考B樹的生成過程。構(gòu)建CFT的過程，需要定義內(nèi)部節(jié)點的最大CF數(shù)量B，葉子節(jié)點的最大CF數(shù)L，葉子節(jié)點每個CF的最大樣本半徑閾值T。T值的大小能夠確定CFTree的規(guī)模，如果T太小，簇的數(shù)量將會非常的大，導致樹節(jié)點數(shù)量也會增大，內(nèi)存消耗較大。
