降维和聚类效果的评价指标一览
做降维（dimensionality reduction）或聚类（clustering）算法研究时，最烦人的事之一就是：效果好不好，要看很多个侧面，没有一个指标能包打天下。这篇把常见的评价指标整理一下，方便以后查。
一、降维评价指标
降维的目标是用低维表示 $Z \in \mathbb{R}^{n \times d}$ 来近似高维数据 $X \in \mathbb{R}^{n \times D}$（$d \ll D$）的某种结构。不同的指标侧重不同的”结构”。
1.1 邻域保持类
这类指标的核心思想：如果高维空间中两个点很近，低维中也应该很近；反之亦然。
Trustworthiness（信任度）
度量低维空间中有多少”假邻居”——那些在低维中靠得很近但在高维中并不近的点。值越高越好。
\[\text{Trustworthiness}(k) = 1 - \frac{2}{nk(2n - 3k - 1)} \sum_{i=1}^n \sum_{j \in \mathcal{N}_i^k(Z)} \max(0, r(i,j) - k)\]其中 $\mathcal{N}_i^k(Z)$ 是点 $i$ 在低维空间的 $k$ 近邻，$r(i,j)$ 是点 $j$ 在高维空间中对点 $i$ 的秩。惩罚的是那些本不是近邻却被拉进低维邻域的点。
Continuity（连续性）
Trustworthiness 的对称版本——度量高维空间中近邻的点，在低维中是否还保持为近邻。惩罚的是那些高维中本是近邻但在低维中被推开的点。
\[\text{Continuity}(k) = 1 - \frac{2}{nk(2n - 3k - 1)} \sum_{i=1}^n \sum_{j \in \mathcal{N}_i^k(X)} \max(0, \hat{r}(i,j) - k)\]Trustworthiness + Continuity 是所有降维论文的标配，几乎成了标准。一般取不同的 $k$ 画曲线看整体表现。
Mean Relative Rank Error（MRRE）
不只看 binary 的”在/不在”近邻集里，而是衡量秩的偏差程度：
\[\text{MRRE}(k) = \frac{1}{n} \sum_{i=1}^n \frac{1}{k} \sum_{j \in \mathcal{N}_i^k(X)} \frac{|r_X(i,j) - r_Z(i,j)|}{\max(r_X(i,j), r_Z(i,j))}\]这里 $r_X(i,j)$ 是 $j$ 在 $X$ 中对 $i$ 的秩，$r_Z(i,j)$ 是 $j$ 在 $Z$ 中对 $i$ 的秩。值越小越好。
Neighborhood Preservation / Neighbourhood Hit
对每个点，看它的 $k$ 近邻中有多少个在高低维中保持一致的比例：
\[\text{NH}(k) = \frac{1}{n} \sum_{i=1}^n \frac{|\mathcal{N}_i^k(X) \cap \mathcal{N}_i^k(Z)|}{k}\]AUC of ROC for Neighborhood Preservation
以 $k$ 为横轴、$\text{NH}(k)$ 为纵轴画曲线，曲线下的面积：
\[\text{AUC-NP} = \int_1^{n-1} \text{NH}(k) \, dk \approx \sum_{k=1}^{n-2} \frac{\text{NH}(k) + \text{NH}(k+1)}{2}\]具体算法： 1. 对每个 $k=1$ 到 $n-1$，计算 $\text{NH}(k)$ 2. 对相邻 $k$ 的 NH 值做梯形积分 3. 归一化到 $[0, 1]$：$\text{AUC-NP} / (n-2)$
值越接近 1 越好。优点是给出一个标量，不用看多 $k$ 曲线。
Co-ranking Matrix & LCMC（Local Continuity Meta-Criterion） ⭐
Lee & Verleysen (2009) 提出的统一框架。记录每个点对在高低维的秩，构造 co-ranking 矩阵 $Q = {q_{kl}}$，其中 $q_{kl}$ 是”高维中秩为 $k$、低维中秩为 $l$”的点对数量：
\[Q_{kl} = \#\{(i,j): r_X(i,j) = k \text{ and } r_Z(i,j) = l\}\]基于此可以定义任意 $k$ 下的LCMC——同时考虑了 Trustworthiness 和 Continuity：
\[\text{LCMC}(k) = \frac{1}{nk} \sum_{i=1}^k \sum_{j=1}^k Q_{ij} - \frac{k}{n-1}\]其中第一项是邻域命中率（hit rate），第二项减去随机期望。$\text{LCMC}(k) = \text{Trustworthiness}(k) + \text{Continuity}(k) - 1$，所以它本质上是两者的加总。
优势：用一个指标替代两个，且 $k$ 从 $1$ 到 $n-1$ 的 LCMC 曲线下的面积（AUC of LCMC）可以作为降维质量的单一标量评价。
Triplet Accuracy（三元组准确率） ⭐
考察高低维空间中的三元组关系是否一致。对任意三个点 $(i,j,k)$，如果 $d_X(i,j) < d_X(i,k)$，则希望在低维中也有 $d_Z(i,j) < d_Z(i,k)$：
\[\text{TripletAcc} = \frac{1}{\binom{n}{3}} \sum_{i,j,k: i<j\neq k} \mathbb{1}\big( (d_X(i,j) < d_X(i,k)) \iff (d_Z(i,j) < d_Z(i,k)) \big)\]取值范围 $[0.5, 1]$——随机排序的期望是 0.5。这个指标比 Trustworthiness 更全局，因为它不受限于邻域，而是考察所有的相对位置关系。
C Measure
Lebanon et al. 提出，基于所有三元组关系的一致程度：
\[C = \frac{1}{\binom{n}{3}} \sum_{i,j,k} \mathbb{1}\big((d_X(i,j)-d_X(i,k))(d_Z(i,j)-d_Z(i,k)) > 0\big)\]与 Triplet Accuracy 本质相同，但实现更直接。值越大越好。
KL Divergence / Cross-Entropy（损失函数类）
t-SNE 和 UMAP 各自优化一个特定的损失函数。这些损失本身也可以用来评价嵌入质量：
- t-SNE KL: $\text{KL}(P|Q) = \sum_{i,j} p_{ij} \log \frac{p_{ij}}{q_{ij}}$ — 惩罚高维近邻在低维中被拉远
- UMAP CE: $\text{CE}(P|Q) = \sum_{i,j} p_{ij} \log \frac{p_{ij}}{q_{ij}} + \sum_{i,j} (1-p_{ij}) \log \frac{1-p_{ij}}{1-q_{ij}}$ — 同时惩罚高维远的点在低维中被拉近
不过这些指标偏向各自的方法，跨方法比较时不够公平。
Normalized Stress / Trustworthiness 谱系一览
Lee & Verleysen (2010) 的经典综述把降维评价指标归纳为一个谱系：
全局距离保持 ←——————→ 局部邻域保持
Stress Trustworthiness
Sammon Stress Continuity
Spearman ρ LCMC
Triplet Accuracy k-NN preservation
Procrustes Co-ranking
没有单一的”最好”指标——取决于你关心数据结构的哪个层次。
1.2 距离保持类
Spearman / Rank Correlation
高维距离矩阵 ${d_X(i,j)}$ 与低维距离矩阵 ${d_Z(i,j)}$ 之间的秩相关系数（去掉对角线的所有点对）。值越接近1说明距离顺序保持得越好。
Shepard Diagram / Stress
Shepard diagram 是散点图，横轴为高维距离，纵轴为低维距离，理想情况所有点落在 $y=x$ 上。
Stress（归一化残差） 则量化偏离程度：
\[\text{Stress} = \frac{\sum_{i<j} (d_X(i,j) - d_Z(i,j))^2}{\sum_{i<j} d_X(i,j)^2}\]MDS 系列方法直接优化这个指标，其他方法（t-SNE、UMAP）通常不直接优化它但可以用它来评价。
Sammon’s Stress
与 Stress 类似但给短距离更高权重：
\[E_{\text{Sammon}} = \frac{1}{\sum_{i<j} d_X(i,j)} \sum_{i<j} \frac{(d_X(i,j) - d_Z(i,j))^2}{d_X(i,j)}\]Residual Variance
\[\text{Residual Var} = 1 - \rho^2(D_X, D_Z)\]其中 $\rho$ 是 Pearson 相关。值越小越好。
1.4 下游任务类（Downstream Task Evaluation） ⭐
这是更常用也更有说服力的做法：降维后的低维嵌入 $Z$ 不直接看结构保持，而是跑一个下游任务，看降维后的数据能不能把任务做好。如果下游任务表现好，说明降维保住了任务相关的信息。
K-means 聚类质量（K-means on Embedding）
对低维嵌入 $Z$ 跑 k-means（用欧氏距离），然后用 ARI / NMI / AMI / Silhouette 评估聚类质量：
\[\text{DR-KMeans-ARI} = \text{ARI}\big(\text{KMeans}(Z, k), Y\big)\]这是 t-SNE、UMAP、PCA 论文里最常用来对比的方法之一——虽然降维方法本身没有聚类，但如果嵌入空间本身是”好”的，k-means 应该能从中提取出有意义的簇。
指标选哪个： - 有标签数据：ARI 或 NMI，看聚类是否与真实标签对齐 - 无标签数据：Silhouette，看嵌入空间中是否存在自然的簇结构
KNN 分类准确率（KNN Accuracy on Embedding）
在低维嵌入 $Z$ 上跑一个简单的 $k$-近邻分类器，用真实标签算准确率：
\[\text{KNN-ACC}(k) = \frac{1}{n} \sum_{i=1}^n \mathbb{1}\big(\text{KNN}(Z_{-i}, k) = y_i\big)\]一般取 $k=1$ 或 $k=5$，用留一法（LOO）或交叉验证。值越高说明嵌入空间保留了类别判别信息。
为什么有效： KNN 是一个没有归纳偏置的非参数分类器——如果它在低维嵌入上表现好，说明降维真的保留了数据的判别结构，而不只是拟合了某个特定分类器的偏好。
很多论文会用 1-NN LOO accuracy 作为标准指标，简单、可复现。
KNN 检索/回召（KNN Retrieval Precision）
对每个查询点，看它在低维空间的 $k$ 近邻中有多少与它同标签：
\[\text{KNN-Precision}(k) = \frac{1}{n} \sum_{i=1}^n \frac{|\mathcal{N}_i^k(Z) \cap \text{same-class}(i)|}{k}\]相当于另一种量化的邻域保持，但不是看高维邻居是否被保持，而是直接看语义标签是否在嵌入空间中局部一致。
Reconstruction-based（重建误差法）
如果降维方法有显式的解码/重建机制： - PCA：$|X - ZW^T|_F^2$ - Autoencoder：$|X - \text{Dec}(Z)|_2^2$ - Distributional Reduction：低维原型点通过 srGW 映射回高维的重建误差
但注意：很多流行降维方法（t-SNE, UMAP）没有自然的重建机制。
1.5 全局结构保持类
Procrustes Analysis
通过旋转/缩放/平移将低维嵌入对齐到高维空间的某种参考（如PCA的结果），然后计算均方根误差：
\[\text{Procrustes RMSE} = \min_{R, t, s} \frac{1}{n} \| ZR + t - sX_{\text{ref}}\|_F^2\]反映了降维结果与”标准”全局结构之间的形状差异。
Explained Variance（PCA特有）
\[\text{EV}(d) = \frac{\sum_{j=1}^d \lambda_j}{\sum_{j=1}^D \lambda_j}\]对于 PCA 直接适用，对非线性降维方法意义不大。
Kruskal’s Stress
\[\text{Stress-1} = \sqrt{\frac{\sum_{i<j} \big(d_Z(i,j) - \hat{d}(i,j)\big)^2}{\sum_{i<j} d_Z(i,j)^2}}\]适用于 MDS 类方法，$\hat{d}$ 是最优单调回归后的距离。
二、聚类评价指标
聚类指标分为两类：外部指标（有ground truth标签）和内部指标（无标签，仅靠数据自身结构）。
2.1 外部指标
假设真实标签为 $Y$，聚类结果为 $\hat{Y}$。
Adjusted Rand Index（ARI）
ARI 是 Rand Index 的修正版，排除了随机聚类的期望值：
\[\text{ARI} = \frac{\text{RI} - \mathbb{E}[\text{RI}]}{\max(\text{RI}) - \mathbb{E}[\text{RI}]}\]用计数表表示：设 $n_{ij}$ 为真实类别 $i$、聚类 $j$ 中的样本数，$a_i$ 为真实类别 $i$ 的总数，$b_j$ 为聚类 $j$ 的总数。
\[\text{ARI} = \frac{\sum_{ij} \binom{n_{ij}}{2} - \big[\sum_i \binom{a_i}{2} \sum_j \binom{b_j}{2}\big] / \binom{n}{2}}{\frac{1}{2} \big[\sum_i \binom{a_i}{2} + \sum_j \binom{b_j}{2}\big] - \big[\sum_i \binom{a_i}{2} \sum_j \binom{b_j}{2}\big] / \binom{n}{2}}\]取值 $[-1, 1]$，1 是完全一致，0 是随机。最推荐的外部指标——对类别不平衡不敏感。
Normalized Mutual Information（NMI）
\[\text{NMI}(Y, \hat{Y}) = \frac{2 I(Y; \hat{Y})}{H(Y) + H(\hat{Y})}\]$I$ 是互信息，$H$ 是熵。取值 $[0, 1]$。
Adjusted Mutual Information（AMI）
NMI 的修正版，同样排除了随机期望值：
\[\text{AMI} = \frac{\text{MI} - \mathbb{E}[\text{MI}]}{\max(H(Y), H(\hat{Y})) - \mathbb{E}[\text{MI}]}\]比 NMI 更可靠，对聚类数多少更鲁棒。
Homogeneity, Completeness, V-measure
- Homogeneity（同质性）：每个聚类中只包含单个类别的样本
- Completeness（完整性）：同一类别的所有样本被分到同一个聚类中
- V-measure：两者的调和平均
Fowlkes-Mallows Index（FMI）
\[\text{FMI} = \frac{\text{TP}}{\sqrt{(\text{TP} + \text{FP})(\text{TP} + \text{FN})}}\]基于点对的分类——所有样本对要么在同一聚类中（正），要么不在（负）。取值 $[0, 1]$。
Purity（纯度）
\[\text{Purity} = \frac{1}{n} \sum_{j=1}^k \max_i n_{ij}\]简单直观的缺点：聚类数越多纯度越高，且对不平衡很敏感。
Clustering Accuracy（ACC）
先用匈牙利算法（Hungarian algorithm）做聚类与真实标签的最佳匹配，再算准确率。常用于 k-means 等论文。
Pairwise F-measure
计算所有点对的精确率和召回率的调和平均，与FMI类似但可以调 $\beta$ 权重。
Rand Index（原始 RI）
\[\text{RI} = \frac{\text{TP} + \text{TN}}{\text{TP} + \text{TN} + \text{FP} + \text{FN}}\]取值 $[0, 1]$。注意它没有做随机校正——所以当聚类数增多时 RI 天然偏高。ARI 通常是更好的选择，但 RI 更直觉，有时用于简单汇报。
Variation of Information（VI）
Meilă (2003, 2007) 从信息论角度定义的两个聚类之间的距离：
\[\text{VI}(Y, \hat{Y}) = H(Y) + H(\hat{Y}) - 2 I(Y; \hat{Y}) = H(Y | \hat{Y}) + H(\hat{Y} | Y)\]取值 $[0, \log n]$，越小越好。VI 是严格的度量（满足三角不等式），而 NMI/ARI 不是。在聚类比较的理论分析中非常有用，但实践中的解读不如 NMI 直观。
Cophenetic Correlation Coefficient（共表型相关系数）
专用于评估层次聚类（hierarchical clustering）的树状图质量。
算法流程： 1. 对数据做层次聚类，得到树状图（dendrogram） 2. 对每对点 $(i,j)$，提取它们在树状图中首次合并时的高度（cophenetic distance），记为 $c_{ij}$ 3. 计算 $C = \text{Corr}(d_{ij}, c_{ij})$，即原始距离矩阵 ${d_{ij}}$ 与共表型距离矩阵 ${c_{ij}}$ 的 Pearson 相关系数：
\[C = \frac{\sum_{i<j} (d_{ij} - \bar{d})(c_{ij} - \bar{c})}{\sqrt{\sum_{i<j} (d_{ij} - \bar{d})^2} \sqrt{\sum_{i<j} (c_{ij} - \bar{c})^2}}\]值越接近 1 越好——说明树状图忠实地反映了原始距离结构。
注意事项： 仅适用于层次聚类（agglomerative/divisive），不适用于 k-means 等扁平聚类。
2.2 内部指标
没有真实标签时，靠数据的几何结构来评估聚类质量。
Silhouette Score（轮廓系数）
对每个样本 $i$，计算： - $a(i)$：与同簇其他样本的平均距离（簇内紧致度） - $b(i)$：与最近邻簇中所有样本的平均距离（簇间分离度）
\[s(i) = \frac{b(i) - a(i)}{\max(a(i), b(i))},\quad \text{Silhouette} = \frac{1}{n}\sum_{i=1}^n s(i)\]取值 $[-1, 1]$，越大越好。最常用的内部指标，但计算复杂度 $O(n^2)$。 对凸簇有效，对任意形状的簇可能失真。
Davies–Bouldin Index（DBI）
\[\text{DBI} = \frac{1}{k} \sum_{i=1}^k \max_{j \neq i} \frac{\sigma_i + \sigma_j}{d(c_i, c_j)}\]其中 $\sigma_i$ 是簇 $i$ 中点到中心的平均距离，$d(c_i, c_j)$ 是两簇中心的距离。值越小越好。
Calinski–Harabasz Index（CH / VRC）
\[\text{CH} = \frac{\text{Tr}(B_k)}{\text{Tr}(W_k)} \times \frac{n - k}{k - 1}\]$B_k$ 是簇间散度矩阵，$W_k$ 是簇内散度矩阵。值越大越好。计算快，但假设凸簇。
Dunn Index
\[\text{Dunn} = \frac{\min_{i \neq j} \delta(C_i, C_j)}{\max_{1 \leq l \leq k} \Delta(C_l)}\]$\delta$ 是两簇间最小距离（最短的簇间距离），$\Delta$ 是簇内最大直径（最远的两点距离）。值越大越好。对离群点很敏感。
Gap Statistic
比较实际数据的 WSS（within-cluster sum of squares）与随机均匀数据的 WSS：
\[\text{Gap}(k) = \mathbb{E}[\log W_{\text{null}}(k)] - \log W(k)\]选择使 Gap 最大的 $k$，或 Gap 增速突然放缓的 $k$。
Ball-Hall Index
\[\text{Ball-Hall} = \frac{1}{k} \sum_{i=1}^k \frac{W_i}{n_i}\]其中 $W_i$ 是簇 $i$ 内各点到中心距离的平方和，$n_i$ 是簇 $i$ 中点数。值越小越好。
Hubert’s Gamma（Hubert’s Γ 统计量）
计算点对”是否属于同一簇”与”距离远近”之间的相关性。构造两个矩阵： - $P$：$P_{ij} = 1$ 如果 $i,j$ 在同一簇，否则 0 - $D$：$d_X(i,j)$（或单调变换）
\[\Gamma = \frac{1}{M} \sum_{i=1}^{n-1} \sum_{j=i+1}^n \frac{(P_{ij} - \bar{P})(D_{ij} - \bar{D})}{\sigma_P \sigma_D}\]取值 $[-1, 1]$，越大越好。归一化版本称为 Hubert’s normalized Gamma。
Point Biserial Correlation（点二列相关）
同样是基于点对的相关性——看”距离”与”是否同簇”的 Pearson 相关：
\[\text{PB} = \frac{\bar{d}_{\text{within}} - \bar{d}_{\text{between}}}{\sigma_d} \sqrt{\frac{n_{\text{within}} \cdot n_{\text{between}}}{n(n-1)/2}}\]负值说明簇内距离小于簇间距离——这是期望的情况。
BIC / AIC（信息准则类）
对基于概率模型的聚类（GMM）：
\[\text{BIC} = -2\log L(\hat{\theta}) + k \log n, \quad \text{AIC} = -2\log L(\hat{\theta}) + 2k\]选择 BIC 或 AIC 最小的 $k$。BIC 更保守（惩罚更重）。聚类形状（协方差结构）的选择也通过 BIC 比较。
Clustering Stability / Consensus Clustering（聚类稳定性） ⭐
核心思想：好的聚类应对数据扰动不敏感。通过重采样评估。
通用算法（bootstrap + ARI）： ``` 输入：数据 X，聚类算法 A，聚类数 k，重采样次数 B 输出：稳定性得分 S
for b = 1 to B: 1. 从 X 中 bootstrap 采样（有放回），得到 X_b 2. 在 X_b 上跑 A，得聚类标签 y_b 3. 在 X 的原始点上，用最近邻映射 y_b 到全量标签 y_b^full （或：对不在 X_b 中的点用 A 预测）
计算一致性矩阵 C： C[i][j] = (样本 i,j 在 bootstrap 中同时出现的次数中， 它们被分到同一簇的比例)
计算稳定性：S = 在 C 上跑 A 的 ARI 或 S = mean_{b≠b’} ARI(y_b^full, y_{b’}^full) ```
如果聚类方法对数据扰动敏感，说明发现的结构虚假。稳定性好的聚类更可信。
公式版：
\[\text{Stability} = \frac{2}{B(B-1)} \sum_{1 \leq b < b' \leq B} \text{ARI}(\hat{Y}_b, \hat{Y}_{b'})\]常见的稳定性方法： - Brecken’s method：子样本聚类 → 用最近邻分类器预测剩余样本 → 比较两次预测的一致性 - Lange’s method：类似重采样 + kappa 系数而不是 ARI - Ben-Hur’s method：基于自洽性（self-consistency）的图结构分析
计算量警告： $O(B \cdot T_A)$，其中 $T_A$ 是聚类算法的单次运行时间。B=20~50 是常见的折中。
其他内部指标（快速参考）
| 指标 | 完整公式 | 计算流程 | 越小越好？ |
|---|---|---|---|
| Scott-Symons | $\sum_{i=1}^k n_i \log \frac{|W_i|}{n_i}$ | 1. 对每个簇 $i$，计算类内协方差矩阵 $W_i$ 2. $|W_i|$ 是 $W_i$ 的行列式 3. 加权求和 |
越小 |
| Krzanowski-Lai | $\text{KL}(k) = \left| \frac{\text{CH}(k) - \text{CH}(k-1)}{\text{CH}(k+1) - \text{CH}(k)} \right|$ | 1. 对 $k = k_{\min}$ 到 $k_{\max}$ 算 CH index 2. 计算相邻 CH 的差分比 3. 选 $\text{KL}(k)$ 最大的 $k$ |
选 KL 最大的 $k$ |
| Hartigan | $\text{Hart}(k) = \left( \frac{\text{Tr}(W_k)}{\text{Tr}(W_{k+1})} - 1 \right)(n - k - 1)$ | 1. 对 $k=1$ 到 $k_{\max}$ 算 Tr($W_k$) 2. 计算相邻 WSS 比的变换 3. 选 $\text{Hart}(k) < 10$ 的首个 $k$ |
选首次 < 10 的 $k$ |
| McClain-Rao | $\frac{\bar{d}{\text{within}}}{\bar{d}{\text{between}}}$ | 1. 计算所有簇内点对距离的平均值 $\bar{d}{\text{within}}$ 2. 计算所有簇间点对距离的平均值 $\bar{d}{\text{between}}$ 3. 取比值 |
越小 |
| C-Index | $\frac{S_{\text{within}} - \min(S_{\text{within}})}{\max(S_{\text{within}}) - \min(S_{\text{within}})}$ | 1. $S_{\text{within}}$ = 所有簇内点对距离之和 2. $\min(S_{\text{within}})$ = 所有点对中取 $n_{\text{within}}$ 个最小距离的和 3. $\max$ 同理取最大距离和 |
越小 ($\leq 1$) |
| Trace W (肘部) | $\text{Tr}(W_k) = \sum_{i=1}^k \sum_{x \in C_i} |x - \mu_i|^2$ | 1. 对每个 $k$ 算 WSS 2. 画 $\text{Tr}(W_k) \sim k$ 曲线 3. 找”肘部”（拐点） |
越小（但不是选最小的，选肘部） |
三、Joint 指标（降维 + 聚类同步评价）
有些方法（如 Distributional Reduction、srGW 降维）同时做降维和聚类，评价时需要兼顾两方面。
3.1 原型质量指标
分布缩减（Distributional Reduction）产出的是低维原型点（prototypes）。评价这类方法：
- Cluster Purity（基于原型分配）：看每个原型映射到的原始数据点的类别纯度
- Reconstruction Error：低维原型映射回高维空间的重建误差（与PCA的reconstruction类似，但用非线性的srGW重建）
- Prototype Coverage：原始数据点离最近原型的平均距离（越小越充分的覆盖）
3.2 Mixed Metrics
- NMI + Trustworthiness 联合曲线：以聚类质量（NMI）为横轴、降维质量（Trustworthiness）为纵轴，看方法是否能同时在两个指标上取得好成绩。Distributional Reduction 论文用这种思路。
- Scatter Plot of DR + Color by Cluster：可视化上，好的结果应该同时呈现（1）清晰的分离簇（2）每个簇内的几何结构被合理保持
3.3 谱系指标
当聚类数 $K$ 与嵌入维度 $d$ 之间存在连续谱时（分布缩减的核心创新），需要考察：
- Interpolation Trajectory：固定 $K$ 变化 $d$（或反之）时，NMI 和 Trustworthiness 如何连续变化
- Pseudo-R²：每个数据点到原型之间关系的拟合优度
四、实战建议
| 场景 | 推荐指标组合 |
|---|---|
| 降维论文（标准） | Trustworthiness + Continuity + MRRE + KNN-ACC + NMI on k-means |
| 降维论文（快速） | Trustworthiness(k=5,30,100) + 1-NN LOO |
| 降维论文（有标签数据） | KNN-ACC(1) + NMI(k-means) + Trustworthiness（三个维度） |
| 降维论文（无标签数据） | Trustworthiness + Continuity + Silhouette on embedding |
| 聚类论文（有标签） | ARI + NMI（并列，两个都要看） |
| 聚类论文（无标签） | Silhouette + DBI + Gap Statistic |
| 同时做降维+聚类 | ARI(k-means) + Trustworthiness + 联合散点图 |
| 评估不同降维方法的可视化质量 | Trustworthiness + 目视检查 + 1-NN LOO |
| k-means变体 | ARI + CH index（CH基于欧氏距离正好匹配k-means的前提） |
常见坑： - ARI 在 $n$ 较小时方差很大，需要多次重复 - Silhouette 对非凸簇完全不work - Trustworthiness 只取一个 $k$ 会误导——必须画 $k$ 从1到 $n/2$ 的曲线 - 没有”最好的指标”，永远要配合可视化看
五、计算复杂度总表
下面的复杂度以 $n$ 为样本数、$D$ 为原始维度、$d$ 为降维后维度、$k$ 为近邻数或聚类数来标注。假设距离矩阵已预计算（$O(n^2 D)$），除非特别说明。
5.1 降维指标复杂度
| 指标 | 时间复杂度 | 空间复杂度 | 关键操作 | 注意 |
|---|---|---|---|---|
| Trustworthiness $(k)$ | $O(n^2 \log n + n^2 k)$ | $O(n^2)$ | 全距离矩阵 + 排序 | 瓶颈在排序 |
| Continuity $(k)$ | $O(n^2 \log n + n^2 k)$ | $O(n^2)$ | 同上 | 同上 |
| MRRE $(k)$ | $O(n^2 \log n + n^2 k)$ | $O(n^2)$ | 同上 + 秩差 | 略慢于 T+C |
| NH $(k)$ | $O(n^2 \log n)$ | $O(n^2)$ | 排序 + 求交 | 快于 T+C |
| AUC of NP | $O(n^2 \log n)$ | $O(n^2)$ | NH 对所有 k 积分 | 快速 |
| LCMC | $O(n^2 \log n)$ | $O(n^2)$ | co-ranking 矩阵 | 等价于 T+C-1，$O(1)$ 额外 |
| Triplet Accuracy | $\boldsymbol{O(n^3 \log n)}$ ⚠️ | $O(n^2)$ | 全三元组排序比较 | n > 1000 时不可行，一般用采样近似 |
| C Measure | $\boldsymbol{O(n^3)}$ ⚠️ | $O(1)$ | 三元组比较 | 同上，$\binom{n}{3} \approx n^3/6$ |
| KL Divergence | $O(n^2)$ | $O(n^2)$ | softmax + 求和 | 较快 |
| Spearman $\rho$ | $O(n^2 \log n)$ | $O(n^2)$ | 全秩排序 | 无需指定 k |
| Stress | $O(n^2)$ | $O(n^2)$ | 简单代数 | 最快之一 |
| Sammon Stress | $O(n^2)$ | $O(n^2)$ | 加权 Stress | 比 Stress 多一步除法 |
| Residual Var | $O(n^2)$ | $O(n^2)$ | Pearson 相关 | 快速 |
| Procrustes | $O(D d^2 + d^3)$ | $O(Dd)$ | SVD | 维度无关 $n$ |
| KNN-ACC | $O(n^2 \log n + n k)$ | $O(n^2)$ | 距离排序 + LOO 投票 | 1-NN 最快 |
| K-means on embedding | $O(n k d \cdot \text{iter})$ | $O(n d + k d)$ | Lloyd 迭代 | 比 true k 慢，iter ~ 10-100 |
5.2 聚类外部指标复杂度
| 指标 | 时间复杂度 | 空间复杂度 | 关键操作 | 注意 |
|---|---|---|---|---|
| ARI | $O(n k + k^2)$ | $O(k^2)$ | 列联表 | 极快 |
| NMI | $O(n k + k^2)$ | $O(k^2)$ | 熵/互信息 | 极快 |
| AMI | $O(n k + k^2)$ | $O(k^2)$ | NMI + 期望估计 | 比 NMI 多算一项 |
| Homogeneity/Completeness | $O(n k)$ | $O(k^2)$ | 条件熵 | 极快 |
| FMI | $O(n^2)$ | $O(n^2)$ | 全点对计数 | n 大时慢，可采样 |
| Purity | $O(n k)$ | $O(k^2)$ | 列联表 max | 极快 |
| ACC | $O(k^3 + n)$ | $O(k^2)$ | Hungarian 匹配 | $k < 50$ 时极快 |
| RI | $O(n^2)$ | $O(n^2)$ | 全点对 | n 大时慢 |
| VI | $O(n k + k^2)$ | $O(k^2)$ | 熵 + 互信息 | 极快 |
| Cophenetic | $O(n^2)$ | $O(n^2)$ | 树状图距离 + 相关 | 仅层次聚类 |
5.3 聚类内部指标复杂度
| 指标 | 时间复杂度 | 空间复杂度 | 关键操作 | 注意 |
|---|---|---|---|---|
| Silhouette | $\boldsymbol{O(n^2)}$ ⚠️ | $O(n^2)$ | 全距离 + 跨簇平均 | n=10⁵ 时不可行 |
| DBI | $O(n k d + k^2)$ | $O(k^2)$ | 簇中心 + 半径 | 快 |
| CH | $O(n d k)$ | $O(d^2)$ | 散度矩阵迹 | 快 |
| Dunn | $\boldsymbol{O(n^2)}$ ⚠️ | $O(n^2)$ | 簇间/簇内距离极值 | 对噪声敏感 |
| Gap Statistic | $\boldsymbol{O(B \cdot n \cdot k \cdot d)}$ ⚠️ | $O(n^2)$ | B 次 bootstrap | B=10~50，每次跑 k-means |
| Ball-Hall | $O(n d k)$ | $O(d)$ | WSS 累加 | 快 |
| Hubert’s Gamma | $\boldsymbol{O(n^2)}$ ⚠️ | $O(n^2)$ | 全点对相关 | n 大时慢 |
| Point Biserial | $\boldsymbol{O(n^2)}$ | $O(n^2)$ | 同上变体 | 同上 |
| BIC / AIC | $O(n d k + k d^2)$ | $O(d^2)$ | MLE + 似然 | GMM 时更慢 |
| Stability | $\boldsymbol{O(B \cdot n \cdot k \cdot d \cdot \text{iter})}$ ⚠️ | $O(n k)$ | 重采样 + 再聚类 | B=20~100，昂贵 |
| Krzanowski-Lai | $O(n d k)$ | $O(d^2)$ | 基于 CH 的比值 | 需算多个 k 的 CH |
| Hartigan | $O(n d k)$ | $O(d)$ | WSS 比值 | 需算多个 k 的 WSS |
| McClain-Rao | $\boldsymbol{O(n^2)}$ | $O(n^2)$ | 全距离平均 | 同 Silhouette |
| C-Index | $\boldsymbol{O(n^2)}$ | $O(n^2)$ | 极值搜索 | 同 Silhouette |
| Trace W (肘部) | $O(n d k)$ | $O(d)$ | WSS 累加 | 极快 |
5.4 复杂度速记口诀
降维：O(n² log n) 是日常，O(n³) 别碰（Triplet/C）
聚类外部：O(nk) 到 O(k³)，列联表就够
聚类内部：快的 O(ndk)，慢的 O(n²)
最贵操作排序：距离矩阵计算 > 全排序 > Lloyd > 列联表
速度优先级排序（从快到慢）： 1. 超快 ($\ll 1s$ for n=10⁴)：ARI, NMI, Purity, CH, BIC — 适合大规模筛选 2. 快 ($\sim 1s$)：Trustworthiness, KNN-ACC, DBI — 标准配置 3. 中 ($\sim 10s$)：Silhouette, Gap Statistic — n 到万级 4. 慢 ($\sim \text{min}$)：Stability (bootstrap), Triplet Accuracy — 仅验证实验
实战经验： 对于 n=10⁴、D=100 的数据集，算全距离矩阵约 0.5s，Trustworthiness(十个 k) 约 2s，Silhouette 约 1s，Stability(B=20) 约 30s。时间大头一般在多次跑 k-means（对每个 k 值），而不是算指标本身。