11.聚类 - 四、层次聚类 - 《AI算法工程师手册》

四、层次聚类
- 4.1 AGNES 算法
- 4.2 BIRCH 算法

四、层次聚类

层次聚类hierarchical clustering 试图在不同层次上对数据集进行划分，从而形成树形的聚类结构。

4.1 AGNES 算法

AGglomerative NESting：AGNES是一种常用的采用自底向上聚合策略的层次聚类算法。
AGNES首先将数据集中的每个样本看作一个初始的聚类簇，然后在算法运行的每一步中，找出距离最近的两个聚类簇进行合并。

合并过程不断重复，直到达到预设的聚类簇的个数。
这里的关键在于：如何计算聚类簇之间的距离？

由于每个簇就是一个集合，因此只需要采用关于集合的某个距离即可。给定聚类簇，有三种距离：
- 最小距离：。
  
  最小距离由两个簇的最近样本决定。
- 最大距离：。
  
  最大距离由两个簇的最远样本决定。
- 平均距离：。
  
  平均距离由两个簇的所有样本决定。
AGNES 算法可以采取上述任意一种距离：
- 当AGNES算法的聚类簇距离采用时，称作单链接single-linkage算法。
- 当AGNES算法的聚类簇距离采用时，称作全链接complete-linkage算法。
- 当AGNES算法的聚类簇距离采用时，称作均链接average-linkage算法。
AGNES算法：
- 输入：
  - 数据集
  - 聚类簇距离度量函数
  - 聚类簇数量
- 输出：簇划分
- 算法步骤：
  - 初始化：将每个样本都作为一个簇
  - 迭代，终止条件为聚类簇的数量为。迭代过程为：
    
    计算聚类簇之间的距离，找出距离最近的两个簇，将这两个簇合并。
    
    每进行一次迭代，聚类簇的数量就减少一些。
AGNES 算法的优点：
- 距离容易定义，使用限制较少。
- 可以发现聚类的层次关系。
AGNES 算法的缺点：
- 计算复杂度较高。
- 算法容易聚成链状。

4.2 BIRCH 算法

BIRCH:Balanced Iterative Reducing and Clustering Using Hierarchies 算法通过聚类特征树CF Tree:Clustering Feature True来执行层次聚类，适合于样本量较大、聚类类别数较大的场景。

4.2.1 聚类特征

聚类特征CF：每个CF 都是刻画一个簇的特征的三元组：。其中：
- ：表示簇内样本数量的数量。
- ：表示簇内样本的线性求和：，其中为该CF 对应的簇。
- ：表示簇内样本的长度的平方和。，其中为该CF 对应的簇。
根据CF 的定义可知：如果CF1 和 CF2 分别表示两个不相交的簇的特征，如果将这两个簇合并成一个大簇，则大簇的特征为：。

即：CF 满足可加性。
给定聚类特征CF，则可以统计出簇的一些统计量：
- 簇心：。
- 簇内数据点到簇心的平均距离（也称作簇的半径）：。
- 簇内两两数据点之间的平均距离（也称作簇的直径）：。
给定两个不相交的簇，其特征分别为和。

假设合并之后的簇为，其中，，。

可以通过下列的距离来度量 CF1 和 CF2 的相异性：
- 簇心欧氏距离centroid Euclidian distance：，其中分别为各自的簇心。
- 簇心曼哈顿距离centroid Manhattan distance：。
- 簇连通平均距离average inter-cluster distance：
- 全连通平均距离average intra-cluster distance：
- 方差恶化距离variance incress distance：。

4.2.2 CF 树

CF树的结构类似于平衡B+树。树由三种结点构成：根结点、中间结点、叶结点。
- 根结点、中间结点：由若干个聚类特征CF ，以及这些CF 指向子结点的指针组成。
- 叶结点：由若干个聚类特征CF 组成。
  - 叶结点没有子结点，因此CF 没有指向子结点的指针。
  - 所有的叶结点通过双向链表连接起来。
  - 在BIRCH 算法结束时，叶结点的每个CF 对应的样本集就对应了一个簇。
CF 树有三个关键参数：
- 枝平衡因子：非叶结点中，最多不能包含超过个 CF 。
- 叶平衡因子：叶结点中，最多不能包含超过个 CF 。
- 空间阈值：叶结点中，每个CF 对应的子簇的大小（通过簇半径来描述）不能超过。
由于CF 的可加性，所以CF 树中，每个父结点的CF 等于它所有子结点的所有CF 之和。
CF 树的生成算法：
- 输入：
  - 样本集
  - 枝平衡因子
  - 叶平衡因子
  - 空间阈值
