用于寻找聚类层次结构的遗传算法

### 用于寻找聚类层次结构的遗传算法 #### 1. 相关工作 如今，尽管有大量的聚类方法可供使用，但几乎所有方法都至少存在以下缺点之一：局限于划分聚类；对异常值敏感；需要用户定义参数（如聚类数量）。接下来将对层次聚类、基于模型的聚类、信息论聚类和遗传聚类算法进行概述。 ##### 1.1 层次聚类 - **单链接法（Single Link）**：这是一种广泛应用的层次聚类方法，会生成一种图形输出，即树状图。通过在树状图的不同层次进行切割，可以得到划分聚类结果。然而，对于复杂数据集，很难定义合适的分割层次以得到有意义的聚类。此外，异常值可能导致著名的单链接效应，且对于大型数据集，精细尺度的可视化并不合适。 - **OPTICS算法**：该算法通过要求聚类具有最小对象密度（即MinPts数量的对象位于半径为ϵ的超球体内）来避免单链接效应。它还提供了一种更合适的可视化方式，即可达性图。但参数的正确选择并不直观，且对算法性能和结果准确性有显著影响，同时只有某些切割代表有用聚类的问题仍未解决。 ##### 1.2 基于模型的聚类 基于模型的聚类假设数据由有限的潜在概率分布（如多元正态分布）混合生成。常用的算法是期望最大化（EM）算法。在适当初始化后，EM算法迭代优化k个高斯分布的混合模型，直到数据的对数似然不再有显著改善。EM算法存在两个常见问题：一是可能陷入局部最优；二是结果质量强烈依赖于k的合适选择。除了经典的EM算法，文献中还有多种层次扩展方法，但这些方法都需要为层次级别数量设置合适的参数。 ##### 1.3 信息论聚类 信息论聚类通常可以避免困难的参数设置。X - Means、G - Means和RIC算法试图通过平衡数据似然和模型复杂度来找到划分聚类中的最优k值，这种敏感的权衡通过模型选择标准（如最小描述长度MDL）来评估。RIC算法使用MDL来定义异常值的编码方案并识别非高斯聚类，但这些方法只是划分方法，并非层次方法。文献中还提出了一种类似EM的信息论层次聚类算法ITCH，初始化后，ITCH以贪心搜索的方式重新排列层次结构，通常只能收敛到局部最优。 ##### 1.4 遗传聚类算法 文献中介绍了多种遗传聚类算法，如遗传k - 均值算法、遗传c - 均值聚类算法的变体以及半监督遗传聚类算法等。Pernkopf和Bouchaffra提出的方法将遗传算法的优点与基于模型的聚类相结合，通过MDL准则自动确定正确的聚类数量。但这些方法要么仅适用于划分聚类，要么需要人工输入合适的k值，且都不支持噪声和异常值的检测。 #### 2. GACH - 用于寻找聚类层次结构的遗传算法 GACH算法结合了遗传算法的基本组件，并进行了必要的修改以用于聚类层次结构。 ##### 2.1 聚类层次结构的染色体表示 对于GACH算法，染色体是对层次聚类结构（HCS）的编码，需要满足以下三个特征： - 存储k个聚类，k为任意聚类数量。 - 表示聚类之间的层次关系，形成聚类树T。 - 对聚类代表进行编码，即底层概率密度函数（PDF）的参数。 在GACH中，每个聚类用高斯PDF表示，模型也可扩展到其他类型的PDF。染色体HCS的定义如下： - 染色体HCS（HCSChrom）是一个动态列表，存储k个聚类对象。 - 每个聚类C持有其父聚类和子聚类的引用，聚类C的级别lC表示其后代子树的高度，根节点级别最高，叶子节点级别为0。 - 聚类C的底层高斯PDF的参数（均值μC和标准差σC）被建模为聚类对象C的附加参数。 - 每个聚类C关联一个权重WC，且所有聚类的权重之和为1。 聚类C的底层PDF是d维数据空间中的多元高斯分布，由以下公式定义： \[N(\mu_C, \sigma_C, x) = \prod_{1\leq i\leq d}\frac{1}{\sqrt{2\pi\sigma_{C,i}^2}}\cdot e^{-\frac{(x_i - \mu_{C,i})^2}{2\sigma_{C,i}^2}}\] GACH将数据集D中的每个点x直接分配给HCSChrom中在x位置概率密度最大的聚类C： \[C(x) = \arg\max_{C\in HCSChrom}\{W_C\cdot N(\mu_C, \sigma_C, x)\}\] ##### 2.2 GACH的初始化 GACH的初始种