K-Means
K-Means算法的思想很簡單痊末，對于給定的樣本集，按照樣本之間的距離大小松申，將樣本集劃分為K個簇。讓簇內(nèi)的點盡量緊密的連在一起俯逾，而讓簇間的距離盡量的大贸桶。
目標(biāo)函數(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標(biāo)記最小的為dij所對應(yīng)的類別λ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ì)心贿衍。如果僅僅是完全隨機的選擇，有可能導(dǎo)致算法收斂很慢救恨。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) 重復(fù)b和c直到選擇出k個聚類質(zhì)心
e) 利用這k個質(zhì)心來作為初始化質(zhì)心去運行標(biāo)準(zhǔn)的K-Means算法
（2）elkan K-Means
距離計算優(yōu)化
在傳統(tǒng)的K-Means算法中署浩，我們在每輪迭代時，要計算所有的樣本點到所有的質(zhì)心的距離扫尺，這樣會比較的耗時筋栋。那么，對于距離的計算有沒有能夠簡化的地方呢正驻？elkan K-Means算法就是從這塊入手加以改進弊攘。它的目標(biāo)是減少不必要的距離的計算。那么哪些距離不需要計算呢姑曙？
elkan K-Means利用了兩邊之和大于等于第三邊,以及兩邊之差小于第三邊的三角形性質(zhì)襟交，來減少距離的計算。
第一種規(guī)律是對于一個樣本點x和兩個質(zhì)心,
伤靠。如果我們預(yù)先計算出了這兩個質(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應(yīng)運而生醉锅。
顧名思義，Mini Batch发绢，也就是用樣本集中的一部分的樣本來做傳統(tǒng)的K-Means硬耍，這樣可以避免樣本量太大時的計算難題，算法收斂速度大大加快边酒。當(dāng)然此時的代價就是我們的聚類的精確度也會有一些降低经柴。一般來說這個降低的幅度在可以接受的范圍之內(nèi)。
在Mini Batch K-Means中墩朦，我們會選擇一個合適的批樣本大小batch size坯认，我們僅僅用batch size個樣本來做K-Means聚類。那么這batch size個樣本怎么來的氓涣？一般是通過無放回的隨機采樣得到的牛哺。
為了增加算法的準(zhǔn)確性，我們一般會多跑幾次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ù)量嚴(yán)重失衡到涂，或者各隱含類別的方差不同脊框，則聚類效果不佳。
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ù)量將會非常的大，導(dǎo)致樹節(jié)點數(shù)量也會增大长赞，內(nèi)存消耗較大。
