构建分类树：原理、算法与优化

# 构建分类树：原理、算法与优化 ## 1. 引言 在数据处理和分析中，对有限集合进行聚类并构建分类树是一项重要任务。基本数据由一个有限集合 $E$ 构成，该集合配备了相异度或相似度函数。集合 $E$ 中的元素性质相同，它可以是属性集、对象集或类别集。 集合 $E$ 可能会被一个正数值测度 $\mu_E$ 加权，为每个元素 $x$（$x \in E$）赋予权重 $\mu_x$，这个权重定义了元素 $x$ 的“重要性”。集合 $E$ 上的相异度或相似度函数大多是数值型的，但也可能是顺序型的。 分类树是通过对集合 $E$ 进行有序划分链 $\Pi = (P_0, P_1, \ldots, P_{l - 1}, P_l, \ldots, P_m)$ 来定义的。其中，划分 $P_l$ 是由 $P_{l - 1}$ 合并其类得到的。$P_0$ 是最细划分，每个类都是单元素类；$P_m$ 是“粗”划分，只包含一个对应整个集合 $E$ 的类。 例如，给定集合 $E$，其划分序列可能如下： $P_0 = \{\{e_1\}, \{e_2\}, \{e_3\}, \{e_4\}, \{e_5\}, \{e_6\}\}$ $P_1 = \{\{e_1, e_3\}, \{e_2\}, \{e_4\}, \{e_5\}, \{e_6\}\}$ $P_2 = \{\{e_1, e_3, e_6\}, \{e_2, e_4, e_5\}\}$ $P_3 = \{\{e_1, e_2, e_3, e_4, e_5, e_6\}\}$ 构建分类树的目标是尽可能尊重集合 $E$ 中元素之间的相似度。也就是说，从全局和统计角度来看，两个元素 $x$ 和 $y$ 的连接级别应与它们的相似度 $S(x, y)$（或相异度 $D(x, y)$）成反比。 ### 1.1 相似度函数类型 相似度函数可能是顺序型的。在这种情况下，数据由与集合 $E$ 上的相似度指数 $S$ 相关联的预序 $\omega_S$ 定义。预序 $\omega_S$ 是根据以下规则建立的： $\forall (p, q) \in P_2(E) \times P_2(E)$，$p \leq q \Leftrightarrow S(p) \geq S(q)$ 其中，$P_2(E)$ 表示集合 $E$ 的无序元素对集合，$S(p)$ 是元素对 $p = \{x, y\}$ 的相似度值。 ### 1.2 相关算法 - **字典序算法**：可以直接从顺序数据 $\omega_S$ 构建分类树，而无需参考导出 $\omega_S$ 的相似度指数 $S$。该算法具有相对于字典序准则的最优性，因此被称为“字典序算法”。 - **最大下限算法**：由 M. Roux 定义，具有度量性质，与字典序算法构思不同，但在实际结果上与著名的“单链接”算法等价。“单链接”算法可以在集合 $E$ 的子集层面表达，它基于将元素间的相似度指数 $S$ 扩展到不相交子集间的相似度指数 $\sigma$。 ### 1.3 合并准则 对于所有聚合层次聚类方法，不相交子集 $C$ 和 $D$ 之间的相异度 $\delta(C, D)$ 可以形式化地表示为： $\forall (C, D) \in P(E) \times P(E), C \cap D = \varnothing$，$\delta(C, D) = f(\{D(x, y)|(x, y) \in (C \cup D) \times (C \cup D)\}, \mu_{C \cup D})$ 其中，$P(E)$ 是 $E$ 的子集集合，函数 $f$ 要在加权元素的相互相异度集合上定义，$\mu_{C \cup D}$ 是 $\mu_E$ 在 $C \cup D$ 上的限制。 常见的合并准则包括： |准则名称|定义| | ---- | ---- | |单链接（$\delta_{min}$）|$\delta_{min}(C, D) = \min\{D(x, y)|(x, y) \in C \times D\}$| |完全链接（$\delta_{max}$）|使用最大值函数| |平均链接（$\delta_{ave}$）|使用平均值函数| |沃德惯性变化（$\delta_{iner}$）|在欧几里得空间中基于惯性变化定义| ### 1.4 信息相异度矩阵 通过 LLA 方法可以得到一个判别概率指数矩阵 $P_g$： $P_g = \{P_g(x, y)|\{x, y\} \in P_2(E)\}$ 与之关联的是“信息相异度矩阵”$D$： $D = \{D_{inf}(x, y) = -\log_2(P_g(x, y))|\{x, y\} \in P_2(E)\}$ ### 1.5 其他聚类方法 除了上