聚类算法

2018/6/8 posted in  MachineLearning

什么是聚类算法

聚类算法的度量

聚类的思想

K-Means算法

K-Means++算法

K-Means||算法

Canopy算法

Mini Batch K-Means算法

聚类算法的衡量指标

层次聚类方法

层次聚类方法对给定的数据集进行层次的分解,直到满足某种条件为止,传统的层次聚类算法主要分为两大类算法:
凝聚的层次聚类(AGNES算法:AGglomerative NESting):采用自底向上的策略.最初将每个对象作为一个簇,然后这些簇根据某些准则被一步一步合并,两个簇间的距离可以由这两个不同簇中距离最近的数据点的相似度来确定;聚类的合并过程反复进行直到所有的对象满足簇数目.

分裂的层次聚类(DIANA算法:DIvisive ANALysis):采用自顶向下的策略.首先将所有对象置于一个簇中,然后按照某种既定的规则逐渐细分为越来越小的簇(比如最大的欧式距离),直到达到某个终结条件(簇数目或者簇距离达到阈值).

AGNES和DIANA算法优缺点:

  • 简单,理解容易
  • 合并点/分裂点选择不太容易
  • 合并/分类的操作不能进行撤销
  • 大数据集不太适合
  • 执行效率较低

AGNES算法中簇间距离

  • 最小距离(SL聚类)
    • 两个聚簇中最近的两个样本之间的距离(single/word-linkage聚类法)
    • 最终得到模型容易形成链式结构
  • 最大距离(CL聚类)
    • 两个聚簇中最远的两个样本的距离(complete-linkage聚类法)
    • 如果存在异常值,那么构建可能不太稳定
  • 平均距离(AL聚类)
    • 两个聚类中样本间两两距离的平均值(average-linkage聚类法)
    • 两个聚簇中样本间两两距离的中值(median-linkage聚类法)

密度聚类方法

谱聚类