Rank-Transformed Dissimilarity Profiles for High-Dimensional Classification¶

会议: NeurIPS 2026
arXiv: 2306.15199
论文: https://arxiv.org/abs/2306.15199
领域: 学习理论
关键词: 高维小样本分类, 相异度画像, 秩变换, 二次判别分析, 维度灾难

一句话总结¶

针对高维小样本（HDLSS）下均值与方差信号混杂的分类难题，本文提出将高维样本间的成对相异度转化为类别级秩次画像，直接将特征维度压缩至类别数，并利用画像空间的渐近高斯性质实现自适应且对异常值鲁棒的判别分类。

研究背景与动机¶

高维小样本（High-Dimensional Low-Sample-Size, HDLSS）分类广泛存在于肿瘤基因表达谱分析、高维文本情感识别以及多通道语音信号处理等实际任务中。在这些场景中，特征维度 \(d\) 往往远大于有标签样本容量 \(N\)，且不同任务中区分不同类别的真实统计信号形态各异。现有分类器大多建立在经典低维几何直觉之上，即预设同类样本之间的距离倾向于小于异类样本之间的距离。无论是基于边界的支持向量机（SVM）、基于正则化的线性判别分析（GLDA）、集成树模型（Random Forest, LightGBM），还是多层感知机（MLP），在处理特征极其稀疏或高度相关的超高维数据时，都高度依赖这一邻近性假设。

然而在超高维几何空间中，“维度灾难”使得传统距离邻近假设极易失效。当两个类别的真实分布不仅存在均值漂移（Location Difference），还伴随尺度/协方差差异（Scale/Variance Difference）时，高维空间的离散度会导致反常的几何排序：更分散的类别内部样本距离 \(D_{YY}\) 不仅大于较紧凑类别的内部距离 \(D_{XX}\)，甚至会系统性大于类间交叉距离 \(D_{XY}\)（即呈现 \(D_{XX} < D_{XY} < D_{YY}\)）。在此类场景下，依赖“同类更近”的常规分类器（如 GLDA 和 SVM）性能急剧恶化，错误率往往退化至随机猜测（接近 0.50）；而专门针对尺度差异设计的距离分类器（如 gMADD）在纯均值差异任务中又表现乏力。领域内缺乏一种无需预验假设、能够同时自适应捕获位置漂移、尺度缩放及高阶矩差异的通用表征。

本文的切入角度是“反客为主”——既然维度灾难必然引发系统性的类内与类间距离排序形变，那么这种相对几何模式本身就是最具辨别力的高阶信号。核心 idea：将每个高维样本与所有训练样本的成对相异度映射为列向秩次，聚合为仅有类别数维度的类间相异度秩画像（Rank-Transformed Dissimilarity Profiles），在大幅压降维度的同时兼顾对异常值的强鲁棒性，并在画像空间中借助渐近正态性通过二次判别分析（QDA）自适应识别多重分布差异。

方法详解¶

整体框架¶

本文提出的方法由相异度计算、列向秩变换、类别级均值画像聚合以及低维画像空间判别分类四个阶段组成。对于包含 \(N\) 个有标签样本、类别数为 \(k\) 的训练集，方法首先构建样本间的成对平方欧氏距离（或非欧测度）矩阵；随后在每个参考样本的列视角下将距离转换为排序秩次；紧接着，将样本对各类别成员的秩次分别求均值，将原 \(d\) 维高维特征无损收敛为仅 \(k\) 维的类级秩画像矩阵 \(M^{(R)} \in \mathbb{R}^{N \times k}\)；最后，对任意测试样本计算其相对于训练集的投影画像，并在 \(k\) 维空间中运用二次判别分析（QDA）完成最终归类。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：高维小样本数据<br/>Z ∈ R^(N×d) 与类别标签 g"] --> B["成对相异度与列向秩变换<br/>计算 D[i,j] 并求列向秩矩阵 R"]
    B --> C["类内与类间画像压缩<br/>类别均值聚合生成 k 维画像 M^(R)"]
    D["新测试样本 W<br/>计算至各训练点距离"] --> E["测试样本快速秩投影<br/>将 W 插入各列计算 R_W 与 M_W^(R)"]
    C --> F["渐近高斯二次判别 QDA<br/>基于类均值 μ_j 与协方差 Σ_j 分类决策"]
    E --> F
    F --> G["输出：预测类别 g(W)"]

关键设计¶

1. 成对相异度与列向秩变换：消除尺度极值并抵抗重尾扰动

