聚类是一种无监督的学习，它将相似的对象归到同一个簇中。
这篇文章介绍一种称为K-均值的聚类算法，之所以称为K-均值是因为它可以发现k个不同的簇，且每个簇的中心采用簇中所含值的均值计算而成。
聚类分析视图将相似对象归入同一簇，将不相似对象归到不同簇。
下面用Python简单演示该算法实现的原理：
函数loadDataSet先将文本文件导入到一个列表中，并添加到dataSet中，返回的结果即为需加载的训练数据。
def loadDataSet(fileName):
dataMat = []
fr = open(fileName)
for line in fr.readlines():
curLine = line.strip().split('\t')
fltLine = map(float,curLine)
dataMat.append(list(fltLine))
return dataMat
函数distEclud用于计算两个向量的距离：
def distEclud(vecA, vecB):
return sqrt(sum(power(vecA - vecB, 2))) # 计算距离
def randCent(dataSet,k):
n = shape(dataSet)[1] # 列数
centroids = mat(zeros((k,n))) # 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) # 生成坐标
return centroids
函数randCent有两个参数，其中k为用户指定的质心的数量（即最后分成的类的个数），该函数的作用是为给定的数据集dataSet构建一个包含k个随机质心的集合（centroids）。
上面三个为辅助函数，下面为完整的K-均值算法：
def kMeans(dataSet,k,disMeas = distEclud, createCent = randCent):
m = shape(dataSet)[0] # 训练数据集的数量
clusterAssent = mat(zeros((m,2))) # 用于保存每个点对应的质心
centroids = createCent(dataSet,k) #初始化质心并保存
clusterChanged = True
while clusterChanged:
clusterChanged = False
for i in range(m): # 遍历所有数据点 计算每一个数据点到每个质心的距离
minDist = inf
minIndex = -1
for j in range(k): # 遍历所有的质心点
distJI = disMeas(centroids[j,:], dataSet[i ,:])
if distJI < minDist:
minDist = distJI
minIndex = j
if clusterAssent[i,0] != minIndex:
clusterChanged = True # 任何一个点对应的质心发生变化需要重新遍历计算
clusterAssent[i,:] = minIndex,minDist ** 2
print(centroids)
for cent in range(k): # 更新质心的位置
ptsInClust = dataSet[nonzero(clusterAssent[:,0].A == cent)[0]]
centroids[cent : ] = mean(ptsInClust, axis= 0)
return centroids,clusterAssent
思路大概为：
-
遍历所有训练数据点（m个数据点）
-
对所有质心（k个质心）
- 计算该数据点与质心之间的距离，并保存该数据点最近的质心
- 对比之前保存的该数据点的质心（即该数据点所属的簇，保存在clusterAssent中），若发生更改，则证明未收敛，结束后需要从头开始循环
-
对所有质心（k个质心）
- 对于每一个簇，计算簇中所有点的均值作为质心。
K-均值算法有时候会出现聚类效果较差，收敛到了局部最小值，而非全局最小值。一种用于度量聚类效果的指标是SSE（Sum of Squared Error，误差平方和），SSE越小表示数据点越接近于它们的质心，聚类效果也越好。因此，要对聚类的结果进行改进的方法可以将具有最大SSE值的簇划分为两个簇，同时为了保持簇总数不变，可以将某两个簇进行合并。