大家早安、午安、晚安哈，继续学习机器学习算法，接下来几篇均是无监督学习算法。今天首先学习K-means（K-均值）聚类算法，希望我整理的资料对大家有用。
聚类是一种无监督的学习（不同于分类，事先不知道目标类别），它将相似的对象归到同一个簇中。簇内的对象越相似，聚类的效果越好。
K-means算法是发现给定数据集的k个簇的算法。簇个数k是用户给定的，每个簇通过其质心(centroid)，即簇中所有点的中心来描述。
1、算法描述
1）比如针对下图所示的无标签点集，想要把他分为两类（即k=2）
图1
2）那么，随机分配两个点作为每个簇的质心，比如下图中的红色和蓝色的‘x’
图2
3）然后判断全部点到这两个质心的距离，与质心距离较近的标志为同种颜色：
图3
4）根据新划分的簇，重新计算质心，直到达到一定的要求（比如均方误差最小等）
图4
上述循环过程可以用下图所示的文字以及公式来描述：
图5
5）接下来，将基于Python编程实现K-means算法
（1）准备一些基本工具函数：获取数据、计算欧氏距离、初始化簇
图1
（2）设置K-Means函数
图2 K-means函数
（3）将原始特征值（蓝色表示）和质心（红色星星）表示出来
图3
图3
因为在上述代码中，我们设置的是K=4，也就是4个质心
备注：在编程过程中发现，当数据为array类型时，才能使用scatter函数绘制点，当数据类型是matrix时，会报错“RuntimeError: maximum recursion depth exceeded”
在上述代码中，clusterAssment数组中，第一列表示的是距离该样本最近的质心的下标，第二列表示该点与质心的距离，其实这个距离也可以看做是将该样本分为该类型的误差大小。距离该质心更近的点，距离越小，该误差也就越小。一种用于度量聚类效果的指标是SSE（Sum of Squared Error，误差平方和）。SSE越小表示数据点越接近它们的质心，聚类效果越好。
2、二分K-means算法（bisecting K-means）
该算法主要是为克服K-means算法收敛于局部最小值的问题。该算法首先将所有点作为一个簇，然后将该簇一分为二。之后选择其中一个簇继续进行划分，选择哪个簇进行划分取决于对其划分是否可以最大程度降低SSE值。上述基于SSE的划分过程不断重复，直到得到用户指定的簇数目为止。
图4
图5
在运行上述代码中，发现每次获得的质心的位置是变化的，效果好点的如图6，效果不好的如图7，这是什么原因，为什么每次计算质心会出现不一样的效果？
图6
图7
其实，主要原因是二分K-means算法有时候会陷入全局最小值，所以需要运行多次。
综上所述：K-means聚类算法以k个随机质心开始，计算每个点到质心的距离；然后每个点会被分配到距离其最近的簇，然后这个簇内的数据更新质心。以上过程重复多次，直到质心不再改变。因为该算法容易受初始质心的影响而陷入局部最优，提出了二分K-means聚类算法。二分K-means算法将所有点作为一个簇，然后使用K-means算法（k=2）对其划分。下一次迭代时，选择有最大误差的簇进行划分。该过程重复直到k个簇创建成功。但是不得不说，根据什么仿真的结果，该算法有时会陷入全局最小值，需要运行多次。
PS：出差中及时不干活，也会感觉累，然后就不想好好学习，不知道大家有木有好的建议可以让出差
网友评论