论文的前一部分

FEATURE SELECTION ON CONVENTIONAL DATA

在本节中，我们根据所使用的技术对传统数据的传统特征选择算法进行了广泛的分类：

• 基于相似性（Similarity based Methods）；
• 基于信息理论（）;
• 基于稀疏学习;
• 基于统计;
• 其他方法。

Similarity based Methods

不同的特征选择算法利用各种类型的标准来定义特征的相关性。
基于相似性的方法：通过保存数据相似性的能力来评估特征的重要性。

• 对于有监督的特征选择，可以从标签信息导出数据相似性;
• 而对于无监督的特征选择方法，大多数方法利用不同的距离度量来获得数据相似性。

给定一个具有n个实例和d个特征的数据集X∈Rn×d，可以在一个相似度/亲和度（affinity）矩阵S∈Rn×n中编码具有相似性的对。假设我们希望选择k个最相关的特征S，一种方法是最大化它们的效用：maxSU(S)，其中U(S)表示特征子集S的效用。由于该系列中的算法经常单独评估特征，特征子集S上的效用最大化可以进一步分解为以下形式：

其中U(f)是特征f的效用（utility）函数。 f^表示原始特征向量f的变换（例如缩放，归一化等）。 S^是从亲和度矩阵S得到的一个新的亲和度矩阵。

公式(1)表明我们将从S中选择一个特征子集，以便它们能够很好地保留在 S^中编码的数据流形结构。这个问题通常通过贪婪地选择最大化它们的个别效用的前k个特征来解决。 这个类别的方法在设计亲和度矩阵S的方式上有所不同。 接下来我们讨论一些代表性的算法，这个算法可以在单个最大化框架下进行修改。

Laplacian Score

拉普拉斯分数是一种无监督的特征选择算法，它选择最能保留数据流形结构的特征。 它由三个阶段组成。

• 首先，它构造了亲和度矩阵S(i,j)， 如果xi是 xj 的P最近邻，则S(i,j)=e−∥xi−xj∥22t；否则S(i,j)=0。
• 构造对角矩阵D，D(i,i)=∑nj=1S(i,j)； 拉普拉斯矩阵L，L=D−S.
• 最后对于每个特征fi的拉普拉斯分数如下：
  

由于拉普拉斯分数单独评估每个特征，选择k个特征的任务可以通过用最小的拉普拉斯分数来贪婪地选择前k个特征来解决。 每个特征的拉普拉斯分数可以重新表示为：

其中∥D12f~i∥2是特征fi的标准数据方差；f~i∥D12f~i∥2是特征fi的归一化特征向量。很显然，拉普拉斯分数是公式（1）中效用最大化的一个特例。

SPEC

SPEC是拉普拉斯分数的一个扩展，适用于有监督和无监督两种情况。例如，在无监督情景下，数据相似性由RBF kernel测量; 而在监督情景下，数据相似性可以由以下公式定义：

其中nl则是第l类中的数据样本的数量。 在获得了亲和度矩阵S和对角矩阵D之后，归一化拉普拉斯矩阵 Lnorm=D−12(D−S)D−12。

SPEC的基本思想与Laplacian Score相似：与数据流形结构一致的特征应该将相似的值分配给彼此相邻的实例。

在SPEC中，特征相关性通过三个不同的标准来衡量：

在上述公式中，f^i=D12fi∥D12fi∥2