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