聚类算法

聚类是数据挖掘中的概念，就是按照某个特定标准(如距离)把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，同时不在同一个簇中的数据对象的差异性也尽可能地大。也即聚类后同一类的数据尽可能聚集到一起，不同类数据尽量分离。聚类的时候，我们并不关心某一类是什么，我们需要实现的目标只是把相似的东西聚到一起。因此，一个聚类算法通常只需要知道如何计算相似度就可以开始工作了，因此 clustering 通常并不需要使用训练数据进行学习，这在Machine Learning中被称作unsupervised learning (无监督学习)。

聚类过程

• 数据准备: 包括特征标准化和降维；
• 特征选择：从最初的特征中选择最有效的特征,并将其存储于向量中；
• 特征提取：通过对所选择的特征进行转换形成新的突出特征；
• 聚类(或分组)：首先选择合适特征类型的某种距离函数(或构造新的距离函数)进行接近程度的度量，而后执行聚类或分组；
• 聚类结果评估：是指对聚类结果进行评估，评估主要有3种：外部有效性评估、内部有效性评估和相关性测试评估。

聚类算法分类

• 划分式聚类的算法： 预先指定聚类数目或聚类中心，反复迭代逐步降低目标函数误差值直至 收敛，得到最终结果
  • K-Means
    • 算法：
      1. 选择k个聚类中心
      2. 将所有样本划分到与其距离最近的中心
      3. 根据划分好的k个类，重新计算k个聚类中心，如果不满足结束条件重复步骤2，否则结束。
    • 缺点：
      • 收敛太慢
      • 算法复杂度高O(nkt)
      • 不能发现非凸形状的簇，或大小差别很大的簇
      • 需样本存在均值（限定数据种类）
      • 需先确定k的个数
      • 对噪声和离群点敏感
      • 最重要是结果不一定是全局最优，只能保证局部最优。
      • 结果不稳定
      • 无法增量计算
    • 优点
      • 速度较快
      • 原理简单易于实现
      • 效果还不错
    • 改进:
      • k-means++: 使初始的聚类中心尽量远
• 基于模型的聚类算法: 为每簇假定了一个模型，寻找数据对给定模型的最佳拟合
  • GMM SOM
• 基于密度
  • DBSCAN
• 基于网格
  • STING(Statistical INformation Grid)
  • CLIQUE(CLustering In QUEst)

• 基于连通性

• 层次聚类
  • 自顶向下
  • 自地向上
• 流式数据聚类算法
  • single pass

算法实践

K-Means