24小时热门版块排行榜

返回列表

当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

sunices

木虫 (初入文坛)

应助: 0 (幼儿园)
金币: 2435.5
帖子: 33
在线: 52.5小时
虫号: 585515
注册: 2008-08-08
性别: GG
专业: 计算机应用技术

[交流] 【求助】欧式距离在很高维空间是否有维数灾难问题(太重要了)

我们知道维数灾难（Curse of Dimensionality）是说由于维数增加使得空间体积指数级增长所引起的问题。一个方法的性能如果受空间体积指数级增长的影响，则发生维数灾难。例如估计密度函数的邻域法，当维数较高时，在大部分邻域内是没有样本的，从而邻域法取不到样本。
（1）对于计算空间中两个点之间距离的欧式距离公式，其计算的欧式距离在很高维空间是否有维数灾难问题？
（2）当维数很高时，是否欧式距离测度将使得任两点间的距离趋向相等？
此问题的重要性在于，广泛使用的欧式距离在高维空间若有维数灾难问题，那么现有的与欧式距离有关的大部分方法将在高维空间失效，不能使用！例如在做高维数据的聚类时就碰到这个问题，若此问题成立，则基于欧式距离的聚类方法都不能使用！
那么如何分析这个问题？有什么可参考的文章？

请大家指点！

看了大家的回复，这里举个例子以更好地说明：
数据(1,0)和(0,1)是2维的，放在平面上就是2个点，可以计算这2个点之间的欧式距离为根号2；数据(1,0,1)和(0,1,0)是3维的，可在3维空间中表示这2个点，可以计算这2个点之间的欧式距离为根号3；这种低维情况没有维数灾难问题。那么，若数据(1,0,1,0,1,0,...)和(0,1,0,1,0,1,...)是例如1万或1亿维的（生物学中的基因表达数据就有上万维的数据），就要考虑是否有维数灾难问题。此时，就需要知道上述（1）和（2）的问题是否成立。

[ Last edited by sunices on 2010-4-1 at 08:39 ]

回复此楼

» 猜你喜欢

1楼 2010-03-27 10:08:45

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

ilike6178

铁虫 (初入文坛)

应助: 0 (幼儿园)
金币: 159
帖子: 15
在线: 4.7小时
虫号: 685948
注册: 2009-01-01

★
sunices(金币+1):谢谢参与
sunices(金币+1):学习了:随机试验取样本，总会取到样本的 2010-05-30 17:14:58

虽然没有太看明白，但是随便聊聊吧．你说邻域法取不到样本，
那么样本空间是不是整个高维空间？我猜测你的意思是说，
除去一个零概率集，样本空间位于高维空间的(通常欧式空间测度下)
零测集上, e.g. 低维流形上，但这样也不对啊，随机试验取样本，
总会取到样本的, (什么叫样本, 随机试验可能的结果啊) ．除非你取样本
是人为在高维空间构造，因为样本空间零测，又不知道样本空间具体位置
所以很难取到．

关于两点距离是否会随着所考虑的外围欧式空间维数变化，像你说
的任意两点距离都趋于相等，(不知道我理解你的意思了么) 是不可能的．
我们假设 3 维空间内有两点，用这个 3 维坐标测量它们的距离; 再考虑
这两点所在的某个(随便选)平面，再在这个平面内测量它们的距离;
最后我们考虑两点所在的直线, ... 距离显然是一样的．

[ Last edited by ilike6178 on 2010-3-31 at 19:15 ]