关键词  特征选取；特征排序；神经网络；多层神经网络

 

    随着信息 科学 技术的快速 发展 ，在 工业 界和学术界有着更复杂和更大的多变量建模 问题 。 研究 人员发现当不相关和冗余的特征向量剔除之后，模式识别技术的性能将显著的提高。由此，特征提取成为了数据预处理和数据挖掘技术的重要的步骤之一。具体来讲，特征提取有助于在线 计算 ，加强系统的可读性，以及提高系统的预测性能。

    一般来讲，特征选择有两大步骤：计算评价函数值和特征子集搜寻^[1]。评价函数要能反映出特征向量与数据类信息的匹配度信息，以及分类器性能变化的信息。而就特征子集搜寻来讲，为了避免繁冗的无遗漏搜寻，一些被大多数学者认可的搜寻方法被广泛采用，例如：前向选择，后向删除，双向搜寻等等^[2]。与完全搜寻和随即搜寻相比，这三种顺序的搜寻方法都能简单而快速的执行。

在构造输入数据和输出数据的复杂映射方面，由于多层神经网络(MLP)的卓越性能，因而MLP被广泛的采用。本文采用MLP来作为分类器，来展示各种特征选取方法在各个数据集上的分类性能。

    根据Shannon信息 理论 ，一个随机变量C的不确定性可以由熵H（C）来估计。对于两个随机变量X和C，条件熵可以估计当变量X已知时，变量C的不确定性。而互信息可以估计变量C和变量X的相互依赖性。从而，H（C） ， 和 三者有如下的关系^[3]：

，等价于

                                               (1)

    训练分类模型的目的是最小化已知训练数据与类属性数据的不确定性。若 比较大，则意味着训练数据集X所包含的信息能够有效地预测它们的类属性；相反地，若 比较小，则意味着训练数据集X所包含的信息不能够有效地预测它们的类属性。所以，训练分类器的过程应该找一组分类器参数Θ，而尽可能增大互信息 。

    而对于特征选取而言，其目的是从特征全集中选取一特征子集使得互信息尽可能的大以致于特征子集F能够有效地预测训练数据的类属性。也就是说，共有个F从而即可得到，我们可以选择最大的所对应的F来作为最优的特征集来代表特征全集X。

    然而，以上的描述只是考虑到了特征子集F与类属性C有最大的相关性，F未必成为最优的特征集。例如若F中每个的特征与属性C有最大的相关性时，它们当中有可能含有极大线性或非线性相关的特征甚至重复的特征。所以我们应该剔除掉这些冗余的特征，使得处理后的F成为新的最优的特征集。

即最小化。

    因此，最大相关性和最小冗余性应同时考虑在一起。我们定义一个算子Θ 将D和S结合起来来最大化Θ ，从而可以同时优化D和S：

                            (2)

    在实际中，我们可以采取前向递增的搜寻方法，并根据(2)来找到最优的特征向量集。假设我们已经有了(m-1)个特征集F_m-1。现在的任务是要选取m^th特征从。这一过程可以通过最大化Θ()来实现。也即优化下式：

           (3)

    其中， 。

    通过以上 分析 ，我们将OMI特征提取算法，表述为如下过程：

    初始化：将F设为空集，X为包含所有特征的全集。

    (1)计算与类属性的互信息：对每一个特征，计算 。

    (2)选取第一个特征：选择特征f，对应最大的互信息值；并且设置。

    (3)递归计算：选择特征f，对应最大的OMI评价函数，即：

    (4)如果，回到第2步，否则F即为最终所有特征向量的排序。

    需要指出的是，通过计算特征向量与类属性的互信息值，来导出每个特征向量相关性的排序，在理论上是可以证明的。另外，OMI评价函数可以避免估算多变量的的密度函数来求互信息。例如：计算 和 ，意味着需要先计算和。而这两项在高维数据集的实例中，无法有效地准确地估计。而OMI中，只需计算和，意味着只需先计算和即可。通常这两项可以用Parzen Window，Histogram等常用的低维密度函数估计的方法来估计。

    当今，特征提取的方法可以总体分为两大类：过滤式和嵌入式。过滤式是指特征提取的算法与分类器的训练算法无关；而嵌入式是指特征提取的算法与分类器的训练算法直接相关。一般而言，过滤式的方法容易执行而且运行效率高，然而嵌入式的方法选出的特征向量更可靠但是计算量非常大。本文提出的OMI方法，在特征向量选取和排序时并未用到任何分类器的训练算法，所以OMI属于过滤式的特征选取方法。但是在后文的实验部分可以看到OMI选取的特征向量比有代表性的嵌入式特征选取方法还要好。

    当今有代表性的过滤式方法为Fisher Score^[4]。Fisher Score方法通过式(4)来估计每个特征向量对不同类属性的区分能力，从而得出所有特征的排序。

                                                   (4)

    其中和分别是特征向量在第一类的均值和方差，而和分别是特征向量在第二类的均值和方差。从式(4) 可以看到每个特征向量的重要性只是由均值和方差的比值来衡量。所以在高维的数据集中，其特征选取的效果并不可靠。

    而有代表性的嵌入式方法有：Leave-one-out^[5]，Maximum output information^[6]。Leave-one-out是在每删除一个特征向量时，计算一次validation数据集上的分类器错误率变化。若其错误率变化相对较大，这可推断此特征向量相对重要；反之相对不重要。由此，也可得出所有特征向量的排序。而最近新提出的Maximum Output Information方法与MLP神经网络分类器相结合，通过计算输出信息在神经网络输入层各个节点的权值的大小来选出一个最不重要的特征向量。将其剔除后再依次重复以上过程剔除每一个特征向量。最先剔除的为最不重要的特征向量，最后剔除的为最重要的特征向量。从而也可得出所有特征向量的排序。值得注意的是，这两种嵌入式的特征选取的方法在递归计算各个特征向量的重要程度是都必须重新训练分类器，所以嵌入式的特征选取方法计算效率普遍很低。

    本文选取两个被广泛采用的人造数据集Monk和Weston数据集来展现OMI特征提取算法能够有效地可靠地对所有特征向量进行排序。关于两个数据集的介绍见表1。本文所有数据集的分类器采用3层MLP神经网络。其内部节点的数目由5-fold crossvalidation的方法来确定。

表1  数据集介绍

数据集名称	Monk	Weston
训练集样本个数	432	200
测试集样本个数	124	9800
特征向量个数	6	10
MLP二层节点个数	5	6

    Monk1数据集可以从UCI网站公共数据库下载得到( http：//archive.ics.uci.edu/ml/ )。已知6个特征向量与类属性的关系：当（f₁=f₂）或者（f₅=1） 时，样本属于第一类，反之属于第二类。由此可见这