Python 2.7
IDE Pycharm 5.0.3
numpy 1.11.0
matplotlib 1.5.1
可以擴展閱讀：
1.(大)數(shù)據(jù)處理：從txt到數(shù)據(jù)可視化
2.機器學習之K-近鄰算法（Python描述）基礎
3.機器學習之K-近鄰算法（Python描述）實戰(zhàn)百維萬組數(shù)據(jù)
前言
從程序上讀懂每一行赊窥，才是了解算法的開始涌庭。
什么是K-means?
一句話：一堆數(shù)據(jù)我也不知道是啥玩意的(無標簽)的扔給你，你給我分一下同衣，哪一堆屬于一類瑰枫。這就是聚類！
Knn VS K-means
knn表現(xiàn)的是有監(jiān)督情況下对竣，也就是我都知道標簽了巫玻，載扔進去一個沒有帶標簽的，根據(jù)特性(特征)逗栽，你給我判斷出來盖袭，這個屬于哪一類，就像分類匹配一樣彼宠。
K-means表現(xiàn)的是無監(jiān)督情況下苍凛，我不知道標簽，我只有數(shù)據(jù)集兵志，那么從那么大一堆數(shù)據(jù)集中，我需要找出“規(guī)律”宣肚，也就是數(shù)據(jù)挖掘的一部分了想罕，哪一些數(shù)據(jù)屬于同一個類(雖然我并不知道這個類叫什么，whatever)霉涨，
來張圖可能清楚點按价。左邊的是knn，主要用于未知點的分類笙瑟，右圖是k-means楼镐，主要用于聚類(當然也可以用來對未知點的聚類判斷)
還是不理解分類和聚類請看我在知乎上的回答@徐凱--聚類與分類有什么區(qū)別？
數(shù)據(jù)形式
ok往枷，還是老樣子的txt格式框产，數(shù)據(jù)的清洗和讀取必不可少，至于怎么將txt寫入矩陣错洁，請參考（大）數(shù)據(jù)處理：從txt到數(shù)據(jù)可視化或者以下代碼注釋
展示以下大概是這樣的秉宿，雖然，我們一看就能知道屯碴，簇中心也就是聚類中心大概的位置描睦，但是機器并不知道，怎么計算出聚類中心导而，這就是k-means干的活了忱叭！
k-means算法流程
具體的k-means原理不再累述隔崎，很詳細的請見
深入淺出K-Means算法
我這里用自己的話概括下
- 隨機選k個點作為初代的聚類中心點
- 計算其余各點到這些聚類中心點的‘距離’，并選擇距離自己最近的聚類點作為自己的類韵丑，給自己打上標簽
- 屬于同一簇的一群點進行取質(zhì)心運算爵卒，計算新的簇中心
- 重復2~3，直到簇中心不再改變
代碼--K-means基礎
# -*- coding: utf-8 -*-
import math
from numpy import *
#C:\\\\Users\\\\MrLevo\\\\Desktop\\\\machine_learning_in_action\\\\Ch10\\\\testSet.txt
#載入數(shù)據(jù)埂息，清洗數(shù)據(jù)保存為矩陣形式
def loadDataSet(filename):
fr = open(filename)
lines = fr.readlines()
dataMat = []
for line in lines:
result = line.strip().split('\\t')
fltline = map(float,result)
dataMat.append(fltline)
return dataMat
#向量計算距離
def distEclud(vecA,vecB):
return sqrt(sum(power(vecA-vecB,2)))
# 給定數(shù)據(jù)集構建一個包含k個隨機質(zhì)心的集合技潘，
def randCent(dataSet,k):
n = shape(dataSet)[1] # 計算列數(shù)
centroids = mat(zeros((k,n)))
for j in range(n):
minJ = min(dataSet[:,j]) #取每列最小值
rangeJ = float(max(dataSet[:,j])-minJ)
centroids[:,j] = minJ + rangeJ*random.rand(k,1) # random.rand(k,1)構建k行一列，每行代表二維的質(zhì)心坐標
#random.rand(2,1)#產(chǎn)生兩行一列0~1隨機數(shù)
return centroids
#minJ + rangeJ*random.rand(k,1)自動擴充陣進行匹配千康，實現(xiàn)不同維數(shù)矩陣相加,列需相同
#一切都是對象
def kMeans(dataSet,k,distMeas = distEclud,creatCent = randCent):
m = shape(dataSet)[0] # 行數(shù)
clusterAssment = mat(zeros((m,2))) # 建立簇分配結果矩陣享幽，第一列存索引，第二列存誤差
centroids = creatCent(dataSet,k) #聚類點
clusterChanged = True
while clusterChanged:
clusterChanged = False
for i in range(m):
minDist = inf # 無窮大
minIndex = -1 #初始化
for j in range(k):
distJI = distMeas(centroids[j,:],dataSet[i,:]) # 計算各點與新的聚類中心的距離
if distJI < minDist: # 存儲最小值拾弃，存儲最小值所在位置
minDist = distJI
minIndex = j
if clusterAssment[i,0] != minIndex:
clusterChanged = True
clusterAssment[i,:] = minIndex,minDist**2
print centroids
for cent in range(k):
ptsInClust = dataSet[nonzero(clusterAssment[:,0].A== cent)[0]]
# nonzeros(a==k)返回數(shù)組a中值不為k的元素的下標
#print type(ptsInClust)
'''
#上式理解不了可見下面的值桩，效果一樣
#方法二把同一類點抓出來
ptsInClust=[]
for j in range(m):
if clusterAssment[j,0]==cent:
ptsInClust.append(dataSet[j].tolist()[0])
ptsInClust = mat(ptsInClust)
#tolist http://docs.scipy.org/doc/numpy/reference/generated/numpy.ndarray.tolist.html
'''
centroids[cent,:] = mean(ptsInClust,axis=0) # 沿矩陣列方向進行均值計算,重新計算質(zhì)心
return centroids,clusterAssment
dataMat =mat(loadDataSet('C:\\\\Users\\\\MrLevo\\\\Desktop\\\\machine_learning_in_action\\\\Ch10\\\\testSet.txt'))
myCentroids,clustAssing = kMeans(dataMat,4)
IDE上輸出
[[ 0.44698578 3.66996803]
[ 4.4566098 1.69900322]
[-1.54424114 3.58626959]
[ 4.44813429 1.63720788]]
...
[[-2.46154315 2.78737555]
[ 2.6265299 3.10868015]
[-3.53973889 -2.89384326]
[ 2.65077367 -2.79019029]]
#四個聚類中心坐標如上，從圖中可以看出豪椿，大概是這么個情況
設定不同k值奔坟，它會怎么聚類呢
以下是不同k的時候聚類情況
K-means出現(xiàn)的問題
收斂于局部最小，而不是全局最小搭盾，因為剛開始的聚類中心是隨機給定的咳秉，所以搞不好就陷入局部最小了，而度量聚類效果的指標是誤差平方和SSE鸯隅，誤差越大澜建，簇的效果越不好，解決這個問題的方法之一就是二分K-means
什么是二分K-means
簡單的說蝌以，就是將所有點先看成一個簇炕舵，然后簇一分為二，依次選擇其中的一個簇繼續(xù)劃分跟畅，選擇哪一個簇進行劃分取決于對其劃分是否可以最大程度降低SSE的值咽筋。
實現(xiàn)過程
二分K-means代碼
在原有代碼基礎上，添加biKmeans函數(shù)
# 構建二分k-均值聚類
def biKmeans(dataSet, k, distMeas=distEclud):
m = shape(dataSet)[0]
clusterAssment = mat(zeros((m,2))) # 初始化徊件，簇點都為0
centroid0 = mean(dataSet, axis=0).tolist()[0] # 起始第一個聚類點奸攻，即所有點的質(zhì)心
centList =[centroid0] # 質(zhì)心存在一個列表中
for j in range(m):#calc initial Error
clusterAssment[j,1] = distMeas(mat(centroid0), dataSet[j,:])**2
# 計算各點與簇的距離，均方誤差庇忌，大家都為簇0的群
while (len(centList) < k):
lowestSSE = inf
for i in range(len(centList)):
ptsInCurrCluster = dataSet[nonzero(clusterAssment[:,0].A==i)[0],:]#get the data points currently in cluster i
# 找出歸為一類簇的點的集合舞箍，之后再進行二分，在其中的簇的群下再劃分簇
#第一次循環(huán)時皆疹，i=0疏橄，相當于，一整個數(shù)據(jù)集都是屬于0簇，取了全部的dataSet數(shù)據(jù)
centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas)
#開始正常的一次二分簇點
#splitClustAss捎迫，類似于[0 2.3243]之類的晃酒，第一列是簇類，第二列是簇內(nèi)點到簇點的誤差
sseSplit = sum(splitClustAss[:,1]) # 再分后的誤差和
sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1]) # 沒分之前的誤差
print "sseSplit: ",sseSplit
print "sseNotSplit: ",sseNotSplit
#至于第一次運行為什么出現(xiàn)seeNoSplit=0的情況窄绒，因為nonzero(clusterAssment[:,0].A!=i)[0]不存在贝次，第一次的時候都屬于編號為0的簇
if (sseSplit + sseNotSplit) < lowestSSE:
bestCentToSplit = i
bestNewCents = centroidMat
bestClustAss = splitClustAss.copy()
lowestSSE = sseSplit + sseNotSplit
# copy用法http://www.cnblogs.com/BeginMan/p/3197649.html
bestClustAss[nonzero(bestClustAss[:,0].A == 1)[0],0] = len(centList) #change 1 to 3,4, or whatever
bestClustAss[nonzero(bestClustAss[:,0].A == 0)[0],0] = bestCentToSplit
#至于nonzero(bestClustAss[:,0].A == 1)[0]其中的==1這簇點，由kMeans產(chǎn)生
print 'the bestCentToSplit is: ',bestCentToSplit
print 'the len of bestClustAss is: ', len(bestClustAss)
centList[bestCentToSplit] = bestNewCents[0,:].tolist()[0]#replace a centroid with two best centroids
centList.append(bestNewCents[1,:].tolist()[0])
clusterAssment[nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:]= bestClustAss#reassign new clusters, and SSE
return mat(centList), clusterAssment
效果如上圖流程的第三幅可見彰导，所以要講的都寫在注釋上了蛔翅，好好讀代碼，才是理解算法的唯一道路位谋，光知道算法咋回事山析，自己重構不出，以后還是會忘的掏父。
附錄-matplotlib畫圖代碼
# -*- coding: utf-8 -*-
from numpy import *
import matplotlib.pyplot as plt
import kMeans as km
#注意導入自己的Kmeans的py文件
data3 = mat(km.loadDataSet('C:\\\\Users\\\\MrLevo\\\\Desktop\\\\machine_learning_in_action\\\\Ch10\\\\testSet2.txt'))
centList,myNewAssments =km.biKmeans(data3,3)
###################創(chuàng)建圖表2####################
plt.figure(2) #創(chuàng)建圖表2
ax3 = plt.subplot() # 圖表2中創(chuàng)建子圖1
plt.title("biK-means Scatter")
plt.xlabel('x')
plt.ylabel('y')
ax3.scatter(data3[:,0],data3[:,1],color='b',marker='o',s=100)
ax3.scatter(centList[:,0],centList[:,1],color='r',marker='o',s=200,label='Cluster & K=3')
#顯示label位置的函數(shù)
ax3.legend(loc='upper right')
plt.show()
核心語句解析
ptsInClust = dataSet[nonzero(clusterAssment[:,0].A== cent)[0]]
nonzeros(a)返回數(shù)組a中值不為零的元素的下標笋轨，它的返回值是一個長度為a.ndim(數(shù)組a的軸數(shù))的元組，元組的每個元素都是一個整數(shù)數(shù)組赊淑，其值為非零元素的下標在對應軸上的值爵政。
舉例如下
>>> b1 = np.array([True, False, True, False])
>>> np.nonzero(b1)
(array([0, 2]),)
>>> b2 = np.array([[True, False, True], [True, False, False]])
>>> np.nonzero(b2)
(array([0, 0, 1]), array([0, 2, 0]))
再來個例子補充下
>>> a = np.arange(3*4*5).reshape(3,4,5)
>>> a[b2]
array([[ 0, 1, 2, 3, 4],
[10, 11, 12, 13, 14],
[20, 21, 22, 23, 24]])
>>> a[np.nonzero(b2)]
array([[ 0, 1, 2, 3, 4],
[10, 11, 12, 13, 14],
[20, 21, 22, 23, 24]]))
也就是說，找到True的條件陶缺，返回索引钾挟，ok，這就夠用來解釋那句話的了饱岸，因為返回的是array形式的等龙，所以需要再對應的取值，具體的可以看源代碼的解釋語句伶贰，我還另外的寫了個實現(xiàn)一樣功能的代碼片段，注釋起來了罐栈，實現(xiàn)的是同樣的算法黍衙，希望理解結構的時候能幫到你
ptsInClust=[]
for j in range(m):
if clusterAssment[j,0]==cent:
ptsInClust.append(dataSet[j].tolist()[0])
ptsInClust = mat(ptsInClust)
#tolist用法 http://docs.scipy.org/doc/numpy/reference/generated/numpy.ndarray.tolist.html
致謝
利用python進行數(shù)據(jù)分析.Wes McKinney著
機器學習實戰(zhàn).Peter Harrington著
@stackoverflow--pyplot scatter plot marker size
@轉--Python圖表繪制：matplotlib繪圖庫入門
@BeginMan--深入Python(4):深拷貝和淺拷貝
@轉--深入淺出K-Means算法
@MrLevo520--（大）數(shù)據(jù)處理：從txt到數(shù)據(jù)可視化
@MrLevo520--機器學習之K-近鄰算法（Python描述）基礎
@MrLevo520--機器學習之K-近鄰算法（Python描述）實戰(zhàn)百維萬組數(shù)據(jù)
