什么是维数灾难?

SVM第一话(回复 SVM1 查看)里提到了“维数灾难”,什么是维数灾难呢?

维数灾难(英语:curseof dimensionality,又名维度的诅咒)是一个最早由理查德·贝尔曼(Richard E. Bellman)在考虑动态优化问题时首次提出来的术语,用来描述当(数学)空间维度增加时,分析和组织高维空间(通常有成百上千维),因体积指数增加而遇到各种问题场景。这样的难题在低维空间中不会遇到,如物理空间通常只用三维来建模。

数据的维数越高,会引发灾难,首先是计算量巨大,不用多说。其次,对于已知样本数目,存在一个特征数目的最大值,当实际使用的特征数目超过这个最大值时,分类器的性能不是得到改善,而是退化。因为在高维空间中,所有的数据都很稀疏,于是导致在相似度度量上,距离计算上都会出现很大的偏差,因为平时我们采用的算法也都会变得很低效。因此,多于多维数据,我们通常采用降维处理(比如主成分,你知道主成分吗?),而SVM机智的采用了核函数技术。

举例来说,100个平均分布的点能把一个单位区间以每个点距离不超过0.01采样;而当维度增加到10后,如果以相邻点距离不超过0.01小方格采样一单位超正方体,则需要1020 个采样点:所以,这个10维的超正方体也可以说是比单位区间大1018倍(这个是Richard Bellman所举的例子)。

在很多领域中,如采样、组合数学、机器学习和数据挖掘都有提及到这个名字的现象。这些问题的共同特色是当维数提高时,空间的体积提高太快,因而可用数据变得很稀疏。稀疏性对于任何要求有统计学意义的方法而言都是一个问题,为了获得在统计学上正确并且有可靠的结果,用来支撑这一结果所需要的数据量通常随着维数的提高而呈指数级增长。而且,在组织和搜索数据时也有赖于检测对象区域,这些区域中的对象通过相似度属性而形成分组。然而在高维空间中,所有的数据都很稀疏,从很多角度看都不相似,因而平常使用的数据组织策略变得极其低效。

“维数灾难”通常是用来作为不要处理高维数据的无力借口。然而,学术界一直都对其有兴趣,而且在继续研究。另一方面,也由于本征维度的存在,其概念是指任意低维数据空间可简单地通过增加空余(如复制)或随机维将其转换至更高维空间中,相反地,许多高维空间中的数据集也可削减至低维空间数据,而不必丢失重要信息。这一点也通过众多降维方法的有效性反映出来,如应用广泛的主成分分析方法。针对距离函数和最近邻搜索,当前的研究也表明除非其中存在太多不相关的维度,带有维数灾难特色的数据集依然可以处理,因为相关维度实际上可使得许多问题(如聚类分析)变得更加容易。

原文发布于微信公众号 - 数说工作室(shushuojun)

原文发表时间:2014-12-04

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习算法与Python学习

称霸Kaggle的十大深度学习技巧

在各种Kaggle竞赛的排行榜上,都有不少刚刚进入深度学习领域的程序员,其中大部分有一个共同点:

1372
来自专栏机器之心

业界 | 如何达到Kaggle竞赛top 2%?这里有一篇特征探索经验帖

在数值数据上构建任意监督学习模型的一个重要方面是理解特征。查看模型的部分依赖图可帮助理解任意特征对模型输出的影响。

1033
来自专栏AI派

业界 | 如何达到Kaggle竞赛top 2%?这里有一篇特征探索经验帖

在数值数据上构建任意监督学习模型的一个重要方面是理解特征。查看模型的部分依赖图可帮助理解任意特征对模型输出的影响。

983
来自专栏磐创AI技术团队的专栏

十大预训练模型,助力入门深度学习(第1部分 - 计算机视觉)

对于希望运用某个现有框架来解决自己的任务的人来说,预训练模型可以帮你快速实现这一点。通常来说,由于时间限制或硬件水平限制大家往往并不会从头开始构建并训练模型,这...

1393
来自专栏数据派THU

一文助你解决90%的自然语言处理问题(附代码)

作者:Emmanuel Ameisen 来源:机器之心 本文为大家解析了人工智能领域中的自然语言如何处理。 自然语言处理(NLP)与计算机视觉(CV)一样,是...

3603
来自专栏AI科技大本营的专栏

八大深度学习最佳实践

翻译 | AI科技大本营 参与 | 刘畅 [AI 科技大本营导读]2017年,许多的人工智能算法得到了实践和应用。名博Hack Noon作者 Brian Muh...

35812
来自专栏鸿的学习笔记

Yoshua Bengio关于深度学习结构的综述

深度学习方法旨在学习特征层次,其具有由较低层特征的组合形成的较高层级的特征。在多个抽象级别自动学习特征允许系统去学习将输入直接从数据映射到输出的复杂函数,而不完...

641
来自专栏IT派

机器学习新手常犯的6大错误

在刚入门的时候,均方误差作为损失函数是很好的默认选择。但是当需要处理现实问题的时候,这种未经专门设计的损失函数很少能给出最优解。

1070
来自专栏机器之心

如何解决90%的自然语言处理问题:分步指南奉上

3808
来自专栏量子位

称霸Kaggle的十大深度学习技巧

在各种Kaggle竞赛的排行榜上,都有不少刚刚进入深度学习领域的程序员,其中大部分有一个共同点:

1581

扫码关注云+社区

领取腾讯云代金券