在高维小样本场景下，直接使用原始相异度（如平方欧氏距离）极易受到数据分布重尾性或单侧离群样本的剧烈干扰，导致距离矩阵被极端大值主导。针对这一痛点，算法在构建训练样本成对相异度矩阵 \(D \in \mathbb{R}^{N \times N}\)（其中 \(D[i,j] = \|Z_i - Z_j\|_2^2\)）后，并不直接基于数值聚合，而是在每个参考样本 \(Z_j\) 的列视角下进行升序排序，将数值矩阵映射为秩矩阵 \(R \in \mathbb{R}^{N \times N}\)，其中 \(R[i,j]\) 即为 \(D[i,j]\) 在第 \(j\) 列所有元素中的相对排序秩次。

通过将相异度数值单调映射为 \([1, N]\) 内的均匀相对位次，算法剥离了不同特征坐标的绝对量纲差异，极大压制了重尾噪声与异常值对几何分布的畸变。更重要的是，高维空间中由于均值位移或方差不对称所引发的“同类或异类样本在几何球面上系统性偏近或偏远”的本质信息，被完好地保留在秩次矩阵的相对排序结构之中。

2. 类内与类间画像压缩：将 \(d\) 维高维特征聚合为 \(k\) 维低维剖面

当特征维度 \(d \gg N\) 时，任何直接估计全协方差矩阵的参数模型都会面临维数灾难与过拟合。本文的设计是利用类别先验，将每个样本相对于全体训练集的繁杂秩次关系，按类别划分为 \(k\) 个紧凑的类级统计量。具体而言，对于第 \(i\) 个训练样本，其在第 \(j\) 个类别上的平均秩次定义为：

\[M^{(R)}[i,j] = \frac{1}{n_j - \mathbb{I}\{g_i = j\}} \sum_{l: g_l = j, l \neq i} R[i,l]\]

该操作排除了样本与自身的比较项，将每个样本压缩为一个 \(k\) 维向量 \(M^{(R)}[i, \cdot] = (M^{(R)}[i,1], \dots, M^{(R)}[i,k])^\top\)。在两分类问题中，这等价于将 1000 维的复杂数据点直接投影到仅有 2 维的平面上：横坐标表示该样本相对于类别 1 成员的平均相对距离秩次，纵坐标表示其相对于类别 2 成员的平均相对距离秩次。高维几何中的位置差异使得两类在交叉轴上拉开，而尺度差异则使两类在对角轴呈现非对称偏移，从而在极低维空间中构造出天然线性或二次可分的紧凑聚类结构。

3. 测试样本快速秩投影与自适应二次判别分析（QDA）：理论保证下的最优边界划分

在推理阶段，新样本 \(W \in \mathbb{R}^d\) 无法直接重排整个训练集矩阵而不破坏已有结构。本文采用快速插入排序法构建新样本的秩剖面：对于每个参考训练样本 \(Z_i\)，统计训练集中比 \(W\) 距离 \(Z_i\) 更近的样本数，并赋予平局校正：

\[R_W[i] = \frac{1}{2} + \sum_{t=1}^N \mathbb{I}\{\|Z_t - Z_i\|_2^2 < \|W - Z_i\|_2^2\} + \frac{1}{2} \sum_{t=1}^N \mathbb{I}\{\|Z_t - Z_i\|_2^2 = \|W - Z_i\|_2^2\}\]

随后在各类内部计算平均秩次，获得新样本在画像空间的坐标 \(M_W^{(R)} \in \mathbb{R}^k\)。在分类决策器的选取上，论文证明了在带状依赖与有界条件下，相异度画像在大维度极限下渐近服从多元正态分布（定理 4.2）。因此，在 \(k\) 维剖面空间中无需求助复杂的黑盒模型，直接应用参数极少且闭式可解的二次判别分析（QDA）：

\[g(W) = \arg\max_j \left\{ -\frac{1}{2} \log |\hat{\Sigma}_j^{(R)}| - \frac{1}{2} (M_W^{(R)} - \hat{\mu}_j^{(R)})^\top (\hat{\Sigma}_j^{(R)})^{-1} (M_W^{(R)} - \hat{\mu}_j^{(R)}) + \log \frac{n_j}{N} \right\}\]

由于 QDA 允许不同类别拥有独立的类协方差矩阵 \(\hat{\Sigma}_j^{(R)}\)，它能够完美适应由于类别方差不同在画像空间中诱导出的非均匀椭圆分布形状，实现了自适应的贝叶斯最优判别边界划分。

一个完整示例¶

