| 查看: 665 | 回复: 2 | |||
| 当前主题已经存档。 | |||
sunices木虫 (初入文坛)
|
[交流]
【讨论】欧式距离在很高维空间是否有维数灾难问题(太重要了)
|
||
|
我们知道维数灾难（Curse of Dimensionality）是说由于维数增加使得空间体积指数级增长所引起的问题。一个方法的性能如果受空间体积指数级增长的影响，则发生维数灾难。例如估计密度函数的邻域法，当维数较高时，在大部分邻域内是没有样本的，从而邻域法取不到样本。 （1）对于计算空间中两个点之间距离的欧式距离公式，其计算的欧式距离在很高维空间是否有维数灾难问题？ （2）当维数很高时，是否欧式距离测度将使得任两点间的距离趋向相等？ 此问题的重要性在于，广泛使用的欧式距离在高维空间若有维数灾难问题，那么现有的与欧式距离有关的大部分方法将在高维空间失效，不能使用！例如在做高维数据的聚类时就碰到这个问题，若此问题成立，则基于欧式距离的聚类方法都不能使用！ 那么如何分析这个问题？有什么可参考的文章？ 请大家指点！ |
回复此楼» 猜你喜欢
323求调剂
已经有6人回复
-
一志愿北京化工大学 070300 学硕 336分 求调剂
已经有4人回复
-
352求调剂
已经有3人回复
-
一志愿东华大学化学070300，求调剂
已经有8人回复
-
277材料科学与工程080500求调剂
已经有7人回复
-
317求调剂
已经有18人回复
-
293求调剂
已经有5人回复
-
280分求调剂 一志愿085802
已经有7人回复
-
0854电子信息求调剂
已经有3人回复
-
263求调剂
已经有4人回复
yalefield
金虫 (文坛精英)
老汉一枚
- 应助: 129 (高中生)
- 贵宾: 0.17
- 金币: 21238.9
- 散金: 3440
- 红花: 66
- 帖子: 12101
- 在线: 759.1小时
- 虫号: 96063
- 注册: 2005-10-07
- 专业: 高等教育学
- 管辖: 计算模拟
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖交流
无奈的云(金币+2):谢谢积极参与交流~ 2010-03-24 10:48
小木虫(金币+0.5):给个红包，谢谢回帖交流
无奈的云(金币+2):谢谢积极参与交流~ 2010-03-24 10:48
|
建议你了解一下核方法（Kernel method）和VC维（The VC dimension， Vapnik Chervonenkis dimension）。然后考虑用Support Vector Machine吧。 The VC dimension (for Vapnik Chervonenkis dimension) is a measure of the capacity of a classification algorithm. It is one of the core concepts in statistical learning theory. It was originally defined by Vladimir Vapnik and Alexey Chervonenkis. 在N个空间的超平面里，VC就是N+1。 VC维在有限的训练样本情况下，当样本数 n 固定时，此时学习机器的 VC 维越高学习机器的复杂性越高。VC 维反映了函数集的学习能力，VC 维越大则学习机器越复杂(容量越大)。 所谓的结构风险最小化就是在保证分类精度（经验风险）的同时，降低学习机器的 VC 维，可以使学习机器在整个样本集上的期望风险得到控制。 推广的界（经验风险和实际风险之间的关系，注意引入这个原因是什么？因为训练误差再小也就是在这个训练集合上，实际的推广能力不行就会引起过拟合问题还。 所以说要引入置信范围也就是经验误差和实际期望误差之间的关系）： 期望误差R(ω) ≤ Remp (ω)+ Φ（n/h） 注意Remp (ω)是经验误差也就是训练误差（线性中使得所有的都训练正确），Φ（n/h）是置信范围，它是和样本数和VC维有关的。 上式中置信范围Φ 随n/h增加，单调下降。即当n/h较小时，置信范围Φ 较大，用经验风险近似实际风险就存在较大的误差，因此，用采用经验风险最小化准则，取得的最优解可能具有较差的推广性； 如果样本数较多，n/h较大，则置 信范围就会很小，采用经验风险最小化准则，求得的最优解就接近实际的最优解。 可知影响期望风险上界的因子有两个方面： 首先是训练集的规模 n，其次是 VC 维 h。 可见，在保证分类精度（经验风险）的同时，降低学习机器的 VC 维，可以使学习机器在整个样本集上的期望风险得到控制，这就是结构风险最小化（Structure Risk Minimization，简称 SRM）的由来。 在有限的训练样本情况下，当样本数 n 固定时，此时学习机器的 VC 维越高(学习机器的复杂性越高)，则置信范围就越大，此时，真实风险与经验风险之间的差别就越大，这就是为什么会出现过学习现象的原因。机器学习过程不但 要使经验风险最小，还要使其 VC 维尽量小，以缩小置信范围，才能取得较小的实际风险，即对未来样本有较好的推广性，它与学习机器的 VC 维及训练样本数有关。 线性可分的问题就是满足最优分类面的面要求分类面不但能将两类样本正确分开（训练错误率为 0），而且要使两类的分类间隔最大（在 @ 间隔下，超平面集合的 VC 维 h 满足下面关系： h = f （1/@*@） 其中， f().是单调增函数，即 h 与@的平方成反比关系。因此，当训练样本给定时，分类间隔越大，则对应的分类超平面集合的 VC 维就越小。）。根据结构风险最小化原则，前者是保证经验风险（经验风险和期望风险依赖于学习机器函数族的选择）最小，而后者使分类间隔最大，导致 VC 维最小，实际上就是使推广性的界中的置信范围最小，从而达到使真实风险最小。注意：置信范围大说明真实风险和经验风险的差别较大。 总结： 训练样本在线性可分的情况下，全部样本能被正确地分类（就是 yi*(w*xi+b)）>=1的条件），即经验风险Remp 为 0 的前提下，通过对分类间隔最大化（Φ（w）＝(1/2)*w*w），使分类器获得最好的推广性能。 很多时候是线性不可分的啊，那么有什么区别？ 本质的区别就是不知道是否线性可分但是允许有错分的样本存在。正是由于允许存在错分样本，此时的软间隔分类超平面表示在剔除那些错分样本后最大分类间隔的超平面。这里就出现了新词：松驰因子。就是用来控制错分样本。 这样，经验风险就要跟松驰因子联系在一起了。而C就是松驰因子前面的系数，C>0 是一个自定义的惩罚因子，它控制对错分样本惩罚的程度，用来控制样本偏差与机器推广能力之间的折衷。c越小，惩罚越小，那么训练误差就越大，使得结构风险 也变大，而C 越大呢，惩罚就越大，对错分样本的约束程度就越大，但是这样会使得第二项置信范围的权重变大那么分类间隔的权重就相对变小了，系统的泛化能力就变差了。所以选择合适的C还是很有必要的。 选择核函数 核函数有很多种，如线性核、多项式核、Sigmoid 核和 RBF（Radial Basis function）核。本文选定 RBF 核为 SVM 的核函数（RBF 核K(x, y) = exp(－γ || x －y ||的平方),γ > 0）。因为RBF 核可以将样本映射到一个更高维的空间，可以处理当类标签（Class Labels）和特征之间的关系是非线性时的样例。Keerthi 等证明了一个有惩罚参数C 的线性核同有参数(C,γ )（其中C 为惩罚因子，γ 为核参数）的 RBF 核具有相同的性能。对某些参数，Sigmoid核同 RBF 核具有相似的性能。另外，RBF 核与多项式核相比具有参数少的优点。因为参数的个数直接影响到模型选择的复杂性。非常重要的一点是0< Kij ≤1与多项式核相反，核值可能趋向无限(γxi xj + r >1)或者0 < γxi xj + r <1，跨度非常大。而且，必须注意的是Sigmoid 核在某些参数下是不正确的（例如，没有两个向量的内积）。 用交叉验证找到最好的参数 C 和γ。 使用 RBF 核时，要考虑两个参数 C 和γ 。因为参数的选择并没有一定的先验知识，必须做某种类型的模型选择（参数搜索）。目的是确定好的(C,γ)使得分类器能正确的预测未知数据（即测试集数 据），有较高的分类精确率。值得注意的是得到高的训练正确率即是分类器预测类标签已知的训练数据的正确率）不能保证在测试集上具有高的预测精度。因此，通 常采用交叉验证方法提高预测精度。k 折交叉验证（k-fold cross validation） 是将训练集合分成 k 个大小相同的子集。其中一个子集用于测试，其它 k-1 个子集用于对分类器进行训练。这样，整个训练集中的每一个子集被预测一次，交叉验证的正确率是 k次正确分类数据百分比的平均值。它可以防止过拟合的问题。 [ Last edited by yalefield on 2010-3-24 at 10:39 ] |
2楼2010-03-24 10:37:46
sunices
木虫 (初入文坛)
- 应助: 0 (幼儿园)
- 金币: 2435.5
- 帖子: 33
- 在线: 52.5小时
- 虫号: 585515
- 注册: 2008-08-08
- 性别: GG
- 专业: 计算机应用技术
3楼2010-03-29 11:31:25
