英语原文共 17 页，剩余内容已隐藏，支付完成后下载完整资料

利用排序方法和分类算法进行最优特征选择

Jasmina NOVAKOVIĆ, Perica STRBAC, Dusan BULATOVIĆ

摘要：本文对两个实际数据集的特征排序方法进行了比较。我们考虑了六种排序方法，可以分为两大类：统计的和基于熵的。采用IB1、朴素贝叶斯、C4.5决策树和RBF网络四种监督学习算法建立模型。结果表明，排序方法的选择对分类精度有重要影响。在我们的实验中，不同监督学习算法的排序方法在平衡精度方面给出了不同的结果。我们的案例证实，为了确保选择了具有最高精确度的特性子集，建议使用许多不同的指标。

关键词：特征选择，特征排序方法，分类算法，分类精度。

1.引言

特征选择可以定义为从原始的N个特征集合中选择M个特征的最小子集的过程，使特征空间按照一定的评价准则得到最优缩减。随着域维数的增大，特征的个数N也随之增加。寻找最佳特征子集通常是一个棘手的问题，许多与特征选择相关的问题已经被证明是NP-hard[1，2]。

特征选择是计算机科学中的一个活跃领域。自20世纪70年代以来，在统计模式识别[3,4,5]、机器学习和数据挖掘[6,7,8,9,10,11]方面，它一直是一个研究和开发的沃土。

特征选择是许多不同领域的一个基本问题，特别是在预测、文档分类、生物信息学和对象识别或复杂技术过程建模中[12,13,14,15]。具有数千个特性的数据集在此类应用程序中并不少见。对于某些问题，所有的特性可能都很重要，但是对于某些目标概念，通常只有一小部分特性是相关的。

特征选择减少特征空间的维数，删除冗余、无关或有噪声的数据。它的应用带来了立竿见影的效果：加快了数据挖掘算法的速度，提高了数据质量及其挖掘性能，提高了挖掘结果的可理解性。

特征选择算法可以分为过滤器[16,17]、包装器[1]和嵌入式方法[6]。过滤器方法依赖于分类算法评估所选特征的质量，而包装器方法需要应用分类器(应该针对给定的特征子集进行训练)来评估质量，嵌入式方法在学习最优参数时进行特征选择(例如，输入层和隐含层之间的神经网络权重)。

一些分类算法继承了专注相关特征而忽略不相关特征的能力。决策树是此类算法的一个典型例子[18,12]；多层感知器(MLP)神经网络对输入层具有较强的正则性，可以自动排除不相关的特征。这些方法也可以从独立的特征选择中获益。另一方面，一些算法对特征选择没有规定。K近邻算法是一类通过检索最近的训练实例对新实例进行分类的方法，它强烈地依赖于特征选择方法来去除噪声特征。

研究人员研究了特征选择的各个方面。搜索是研究特征选择[13]的一个重要课题，包括搜索起点、搜索方向、搜索策略等。另一个重要方面是如何度量特性子集[13]的优劣。有过滤器方法[5,20,21]，包装器方法[22,23,8]，最近还有混合方法[10,24]。根据数据中的类信息可用性，有监督的特征选择方法[25,7]和非监督的特征选择方法[26,27,14,8]。

本文的主要目的是通过实验验证基于熵和统计的不同分类器对分类精度的影响。20已经表明，对于不同的数据集和不同的分类器精度曲线没有最佳的排序指数，因为所使用的特征数的函数可能有显著的不同。要确保在实际问题中获得最高的精确度，唯一的方法是在从不同的排序指数获得的多个特征子集上测试给定的分类器。

本文结构如下：在下一节中，我们简要描述了大多数特征选择算法的一般架构。第3节包含了关于不同特性排序和特性选择技术的一般问题。第4节简要介绍了所采用的算法，即IB1、朴素贝叶斯、C4.5决策树和径向基函数(RBF)网络。第5部分是实验评价。最后一节讨论了取得的成果，一些结束语，以及有待处理的问题，我们打算在今后的工作中进行研究。

2.一般特征选择结构

从大多数特征选择算法中可以得到一个通用的体系结构。它包括四个基本步骤(参见图1)：子集生成、子集评估、停止准则和结果验证[7]。特征选择算法创建一个子集，对它求值，然后循环，直到满足一个结束条件[15]。最后，用分类器算法对实际数据进行了分类验证。

