1. K-均值聚類算法
優點：容易實作。
缺點：可能收斂到局部最小值，在大規模資料集上收斂較慢。
适用資料類型：數值型資料。
K-均值算法的工作流程是這樣的。首先，随機确定&個初始點作為質心。然後将資料集中的每個點配置設定到一個簇中，具體來講，為每個點找距其最近的質心，并将其配置設定給該質心所對應的簇。這一步完成之後，每個簇的質心更新為該簇所有點的平均值。
上述過程的僞代碼表示如下：
建立k個點作為起始質心（經常是随機選擇）
當任意一個點的簇配置設定結果發生改變時
對養據集中的每個資料點
對每個質心
計算質心與資料點之間的距離
将資料點配置設定到距其最近的簇
對每一個簇，計算簇中所有點的均值并将均值作為質心
k均值聚類算法：
# -*- coding: utf-8 -*-
from numpy import *
# K-均值聚類支援函數
def loadDataSet(fileName):
dataMat = []
fr = open(fileName)
for line in fr.readlines():
curLine = line.strip().split('\t')
fltLine = map(float,curLine)
dataMat.append(fltLine)
return dataMat
# 計算兩個向量的歐式距離
def distEclud(vecA, vecB):
return sqrt(sum(power(vecA - vecB, )))
# 為給定資料集建構一個包含k個随機質心的集合,是以每列的形式生成的
def randCent(dataSet, k):
n = shape(dataSet)[]
centroids = mat(zeros((k,n)))
for j in range(n):
minJ = min(dataSet[:,j]) # 找到每一維的最小
rangeJ = float(max(dataSet[:,j]) - minJ) # 每一維的最大和最小值之差
centroids[:,j] = mat(minJ + rangeJ * random.rand(k,)) # 生成随機值
#print centroids[:,j]
return centroids # 傳回随機質心,是和資料點相同的結構
# k--均值聚類算法(計算質心--配置設定--重新計算)
def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent): # k是簇的數目
m = shape(dataSet)[] # 得到樣本的數目
clusterAssment = mat(zeros((m,))) # 建立矩陣來存儲每個點的簇配置設定結果
# 第一列：記錄簇索引值，第二列：存儲誤差，歐式距離的平方
centroids = createCent(dataSet, k) # 建立k個随機質心
clusterChanged = True
while clusterChanged: # 疊代使用while循環來實作
clusterChanged = False
for i in range(m): # 周遊每個資料點，找到距離每個點最近的質心
minDist = inf; minIndex = -
for j in range(k): # 尋找最近的質心
distJI = distMeas(centroids[j,:],dataSet[i,:])
if distJI < minDist:
minDist = distJI; minIndex = j
if clusterAssment[i,] != minIndex: # 更新停止的條件
clusterChanged = True
clusterAssment[i,:] = minIndex,minDist** # minDist**2就去掉了根号
for cent in range(k): # 更新質心的位置
ptsInClust = dataSet[nonzero(clusterAssment[:,].A==cent)[]]
centroids[cent,:] = mean(ptsInClust, axis=) # 然後計算均值，axis=0:沿列方向
print 'centroids:',centroids
return centroids, clusterAssment # 傳回簇和每個簇的誤內插補點，誤內插補點是目前點到該簇的質心的距離
# 主函數
datMat=mat(loadDataSet('testSet.txt'))
rand_centroids=randCent(datMat, )
print 'Random centroids:',rand_centroids
myCentroids,clustAssing=kMeans(datMat,)
print 'myCentroids：',myCentroids
#centList,myNewAssments=biKmeans(datMat, 3)
運作結果：
Random centroids: [[ 0.47004012 -0.70046073]
[ 4.59776536 2.61143197]]
centroids: [[-3.38237045 -2.9473363 ]
[-2.46154315 2.78737555]
[ 2.80293085 -2.7315146 ]
[ 2.6265299 3.10868015]]
myCentroids： [[-3.38237045 -2.9473363 ]
[-2.46154315 2.78737555]
[ 2.80293085 -2.7315146 ]
[ 2.6265299 3.10868015]]
上面的結果可以看出得到了4個質心
2. 二分k-均值算法
在K-均值聚類中簇的數目k是一個使用者預先定義的參數，那麼使用者如何才能知道乂的選擇是否正确？如何才能知道生成的簇比較好呢？在包含簇配置設定結果的矩陣中儲存着每個點的誤差，即該點到簇質心的距離平方值。
使用後處理來提高聚類性能：
- K-均值算法收斂到了局部最小值，而非全局最小值（局部最小值指結果還可以但并非最好結果，全局最小值是可能的最好結果)。
- 一種用于度量聚類效果的名額是SSE(Sum of Squared Error,誤差平方和。SSE值越小表示資料點越接近于它們的質心，聚類效果也越好。因為對誤差取了平方，是以更加重視那些遠離中心的點。一種肯定可以降低SSE值的方法是增加簇的個數，但這違背了聚類的目标。聚類的目标是在保持族數目不變的情況下提高簇的品質。那麼如何進行改進？可以對生成的簇進行後處理，一種方法是将具有最大SSE值的簇劃分成兩個簇。具體實作時可以将最大簇包含的點過濾出來并在這些點上運作尺-均值算法，其中的K設為2。
為克服k-均值算法收斂于局部最小值的問題：
- 二分k-均值（bisecting K-means)算法，該算法首先将所有點作為一個簇，然後将該簇一分為二。之後選擇其中一個簇繼續進行劃分，選擇哪一個簇進行劃分取決于對”其劃分是否可以最大程度降低SSE的值。上述基于SSE的劃分過程不斷重複，直到得到使用者指定的簇數目為止。
- 另一種做法是選擇SSE最大的簇進行劃分，直到簇數目達到使用者指定的數目為止。這個做法聽起來并不難實作。
下面就來看一下該算法的實際效果。
# -*- coding: utf-8 -*-
from numpy import *
# K-均值聚類支援函數
def loadDataSet(fileName):
dataMat = []
fr = open(fileName)
for line in fr.readlines():
curLine = line.strip().split('\t')
fltLine = map(float,curLine)
dataMat.append(fltLine)
return dataMat
# 計算兩個向量的歐式距離
def distEclud(vecA, vecB):
return sqrt(sum(power(vecA - vecB, )))
# 為給定資料集建構一個包含k個随機質心的集合,是以每列的形式生成的
def randCent(dataSet, k):
n = shape(dataSet)[]
centroids = mat(zeros((k,n)))
for j in range(n):
minJ = min(dataSet[:,j]) # 找到每一維的最小
rangeJ = float(max(dataSet[:,j]) - minJ) # 每一維的最大和最小值之差
centroids[:,j] = mat(minJ + rangeJ * random.rand(k,)) # 生成随機值
#print centroids[:,j]
return centroids # 傳回随機質心,是和資料點相同的結構
# k--均值聚類算法(計算質心--配置設定--重新計算)
def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent): # k是簇的數目
m = shape(dataSet)[] # 得到樣本的數目
clusterAssment = mat(zeros((m,))) # 建立矩陣來存儲每個點的簇配置設定結果
# 第一列：記錄簇索引值，第二列：存儲誤差，歐式距離的平方
centroids = createCent(dataSet, k) # 建立k個随機質心
clusterChanged = True
while clusterChanged: # 疊代使用while循環來實作
clusterChanged = False
for i in range(m): # 周遊每個資料點，找到距離每個點最近的質心
minDist = inf; minIndex = -
for j in range(k): # 尋找最近的質心
distJI = distMeas(centroids[j,:],dataSet[i,:])
if distJI < minDist:
minDist = distJI; minIndex = j
if clusterAssment[i,] != minIndex: # 更新停止的條件
clusterChanged = True
clusterAssment[i,:] = minIndex,minDist** # minDist**2就去掉了根号
for cent in range(k): # 更新質心的位置
ptsInClust = dataSet[nonzero(clusterAssment[:,].A==cent)[]]
centroids[cent,:] = mean(ptsInClust, axis=) # 然後計算均值，axis=0:沿列方向
print 'centroids:',centroids
return centroids, clusterAssment # 傳回簇和每個簇的誤內插補點，誤內插補點是目前點到該簇的質心的距離
# 二分k--均值聚類算法
def biKmeans(dataSet, k, distMeas=distEclud):
m = shape(dataSet)[]
clusterAssment = mat(zeros((m,))) # 存儲資料集中每個點的簇配置設定結果及平方誤差
centroid0 = mean(dataSet, axis=).tolist()[] # 計算整個資料集的質心：1*2的向量
centList =[centroid0] # []的意思是使用一個清單儲存所有的質心,簇清單,[]的作用很大
for j in range(m): # 周遊所有的資料點，計算到初始質心的誤內插補點，存儲在第1列
clusterAssment[j,] = distMeas(mat(centroid0), dataSet[j,:])**
while (len(centList) < k): # 不斷對簇進行劃分，直到k
lowestSSE = inf # 初始化SSE為無窮大
for i in range(len(centList)): # 周遊每一個簇
print 'i:',i # 數組過濾得到所有的類别簇等于i的資料集
ptsInCurrCluster = dataSet[nonzero(clusterAssment[:,].A==i)[],:]
# 得到2個簇和每個簇的誤差，centroidMat：簇矩陣 splitClustAss：[索引值,誤差]
centroidMat, splitClustAss = kMeans(ptsInCurrCluster, , distMeas) # centroidMat是矩陣
sseSplit = sum(splitClustAss[:,]) # 求二分k劃分後所有資料點的誤差和
# 數組過濾得到整個資料點集的簇中不等于i的點集
print nonzero(clusterAssment[:,].A!=i)[]
sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,].A!=i)[],])# 所有剩餘資料集的誤差之和
print "sseSplit and notSplit: ",sseSplit,',',sseNotSplit
if (sseSplit + sseNotSplit) < lowestSSE: # 劃分後的誤差和小于目前的誤差，本次劃分被儲存
print 'here..........'
bestCentToSplit = i # i代表簇數
bestNewCents = centroidMat # 儲存簇矩陣
print 'bestNewCents',bestNewCents
bestClustAss = splitClustAss.copy() # 拷貝所有資料點的簇索引和誤差
lowestSSE = sseSplit + sseNotSplit # 儲存目前誤差和
# centList是原劃分的簇向量，bestCentToSplit是i值
print 'len(centList) and bestCentToSplit ',len(centList),',',bestCentToSplit
# 數組過濾得到的是新劃分的簇類别是1的資料集的類别簇重新劃為新的類别值為最大的類别數
bestClustAss[nonzero(bestClustAss[:,].A == )[],] = len(centList)
# 數組過濾得到的是新劃分的簇類别是0的資料集的類别簇重新劃為新的類别值為i
bestClustAss[nonzero(bestClustAss[:,].A == )[],] = bestCentToSplit
print 'the bestCentToSplit is: ',bestCentToSplit # 代表的是劃分的簇個數-1
print 'the len of bestClustAss is: ', len(bestClustAss) # 資料簇的資料點個數
# 新劃分簇矩陣的第0簇向量新增到目前的簇清單中
centList[bestCentToSplit] = bestNewCents[,:].tolist()[]
print 'centList[bestCentToSplit]:',centList[bestCentToSplit]
# 新劃分簇矩陣的第1簇向量添加到目前的簇清單中
centList.append(bestNewCents[,:].tolist()[]) # centList是清單的格式
print 'centList',centList
# 數組過濾得到所有資料集中簇類别是新簇的資料點
clusterAssment[nonzero(clusterAssment[:,].A == bestCentToSplit)[],:]= bestClustAss
return mat(centList), clusterAssment # 傳回質心清單和簇配置設定結果
# 主函數
datMat=mat(loadDataSet('testSet.txt'))
centList,myNewAssments=biKmeans(datMat, )
運作結果：
i:
centroids: [[-1.12630774 1.13042276]
[ 2.59258145 -2.78274655]]
[]
sseSplit and notSplit: ,
here..........
bestNewCents [[-1.12630774 1.13042276]
[ 2.59258145 -2.78274655]]
len(centList) and bestCentToSplit ,
the bestCentToSplit is:
the len of bestClustAss is:
centList[bestCentToSplit]: [-, ]
centList [[-1.1263077413793101, 1.13042275862069], [2.592581454545454, -2.782746545454545]]
i:
centroids: [[ 1.88660209 3.23434291]
[-3.10621991 -0.25215334]]
[ ..., ]
sseSplit and notSplit: ,
here..........
bestNewCents [[ 1.88660209 3.23434291]
[-3.10621991 -0.25215334]]
i:
centroids: [[ 4.5110462 -1.0349174 ]
[ 2.02832712 -3.29681394]]
[ ..., ]
sseSplit and notSplit: ,
len(centList) and bestCentToSplit ,
the bestCentToSplit is:
the len of bestClustAss is:
centList[bestCentToSplit]: [, ]
centList [[1.8866020869565217, 3.2343429130434784], [2.592581454545454, -2.782746545454545], [-3.1062199142857145, -0.2521533428571429]]
可以看出算法運作的中間過程，其中最容易迷惑的地方就是數組過濾器。可參考：
tolist()的用法
nonzero()
要注意的幾點：
（1）
centList =[centroid0] # []的意思是使用一個清單儲存所有的質心,簇清單,[]的作用很大
In []: mean(datMat, axis=).tolist()[]
Out[]: [-, ]
In []: centroid0=mean(datMat, axis=).tolist()[]
In []: centList =[centroid0]
In []: centList
Out[]: [[-0.10361321250000004, 0.05430119999999998]]
（2）
dataSet[nonzero(clusterAssment[:,0].A==i)[0],:]
>>> from numpy import *
>>> clusterAssment = mat(zeros((,)))
>>> clusterAssment[:,].A==
array([[ True],
[ True],
[ True],
[ True],
[ True]], dtype=bool)
>>> clusterAssment[:,]==
matrix([[ True],
[ True],
[ True],
[ True],
[ True]], dtype=bool)
>>> clusterAssment[:,].A==
array([[False],
[False],
[False],
[False],
[False]], dtype=bool)
>>> clusterAssment
matrix([[ 0., 0.],
[ 0., 0.],
[ 0., 0.],
[ 0., 0.],
[ 0., 0.]])
>>> mm=transpose(nonzero(clusterAssment[:,]==))
>>> mm
array([[0, 0],
[1, 0],
[2, 0],
[3, 0],
[4, 0]], dtype=int64)
>>> nonzero(clusterAssment[:,].A==)[]
array([, , , , ], dtype=int64)
>>> transpose(nonzero(clusterAssment[:,].A==))
array([[0, 0],
[1, 0],
[2, 0],
[3, 0],
[4, 0]], dtype=int64)
>>> nonzero(clusterAssment[:,].A==)
(array([, , , , ], dtype=int64), array([, , , , ], dtype=int64))
>>> dataSet=mat([[1,2],[2,3],[3,4],[4,5],[5,6]])
>>> dataSet[nonzero(clusterAssment[:,].A==)[],:]
matrix([[1, 2],
[2, 3],
[3, 4],
[4, 5],
[5, 6]])
>>>
（3）
bestNewCents[0,:].tolist()[0]
In []:a=mat([[1,2],[2,3]])
In []:a
Out[]:
matrix([[1, 2],
[2, 3]])
In []:a[,:]
Out[]: matrix([[1, 2]])
In []:a[,:].tolist()
Out[]: [[1, 2]]
In []:a[,:].tolist()[]
Out[]: [, ]
![PCA(主成分分析)降維可視化Matlab實作[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)