K-means

K-means聚类算法原理及拓展。算法思想:针对给定的数据对象集，按照数据对象之间的距离大小，将数据对象集划分为K个簇，让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。

K-means

• 简介
  • 算法思想：针对给定的数据对象集，按照数据对象之间的距离大小，将数据对象集划分为K个簇，让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大
  • 图解：
• 算法步骤
  • 第一步：选择K个簇的初始中心
  • 第二步：计算各个样本到K个初始中心的距离，并归于距离最近的簇
  • 第三步：重新计算簇的中心(簇中样本的均值)
  • 第四步：循环步骤二、步骤三，直到所有样本不再变化
  • 图解：
• K-means需要思考的几个问题
  • 簇的数量如何确定？
    • 方法一：手肘法(计算各个K值下模型的SSE，选择SSE变化最小的K值)
    • 图解：
    • 方法二：轮廓系数(计算各个K值下模型的轮廓系数，选择轮廓系数最大的K值)
      • 思想：通过考察簇的分离情况与紧凑情况进行聚类评估
      • 图解：
  • 初始中心如何确定？
    • 方法一：随机选择
    • 方法二：指定位置
    • 方法三：K-means++
      • 思想：选取初始中心时，尽可能使各个初始中心距离较远
      • 图解：
• K-means的优缺点
  • 优点
    • 针对大型数据集同样简单高效、时间复杂度、空间复杂度低
    • 算法的可解释度较强
  • 缺点
    • 数据集大时计算速度较慢且结果容易局部最优
    • K-means对K值的数量与初始中心的位置较为敏感
    • K-means对噪声和离群值非常敏感
    • 面对含分类型属性的数据集无法计算均值，导致算法不可用
    • K-means只能聚类出球形簇
• K-means的优化
  • 针对数据集过大计算速度缓慢的问题
    • 方法：多次对数据集随机抽样，每次抽样的子集均采用K-means进行聚类，直到簇中心趋于稳定为止(MiniBatchKMeans)
    • MiniBatchKMeans算法步骤
      • 第一步：样本集随机采样
      • 第二步：K-means
      • 第三步：循环步骤一、二，直到簇中心趋于稳定
  • 针对属性为分类型无法计算均值的问题
    • 方法：通过计算众数取代均值(K-mode)
  • 针对难以确定聚类个数K的数据集
    • 方法：通过给定区域中的样本的均值计算聚类中心，并不断更新聚类中心，直到聚类中心趋于稳定为止(Mean-Shift)
    • Mean-Shift算法步骤
      • 第一步：随机选取一个样本点，计算其他样本点到它的距离的均值向量：
      • 第二步：根据均值向量，移动样本点的位置，再次计算其他样本点到它的距离的均值向量，直到均值向量的绝对值足够小或样本点无法移动为止
      • 第三步：重复步骤一、二，直到遍历完所有的样本点
    • Mean-Shift优化
      • 针对均值向量的计算，没考虑其他样本点对当前样本点的贡献
        • 通过高斯核函数度量其他样本点对当前样本点的贡献度：