专栏首页鸿的学习笔记分类问题中的维度诅咒(下)

分类问题中的维度诅咒(下)

换句话说,如果可用训练数据的数量是固定的,我们继续添加维度的话,则会发生过拟合。另一方面,如果我们不断增加维度,训练数据的数量需要快速增长以保持相同的覆盖,并避免过拟合。在上面的例子中,我们表明维度的诅咒引入了训练数据的稀疏性。我们使用的特征越多,数据越稀疏,使得对分类器参数(即,其判定边界)的精确估计变得更加困难。维度的诅咒的另一个效果是,这种稀疏性在搜索空间上不是均匀分布的。事实上,围绕原点(在超立方体的中心)的数据比搜索空间的角落中的数据稀疏得多。这可以理解如下:

设想一个表示2D特征空间的单位正方形。特征空间的平均值是该单位正方形的中心,并且距离该中心的单位距离内的所有点都在内切单位正方形的单位圆内。不在此单位圆内的训练样本会更接近搜索空间的角落而不是其中心。这些样本难以分类,因为它们的特征值极大地不同(例如,在单位正方形的对角的样本)。因此,如果大多数样品落入内切单位圆内,则分类更容易,如图9所示:

Figure 9.Training samples that falloutside the unit circle are in the corners of the feature space and are moredifficult to classify than samples near the center of the feature space.

一个有趣的问题是,当我们增加特征空间的维度时,圆(超球面)的体积相对于正方形(超立方体)的体积如何变化。维度d的单位超立方体的体积总是1 ^ d = 1。维度d和半径0.5的刻入超球面的体积可以计算为:

(1)

图10显示了随着维度的增加,超立方体体积的改变:

Figure 10. The volume of the hyperspheretends to zero as the dimensionality increases.

这表明超球面的体积趋向于零,因为维度趋于无穷大,而周围超立方体的体积保持恒定。这种令人惊讶且违背直觉的观察部分地解释了与分类中的维度的诅咒相关联的问题:在高维空间中,大多数训练数据驻留在限定特征空间的超立方体的角落中。如前所述,特征空间的角落中的实例比围绕超球面的质心的实例更难以分类。这由图11示出,其示出了2D单位正方形,3D单位立方体以及具有2 ^ 8 = 256个角的8D超立方体的创造性可视化:

Figure 11. As the dimensionalityincreases, a larger percentage of the training data resides in the corners ofthe feature space.

这表明超球体的体积作为维度时趋于零。对于8维超立方体,约98%的数据集中在其256个角。结果,当特征空间的维度变为无穷大时,从采样点到质心的最小和最大欧几里德距离的差和最小距离本身的比率趋于为零:

(2)

因此,距离测量开始丧失其在高维空间中测量差异的有效性。由于分类器取决于这些距离度量(例如欧几里德距离,马哈拉诺比斯距离,曼哈顿距离),所以在较少维度空间中分类通常更容易,其中较少特征用于描述感兴趣对象。类似地,高斯似然在高维空间中变得平坦和长尾分布,使得最小和最大似然之间的差的比率和最小似然本身趋于零。

如何避免维度的诅咒

图1表明,当问题的维数变得太大时,分类器的性能会降低。那么“太大”这个意味着什么呢,以及如何避免过拟合。遗憾的是,没有固定的规则来定义在分类问题中应该使用多少个特征。事实上,这取决于可用的训练数据的量,决策边界的复杂性以及所使用的分类器的类型。

如果理论上有无限数量的训练样本可用,则维度的诅咒不适用,并且我们可以简单地使用无限数量的特征来获得完美分类。训练数据的大小越小,应使用的特征越少。如果N个训练样本足以覆盖单位间隔大小的1D特征空间,则需要N ^ 2个样本来覆盖具有相同密度的2D特征空间,并且在3D特征空间中需要N ^ 3个样本。换句话说,所需的训练实例的数量随着所使用的维度的数量呈指数增长。

此外,倾向于非常精确地建模非线性决策边界的分类器(例如神经网络,KNN分类器,决策树)不能很好地泛化,并且很容易过拟合。因此,当使用这些分类器时,维度应保持相对低。如果使用容易泛化的分类器(例如朴素贝叶斯分类器,线性分类器),则所使用的特征的数量可以更高,因为分类器本身不具有表现力。图6显示出了在高维空间中使用简单分类器模型对应于在较低维空间中使用复杂分类器模型。

因此,当在高维空间中使用相对较少的参数时以及当在较低维空间中使用许多参数时都会发生过拟合。作为示例,考虑由其平均和协方差矩阵参数化的高斯密度函数。假设我们在3D空间中操作,使得协方差矩阵是由6个唯一元素(对角线上的3个方差和非对角线上的3个协方差)组成的3×3对称矩阵。与分布的3D均值一起,这意味着我们需要基于我们的训练数据估计9个参数,以获得表示我们的数据的可能性的高斯密度。在1D情况下,仅需要估计2个参数(平均值和方差),而在2D情况下需要5个参数(2D平均值,两个方差和协方差)。再次,我们可以看到要估计的参数的数量与维数的二次方增长。

