机器学习与数据挖掘特征选择与降维分析ppt课件.ppt
机器学习与数据挖掘,特征选择与特征降维,维数灾难,Curse of Dimensionality随着维数的增加，特征空间的体积指数增加，从而导致各方面的成本指数增加样本数量存储空间计算量图灵可计算问题：多项式复杂度涉及高维空间的算法是不可计算的！？,维数灾难,维数灾难的几个表现空间采样,0,1,1维：4,2维：4*4=16,10维：410=1048576,Monte Carlo:,40,160,10M,维数灾难,维数灾难的几个表现索引困难,0,1,1,1,立方体体积,球体积,1,比例,100%,/4,78.5%,1,0.25%,维数灾难,维数灾难的几个表现样本稀疏总样本：1000每维划分：41维：1000/4 = 250 样本/区间2维：1000/(4*4)= 62.5 样本/区间10维：1000/(410)= 0.001 样本/区间,维数灾难,维数灾难的几个表现噪声影响特征空间：101维正负样本在第一维的距离：1样本在其余维的噪声：10%“噪声距离”：即使噪声只有10%，高维空间的“噪声距离”足以掩盖正负样本的本质区别,维数灾难,高维空间的奇异特性,克莱因瓶Klein bottle,莫比乌斯带Mbius strip,N维单位超球的表面积(http:/,维数灾难,数学理论偏好较低维数的空间要在特征空间进行合理密度的采样，特征维数超过5都是非常困难的实际问题偏好较高维数的空间问题的复杂性特征的完备性特征降维,维数灾难,更多的特征可能导致分类性能反而下降,Yiming Yang and Jan Pedersen“A comparative study on feature selection in text categorization”.,维数灾难,特征降维的途径去除无用特征特征的必要性：不必要的特征对训练无用特征选择去除相关分量特征的相关性：相关的多个特征可以变换成较少的不相关分量特征变换/特征降维,特征选择,从整个特征集中选择最有效的子集如何评价特征“有效性”？互信息量， 测试，如何决定阈值？指定维数指定“有效性”指标指定性能增量式、减量式性能评价,特征选择,特征有效性评价从概率论的角度协方差两个随机变量不相关：协方差为0随机变量相关度与协方差正相关问题：协方差是两个变量的总方差如果某变量方差大，则协方差也大,特征,目标函数,特征选择,特征有效性评价从概率论的角度相关系数（归一化协方差）值域范围：-1, +1绝对值越大，相关性越大一般使用其平方作为特征选择指标,标准差,特征选择,特征有效性评价从数理统计的角度（假设检验） 测试T测试自己翻课本查公式与相关系数在理论上非常接近，但更偏重于有限样本下的估计,特征选择,特征有效性评价从信息论角度把机器学习过程看做通信特征是编码目标函数是信息特征包含的有关目标函数的信息越多，则从特征解出的信息就越多完全编码目标函数需要的额外特征就越少各种信息量/熵衡量指标,特征选择,特征有效性评价从信息论角度条件熵与“相关性”负相关信息增益相对信息增益http:/www.autonlab.org/tutorials/infogain.html,特征选择,特征有效性评价从信息论角度互信息量(Mutual Information)KL-距离,特征选择,特征有效性评价IR领域的度量（逆）文档词频(inverse document frequency),包含词(特征)t的文档数,所有文档都出现的词(如“的”)：D=Dt idft = log(1) = 0在1%文档中出现的词：D/Dt = 100 idft = log(100) 0,特征选择,特征有效性评价IR领域的度量词强度(term strength)已知一个词(特征)在某文档(实例)中出现，该词在同类(目标函数值相同)文档中出现的概率为词强度,特征选择,特征有效性评价学习相关的度量分类准确率用单一维特征进行分类训练，某种分类准确率指标作为特征的有效性度量复杂度较大不一定有合适的准确率指标,特征选择,选择方法独立选择指定维数如何确定？指定阈值如何确定？特征的组合可能比单个的特征有效联合选择,Guyon-Elisseeff, JMLR 2004; Springer 2006,特征选择,联合选择减量法F =全体特征计算在F上的分类性能F = F -ff可以用评价准则选择，也可以遍历所有特征计算在F上的分类性能如果分类性能不降低： F=F，循环否则结束,特征选择,联合选择增量法F =f1计算在F上的分类性能F = F +f 2f1、 f2可以用评价准则选择，也可以遍历所有特征计算在F上的分类性能如果分类性能增加： F=F，循环否则结束,特征选择,联合选择增/减量法优缺点复杂度关于维数为 或选单个特征采用评价准则排序的方式为一次选单个特征采用测试全部特征的方式为二次本质上是贪心算法某些组合无法遍历可能陷入局部极值,特征选择,联合选择全组合遍历NP难,Kohavi-John, 1997,特征选择,联合选择模拟退火/遗传算法（通用的优化算法）随机生成一批解可以用梯度下降法迭代到局部极值用现有解通过操作合成新的解不要求合成操作具有任何理论依据好的合成操作将极大提高解题效率对新生成的解进行生存选择同上，并可用梯度下降法迭代到局部极值迭代直到收敛或已支付预期的计算量,特征选择,模拟退火/遗传算法理论依据梯度下降法（爬山法）往往陷入局部极值非梯度下降手段使解“跳”到爬山法可求解范围不同的非梯度下降手段产生不同的算法,梯度下降法可求解的范围,局部极值,特征选择,模拟退火/遗传算法应用实例N皇后问题求解旅行商(TSP)问题求解很多类似NP完全和NP难问题适合于解可能有大量解，但解的比例很小，而整个解空间巨大的问题,特征选择,特征的相关性问题例：直方图通过特征选择算法不可能消除相关特征的相关性,Guyon-Elisseeff, JMLR 2004; Springer 2006,Hn可以由前n-1维完全预测出,Hn不能告诉我们任何额外信息可预测则不携带信息,特征选择,相关特征的选择把所有特征的各种可能变换、组合加入特征矢量在这个巨大的特征矢量上进行特征选择比NP难还难的问题特征的函数组合是无限的核函数（kernel functions）类似于利用原有特征构造各种新特征仅哲学上类似，并无数学依据变换降维,特征降维,主分量分析(PCA: Principle Component Analysis)在特征空间，如果特征维之间有相关性，则样本将分布在较低维的(高维)(曲)面上,特征降维,主分量分析线性变换,原始特征矢量：,主分量：,“轴”：,特征降维,主分量分析,如何求极值：,约束条件：,特征降维,主分量分析Lagrange乘数法,目标函数,约束条件,a1是S的最大特征值对应的特征矢量,特征降维,主分量分析同理可证：所有主分量对应的“轴”都是S的特征矢量，相应的特征值为其方差,A可通过KL变换从协方差矩阵S求,特征降维,主分量分析如果H是线性相关的：S是降秩的特征矢量个数小于维数降维无信息损失如果H各维相关性大，但没有达到完全相关有很小的特征值对应的特征矢量可以去除降维，有信息损失相关但非线性相关？目前还没有好的方法,特征降维,多模特征的降维同质特征可以方便地使用PCA同质特征内部是已经归一化的例：直方图，像素值，等等异质特征不能简单地进行PCA不同的归一化导致不同的主分量异质特征之间没有归一化例：颜色直方图和“粗糙度”如何归一化？,特征降维,多模特征的降维分组降维，组间加权同质特征用PCA降维，组间自动计算权重,如何计算组间权重？,w1,w2,wk,须依据最终目的优化,特征降维,权重计算类EM算法权重作为待计算变量分类准确率/目标匹配率作为优化目标随机权重计算目标计算修正权重权重修正算法依据不同的分类器甚至不同的问题，可能需要设计不同的修正算法更复杂：加入模拟退火/遗传算法过程对没有好算法的问题的一般解法,
