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

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

导论:

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

考虑一个例子,其中我们有一组图像,每个描绘了一只猫或狗。我们想创建一个能够自动区分狗和猫的分类器。为此,我们首先需要考虑通过数字表示的每个对象类的描述符,例如数学算法(即分类器),可以使用这些数字来识别对象。例如,我们可以认为猫和狗的颜色通常不同。鉴别这两个类的可能的描述符可以包括三个数字; 所考虑的图像的平均红色,平均绿色和平均蓝色。例如,一个简单的线性分类器可以线性组合这些特征来决定类标签:

If 0.5*red + 0.3*green + 0.2*blue > 0.6 : return cat; else return dog;

然而,这三个描述颜色的数字,所谓特征,显然不足以获得完美的分类。因此,我们可以决定添加一些描述图像纹理的特征,例如通过计算X和Y方向上的平均边缘或梯度强度。我们现在有5个特征了,组合在一起可能被分类算法用于区分猫和狗。

为了获得更准确的分类,我们可以基于颜色或纹理的直方图,统计矩等添加更多的特征。也许我们可以通过认真定义几百个这些特征来获得完美的分类?这个问题的答案听起来有点反直觉:不,我们不能!事实上,在某一点之后,通过添加新特征来增加问题的维度实际上会降低我们的分类器的性能。这由图1示出,并且通常被称为“维度的诅咒”。

Figure 1.随着维数的增加,分类器的性能随之增加,直到达到最佳数量的特征。进一步增加维度而不增加训练样本的数量导致分类器性能的降低。

维度的诅咒和过拟合

在前面介绍的猫和狗的例子中,让我们假设有无限数量的猫和狗住在我们的星球上。然而,由于我们有限的时间和处理能力,我们只能够获得10张猫和狗的图片。分类的最终目标是训练基于这10个训练实例的分类器,能够正确地分类无限数量的狗和猫,这些我们没有任何信息的实例。现在让我们使用一个简单的线性分类器,并尝试获得完美的分类。我们可以从一个特征开始,例如,图像中的平均“红色”:

Figure 2. A single feature does notresult in a perfect separation of our training data.

图2显示,如果只使用一个特征,我们不能获得完美的分类结果。因此,我们可能会决定添加其他特征,例如,图像中的平均“绿色”:

Figure 3.Adding a second feature stilldoes not result in a linearly separable classification problem: No single linecan separate all cats from all dogs in this example.

最后我们决定添加第三个特征,例如,平均“蓝色”因此构造了一个三维特征空间:

Figure 4. Adding a third featureresults in a linearly separable classification problem in our example. A planeexists that perfectly separates dogs from cats.

在三维特征空间中,我们现在可以找到一个将狗与猫完美分开的平面。这意味着三个特征的线性组合可以用于在我们的10个图像的训练数据上获得完美的分类结果:

Figure 5. The more features we use, thehigher the likelihood that we can successfully separate the classes perfectly.

这似乎暗示增加特征的数量直到获得完美的分类结果是训练分类器的最佳方式,而在图1所示的引言中,我们认为这种情况不行。但是,请注意,当我们增加问题的维数时,训练样本的密度是如何呈指数下降。

在1D情况下(图2),10个训练实例覆盖了完整的1D特征空间,其宽度为5个单位间隔。因此,在1D情况下,样品密度为10/5 = 2个样品/间隔。在2D情况下(图3),我们仍然有10个训练实例,我们现在覆盖了一个面积为5×5 = 25个单位正方形的2D特征。因此,在2D情况下,样品密度为10/25 = 0.4样品/间隔。最后,在3D情况下,10个样本必须覆盖5×5×5 = 125个单位立方体的特征空间。因此,在3D情况下,样品密度为10/125 = 0.08个样品/间隔。

