主要内容
一般K-means:
-
簇数k是用户给定的，每个簇通过其质心(centroid)，即簇中所有点的中心来描述。
-
首先，随机确定k个初始点作为质心。然后，将数据集中的每个点分配到一个簇中，具体来讲，为每个点找距其最近的质心，并将其分配给该质心所对应的簇。这一步完成后，每个簇的质心更新为该簇所有点的平均值。
-
方法：(计算质心 - 分配 - 重新计算) - 反复迭代，直到所有数据点的簇分配结果不再改变为止
使用后处理提高聚类性能(《机器学习实战》 - P189)：
-
问题
- 怎样知道k值的选择是否正确?怎样知道生成的簇比较好呢？
-
怎样评价
- 在包含簇分配结果的矩阵中包含着每个点的误差，即该点到簇质心的距离平方值，将以此来评价聚类质量
-
原因：
- K-Means算法收敛但聚类效果交叉的原因是：K-Means收敛到了局部最小值，而非全局最小值(局部最小值结果可以但并非最好结果，全局最小值是可能的最小结果)
-
衡量指标：
- 一种用于度量聚类效果的指标是SSE(Sum of Squared Error 误差平方和),即每个点距离质心距离的平方和。SSE越小表示数据点越接近质心，聚类效果也越好。
因为对误差取了平方，因此更加重视那些远离中心的点。增加簇个数能够降低SSE值，但这违背了聚类的目标：在保持簇数目不变情况下提高簇的质量
- 一种用于度量聚类效果的指标是SSE(Sum of Squared Error 误差平方和),即每个点距离质心距离的平方和。SSE越小表示数据点越接近质心，聚类效果也越好。
-
一种方法
- 对生成后的簇进行处理，将SSE值最大的簇划分为两个簇。具体实现时可以将最大簇包含的点过滤出来，并在这些点上运行k=2的K-means。
二分K-均值算法
为了克服k-均值算法收敛于局部最小值的问题，有人提出了另一个称为二分k-均值(bisecting K-means)的算法。该算法首先将所有点作为一个簇，然后将该簇一分为二，之后选择其中一个簇继续进行划分，选择哪一个簇进行划分取决于对其划分是否可可以最大程度降低SSE的值。上述基于SSE的划分过程不断重复，知道得到用户指定的簇数目为止
代码
代码整理自《机器学习实战》
# -*- coding: utf-8 -*-
from numpy import *
import matplotlib.pyplot as plt
def loadDataSet(fileName):
"""
功能：读取文件，加载数据
"""
dataMat = []
fr = open(fileName)
for line in fr.readlines():
curLine = line.strip().split(' ')
# 注意： python2中map函数直接返回列表，不用list处理
fltLine = list(map(float,curLine))
dataMat.append(fltLine)
return dataMat
def disEclud(vecA,vecB):
"""
功能： 计算两个向量间的欧氏距离
"""
return sqrt(sum(power(vecA - vecB, 2)))
def randCent(dataSet, k):
"""
功能： 为给定数据集构建一个包含k个随机质心的集合(通过找到数据集每一维的最小和最大值来完成)
"""
# array(dataSet)是自己加的，否则无法进行dataSet[:,j]操作，用mat转成矩阵也不能进行dataSet[:,j]操作
dataSet = array(dataSet)
n = shape(dataSet)[1]
centroids = mat(zeros((k,n)))
# 构建簇质心
for j in range(n):
# 第j维的最小值
minJ = min(dataSet[:,j])
# 第j维的最大最小值之差
rangeJ = float(max(dataSet[:,j]) - minJ)
# 原代码是: centroids[:,j] = minJ + rangeJ * random.rand(k,1), randoma.rand(k,1)是k行1列的ndarray,且随机产生的每个数字在0-1之间
temp = random.rand(k,1)
centroids[:,j] = minJ + rangeJ * temp
return centroids
def kMeans(dataSet,k,distMeas = disEclud, createCent = randCent):
"""
功能：kmearns聚类代码
首先，随机确定k个初始点作为质心。然后，将数据集中的每个点分配到一个簇中，具体来讲，为每个点找距其最近的质心，并将其分配给该质心所对应的簇。这一步完成后，每个簇的质心更新为该簇所有点的平均值。
方法：(计算质心 - 分配 - 重新计算) - 反复迭代，直到所有数据点的簇分配结果不再改变为止
param: dataSet: 数据计划
param: k: 簇的数量
param: distMeas: 距离计算方法
param: createCent: 计算原始的质心
return: centroids: 最终的质心
return: clusterAssment: 簇分配结果矩阵，包含两列，一列记录簇索引值，第二列存储误差(指当前点到簇质心的距离，后续会用该误差评价聚类的效果)
"""
m = shape(dataSet)[0]
clusterAssment = mat(zeros((m,2)))
centroids = createCent(dataSet,k)
centroids = array(centroids)
dataSet = array(dataSet)
# 标识是否继续迭代(如果为True,则继续迭代)
clusterChanged = True
while clusterChanged:
clusterChanged = False
# 遍历所有样本点，找到距离每个点最近的质心(通过对每个点遍历所有质心并计算点到每个质心的距离来完成)
for i in range(m):
minDist = inf
minIndex = -1
# 当前样本点便利便利所有的质心
for j in range(k):
# 计算第i个样本与第j个质心间的距离
distJI = distMeas(centroids[j,:], dataSet[i,:])
if distJI < minDist:
minDist = distJI
minIndex = j
# 如果当前第i个点的分配结果发生了改变，则更新clusterChanged标识
if clusterAssment[i,0] != minIndex:
clusterChanged = True
# clusterAssment的两列分别存储簇索引值和距离(第i个样本点到质心的距离)
clusterAssment[i,:] = minIndex, minDist ** 2
# print (centroids)
# 遍历所有质心并更新它们的取值
for cent in range(k):
# 这一步操作每台明白？？？？？
pstInClust = dataSet[nonzero(clusterAssment[:,0].A == cent)[0]]
# 在pstInclust的列上计算均值
centroids[cent,:] = mean(pstInClust, axis = 0)
return centroids, clusterAssment
def biKmeans(dataSet, k, distMeas = disEclud):
"""
功能：二分K-均值算法
为了克服k-均值算法收敛于局部最小值的问题，有人提出了另一个称为二分k-均值(bisecting K-means)的算法。
该算法首先将所有点作为一个簇，然后将该簇一分为二，之后选择其中一个簇继续进行划分，选择哪一个簇进行划分取决于
对其划分是否可可以最大程度降低SSE的值。上述基于SSE的划分过程不断重复，知道得到用户指定的簇数目为止
param: dataSet: 数据计划
param: k: 簇的数量
param: distMeas: 距离计算方法
return: centroids: 最终的质心
return: clusterAssment: 簇分配结果矩阵，包含两列，一列记录簇索引值，第二列存储误差
"""
dataSet = array(dataSet)
m = shape(dataSet)[0]
# 创建一个矩阵来存储数据集中每个点的簇分配结果及平方误差，然后计算整个数据集的质心，并使用一个列表来保留所有的质心
# 得到上述质心后，可以遍历数据集中所有点来计算每个点到质心的误差，这些误差值都将在后续用到
clusterAssment = mat(zeros((m,2)))
centroid0 = mean(dataSet,axis=0).tolist()[0]
cenList = [centroid0]
for j in range(m):
clusterAssment[j,1] = distMeas(mat(centroid0),dataSet[j,:]) ** 2
# while循环汇总会不停地对簇进行划分，直到得到想要的簇数目位置
while len(cenList) < k:
# SSE初值设为无穷大
lowestSSE = inf
# 遍历簇列表centList中的每一个簇
for i in range(len(cenList)):
# 对每一个簇，将该簇中的所有点看称一个小的数据集pstIncurrCluster
# QUESTION:为什么要选与i相等的？？？
ptsIncurrCluster = dataSet[nonzero(clusterAssment[:,0].A == i)[0],:]
# 将pstIncurrCluster输入到函数KMeans()中进行处理(k=2),然后得到2个质心(簇)和每个簇的误差值
centroidMat, splitClustAss = kMeans(ptsIncurrCluster, 2, distMeas)
# 上述得到的误差与剩余数据集的误差之和作为本次划分的误差
sseSplit = sum(splitClustAss[:,1])
sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,0].A != i)[0],1])
print ("seeSplit, and notSplit: ", sseSplit, sseNotSplit)
# 如果划分的SSE值最小，则本次划分被保存
if (sseSplit + sseNotSplit) < lowestSSE:
bestCentToSplit = i
bestNewCents = centroidMat
bestClustAss = splitClustAss.copy()
lowestSSe = sseSplit + sseNotSplit
"""更新簇的分配结果"""
bestClustAss[nonzero(bestClustAss[:,0].A == 1)[0],0] = len(cenList)
bestClustAss[nonzero(bestClustAss[:,0].A == 0)[0],0] = bestCentToSplit
print ("the bestCentToSplit is : ", bestCentToSplit)
print ("the len of bestClustAss is: ", len(bestClustAss))
cenList[bestCentToSplit] = bestNewCents[0, :]
cenList.append(bestNewCents[1,:])
clusterAssment[nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:] = bestClustAss
return mat(cenList), clusterAssment
def show_pic(dataMat):
dataArr = array(dataMat)
# 作图方法一
# plt.scatter(dataArr[:,0], dataArr[:,1], alpha=0.8) # 绘制散点图，透明度为0.6（这样颜色浅一点，比较好看）
# plt.show()
# 作图方法二
fig = plt.figure()
ax = plt.subplot()
ax.scatter(dataArr[:,0], dataArr[:,1], s=30, alpha=0.8) # 绘制散点图，面积随机
plt.show()
if __name__ == '__main__':
# dataMat = loadDataSet('KMeans_testSet.txt')
# show_pic(dataMat)
# centroids, clusterAssment = kMeans(dataMat,4)
dataMat2 = loadDataSet('KMeans_testSet2.txt')
# show_pic(dataMat2)
cenList,myNewAssments = biKmeans(dataMat2,3)
print (cenList)
# print (myNewAssments)
网友评论