KNN与维度灾难

---

现象：

分类器的准确度会随通道（特征）数增多而下降:

image.png

---

维数灾难与过拟合:

1. 假设猫和狗图片的数量是有限的(实际上也确实如此，样本数量总是有限的)

2. 使用单一特征准确度低：

   
   image.png

3. 使用二维特征：

   
   image.png

4. 从1维到3维，给我们的感觉是：维数越高，分类性能越优。

• 然而，当样本数稳定在十个的时候，在一维特征空间下，我们假设一个维度的宽度为5个单位，这样样本密度为10/5=2;在2维特征空间下，10个样本所分布的空间大小5*5=25，这样样本密度为10/25=0.4;在3维特征空间下，10个样本分布的空间大小为5*5*5=125，样本密度就为10/125=0.08

5. 假设样本是均匀分布:

• 如果我们的训练数据覆盖了取值范围的20%(0到0.2)，那么所使用的训练数据就占总样本量的20%。上升到二维情况下，覆盖二维特征空间20%的面积，则需要在每个维度上取得45%的取值范围。在三维情况下，要覆盖特征空间20%的体积，则需要在每个维度上取得58%的取值范围...在维度接近一定程度时，要取得同样的训练样本数量，则几乎要在每个维度上取得接近100%的取值范围，或者增加总样本数量，但样本数量也总是有限的。

image.png

过多的特征导致的过拟合现象：训练集上表现良好，但是对新数据缺乏泛化能力，因为数据增长跟不上样本空间的增长，难以表示全部样本空间的特征。

解决方案： 特征选择，只包含所有重要特征的特征子集。