如果我们继续添加特征,特征空间的维度随之增长,并且变得更稀疏。由于这种稀疏性,变得更容易找到可分离的超平面,因为当特征的数目变得无限大时,训练样本位于最佳超平面的错误方向的可能性变得无限小。然而,如果我们将高维分类结果投影回较低维的空间,则与该方法相关联的问题的严重性变得更明显:

Figure 7. Although the training data isnot classified perfectly, this classifier achieves better results on unseendata than the one from figure 5.

虽然图7所示的具有决策边界的简单线性分类器看起来比图5中的非线性分类器更差,但是这种简单分类器更好地泛化了不可见的数据,因为它没有学习仅在我们的训练数据中的特定异常。换句话说,通过使用较少的特征,避免了维度的诅咒,使得分类器没有过拟合训练数据。

图8以不同的方式示出了上述内容。假设我们想训练一个分类器,只使用一个单一的特征,其值的范围从0到1。让我们假设这个特征对于每个猫和狗是唯一的。如果我们希望我们的训练数据覆盖这个范围的20%,那么所需的训练数据量是猫和狗的完整数量的20%。现在,如果我们添加另一个特征,产生了2D特征空间,于是事情改变了;为了覆盖2D特征范围的20%,我们现在需要在每个维度上获得45%的猫和狗的完整群体(0.45 ^ 2 = 0.2)。在3D情况下,这变得更糟:为了覆盖3D特征范围的20%,我们需要在每个维度中获得58%的群体(0.58 ^ 3 = 0.2)。

Figure 8. The amount of training dataneeded to cover 20% of the feature range grows exponentially with the number ofdimensions.

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    换句话说,如果可用训练数据的数量是固定的,我们继续添加维度的话,则会发生过拟合。另一方面,如果我们不断增加维度,训练数据的数量需要快速增长以保持相同的覆盖,并避...

    哒呵呵
  • 大数据概览系列(一)

    就像互联网一样,大数据是我们今天生活的一部分。从搜索,在线购物,视频点播,到网上约会,大数据总是幕后的重要角色。有些人声称,物联网(IoT)将会接管大数据作为最...

    哒呵呵
  • Procella 数据库的简单介绍

    最近看到了一个很有趣的数据库 Procella ,它的架构图就和当初亚马逊公司发布的数据库论文 Aurora 里面的一样,一眼就吸引住我了。

    哒呵呵
  • 「知识图谱」领域近期值得读的 6 篇顶会论文

    论文 | Hike: A Hybrid Human-Machine Method for Entity Alignmentin Large-Scale Know...

    华章科技
  • 用innodb_ruby分析InnoDB的页管理

    我创建了一个空表(模式无关紧要)来说明InnoDB页面管理结构的“最小”状态。space-page-type-regions模式将汇总同一页面类型的所有相邻区域...

    冬天里的懒猫
  • 【陆勤阅读】怎样收集智能数据?

    快餐内容,约会,甚至领导力。你到处可以听到这些营销流行语。然而这所有一切的罪魁祸首也许就是——大数据。 每个人都听到许多有关大数据的东西。不论是通过文章、博客还...

    陆勤_数据人网
  • 这7个不可错过的数据可视化技术,能让地图惊喜跃动

    ▍Choropleths 如果你想要呈现基于地域的数据信息,那么choropleth一定是你的不二选择。通过对于不同区域对应的数值着色,可以十分方便的呈现出某一...

    企鹅号小编
  • Js文件异步加载

    浏览器中渲染引擎与Js脚本引擎是互斥的,在浏览器开始渲染页面时,如果遇到<script>标签,会停止渲染当前页面,也就是说在脚本加载与执行的过程中会阻塞页面的渲...

    WindrunnerMax
  • 2018年智能机器人技术综合实训专题二控制算法

    第8章,在Matlab和Android上运行ROS,此部分延续专题一,很多算法可以在Matlab中找到,

    zhangrelay
  • [jQuery笔记] 小图片切换

    行 者

扫码关注云+社区

领取腾讯云代金券