本文主要介绍最常见的一种聚类算法：K-means算法，及其改进算法二分K-均值算法。文中示例代码取源于《Machine Learning in Action》。
机器学习的算法主要分为监督学习和无监督学习监督学习。
监督学习(supervised learning)，利用样本输入和期望输出来学习如何预测的技术叫做监督学习法。一个房地产经理看过一处房子后，可以估算出这处房产的价格，这是因为他根据自己以往的经验得来的。如何让计算机去预估一处房产的价格呢？我们可以给它一些已知价格的房产数据，这些数据包括面积、楼层、是否向阳等一组属性以及对应的价格，计算机可以从这些已知样本训练得到一个公式，这就叫做监督学习。监督学习包括：神经网络、决策树、支持向量机、贝叶斯过滤等。
无监督学习(unsupervised learning)，主要用来处理未被标记的样本集。还是上一个例子，已知一组房产的数据，这些数据包括面积、楼层、是否向阳等一组属性，但是没有对应的价格。这时候，我们仍然可以利用这些数据得到一些信息，利用房产间的相似程度把它们分类，分过类之后可以更合理地定价，也可以根据分类调整营销策略。
K-means算法是一种聚类算法，属于无监督学习算法。
K-means算法，顾名思义，将数据分为K个聚类。 K-means算法将n个数据对象划分为k个聚类，并使所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。
K-means算法首先会随机确定k个中心位置(位于空间中代表聚类中心的点)，然后将各个数据项分配给最邻近的中心点。待分配完成后，重新计算聚类中心，聚类中心移动到分配给该聚类的所有节点的平均位置处，然后重复以上分配过程，直到分配过程不再产生变化为止。
下面摘取《Machine Learning in Action》书中第10章的代码例子，本文代码使用Python3.3.2。
from numpy import *
# general function to parse tab-delimited floats
def loadDataSet(fileName):
# assume last column is target value
dataMat = []
fr = open(fileName)
for line in fr.readlines():
curLine = line.strip().split('\t')
# map all elements to float()
fltLine = map(float, curLine)
dataMat.append(list(fltLine))
return dataMat
def distEclud(vecA, vecB):
return sqrt(sum(power(vecA-vecB, 2)))
def randCent(dataSet, k):
n = shape(dataSet)[1]
# create centroid mat
centroids = mat(zeros((k, n)))
# create random cluster centers, within bounds of each dimension
for j in range(n):
minJ = min(dataSet[:,j])
rangeJ = float(max(dataSet[:,j]) - minJ)
centroids[:,j] = mat(minJ + rangeJ * random.rand(k,1))
return centroids
def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
m = shape(dataSet)[0]
# create mat to assign data points to a
# centroid, also hods SE of each point
clusterAssment = mat(zeros((m, 2)))
centroids = createCent(dataSet, k)
clusterChanged = True
while clusterChanged:
clusterChanged = False
# for each data point assign it to the
# closest centroid
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)
# recalculate centroids
for cent in range(k):
# get all the point in this cluster
ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]
# assign centroid to mean
centroids[cent,:] = mean(ptsInClust, axis=0)
return centroids, clusterAssment
运行算法：
import kMeans
datMat = mat(kMeans.loadDataSet('testSet.txt'))
myCentroids, clustAssing = kMeans.kMeans(datMat, 4)
K-means算法并不总是能得到正确的聚类，如下图
运行K-means算法实现了聚类，但是却不能保证一个理想的聚类结果，为什么？因为K-means算法总是根据局部最小化原则进行聚类，而没有考虑全局的最小化。每次进行节点分配时都是参考该节点到中心点距离的最小值，没有考虑全局的距离最小值。下面介绍一种改进了的K-means算法，即Bisecting k-means算法，可以解决这一问题。
在这里我们选择一种全局最小值的度量方法，SSE(sum of squared error)。SSE越小，所有的节点距离它们的中心点越近。
算法原理：开始时只有一个聚类，然后将其分割为两个聚类，分割之后根据SSE最小化原则从所有聚类中选择一个聚类继续进行分割，直到聚类个数达到K。
伪代码如下
Start with all the points in one cluster
While the number of clusters is less than k
for every cluster
measure total error
perform k-means clustering with k=2 on the given cluster
measure total error after k-means has split the cluster in two
choose the cluster split that gives the lowest error and commit this split
算法具体实现如下，将biKmeans函数添加到kMeans.py文件中
def biKmeans(dataSet, k, distMeas=distEclud):
m = shape(dataSet)[0]
clusterAssment = mat(zeros((m, 2)))
centroid0 = mean(dataSet, axis=0).tolist()[0]
centList = [centroid0]
for j in range(m):
clusterAssment[j,1] = distMeas(mat(centroid0), dataSet[j,:])**2
while len(centList) < k:
lowestSSE = inf
for i in range(len(centList)):
ptsInCurrCluster = \
dataSet[nonzero(clusterAssment[:,0].A==i)[0],:]
centroidMat,splitClustAss = \
kMeans(ptsInCurrCluster, 2, distMeas)
sseSplit = sum(splitClustAss[:,1])
sseNotSplit = \
sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1])
print("sseSplit, and notSplit: ", sseSplit, sseNotSplit)
if (sseSplit+sseNotSplit) < lowestSSE:
bestCentToSplit = i
bestNewCents = centroidMat
bestClustAss = splitClustAss.copy()
lowestSSE = sseSplit + sseNotSplit
bestClustAss[nonzero(bestClustAss[:,0].A==1)[0],0] = len(centList)
bestClustAss[nonzero(bestClustAss[:,0].A==0)[0],0] = bestCentToSplit
print('the bestCentToSplit is ', bestCentToSplit)
print('the len of bestClustAss is: ', len(bestClustAss))
centList[bestCentToSplit] = bestNewCents[0,:]
centList.append(bestNewCents[1,:])
clusterAssment[nonzero(clusterAssment[:,0].A == \
bestCentToSplit)[0],:] = bestClustAss
return centList, clusterAssment
算法测试：
import kMeans
datMat2 = mat(kMeans.loadDataSet('testSet2.txt'))
centList, myNewAssments = kMeans.biKmeans(datMat2, 3)