子集生成：子集生成是一个搜索过程，它生成用于评估的特性子集。候选子集的总数为2N，其中N为原始数据集中特征的个数，这使得穷举搜索在特征空间中不可行，即使是中等规模的N也不可行。非确定性搜索，如进化搜索，通常用于构建子集[28]。也可以使用启发式搜索方法。这些方法主要有两大类：正向添加[29](从一个空子集开始，我们通过局部搜索添加一个又一个特性)或反向消除(相反)。

子集评估：子集生成过程生成的每个子集都需要使用特定的评估标准进行评估，并就该标准与之前的最佳子集进行比较。如果发现它更好，那么它将替换之前的最佳子集。评估子集的一个简单方法是考虑分类器算法在运行子集时的性能，该方法被分类为一个包装器，因为在这种情况下，分类器算法被包装在循环中。相比之下，过滤方法不依赖于分类器算法，而是使用基于相关概念的其他准则。

3.特性排序和选择

3.1 信息增益

3.2 增益比

如式（4）所示，当需要预测变量Y时，通过除以X的熵对IG进行标准化，反之亦然。由于这种标准化，GR值总是落在范围内。表示X的知识完全预测了Y，表示Y和X之间没有关系。与IG相反，GR更倾向于值较少的变量。

3.3 对称不确定度

对称不确定性准则通过将IG除以X和Y[31]的熵之和来补偿IG固有的偏置。它的定义为：

由于校正因子2，SU接受值被归一化为范围。表示对一个特征的知识完全可以预测，而表示X和Y不相关。与GR类似，SU偏向于值较少的特性。

3.4 卡方属性评价

通过卡方（）测试选择特征是另一种非常常用的方法[32]。卡方属性评估通过计算卡方统计量相对于类的值来评估特征的价值。H0的初始假设是假设两个特征是不相关的，并通过卡方公式进行检验：

其中为观测频率，为期望(理论)频率。价值越大，反对假设的证据越多。

3.5 One-R属性评价

One-R是Holte[33]提出的一种简单算法。它为训练数据中的每个属性构建一个规则，然后选择错误最小的规则。它将所有数值特征都视为连续的，并使用一种简单的方法将值的范围划分为几个不相交的区间。它通过将“missing”作为一个合法值来处理丢失的值。

这是最原始的方案之一。它只基于一个特性生成简单的规则。虽然它是分类器的最小形式，但它可以用于确定基准性能，作为其他学习模式的基准。

3.6 Relief-F属性评价

Relief-F属性评估[34]通过反复采样一个实例，并考虑相同和不同类的最近实例的给定特征值，来评估一个特征的价值。该属性评估根据特性区分类的能力为每个特性分配一个权重，然后选择权重超过用户定义阈值的特性作为相关特性。权重计算是基于特征值不同的两个不同类的最近邻的概率和特征值相同的两个类的最近邻的概率。这两种概率的差异越大，特征越显著。本质上，这个方法是为一个两类问题定义的，通过将问题分解为一系列两类问题，可以扩展到处理多个类。

4.分类算法

分类算法是对数据集中每个特性进行排序的方法。使用不同的分类算法可以对结果进行验证。分类算法种类繁多，各有优缺点。没有一种单一的学习算法能最好地解决所有的监督学习问题。本文采用四种常用的监督学习算法，即IB1、朴素贝叶斯、C4.5决策树和径向基函数(RBF)网络来建立模型。IB1的优点是他们能够从非常小的数据集中快速学习。朴素贝叶斯分类器的优点是，它需要少量的训练数据来估计分类所需的参数（变量的均值和方差）。C4.5决策树具有多种优点：易于理解和解释，数据准备少，鲁棒性强，在短时间内处理大数据性能好。RBF网络也有许多优点，包括需要较少形式的统计训练，能够隐式地检测依赖变量和自变量之间的复杂非线性关系，能够检测预测变量之间所有可能的交互，以及多种训练算法的可用性。本节简要概述这些算法。

4.1 IB1

IB1是最近邻分类器。它使用标准化的欧氏距离来查找最接近给定测试实例的训练实例，并预测与此训练实例相同的类。如果多个实例到测试实例的距离相同(最小)，则使用找到的第一个实例。最近邻算法是最简单的学习/分类算法之一，已成功地应用于广泛的问题[35]中。

