维度灾难

一、维度灾难及其影响

维度灾难
原文：The Curse of Dimensionality in classification

" In fact, data around the origin (at the center of the hypercube) is much more sparse than data in the corners of the search space. "
不明白为什么中心的数据会比角落的数据稀疏。

--------------------------------------------------------------------------------
以下摘自 当你在应用机器学习时你应该想什么
高维"灾难"
经过上一节你可能会想"既然特征工程这么重要, 那我就把想到的所有的特征组合都作为数据的特征不就好了吗". 这么做的结果会使特征维数增加, 一方面会增加存储和计算开销, 更重要的是, 它会招来机器学习担忧的另一头猛兽: 维数灾难(curse of dimensionality).

由于你能拿到手中的训练数据是有限的, 当维数增加时, 输入空间(input space)的大小随维数指数级增加, 训练数据占整个数据空间的比例将急剧下降, 这将导致模型的泛化变得更困难. 在高维空间中, 样本数据将变得十分稀疏, 许多的相似性度量在高维都会失效. 比如下图中, 最左边的是原图, 右边三张图看上去差别很大, 但和原图都有着相同的欧氏距离.

image
解决维数灾难的一个重要途径是降维(dimension reduction), 即通过一些手段将原始高维空间数据转变为一个低维子空间, 在这个子空间中样本密度大幅提高, 距离计算也更容易. 特征选择(feature selection)和低维投影(如PCA)是用来处理高维数据的两大主流技术.
--------------------------------------------------------------------------------

以下摘自知乎:
作者：周天元
链接：https://www.zhihu.com/question/27836140/answer/406327359
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

反对楼上几乎所有回答，因为他们只说了cod的一个方面，就是近邻。cod是一个很杂的现象，即使不是近邻也会遇到。如果只从近邻去理解cod，那很多东西你就理解不了。cod本身是一个总称，在不同算法下表现不同。例如在knn rbf-svm之类的local kernelmachine 中表现为近邻找不准，或者说，如果要找准近邻，那么所需数据量随维数(更精确点，该数据点所在流形维数)呈指数上升，这方面的资料可以参见bengio 在09年的paper，就叫curse of dimensionality of local kernel machines。如果对树方法比如随机森林，那么cod体现在树split时会split在noise dim上，或者说要想split准，所需数据量随树的层数呈指数上升，这方面的材料可以参见zhu ruoqing在2015年的文章reinforcement learning trees。如果对线性分类器，那么cod体现就多了，比如可以体现在分类边界的不稳定上，具体可以看liu feng的文章。总之cod是一个总称，背后反应的是complexity随维度增加而增加，这方面抽象成高级理论，就叫learning theory，具体可以看vapnik的教材。
--------------------------------------------------------------------------------

Bengio 论文 The Curse of Dimensionality for Local Kernel Machines

理解：在高维空间中，许多基于距离的度量都会失效，比如欧式距离。特征的维度越高，所需的数据越多，否则就容易过拟合。

二、如何解决维度灾难

解决维数灾难的一个重要途径是降维(dimension reduction), 即通过一些手段将原始高维空间数据转变为一个低维子空间, 在这个子空间中样本密度大幅提高, 距离计算也更容易. 特征选择(feature selection)和低维投影(如PCA)是用来处理高维数据的两大主流技术.