机器学习与数据挖掘_特征选择与降维

《机器学习与数据挖掘_特征选择与降维》由会员分享，可在线阅读，更多相关《机器学习与数据挖掘_特征选择与降维（39页珍藏版）》请在文档大全上搜索。

1、机器学习与数据挖掘特征选择与特征降维维数灾难nCurse of Dimensionality随着维数的增加，特征空间的体积指数增加，从而导致各方面的成本指数增加n样本数量n存储空间n计算量nn图灵可计算问题：多项式复杂度涉及高维空间的算法是不可计算的！？维数灾难n维数灾难的几个表现空间采样011维：42维：4*4=1610维：410=1048576Monte Carlo: 4016010M维数灾难n维数灾难的几个表现索引困难0111立方体体积球体积1比例100%/478.5%11055 . 0! 50.25%维数灾难n维数灾难的几个表现样本稀疏n总样本：1000n每维划分：41维：1000/4

2、 = 250 样本/区间2维：1000/(4*4)= 62.5 样本/区间10维：1000/(410)= 0.001 样本/区间维数灾难n维数灾难的几个表现噪声影响n特征空间：101维n正负样本在第一维的距离：1n样本在其余维的噪声：10%n“噪声距离”：n即使噪声只有10%，高维空间的“噪声距离”足以掩盖正负样本的本质区别11 . 01002维数灾难n高维空间的奇异特性克莱因瓶Klein bottle莫比乌斯带Mbius stripN维单位超球的表面积(http:/ Yang and Jan Pedersen“A comparative study on feature selection

3、in text categorization”.维数灾难n特征降维的途径去除无用特征n特征的必要性：不必要的特征对训练无用n特征选择去除相关分量n特征的相关性：相关的多个特征可以变换成较少的不相关分量n特征变换/特征降维特征选择n从整个特征集中选择最有效的子集如何评价特征“有效性”？n互信息量， 测试，如何决定阈值？n指定维数n指定“有效性”指标n指定性能n增量式、减量式性能评价2x特征选择n特征有效性评价从概率论的角度n协方差两个随机变量不相关：协方差为0随机变量相关度与协方差正相关问题：协方差是两个变量的总方差n如果某变量方差大，则协方差也大 YEYXEXEYXiii,cov特征目标函数特

4、征选择n特征有效性评价从概率论的角度n相关系数（归一化协方差）值域范围：-1, +1绝对值越大，相关性越大n一般使用其平方作为特征选择指标 YXYXiii,cov标准差特征选择n特征有效性评价从数理统计的角度（假设检验）n 测试nT测试n自己翻课本查公式n与相关系数在理论上非常接近，但更偏重于有限样本下的估计2x特征选择n特征有效性评价从信息论角度n把机器学习过程看做通信特征是编码目标函数是信息特征包含的有关目标函数的信息越多，则从特征解出的信息就越多完全编码目标函数需要的额外特征就越少各种信息量/熵衡量指标特征选择n特征有效性评价从信息论角度n条件熵与“相关性”负相关n信息增益n相对信息增益

5、nhttp:/www.autonlab.org/tutorials/infogain.htmliXYH| iiXYHYHXYIG| YHXYHYHXYRIGii/|特征选择n特征有效性评价从信息论角度n互信息量(Mutual Information)KL-距离 YPXPYXPKLdYdXYPXPYXPYXPiMIiiiiii|,log,特征选择n特征有效性评价IR领域的度量n（逆）文档词频(inverse document frequency)ttDDidflog总文档数总文档数包含词包含词(特征特征)t的文档数的文档数所有文档都出现的词(如“的”)：D=Dt idft = log(1) =

6、0在1%文档中出现的词：D/Dt = 100 idft = log(100) 0特征选择n特征有效性评价IR领域的度量n词强度(term strength)已知一个词(特征)在某文档(实例)中出现，该词在同类(目标函数值相同)文档中出现的概率为词强度 jyYiyYdtdtPts|特征选择n特征有效性评价学习相关的度量n分类准确率用单一维特征进行分类训练，某种分类准确率指标作为特征的有效性度量复杂度较大不一定有合适的准确率指标特征选择n选择方法独立选择n指定维数如何确定？n指定阈值如何确定？n特征的组合可能比单个的特征有效联合选择Guyon-Elisseeff, JMLR 2004; Sprin