既然聚類(lèi)可以看做是一種無(wú)監(jiān)督分類(lèi)，那么其應(yīng)用場(chǎng)景就是廣泛的，包括用戶群劃分、文本分類(lèi)、圖像識(shí)別等等。當(dāng)幾乎沒(méi)有有關(guān)數(shù)據(jù)的先驗(yàn)信息(如統(tǒng)計(jì)模型)可用，而用戶又要求盡可能地對(duì)數(shù)據(jù)的可能性少進(jìn)行假設(shè)等限制條件下，聚類(lèi)方法都適合用來(lái)查看數(shù)據(jù)點(diǎn)中的內(nèi)在關(guān)系以對(duì)它們的結(jié)構(gòu)進(jìn)行評(píng)估、決策。
機(jī)器學(xué)習(xí)中常見(jiàn)的聚類(lèi)算法包括 k-Means算法、期望最大化算法(Expectation Maximization，EM，參考“EM算法原理”)、譜聚類(lèi)算法(參考機(jī)器學(xué)習(xí)算法復(fù)習(xí)-譜聚類(lèi))以及人工神經(jīng)網(wǎng)絡(luò)算法，本文介紹K-均值(K-means)聚類(lèi)算法。
(二)K-均值(K-means)聚類(lèi)算法
1. 認(rèn)識(shí)K-均值聚類(lèi)算法
K-均值算法是最簡(jiǎn)單的一種聚類(lèi)算法，屬于分割式聚類(lèi)算法，目的是使各個(gè)簇(共k個(gè))中的數(shù)據(jù)點(diǎn)與所在簇質(zhì)心的誤差平方和SSE(Sum of Squared Error)達(dá)到最小，這也是評(píng)價(jià)K-means算法最后聚類(lèi)效果的評(píng)價(jià)標(biāo)準(zhǔn)。
k-means算法的基礎(chǔ)是最小誤差平方和準(zhǔn)則。其代價(jià)函數(shù)是：
式中，μc(i)表示第i個(gè)簇的質(zhì)心，我們希望得到的聚類(lèi)模型代價(jià)函數(shù)最小，直觀的來(lái)說(shuō)，各簇內(nèi)的樣本越相似，其與該簇質(zhì)心的誤差平方越小。計(jì)算所有簇的誤差平方之和，即可驗(yàn)證分為k個(gè)簇時(shí)時(shí)的聚類(lèi)是否是最優(yōu)的。SSE值越小表示數(shù)據(jù)點(diǎn)越接近于它們的質(zhì)心，聚類(lèi)效果也越好。因?yàn)閷?duì)誤差取了平方，因此更加重視那些遠(yuǎn)離中心的點(diǎn)。
一種肯定可以降低SSE值的方法是增加簇的個(gè)數(shù)，但這違背了聚類(lèi)的目標(biāo)，聚類(lèi)的目標(biāo)是在保持族數(shù)目不變的情況下提高簇的質(zhì)量。
k-均值(k-means)聚類(lèi)算法之所以稱之為k-均值是因?yàn)樗梢园l(fā)現(xiàn)k個(gè)不同的簇，且每個(gè)簇的中心采用簇中所含子數(shù)據(jù)集樣本特征的均值計(jì)算而成。k-均值是發(fā)現(xiàn)給定數(shù)據(jù)集的k個(gè)簇的算法，簇個(gè)數(shù)k由用戶給定，每一個(gè)簇通過(guò)其質(zhì)心( centroid) — 即簇中所有點(diǎn)的中心來(lái)描述。K-均值聚類(lèi)算法需要數(shù)值型數(shù)據(jù)來(lái)進(jìn)行相似性度量，也可以將標(biāo)稱型數(shù)據(jù)映射為二值型數(shù)據(jù)再用于度量相似性，其優(yōu)點(diǎn)是容易實(shí)現(xiàn)，缺點(diǎn)是可能收斂到局部最小值，在大規(guī)模數(shù)據(jù)集上收斂較慢。
假設(shè)訓(xùn)練樣本數(shù)據(jù)集X為(m, n)維矩陣，m表示樣本數(shù)、n表示每個(gè)樣本點(diǎn)的特征數(shù)，那么k-均值聚類(lèi)算法的結(jié)果就是得到一個(gè)kxn維矩陣，k表示用戶指定的簇個(gè)數(shù)，每一行都是一個(gè)長(zhǎng)度為n的行向量–第i個(gè)元素就是該簇中所有樣本第j(j=0,1,…,n-1)個(gè)特征的均值。下圖是K-均值聚類(lèi)算法聚類(lèi)的過(guò)程：
2. 算法過(guò)程
K-均值算法的工作流程是這樣的。首先，隨機(jī)確定k個(gè)初始點(diǎn)作為質(zhì)心;然后將數(shù)據(jù)集中的每個(gè)點(diǎn)分配到一個(gè)簇中–就是為每個(gè)點(diǎn)找距其最近的質(zhì)心，并將其分配給該質(zhì)心所對(duì)應(yīng)的簇;該步完成之后更新每個(gè)簇的質(zhì)心(該簇所有數(shù)據(jù)樣本特征的平均值);
上述過(guò)程迭代多次直至所有數(shù)據(jù)點(diǎn)的簇歸屬不再改變或者達(dá)到了最大迭代次數(shù)Maxiteration。k-均值算法的性能會(huì)受到所選相似性度量方法的影響，常用的相似性度量方法就是計(jì)算歐氏距離。上述過(guò)程的偽代碼表示如下：
***************************************************************
創(chuàng)建k個(gè)點(diǎn)作為起始質(zhì)心
任意點(diǎn)的簇分配結(jié)果發(fā)生改變時(shí)(循環(huán)內(nèi)設(shè)置、維護(hù)標(biāo)志位changed，也可同時(shí)設(shè)定最大迭代次數(shù)max)
對(duì)數(shù)據(jù)集中的每個(gè)數(shù)據(jù)點(diǎn)
對(duì)每個(gè)質(zhì)心
計(jì)算質(zhì)心與數(shù)據(jù)點(diǎn)之間的距離
將數(shù)據(jù)點(diǎn)分配到距其最近的簇(若有點(diǎn)的簇發(fā)生改變則置標(biāo)志位為changed = True)
更新簇中心： 對(duì)每一個(gè)簇，計(jì)算簇中所有點(diǎn)的均值并將均值作為質(zhì)心
***************************************************************
上述循環(huán)的終止條件是每個(gè)點(diǎn)的簇分配結(jié)果沒(méi)有發(fā)生改變或者達(dá)到了最大循環(huán)次數(shù)。
初始化時(shí)k個(gè)質(zhì)心的選擇可以是隨機(jī)的，但為了提高性能常用的方式是