• 优点: 容易实现
  • 缺点: 可能收敛到局部最小值,在大规模数据集上收敛较慢
  • 适用数据类型: 数值型数据
    k-means是发现给定数据集的K个簇的算法.簇个数K是用户给定的,每一个簇通过其’质心(centroid)’,即簇中所有点的中心来描述

    K-means的工作流程

  • 上述过程伪代码如下

  1. 准备数据: 需要数值型数据来计算距离,也可以将标称型数据映射为二值性数据再用于距离计算
  2. 分析数据: 使用任意方法
  3. 训练算法: 不适用与无监督学习,即无监督学习没有训练过程
  4. 测试算法: 应用聚类算法,观察结果.可以使用量化的误差指标如误差平方和来评价算法的结果
  5. 使用算法: 可用用于所希望的任何应用.通常情况下,簇质心可以代表整个簇的数据来做出决策

    使用后处理来提高聚类性能

  • 在包含簇分配结果的矩阵中保存着每个点的误差,即该点到簇质心的距离平方值.这个误差可以确定用户预先定义的参数K是否正确,也可以确定生成的簇是否较好
  • SSE(Sum of Squared Error,误差平方和):一种用于度量聚类效果的指标.
  • SSE值越小表示数据点越接近于它们的质心,聚类效果也越好.因为对误差取了平方,因此更重视那些远离中心的点.一种肯定可以降低SSE值的方法事增加簇的个数,但这违背了聚类的目标.聚类的目标事在保持簇数据不变的情况下提高簇的质量
  • 为了保持簇总数不变,可以将两个簇进行合并.可以很容易对二维数据上的聚类进行可视化,如果是多维 的,有两种可以量化的办法:合并最近的质心,或者合并两个使得SSE增幅最小的质心.第一种思路通过计算所有质心之间的距离,然后合并距离最近的两个点来实现.第二种方法需要合并两个簇然后计算总SSE值.必须在所有可能的两个簇上重复上述处理过程,直到找到合并最佳的两个簇为止

  • 二分k-means的伪代码形式如下:

    1.   当簇数目小于k时
    3.       计算总误差
    5.       计算将该簇一分为二之后的总误差

    对于地理数据应用二分k-means

  1. 收集数据: 使用Yahoo!PlaceFinder API收集数据
  2. 准备数据: 只保留经纬度信息
  3. 分析数据: 使用Matplotlib来构建一个二维数据图,其中包含簇与地图
  4. 训练算法: 训练不适用于无监督学习
  5. 测试算法: 使用biKmeans()函数

欧式距离公式: $d=\sqrt{(xA_0-xB_0)^2+(xA_1-xB_1)^2