维数灾难的深度理解
看机器学习的论⽂时，经常会看到有作者提到“cur of dimensionality”，中⽂译为“维数灾难”，这到底是⼀个什么样的“灾难”？本⽂将通过⼀个例⼦来介绍这令⼈讨厌的“cur of dimensionality”以及它在分类问题中的重要性。
假设现在有⼀组照⽚，每⼀张照⽚⾥有⼀只猫或者⼀条狗。我们希望设计⼀个分类器可以⾃动地将照⽚中的动物辨别开来。为了实现这个⽬标，⾸先需要考虑如何将照⽚中的动物的特征⽤数字的形式表达出来。猫与狗的最⼤区别是什么？有⼈可能⾸先想到猫与狗的颜⾊不⼀样，有⼈则可能想到猫与狗的⼤⼩不⼀样。假设从颜⾊来辨别猫与狗，可以设计三个特征：红⾊的平均值，绿⾊的平均值和蓝⾊的平均值，来决定照⽚中的动物属于哪⼀个类：
1if 0.5 * red + 0.3 * green + 0.2 * blue > 0.6:
2return cat
hamony
scenery3el:
4return dog
但是，仅仅通过这三个特征进⾏分类可能⽆法得到⼀个令⼈满意的结果。因此，可以再增加⼀些特征：⼤⼩，纹理等。也许增加特征之后，分类的结果会有所提⾼。但是，特征是不是越多越好？
图1 过了某⼀个值后，分类器的性能随着维数的增加不升反降
从图1可以看到分类器的性能随着特征个数的变化不断增加，过了某⼀个值后，性能不升反降。这种现象称为“维数灾难”。
继续之前的例⼦。假设地球上猫和狗的数量是⽆限的。由于有限的时间和计算能⼒，我们仅仅选取了10张照⽚作为训练样本。我们的⽬的是基于这10张照⽚来训练⼀个线性分类器，使得这个线性分类器可以对剩余的猫或狗的照⽚进⾏正确分类。我们从只⽤⼀个特征来辨别猫和狗开始：
adele怎么读
图2
从图2可以看到，如果仅仅只有⼀个特征的话，猫和狗⼏乎是均匀分布在这条线段上，很难将10张照⽚线性分类。那么，增加⼀个特征后的情况会怎么样：
sign是什么意思图3
增加⼀个特征后，我们发现仍然⽆法找到⼀条直线将猫和狗分开。所以，考虑需要再增加⼀个特征：
图3
图4
此时，我们终于找到了⼀个平⾯将猫和狗分开。需要注意的是，只有⼀个特征时，假设特征空间是长度为5的线段，则样本密度是
石家庄会计培训学校10/5=2。有两个特征时，特征空间⼤⼩是5*5=25，样本密度是10/25=0.4。有三个特征时，特征空间⼤⼩是5*5*5=125，样本密度是
10/125=0.08。如果继续增加特征数量，样本密度会更加稀疏，也就更容易找到⼀个超平⾯将训练样本分开。因为随着特征数量趋向于⽆限⼤，样本密度⾮常稀疏，训练样本被分错的可能性趋向于零。当我们将⾼维空间的分类结果映射到低维空间时，⼀个严重的问题出现了：
图5
从图5可以看到将三维特征空间映射到⼆维特征空间后的结果。尽管在⾼维特征空间时训练样本线性可分，但是映射到低维空间后，结果正好相反。事实上，增加特征数量使得⾼维空间线性可分，相当于在低维空间内训练⼀个复杂的⾮线性分类器。不过，这个⾮线性分类器太过“聪明”，仅仅学到了⼀些特例。如果将其⽤来辨别那些未曾出现在训练样本中的测试样本时，通常结果不太理想。这其实就是我们在机器学习中学过的过拟合问题。
图6
尽管图6所⽰的只采⽤2个特征的线性分类器分错了⼀些训练样本，准确率似乎没有图4的⾼，但是，采⽤2个特征的线性分类器的泛化能⼒⽐采⽤3个特征的线性分类器要强。因为，采⽤2个特征的线性分类器学习到的不只是特例，⽽是⼀个整体趋势，对于那些未曾出现过的样本也可以⽐较好地辨别开来。换句话说，通过减少特征数量，可以避免出现过拟合问题，从⽽避免“维数灾难”。
图7
图7从另⼀个⾓度诠释了“维数灾难”。假设只有⼀个特征时，特征的值域是0到1，每⼀只猫和狗的特征值都是唯⼀的。如果我们希望训练样本覆盖特征值值域的20%，那么就需要猫和狗总数的20%。我们增加⼀个特征后，为了继续覆盖特征值值域的20%就需要猫和狗总数的45%(0.45^2=0.2)。继续增加⼀个特征后，需要猫和狗总数的58%(0.58^3=0.2)。随着特征数量的增加，为了覆盖特征值值域的20%，就需要更多的训练样本。如果没有⾜够的训练样本，就可能会出现过拟合问题。
通过上述例⼦，我们可以看到特征数量越多，训练样本就会越稀疏，分类器的参数估计就会越不准确，更加容易出现过拟合问题。“维数灾难”的另⼀个影响是训练样本的稀疏性并不是均匀分布的。处于中⼼位置的训练样本⽐四周的训练样本更加稀疏。
图8
假设有⼀个⼆维特征空间，如图8所⽰的矩形，在矩形内部有⼀个内切的圆形。由于越接近圆⼼的样本越稀疏，因此，相⽐于圆形内的样本，那些位于矩形四⾓的样本更加难以分类。那么，随着特征数量的增加，圆形的⾯积会不会变化呢？这⾥我们假设超⽴⽅体(hypercube)的边长d=1，那么计算半径为0.5的超球⾯(hypersphere)的体积(volume)的公式为：
idp
公式1
图9
从图9可以看出随着特征数量的增加，超球⾯的体积逐渐减⼩直⾄趋向于零，然⽽超⽴⽅体的体积却不变。这个结果有点出乎意料，但部分说明了分类问题中的“维数灾难”：在⾼维特征空间中，⼤多数的训练样本位于超⽴⽅体的⾓落。
英国人的性格
图10
图10显⽰了不同维度下，样本的分布情况。在8维特征空间中，共有2^8=256个⾓落，⽽98%的样本分布在这些⾓落。随着维度的不断增加，公式2将趋向于0，其中dist_max和dist_min分别表⽰样本到中⼼的最⼤与最⼩距离。
公式2concutive
因此，在⾼维特征空间中对于样本距离的度量失去意义。由于分类器基本都依赖于如Euclidean距离，Manhattan距离等，所以在特征数量过⼤时，分类器的性能就会出现下降。
所以，我们如何避免“维数灾难”？图1显⽰了分类器的性能随着特征个数的变化不断增加，过了某⼀个值后，性能不升反降。这⾥的某⼀个值到底是多少呢？⽬前，还没有⽅法来确定分类问题中的这个阈值是多少，这依赖于训练样本的数量，决策边界的复杂性以及分类器的类型。理论上，如果训练样本的数量⽆限⼤，那么就不会存在“维数灾难”，我们可以采⽤任意多的特征来训练分类器。事实上，训练样本的数量是有限的，所以不应该采⽤过多的特征。此外，那些需要精确的⾮线性决策边界的分类器，⽐如neural network，knn，decision trees等的泛化能⼒往往并不是很好，更容易发⽣过拟合问
题。因此，在设计这些分类器时应当慎重考虑特征的数量。相反，那些泛化能⼒较好的分类器，⽐如naive Bayesian，linear classifier等，可以适当增加特征的数量。
英语语法新思维 如果给定了N个特征，我们该如何从中选出M个最优的特征？最简单粗暴的⽅法是尝试所有特征的组合，从中挑出M个最优的特征。事实上，这是⾮常花时间的，或者说不可⾏的。其实，已经有许多特征选择算法()来帮助我们确定特征的数量以及选择特征。此外，还有许多特征抽取⽅法()，⽐如等。交叉验证()也常常被⽤于检测与避免过拟合问题。
参考资料：
[1] Vincent Spruyt. The Cur of Dimensionality in classification. Computer vision for dummies. 2014. []
dance with me
