转载请注明作者和出处： https://blog.csdn.net/weixin_37392582
代码地址： https://gitee.com/wuweijun
开发平台： Win10 + Python3.6 + Anaconda3
编 者： 无尾
-
- 一、前言
- 二、K-均值聚类算法
- 1、工作流程
- 2、伪代码
- 3、流程图
- 4、核心代码解释
- （１）euclidentDistance
- （２）initCentroids
- （３）kmenas
- 三、二分K-均值算法
- 1、工作流程
- 2、伪代码
- 3、流程图
- 4、核心代码解释
一、前言
聚类是一种无监督的学习，它将相似的对象归到同一簇中。它有点像全自动分类。聚类的方法几乎可以应用于所有对象，簇内的对象越相似，聚类的效果越好。本章要学习一种称为K-均值（K-means）聚类的孙发。之所以称之为K-均值，是因为它可以发现k个不同的簇，且每个簇的中心采用簇中所含值的均值计算而成。
簇识别。簇识别给出聚类结果的含义。假定有一些数据，现在将相似数据归到一起，簇识别会告诉我们这些簇到底都是些什么。聚类与分类的最大不同在与，分类的目标实现已知，而聚类则不一样。不易呀其产生的结果与分类相同，而只是类别没有预先定义，聚类有时也被称为无监督分类（unsupervised）。
二、K-均值聚类算法
优点：容易实现
缺点：可能收敛到局部最小值，在大规模数据集上收敛较慢
适用数据类型：数值型数据
1、工作流程
- 首先随机确定k个初始点作为质心
- 为每个点找到距其最近的质心，并将其分配给该质心所对应的簇（打标签）
- 将每个质心更新为该簇所有点的平均值
- 重复前面两个步骤，知道所有点的簇类不再变化，即确定的质心为最优，即可完成聚类。
2、伪代码
创建k个点作为起始质心（通常是随机选择样本点）
当任意一个点的簇类（簇分配结果）发生改变时
对数据集中的每个数据点
对每个质心
计算质心与数据点之间的距离
将数据点分配到距其最近的簇
对每一个簇，计算簇中所有点的均值并将均值作为质心
3、流程图
4、核心代码解释
（１）euclidentDistance
计算了各样本点到各质心距离，用距离差平方和表示,也称误差平方和。在主函数中，样本点会根据距离选取最新的质心作为簇类。
def euclidentDistance(vector1, vector2): #欧氏距离 Euclidean
"""
Function: 欧式距离计算
Input：两个坐标（x0,x1），（x2, x3）
Output： 两点的欧式距离
"""
return np.sqrt(np.sum(np.power(vector2 - vector1,)))
（２）initCentroids
在样本点中，随机获取k个样本作为初始质心
random.uniform(x1,x2) _在[x1,x2)内随机选取一个符合均匀分布的浮点数
def initCentroids(data, k):
"""
Function: 随机获取k个质心
Input：数据集，质心数量
Output：k个质心的集合
"""
numSamples, dim = data.shape
centroids = np.zeros((k,dim))
for i in range(k):
#
index = int(np.random.uniform(, numSamples))
centroids[i,:] = data[index,:]
return centroids
（３）kmenas
程序的主函数，通过迭代（划分样本－更新质心），实现聚类
def kmeans(dataSet, k):
"""
Function:通过迭代，确定质心和样本类别
Input :数据集，质心数量
Output :质心坐标 + [Ki,distance^2]
"""
"""
伪代码：
当质心还未更新完毕（各样本点的簇类值不再变化）:
1对每一个样本：
对每一个质心：
计算样本到质心的距离
选取得到最小距离值时的质心，作为该样本的簇类
判断该簇类是否是更新值，如果是：
将该样本的簇类和平方误差进行保存
2由已分好的簇类中取均值，重新确立质心
输出：质心 + 样本的簇类标签、
"""
numSamples = dataSet.shape[]
#获取样本数
clusterAssment = np.mat((np.zeros((numSamples,))))
clusterChanged = True
#初始化k个质心
centroids = initCentroids(dataSet, k)
#当聚类不在变化时，停止循环
while clusterChanged:
clusterChanged = False
#遍历所有样本
for i in range(numSamples):
#对所有质心点，计算样本点到质心的距离，找到样本点到
#一质心的最小距离，并取对该样本点进行划分
minDist = float('inf')
minIndex =
for j in range(k):
#计算点到质心的距离
distance = euclidentDistance(centroids[j,:], dataSet[i,:])
#取距点最近的质心为当前的簇类2
if distance < minDist:
minDist = distance
minIndex = j
#更新clusterChanged为True，将簇类和距离的平方保存
if clusterAssment[i,] != minIndex:
clusterChanged = True
clusterAssment[i,:] = minIndex, minDist**
#更新质心
for j in range(k):
pointsInCluster = dataSet[np.nonzero(clusterAssment[:,] == j)[]]
centroids[j,:] = np.mean(pointsInCluster, axis = )
print('完成聚类算法')
return centroids, clusterAssment
三、二分K-均值算法
在K-均值聚类中，点的簇分配结果值没有那么准确，K-均值算法收敛但是聚类效果较差。因为K-均值算法收敛到了局部最小值，而非全局最小值。因为初始的质心点是随机选取的，在对质心点优化过程的迭代，也是基于初始质心的位置而进行优化的，这样的优化结果只是这一局部的最优解，而非全局的。
那么，我们引入一种用于度量聚类效果的指标：SSE（Sum of Squared Error,误差平方和）。SSE对应函数euclidentDistance的返回结果，SSE值越小，表明数据点越接近于它们的质心，质心位于数据点的中央，聚类效果也越好。因为我们对误差（点到质心的距离）取了平方，因此更加重视那些远离中心的点。
因此，我们在每次划分簇的时候，对所有的划分结果用SSE进行比较，选取SSE值最小的划分方式进行聚类。这样避免了本应该划分的簇没有被划分，而点很集中的簇却被划分了的情况。
1、工作流程
- 首先将所有点作为一个簇，然后将该簇一分为二
- 之后选取其中一个簇继续划分，划分哪一个簇取决于其划分是否可以最大程度降低SSE值
- 上述基于SSE的划分过程不断重复，直到得到指定的簇数目为止。
2、伪代码
将所有的点看成一个簇
当簇数目小于k时
对每一个簇
在给定的簇上面进行K-均值聚类（k=2）
计算将该簇一分为二之后的总误差（被划分的簇+没有被选择划分的簇）
选择使得误差SSE最小的那个簇的划分操作执行
3、流程图
4、核心代码解释
def biKmeans(dataSet, k):
"""
Function:不断二次划分最小误差数据集，得到质点和分类
Input :数据集，质心数量
Output :质心坐标 + [Ki,distance^2]
"""
"""
伪代码：
初始化质心为所有样本点的均值
计算样本点到初始质心的欧式距离，clusterAssment
当确定的质心数量不足k个时：
分类标签索引为质心的数量- len（centList）
遍历每个质心：
得到质心类别对应的数据样本
将这些样本划分成2类，得到新的质心点和clusterAssment
计算总体误差 - 参与划分的样本误差和没参与划分的样本误差之和
当，当前误差值为最小误差时：
最佳分类标签(bestCentroidSplit)是当前的质心索引
最佳质心点（bestNewCentroids）是当前对应的质心点
bestClusterAssment为当前对应的clusterAssment
选择一个类别的样本继续划分，类别为 len（cenList），另外一个样本标签为bestCentroidToSplit
更新质心数组，最后一个质点更新为‘kmeans’中‘0’对应的质点，然后append进一个最新的质点
"""
m = np.shape(dataSet)[]
clusterAssment = np.mat(np.zeros((m,)))
#初始质心,为所有样本点的均值
centroid = np.mean(dataSet, axis = ).tolist()[]
centList = [centroid]
#计算样本点到质心的距离
for i in range(m):
clusterAssment[i,] = euclidentDistance(np.mat(centroid), dataSet[i,:]) **
#迭代收敛，分裂出新的质心，退出条件是分裂出的质心数量达到k
while len(centList) < k:
#定义误差值
minSSE = float('inf')
#看上去是定义长度， 实则为每个质心打标签（0，1，2……）
numCurrCluster = len(centList)
#判断哪个质心好
for i in range(numCurrCluster):
#得到属于该质心的数据
pointsInCurrCluster = dataSet[np.nonzero(clusterAssment[:,] == i)[],:]
#得到划分成2类的【质心，分类+误差】
centroids, splitClusterAssment = kmeans(pointsInCurrCluster, )
#计算质心划分后的误差
splitSSE = sum(splitClusterAssment[:,])
#计算没有参与划分的误差
notSplitSSE = sum(clusterAssment[np.nonzero(clusterAssment[:,] != i)[],])
currSplitSSE = splitSSE + notSplitSSE
#寻找最小的误差
if currSplitSSE < minSSE:
minSSE = currSplitSSE
bestCentroidToSplit = i
bestNewCentroids = centroids.copy()
bestClusterAssment = splitClusterAssment.copy()\
#修改集群索引以添加新集群， 类别1返回该质心原来的值， 0 更新为选择误差最小的质心再进行划分
#给予新的分类新的标签，另外一个分类标签沿用原来的
bestClusterAssment[np.nonzero(bestClusterAssment[:,] == )[],[]] = numCurrCluster
bestClusterAssment[np.nonzero(bestClusterAssment[:,] == )[],[]] = bestCentroidToSplit
#更新和添加新的2子簇的质心
centList[bestCentroidToSplit] = bestNewCentroids[,:]
centList.append(bestNewCentroids[,:])
#更新集群被更改的样本的索引和错误 - 在kmens中被贴上‘0’分类，在此处进行恢复
clusterAssment[np.nonzero(clusterAssment[:,] == bestCentroidToSplit), :] = bestClusterAssment
print('二分k-均值算法完成')
return np.mat(centList), clusterAssment
![简单文档分类——朴素贝叶斯算法朴素贝叶斯算法简单文档分类实例步骤总结朴素贝叶斯分类调用(sklearn)[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)