博客CSDN：深入淺出K-Means算法
博客：機(jī)器學(xué)習(xí)算法-K-means聚類
分布式：MapReduce實(shí)現(xiàn)
并行化：kmeans算法并行化的mpi程序
1. K-Means算法步驟
算法步驟
收斂性定義圾浅，畸變函數(shù)（distortion function）：
偽代碼：
1) 創(chuàng)建k個(gè)點(diǎn)作為K個(gè)簇的起始質(zhì)心（經(jīng)常隨機(jī)選擇）
2) 當(dāng)任意一個(gè)點(diǎn)的蔟分配結(jié)果發(fā)生變化時(shí)（初始化為True）
對數(shù)據(jù)集中的每個(gè)數(shù)據(jù)點(diǎn)亮钦，重新分配質(zhì)心
對每個(gè)質(zhì)心
計(jì)算質(zhì)心到數(shù)據(jù)點(diǎn)之間的距離
將數(shù)據(jù)點(diǎn)分配到距其最近的蔟
對每個(gè)蔟，計(jì)算蔟中所有點(diǎn)的均值并將均值作為新的質(zhì)心
缺點(diǎn)：
- 需要提前確定K值申眼；
- 對異常值敏感；
- 對初始聚類中心敏感争拐；
優(yōu)點(diǎn)：
- 易解釋辰妙；
- 運(yùn)行速度快；
- 一般效果不錯碉输；
2. K-Means改進(jìn)
2.1 K-Mediods
每次選取中值作為聚類中心，排除異常值的影響亭珍；
2.2 K-Means++算法
K-Means主要有兩個(gè)最重大的缺陷——都和初始值有關(guān)：
K是事先給定的敷钾，這個(gè)K值的選定是非常難以估計(jì)的。很多時(shí)候肄梨，事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少個(gè)類別才最合適阻荒。（ISODATA算法通過類的自動合并和分裂，得到較為合理的類型數(shù)目K）
K-Means算法需要用初始隨機(jī)種子點(diǎn)來搞众羡，這個(gè)隨機(jī)種子點(diǎn)太重要侨赡，不同的隨機(jī)種子點(diǎn)會有得到完全不同的結(jié)果。（K-Means++算法可以用來解決這個(gè)問題纱控，其可以有效地選擇初始點(diǎn)）
我在這里重點(diǎn)說一下K-Means++算法步驟：
- 先從我們的數(shù)據(jù)庫隨機(jī)挑個(gè)隨機(jī)點(diǎn)當(dāng)“種子點(diǎn)”辆毡。
- 對于每個(gè)點(diǎn)，我們都計(jì)算其和最近的一個(gè)“種子點(diǎn)”的距離D(x)并保存在一個(gè)數(shù)組里甜害，然后把這些距離加起來得到Sum(D(x))。
- 然后球昨，再取一個(gè)隨機(jī)值尔店，用權(quán)重的方式來取計(jì)算下一個(gè)“種子點(diǎn)”。這個(gè)算法的實(shí)現(xiàn)是主慰，先取一個(gè)能落在Sum(D(x))中的隨機(jī)值Random嚣州，然后用Random -= D(x)，直到其<=0共螺，此時(shí)的點(diǎn)就是下一個(gè)“種子點(diǎn)”该肴。
- 重復(fù)第（2）和第（3）步直到所有的K個(gè)種子點(diǎn)都被選出來。
- 進(jìn)行K-Means算法藐不。
3. K-Means分布式實(shí)現(xiàn)
算法偽代碼：
k-means的每一次迭代都可以分為以下3個(gè)步驟匀哄。
-
第一步：Map：對于每一個(gè)點(diǎn)秦效，將其對應(yīng)的最近的聚類中心
-
第二步：Combine：剛完成map的機(jī)器在本機(jī)上都分別完成同一個(gè)聚類的點(diǎn)的求和，減少reduce操作的通信量和計(jì)算量涎嚼。
-
第三步：reduce：將同一聚類中心的中間數(shù)據(jù)再進(jìn)行求和阱州，得到新的聚類中心
4. K-Means并行化
并行化思路：使用主從模式。由一個(gè)節(jié)點(diǎn)充當(dāng)主節(jié)點(diǎn)負(fù)責(zé)數(shù)據(jù)的劃分與分配法梯，其他節(jié)點(diǎn)完成本地?cái)?shù)據(jù)的計(jì)算苔货，并將結(jié)果返回給主節(jié)點(diǎn)。大致過程如下：
- 進(jìn)程0為主節(jié)點(diǎn)立哑，先從文件中讀取數(shù)據(jù)集夜惭，然后將數(shù)據(jù)集劃分并傳給其他進(jìn)程；
- 進(jìn)程0選擇每個(gè)聚類的中心點(diǎn)铛绰，并發(fā)送給其他進(jìn)程滥嘴；
- 其他進(jìn)程計(jì)算數(shù)據(jù)塊中每個(gè)點(diǎn)到中心點(diǎn)的距離，然后標(biāo)出每個(gè)點(diǎn)所屬的聚類至耻，并計(jì)算每個(gè)聚類所有點(diǎn)到其中心點(diǎn)的距離之和若皱，最后將這些結(jié)果返回給進(jìn)程0；
- 進(jìn)程0計(jì)算出新的中心點(diǎn)并發(fā)送給其他進(jìn)程尘颓，并計(jì)算其他進(jìn)程傳來的聚類所有點(diǎn)到其中心點(diǎn)的距離總和走触；
- 重復(fù)3和4直到，直到步驟4中的所有聚類的距離之和不變（即收斂）疤苹。
