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

2. AGNES首先将数据集中的每个样本看作一个初始的聚类簇，然后在算法运行的每一步中，找出距离最近的两个聚类簇进行合并。

   合并过程不断重复，直到达到预设的聚类簇的个数。

3. 这里的关键在于：如何计算聚类簇之间的距离？

   由于每个簇就是一个集合，因此只需要采用关于集合的某个距离即可。给定聚类簇 ， 有三种距离：

   • 最小距离 ： 。

     最小距离由两个簇的最近样本决定。

   • 最大距离 ： 。

     最大距离由两个簇的最远样本决定。

   • 平均距离： 。

     平均距离由两个簇的所有样本决定。

4. AGNES 算法可以采取上述任意一种距离：

   • 当AGNES算法的聚类簇距离采用 时，称作单链接single-linkage算法。
   • 当AGNES算法的聚类簇距离采用 时，称作全链接complete-linkage算法。
   • 当AGNES算法的聚类簇距离采用 时，称作均链接average-linkage算法 。

5. AGNES算法：

   • 输入：

     • 数据集
     • 聚类簇距离度量函数
     • 聚类簇数量

   • 输出：簇划分

   • 算法步骤：

     • 初始化：将每个样本都作为一个簇

       

     • 迭代，终止条件为聚类簇的数量为 。迭代过程为：

       计算聚类簇之间的距离，找出距离最近的两个簇，将这两个簇合并。

6. AGNES 算法的优点：

   • 距离容易定义，使用限制较少。
   • 可以发现聚类的层次关系。

7. AGNES 算法的缺点：

   • 计算复杂度较高。
   • 算法容易聚成链状。

4.2 BIRCH 算法

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

4.2.1 聚类特征

1. 聚类特征CF：每个CF 都是刻画一个簇的特征的三元组： 。其中：

   • ：表示簇内样本数量的数量。
   • ：表示簇内样本的线性求和： ，其中 为该CF 对应的簇。

2. 根据CF 的定义可知：如果CF1 和 CF2 分别表示两个不相交的簇的特征，如果将这两个簇合并成一个大簇，则大簇的特征为： 。

   即：CF 满足可加性。

3. 给定聚类特征CF，则可以统计出簇的一些统计量：

   • 簇心： 。
   • 簇内数据点到簇心的平均距离（也称作簇的半径）： 。
   • 簇内两两数据点之间的平均距离（也称作簇的直径）： 。

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

   可以通过下列的距离来度量 CF1 和 CF2 的相异性：

   • 簇心欧氏距离centroid Euclidian distance：，其中 分别为各自的簇心。

   • 簇心曼哈顿距离centroid Manhattan distance： 。

   • 簇连通平均距离average inter-cluster distance：

     

   • 全连通平均距离average intra-cluster distance：

   • 方差恶化距离variance incress distance： 。

4.2.2 CF 树

1. CF树的结构类似于平衡B+树 。树由三种结点构成：根结点、中间结点、叶结点。

   • 根结点、中间结点：由若干个聚类特征CF ，以及这些CF 指向子结点的指针组成。

   • 叶结点：由若干个聚类特征 组成。

     • 叶结点没有子结点，因此CF 没有指向子结点的指针。
     • 所有的叶结点通过双向链表连接起来。
     • 在BIRCH 算法结束时，叶结点的每个CF 对应的样本集就对应了一个簇。

2. CF 树有三个关键参数：

   • 枝平衡因子 ：非叶结点中，最多不能包含超过 个 CF 。
   • 叶平衡因子 ：叶结点中，最多不能包含超过 个 CF 。
   • 空间阈值 ：叶结点中，每个CF 对应的子簇的大小（通过簇半径 来描述）不能超过 。

3. 由于CF 的可加性，所以CF 树中，每个父结点的CF 等于它所有子结点的所有CF 之和。

