四、层次聚类

发布于 2023-07-17 23:38:25 字数 9923 浏览 0 评论 0 收藏 0

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

4.1 AGNES 算法

AGglomerative NESting：AGNES是一种常用的采用自底向上聚合策略的层次聚类算法。
AGNES首先将数据集中的每个样本看作一个初始的聚类簇，然后在算法运行的每一步中，找出距离最近的两个聚类簇进行合并。
合并过程不断重复，直到达到预设的聚类簇的个数。
这里的关键在于：如何计算聚类簇之间的距离？
由于每个簇就是一个集合，因此只需要采用关于集合的某个距离即可。给定聚类簇 $ MathJax-Element-463 $ ，有三种距离：
- 最小距离： $ MathJax-Element-464 $ 。
  最小距离由两个簇的最近样本决定。
- 最大距离： $ MathJax-Element-465 $ 。
  最大距离由两个簇的最远样本决定。
- 平均距离： $ MathJax-Element-466 $ 。
  平均距离由两个簇的所有样本决定。
AGNES 算法可以采取上述任意一种距离：
- 当AGNES算法的聚类簇距离采用 $ MathJax-Element-467 $ 时，称作单链接single-linkage算法。
- 当AGNES算法的聚类簇距离采用 $ MathJax-Element-468 $ 时，称作全链接complete-linkage算法。
- 当AGNES算法的聚类簇距离采用 $ MathJax-Element-469 $ 时，称作均链接average-linkage算法。
AGNES算法：
- 输入：
  - 数据集 $ MathJax-Element-470 $
  - 聚类簇距离度量函数 $ MathJax-Element-471 $
  - 聚类簇数量 $ MathJax-Element-554 $
- 输出：簇划分 $ MathJax-Element-473 $
- 算法步骤：
  - 初始化：将每个样本都作为一个簇
    $ \mathbb C_i=\{\mathbf{\vec x}_i\} ,i=1,2,\cdots,N $
  - 迭代，终止条件为聚类簇的数量为 $ MathJax-Element-554 $ 。迭代过程为：
    计算聚类簇之间的距离，找出距离最近的两个簇，将这两个簇合并。
    每进行一次迭代，聚类簇的数量就减少一些。
AGNES 算法的优点：
- 距离容易定义，使用限制较少。
- 可以发现聚类的层次关系。
AGNES 算法的缺点：
- 计算复杂度较高。
- 算法容易聚成链状。

4.2 BIRCH 算法

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

4.2.1 聚类特征

聚类特征CF：每个CF 都是刻画一个簇的特征的三元组： $ MathJax-Element-475 $ 。其中：
- $ MathJax-Element-476 $ ：表示簇内样本数量的数量。
- $ MathJax-Element-477 $ ：表示簇内样本的线性求和： $ MathJax-Element-478 $ ，其中 $ MathJax-Element-482 $ 为该CF 对应的簇。
- $ MathJax-Element-480 $ ：表示簇内样本的长度的平方和。 $ MathJax-Element-481 $ ，其中 $ MathJax-Element-482 $ 为该CF 对应的簇。
根据CF 的定义可知：如果CF1 和 CF2 分别表示两个不相交的簇的特征，如果将这两个簇合并成一个大簇，则大簇的特征为： $ MathJax-Element-483 $ 。
即：CF 满足可加性。
给定聚类特征CF，则可以统计出簇的一些统计量：
- 簇心： $ MathJax-Element-484 $ 。
- 簇内数据点到簇心的平均距离（也称作簇的半径）： $ MathJax-Element-485 $ 。
- 簇内两两数据点之间的平均距离（也称作簇的直径）： $ MathJax-Element-486 $ 。
给定两个不相交的簇，其特征分别为 $ MathJax-Element-487 $ 和 $ MathJax-Element-488 $ 。
假设合并之后的簇为 $ MathJax-Element-489 $ ，其中 $ MathJax-Element-490 $ ， $ MathJax-Element-491 $ ， $ MathJax-Element-492 $ 。
可以通过下列的距离来度量 CF1 和 CF2 的相异性：
- 簇心欧氏距离centroid Euclidian distance： $ MathJax-Element-493 $ ，其中 $ MathJax-Element-494 $ 分别为各自的簇心。
- 簇心曼哈顿距离centroid Manhattan distance： $ MathJax-Element-495 $ 。
- 簇连通平均距离average inter-cluster distance：
  $ d_2=\sqrt{\frac{\sum_{\mathbf{\vec x}_i \in \mathbb S_1}\sum_{\mathbf{\vec x}_j \in \mathbb S_2}||\mathbf{\vec x}_i -\mathbf{\vec x}_j||_2^2}{\text{num}_1\times \text{num}_2}} = \sqrt{\frac{\Sigma_{s,1}}{\text{num}_1}+\frac{\Sigma_{s,2}}{\text{num}_2}-2 \frac{\vec\Sigma_{l,1}^T\vec\Sigma_{l,2}}{\text{num}_1\times\text{num}_2 }} $
- 全连通平均距离average intra-cluster distance：
  $ d_3=\sqrt{\frac{\sum_{\mathbf{\vec x}_i \in \mathbb S_3}\sum_{\mathbf{\vec x}_j \in \mathbb S_3}||\mathbf{\vec x}_i -\mathbf{\vec x}_j||_2^2}{(\text{num}_1+\text{num}_2)\times (\text{num}_1+\text{num}_2-1)}} \\ = \sqrt{\frac{2(\text{num}_1+\text{num}_2)(\Sigma_{s,1}+\Sigma_{s,2})-2||\vec\Sigma_{l,1}-\vec\Sigma_{l,2}||_2^2}{(\text{num}_1+\text{num}_2)\times (\text{num}_1+\text{num}_2-1)}} $
- 方差恶化距离variance incress distance： $ MathJax-Element-496 $ 。

4.2.2 CF 树

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

4.2.3 BIRCH 算法

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