在前面的文章中,我们表明如果预估计参数的数量会增加(并且如果预估偏差和训练数据的量保持恒定),则参数预估方差增加。这意味着如果维度上升,由于方差的增加,我们的参数预估质量会降低。分类器方差的增加对应于过拟合。

另一个有趣的问题是应该使用哪些特征。给定一组N个特征;我们如何选择M个特征的最佳子集,使得M <N?一种方法是在图1所示的曲线中搜索最优。由于对所有特征的所有可能组合训练和测试分类器通常是难以处理的,因此存在尝试以不同方式找到该最优的若干方法。这些方法被称为特征选择算法,并且通常使用启发法(贪婪法,最佳优先方法等)来定位特征的最优数目和组合。

另一种方法是通过一组M个特征来替换N个特征的集合,每个特征是原始特征值的组合。试图找到原始特征的最佳线性或非线性组合以减少最终问题的维度的算法被称为特征提取方法。产生原始N个特征的不相关的线性组合的公知的维数降低技术是主成分分析(PCA)。 PCA试图找到较低维度的线性子空间,使得保持原始数据的最大方差。然而,请注意,数据的最大方差不一定代表最具辨别力的信息。

最后,用于在分类器训练期间检测和避免过拟合技术是交叉验证。交叉验证方法将原始训练数据分成一个或多个训练子集。在分类器训练期间,使用一个子集来测试所得分类器的准确性和精度,而其他子集用于参数估计。如果用于训练的子集上的分类结果与用于测试的子集的结果大不相同,则过拟合正在发挥作用。如果只有有限数量的训练数据可用,则可以使用几种类型的交叉验证,例如k折交叉验证和留一法。

结论

在本文中,我们讨论了特征选择,特征提取和交叉验证的重要性,以避免由于维度的诅咒而导致过拟合。

本文分享自微信公众号 - 鸿的学习笔记(shujuxuexizhilu),作者:鸿

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2016-11-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 分类问题中维度诅咒(上)

    在本文中,我们将讨论所谓的“维度的诅咒”,并解释为什么在设计分类器时很重要。在以下部分中,我将提供对这个概念的直观解释。

    哒呵呵
  • Understanding Convolution in Deep Learning(一)

    卷积可能是目前深度学习中最重要的概念了。卷积和卷积网络是引发深度学习去完成几乎任何机器学习任务的最前沿地概念。但是什么使卷积这么强大?它是如何工作的?在这篇博客...

    哒呵呵
  • python的上下文管理器

    上下文管理器其实是with语句,这是为了简化try/finally模式,这可以保证一段代码在运行完之后,即使出现错误也能正确的运行。finally的语句用于释放...

    哒呵呵
  • matlab学习笔记11_3 高维数组处理 filp, shiftdim, size, permute, ipermute

    本文为matlab自学笔记的一部分,之所以学习matlab是因为其真的是人工智能无论是神经网络还是智能计算中日常使用的,非常重要的软件。也许最近其带来的一...

    DrawSky
  • iOS常用代码段

    控制器中代码设置 > storybord设置 > 全局设置 优先级高的会覆盖优先级低的配置,比如storybord中的设置了navigationbar的样式 那...

    剑行者
  • 小数据:理论和架构 | TW洞见

    今日洞见 文章作者及图片来自ThoughtWorks:熊节。 本文所有内容,包括文字、图片和音视频资料,版权均属ThoughtWorks公司所有,任何媒体、网站...

    ThoughtWorks
  • Roslyn 如何给每个平台设置 PlatformTarget 属性

    在使用 csproj 格式,如果需要给不同的平台设置 PlatformTarget 对应平台的值,需要写比较多的代码,本文告诉大家一个简便的方法

    林德熙
  • Kmeans聚类算法

    在确定K的时候,可以测试10个不同的聚类中心,然后绘制K与误差平方和的曲线图,找到曲线的拐点,即是合适的K值。

    故事尾音
  • 10分钟教你用python下载和拼接微信好友头像图片

    相信微信大家是用得再多也不过了。那么,对于python+微信,又能玩出什么新的花样呢?下面小编就给大家带来一个好玩的东西。用python下载所有的微信好友的头像...

    短短的路走走停停
  • 【每周一库】- Rayon 数据并行计算库

    Rayon 是一个Rust的数据并行计算库。它非常轻巧,可以轻松地将顺序计算转换为并行计算。同时保证不会有数据争用情况出现。

    MikeLoveRust

扫码关注云+社区

领取腾讯云代金券