为了对一个未分类的向量X进行分类，该算法在给定的N组数据中对X的邻域进行排序，并使用K个最相似邻域的类标签来预测新向量X的类。具体来说，这些邻域的类使用X与其每一个邻域之间的相似性进行加权，其中相似性由欧氏距离度量度量。然后，在K个最近的类标签中，给X分配权重最高的类标签。

最近邻分类器的工作原理是基于这样一种直觉：一个实例的分类很可能与向量空间中邻近实例的分类最相似。与朴素贝叶斯等其他分类方法相比，最近邻分类器不依赖先验概率，当数据集不是很大时，最近邻分类器的计算效率较高。但是，如果数据集很大，每次距离计算可能会非常昂贵。这就需要使用PCA和基于信息收益的特征排序来降低数据维数，从而降低计算成本。

4.2 朴素贝叶斯

该分类器基于基本贝叶斯定理。它可以在分类任务[36]上取得较好的性能。朴素贝叶斯分类器通过假设给定类变量的特征是独立的，极大地简化了学习。更正式地说，这个分类器是由判别函数定义的：

其中表示特征向量，表示可能的类标签。

学习分类器的训练阶段包括估计条件概率和先验概率。这里的是通过计算属于类的训练实例，然后将得到的计数除以训练集的大小来估计的。类似地，通过简单地观察标记为类的训练子集内特征的频率分布来估计条件概率。为对一类未知测试向量进行分类，根据测试向量中存在的特征值，计算每个类的后验概率，然后将测试向量分配给具有最高概率的类。

4.3 C4.5决策树

构建决策树有不同的方法，但是它们都以树结构总结给定的训练数据，每个分支表示特征值和类标签之间的关联。其中最著名和最有代表性的是C4.5树[37]。C4.5树通过递归地对训练数据集进行分区来工作，这是根据特性值在分离类时的潜力进行的测试来实现的。决策树是从一组训练实例中学习的，通过一个迭代过程来选择一个特征并根据该特征的值分割给定的示例集。最重要的问题是，在决定分类时，哪些特征是最具影响力的，因此应该首先选择。同样的，信息增益被用来选择最有影响力的，直觉上被认为是最低熵(或最高信息增益的特征。该学习算法的工作原理是：（1）计算每个特征的熵度度，（2）根据熵最小的特征的可能值对样本集进行划分，（3）估计概率，方法与朴素贝叶斯方法完全相同。注意，虽然以贪婪的方式一次选择一个特性测试，但是它们依赖于以前的测试结果。

4.4 RBF网络

一种流行的前馈网络是RBF网络。RBF网络有两层，不包括输入层。每个隐藏单元本质上代表输入空间中的一个特定点，对于给定的实例，它的输出或激活取决于它的点与实例之间的距离（实例只是另一个点）。直觉上，这两点越接近，激活就越强。这是通过使用一个非线性变换函数将距离转换成相似性度量来实现的。通常将其宽度对于每个隐藏单元可以不同的钟形高斯激活函数用于此目的。隐藏单元之所以被称为RBFs，是因为在实例空间中，给定的隐藏单元产生相同的激活，从而形成超球体或超椭球。

RBF网络的输出层采用隐藏单元输出的线性组合，在分类问题中，通过sigmoid函数对其进行输送。该网络学习的参数为：（1）RBFs的中心和宽度，（2）用于形成隐层输出的线性组合的权值。

确定第一组参数的方法是使用集群，而不需要查看训练实例的类标签。采用简单的k-均值聚类算法，对每个类进行独立聚类，得到每个类的k个基函数。直观地说，生成的RBFs表示原型实例。然后，可以学习第二组参数，保持第一个参数不变。这包括使用线性或逻辑回归等技术之一来学习线性模型。如果隐藏的单位比训练实例要少得多，这可以很快完成。

RBF网络的一个缺点是，在距离计算中对每个特征的权值都是相同的。因此，它们不能有效地处理不相关的特性。

5.实验和结果

使用真实的数据集“Statlog（澳大利亚信贷审批）”和“Statlog(德国信贷数据)”用于测试，这些数据来自UCI机器学习数据库的存储库[38]。这些数据集用于比较不同数据的特征排序

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[20809]，资料为PDF文档或Word文档，PDF文档可免费转换为Word