基于层次的聚类算法：AGNES, DIANA

基于层次的办法

层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。

• 凝聚的层次聚类：

  • 一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足，
  • 代表是AGNES算法

  

  最小距离法（Single Linkage）

  • 定义：在两个簇之间的所有可能配对样本点中，选择距离最小的一对样本点的距离作为簇间距离。

  • 特点

    ：

    • 链状效应：由于只考虑最接近的一对点，最小距离法容易形成链状结构，即若干个样本逐个连接在一起，形成较长的“链”。
    • 噪声敏感：对噪声和离群点（outliers）较为敏感，因为离群点可能会导致簇之间的最小距离变小，从而错误地合并簇。
    • 效率较高：计算简单，效率较高，但结果可能不稳定。

  • 适用场景：适用于数据集中的簇呈现不规则形状或链状结构的情况。

  最大距离法（Complete Linkage）

  • 定义：在两个簇之间的所有可能配对样本点中，选择距离最大的一对样本点的距离作为簇间距离。

  • 特点

    ：

    • 紧密簇：最大距离法倾向于形成紧密、球形的簇，因为它考虑了簇中最远样本点之间的距离，从而避免形成链状结构。
    • 抗噪声能力强：对噪声和离群点较为鲁棒，不容易被离群点影响，因为离群点的存在不会显著改变簇的最大距离。
    • 计算复杂度高：由于需要计算所有样本点的最大距离，计算复杂度相对较高。

  • 适用场景：适用于数据集中簇的形状较为规则、且希望得到更紧密的簇的情况。

• 分裂的层次聚类：

  • 采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。

  • 代表是DIANA算法;

  算法    DIANA（自顶向下分裂算法）
  输入：包含n个对象的数据库，终止条件簇的数目k。
  输出：k个簇，达到终止条件规定簇数目。
  （1）将所有对象整个当成一个初始簇；
  （2） FOR （i=1; i≠k; i++) DO BEGIN
  （3）       在所有簇中挑出具有最大直径的簇C；
  （4）      找出C中与其它点平均相异度最大的一个点p并把p放入splinter group，剩余的放在old party中；
  （5）.      REPEAT
  （6）             在old party里找出到最近的splinter group中的点的距离不大于到old party中最近点的距离的点，并将该点加入splinter group。
  （7）       UNTIL 没有新的old party的点被分配给splinter group；
  （8）   splinter group和old party为被选中的簇分裂成的两个簇，与其它簇一起组成新的簇集合。
  （9） END.