1、第3章 大数据的特征选择第3章 大数据的特征选择3.1 特征选择的数学描述及其优势特征选择的数学描述及其优势3.2 特征选择基本框架特征选择基本框架3.3-特征选择算法分类特征选择算法分类3.4 特征选择的稳定性特征选择的稳定性第3章 大数据的特征选择3.1 特征选择的数学描述及其优势特征选择的数学描述及其优势1.特征选择的数学描述特征选择的数学描述 特征选择是指根据某种评估标准,选择特征数量较少、评估效果较好的特征子集。它的主要任务就是删除不重要的、不相关的、干扰性甚至破坏性的特征,不重要的特征是 指对系统性能贡献不大的特征,不相关的特征是指对系统性能没有影响的特征,干扰性甚 至破坏性的特征
2、是指导破坏系统性能的特征。第3章 大数据的特征选择第3章 大数据的特征选择2.特征选择的优势特征选择的优势 特征选择就是从原始数据集中选择与类别具有关联的特征集从而降低数据维度的一个 过程,如何寻找高维数据的“本征维数”对降低数据的维数及其后续信息处理起有重要的意 义,也对后续的模式分类发挥重要的作用。其有如下优势:(1)降低了特征空间维数,减少了需求空间并且加快了算法的速度;(2)去除了冗余的,无关的或“噪声”数据;第3章 大数据的特征选择(3)进行数据分析,缩短了学习算法的运行时间;(4)经过选择的特征更易理解;(5)增加了分类模型的精确度;(6)特征集的消减,为下一轮数据收集和利用节省了
3、资源;(7)分类性能的提高,从而提高了预测的准确性;(8)数据分析,有利于揭示底层数据蕴含的信息。第3章 大数据的特征选择3.2 特征选择基本框架特征选择基本框架特征选择是指在输入的变量数据中运用相应的特征算法构造一个特征子集的算法,而 这个特征子集是在原变量中提取出来的,这些子集最符合设定的特征选取标准。通过特征 选择可以过滤原始数据中权重较轻的数据,保留最能反映数据特征的数据,特征选择会使选择的数据模型更加精确简捷,提高处理效率。第3章 大数据的特征选择对于这些语言描述可以建立一个简单的 数学模型:给定样本数据集S=F、C、D,其中F(feature)代表特征样本集合,C(category
4、)代 表类别样本集合,D(data)代表数据样本集合。令特征算法J(X)(0,1)为特征评价函数,其中J(X)的大小表示着对应数据的信息量大小(即权重),权重越大,数据就越重要。第3章 大数据的特征选择在选取最优特征子集时函数一般会有以下几种类型:一是在特征集合F 中选取子集,使J(X)最大;二是给定J(X)的取值范围J0,选取函数值大于J0的子集;三是在F 中找 一个合适的子集使J(X)大并保证特征数尽量少。这几种方法分别从特征数和权重方面采 取不同的衡量选取方式,但是目的都是为了都得到对选择最有利的数据。特征选择是指在输入的变量数据中运用相应的特征算法构造一个特征子集的算法,这 是一个对数
5、据特征的优化选择过程。第3章 大数据的特征选择1997年 Dash和 Liu在对大量选择方法进行分析后给出了一个通用的特征选择技术框 架。结构框架图如图3-1所示,其中主要包含四个部分:子集产生、评价部分、停止条件 和验证部分,其中以子集产生和评价部分为核心部分,这两个环节进行了对特征子集的 主要筛选工作。第3章 大数据的特征选择图3-1 特征选择的基本框架第3章 大数据的特征选择(1)子集产生(SubsetGeneration)。这是一个搜索过程,通过一定的搜索策略产生候选 的特征子集。(2)评价部分(SubsetEvaluation)。该部分通过与选定的最优子集比较来评价生成部分选 取的特
6、征子集的合理性,并可评价选用的算法针对问题的有效性和对达到目标的帮助。第3章 大数据的特征选择(3)停止条件(StoppingCriterion)。算法结束所需要满足的条件,它与子集的产生过 程和评价准则的选用有关。经常采用的停止条件有:搜索完成;某种给定的界限,如指定的 特征维数或循环次数等已达到;再增加(或删除)任何特征都已不能获得更好的结果;对于 给定的评价准则,已获得足够好的特征子集。第3章 大数据的特征选择(4)验证部分(ResultValidation)。本部分是经过前几步筛选过程在初始特征中选出的 最优子集,通过和已有最优子集比较可以用来验证选用算法的适用性,用以确定最优算法 和
7、特征子集,本部分可通过学习和训练,提高特征选择系统选择特征算法的熟练程度。第3章 大数据的特征选择第3章 大数据的特征选择对于给定的数据集S,每个样本用一个n 维向量描述,算法从一个选定的特征子集fs 开始,根据一定的搜索策略在特征空间中进行搜寻,根据选定的评价准则J 对获取的每一 个特征子集进行评价,并与前面最好的特征子集进行比较。整个搜索过程一直持续到满足 特定的终止条件,算法的输出是相对于评价准则J 的最优特征子集。第3章 大数据的特征选择3.2.1 子集生成子集生成 假设特征集中包含n 维特征,那么搜索得到子集就有2n 种状态,特征选择过程就是寻 优搜索过程,要搜索的空间非常庞大,如果
8、n 非常大,再考虑特征评价过程的时间和空间 开销,这种穷尽式搜索通常是实现不了的。子集生成部分是由搜索方向和搜索策略组成。第3章 大数据的特征选择1.搜索方向搜索方向 搜索方向表明特征选择是以何种起点和方向搜索特征,任意一个子集都可以作为搜索 的起点,同时也决定着搜索特征子集的方向:(1)前向搜索,搜索开始时已选特征子集初始化为空,然后在剩余的未选特征集中依 次筛选每一个特征,将满足使评价测度最大的那个特征加入特征子集,如此循环直到达到停止条件;第3章 大数据的特征选择(2)后向搜索,与前向搜索相反,搜索开始时令已选特征集为整个全集,依次计算评价 测度,然后去除一个使评价测度最大的特征,循环直
9、到满足停止条件;(3)双向搜索,同时从两个方向搜索,先从当前的特征子集中删除一部分特征,然后再 选择合适的若干特征加入当前子集;随机搜索,随机产生一个子集作为搜索起点,这样的 搜索算法多次运行可能会产生不同结果,随机的方法避免了陷入局部最优点。第3章 大数据的特征选择2.搜索策略搜索策略 搜索策略可以分为完全搜索、随机搜索和启发式搜索。(1)完全搜索分为两种,分别为穷举搜索(Exhaustive)和非穷举搜索(Non-Exhaustive)。在这两种搜索方式中,穷举搜索因其列举出了所有的特征组合,有较高的精确度,但由 于其时间复杂度高,在特征组合数量较大的情况下耗时较长,所以并没有太高的应用价
10、 值。第3章 大数据的特征选择(2)随机搜索。其特点是在搜索中加入随机因素,在特征选择上将问题化为对搜索组 合的优化问题,在搜索计算的过程中,将特征选择与遗传算法,模拟退火等算法相结合,基 于特征对应的分类性能求解权重,然后根据用户设定或自调节的阈值筛选特征。(3)启发式搜索。该搜索方式的核心是一个评估函数,该函数通过分析当前的有效信 息得到,在该函数的指导下,搜索可以在众多节点中择优选择,并进行节点扩展。第3章 大数据的特征选择在启发式 搜索的众多方法中,序列前向选择(SequentialForwardSelection,SFS)、序列后向选择方 法(SequentialBackwardSe
11、lection,SBS),因其选择结果的最优性而被广泛应用。有结合两者思想提出的增l去r选择算法,但它的搜索速度比 SBS快,搜索效果比 SFS好;有随之发展来的序列浮动选择,该算法的l与r不是固定的,而是变化的。第3章 大数据的特征选择 还有决策树算法,将决策树生成算法在训练样本集上执行,为得到特征子集,在搜 索前期让决策树充分生长,待其生长后,在树上进行枝剪,则特征子集会在分支处生成。对 于决策树算法优劣需要一个评价标准,通常使用信息增益法。第3章 大数据的特征选择启发式的搜索可以设计出非常实用的应用于特征选择的次优搜索方法,这种算法并不 是搜索所有可能的特征组合,但是它可以估算出一组可用
12、的、潜在的特征组合。当设计合理评价准则时,这类算法在实际应用中甚至可以匹敌前两种搜索算法的效果,并且运算的 速度更快。是一种可以实现,并且效率高性能好的搜索算法,实际运用广泛。第3章 大数据的特征选择表3-1与表3-2 分别列出了各种搜索策略的常用算法描述和一些基本特性。第3章 大数据的特征选择第3章 大数据的特征选择第3章 大数据的特征选择3.2.2 评价测度评价测度 对特征子集的评价测度是特征选择中关键性问题,评价函数不同会产生不同的子集,评价测度的好坏直接影响最终的特征子集。常见的评价测度分为距离度量、一致性度量、信息度量、依赖性度量和分类错误率度量。第3章 大数据的特征选择1.距离度量
13、距离度量 在机器学习和数据挖掘中,我们经常需要知道个体间差异的大小,进而评价个体的相 似性和类别。最常见的是数据分析中的相关分析,数据挖掘中的分类和聚类算法,如 K 最 近邻(KNN)和 K 均值(K-Means)等。根据数据特性的不同,可以采用不同的度量方法。一 般而言,定义一个距离函数d(x,y),需要满足下面几个准则:第3章 大数据的特征选择(1)d(x,x)=0/到自己的距离为0(2)d(x,y)0/距离非负(3)d(x,y)=d(y,x)/对称性:如果 A 到B 距离是a,那么B 到A 的距离也应该 是a(4)d(x,k)+d(k,y)d(x,y)/三角形法则:(两边之和大于第三边)
14、第3章 大数据的特征选择距离度量(Distance)用于衡量个体在空间上存在的距离,距离越远说明个体间的差异 越大。1)欧几里得距离(EuclideanDistance)欧氏距离是最常见的距离度量,衡量的是多维空间中各个点之间的绝对距离。公式 如下:这里的p 值是一个变量,当p=2的时候就得到了上面的欧氏距离。第3章 大数据的特征选择3)曼哈顿距离(ManhattanDistance)曼哈顿距离来源于城市区块距离,是将多个维度上的距离进行求和后的结果,即当上 面的明氏距离中p=1时得到的距离度量公式,如下:第3章 大数据的特征选择4)切比雪夫距离(ChebyshevDistance)切比雪夫距
15、离起源于国际象棋中国王的走法,我们知道国际象棋国王每次只能往周围 的8格中走一步,那么如果要从棋盘中 A 格(x1,y1)走到B 格(x2,y2)最少需要走几步?扩展到多维空间,其实切比雪夫距离就是当p 趋向于无穷大时的明氏距离:其实上面的曼哈顿 距 离、欧 氏 距 离 和 切 比 雪 夫 距 离 都 是 明 氏 距 离 在 特 殊 条 件 下 的 应用。第3章 大数据的特征选择2.相似度度量相似度度量 相似度度量(Similarity),即计算个体间的相似程度,与距离度量相反,相似度度量的 值越小,说明个体间相似度越小,差异越大。1)向量空间余弦相似度(CosineSimilarity)余弦
16、相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。相 比距离度量,余弦相似度更加注重两个向量在方向上的差异,而非距离或长度上。公式 如下:第3章 大数据的特征选择2)皮尔森相关系数(PearsonCorrelationCoefficient)皮尔森相关系数即相关分析中的相关系数r,分别对 X 和Y 基于自身总体标准化后计 算空间向量的余弦夹角。公式如下:第3章 大数据的特征选择3)Jaccard相似系数(JaccardCoefficient)Jaccard系数主要用于计算符号度量或布尔值度量的个体间的相似度,因为个体的特征 属性都是由符号度量或者布尔值标识,因此无法衡量差异具
17、体值的大小,只能获得“是否相 同”这个结果,所以Jaccard系数只关心个体间共同具有的特征是否一致这个问题。如果比 较 X 与Y 基的Jaccard相似系数,只比较xi和yi和中相同的个数,公式如下:第3章 大数据的特征选择4)调整余弦相似度(AdjustedCosineSimilarity)虽然余弦相似度对个体间存在的偏见可以进行一定的修正,但是因为只能分辨个体在 维之间的差异,没法衡量每个维数值的差异,会导致这样一个情况:比如用户对内容评分,5分制,X 和Y 两个用户对两个内容的评分分别为(1,2)和(4,5),使用余弦相似度得出的 结果是0.98,两者极为相似,但从评分上看 X 似乎不
18、喜欢这2个内容,而Y 比较喜欢,余弦相似度对数值的不敏感导致了结果的误差,需要修正这种不合理性,就出现了调整余弦 相似度,即所有维度上的数值都减去一个均值,比如 X 和Y 的评分均值都是3,那么调整 后为(-2,-1)和(1,2),再用余弦相似度计算,得到-0.8,相似度为负值并且差异不小,但显然更加符合现实。第3章 大数据的特征选择5)马氏距离 马氏距离是由印度统计学家马哈拉诺比斯(P.C.Mahalanobis)提出的,表示数据的协 方差距离。它是一种有效地计算两个未知样本集的相似度的方法。与欧氏距离不同的是它 考虑到各种特性之间的联系(例如:一条关于身高的信息会带来一条关于体重的信息,因
19、为 两者是有关联的)并且是尺度无关的(scale-invariant),即独立于测量尺度。对于一个均值为=(1,2,D)T,协方差矩阵为 的多变量向量X=(x1,x2,xD)T 和Y=(y1,y2,yD)T,其马氏距离为第3章 大数据的特征选择如果协方差矩阵为单位矩阵,马氏距离就简化为欧氏距离;如果协方差矩阵为对角阵,其也可称为正规化的欧氏距离。式中,i2是xi的标准差。第3章 大数据的特征选择6)欧氏距离与余弦相似度 欧氏距离是最常见的距离度量,而余弦相似度则是最常见的相似度度量,很多的距离 度量和相似度度量都是基于这两者的变形和衍生,所以下面重点比较下两者在衡量个体差 异时实现方式和应用环
20、境上的区别。第3章 大数据的特征选择借助三维坐标系来看下欧氏距离和余弦相似度的区别:从图3-2可以看出距离度量衡量的是空间各点间的绝对距离,跟各个点所在的位置坐 标(即个体特征维度的数值)直接相关;而余弦相似度衡量的是空间向量的夹角,更加的是 体现在方向上的差异,而不是位置。如果保持A 点的位置不变,B 点朝原方向远离坐标轴 原点,那么这个时候余弦相似度cos是保持不变的,因为夹角不变,而 A、B 两点的距离 显然在发生改变,这就是欧氏距离和余弦相似度的不同之处。第3章 大数据的特征选择图3-2 欧氏距离和余弦相似度的区别第3章 大数据的特征选择根据欧氏距离和余弦相似度各自的计算方式和衡量特征
21、,分别适用于不同的数据分析 模型:欧氏距离能够体现个体数值特征的绝对差异,所以更多的用于需要从维度的数值大 小中体现差异的分析,如使用用户行为指标分析用户价值的相似度或差异;而余弦相似度 更多的是从方向上区分差异,而对绝对的数值不敏感,更多的用于使用用户对内容评分来 区分用户兴趣的相似度和差异,同时修正了用户间可能存在的度量标准不统一的问题(因 为余弦相似度对绝对数值不敏感)第3章 大数据的特征选择3.条件概率度量条件概率度量 上面讨论的是样本在特征空间的分布距离作为特征提取的依据。该种原理直观,计算 简便。但是这种原理没有考虑概率分布,因此当不同类样本中有部分在特征空间中交叠分 布时,简单地
22、按距离划分,无法表明与错误概率之间的联系。基于概率分布的可分性判据 则依据如下观察到的现象。第3章 大数据的特征选择如果我们不考虑各类的先验概率,或假设两类样本的先验概率相等,那么从两类条件 概率分布可以看出,如果两类条件概率分布互不交叠,即对p(X|w2)0处都有p(X|w1)=0,如图3-3(a)所示,则这两类就完全可分;另一种极端情况是对所有X 都有p(X|w1)=p(X|w2),如图3-3(b)所示,则两类就完全不可分。因此人们设计出与概率分布交叠程 度有关的距离度量方法,这些距离Jp有以下几个共同点:(1)Jp是非负,即Jp0;(2)当两类完全不交叠时Jp达到其最大值;(3)当两类分
23、布密度相同时,Jp=0。第3章 大数据的特征选择这种函数的一般式可表示为第3章 大数据的特征选择图3-3-条件概率分布第3章 大数据的特征选择下面列出一些常用的概率距离度量。1)Bhattacharyya距离和 Chernoff界限 Bhattacharyya距离的定义用下式表示:显然,当p(X|w1)=p(X|w2)对所有X 值成立时JB=0,而当两者完全不交叠时JB 为无穷大。第3章 大数据的特征选择Chernoff界限的定义与其相似,为式中,S 为0,1区间的一个参数,显然式(3-13)在S=0.5时就变为式(3-12),因此 Bhattacharyya是 Chernoff的一个特例。第
24、3章 大数据的特征选择2)散度 另一种常用的基于概率距离度量的判据是利用似然比或对数似然比。对两类问题,其 对数似然比为如果对某个 X,p(X|wi)=p(X|wj),则Iij=0,反之若两者差异越大,则Iij的绝绝对值 也大。第3章 大数据的特征选择以上只是对某一 X 值而言,为了对整个特征空间概率分布的差异程度作出评价,将 对wi类及wj对的可分性信息分别定义为与第3章 大数据的特征选择而总的平均可分信息则可表示成被称为散度。第3章 大数据的特征选择3)正态分布时基于概率分布距离度量正态分布时基于概率分布距离度量 显然在一般情况下由于概率分布本身的复杂形式,以上这些基于概率分布的距离相当
25、复杂。这些判据在概率分布具有某种参数形式,尤其是正态分布时可以得到进一步简化。下面讨论两类别正态分布时散度判据的表达式。第3章 大数据的特征选择设两类别分别表示为wi N(i,i),wj N(j,j)则,设两类分别表示为第3章 大数据的特征选择第3章 大数据的特征选择在正态分布时,Bhattacharyya距离JB 可表示成:它与散度JD 的表达式只差一个常系数。第3章 大数据的特征选择4)x2(CHI)统计量 CHI统计特征项w 和类别c之间的相关程度,并假设特征项w 和类别c之间符合具有 一阶自由度的x2分布。特征项 w 对于某类的x2统计值越高,它与该类之间的相关性越大,携带的类别信息也
26、越多。反之,x2统计量也能反映特征项 w 和类别c 之间的独立程度。当 x2值为0时,特征项w 和类别c完全独立。第3章 大数据的特征选择令 N 表示样本总数,c为某一特定类别,w 表示特征项,A 表示属于类别c 且包含特 征w 的频数,B 为不属于类别c且包含特征w 的频数,C 表示属于类别c 且但不包含特征 w 的频数,D 表示既不属于类别c且也不包含特征w 的频数。如表3-3所示。第3章 大数据的特征选择特征项w 对于类别c的 CHI值由如下公式计算:且有:N=A+B+C+D对于多类问题,分别计算 特 征 项 w 对 于 每 个 类 别 的 CHI值,再 用 式(3-28)或 式(3-2
27、9)计算特征项w 所对的 CHI值。CHI值也有最大值和平均值两种方法进行检验。第3章 大数据的特征选择最大值法:平均值法:2统计量和互信息的区别在于,它是一个归一化的统计量。它对于低频特征项的区分 效果仍然不是很好。第3章 大数据的特征选择5)期望交叉熵 期望交叉熵(ExpectedCross Entropy,ECE)与信息增益相似,也是一种基于概率的 方法。所不同的是信息增益要求计算所有特征项的值,而期望交叉熵则只计算出现特征项 的值。第3章 大数据的特征选择如果令m 表示 类 别 数,P(ci/w)表 示 出 现 在 特 征 项 w 时,属 于ci 类 别 的 概 率。P(ci)表示ci
28、类别的概率,则期望交叉熵可由式(3-30)计算:如果特征项w 和类别ci 强相关,也就是P(ci/w)大,且相应的类别出现概率又小的话,则说明该特征项对分类影响大,相应的函数值越大,就可能被选中作为特征项。第3章 大数据的特征选择4.后验概率分布度量后验概率分布度量 如果对某些特征,各类后验概率都相等,即式中,c为类别数,则样本的类属就无法确定,或者只能任意指定样本所属类别。此时这也就是错误率最大的情况。第3章 大数据的特征选择如果考虑另一极端,假设能有一组特征使得且那么此时的 X 肯定可划分为wj,而错误率为零。由此可看出,后验概率越集中,错误概率 就越小,反之后验概率分布越平缓,即接近均匀
29、分布,则分类错误概率就越大。第3章 大数据的特征选择为了衡量后验概率分布的集中程度,可以借助于信息论中熵的概念,制订定量指标。例如Shannon熵为另一常用的平方熵这两者都有熵函数的以下共性。第3章 大数据的特征选择第3章 大数据的特征选择5.一致性度量一致性度量 一致性度量就是计算一个特征子集对应的样本中“不一致”的样本所占的比例,不一致 的样本就是说两个样本上所有特征取值都相等,但是它们却属于不同的类别,则称这两个 样本为不一致样本。第3章 大数据的特征选择6.信息度量信息度量 信息度量是基于信息论中信息熵和互信息为理论依据的。信息度量标准的优势是它能 很好地度量特征与类别之间的非线性相关
30、程度。并且,它不依赖于特征的具体取值,是一 种无参数的评价标准,它只取决于特征值的分布,所以能有效地避免噪声的干扰。通过信 息熵计算特征与类别的不确定性程度,或通过互信息计算特征与类别的非线性相关度,选 出有重要意义的特征。第3章 大数据的特征选择1)信息熵 熵(Entropy)是一个来自于统计热力学的概念,它表示一个系统混乱的程度,如果系统 越混乱熵值就越高;反之,若是系统越有序,那么它所对应的熵值就越低。熵是描述随机变 量的不确定度的,通常也被称为信息熵或Shannon。假设 X 为一个随机变量,它可能取值 为x 的概率为p(x),那么它的信息熵 H(x)定义为第3章 大数据的特征选择由式
31、(3-36)可知,信息熵 H(x)和变量X 的概率分布密切相关,而与其具体值无关。这在某种程度上说明信息熵有效地避免噪声数据的干扰。研究发现,若随机变量 X 的概率 分布越大,即不确定性的程度越高,那么信息熵值就越大,表明它所需要的信息量也大。用 信息熵表示变量的随机性,也表示随机变量 X 的不确定度;H(x)值越小,表示不确定性 越小,则该变量分布越不均匀,数据集越纯。第3章 大数据的特征选择2)条件熵和联合熵 除此还引入了条件熵和联合熵的概念,联合熵主要用来描述多个变量之间共同拥有的 信息量。式中,p(x,y)为随机变量X 和Y 的联合概率分布;(p y|x)为在给定变量X 的条件下Y的概
32、率分布。第3章 大数据的特征选择条件熵 H(Y|X)表示在随机变量X 已知的情况下随机变量Y 的不确定性度,联合熵H(X,Y)表示随机变量 X 和随机变量Y 共同拥有的信息量,且通过变换可知第3章 大数据的特征选择3)互信息(mutualinformation)在信息论中,互信息描述两个变量的相互依赖程度,假设随机变量 X 和变量Y 存在某 种联系,则用互信息给出两者的共有的信息量,定义为I(X;Y)越大,说明 X 和Y 的相关性越大,说明变量 X 和变量Y 相关性越大,反之,两者 依赖程度越低。第3章 大数据的特征选择可以推导得到以下几种互信息的形式:也就是说在一个随机变量已知的情况下,另一
33、个变量的不确定性的减少程度。且当X、Y 相互独立时,互信息值为零。第3章 大数据的特征选择4)信息增益 信息增益(InformationGain,IG)是信息论中的一个重要概念,是基于信息熵的测评方 法,普遍应用于机器学习中。它表示了某一个特征的存在与否对类别预测的影响,定义为 特征在数据集中出现前后的信息量大小。信息增益的特征选择算法的指导思想是:对每一 个特征的信息增益值进行计算,并按照信息增益值的大小排序,删除小于预定义阈值的特 征,保留信息增益值大于预定阈值的特征,那么对于信息增益值的特征而言,它们对分类 的重要性是与其对分类的贡献成正比的。第3章 大数据的特征选择第3章 大数据的特征
34、选择7.依赖性度量依赖性度量 依赖性度量实际上是计算特征与类别之间的统计相关性,在面对庞大的特征集时,如 何快速定位那些和类别相关的特征而忽略其他无关或影响不大的特征。定义特征与目标函 数C 相关:实例空间中存在样本A 和样本B,C(A)C(B),其中样本 A 和 B 其余特征 均相同仅属性xi不同,则称特征xi与类别C 相关。在实际应用中,很多情况下不存在两个 样本间只有一个特征属性不一致,因而无法使用这种严格的定义,所以有了强相关和弱相 关的定义。当去掉强相关特征后,特征xi变为强相关特征,则称xi为弱相关特征。特征选择 的目的就是从原始特征集中选择出强相关特征和部分弱相关特征。第3章 大
35、数据的特征选择8.分类错误率度量分类错误率度量 分类错误率度量和上述四种度量是截然不同的,以上几种算法都是考察特征与类别、特征与特征之间的度量函数,是典型的 Filter式特征选择模型,而分类错误率度量是一种 Wrapper型特征选择模型,直接用分类错误率作为特征子集评价的标准。显然这种方法选 择的特征子集有很好的分类性能,受到很多研究者的推崇,缺点就是计算量颇大,通用性 差。表3-4中简单比较了上述5种评价测度的优缺点。第3章 大数据的特征选择第3章 大数据的特征选择3.2.3-停止条件停止条件 特征子集的搜索是一个循环的过程,所以必须设定一个停止条件,避免搜索过程无尽 的进行下去。一般的停
36、止条件设置如下:(1)已选特征子集的数目达到预先的设定值;(2)通过当前的已选特征集,达到了要求的分类率,或者提高了分类率;(3)特征的增加或减少,不再对评价函数值有影响;(4)评价函数的值已经达到预先设定的阈值,或者是达到拐点临界值;(5)当前的已选特征子集就是评价函数的最优解。第3章 大数据的特征选择3.2.4 结果验证结果验证 子集有效性验证是特征选择的最后一个步骤,在实际应用中必不可少。有效性验证通 过常用经过特征选择处理后的数据集进行训练和预测,将训练和预测的结果与在原始数据 集上的结果进行比较,比较的内容包括预测性的准确性、模型的复杂度等。第3章 大数据的特征选择3.3-特征选择算
37、法分类特征选择算法分类3.3.1 按样本是否标记分类按样本是否标记分类 根据训练集中样本是否标记或者部分标记,该分类方法可以基于三种学习模式:有监督学习(supervisedlearning)模式、半监督学习(semi-supervisedlearning)模式和无监督学 习(unsupervisedlearning)模式。第3章 大数据的特征选择有监督模式特征选择算法是通过计算特征与类别之间的关系,选择最具类别区分能力 的特征子集,大多数衡量准则中都包含类别变量。由于充分利用了类别信息,它能获得很 高的分类性能,缺点是通用性不高,由于该特征选择算法要求必须预先知道训练样本的类 标签,故其在实
38、际应用中存在一定的局限。无监督模式特征选择算法的目的是通过利用特征间内在关系或结构特征,运用数据的 方差或分离性对各个特征的重要性进行判断,在无需经验指导的条件下筛选出有意义的数 据类簇。第3章 大数据的特征选择一般,无监督特征选择性能不如有监督特征选择,而且算法的复杂度也高于有监督特 征选择,所以结合了两者的优点,产生了半监督特征选择。半监督特征选择是利用少数已 知类别的样本数据作为指导信息,来提高未知类别样本的特征选择性能。第3章 大数据的特征选择3.3.2 按与学习算法的结合方式分类1.Filter特征选择特征选择 Filter模型通过某个适应函数(FitnessFuction)的值来估
39、计某个特征子集的有效性,与 具体的分类器无关。基于 Filter过滤式的特征选择算法使用某种度量去分类特征,不依赖 于分类器的种类,主要基于数据本身的特征独立作为分类学习算法的预处理步骤,图3-4 是Filter特征选择流程图。第3章 大数据的特征选择图3-4 Filter特征选择流程图第3章 大数据的特征选择通过训练样本所具有的特征评价标准,低等级的特征被淘汰,数 据中固有特征被考虑去评估特征子集。由于 Filter过滤式的特征选择没有用到学习算法,而且在整个过程中不需要建模。Filter方法计算简洁且快速,可以评价特征子集,并且独立 于分类算法,因此计算资源要求少,适用于大规模的高维数据集
40、而且方法简单。缺点就是 该类型的方法大多数是基于变量的排序算法,忽略了特征与特征之间的相互作用,选择的 特征子集也许不能很好地匹配学习算法,所以性能不太高。第3章 大数据的特征选择2.Wrapper特征选择特征选择 Wrapper模型用某个特定分类器的性能作为特征子集选择的准则,这种直接优化分类器的策略可改进分类器的泛化性,但计算代价相对较高,且不具备通用性。基于 Wrpper包裹式学习算法,与 Filter过滤式的特征选择算法相反,它使用了学习算法去预测特征子集,图3-5是 Wrapper特征选择流程图。第3章 大数据的特征选择图3-5 Wrapper特征选择流程图第3章 大数据的特征选择3
41、.Embedded特征选择特征选择 Embedded模型同时进行特征选择和学习器设计。基于 Embedded嵌入式特征选择方 法结合了学习算法和特征选择机制去评价学习过程中被考虑的特征。特征选择算法嵌入到 学习和分类算法,也就是学习训练和特征选择同时进行,互相结合,如图3-6所示。构造 分类模型的过程就是选择特征的过程,重复循环迭代,当分类模型构造结束时,此时分类 模型用到的特征子集就是最终特征选择的结果。第3章 大数据的特征选择图3-6 Embedded特征选择流程图第3章 大数据的特征选择4.Hybrid特征选择特征选择 Hybrid特征选择方法使用结合学习算法的独立措施去评价子集有效性。
42、Filter模型 执行效率高,但是分类性能较差,而 Wrapper模型能获得很好的分类性能,但是计算复杂、耗时且占用资源。所以考虑集合两种特征选择模型,两者互补克服各自的限制,如图3-7所示。第3章 大数据的特征选择图3-7 Hybrid特征选择流程图第3章 大数据的特征选择3.3.3-Filter方法方法 1.特征选择中的相关性特征选择中的相关性 特征选择的研究离不开对自变量 X 和因变量y 之间相关关系以及自变量X 自身内部 变量之间关系的定义,前者表明了一种正向的相关关系,即相关度越高,包含的潜在信息 越多;后者则是冗余程度的反映,自变量内部相关程度越高,说明二者的替代性越强,可以 进行
43、取舍,实现特征选择的目的。第3章 大数据的特征选择在自变量 X 和因变量y 之间相关关系的定义方面,许多 文献将其分为强相关关系(strongrelevance)、弱相关关系(weakrelevance)和非相关 关系(irrelevance),他们各自的表达形式有差异,并且都可以找出反例证明各自的相关性定 义在某种情况下失效。现在针对特征相关性研究领域常采用的定义是由 Kohavi中给出的。第3章 大数据的特征选择令F 表示全体特征集合,Fi为其中第i个特征,Si=F-Fi,C 表示全体因变量y 的集合,因此自变量 X 和因变量y 之间的相关关系可以表示如下:第3章 大数据的特征选择给定一个
44、特征Fi,令特征子集MiF(Fi Mi),则当且仅当时,则称Mi为特征Fi的“马尔科夫毯”。Mi中包含了能够表征因变量集合C 的足够特征,Koller和Sahami在统计理论上提出采用后向消除算法过程最优特征子集,消除过程中以 特征是否存在马尔科夫毯为标准,故又称作马尔科夫毯特征过滤。第3章 大数据的特征选择令G 是一个给定的特征集合,当且仅当特征Fi具有弱相关性并且在G 中存在关于Fi 的马尔科夫毯Mi时,称Fi是集合G 中的一个冗余特征,可以被剔除掉。上述三种强相关、弱相关和不相关特征是自变量与因变量关系的反映;冗余特征是自 变量内部之间关系的反映,相互冗余的两个变量xi和xj很可能都是强
45、相关特征变量,也可 能都是弱相关特征变量,还可能都是不相关特征变量,有些特征选择算法可以找到强相关 特征,但无法剔除其中的冗余特征。相第3章 大数据的特征选择2.Filter方法方法 1)Filter方法基本原理 Filter方法通过某种准则考察每个变量的显著性,过滤掉不显著的变量,剩余的构成变 量子集。考虑包含有m 个样本的数据集Xk yk(k=1,2,m),其中Xk包括N 个变量 Xk,i(i=1,2,N),对应的输出为yk。Filter方法就是考察每个输入变量Xk,i与输出变量 yk相关程度,据此选择或过滤掉某些变量。因此,只要该变量与yk的相关度强,就有可能被 选中。即使真正的变量集合
46、只有一小部分,而其余的无关变量都与yk具有一定的相关度时,则大多数变量都可能会被选中。第3章 大数据的特征选择2)Filter方法分类 Filter模型依据数据内在的结构特征如样本类间距离或相关性选择最相关的特征。(1)基于距离准则的典型算法是 RELIEF,作者认为重要的特征将增大样本与非同类 近邻距离和样本与同类最近邻距离的差异,因此在加权特征子空间中样本集会呈现出较好的 类间分离性质。第3章 大数据的特征选择(2)基于相关性度量的特征选择方法评估特征与类别之间的相关度,以及特征彼此之 间的相关度。目前使用最广泛的相关度准则是 Pearson统计量(correlation)、熵(entro
47、py)、对称不确定准则(SymmetryUncertainty)与互信息(MutualInformation)准则,Pearson统 计量用来衡量特征之间的线性依赖关系,熵、对称不确定准则与互信息准则都来自于信息 理论,既可以衡量线性相关,又能够衡量非线性相关关系。第3章 大数据的特征选择(3)相关度准则也可用于无监督特征选择,由于这种情形下样本不含标记,难以计算 特征与类别的相关度,因此无监督特征选择研究算法重点放在如何消除冗余特征。例第3章 大数据的特征选择3.3.4 Wrapper方法方法 1.Wrapper方法的概念方法的概念 有指导学习中,将特征子集的选择算法看作是对有指导学习过程的
48、“封装”,有指导 学习作为每一步特征子集选择结果的评估,最终得到的特征子集可以实现分类准确率的最 大化。有指导学习过程既作为一个对检验样本的学习过程,又在特征选择中作为特征子集 好坏的评判标准(见图3-8)。第3章 大数据的特征选择图3-8 Wrapper方法特征选择流程图第3章 大数据的特征选择2.Filter和和 Wrapper方法的比较方法的比较 理解 Filter和 Wrapper方法的关键点在于首先明确特征选择的输出将作为新的特征集(设计矩阵),成为另一个机器学习算法的输入,通过该算法完成机器学习过程,达成用户 预期的数据分析目的。为区别于特征选择算法中可能用到的机器学习算法概念,我
49、们称之 为目标学习器。其次,在特征子集的评估过程中,又必须用到一个专门的中间算法来产生 评估值,这个中间算法可能是一个简单的单映射函数(如费舍尔判据或皮尔森相关系数 等),也可能是与目标学习器相同的机器学习算法,也可能是与之不同的其他学习算法。Filter和 Wrapper方法的区别就在于对中间算法的选取。第3章 大数据的特征选择Wrapper方法的主要缺点是:特征选择过程的计算效率低于 Filter方法,因为每一 步选择出的特征子集都需要通过运行学习算法进行交叉验证才能确定其优良性;所选择 的特征子集是有偏的,选择不同的学习器在同一数据集上进行训练,所得到的最优特征子 集很可能是不同的,这种
50、有偏性一方面会导致过拟合(over-fitting)的发生,另一方面,特征 选择的不稳定性会给研究者解释试验数据造成困扰。第3章 大数据的特征选择3.3.5 Embeded方法方法 Embeded方法同时解决了特征选择与分类、回归或聚类问题,即将特征选择视为学习算法的子系统。这类算法计算复杂度介于 Wra pper方法与 Filter方法之间,选择出的特征也比 Filter模型更准确,但需要与新设计的算法相结合。Embeded方法与上述两种方法的区别在于,它不需要将训练样本分为训练集(Training Set)和验证集(ValidationSet),也就是说,在 Embeded方法中不需要对中
