模式识别中的相异度表示与学习方法

# 模式识别中的相异度表示与学习方法 ## 1. 决策树与相异度表示 在模式识别中，决策树是一种常用的分类工具。不同层次的决策树会使用原始向量空间的不同子集。每个样本根据其到达的叶子节点的标签进行分类，通常考虑的是二叉决策树。最大熵准则和基尼指数是最常用的分裂规则，它们在每个节点确定一个特征和一个阈值，用于进行划分。 当基于相异度表示进行操作时，特征选择等同于对象选择。分裂过程通过检查所研究的样本是否位于所选对象的邻域（由所考虑的相异度度量中的阈值确定）内来进行。 ## 2. 伪欧几里得空间中的分类 ### 2.1 相异度矩阵与向量配置 假设集合 $R$ 和 $T$ 相同，对称相异度矩阵 $D(R, R)$ 可以解释为底层向量配置 $X$ 的描述，该向量配置由 $D$ 的线性嵌入确定。此过程依赖于从 $D^2$ 通过特定公式推导得到的格拉姆矩阵 $K = G$ 的嵌入，$K$ 是欧几里得或伪欧几里得空间中的埃尔米特（对称）核。因此，也可以直接从 $K$ 给出的相似性表示开始。 如果 $D(R, R)$ 是非对称的，则可以构造两个对称相异度表示 $D_1 = \frac{1}{2}(D + D^T)$ 和 $D_2 = \frac{1}{2}(D - D^T)$，从而得到两个伪欧几里得配置 $X_1$ 和 $X_2$，然后构建两个分类器并在后续进行组合。为了简化，我们主要关注对称表示。如果 $R \subset T$，则推理依赖于 $D(R, R)$ 的嵌入，并将 $T \setminus R$ 中的其余对象投影到嵌入空间中。为了简单起见，假设 $R = T$。 ### 2.2 不同空间中的分类器选择 如果 $X$ 位于欧几里得空间中，则可以使用任何传统分类器。如果 $X$ 位于伪欧几里得空间中，则可以使用相关的欧几里得空间来构建分类器，或者对传统分类器进行适当调整。这里主要考虑简单的线性和二次决策规则，因为它们自然依赖于伪欧几里得内积。 设 $E = \mathbb{R}^m = \mathbb{R}^{(p,q)}$，$m = p + q$ 是具有签名 $(p, q)$ 和基本对称性 $J_{pq}$ 的伪欧几里得空间。$E$ 中的线性函数定义为 $f(x) = v^T J_{pq} x + w_0$，可以解释为 $f(x) = w^T x + w_0$，其中 $w = v J_{pq}$ 在相关的欧几里得空间 $\vert E \vert = \mathbb{R}^{p + q}$ 中。为了满足向量 $x$ 到超平面的有符号距离能指示 $x$ 位于超平面哪一侧的条件，需要满足 $\vert\vert v \vert\vert_E^2 > 0$，否则会出现歧义。 在实践中，由于从正相异度开始，数据嵌入后使得 $\mathbb{R}^q$ 空间的“负”贡献小于 $\mathbb{R}^p$ 空间的“正”贡献，因此 $v$ 的不定范数为正，并且对于从 $D$ 嵌入得到的任何 $x \in \mathbb{R}^{(p,q)}$，有 $\vert\vert x \vert\vert_E^2 > 0$。但如果从任意不定核开始，这一条件不再保证。 ### 2.3 最近均值分类器（NMC）和广义最近均值分类器（GNMC） - **最近均值分类器（NMC）**：是最简单的线性分类器，它将未知对象分配到其最近均值所在的类。在通过 $D$ 的线性嵌入获得的伪欧几里得空间 $I$ 中，这种决策基于伪欧几里得距离。对于 $K$ 类问题，定义 $f_j(x) = \vert d_E^2(x, X^{(j)}) \vert$，$j = 1, \cdots, K$，其中 $X^{(j)}$ 是第 $j$ 类的均值向量。使用伪欧几里得距离平方的绝对值是因为在某些情况下，$d_E^2(x, X^{(j)})$ 可能为负。NMC 规则将新对象 $x$ 分类为：如果 $f_j(x) = \min_{i = 1, 2, \cdots, K} \{ f_i(x) \}$，则将 $x$ 分配到 $\omega_j$ 类。 - **广义最近均值分类器（GNMC）**：由于 NMC 的决策仅依赖于到类均值向量的伪欧几里得距离，因此可以以一种修改的方式进行分类，而无需进行 $D$ 的精确嵌入。假设类 $\omega_i$ 由基于集合 $R^i$ 的相异度矩阵 $D(R^i, R^i)$ 表示，新对象 $z$ 由与集合 $R^i$ 的相异度表示。则 $x$ 到类 $\omega_i$ 的接近度由函数 $f_i$ 衡量，该函数可以等效地表示为 $f_i(x) = \vert\vert x^i - X^i \vert\vert_{E_i}^2$，其中 $x^i$ 是对象 $z$ 的向量表示，$X^i$ 是整个表示 $R^i$ 在 $E_i$ 中的均值向量。K 类 GNMC 定义为：如果 $j = \arg \min_{i = 1, \cdots, K} \{ f_i(z) \}$，则将 $z$ 分配到 $\omega_j$ 类。 NMC 和 GNMC 在伪欧几里得空间中通常不是相同的分类器。NMC 在由完整矩阵 $D$ 的线性嵌入得到的伪欧几里得空间 $E$ 中训练，其维度由类内和类间相异度共同决定。GNMC 仅对类内相异度进行操作，它在为每个类单独定义的底层特征空间 $