基于最优互信息的特征选取
基于最优互信息的特征选取 摘 要 本文提出一种新的多层神经网络的特征提取的方法。基于所提出的每个特征的评价函数值，此方法能够给出所有特征的排序。该方法在人造数据集和真实数据集上进行了实验。实验结果表明OMI能够准确地高效地在各种数据集上鉴别出最优特征集。关键词 特征选取；特征排序；神经网络；多层神经网络 1 引言随着信息科学技术的快速发展，在工业界和学术界有着更复杂和更大的多变量建模问题。研究人员发现当不相关和冗余的特征向量剔除之后，模式识别技术的性能将显著的提高。由此，特征提取成为了数据预处理和数据挖掘技术的重要的步骤之一。具体来讲，特征提取有助于在线计算，加强系统的可读性，以及提高系统的预测性能。一般来讲，特征选择有两大步骤：计算评价函数值和特征子集搜寻1。评价函数要能反映出特征向量与数据类信息的匹配度信息，以及分类器性能变化的信息。而就特征子集搜寻来讲，为了避免繁冗的无遗漏搜寻，一些被大多数学者认可的搜寻方法被广泛采用，例如：前向选择，后向删除，双向搜寻等等2。与完全搜寻和随即搜寻相比，这三种顺序的搜寻方法都能简单而快速的执行。在构造输入数据和输出数据的复杂映射方面，由于多层神经网络(MLP)的卓越性能，因而MLP被广泛的采用。本文采用MLP来作为分类器，来展示各种特征选取方法在各个数据集上的分类性能。2 最优互信息根据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)个特征集Fm-1。现在的任务是要选取mth特征从。这一过程可以通过最大化()来实现。也即优化下式： (3)其中， 。3 OMI特征提取算法通过以上分析，我们将OMI特征提取算法，表述为如下过程：初始化：将F设为空集，X为包含所有特征的全集。(1)计算与类属性的互信息：对每一个特征，计算 。(2)选取第一个特征：选择特征f，对应最大的互信息值；并且设置。(3)递归计算：选择特征f，对应最大的OMI评价函数，即：(4)如果，回到第2步，否则F即为最终所有特征向量的排序。需要指出的是，通过计算特征向量与类属性的互信息值，来导出每个特征向量相关性的排序，在理论上是可以证明的。另外，OMI评价函数可以避免估算多变量的的密度函数来求互信息。例如：计算 和 ，意味着需要先计算和。而这两项在高维数据集的实例中，无法有效地准确地估计。而OMI中，只需计算和，意味着只需先计算和即可。通常这两项可以用Parzen Window，Histogram等常用的低维密度函数估计的方法来估计。4 其它特征提取算法当今，特征提取的方法可以总体分为两大类：过滤式和嵌入式。过滤式是指特征提取的算法与分类器的训练算法无关；而嵌入式是指特征提取的算法与分类器的训练算法直接相关。一般而言，过滤式的方法容易执行而且运行效率高，然而嵌入式的方法选出的特征向量更可靠但是计算量非常大。本文提出的OMI方法，在特征向量选取和排序时并未用到任何分类器的训练算法，所以OMI属于过滤式的特征选取方法。但是在后文的实验部分可以看到OMI选取的特征向量比有代表性的嵌入式特征选取方法还要好。当今有代表性的过滤式方法为Fisher Score4。Fisher Score方法通过式(4)来估计每个特征向量对不同类属性的区分能力，从而得出所有特征的排序。 (4)其中和分别是特征向量在第一类的均值和方差，而和分别是特征向量在第二类的均值和方差。从式(4) 可以看到每个特征向量的重要性只是由均值和方差的比值来衡量。所以在高维的数据集中，其特征选取的效果并不可靠。而有代表性的嵌入式方法有：Leave-one-out5，Maximum output information6。Leave-one-out是在每删除一个特征向量时，计算一次validation数据集上的分类器错误率变化。若其错误率变化相对较大，这可推断此特征向量相对重要；反之相对不重要。由此，也可得出所有特征向量的排序。而最近新提出的Maximum Output Information方法与MLP神经网络分类器相结合，通过计算输出信息在神经网络输入层各个节点的权值的大小来选出一个最不重要的特征向量。将其剔除后再依次重复以上过程剔除每一个特征向量。最先剔除的为最不重要的特征向量，最后剔除的为最重要的特征向量。从而也可得出所有特征向量的排序。值得注意的是，这两种嵌入式的特征选取的方法在递归计算各个特征向量的重要程度是都必须重新训练分类器，所以嵌入式的特征选取方法计算效率普遍很低。5 实验结果5.1 人造数据集本文选取两个被广泛采用的人造数据集Monk和Weston数据集来展现OMI特征提取算法能够有效地可靠地对所有特征向量进行排序。关于两个数据集的介绍见表1。本文所有数据集的分类器采用3层MLP神经网络。其内部节点的数目由5-fold crossvalidation的方法来确定。表1 数据集介绍数据集名称MonkWeston训练集样本个数432200测试集样本个数1249800特征向量个数610MLP二层节点个数56Monk1数据集可以从UCI网站公共数据库下载得到(http：/archive.ics.uci.edu/ml/)。已知6个特征向量与类属性的关系：当（f1=f2）或者（f5=1） 时，样本属于第一类，反之属于第二类。由此可见这转贴于 个数据集只需选择特征向量1，2，5即可。表2列出了所有特征向量的重要程度降序的排序。其Top1-Top6特征向量作为输入，相应的测试样本集的分类错误率在图1中给出。表2 Monk数据集特征向量排序215346 图1 Monk测试集错误率我们按照Weston5的方法生成了Weston数据集。此数据集共有10，000个样本，每个样本包含10个特征向量。其中只有f1，f2是与类属性相关的，其它的特征向量全部都是服从N（0，20）的随机噪声。而f1，f2分别服从和分布。在第一类中，。而在第二类中，。两类中的。因而这个数据集只需选择特征向量1，2即可。为了避免神经网络初始值等不确定因素的影响，此实验共运行30次。图2中给出了Top1-Top10特征向量作为输入，其30次平均的测试集分类错误率。表3列出了所有特征向量的重要程度最终的降序的排序。表3 Weston数据集特征向量排序12107845396图2 Weston平均测试集错误率由此可见，OMI能有效地可靠地并准确地对所有特征向量进行排序。5.2 真实数据集MOI特征向量选取方法在三个真实数据集Heart，Ionosphere和Waveform+noise 上进行测试。关于三个数据集的介绍见表4。表4 数据集介绍数据集名称HeartIonosphereWaveform noise训练集样本个数170200400测试集样本个数1001514600特征向量个数133440MLP二层节点个数1263第3部分所介绍Fisher Score，Leave-one-out，Maximum Output Information与OMI按各自的特征向量排序，而后Top1-TopN特征向量作为输入，其30次平均的测试集分类错误率在图3-图5中给出。同样为了避免神经网络初始值等不确定因素的影响，所有的方法在三个数据集上分别运行30次。图3 Heart平均测试集错误率图4 Ionosphere平均测试集错误率图5 Waveform noise平均测试集错误率由图5所示，OMI的方法得出特征向量排序要好于其它三个方法。尽管从上图可知OMI在某些Top特征向量的错误率要低于其它三个方法，但是通过t-test的分析可以得出四种方法在这些Top特征向量的错误率均值可近似看作是相等的。换句话说，这三个数据集的结果均表明MOI的选出的Top特征向量不差于其它三种特征选取方法选出的Top特征向量。就运行速度而言，Fisher Score最快，OMI次之，而Leave-one-out，Maximum Output Information由于嵌入式方法的特性，它们必须在排完一个特征向量后，重新训练MLP神经网络，所以，运行时间大幅增加。6 结论本文描述了一种基于互信息理论的特征向量选取的方法。由于具有足够的信息理论支持，这一新的特征向量排序的评价标准式主要有两种显著的优越性。首先，它可以最优地或接近最优地选出用户所需求的特征向量集。其次，这个特征向量集估计可以以集成化的方式有效进行。这第二个特性在高维数据集中尤为重要，因为它不需要任何人工的干预或调整。而我们的逐次增加的特征向量选取方案，避免了多变量密度估计。由于其过滤式特征向量选取的本质，此方法可以与所有的分类器算法相结合，来执行各种模式识别。在人造数据集和真实数据集的结果比较，表明OMI特征选取方法能够显著的提高分类精度降低运行时间。例如在神经网络中，复杂的神经网络结构使得在高维数据集变得无法有效地执行。而OMI特征选取可以有效地剔除高维数据集中不相关或冗余的特征向量。这将大大提高神经网络算法的性能。参考文献1A.L. Blum and P.Langley，“Selection of Relevant Features and Examples in Machine Learning，” Artifical Intelligence，vol. 97，pp. 245271，19972Vapnik，V.N.，Statistical Learning Theory. New York： Wiley3T.M.Cover and J.A.Thomas，Elements of Information theory. New York： Wiley，19914Guyon.I.，and Andre.E.，“An introduction to variable and feature selection，” Journal of Machine Learning Resear
