在本节中，我首先介绍两种特征选择算法，分别是RELIEF算法和LSI下的特征选择（FSLSI）算法，这两种方法的思路都是从大量特征中选取一定数目的最有价值的特征。通过实验实现这两种算法，并与其他方法进行比较。随后我再提出对RELEIF算法的一个改进，在一定程度上能够提高选取最优样本的准确率。最后，将实验结果进行比较分析。

2.1  RELIEF算法

在现有的特征加权算法中，RELIEF算法由于其简单性和高效性，从而被认为是最成功的算法之一。该算法的伪代码呈现在图2.1.1 。

图2.1.1.1  RELIEF算法的伪代码

RELIEF算法的关键思想是根据特征对邻近样本的辨别能力来迭代的估量特征权重。在每次迭代中，随即选择一个样本x，然后找到X的两个最近样本，一个来自同一类别（被称为最近命中的，即NH），另一个来自不同类别（被称为最近不命中的，即NM）。然后更新第i个特征的权重：  。RELIEF算法被扩展为用来处理噪声数据和丢失的数据，其中也提供了对RELIEF算法的一个概率意义上的解释，即最后更新了的权重值大概与下式近似：

            (1)

然而，由于(1)中的两个概率没有明确定义，理解这个解释是不容易的。为了进一步研究这个问题，我们从优化的角度对RELIEF算法提出了一种新的解释。我们可以证明RELIEF算法是一个通过基于边缘检测的目标函数来解决凸优化问题的在线算法。边缘的定义是基于1-NN（一个最近的邻居）分类器。因此，与滤波方法相比，RELIEF算法之所以性能更好，是因为其在非线性分类搜索信息量最丰富的特征时的反馈性能。与传统的包装方法相比，通过优化的凸优化问题，RELIEF能够避免任何穷举式或启发式的组合搜索，从而可以被高效的实施。这两个优点使得REIEF算法特别适合大规模问题，例如微矩阵数据分析。文献综述

RELIEF算法的全新解释，使得我们能够识别和处理所用算法的一些缺点。RELIEF算法的一个主要缺点是样本的最近邻居在原始特征空间内就被定义，这在加权空间内是及其不可能的事件。此外，RELIEF算法缺乏一种处理异常数据的机制。由于存在着大量无关特征和许多错误归类的样本，RELIEF算法的解决办法的质量会严重下降。

RELIEF算法是这样一种特征加权算法，它利用一个高度非线性分类器的性能来搜索有用的特征，然而结果却是一个带有封闭形式的解决方案的凸优化问题。这清楚的解释了RELIEF算法的简单性和高效性。

2.2  基于隐藏语义空间的特征选择算法（FSLSI）

2.2.1  LSI算法的阐述

在本节中，我们假定所有的文本文档和索引是由词频-反文档频率（TF-IDF）所定义的经典向量空间（VSM）呈现。因此，一个语料库文本文件是由一个 的词语-文档矩阵 所表示，其中n是样本数目，d是特征数目。每一个样本由一个列向量 ,i=1,2,,n所定义的。令 代表 的第K个项目。 代表矩阵X的转置，I代表任意大小的单位矩阵。在经典LSI算法中，对经典向量空间进行改进，用SVD推导得出的低秩逼近来代替原始词语-文档矩阵。矩阵X的奇异值分解可以被描述为 ，其中 是一个对角矩阵。 的对角元素为 ，它们都是矩阵X的对角元素。矩阵 ， 分别包含矩阵X的左奇异向量和右奇异向量。因而有 ， 。LSI只保留领先的奇异向量，例如，矩阵U和V的前p列，（通常情况下p d），以及 左上角的子矩阵，使得 ，其中矩阵 ， ， =diag( )。