一、维度灾难

1. 近邻法要求样本点比较密集。给定测试样本点 ，理论上希望在 附近距离 范围内总能找到一个训练样本 ，其中 是个充分小的正数。即：要求训练样本的采样密度足够大，也称作“密采样”。

   • 假设 ， 且假设样本点只有一个特征，且该特征归一化后范围是 [0,1] ，则需要 1000 个样本点平均分布在 [0,1] 之间。

     此时任何测试样本在其附近 0.001 距离范围内总能找到一个训练样本。

   • 假设 ， 且假设样本点只有十个特征，且该特征归一化后范围是 [0,1]，则需要 个样本点平均分布[0,1] 之间。

     此时任何测试样本在其附近 0.001 距离范围内总能找到一个训练样本。

2. 现实应用中特征维度经常成千上万，要满足密采样所需的样本数目是个天文数字。

   另外许多学习方法都涉及距离计算，而高维空间会给距离计算带来很大的麻烦（高维空间中计算内积都麻烦）。

   在高维情形下出现的数据样本稀疏、距离计算困难等问题是所有机器学习方法共同面临的严重障碍，称作“维度灾难”(curse of dimensionality)。

3. 缓解维度灾难的一个重要途径是降维(dimension reduction)。

   降维之所以有效的原因是：人们观测或者收集到的数据样本虽然是高维的，但是与学习任务密切相关的也许仅仅是某个低维分布，即高维空间中的一个低维“嵌入”。

4. 常见的降维方法：

   • 监督降维算法。如：线性判别分析Linear Discriminant Analysis:LDA 。
   • 无监督降维算法。如：主成分分析PCA 。

5. 对于降维效果的评估，通常是比较降维前后学习器的性能。如果性能有所提高，则认为降维起了作用。

   也可以将维数降至二维或者三维，然后通过可视化技术来直观地判断降维效果。

6. 对于常见的降维算法，无论是PCA 还是流形学习，都是基于距离来计算重构误差。此时建议对特征进行标准化，因为距离的计算依赖于特征的量纲。如身高特征：

   • 如果采用m量纲，则取值范围通常在1~2 之间。
   • 如果采用cm 量纲，则取值范围通常在100~200 之间。

   采用不同的量纲会导致不同的重构误差。