PRML系列：1.4 The Curse of Dimensionality
PRML系列：1.4 The Curse of Dimensionality
随便扯扯
PRML例举了一个人工合成的数据集，这个数据集中表示一个管道中石油，水，天然气各自所占的比例。这三种物质在管道中的几何形状有三种不同的配饰，被称为“同质状”、“环状”和“薄片状”。
输入有12个维度，是用伽马射线密度计采集的数据，输出对应的是三个类别：同质状，环状和薄片状。为了能够直观的呈现数据在二维空间中的分布，PRML可视化了
图中标注了一个”x”点，可以发现在”x”点附近大量聚集了红色类别的点，而蓝色的点和绿色点离”x”点较远，或者说蓝色呈现的空间并不在”x”点附近。于是PRML得出了一个直观的结论：”x”点的性质能够由它附近点所决定（有点像KNN）,但随着空间距离的增加，越远的点对它的影响则越小。
所以，直观的做法，对图中100个数据点进行空间划分，分成如上16个单元格，统计每个单元格出现类别最多的，作为预测标签。
但上述做法有两种致命的缺陷：
- 随着维度的增加，单元格的数目呈指数级增长，比如D = 2，对应的是4^2 = 16个单元格，而当D = 3时，为4^3 = 64个单元格。
- 这种简单粗暴的方法没法适应数据稀疏的问题，这要求每个单元格内至少有一堆数据存在，所以随着维度的增加，对数据大小的要求也是指数上升的。（非常感性的认识）
这里给出理性的解释，比如假设对应一维特征的取值范围为[0, 4]，那么固定样本大小100，在一维线密度如下： 100 / 5 = 20，表示平均每个坐标点周围能够得到20个样本。考虑二维，两特征依旧在范围[0, 4]，平面面积为 5 x 5 = 25， 面密度如下：100 / 25 = 4, 同理D= 3时，则体密度为0.8。单位区域内的样本数量急剧下降，自然地超平面的划分在高维空间越容易，不过所带来的就是过拟合问题（高维空间的描述能力大大超越了低维，而实际上数据集是由低维空间产生的，因此高维过剩的力量只能用来描述噪声了，自然就过拟合）。
维度灾难有一篇很好的中文参考博文【机器学习中的维度灾难】，其中有一段解释如下：
图8用不同的方式解释上面的内容。假设我们只使用一个特征来训练分类器，1D特征值的范围限定在0到1之间，且每只猫和狗对应的特征值是唯一的。如果我们希望训练样本的特征值占特征值范围的20%，那么训练样本的数量就要达到总体样本数的20%。现在，如果增加第二个特征，也就是从直线变为平面2D特征空间，这种情况下，如果要覆盖特征值范围的20%，那么训练样本数量就要达到总体样本数的45%（0.45*0.45=0.2）。而在3D空间中，如果要覆盖特征值范围的20%，就需要训练样本数量达到总体样本数的58%（0.58*0.58*0.58=0.2）。
如果增加特征维度，为了覆盖同样的特征值范围、防止过拟合，那么所需的训练样本数量就会成指数型增长。
实际上我并没有理解为什么所占数据集在二维情况下就从20%上升到了45%（该解释可能是错的）。这里给一波我对此处产生维度灾难的解释：
在石油例子中PRML中提到了一个结论：”x”附近的点对”x”的预测有着至关重要的影响，所以我们考虑”x”的邻近区域，并以投票的形式来决定”x”的类别，不过为了防止过拟合，我们希望这个邻近区域在一定范围内能够覆盖尽可能多样本，比如每个邻近区域占样本的20%，这样以这20%的样本进行投票还是比较可靠的，为了让模型变现的更优，显然邻域也是越小越好。综上：邻域越小且占领样本数越多，模型则越优。
接着看上图，在一维情况下，假设以样本20%来进行投票，那么我们只需要让特征覆盖20%的范围即可。到了二维情况，为了还是拿20%的样本去决策该区域的类别，经过计算发现特征值增长到了0.45（0.45 * 0.45 = 0.2），同理到了三维，则需要覆盖0.58的特征范围。我去，取20%样本去决策是为了防止过拟合，结果随着维数的上升，特征范围几乎要覆盖整个区域，考虑
为了区域不重叠才有了PRML中的单元格划分，但是同样的划分，在高维为了弥补过拟合，则需要在该区域填充更多的数据才行。
PRML举了个3单元格，D = 1， 2， 3的情形，如下：
再来谈谈1.1中提到的多项式拟合问题，在D个维度下，对应多项式阶数M = 3的式子如下：
可以得出，当M = 3固定不变时，能够得到系数的个数为：
很奇怪，PRML突然举了一个在高维空间球体比的例子，只是为了说明我们在低维空间的直觉在高维空间时不一定起作用。比如在D维下，关于一个半径为r的球体”体积”如下：
因为二维球面积为：
假设在高维情况下，
神奇的事情发生了，即时
这的确和我们的直觉有所出入，不过为何高维就一定满足这式子呢？
求解释。
实际上关于超球体在球面的体积有着很重要的意义，常见的分类器如KNN，SVM都是基于距离度量来实现的。但在高维，我们发现超球的体积大部分分布在薄球面上，（体积可以理解为数据可以分布到的地方），那么显然由于数据聚集在一块，距离度量将接近于0，这就意味着基于距离度量的分类器在高维不再起作用。
PRML还列举了一个高斯分布在各种维度下的密度质量分布。基本思路如下：首先根据高斯分布能够得到各种维度下，在空间中的数据分布情况，比如一维是这样的：
二维是这样的：
接着考虑从原点出发，半径为r，邻域为
具体的求解过程如下：
最后PRML总结说：虽然维度灾难在模式识别应用中是一个重要的问题，但它并不能阻止我们寻找应用于高维空间的有效技术。原因如下：
- 真实的数据经常被限制在有着较低的有效维度的空间区域中，特别地，在⽬标值会发⽣重要变化的⽅向上也会有这种限制。（所以高维数据存在维度冗余，才有了降维技术的发展？）
- 真实数据通常⽐较光滑（⾄少局部上⽐较光滑），因此⼤多数情况下，对于输⼊变量的微⼩改变，⽬标值的改变也很⼩，因此对于新的输⼊变量，我们可以通过局部的类似于插值的技术来进⾏预测。（可这为什么就能够避免维度灾难问题呢？）
考虑制造业中的一个应用，照相机拍摄了传送带上的相同的平面物体，目标是判断它们的方向，但是采集过程中实际能够得到物体所有的行为信息，如位置，方向，像素灰度值，所以实际上，这些数据呈现在空间内是一种三维流形（什么玩意）。。。或者这么考虑，在一维上，我们行走只有一个方向前或者后，而在二维空间内，我们可以上下左右，移动的方向变多。在三维空间，我们还可以上天，所以自由度越多，我们越自由，选择越多样化。但问题输出可能只需要判断方向，与位置无关，这就很有意义了。（意义在哪呢！）大胆猜测一波，或许可以借用其他信息如物体占空间大小的比例来推断方向。