聚类算法之k-means
文章目录
分类与聚类
分类是指将数据归于一系列已知类别之中的某个类的分类过程
聚类是根据客体属性对一系列未分类的客体进行类别的识别，把一组个体按照相似性归成若干类。聚类属于无监督学习（根据类别未知(没有被标记)的训练样本解决模式识别中的各种问题，称之为无监督学习。）
聚类的划分
聚类分析的算法可以分为划分法，层次法，基于密度的方法，基于网格的方法，基于模型的方法。
其中，最广泛使用的聚类算法k-means算法属于划分法
划分法
给定一个有n个记录的数据集，划分法将构造k个分组，每一个分组代表一个聚类（k<n）
k个分组满足以下条件：
- 每个分组至少包含一个数据记录
- 每个数据记录属于且仅属于一个分组（某些模糊聚类算法中该条件可以放宽，例如c均值算法）
k-means算法
k-means算法，也被称为k-均值或者k-平均算法。
k-means算法步骤
-
首先随机选取k个对象作为初始的k个簇（一堆）的中心
-
对剩下的每个对象，算出它到每个质心的距离，并将它分给最近的簇
-
重新计算每簇的中心
-
2,3过程不断重复知道准则函数不断收敛
距离的计算
1.欧几里得距离：
2.曼哈顿距离
3,闵可夫斯基距离
准则函数
使用准则函数的实质也可以理解为：你算的每个簇的中心的坐标不再改变；每个对象所属的簇不再改变
准则函数：平方误差和准则函数，即SSE（sum of the squared error）
公式为：
SSE是数据集中所有对象的平方误差总和，p为数据对象，mi是簇ci的平均值，这个准则函数使生成的结果尽可能的紧凑和独立。
应用实例理解k-means算法
下图是采集的亚洲15只球队在2006-2010年键大型比赛的战绩（澳大利亚未收入），赋分值的过程就不多说了，图如下：
第一步：规格化数据
由于取值范围大的属性对距离的影响改与取值范围小的属性（对中心的计算），不利于反映这真实的相异度，因此聚类前，一般要对属性值进行规格化。
规格化：将各个属性值按比例映射到相同的取值区间，通常为[0,1]
公式：
min(ai)表示这一列属性的最小值，max（ai）表示这一列属性的最大值
规范后的数据集为：
已第一个属性为例（B）：最大值为50，最小值为17
第一个数据集（中国）的第一个属性（2006年世界杯）规格化为：（50-17）/（50-17）=1
第二个数据集（日本）的第一个属性（2006年世界杯）规格化为：（28-17）/（50-17）≈0.3
第二步：选取k个初始聚类中心
设k=3，即将这15支球队分成三个簇，假设抽取日本，巴林，和泰国为三个簇的初始中心（A,B,C）,则：A：{0.3，0，0.19}，B{0.7，0.76，0.5},C{1，1，0.5}。
第三步：计算每个对象到每个簇中心的距离
这里使用欧几里得距离：
例：中国{1,1，0.5}，A：{0.3，0，0.19}
计算给个对象到各个簇中心的距离为：
于是做出以下分类：
A：日本，韩国
B：伊朗，沙特，乌兹别克斯坦，巴林，朝鲜
C：中国，伊拉克，卡塔尔，阿联酋，泰国，越南，阿曼，印尼
第四步：根据上面第一次分类的结果重新计算中心
A：{（0.3+0）/2=0.15，(0+0.15)/2=0.075，(0.19+0.13)/2=0.16}={0.15,0.0.75,0.16}
B:{(0.24+0.3+0.73)/5=0.528,(0.764+0.68)/5=0.744,(0.25+0.06+0.25+0.5+1)/5=0.412}={0.528,0.744,0.412}
C:{1,0.94,0.40625}
第五步：判断
你算的每个簇的中心的坐标是否和上一轮的坐标一样；每个对象所属的簇和上一轮所属对象是否一样，不一样就要进行第三四步，直到不变
实例的最后分类
A：日本，韩国
B：伊朗，沙特，乌兹别克斯坦，巴林，朝鲜
C：中国，伊拉克，卡塔尔，阿联酋，泰国，越南，阿曼，印尼
k-means算法可视化python代码
连接：代码有详细的注释
运用上述代码可运行出结果：
有些数据的相同，有的数据可能就是中心
k-means算法的优缺点
优点：
- 是解决聚类问题的一种经典算法，简单，快速
- 对处理大数据集，该算法是相对可伸缩和高效率的
- 当结果簇是密集的，簇与簇之间区别明显时，它的效果好
缺点： - 必须事先给出k值，但很多时候并不知道数据集应该分成多少个类别才最合适。聚类结果对初值敏感，对于不同的初始值，可能会导致不同的结果
- 初始聚类中心的选择对聚类结果又较大的影响，一旦初值选择的不好，可能无法得到有效的聚类结果。可以多设置一些不同的初值，对比最后的运算的结果，一直到结果趋于稳定来解决这一问题，但比较耗时，浪费资源
- 对于“噪声”和孤立点数据是敏感的