K-Means原理K-Means算法的思想很簡單绽昏，對于給定的樣本集悉稠，按照樣本之間的距離大小，將樣本集劃分為K個(gè)簇赊抖。讓簇內(nèi)的點(diǎn)盡量緊密的連在一起统倒，而讓簇間的距離盡量的大。如果用數(shù)據(jù)表達(dá)式表示氛雪，假設(shè)簇劃分為(C1,C2,...Ck)，則我們的目標(biāo)是最小化平方誤差E：
其中μi是簇Ci的均值向量报亩，有時(shí)也稱為質(zhì)心浴鸿，表達(dá)式為：
如果我們想直接求上式的最小值并不容易，這是一個(gè)NP難的問題弦追，因此只能采用啟發(fā)式的迭代方法赚楚。K-Means采用的啟發(fā)式方式很簡單，用下面一組圖就可以形象的描述骗卜。
上圖a表達(dá)了初始的數(shù)據(jù)集宠页，假設(shè)k=2。在圖b中寇仓，我們隨機(jī)選擇了兩個(gè)k類所對應(yīng)的類別質(zhì)心举户，即圖中的紅色質(zhì)心和藍(lán)色質(zhì)心，然后分別求樣本中所有點(diǎn)到這兩個(gè)質(zhì)心的距離遍烦，并標(biāo)記每個(gè)樣本的類別為和該樣本距離最小的質(zhì)心的類別俭嘁，如圖c所示，經(jīng)過計(jì)算樣本和紅色質(zhì)心和藍(lán)色質(zhì)心的距離服猪，我們得到了所有樣本點(diǎn)的第一輪迭代后的類別供填。此時(shí)我們對當(dāng)前標(biāo)記為紅色和藍(lán)色的點(diǎn)分別求其新的質(zhì)心，如圖d所示罢猪，新的紅色質(zhì)心和藍(lán)色質(zhì)心的位置已經(jīng)發(fā)生了變動(dòng)近她。圖e和圖f重復(fù)了我們在圖c和圖d的過程，即將所有點(diǎn)的類別標(biāo)記為距離最近的質(zhì)心的類別并求新的質(zhì)心膳帕。最終我們得到的兩個(gè)類別如圖f粘捎。
當(dāng)然在實(shí)際K-Mean算法中，我們一般會(huì)多次運(yùn)行圖c和圖d危彩，才能達(dá)到最終的比較優(yōu)的類別攒磨。
經(jīng)典K-Meams算法流程首先我們看看K-Means算法的一些要點(diǎn)。
1）對于K-Means算法汤徽，首先要注意的是k值的選擇娩缰，一般來說，我們會(huì)根據(jù)對數(shù)據(jù)的先驗(yàn)經(jīng)驗(yàn)選擇一個(gè)合適的k值谒府，如果沒有什么先驗(yàn)知識(shí)拼坎，則可以通過交叉驗(yàn)證選擇一個(gè)合適的k值梧奢。
2）在確定了k的個(gè)數(shù)后，我們需要選擇k個(gè)初始化的質(zhì)心演痒，就像上圖b中的隨機(jī)質(zhì)心。由于我們是啟發(fā)式方法趋惨，k個(gè)初始化的質(zhì)心的位置選擇對最后的聚類結(jié)果和運(yùn)行時(shí)間都有很大的影響鸟顺，因此需要選擇合適的k個(gè)質(zhì)心，最好這些質(zhì)心不能太近器虾。
好了讯嫂，現(xiàn)在我們來總結(jié)下傳統(tǒng)的K-Means算法流程。
輸入：樣本集D={x1,x2,...xm},聚類的簇樹k,最大迭代次數(shù)N
輸出：簇劃分C={C1,C2,...Ck}
算法流程：
1）從數(shù)據(jù)集D中隨機(jī)選擇k個(gè)樣本作為初始的k個(gè)質(zhì)心向量： {μ1,μ2,...,μk}
2）對于n=1,2,...,N
?a) 將簇劃分C初始化為Ct=?兆沙，t=1,2...k
?b) 對于i=1,2...m,計(jì)算樣本xi和各個(gè)質(zhì)心向量μj (j=1,2,...k)的距離：
?將xi標(biāo)記最小的為dij所對應(yīng)的類別λi欧芽。此時(shí)更新Cλi=Cλi∪{xi}
?c) 對于j=1,2,...,k,對Cj中所有的樣本點(diǎn)重新計(jì)算新的質(zhì)心
?d）如果所有的k個(gè)質(zhì)心向量都沒有發(fā)生變化，則轉(zhuǎn)到步驟3）
3） 輸出簇劃分
K-Means不同改進(jìn)版本初始化優(yōu)化版：K-Means++在上節(jié)我們提到葛圃，k個(gè)初始化的質(zhì)心的位置選擇對最后的聚類結(jié)果和運(yùn)行時(shí)間都有很大的影響千扔，因此需要選擇合適的k個(gè)質(zhì)心。如果僅僅是完全隨機(jī)的選擇库正，有可能導(dǎo)致算法收斂很慢曲楚。K-Means++算法就是對K-Means隨機(jī)初始化質(zhì)心的方法的優(yōu)化。
K-Means++的對于初始化質(zhì)心的優(yōu)化策略也很簡單褥符，如下：
a) 從輸入的數(shù)據(jù)點(diǎn)集合中隨機(jī)選擇一個(gè)點(diǎn)作為第一個(gè)聚類中心μ1
b) 對于數(shù)據(jù)集中的每一個(gè)點(diǎn)xi龙誊，計(jì)算它與已選擇的聚類中心中最近聚類中心的距離
c) 選擇一個(gè)新的數(shù)據(jù)點(diǎn)作為新的聚類中心，選擇的原則是：D(x)較大的點(diǎn)喷楣，被選取作為聚類中心的概率較大d) 重復(fù)b和c直到選擇出k個(gè)聚類質(zhì)心e) 利用這k個(gè)質(zhì)心來作為初始化質(zhì)心去運(yùn)行標(biāo)準(zhǔn)的K-Means算法
距離計(jì)算優(yōu)化版：elkan K-Means
在傳統(tǒng)的K-Means算法中趟大，我們在每輪迭代時(shí)，要計(jì)算所有的樣本點(diǎn)到所有的質(zhì)心的距離铣焊，這樣會(huì)比較的耗時(shí)逊朽。那么，對于距離的計(jì)算有沒有能夠簡化的地方呢曲伊？elkan K-Means算法就是從這塊入手加以改進(jìn)惋耙。它的目標(biāo)是減少不必要的距離的計(jì)算。那么哪些距離不需要計(jì)算呢熊昌？elkan K-Means利用了兩邊之和大于等于第三邊,以及兩邊之差小于第三邊的三角形性質(zhì)绽榛，來減少距離的計(jì)算。
第一種規(guī)律是對于一個(gè)樣本點(diǎn)x和兩個(gè)質(zhì)心μj1,μj2婿屹。如果我們預(yù)先計(jì)算出了這兩個(gè)質(zhì)心之間的距離D(j1,j2)灭美，則如果計(jì)算發(fā)現(xiàn)2D(x,j1)≤D(j1,j2),我們立即就可以知道D(x,j1)≤D(x,j2)。此時(shí)我們不需要再計(jì)算D(x,j2),也就是說省了一步距離計(jì)算昂利。
第二種規(guī)律是對于一個(gè)樣本點(diǎn)x和兩個(gè)質(zhì)心μj1,μj2届腐。我們可以得到D(x,j2)≥max{0,D(x,j1)?D(j1,j2)}铁坎。這個(gè)從三角形的性質(zhì)也很容易得到。
利用上邊的兩個(gè)規(guī)律犁苏，elkan K-Means比起傳統(tǒng)的K-Means迭代速度有很大的提高硬萍。但是如果我們的樣本的特征是稀疏的，有缺失值的話围详，這個(gè)方法就不使用了朴乖，此時(shí)某些距離無法計(jì)算，則不能使用該算法助赞。
大樣本優(yōu)化版：Mini Batch K-Means
在統(tǒng)的K-Means算法中买羞，要計(jì)算所有的樣本點(diǎn)到所有的質(zhì)心的距離。如果樣本量非常大雹食，比如達(dá)到10萬以上畜普，特征有100以上，此時(shí)用傳統(tǒng)的K-Means算法非常的耗時(shí)群叶，就算加上elkan K-Means優(yōu)化也依舊吃挑。在大數(shù)據(jù)時(shí)代，這樣的場景越來越多街立。此時(shí)Mini Batch K-Means應(yīng)運(yùn)而生儒鹿。顧名思義，Mini Batch几晤，也就是用樣本集中的一部分的樣本來做傳統(tǒng)的K-Means约炎，這樣可以避免樣本量太大時(shí)的計(jì)算難題，算法收斂速度大大加快蟹瘾。當(dāng)然此時(shí)的代價(jià)就是我們的聚類的精確度也會(huì)有一些降低圾浅。一般來說這個(gè)降低的幅度在可以接受的范圍之內(nèi)。
在Mini Batch K-Means中憾朴，我們會(huì)選擇一個(gè)合適的批樣本大小batch size狸捕，我們僅僅用batch size個(gè)樣本來做K-Means聚類。那么這batch size個(gè)樣本怎么來的众雷？一般是通過無放回的隨機(jī)采樣得到的灸拍。為了增加算法的準(zhǔn)確性，我們一般會(huì)多跑幾次Mini Batch K-Means算法砾省，用得到不同的隨機(jī)采樣集來得到聚類簇鸡岗，選擇其中最優(yōu)的聚類簇。
K-Means與KNN
初學(xué)者很容易把K-Means和KNN搞混编兄，兩者其實(shí)差別還是很大的轩性。K-Means是無監(jiān)督學(xué)習(xí)的聚類算法，沒有樣本輸出狠鸳；而KNN是監(jiān)督學(xué)習(xí)的分類算法揣苏，有對應(yīng)的類別輸出悯嗓。KNN基本不需要訓(xùn)練，對測試集里面的點(diǎn)卸察，只需要找到在訓(xùn)練集中最近的k個(gè)點(diǎn)脯厨，用這最近的k個(gè)點(diǎn)的類別來決定測試點(diǎn)的類別。而K-Means則有明顯的訓(xùn)練過程坑质，找到k個(gè)類別的最佳質(zhì)心合武，從而決定樣本的簇類別.當(dāng)然，兩者也有一些相似點(diǎn)洪乍，兩個(gè)算法都包含一個(gè)過程，即找出和某一個(gè)點(diǎn)最近的點(diǎn)夜焦。兩者都利用了最近鄰(nearest neighbors)的思想壳澳。
K-Means小結(jié)
K-Means是個(gè)簡單實(shí)用的聚類算法，這里對K-Means的優(yōu)缺點(diǎn)做一個(gè)總結(jié)茫经。
優(yōu)點(diǎn)
1）原理比較簡單巷波，實(shí)現(xiàn)也是很容易，收斂速度快卸伞。
2）聚類效果較優(yōu)抹镊。
3）算法的可解釋度比較強(qiáng)。
4）主要需要調(diào)參的參數(shù)僅僅是簇?cái)?shù)k荤傲。
缺點(diǎn)
1）K值的選取不好把握
2）對于不是凸的數(shù)據(jù)集比較難收斂
3）如果各隱含類別的數(shù)據(jù)不平衡垮耳，比如各隱含類別的數(shù)據(jù)量嚴(yán)重失衡，或者各隱含類別的方差不同遂黍，則聚類效果不佳终佛。
4） 采用迭代方法，得到的結(jié)果只是局部最優(yōu)雾家。
5） 對噪音和異常點(diǎn)比較的敏感铃彰。