- 输出：CF 树
- 算法步骤：
  - 初始化：CF 树的根结点为空。
  - 随机从样本集中选出一个样本，放入一个新的CF 中，并将该CF 放入到根结点中。
  - 遍历中的样本，并向CF 树中插入。迭代停止条件为：样本集中所有样本都插入到CF 树中。
    
    迭代过程如下：
    - 随机从样本集中选出一个样本，从根结点向下寻找与距离最近的叶结点，和里与最近的。
    - 如果加入到对应的簇中之后，该簇的簇半径，则将加入到对应的簇中，并更新路径上的所有CF 。本次插入结束。
    - 否则，创建一个新的CF，将放入该CF 中，并将该CF 添加到叶结点中。
      
      如果的CF 数量小于，则更新路径上的所有CF 。本次插入结束。
    - 否则，将叶结点分裂为两个新的叶结点。分裂方式为：
      - 选择叶结点中距离最远的两个CF，分别作为中的首个CF 。
      - 将叶结点中剩下的CF 按照距离这两个CF 的远近，分别放置到中。
    - 依次向上检查父结点是否也需要分裂。如果需要，则按照和叶子结点分裂方式相同。

4.2.3 BIRCH 算法

BIRCH 算法的主要步骤是建立CF 树，除此之外还涉及到CF 树的瘦身、离群点的处理。
BIRCH 需要对CF 树瘦身，有两个原因：
- 将数据点插入到CF 树的过程中，用于存储CF 树结点及其相关信息的内存有限，导致部分数据点生长形成的CF 树占满了内存。因此需要对CF 树瘦身，从而使得剩下的数据点也能插入到CF 树中。
- CF 树生长完毕后，如果叶结点中的CF 对应的簇太小，则会影响后续聚类的速度和质量。
BIRCH 瘦身是在将增加的过程。算法会在内存中同时存放旧树和新树，初始时刻为空。
- 算法同时处理和，将中的 CF 迁移到中。
- 在完成所有的CF 迁移之后，为空，就是瘦身后的 CF 树。
BIRCH 离群点的处理：
- 在对CF 瘦身之后，搜索所有叶结点中的所有子簇，寻找那些稀疏子簇，并将稀疏子簇放入待定区。
  
  稀疏子簇：簇内数据点的数量远远少于所有子簇的平均数据点的那些子簇。
  
  将稀疏子簇放入待定区时，需要同步更新CF 树上相关路径及结点。
- 当中所有数据点都被插入之后，扫描待定区中的所有数据点（这些数据点就是候选的离群点），并尝试将其插入到CF 树中。
  
  如果数据点无法插入到CF 树中，则可以确定为真正的离群点。
BIRCH 算法：
- 输入：
  - 样本集
  - 枝平衡因子
  - 叶平衡因子
  - 空间阈值
- 输出：CF 树
- 算法步骤：
  - 建立 CF 树。
  - （可选）对CF 树瘦身、去除离群点，以及合并距离非常近的CF 。
  - （可选）利用其它的一些聚类算法（如：k-means）对CF树的所有叶结点中的CF 进行聚类，得到新的CF 树。
    
    这是为了消除由于样本读入顺序不同导致产生不合理的树结构。
    
    这一步是对 CF 结构进行聚类。由于每个CF 对应一组样本，因此对CF 聚类就是对进行聚类。
  - （可选）将上一步得到的、新的CF 树的叶结点中每个簇的中心点作为簇心，对所有样本按照它距这些中心点的距离远近进行聚类。
    
    这是对上一步的结果进行精修。
BIRCH 算法优点：
- 节省内存。所有样本都存放在磁盘上，内存中仅仅存放CF 结构。
- 计算速度快。只需要扫描一遍就可以建立CF 树。
- 可以识别噪声点。
BIRCH 算法缺点：
- 结果依赖于数据点的插入顺序。原本属于同一个簇的两个点可能由于插入顺序相差很远，从而导致分配到不同的簇中。
  
  甚至同一个点在不同时刻插入，也会被分配到不同的簇中。
- 对非球状的簇聚类效果不好。这是因为簇直径和簇间距离的计算方法导致。
- 每个结点只能包含规定数目的子结点，最后聚类的簇可能和真实的簇差距很大。
BIRCH 可以不用指定聚类的类别数。
- 如果不指定，则最终叶结点中CF 的数量就是。
- 如果指定，则需要将叶结点按照距离远近进行合并，直到叶结点中CF 数量等于。