当我们在谈论kmeans（5）

时间：2021-01-02 04:38:55

本系列意在长期连载分享，内容上可能也会有所删改；

因此如果转载，请务必保留源地址，非常感谢！

博客园：http://www.cnblogs.com/data-miner/（暂时公式显示有问题）

其他：建设中…

当我们在谈论kmeans：总结

概述

　　通过前面阅读K-means相关论文，大致能梳理出K-means算法发展过程中的一些轨迹。由于本人所阅读的仅仅是一部分，因此还会有更多的方面，欢迎大家补充（补充时请给出具体例子）。

  1. K-means算法的提出
  2. 对K-means算法的性质进行分析的文章相继发出
  3. 对K-means算法思想进行扩展：
    • 有作者提出“Maximum Entropy”算法，并表示K-means为其一种特殊形式
    • 后又有作者提出“Mean Shift”算法，并表示“Maximum Entropy”也是其特殊形式
  4. 针对K-means缺陷，对K-means算法进行修改（一般仅适用于某场景）：
    • 提出online的K-means
    • 提出针对非凸数据集的K-means
    • 提出应用在FPGA中的K-means
    • 提出自动对特征进行加权的K-means
    • Intelligent K-means算法使用异常检测的思想聚类
  5. 对K-means算法进行优化：
    • KD树加速的K-means
    • 利用SVD分解加速K-means
    • K-means++的初始化聚类中心算法
  6. 将K-means与新提出的思想融合：
    • 结合Ensembling与K-means

K-means存在的问题

K-means由于简单有效被大量的用于数据预处理、数据分析等。在K-means被实际应用的过程中，大家也逐渐发现它本身存在很多的问题。如：

  1. 计算量大
  2. 聚类数量K需要提前设定，并影响聚类效果
  3. 聚类中心需要人为初始化，并影响聚类效果
  4. 异常点的存在，会影响聚类效果
  5. 只能收敛到局部最优

其中每个问题都有作者分析，并尝试提出解决办法：

  1. 计算量大
    • KD树加速K-means
  2. 聚类数量K需要提前设定，并影响聚类效果
    • 各种估计K的方法
  3. 聚类中心需要人为初始化，并影响聚类效果
    • K-means++方法
    • 其他初始化聚类中心方法
  4. 异常点的存在，会影响聚类效果
    • 数据预处理
  5. 只能收敛到局部最优
    • 未知

以下我们对其中两点（“类别数量估计”，“初始化聚类中心”）进行更多的介绍

类别数量估计

估计类别数量，现在还没有很通用的方法。以下介绍常见的估计类别数量的一些方式

  1. 数据的先验知识，或者数据进行简单分析能得到

  2. 基于变化的算法：即定义一个函数，认为在正确的K时会产生极值。

  3. 基于结构的算法：即比较类内距离、类间距离以确定K。

  4. 基于一致性矩阵的算法：即认为在正确的K时，不同聚类的结果会更加相似，以此确定K。

  5. 基于层次聚类：即基于合并或分裂的思想，在一定情况下停止获得K。

  6. 基于采样的算法：即对样本采样，分别做聚类；根据这些结果的相似性确定K。

初始化聚类中心

接下来介绍几个看到的初始化聚类中心的方法。需要强调的是，在任何场景下都合适的方法是不存在的。理想情况应该是针对数据的特点，挑选或设计出适合的方法。

  1. K-means++已经被证明是一种简单、好用的方法
  2. 先计算整体样本中心，然后根据样本点到中心的距离，由近至远均匀采样作为初试聚类中心
  3. 初步将数据分成K个区域，将每个区域中心作为初始聚类中心
  4. 计算出每个点的”密度“，认为”密度“较大的是聚类中心。先把”密度“最大的挑出作为第一个聚类中心，从剩下的点中找出密度最大，且离所有已有聚类中心大于一定距离的点作为下一个聚类中心，直到选择了K个
  5. 计算整体均值，作为第一个聚类中心。从剩下的点中顺序寻找，当遇到离所有已有聚类中心大于一定距离的点，则作为下一个聚类中心，直到选择了K个

其他聚类算法总结

ING。。。

相关文章