维度灾难

维度灾难 (Curse of Dimensionality)

维度灾难→1957 Bellman→机器学习/统计/数据挖掘→高维空间致传算法非线性/指数恶→涵盖距离失效/样本稀疏/计算爆/过拟合。

数学本质与影响

距离集中→d→∞→任意两点距收$\sqrt{d/6}$→方差/均比→0→失判别→最近邻/聚类基挑。样本稀疏→维数为d→覆同密需样量指数增→$N\propto(1/\epsilon)^d$→超立方体样集边界非内部→高度稀疏。计算激增→网格→每维k分→$k^d$单元→kd树退近线性→梯度下降面更局极/鞍点。过拟合→d>n→设阵趋奇→解不稳→噪声维与信号混杂→模将随波视真→$d/n\to c$时线模测差收非最优。

对算法影响：①最邻→$\mathbb{E}[d_{\min}]\approx(1/N)^{1/d}$→d=2,N=1000→距≈0.03→d=100→距≈0.9→几覆全空。②核密度→带宽$h_{opt}\propto N^{-1/(d+4)}$→收敛极慢。③k-means→簇内距/簇间距比→1→轮廓系数效。④决策树→可树结数$V^{O(d)}$→模选剪极难。

应对与前沿

约简：特征选择(相关/互信/L1稀)→PCA($max_W tr(W^T\Sigma W)$)→LDA→流形学习(t-SNE/UMAP/Isomap)。正则化：Lasso$min\|y-Xw\|^2+\lambda\|w\|_1$→稀解→岭回归L2→弹性网络。他法：核方法(隐式高不显式算)→随机森林(特征子空采)→深度学习(逐层抽象自动学低维表→自编码器)→贝叶斯(高斯过程核控函空容)。

理论：VC维→d+1需N≥O(d)→双重下降挑传统→内在维度→真数据位高维低流形→有效算复倚$d_{int}$非$d_{env}$。核→加特征非总益→须在表力/数需/算城衡。