考虑一个两类分类任务（\(k=2\)），两类各包含 \(n_1=n_2=50\) 个样本，总计 \(N=100\)，特征维度 \(d=1000\)。类别 1 服从标准分布，类别 2 尺度放大了 \(1.1\) 倍且存在微小均值位移。 1. 训练画像构建：计算 \(100 \times 100\) 的平方距离矩阵 \(D\)。对第 \(j\) 列进行排序，得到每一列中的秩次 \(R[i,j] \in [1, 100]\)。对类别 1 的样本 \(X_i\)，其与类别 1 其余 49 个样本的平均距离较小，在各列中的平均秩次约为 \(M^{(R)}[i, 1] \approx 35.2\)，而与类别 2 的 50 个样本平均秩次约为 \(M^{(R)}[i, 2] \approx 58.4\)；对于类别 2 的样本 \(Y_j\)，由于尺度更大，根据高维反常几何，其画像坐标则聚集在 \((M^{(R)}[j, 1], M^{(R)}[j, 2]) \approx (42.1, 65.8)\) 区域。 2. 测试样本分类：到来一个属于类别 1 的未知样本 \(W\)。针对训练集每个 \(Z_i\) 计算 \(\|W - Z_i\|_2^2\) 并与训练集自身距离比对，得到 \(W\) 的 100 维秩向量 \(R_W\)。在类别 1 与类别 2 上分别求均值，得到测试画像 \(M_W^{(R)} = (36.0, 57.5)^\top\)。 3. QDA 决策：将该二维向量代入类别 1 与类别 2 预先拟合的高斯判别函数中，类别 1 的二次得分显著高于类别 2，样本被正确判定为类别 1。

实验关键数据¶

主实验¶

论文在 \(d=1000\) 的两类高维小样本合成数据集（每类训练与测试各 50 个样本）上对比了所提方法与 8 种主流基线。生成模型为 \(X_i = \mathbf{A} x_i, Y_j = a \mathbf{A} y_j + \mu\)。涵盖标准高斯（S1）、重尾 \(t_5\) 分布（S2）、偏态卡方 \(\chi_5^2-5\) 分布（S3）以及混合分布（S4）。

实验场景	信号参数 \((\mu_0, a)\)	本文方法	GLDA	SVM	RF	glmnet	LightGBM	MLP	gMADD	RP-Ensemble
S1 (高斯)	\(\mu_0=6, a=1.0\) (纯均值)	0.025	0.025	0.019	0.106	0.200	0.336	0.149	0.293	0.179
S1 (高斯)	\(\mu_0=0, a=1.1\) (纯尺度)	0.019	0.493	0.127	0.416	0.497	0.505	0.494	0.051	0.507
S1 (高斯)	\(\mu_0=6, a=1.1\) (均值+尺度)	0.002	0.041	0.003	0.105	0.216	0.338	0.198	0.032	0.200
S2 (\(t_5\))	\(\mu_0=6, a=1.0\) (纯均值)	0.102	0.096	0.091	0.163	0.296	0.340	0.208	0.351	0.266
S2 (\(t_5\))	\(\mu_0=0, a=1.1\) (纯尺度)	0.119	0.489	0.201	0.433	0.497	0.494	0.494	0.092	0.511
S2 (\(t_5\))	\(\mu_0=6, a=1.1\) (均值+尺度)	0.048	0.124	0.054	0.170	0.319	0.344	0.244	0.066	0.274
S3 (\(\chi_5^2\))	\(\mu_0=0, a=1.1\) (纯尺度)	0.083	0.501	0.176	0.378	0.502	0.491	0.502	0.106	0.506
S4 (混合)	\(\mu_0=0, a=1.0\) (高阶矩差)	0.000	0.485	0.000	0.405	0.495	0.500	0.473	0.007	0.489

此外，在四分类任务（S5-S7，\(d=1000\)）与真实基因表达谱数据集上的错误率如下： - 四分类高斯 S5：本文 0.025，SVM 0.138，gMADD 0.047，GLDA 0.508，LightGBM 0.756。 - 四分类偏态 S7：本文 0.217，SVM 0.294，gMADD 0.487，GLDA 0.571，LightGBM 0.755。 - 真实数据 Shipp (淋巴瘤)：本文 0.178，GLDA 0.174，MLP 0.172，SVM 0.250，gMADD 0.316。 - 真实数据 Nutt (脑胶质瘤)：本文 0.160，RP-Ensemble 0.193，GLDA 0.201，SVM 0.470，gMADD 0.366。

消融实验¶

为验证秩变换机制相比于原始距离度量对离群污染的抗干扰能力，论文在附录 D 中设计了异常点污染消融实验（在 50 个样本中注入 \(n_o\) 个重度污染样本，对比算法 1 与无秩变换的原始相异度算法 C.1）：

