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

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、n/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

7、ger 2006特征选择n联合选择减量法nF =全体特征n计算在F上的分类性能nF = F -ff可以用评价准则选择，也可以遍历所有特征n计算在F 上的分类性能n如果分类性能不降低： F=F ，循环否则结束特征选择n联合选择增量法nF =f1n计算在F上的分类性能nF = F +f 2f1、 f2可以用评价准则选择，也可以遍历所有特征n计算在F 上的分类性能n如果分类性能增加： F=F ，循环否则结束特征选择n联合选择增/减量法优缺点n复杂度关于维数为 或选单个特征采用评价准则排序的方式为一次选单个特征采用测试全部特征的方式为二次n本质上是贪心算法某些组合无法遍历可能陷入局部极值 NO2NO特

8、征选择n联合选择全组合遍历nNP难NO 2Kohavi-John, 1997特征选择n联合选择模拟退火/遗传算法（通用的优化算法）n随机生成一批解可以用梯度下降法迭代到局部极值n用现有解通过操作合成新的解不要求合成操作具有任何理论依据好的合成操作将极大提高解题效率n对新生成的解进行生存选择同上，并可用梯度下降法迭代到局部极值n迭代直到收敛或已支付预期的计算量特征选择n模拟退火/遗传算法理论依据n梯度下降法（爬山法）往往陷入局部极值n非梯度下降手段使解“跳”到爬山法可求解范围不同的非梯度下降手段产生不同的算法梯度下降法可求解的范围局部极值特征选择n模拟退火/遗传算法应用实例nN皇后问题求解n旅行

9、商(TSP)问题求解n很多类似NP完全和NP难问题n适合于解可能有大量解，但解的比例很小，而整个解空间巨大的问题特征选择n特征的相关性问题例：直方图通过特征选择算法不可能消除相关特征的相关性Guyon-Elisseeff, JMLR 2004; Springer 2006iiH1niHHHH,.,.,1niinHH11Hn可以由前n-1维完全预测出Hn不能告诉我们任何额外信息可预测则不携带信息特征选择n相关特征的选择把所有特征的各种可能变换、组合加入特征矢量在这个巨大的特征矢量上进行特征选择n比NP难还难的问题特征的函数组合是无限的核函数（kernel functions）类似于利用原有特征构

10、造各种新特征n仅哲学上类似，并无数学依据变换降维特征降维n主分量分析(PCA: Principle Component Analysis)在特征空间，如果特征维之间有相关性，则样本将分布在较低维的(高维)(曲)面上特征降维n主分量分析线性变换iiiTHaHaz111niHHHH,.,.,1原始特征矢量：主分量：11111,.,.,niaaaa “轴”： 11varmaxarg1zaa111aaTHazTkk kakzakvarmaxargak垂直于所有前面的“轴”特征降维n主分量分析 11,11,11,11,1121211varSaaSaaHHHHaaHHaaHHaazzzTjiijjijij

11、ijijijijijijijiji协方差矩阵如何求极值： 111varSaazT111aaT约束条件：特征降维n主分量分析Lagrange乘数法11111aaSaaTT目标函数约束条件求导，导数为0处为极值011 aSa01aISa1是S的最大特征值对应的特征矢量特征降维n主分量分析同理可证：所有主分量对应的“轴”都是S的特征矢量，相应的特征值为其方差HAzT正交阵A可通过KL变换从协方差矩阵S求特征降维n主分量分析如果H是线性相关的：S是降秩的n特征矢量个数小于维数降维无信息损失如果H各维相关性大，但没有达到完全相关n有很小的特征值对应的特征矢量可以去除n降维，有信息损失n相关但非线性相关？目前还没有好的方法特征降维n多模特征的降维同质特征可以方便地使用PCAn同质特征内部是已经归一化的n例：直方图，像素值，等等异质特征不能简单地进行PCAn不同的归一化导致不同的主分量n异质特征之间没有归一化例：颜色直方图和“粗糙度”如何归一化？特征降维n多模特征的降维分组降维，组