4. CF 树的生成算法：

   • 输入：

     • 样本集
     • 枝平衡因子
     • 叶平衡因子
     • 空间阈值

   • 输出：CF 树

   • 算法步骤：

     • 初始化：CF 树的根结点为空。

     • 随机从样本集 中选出一个样本，放入一个新的CF 中，并将该CF 放入到根结点中。

     • 遍历 中的样本，并向CF 树中插入。迭代停止条件为：样本集 中所有样本都插入到CF 树中。

       迭代过程如下：

       • 随机从样本集 中选出一个样本 ，从根结点向下寻找与 距离最近的叶结点 ，和 里与 最近的 。

       • 如果 加入到 对应的簇中之后，该簇的簇半径 ，则将 加入到 对应的簇中，并更新路径上的所有CF 。本次插入结束。

       • 否则，将叶结点 分裂为两个新的叶结点 。分裂方式为：

         • 选择叶结点 中距离最远的两个CF，分别作为 中的首个CF 。
         • 将叶结点 中剩下的CF 按照距离这两个CF 的远近，分别放置到 中。
       • 依次向上检查父结点是否也需要分裂。如果需要，则按照和叶子结点分裂方式相同。

4.2.3 BIRCH 算法

1. BIRCH 算法的主要步骤是建立CF 树，除此之外还涉及到CF 树的瘦身、离群点的处理。

2. BIRCH 需要对CF 树瘦身，有两个原因：

   • 将数据点插入到CF 树的过程中，用于存储 树结点及其相关信息的内存有限，导致部分数据点生长形成的CF 树占满了内存。因此需要对CF 树瘦身，从而使得剩下的数据点也能插入到CF 树中。
   • CF 树生长完毕后，如果叶结点中的CF 对应的簇太小，则会影响后续聚类的速度和质量。

3. BIRCH 瘦身是在将 增加的过程。算法会在内存中同时存放旧树 和新树 ，初始时刻 为空。

   • 算法同时处理 和 ，将 中的 CF 迁移到 中。
   • 在完成所有的CF 迁移之后， 为空， 就是瘦身后的 CF 树。

4. BIRCH 离群点的处理：

   • 在对CF 瘦身之后，搜索所有叶结点中的所有子簇，寻找那些稀疏子簇，并将稀疏子簇放入待定区。

     稀疏子簇：簇内数据点的数量远远少于所有子簇的平均数据点的那些子簇。

   • 当 中所有数据点都被插入之后，扫描待定区中的所有数据点（这些数据点就是候选的离群点），并尝试将其插入到CF 树中。

     如果数据点无法插入到CF 树中，则可以确定为真正的离群点。

5. BIRCH 算法：

   • 输入：

     • 样本集
     • 枝平衡因子
     • 叶平衡因子
     • 空间阈值

   • 输出：CF 树

   • 算法步骤：

     • 建立 CF 树。

     • （可选）对CF 树瘦身、去除离群点，以及合并距离非常近的CF 。

     • （可选）利用其它的一些聚类算法（如：k-means）对CF树的所有叶结点中的CF 进行聚类，得到新的CF 树。

       这是为了消除由于样本读入顺序不同导致产生不合理的树结构。

     • （可选）将上一步得到的、新的CF 树的叶结点中每个簇的中心点作为簇心，对所有样本按照它距这些中心点的距离远近进行聚类。

       这是对上一步的结果进行精修。

6. BIRCH 算法优点：

   • 节省内存。所有样本都存放在磁盘上，内存中仅仅存放CF 结构。
   • 计算速度快。只需要扫描一遍就可以建立CF 树。
   • 可以识别噪声点。

7. BIRCH 算法缺点：

   • 结果依赖于数据点的插入顺序。原本属于同一个簇的两个点可能由于插入顺序相差很远，从而导致分配到不同的簇中。

     甚至同一个点在不同时刻插入，也会被分配到不同的簇中。

   • 对非球状的簇聚类效果不好。这是因为簇直径 和簇间距离的计算方法导致。

8. BIRCH 可以不用指定聚类的类别数 。

   • 如果指定 ，则需要将叶结点按照距离远近进行合并，直到叶结点中CF 数量等于 。