第一章 绪论
1.1 研究背景和研究意义
随着互联网的高速发展，数据的体量与维度呈爆炸式的增长，同时数据背后隐藏着的重要信息亟待着人们去挖掘，以方便人们更好的利用这些数据。虽然我们可以通过数据库系统来完成海量数据的储存、修改和统计，但是数据里面存在的关系和规则却无法通过数据库系统来得知。如今随着互联网的进一步发展数据更偏向于呈现半结构化或无结构化，这些数据的特征表示更是高达数万维至几十万维。高维数据往往给有监督学习带来极大的挑战。例如基因表达数据往往由成千上万的基因所组成，在对这种类型的数据直接进行分类的时候，学习算法往往会过拟合。这是因为我们常发现只有一少部分基因是和样本息息相关的，而大部分基因实际上是不相关的。为了处理这样的问题，很多研究人员开始关注特征降维技术。特征降维主要分为特征抽取和特征选择两种。特征抽取关注于将原始特征空间通过一定的变化映射到一个更低维的空间中去。特征抽取中最具有代表性的方法是主成分分析法。而特征选择并不会改变原始特征空间的分布，只是从原始特征空间中抽出一部分重要的特征，然后这些特征可以构成一个原始特征空间的子空间。特征选择是一个选择最优特征子集的有效的方法，其中这个最优特征子集包含了在给定特征维度下高维特征数据中最有判别能力的特征。并且相较于特征抽取的降维方法，特征选择方法选中的特征的可解释性更强。
在过去的数十年间，特征选择在处理高维特征中扮演了一个重要的角色，例如去除不相关的特征。一般来说，特征选择的方法主要可以分为三类：过滤式方法，包裹式方法和嵌入式方法。过滤式的方法在选择特征子集时是依照数据的固有特性来进行特征选择，而没有包含任何学习算法。典型的有监督式的特征选择算法包括 Fisher 得分和Relief-F。包裹式的特征选择方法式把预测器当作一个黑盒子，预测器的性能当作目标函数来进行特征的选择。尽管这类方法可以取得好的效果，但是它们通常是十分耗时的。嵌入式的特征选择算法将学习器的训练与特征选择放在了同一个目标函数中，优化完成的同时特征选择也同步完成。在这三类方法中嵌入式方法比其它两种在诸多方面有着优势，并且已经获得了越来越多的重视。
.........................
1.2 主要贡献
为了解决高维数据中存在的冗余数据的问题，本文研究了高维数据的特征选择算法。主要研究包括如下:
1) 基于特征子空间权重的分层特征选择算法研究：
提出了一种子空间聚类（SFC）算法。SFC 在子空间加权双聚类算法上引入类标信息进行拓展，这种算法可以识别出特征聚类和特征对每个类别的重要性。有了 SFC 的双聚类结果后，特证按照 SFC 算法学习到的子空间权重来独立的为不同的特征聚类中的特征来排序。
因为特征在相同的特征聚类的相关程度是高于不同的聚类中的相关程度的，所以本文提出了一种分层特征加权算法去给特征进行排序，通过分层选择的策略避免选择出来的特征集中在某一特征聚类中，使得选择出的排名靠前的特征是信息量丰富且多样的。
通过在模拟数据的比较，本文可以知道 SFC 是一个高效的特征聚类算法。本文在 12 个标准数据集和 2 个深度特征的数据集上将 SFR 与 6 种特征排序算法比较后，发现 SFR 在大多数数据集上的分类准确率的结果比大部分方法要好。
.........................
第二章 相关工作
2.1 特征选择
特征选择，又常常被称为变量消除，是一个去确定对于预测任务最优的特征集合的过程。这个任务可以追述到上世纪 40 年代[1]。特征选择早期的研究主要集中在线性回归。后来这方面的研究逐渐地覆盖了分类和聚类问题。在过去的数十年间，大量的特征选择算法被提出，而且大量的研究和应用表明了特征选择算法在去除无关变量提升模型性能上发挥着极大的作用[2–7]。
特征是我们可观察到的事物的属性。依照不同的学习任务，我们可以将特征分为相关特征与无关特征。从给定的对象的特征集合中选择特征的过程，我们称之为特征选择。在最近的数十年的时间里，在机器学习或模式识别的应用中，研究对象的特征数量已经增长到成千上万的数量级了。这些高维的数据往往会给有监督的学习任务带来维度灾难的问题[8–12]。一方面对于很多分类器来说，维度的增大会带来参数的增多，为算法带来时间开销上的增大。另一方面，对于很多预测器，维度的增大，会使模型出现过拟合的问题，即加入了不相关的特征使得最后的预测结果反而降低。为了解决这样的问题，特征选择成为了一个有效的方法去识别高维数据中的相关的特征子集[13–15]。在这篇文章中我们重点关注一些文献中的方法，这些方法用特殊手段来找到能提升预测性能的特征子集。
特征选择的过程关注于去寻找一个特征的子集以有效描述数据本身，同时可以消除噪声特征和不相关特征的影响，以此来提升预测的性能。例如，基因表达数据往往由成千上万的基因组成，这些基因会衡量不同的基因表达的水平。当分类这些数据时，
学习模型会遇到过拟合的问题，因为实际上往往只有一小部分的基因与样本之间存在较强的关联性，而绝大部分的基因与样本是不相关的，我们需要找到最有判别能力的特征子集[12]。
............................
2.2 有监督特征选择
在过去的数十年里，很多特征选择的方法被提出，很多研究都表明，特征选择有助于消除无关的特征而不会带来性能上的降低[17,18]。依照利用的类标信息的程度，我们将特征选择方法可以分为有监督的特征选择，无监督的特征选择以及半监督的特征选择。其中有监督的特征选择方法是完全利用样本的类标信息来进行特征选择，无监督的特征选择方法是完全不利用特征的类标信息而是利用数据本身的分布来进行特征的选择，半监督的特征选择则是利用部分类标信息来进行特征选择。我们研究的目标主要集中在有监督的特征选择方法上，所以我们将主要列举有监督的特征选择方法，有监督的特征选择方法被分为 3 种：过滤式方法，包裹式方法，嵌入式方法。
过滤式的方法依照数据的基本属性来选择特征子集，而不需要学习算法的参与。过滤式的方法由于它们的易用性和在实际应用中的较好的效果而广为人使用。这类方法将特征选择作为分类任务的预处理过程，通过去除掉不相关的特征来实现提升分类器性能的目标。这类方法的关键在于如何评价一个特征对数据的重要性或者对输出的重要性，这样典型的有监督式的过滤式特征选择算法主要包括 Fisher 分数[13]、Relief-F[19]、信息增益[20]、互信息量[21]、Inf-FS[22]、ILFS[23]。Fisher 特征选择方法是通过衡量数据在不同特征空间下，类间差异与类内部差异的比值来衡量特征的重要性。研究人员基于 Fisher 提出了一种基于子集迹比率的特征选择算法来改进 Fisher 特征选择的结果[24]。但是这样的有监督的过滤式特征选择算法在评价特征时，往往希望特征与特征之间是条件独立的。当特征与特征本身之间的相关度较高，在计算上述特征性质时，相关度较高的特征可能会得到类似的结果，从而导致我们选择出来的特征子集中的特征之间的相关度很高。但是实际上当我们需要选择的特征较少的时候，这些相关度较高的特征可以看作是一种冗余的特征。当排名靠前的冗余特征对某一类的贡献高时，排名较低的不冗余特征对其他类的贡献会因冗余特征的存在而降低，此时我们可以采取其他方法来去除掉这些冗余的特征，从而使得我们选择出来的特征中的信息更加的丰富，这样可以辅助我们进行更好的分类。
.............................
第三章 基于子空间权重矩阵的分层特征选择算法 ································· 12
3.1 概述 ···································· 12
3.2 分层特征排序方法 ·································· 12
3.2.1 特征聚类算法 ·································· 13
3.2.2 分层加权特征排序 ··························· 15
第四章 基于特征权重的分层特征选择算法 ········································ 29
4.1 概述 ··························· 29
4.2 特征聚类算法 ······························ 29
4.2.1 目标函数 ································ 29
4.2.2 固定 Z 和 c 来更新 V ·························· 30
第五章 基于差异性约束的分层特征选择算法 ···························· 39
5.1 概述 ······························ 39
5.2 标记和定义 ······························ 39
5.3 增广拉格朗日乘子法（ALM） ························· 39
第五章 基于差异性约束的分层特征选择算法
5.1 概述
高维的数据往往会给有监督的学习任务带来极大的挑战，如图像数据往往是由成千上万的像素点构成的。由于图像数据中往往存在着很多不相关或大量冗余的信息，这使得分类器的学习变得十分困难。许多研究表明特征选择技术可以很好的解决这一问题。在第三章中本文提出了一种分层特征选择算法，这个算法通过特征聚类的方式，使关联性较高的特征聚在同一个特征组中，而关联性不高的特征可以聚类到不同的特征组。虽然该方法尽可能的从不同的组中挑选出特征，但是最终挑选出的最有信息量的特征子集在原始组中是高度相关的。为了去选择到信息量更加丰富而且又低相关性的特征，本章将研究如何利用稀疏约束的方式进一步降低同一特征聚类中的冗余特征从而进行特征选择。
.........................
结论和展望
本文针对高维数据中存在的特征冗余的情况进行了研究，所提出的方法可以选择出低冗余的特征。本文的主要的贡献可以分为一下几个方面：本文提出了一个分层特征选择（SFR）的算法用来对高维数据进行特征排序。在这个方法里，一个子空间特征聚类算法（SFC）被提出并用来将特征划分到一系列的特征聚类中去。同一特征组中的特征各自按照从 SFC 学到的子空间权重来进行排序。为了选择到信息量多且多样的特征，本文提出了一种分层加权特征排序算法来给特征进行排序，从而使得最终排在前面的特征可以是尽可能的来自不同的特征聚类。
通过在一系列模拟数据上的实验，SFC 在特征聚类上的有效性和拓展性已经被验证。本文将 SFR 与其他 6 种特征选择算法在一系列高维真实数据来比较，通过的实验的表现我们可以知道在大部分数据集上 SFR 是优于其他 6 种方法的。除此之外 SFR 可以选择信息量高且多样的特征。因此这是一个处理高维数据的新的工具。
在分层特征选择的基础上，本文提出了一种基于特征权重的分层特征选择算法（SFS），算法通过直接学习特征的重要性来简化模型，通过一系列实验我们可以知道SFS 算法仍可以选择出信息量高且多样的特征。
在分层特征选择的基础上，本文进一步分析了 SFR 算法中同一特征组中排名靠前的特征仍然存在相关度高的问题，于是又提出了一种差异性特征选择算法（DFS）去选择高维特征中信息量高且丰富的特征。新的方法同步执行特征聚类和选择，并且用一个差异性约束项来减少排名靠前的特征之间的相关性。通过在 9 个数据集上与其他 8 种算法的比较结果我们可以知道 DFS 在去除不相关特征和冗余特征上的优越性。且相比于 SFR，DFS 可以选择出信息量更加丰富且多样的特征。
参考文献（略）