污染场景	异常样本数 \(n_o\)	本文算法 1 (带秩变换)	算法 C.1 (原始距离画像)	性能差距 (错误率恶化幅度)
S12 (纯尺度, \(a=1.1\))	\(n_o = 0\) (无污染)	0.019	0.020	相差无几 (+0.001)
S12 (纯尺度, \(a=1.1\))	\(n_o = 3\)	0.035	0.325	算法 C.1 激增 +0.290
S12 (纯尺度, \(a=1.1\))	\(n_o = 5\)	0.043	0.335	算法 C.1 激增 +0.292
S12 (纯尺度, \(a=1.1\))	\(n_o = 7\)	0.040	0.338	算法 C.1 激增 +0.298
S13 (纯均值, \(\mu_0=6\))	\(n_o = 3\)	0.044	0.141	算法 C.1 激增 +0.097
S13 (纯均值, \(\mu_0=6\))	\(n_o = 7\)	0.071	0.229	算法 C.1 激增 +0.158
S14 (混合差异)	\(n_o = 3\)	0.026	0.151	算法 C.1 激增 +0.125
S14 (混合差异)	\(n_o = 7\)	0.066	0.227	算法 C.1 激增 +0.161

关键发现¶

自适应捕获混合信号：在纯均值差异下，GLDA 和 SVM 表现优异但 gMADD 较差；在纯尺度差异下，GLDA 和树模型几乎完全退化至随机猜测（~0.50），仅 gMADD 保持有效。唯有本文方法在所有组合下均达到或逼近最优，证明类级画像空间同时承载了均值位移与尺度拉伸的判别几何信息。
秩变换是稳健性的绝对屏障：消融实验清楚表明，在干净数据下，直接用平方距离画像（算法 C.1）与秩画像性能几乎一致（0.019 vs 0.020）；但一旦存在少至 3 个离群样本，原始距离画像的错误率便直接跳水至 0.325，而秩变换算法仅微降至 0.035，展现了近乎免疫极端值的稳健特性。
拓展非欧几何与图分类的能力：在网络分类任务（S8-S9）中，仅需将欧氏距离替换为图邻接矩阵的汉明距离（Hamming Distance），本文方法便取得全场最低错误率（S9 中达到 0.080，远优于 SVM 的 0.129 与 gMADD 的 0.098），展现了通用的非度量空间适应性。

亮点与洞察¶

将“维度灾难”逆向转化为分类特征：经典机器学习竭力避免高维空间中的距离集中和排序形变，而本文独辟蹊径，证明高维下不同方差所导致的 \(D_{XX} < D_{XY} < D_{YY}\) 是强有力的辨识特征，利用类级画像直接将劣势转化为信号。
极简的超参数空间与惊人的降维幅度：将 \(d \gg 1000\) 的空间直接压缩到仅 \(k\) 维（通常为 2 至 4 维），使得后续判别无需复杂的深度网络或正则化微调，一个轻量级的经典 QDA 即可获得极高精度，大幅降低了过拟合风险。
完备的理论正态逼近解释：通过构建距离替代算法（Surrogate），严格推导出距离画像的期望与协方差矩阵，证明其不仅编码一阶均值、二阶方差，还融入了偏度与峰度等高阶矩信息，并在弱依赖条件下给出了中心极限定理（CLT）级别的正态收敛证明。

局限与展望¶

类别规模 \(k\) 极大时的扩展性瓶颈：方法将维度压缩至 \(k\) 维，并依赖每个类别的经验样本均值与协方差矩阵估计。若在超多分类任务中（例如 \(k=1000\) 的长尾分类），画像空间本身会再次变成高维问题，且每个类样本若不足以支撑 \(k \times k\) 协方差矩阵估计，QDA 将面临退化风险。
距离计算的平方级复杂度：成对相异度矩阵的构建时间复杂度为 \(O(N^2 d)\)，当样本量 \(N\) 扩展至百万级时，开销将显著上升；未来可探索基于近似最近邻（ANN）或随机子采样的快速画像逼近。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 逆向利用维度灾难中的距离反常排序，设计类级秩画像，视角非常深刻独特。
实验充分度: ⭐⭐⭐⭐⭐ 覆盖两类、多类、复杂重尾与偏态分布、网络图结构数据、真实基因表达谱以及严格的抗污染消融分析。
写作质量: ⭐⭐⭐⭐⭐ 逻辑层层推进，理论替代分析（Surrogate）不仅推导了高阶矩表达式，还建立了渐近正态收敛，自洽性极强。
价值: ⭐⭐⭐⭐⭐ 为生命科学与生物信息学等典型 HDLSS 领域的通用高维分类提供了一种即插即用、鲁棒强大的非参数基准。