機(jī)器學(xué)習(xí)算法與Python實(shí)踐這個(gè)系列主要是參考《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》這本書禁荒。因?yàn)樽约合雽W(xué)習(xí)Python猬膨，然后也想對(duì)一些機(jī)器學(xué)習(xí)算法加深下了解，所以就想通過Python來實(shí)現(xiàn)幾個(gè)比較常用的機(jī)器學(xué)習(xí)算法呛伴。恰好遇見這本同樣定位的書籍勃痴，所以就參考這本書的過程來學(xué)習(xí)了。
? ? ? ?機(jī)器學(xué)習(xí)中有兩類的大問題热康，一個(gè)是分類沛申，一個(gè)是聚類。分類是根據(jù)一些給定的已知類別標(biāo)號(hào)的樣本姐军，訓(xùn)練某種學(xué)習(xí)機(jī)器铁材，使它能夠?qū)ξ粗悇e的樣本進(jìn)行分類。這屬于supervised learning（監(jiān)督學(xué)習(xí)）奕锌。而聚類指事先并不知道任何樣本的類別標(biāo)號(hào)著觉，希望通過某種算法來把一組未知類別的樣本劃分成若干類別，這在機(jī)器學(xué)習(xí)中被稱作 unsupervised learning （無監(jiān)督學(xué)習(xí)）惊暴。在本文中饼丘，我們關(guān)注其中一個(gè)比較簡單的聚類算法：k-means算法。
一辽话、k-means算法
? ? ? ?通常葬毫，人們根據(jù)樣本間的某種距離或者相似性來定義聚類镇辉，即把相似的（或距離近的）樣本聚為同一類，而把不相似的（或距離遠(yuǎn)的）樣本歸在其他類贴捡。
? ? ? ?我們以一個(gè)二維的例子來說明下聚類的目的忽肛。如下圖左所示，假設(shè)我們的n個(gè)樣本點(diǎn)分布在圖中所示的二維空間烂斋。從數(shù)據(jù)點(diǎn)的大致形狀可以看出它們大致聚為三個(gè)cluster屹逛，其中兩個(gè)緊湊一些，剩下那個(gè)松散一些汛骂。我們的目的是為這些數(shù)據(jù)分組罕模，以便能區(qū)分出屬于不同的簇的數(shù)據(jù)，如果按照分組給它們標(biāo)上不同的顏色帘瞭，就是像下圖右邊的圖那樣：
? ? ? ?如果人可以看到像上圖那樣的數(shù)據(jù)分布淑掌，就可以輕松進(jìn)行聚類。但我們?cè)趺唇虝?huì)計(jì)算機(jī)按照我們的思維去做同樣的事情呢蝶念？這里就介紹個(gè)集簡單和經(jīng)典于一身的k-means算法抛腕。
? ? ? ?k-means算法是一種很常見的聚類算法，它的基本思想是：通過迭代尋找k個(gè)聚類的一種劃分方案媒殉，使得用這k個(gè)聚類的均值來代表相應(yīng)各類樣本時(shí)所得的總體誤差最小担敌。
? ? ? ?k-means算法的基礎(chǔ)是最小誤差平方和準(zhǔn)則。其代價(jià)函數(shù)是：
式中廷蓉，μc(i)表示第i個(gè)聚類的均值全封。我們希望代價(jià)函數(shù)最小，直觀的來說桃犬，各類內(nèi)的樣本越相似刹悴，其與該類均值間的誤差平方越小，對(duì)所有類所得到的誤差平方求和攒暇，即可驗(yàn)證分為k類時(shí)颂跨，各聚類是否是最優(yōu)的。
? ? ? 上式的代價(jià)函數(shù)無法用解析的方法最小化扯饶，只能有迭代的方法恒削。k-means算法是將樣本聚類成 k個(gè)簇（cluster），其中k是用戶給定的尾序，其求解過程非常直觀簡單钓丰，具體算法描述如下：
1、隨機(jī)選取 k個(gè)聚類質(zhì)心點(diǎn)
2每币、重復(fù)下面過程直到收斂? {
? ? ? 對(duì)于每一個(gè)樣例 i携丁，計(jì)算其應(yīng)該屬于的類：
? ? ? 對(duì)于每一個(gè)類 j，重新計(jì)算該類的質(zhì)心：
}
? ? ? 下圖展示了對(duì)n個(gè)樣本點(diǎn)進(jìn)行K-means聚類的效果，這里k取2梦鉴。
其偽代碼如下：
********************************************************************
創(chuàng)建k個(gè)點(diǎn)作為初始的質(zhì)心點(diǎn)（隨機(jī)選擇）
當(dāng)任意一個(gè)點(diǎn)的簇分配結(jié)果發(fā)生改變時(shí)
? ? ? ?對(duì)數(shù)據(jù)集中的每一個(gè)數(shù)據(jù)點(diǎn)
? ? ? ? ? ? ? 對(duì)每一個(gè)質(zhì)心
? ? ? ? ? ? ? ? ? ? ?計(jì)算質(zhì)心與數(shù)據(jù)點(diǎn)的距離
? ? ? ? ? ? ? 將數(shù)據(jù)點(diǎn)分配到距離最近的簇
? ? ? ?對(duì)每一個(gè)簇李茫，計(jì)算簇中所有點(diǎn)的均值，并將均值作為質(zhì)心
********************************************************************
二肥橙、Python實(shí)現(xiàn)
我使用的Python是2.7.5版本的魄宏。附加的庫有Numpy和Matplotlib。具體的安裝和配置見前面的博文存筏。在代碼中已經(jīng)有了比較詳細(xì)的注釋了宠互。不知道有沒有錯(cuò)誤的地方，如果有椭坚，還望大家指正（每次的運(yùn)行結(jié)果都有可能不同）予跌。里面我寫了個(gè)可視化結(jié)果的函數(shù)，但只能在二維的數(shù)據(jù)上面使用善茎。直接貼代碼：
kmeans.py?
??
from?numpy?import?*??
import?time??
import?matplotlib.pyplot?as?plt??
#?calculate?Euclidean?distance??
def?euclDistance(vector1,?vector2):??
return?sqrt(sum(power(vector2?-?vector1,?2)))??
#?init?centroids?with?random?samples??
def?initCentroids(dataSet,?k):??
????numSamples,?dim?=?dataSet.shape??
????centroids?=?zeros((k,?dim))??
for?i?in?range(k):??
index?=?int(random.uniform(0,?numSamples))??
????????centroids[i,?:]?=?dataSet[index,?:]??
return?centroids??
#?k-means?cluster??
def?kmeans(dataSet,?k):??
numSamples?=?dataSet.shape[0]??
#?first?column?stores?which?cluster?this?sample?belongs?to,??
#?second?column?stores?the?error?between?this?sample?and?its?centroid??
clusterAssment?=?mat(zeros((numSamples,2)))??
clusterChanged?=True??
##?step?1:?init?centroids??
????centroids?=?initCentroids(dataSet,?k)??
while?clusterChanged:??
clusterChanged?=False??
##?for?each?sample??
for?i?in?xrange(numSamples):??
minDist??=100000.0??
minIndex?=0??
##?for?each?centroid??
##?step?2:?find?the?centroid?who?is?closest??
for?j?in?range(k):??
????????????????distance?=?euclDistance(centroids[j,?:],?dataSet[i,?:])??
if?distance?<?minDist:??
????????????????????minDist??=?distance??
????????????????????minIndex?=?j??
##?step?3:?update?its?cluster??
if?clusterAssment[i,?0]?!=?minIndex:??
clusterChanged?=True??
clusterAssment[i,?:]?=?minIndex,?minDist**2??
##?step?4:?update?centroids??
for?j?in?range(k):??
pointsInCluster?=?dataSet[nonzero(clusterAssment[:,0].A?==?j)[0]]??
centroids[j,?:]?=?mean(pointsInCluster,?axis?=0)??
print?'Congratulations,?cluster?complete!'??
return?centroids,?clusterAssment??
#?show?your?cluster?only?available?with?2-D?data??
def?showCluster(dataSet,?k,?centroids,?clusterAssment):??
????numSamples,?dim?=?dataSet.shape??
if?dim?!=?2:??
print?"Sorry!?I?can?not?draw?because?the?dimension?of?your?data?is?not?2!"??
return?1??
mark?=?['or',?'ob',?'og',?'ok',?'^r',?'+r',?'sr',?'dr',?'
if?k?>?len(mark):??
print?"Sorry!?Your?k?is?too?large!?please?contact?Zouxy"??
return?1??
#?draw?all?samples??
for?i?in?xrange(numSamples):??
markIndex?=?int(clusterAssment[i,0])??
plt.plot(dataSet[i,0],?dataSet[i,?1],?mark[markIndex])??
mark?=?['Dr',?'Db',?'Dg',?'Dk',?'^b',?'+b',?'sb',?'db',?'
#?draw?the?centroids??
for?i?in?range(k):??
plt.plot(centroids[i,0],?centroids[i,?1],?mark[i],?markersize?=?12)??
????plt.show()?
三券册、測(cè)試結(jié)果
? ? ? 測(cè)試數(shù)據(jù)是二維的，共80個(gè)樣本垂涯。有4個(gè)類烁焙。如下：
testSet.txt
1.658985????4.285136??
-3.453687???3.424321??
4.838138????-1.151539??
-5.379713???-3.362104??
0.972564????2.924086??
-3.567919???1.531611??
0.450614????-3.302219??
-3.487105???-1.724432??
2.668759????1.594842??
-3.156485???3.191137??
3.165506????-3.999838??
-2.786837???-3.099354??
4.208187????2.984927??
-2.123337???2.943366??
0.704199????-0.479481??
-0.392370???-3.963704??
2.831667????1.574018??
-0.790153???3.343144??
2.943496????-3.357075??
-3.195883???-2.283926??
2.336445????2.875106??
-1.786345???2.554248??
2.190101????-1.906020??
-3.403367???-2.778288??
1.778124????3.880832??
-1.688346???2.230267??
2.592976????-2.054368??
-4.007257???-3.207066??
2.257734????3.387564??
-2.679011???0.785119??
0.939512????-4.023563??
-3.674424???-2.261084??
2.046259????2.735279??
-3.189470???1.780269??
4.372646????-0.822248??
-2.579316???-3.497576??
1.889034????5.190400??
-0.798747???2.185588??
2.836520????-2.658556??
-3.837877???-3.253815??
2.096701????3.886007??
-2.709034???2.923887??
3.367037????-3.184789??
-2.121479???-4.232586??
2.329546????3.179764??
-3.284816???3.273099??
3.091414????-3.815232??
-3.762093???-2.432191??
3.542056????2.778832??
-1.736822???4.241041??
2.127073????-2.983680??
-4.323818???-3.938116??
3.792121????5.135768??
-4.786473???3.358547??
2.624081????-3.260715??
-4.009299???-2.978115??
2.493525????1.963710??
-2.513661???2.642162??
1.864375????-3.176309??
-3.171184???-3.572452??
2.894220????2.489128??
-2.562539???2.884438??
3.491078????-3.947487??
-2.565729???-2.012114??
3.332948????3.983102??
-1.616805???3.573188??
2.280615????-2.559444??
-2.651229???-3.103198??
2.321395????3.154987??
-1.685703???2.939697??
3.031012????-3.620252??
-4.599622???-2.185829??
4.196223????1.126677??
-2.133863???3.093686??
4.668892????-2.562705??
-2.793241???-2.149706??
2.884105????3.043438??
-2.967647???2.848696??
4.479332????-1.764772??
-4.905566???-2.911070?
測(cè)試代碼：
test_kmeans.py
from?numpy?import?*??
import?time??
import?matplotlib.pyplot?as?plt??
##?step?1:?load?data??
print?"step?1:?load?data..."??
dataSet?=?[]??
fileIn?=?open('E:/Python/Machine?Learning?in?Action/testSet.txt')??
for?line?in?fileIn.readlines():??
lineArr?=?line.strip().split('\t')??
dataSet.append([float(lineArr[0]),?float(lineArr[1])])??
##?step?2:?clustering...??
print?"step?2:?clustering..."??
dataSet?=?mat(dataSet)??
k?=4??
centroids,?clusterAssment?=?kmeans(dataSet,?k)??
##?step?3:?show?the?result??
print?"step?3:?show?the?result..."??
showCluster(dataSet,?k,?centroids,?clusterAssment)??
運(yùn)行的前后結(jié)果是：
不同的類用不同的顏色來表示，其中的大菱形是對(duì)應(yīng)類的均值質(zhì)心點(diǎn)集币。
四考阱、算法分析
? ? ? ?k-means算法比較簡單翠忠，但也有幾個(gè)比較大的缺點(diǎn)：
（1）k值的選擇是用戶指定的鞠苟，不同的k得到的結(jié)果會(huì)有挺大的不同，如下圖所示秽之，左邊是k=3的結(jié)果当娱，這個(gè)就太稀疏了，藍(lán)色的那個(gè)簇其實(shí)是可以再劃分成兩個(gè)簇的考榨。而右圖是k=5的結(jié)果跨细，可以看到紅色菱形和藍(lán)色菱形這兩個(gè)簇應(yīng)該是可以合并成一個(gè)簇的：
（2）對(duì)k個(gè)初始質(zhì)心的選擇比較敏感，容易陷入局部最小值河质。例如冀惭，我們上面的算法運(yùn)行的時(shí)候，有可能會(huì)得到不同的結(jié)果掀鹅，如下面這兩種情況散休。K-means也是收斂了，只是收斂到了局部最小值：
（3）存在局限性乐尊，如下面這種非球狀的數(shù)據(jù)分布就搞不定了：
（4）數(shù)據(jù)庫比較大的時(shí)候戚丸，收斂會(huì)比較慢。
? ? ? ?k-means老早就出現(xiàn)在江湖了扔嵌。所以以上的這些不足也被世人的目光敏銳的捕捉到限府，并融入世人的智慧進(jìn)行了某種程度上的改良夺颤。例如問題（1）對(duì)k的選擇可以先用一些算法分析數(shù)據(jù)的分布，如重心和密度等胁勺，然后選擇合適的k世澜。而對(duì)問題（2），有人提出了另一個(gè)成為二分k均值（bisecting k-means）算法姻几，它對(duì)初始的k個(gè)質(zhì)心的選擇就不太敏感宜狐，這個(gè)算法我們下一個(gè)博文再分析和實(shí)現(xiàn)。
五蛇捌、參考文獻(xiàn)
[1]?K-means聚類算法
[2]?漫談 Clustering (1): k-means
原文參考：http://blog.csdn.net/zouxy09/article/details/17589329
