（计算机软件与理论专业论文）基于成对约束和稀疏表示的特征选择算法研究.pdf

j置 j ， n a n j i n gu n i v e r s i t yo f a e r o n a u t i c sa n d a s t r o n a u t i c s t h eg r a d u a t es c h 0 0 1 山 j i i iii l l l lli i ii l l l l l lj i i i i j 18 2 5 7 61 c o l l e g eo fi n f o r m a t i o ns c i e n c ea n dt e c h n o l o g y r e s e a r c ho nf e a t u r es e l e c t i o n a l g o r i t h m s b a s e do np a i r w i s ec o n s t r a i n t sa n d s p a r s e r e p r e s e n t a t i o n a t h e s i si n c o m p u t e rs o f t w a r ea n dt h e o r y b y d a ns u n a d v i s e d b y p r o f d a o q i a n gz h a n g s u b m i t t e di np a v i a lf u l f i l l m e n t o ft h er e q u i r e m e n t s f o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g j a n u a r y , 2 0 1 0 誓 ； i 承诺书 本人声明所呈交的硕士学位论文是本人在导师指导下 进行的研究工作及取得的研究成果。除了文中特别加以标注 和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得南京航空航天大学或其他教育机 构的学位或证书而使用过的材料。 本人授权南京航空航天大学可以将学位论文的全部或 部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名：二丝：查 e l 期： 丝! 竺：至：! 兰 i 印 南京航空航天大学硕士学位论文 摘要 特征选择作为高维数据降维的有效方法，已被广泛应用在文本分类、信息检索、遗传基因 分析等领域。现有的大多数特征选择算法都是基于有标记样本或无标记样本的。然而，除了类 标记，还存在另一种监督信息，即标识样本对是否属于同一类的成对约束。成对约束作为一种 新颖的监督信息，由于其比类标记更易获取，已在机器学习的很多方面得到了成功应用。因此， 本文首先针对基于成对约束的特征选择算法从多个角度展开了充分研究。另一方面，由于稀疏 表示的良好特性，近年来，也引起了机器学习领域研究人员的广泛关注。本文将稀疏表示引入 特征选择方法的框架中，提出了一种全新的基于稀疏表示的特征选择算法。主要创新和研究工 作总结如下： ( 1 ) 在基于成对约束的特征选择算法c o n s t r a i n ts c o r e 的基础上，结合半监督降维的思想， 通过加入全局或者局部的无监督信息，提出了半监督特征选择算法s e m i c s 。s e m i - c s 能够同时 利用成对约束和无标号数据进行特征选择，且在多个u c i 高维数据集上获得了很好的性能。 ( 2 ) 针对c o n s t r a i n ts c o r e 的性能易受成对约束集具体组成影响的缺点，提出了特征选择集 成算法b c s 。b c s 以集成的观点利用成对约束集，有效地提高了在多个u c i 高维数据集和基因表 达数据集上的分类和聚类性能。 ( 3 ) 将稀疏表示引入特征选择中，提出了基于稀疏表示的特征选择算法s p a r s i t ys c o r e 。该 算法选取最能够保持数据间稀疏重构关系的特征子集，在多个u c i 高维数据集和基因表达数据 集上的实验结果验证了所提算法的有效性。 关键词：特征选择，成对约束，集成学习，稀疏表示，半监督降维 基于成对约束的特征选择算法研究 南京航空航天大学硕士学位论文 a b s t r a c t f e a t u r es e l e c t i o n ，a sa ne f f e c t i v em e t h o di nd i m e n s i o n a l i t yr e d u c t i o no fh i 【g h d i m e n s i o n a ld a t a ， h a sb e e nw i d e l yu s e di nm a n yp r a c t i c a la p p l i c a t i o n ss u c ha st e x tc a t e g o r i z a t i o n ，i n f o r m a t i o nr e t r i e v a l a n dg e n e t i c a n a l y s i s m o s to ft r a d i t i o n a lf e a t u r es e l e c t i o nm e t h o d sp e r f o r mo nl a b e l e dd a t ao r u n l a b e l e dd a t a h o w e v e r , b e s i d e sc l a s sl a b e l s ，t h e r ee x i s t sa n o t h e rf o r mo fs u p e r v i s i o ni n f o r m a t i o nf o r f e a t u r es e l e c t i o n ，i e ，p a i r w i s ec o n s t r a i n t sw h i c hs p e c i f yw h e t h e rap a i ro fi n s t a n c e sb e l o n g st ot h e s a n t oc l a s s ( m u s t - l i n kc o n s t r a i n t ) o rd i f f e r e n tc l a s s e s ( c a n n o t - l i n kc o n s t r a i n o p a i r w i s ec o n s t r a i n t s ， w h i c hc a nb em o r ee a s i l yo b t a i n e dt h a nc l a s sl a b e l s ，h a v eb e e na p p l i e di nm a n ya r e a so fm a c h i n e l e a r n i n g t h e r e f o r e ，w ef i r s t l yf o c u so ns t u d y i n gf e a t u r es e l e c t i o na l g o r i t h m s 、i mp a i r w i s ec o n s t r a i n t s o nt h eo t h e rh a n d ，b e c a u s eo ft h eg o o dc h a r a c t e r i s t i c so fs p a r s er e p r e s e n t a t i o n s ，i th a sa t t r a c t e d 州d e a t t e n t i o n so fr e s e a r c h e r si nt h ef i e l do fm a c h i n el e a r n i n g w ei m p o s et h en o t i o no f s p a r s e r e p r e s e n t a t i o nt of e a t u r es e l e c t i o nm e t h o d sa n dp r o p o s ean o v e lf e a t u r es e l e c t i o na l g o r i t h m t h em a i n c o n t r i b u t i o n so ft h i st h e s i sms u m m a r i z e da sf o l l o w s ： f i r s t l y ，w es t u d yc o n s t r a i n ts c o r ew h i c hi saf e a t u r es e l e c t i o na l g o r i t h mb a s e d0 np a i r w i s e c o n s t r a i n t s b yi n t e g r a t i n gt h ec o n c e p to fs e m i s u p e r v i s e dd i m e n s i o n a l i t yr e d u c t i o na n da d d i n gt h e g l o b a lo rl o c a li n f o r m a t i o n ，an o v e ls e m i - s u p e r v i s e df e a t u r es e l e c t i o na l g o r i t h mc a l l e ds e m i - c si s p r o p o s e d s e m i - c sc a r tm a k e u s eo fb o t hu n l a b e l e dd a t aa n dp a i r w i s ec o n s t r a i n t sf o rf e a t u r es e l e c t i o n a n dh a sg o o dp e r f o r m a n c e so ns e v e r a lu c ih i g h - d i m e n s i o n a l i t yd a t a s e t s s e c o n d l y , f o rt h es h o r t c o m i n go fc o n s t r a i n ts c o r ew h i c hd e p e n d e n t so nt h ec o m p o s i t i o no f c o n s t r a i n t ss e t 。w ep r o p o s ea ne n s e m b l ef e a t u r es e l e c t i o na l g o r i t h mc a l l e db c s b c sm a k e su s eo f p a i r w i s ec o n s t r a i n t sf r o mt h ee n s e m b l ep e r s p e c t i v ea n de f f e c t i v e l yi m p r o v e st h ec l a s s i f i c a t i o na n d c l u s t e r i n gp e r f o r m a n c e s0 1 1s e v e r a lu c ih i g h - d i m e n s i o n a l i t yd a t a s e t sa n dg e n ee x p r e s s i o nd a t a b a s e s f i n a l l y ，b a s e do ns p a r s er e p r e s e n t a t i o n ，w ep r o p o s eaf e a t u r es e l e c t i o na l g o r i t h mc a l l e ds p a r s i t y s c o r e s p a r s i t ys c o r ea i m st op r e s e r v et h es p a r s er e c o n s t r u c t i v er e l a t i o n s h i po ft h ed a t a e x t e n s i v e e x p e r i m e n t so ns e v e r a lu c ih i g h - d i m e n s i o n a l i t yd a t a s e t sa n dg e n ee x p r e s s i o nd a t a b a s e sv a l i d a t et h e e f f e c t i v e n e s so ft h ep r o p o s e da l g o r i t h m k e y w o r d s ：f e a t u r es e l e c t i o n ，p a i r w i s ec o n s t r a i n t s ，e n s e m b l el e a r n i n g ，s p a r s er e p r e s e n t a t i o n ， s e m i s u p e r v i s e dd i m e n s i o n a l i t yr e d u c t i o n 基于成对约束的特征选择算法研究 南京航空航天大学硕+ 学位论文 第一章绪论 目录 l 1 1 研究背景及其意义1 1 2 特征选择的一般过程2 1 3 特征选择算法的分类2 1 3 1 按与学习算法的结合方式划分特征选择算法2 1 3 2 按搜索策略划分特征选择算法3 1 3 3 按是否使用监督信息划分特征选择算法3 1 4 基于成对约束的学习4 1 5 稀疏表示。5 1 6 本文的研究工作。5 1 7 本文的内容安排。6 第二章基于成对约束的半监督特征选择算法 9 2 1j ；l 言9 2 2 半监督特征选择算法1 0 2 2 1c o n s t r a i n ts c o r e 算法1 0 2 2 2s e m i - c s 算法。1 2 2 3 实验结果与分析1 5 2 3 1 实验设置1 5 2 3 2 聚类性能分析1 6 2 4 本章小结1 7 第三章基于成对约束的特征选择集成算法1 9 3 1 引言1 9 3 2 特征选择集成算法2 0 3 2 i 集成学习。2 0 3 2 2b c s 算法2 0 3 3 实验结果与分析2 3 3 3 1 实验设置。2 3 v 基于成对约束的特征选择算法研究 3 3 2u c i 数据集2 4 3 3 3 基因表达数据集3 l 3 3 4 实验讨论3 3 3 4 本章小结3 6 第四章基于稀疏表示的特征选择算法 4 1 引言3 9 4 1 1 稀疏表示的求解3 9 4 2 基于稀疏表示的特征选择算法4 1 4 2 1 稀疏重构4 l 4 2 2s p a r s i t ys c o r e 算法4 2 4 3 实验结果与分析4 3 4 3 1 实验设置“ 4 3 2 聚类性能分析4 4 4 4 本章小结4 5 第五章总结与展望4 7 5 1 已有工作总结4 7 5 2 未来工作展望4 8 参考文献 致谢 攻读硕士学位期间发表的学术论文 4 9 5 7 5 9 i 气 南京航空航天大学硕士学位论文 图表清单 图1 1 一个典型的特征选择的过程【9 】2 图2 1c o n s t r a i n ts c o r e 算法流程2 6 1 1 2 图2 2s c m i - c s 算法流程l3 图2 3f s c o r e 度量法1 6 图2 4s e m i c s 算法的聚类性能v s 成对约束数目1 7 图3 1b c s 算法流程2 2 图3 2u c i 数据集上的分类精度v s 特征数目2 6 图3 3 分类精度v s 个体分类器中的成对约束数目2 9 图3 4u c i 数据集上的分类精度v s 成对约束数目2 9 图3 5b c s 、i c s 和b i c s 三种算法在u c i 数据集上的分类精度。3 0 图3 6 基因表达数据集上的分类精度v s 特征数目3 1 图3 7 基因表达数据集上的分类精度v s 成对约束数目3 2 图3 8 分类精度v s 集成大小3 4 图3 9 集成的差异性一错误率。3 5 图3 1 0b c s 算法的聚类性能v s 成对约束数目3 6 图4 1 图形化对比，范数和范数最小化问题【5 1 】。4 0 图4 2s s 算法流程4 3 表2 1s c m i - c s 算法的最高聚类性能1 7 表3 1c o m t r a i n t s c o m 算法分类精度的波动范围1 9 表3 2u c i 数据集的统计信息2 4 表3 3b c s 算法在u c i 数据集上的最高分类精度。2 6 表3 4b c s 算法在u c i 数据集上的最高分类精度( c v ，n n ) 2 7 表3 5b c s 算法在u c i 数据集上的最高分类精度( c v ，s v m ) 。2 7 表3 6 基因表达数据集的统计信息3 l 表3 7b c s 算法在基因表达数据集上的最高分类精度。3 2 表4 1s s 算法的最高聚类性能。“ 基于成对约束的特征选择算法研究 注释表 输入样本 样本标号 集成大小 聚类数目 k 近邻集 正约束集 负约束集 正约束个数 负约束个数 稀疏重构向量 稀疏重构矩阵 选定的特征数目 第，个特征向量 第r 个特征的均值 约束得分 主动学习 压缩感知 稀疏得分 f i s h e r 得分 拉普拉斯得分 约束得分集成 半监督约束得分 拉普拉斯特征映射 半监督判别分析方法 l 南京航空航天大学硕士学位论文 i i 研究背景及其意义 第一章绪论 随着数据采集技术和存储技术的发展。人们已经能够非常容易地获取大量高维数据，如生 物数据、网络数据、遥感数据等等。但是，由于数据维数过高，通常会导致许多学习算法面临“维 数灾难”【1 1 。具体来讲，在模式识别与机器学习的实际应用中，问题的概率结构通常不是完全已 知的，大部分学习算法都要对许多未知的参数进行估计，如概率分布密度中的有关参数，而这 些参数的个数往往与特征空间的维数是有关的，如协方差矩阵的阶就等于特征空间的维数。如 果特征空间维数过高，那么要准确估计这些参数必须具备大量的训练样本，或者说，在训练样 本数目有限的实际情况下，过高的特征空间维数会导致参数估计的准确率下降，进而影响学习 算法的性能。同时，数据维数过高和训练样本不足的矛盾常常导致一些学习算法出现“过拟合” 现象【1 1 。另一方面，高维数据中常常存在大量冗余的、与任务不相关的特征，即其内在结构存 在于低维空间中。因此，降维是对高维数据进行挖掘的一个重要预处理步骤。 从一般意义上来讲，降维是指为高维数据找到一个能忠实反映原始数据固有特性的低维表 示。两类常用的数据降维方法为：特征提取和特征选择。特征提取是指将原有空间的特征进行 某种组合，以得到新的特征。典型的特征提取方法有：主成分分析p c a t l l 、线性判别分析l d a t 、 拉普拉斯特征映射l e 2 等等。这些算法对许多学习任务都可以较好地降维，但是特征的理解性 很差，因为即使简单的线性组合也会使构造出的特征难以理解，而在很多情况下，特征的可理 解性是很重要的。另外，因为特征提取的新特征通常由全部原始特征进行变换得到，所以并没 有减少数据收集的工作量。与特征提取方法不同，特征选择是指从原始特征集中选择使某种评 估标准最优的特征子集【3 】。它将数据投影到输入空间的少数坐标轴上，而不是投影到某个变换 后的子空间中。通过特征选择，一些和任务无关或者冗余的特征被删除，并且简化后的数据集 通常会得到更精确的模型，也更容易理解【3 】。 特征选择的目的是利用选出的最小特征子集，使得后续的学习任务，如分类或聚类达到和 特征选择前近似甚至更好的效果【3 】。它是统计学领域的经典问题，最早的特征选择研究是从上 世纪6 0 年代初开始的【4 1 ，当时的研究通常集中于统计学及信号处理问题1 5 1 【6 l ，且所涉及问题的特 征数目通常不多。然而，自上个世纪9 0 年代以来，大规模机器学习问题的不断出现，使得已有 的特征选择算法受到严峻的挑战，迫切需要适应大规模数据计算准确性和复杂度要求的综合性 能较好的特征选择算法。特征选择已经成为当前机器学习中的一个研究热点，并被广泛应用在文 本分类、信息检索、遗传基因分析等领域【7 】强】。 基于成对约束的特征选择算法研究 1 2 特征选择的一般过程 特征选择的任务是按照某种评估标准从一组数量为d 的特征中选择出数量为d ( d d ) 的一 组最优特征。如图1 1 所示，一个典型的特征选择的过程主要由四个部分组成：1 ) 产生器；2 ) 评估准则；3 ) 停止条件；4 ) 验证【训。其主要过程为：首先利用产生器按照一定的策略从原始 特征集中产生出候选特征子集；然后通过某种评估准则度量出其相对于学习任务的相关性；如 果当前的候特征子集满足最优性条件，则停止产生新的特征子集，否则，继续产生新的特征子 集：最后验证已选定的最优特征子集的有效性。 从以上过程可以看出，特征选择问题是一个搜索择优问题。具体来讲，原始特征集，即搜 索的起点，可以是包含全部特征的全集、不包含任何特征的空集以及任意一个特征子集。利用 某种评估准则评价由产生器产生的特征子集的过程就是不断择优的过程。因此，从本质上讲， 特征选择的过程就是一个组合优化问题，即，若有n 个特征，则有2 “个候选特征子集。若采用穷 举法，那么这个择优的过程在特征数目非常多的情况下将是非常低效的。因此，搜索过程中通 常采用一些启发式的搜索策略。最后，验证已选定的特征子集。验证的过程在实际应用当中更 是一个不可或缺的环节。该过程通常将实际的数据集投影到由已选定的特征子集构成的子空间 上，在较低维数的子空间上进行训练或预测，从而不仅降低了模型的计算复杂度，而且其测试 性能比在原有空间中的性能有所提高。 图1 1 一个典型的特征选择的过程1 9 1 1 3 特征选择算法的分类 1 3 1 按与学习算法的结合方式划分特征选择算法 按照特征选择与后续学习算法的结合方式，特征选择算法可分为两大类：1 ) 过滤式( f i l t e r ) 模型【1 0 l ；2 ) 封装式( w r a p p e r ) 模型【i l 】。 2 南京航空航天大学硕士学位论文 过滤式模型独立于后续的学习算法对数据进行处理，即在训练开始之前去除不必要的属性， 其评估准则不涉及学习算法。过滤式模型主要使用基于数据一般特点的启发性规则对特征进行 评价。不同于过滤式模型，封装式模型在特征选择时考虑具体机器学习算法的特点，将学习算 法的性能作为特征选择的评估标准。它通常使用某一归纳算法结合重复统计抽样技术( 比如交 叉确认) 来评价特征子集的准确性。 过滤式和封装式模型各有优缺点。通常就准确率而言，封装式模型优于过滤式模型，然而 前者较后者计算复杂度高，且丧失了数据的一般特性。另外，封装式模型在训练数据很少时， 还存在过拟合现象【l 】。当处理高维数据时，过滤式模型由于其计算效率而得到更多的应用。因 此，本文侧重于讨论过滤式模型。 1 3 2 按搜索策略划分特征选择算法 按照在搜索空间中采用不同的搜索策略，特征选择算法又可进一步划分为两大类【1 2 】：1 ) 特征排列方法；2 ) 子集搜索方法。 特征排列方法独立地评价每个特征，按照每个特征的贡献对所有特征进行排列，然后取前d 个最好特征作为满足条件的特征子集【1 4 】【15 1 。由k i r a 等人在1 9 9 2 年提出的r e l i e f 16 1 方法是典型 的特征排列方法，该方法基于最近邻的思想，认为一个“好”的特征应使得最近邻的同类样本 问的距离越近，而不同类样本间的距离越远。另外，v 撕柚c e 【1 7 1 、l a p l a c i a ns c o r e 1 8 1 和f i s h e r s c o 1 17 】也是两个典型的特征排列方法。 子集搜索方法按照某种评估准则评价每个候选子集的贡献，从所有候选子集中选出最优的 一个特征子集。现有的评估准则有很多，如：一致性、相关性、信息增益等等。搜索策略也有很 多，如：完全搜索、随机搜索、层次搜索。不同的评估准则与不同的搜索策略结合，从而产生 多种特征选择算法【2 0 ) 1 2 1 】【2 2 】。 特征排列方法与子集搜索方法有本质上的区别：特征排列方法独立地评估每个特征，而子 集搜索方法评估每个特征子集，从而转化为一个组合优化问题。特征排列方法可以很容易地应 用到大规模数据和高维数据中型1 2 】，而子集搜索方法通常都很耗时，对高维数据集进行处理时 效率较低。因此，本文着重于研究特征排列方法。 1 3 3 按是否使用监督信息划分特征选择算法 按照特征选择中使用的训练数据是否有标号或者部分有标号，可将特征选择方法分为有监 督的特征选择【1 们、无监督的特征选拶2 3 】【2 4 】1 和半监督的特征选择。 在有监督的特征选择中，通过特征与类标号间的相互关系来评价特征。f i s h e rs c o r e 是一种 典型的利用所有类标号信息的有监督特征选择算法，它寻找最能够保持学习器判别能力的特征 3 基于成对约束的特征选择算法研究 子集。另外，z h a n g 等人2 6 1 提出了利用另外一种监督信息，即成对约束( p a i r w i s ec o n s u a i n t ) 2 r l ， 进行特征选择，其基本思想是选取保持成对约束能力最强的特征。 在无监督的特征选择中，通过特征保持数据结构的能力来评价特征，如方差、局部保持能 力掣2 引。l a p l a c i a ns c o r e 就是一种有效的无监督特征选择算法，它通过单个特征的局部保持能 力来评估每个特征。 当存在充裕的有标号数据时，有监督的特征选择通常优于无监督的特征选择。然而，不同 于无标号数据获取的简便性，获得大量的有标号数据是相当困难的。因此，在实际应用中我们 经常遇到“小样本问题( s m a l ll a b e l e d - s a m p l ep r o b l e m ) 【7 】【2 9 1 。为解决该问题，z h a o 等人【2 3 捷出 了半监督特征选择，能够同时利用有标号的和无标号的数据对特征进行评估，并且其性能明显 优于只使用无标号数据的特征选择算法。 1 4 基于成对约束的学习 l 一 在许多数据挖掘的应用中，有标记样本的获取往往比较困难或者代价昂贵，而无标记样本 中所包含的有用信息又相对较少，因此，近年来，研究以成对约束作为监督信息的学习受到了 研究人员的重视。成对约束( p a i r w i s ec o n s t r a i n t ) 最初出现在图像检索的任务中口7 】【3 0 】p ，可分 为正约束( m u s t - l i n kc o n s t r a i n t ) 和负约束( c a n n o t 1 i n kc o n s t r a i n t ) ，即属于同一类的样本间的约束 称为正约束，而不属于同一类的样本间的约束称为负约束。 成对约束通常比类标号更容易获取，因为数据内在的类标号通常不容易得到，而却可以让 用户简单地指出一对样本是否属于同一类。成对约束可以由类标号产生，类标号却不可以由成 对约束产生。成对约束可以很容易的获得，甚至在某些特定的领域中，还可以在没有人工参与 的情况下自动获取【3 2 1 。其中一个例子是视频数据中的目标物体识别。从视频的多个连续的数据 帧中，只要场景相同，我们就可以把大致在同一个位置出现的物体标记为正约束。类似地，在 同一帧中不同位置出现的两个物体，我们可以标记为负约束。 由于成对约束获取的简便性以及包含较多的监督信息，成对约束已经广泛应用于机器学习 的很多方面，如距离度量学习【3 3 1 ，半监督聚类【3 4 埯等。在聚类任务中，w a g s t a f f 3 5 1 首次证明了 ， 使用随机选取的成对约束可以同时提高聚类精度和减少运行时间。同时，近几年也出现了一些 利用成对约束进行降维的方法，比如b a r - h i l l e l 等人【27 l 提出了利用等价性约束的降维方法 f ( c f l d ) 。t a n g 和z h o n g l 3 6 】利用数据间的正约束和负约束，也提出了一种降维方法。另外，z h a n g 等人【 】提出了结合无标号样本和样本间成对约束的半监督降维算法s s d r 然而，很多研列3 2 】【3 5 】【3 8 】例也表明基于成对约束的算法其性能随着其所使用的约束集的 组成和大小的变化波动较大。d a v i d s o n 等人1 3 9 1 首次尝试度量约束集对基于划分的聚类算法性能 的影响，并且解释了某些约束集的无用性甚至是产生负作用的原因。主动学习( a c t i v el e a r n i n g ) 4 一 南京航空航天人学硕十学位论文 【4 0 1 是解决该问题的一个手段。在主动学习中，学习算法可以主动地提出标注请求。b a s u 等人【4 ” 提出了利用f a r t h e s t - f i r s tt r a v e r s a l 方法主动选取包含信息的成对约束。m e l v i l l e t 4 2 和g r e e n e l 4 3 j 等人 通过集成的方法标识有价值的约束。尽管如此，这些主动选取成对约束的方法都是通过主动查 询实际的类标号得到的。如果限制其从给定的约束集中选取约束，这些方法可能都将失败。事 实上，在许多实际应用中，由于其需要人工干预，主动选取成对约束的方法较之随机给定成对 约束的方法仍然存在缺陷。 1 5 稀疏表示 稀疏表示( s p a r s er e p r e s e n t a t i o n ) 最初是在信号表示领域提出的。在信号与信息处理领域， 如何用最小的代价表达信号，是一个非常重要的问题。传统的信号分解变换是将信号分解在一 组完备的正交基上的，例如：傅里叶变换、短时傅里叶变换、小波变换等等。然而，由于正交 分解存在一定的局限性，信号分解后往往不能够达到一个好的稀疏表示效果。为了实现对信号 更加灵活、简洁和自适应的表示，m a l l a t 和z h a n g 4 4 在小波分析理论的基础上，于1 9 9 3 年首次 提出了信号在过完备字典上进行分解的思想。其中，所谓过完备字典，是一组在信号组成的空 间中足够密集的基集合。它是过完备的、存在冗余的。由于基是过完备的，因此经过分解得到 的信号表示系数将绝大多数为零，即可以得到信号的一个非常简洁的、稀疏的表达，称为稀疏 表示。 由于稀疏表示的良好特性，信号稀疏表示的研究很快被从一维信号的研究推广到作为二维 信号的图像表示研究上。稀疏表示被用于信号分解和编码【4 5 1 、图像去噪m 1 等等。 另外，由d o n o h o 与c a n d e s 等人h 刀于2 0 0 4 年提出的压缩感知( c o m p r e s s e ds e n s i n g ) 理论 是一个充分利用信号稀疏性或可压缩性的全新信号采集编解码理论。它对传统的山农一奈奎斯 特采样定理造成了猛烈的冲击。压缩感知理论表明只要信号在某一个正交空间具有稀疏性，就 能以较低的频率采样信号，而且可以以高概率重构该信号。值得指出的是，基于该理论的单像 素相机也以问世。由于每次拍照只需要存储多个单像素信号，最后再在接收端通过计算得到影 像。因此解压成像之前的信号量非常小，获得了很有效的数据压缩。 特别地，在机器学习与模式识别领域，稀疏表示可用于目标检测4 耵、分类1 4 9 等。稀疏表示 分类是有监督的，它通过所有有标记的样本来重构每一个测试样本。最近的研究表日月【删【5 1 】，基 于稀疏表示的分类器能够在多个人脸数据库上获得很高的识别率，特别对人脸识别中的外部干 扰如残缺人脸图像、化妆及遮挡等，表现出很好的鲁棒性。 1 6 本文的研究工作 本文的研究工作主要围绕两方面展开： 5 基于成对约束的特征选择算法研究 l 、在详细研究基于成对约束的特征选择算法的基础上，从两个方面对其进行了改进。首先 结合半监督学习的思想，提出了基于成对约束的半监督特征选择算法；其次，通过应用集成学 习方法的思想，提出了基于成对约束的特征选择集成算法； 2 、将稀疏表示的思想引入到特征选择的理论中，提出了基于稀疏表示的特征选择算法。 本文的具体研究工作如下： ( 1 ) 深入学习了半监督学习的思想，通过在基于成对约束的特征选择算法c o n s t r a i n ts c o r e 中加入全局或者局部化的无监督信息，提出了基于成对约束的半监督特征选择算法 s e m i s u p e r v i s e dc o n s t r a i n ts c o r e ( s e m i - c s ) 。s e m i - c s 算法能够同时利用大量的无标号数据和少 量的成对约束进行特征选择。为验证提出的算法的有效性，在多个u c i 高维数据集上将其与已 有的特征选择算法进行了对比和讨论。 ( 2 ) 在c o n s t r a i n ts c o r e 算法的基础上，通过引入集成学习的思想，提出了基于成对约束的 特征选择集成算法b a g g i n gc o n s t r a i n ts c o r e ( b c s ) 。b c s 算法采用集成的方法来利用给定的成对 约束集，首先在重采样的约束子集上利用c o n s t r a i n ts c o r e 算法选择特征子集，进而构造个体学 习器，最终合成多个个体成员的学习结果，从而避免了为单个c o n s t r a i n ts c o r e 算法选取成对约 束集的问题。在多个u c i 标准数据集和基因表达数据集上进行了实验。实验结果证实了b c s 算 法在性能上比c o n s w a i n ts c o r e 算法有较大改进，它不仅克服了基于成对约束学习方法的共同缺 点，能够很好地利用已有的成对约束集，使其不易受其约束集具体组成的影响，而且在性能上 也优于其他一些特征选择集成算法。 ( 3 ) 对稀疏表示进行了深入的研究，并将其引入特征选择中，提出了一种新型的基于稀疏 保持的特征选择算法s p a r s i t ys c o r e ( s s ) 。s s 算法选取使得稀疏重构误差最小的特征子集，并且 不需要任何参数。在多个u c i 标准数据集和基因表达数据集上的实验结果证实了该算法的可行 性和有效性。 l r 1 7 本文的内容安排 本文共分5 章，各章节安排如下： ， 第一章首先介绍了特征选择的研究背景及其意义：其次对当前的特征选择算法进行了简单 的总结和归类，并重点介绍了一些典型的特征选择算法；然后介绍了基于成对约束学习的相关 卉 知识，其中重点列举了一些基于约束的降维算法，为研究基于成对约束的特征选择算法作铺垫； 最后阐述了稀疏表示的一般概念，并介绍了其在机器学习领域的一些应用。本章的主要目的是 概要介绍本文的研究工作以及为下文的章节提供一定的背景知识。 第二章详细研究和分析了基于成对约束的特征选择算法c o n s t r a i n ts c o r e 以及当前流行的几 个特征选择算法，进而结合半监督学习的思想，提出了基于成对约束的半监督特征选择算法 6 南京航空航天火学硕士学位论文 s e m i c s ，并且在多个u c i 高维数据集上考察了其聚类性能。 第三章首先重点分析了基于成对约束的特征选择算法c o n s t r a i n ts c o r e 的缺点和不足，接着将 集成学习的思想引入至l j c o n s t r a i n ts c o r e ，提出了基于成对约束的特征选择集成算法b c s 。在多 个u c i 标准数据集和基因表达数据集上，b c s 算法相对于c o n s t r a i n ts c o r e 算法在性能上有了很大 的提升。 第四章首先回顾了稀疏表示的概念与求解过程，其次重点分析了算法的理论基础一一稀疏 重构权重矩阵的构造方法，最后基于稀疏重构权重矩阵提出了一种新型的特征选择算法s p a r s i t y s c o r e ，并且在多个u c i 标准数据集和基因表达上进行了对比实验。 第五章总结已完成的工作并对后继工作进行展望。 7 基于成对约束的特征选择算法研究 8 l 南京航空航天大学硕士学位论文 2 1 引言 第二章基于成对约束的半监督特征选择算法 在许多数据挖掘的应用中，我们可以很容易地获取大量的无标记样本，而有标记样本的获 取则相对比较困难或者代价昂贵。这主要是因为有标记的样本通常要求相关领域的专家对其进 行标记。例如，在医学影像处理领域，通常可从医院得到大量无标记的医学影像，但医学专家 只能选择其中很少的一部分进行标记。传统的有监督学习方法，由于只能利用有标记样本，在 只有大量无标记样本的情况下，常常显得无能为力。而只能利用无标记样本的无监督学习方法， 由于其缺乏监督信息，性能又往往欠佳。近年来，能够同时利用无标记样本和有标记样本进行 学习的半监督学习方法，由于其在诸如文本分类旧等实际问题上的出色性能，受到了研究人员 的广泛重视。基于半监督学习的研究主要可分为：半监督分类【”】、半监督回归卅以及半监督聚 类佟4 1 。 目前，伴随着半监督学习方法的成功应用，半监督降维方法【5 5 】也逐渐引起了人们的关注。 半监督降维方法克服了传统的降维方法只能利用监督信息，或者只利用无监督信息的缺点，从 而提高了很多传统降维方法的性能。半监督降维方法主要可分为：半监督特征提取方法、半监 督特征选择方法。 在半监督特征提取方面，y u 等人【蚓在e m 框架下提出了半监督概率p c a 模型；c a i 等人5 7 1 利用局部近邻信息提出了半监督判别分析方法( s e m i s u p e r v i s e dd i s c r i m i n