层次聚类

层次聚类是一种聚类算法，其基本思想是：将待分类的所有观测值（或样品）视为一个初始的聚类群体，然后根据某种聚类准则，将这个聚类群体按照层次方式依次分解为若干个子群，直到满足某种终止条件为止。

层次聚类

• 简介
  • 算法思想：按照某种方法进行层次划分，直到满足某种条件为止
  • 图解：
• 两种层次聚类方法
  • 凝聚法
    • 算法思路：自底向上，首先将每个对象作为一个簇，然后将簇合并为越来越大的簇，直到所有对象都在一个簇或满足某个终止条件
    • 算法步骤
      • 第一步：计算各个样本间的距离
      • 第二步：距离最小的两个样本聚为一类，即簇C1
      • 第三步：计算其他样本到C1的距离
        • 簇之间的距离度量方法
          • 方法一：最短距离法(簇Ci与簇Cj中样本的距离最小值作为簇间距离)
          • 方法二：最长距离法(簇Ci与簇Cj中样本的距离最大值作为簇间距离)
          • 方法三：类平均法(簇Ci与簇Cj中所有样本的距离的均值作为簇间距离)
          • 方法四：中心法(簇Ci与簇Cj的中心点(簇中样本均值)的距离作为簇间距离)
      • 第四步：循环步骤二、三，直到所有对象都在一个簇或满足某个终止条件
      • 图解：
  • 分裂法
    • 算法思路：自顶向下，首先将所有对象置于同一个簇里，然后逐渐划分为越来越小的簇，直到每个对象自成一簇或满足某个终止条件
    • 算法步骤
      • 第一步：将所有样本归为一簇，计算各个样本的距离，选取距离最远的两个样本
      • 第二步：将距离最远的两个样本分为两个簇，计算其他样本到两个簇的距离
        • 距离度量方法与凝聚法如出一辙
      • 第三步：其他样本划分到距离较近的簇
      • 第四步：循环步骤二、步骤三，直到每个对象自成一簇或满足某个终止条件
      • 图解：
• 层次聚类的优缺点
  • 优点
    • 距离和规则的相似度容易定义
    • 不需要预先制定聚类数
    • 可以发现类的层次关系
  • 缺点
    • 计算复杂度太高，数据量过大无法适用
    • 模型对异常值较为敏感
    • 聚类形状偏向于链状
• 优化
  • 针对层次聚类数据量过大无法使用问题
    • 方法：采用多阶段聚类技术，通过增量的方式进行聚类大大减少聚类时间，即BIRCH算法
      • 增量：每一个数据点的聚类的决策都是基于当前已经处理过的数据点，而不是基于全局的数据点
    • BIRCH算法
      • 算法原理：聚类特征使用3元组进行一个簇的相关信息，通过构建满足分枝因子和簇直径限制的聚类特征树来求聚类，每一个叶子节点就是一个簇
      • 几个概念
        • 聚类特征(CF)
          • 定义：CF是一个三元组，可以用（N，LS，SS）表示。其中N代表了这个CF中拥有的样本数；LS代表了这个CF中拥有的样本点各特征维度的和向量，SS代表了这个CF中拥有的样本点各特征维度的平方和
          • 性质：满足线性关系，即CF1+CF2=(N1+N2,LS1+LS2,SS1+SS2)
          • 举例：设某个CF包含5个二维度特征样本(3,4), (2,6), (4,5), (4,7), (3,8)
            • CF的N=5
            • CF的LS=(3+2+4+4+3,4+6+5+7+8)=(16,30)
            • CF的SS=(3^2+2^2+4^2+4^2+3^2+4^2+6^2+5^2+7^2+8^2)=54+190=244
        • 聚类特征树(CF-tree)
          • 定义：叶子节点为簇，非叶子节点存储了其后代的CF总和
          • CF Tree的参数
            • 非叶子节点最大个数：B（分支因子）
            • 每个叶子节点包含的最大CF数：L
            • 叶子节点每个CF的最大半径阈值：T
          • CF-tree的创建过程
            • 第一步：读入第一个样本，将其纳入新的三元组LN1
            • 图解：
            • 第二步：读入第二个样本，如果它与前一个样本在半径为T的球体内，则置为同一个三元组，否则生成新的三元组LN2
            • 图解：
            • 第三步：如果新样本它离LN1节点最近，但都不再SC1，SC2，SC3的超球体半径T内，且L=3，则需要进行分裂
            • 图解：
            • 第四步：LN1里所有CF元组中，找到两个最远的CF做这两个新叶子节点的种子CF，然后将LN1节点里所有CF sc1, sc2, sc3，以及新样本点的新元组sc6划分到两个新的叶子节点上
            • 图解：
            • 第五步：循环步骤二、三、四，直到满足终止条件
      • 优缺点
        • 优点
          • 聚类速度快，可以识别噪音点
          • 线性可伸缩性，聚类质量较好
        • 缺点
          • 只能处理数值数据
          • 对数据的输入次序敏感
          • 簇非球形时效果不好