基于SMO算法的分类噪声检测外文翻译资料

本科毕业设计（论文）

外文翻译

基于SMO算法的分类噪声检测

出处：Optik 127(2016)7021-7029

摘要：SMO（Sequential Minimal Optimization）是一种出色的SVM算法，用于提高效率和内存要求。但是需要交叉验证来优化数学模型中的参数以避免过度拟合，这会产生过多的中值分类器，从而导致算法稳定性的降低和训练时间的显著增加。在本文中，通过引入“分类噪声”的概念，提出了CNSMO（基于SMO算法的分类噪声检测）。在CNSMO中，不可分割的问题可以转化为可分离的问题，因此不需要考虑过度拟合。这使得在整个算法中可以避免交叉验证，并且可以提高算法的稳定性。训练时间可以大大节省。可以消除CNSMO算法中的惩罚参数，使得CNSMO的模型比其他SMO算法简单得多。本文提出该算法可以在不降低预测精度的情况下显著缩短训练时间。通过对公共数据集的实验证明了CNSMO的有效性和效率。

关键词：SMO;CNSMO;分类噪音;相对密度;SVM;交叉验证

1. 简介

支持向量机是一种相对较新的分类和回归工具[1]。它已被应用于许多领域。SVM的原始模型是通过最小化结构风险而不是先前方法所基于的经验风险进行的凸优化，这使其能够提出全局解决方案。这意味着它在普遍性方面具有良好的性能。但是，原始模型的时间复杂度大于。此外它需要计算内核矩阵，其维度等于训练样本的数量，保证需要非常大的内存。为了克服这些问题，已经提出了改进的算法。¹

Suykens和Vandewalle提出了最小二乘支持向量机（LS-SVM）[2]。LS-SVM使用平方误差而不是传统SVM使用的不等式约束。结果，二次问题被转换为线性系统，从而可以加速SVM。特别是在近似线性和小规模数据集中，LS-SVM可以实现比包含统计算法，基于决策树的算法和基于实例的学习方法的各种方法更好的性能。然而，LS-SVM仍然需要计算阶矩阵，其中是训练样本的数量。为了解决大规模问题，Suykens [3]提出了一种基于共轭梯度（CG）的迭代训练算法。Chu [4]提出了一组简化的函数估计线性方程组。Chua提出了一种基于Sherman-Morrison-Woodbury（SMW）矩阵的算法[5]。通过选择违反KKT最优性条件的一对样本，Zeng[6]提出了SMO（序列最小优化）算法。此外，在[7]中提出了二阶SMO算法。在该方法中，使用双重函数的二阶近似信息来搜索第二索引，从而可以显着减少迭代次数。徐建华[8]提出了Rank-SVMz的随机块坐标下降法（RBCDM）。在每次迭代中，整个QP问题被分成一系列小规模QP子问题，然后每个QP子问题具有单个等式约束和许多盒子问题可以通过二进制SVM中使用的SMO来解决。Xia和Xiong使用距离到超平面来提取包含支持向量的子集[9]。该子集替换了要训练的整个数据集。这些方法可以在一定程度上提高SVM的性能。但是，它可能会丢失一些支持向量并降低预测精度。这些迭代算法可以解决大规模分类和回归问题。但它们都依赖于交叉验证来优化除拉格朗日乘数之外的参数，以避免过度拟合。

分类问题中的噪声数据可能导致过度拟合，这可以通过交叉验证来避免[11]。但是，交叉验证可能会大大降低培训效率并降低培训过程的稳定性。Xia和Xiong提出了分类噪声的概念来描述分类问题中的噪声数据，并使用相对密度模型来检测它[10]。通过检测和消除分类噪声，SVM算法可以大大提高性能[11]。

本文结合分类噪声检测，提出了一种新的SMO算法CNSMO。在CNSMO中，有效地发现分类噪声并消除分类噪声，使得原始不可分离数据集可以有效地转换为可分离数据集，并且可以消除惩罚参数C。因此，可分离SMO的训练不需要交叉验证以避免过度拟合。通过这种方式，可以显著提高CNSMO的效率。 此外，由于消除了惩罚参数C，因此CNSMO的模型比SMO的原始模型简单得多。

1. 用于CSVM的SMO算法（C-支持向量机）

C-支持向量机

给定训练集，其中是训练样本数据，是用于分类的对应标签。 引入映射函数将输入空间转换为Hilbert空间：

通过该映射函数可以将下雨样本映射到Hilbert空间。 线性数据集中的原始问题可以表示如下：

，其中是松弛变量以放松约束，是避免过度拟合的惩罚系数。表示存在异常值的惩罚项。假设希尔伯特空间中的内部函数是，然后问题(2)变为：

当在问题(3)中足够大时，拉格朗日乘子的上界消失，从而将问题(3)转化为可分离的问题。决策函数可表示为：

，其中，是拉格朗日乘子的最佳解。支持向量是拉格朗日乘数大于0的那些样本。

SMO算法

SMO的本质是每次更新两个参数。为了更新表达式(2)中的两个参数和，其他参数被认为是常数。 模型(2)可以转换成如下：

,其中

1. CNSMO（基于SMO算法的分类噪声检测）算法

分类噪声和检测

提出分类噪声[9]来描述分类问题中的噪声数据。

定义1：分类噪声

分类噪声：在数据库中，两个标签中的一个分配给中的每个点，标签分配给。在监督分类任务中，训练所有点，并获得分类器. 如果明显被标记为的点包围，则被认为是分类噪声。此外，当我们使用分类器来预测时，如果被赋予其事实标签（即），则分类器的普遍性会恶化。

提出了“相对密度”用于有效分类噪声检测[10]。

定义2：绝对密度：

给定数据库，对于每个对象和，其中表示对象和对象之间的距离，对象的-最近邻域可以表示为其中。 对于，的绝对密度定义为绝对密度。

定义3和4：异构和同质k-最近邻

给定数据库，可以分为两个可能的类：和。 对于每个对象，的齐次-最近邻可以表示为，使得。的异质-最近邻可以表示为，使得。

定义5：相对密度

给定数据库，可以分为两类：和。给定对象，的相对密度可以定义为：

对于点，如果相对密度大于1，则点可以被认为是分类噪声。

CNSMO

分类噪声影响平滑度，增加决策曲线的弯曲程度，并进一步降低算法的普遍性。因此，在训练之前有效地发现和消除分类噪声对分类器非常有益[11]。通过消除分类噪声，原始数据集被转换成可分离的。基于，不需要惩罚参数，使得原始SMO可以简化为可分离版本。

由于约束中的等式，。然后，

，在时。

当等于时，等式(4)可以转换为：

因此，上限。 下界.当不等于时，可以将等式（4）转换成

因此，上限。 下限。 模型(2)中的目标函数可以转化为

，其中是常数，。

当时，等式(5)可以转换成如下：

函数的推导可以表示如下：

以类似的方式，

等式(9)右侧的参数都是旧的。 从而，

从模型(2)，偏差可以设置为

在CNSMO中，一个不可分割的问题可以转化为可分离的问题，因此不需要考虑过度拟合。这使得在整个算法中可以避免交叉验证。这是现有SVM方法都没有的优点。

为CNSMO设计的算法可描述如下：

算法1：

1. 归一化数据集中的所有数据点，并使用算法1和等式(3)计算所有数据点的所有相对密度值;
2. 按相对密度值的降序对所有数据点进行排序;

3）相对密度值远大于1的那些数据点被认为是分类噪声并被消除。

4）在零上随机初始化所有拉格朗日乘数;

5）选择两个在极端情况下打破KKT规则的乘数;

6）使用等式(10)更新两个选定的参数;

7）如果所有数据点都没有破坏KKT规则，则终止; 否则转到第5步。

CNSMO的效率改进

假设所有实验中使用的内核都是径向基函数：

罚分参数和分别在到的范围内，产生包含17 * 17个点（即289）的网格。以五个交叉验证为例，交叉验证需要验证289 * 5（即1445）组参数。但是，在CNSMO中，可以避免交叉验证。在将参数设置为最大值28之后，仅需要验证与的不同值对应的17组参数。因此，理论上可以节省90％以上的训练时间。

1. 实验

在本节中，将CNSMO与两种众所周知的算法进行比较：LibSVM [12]和DTSVM [13]。LibSVM是支持向量机的集成软件。DTSVM是另一种快速支持向量机，具有决策树和Fisher线性鉴别器,于2014年提出。它结合了投影方法和随机梯度下降方法。所有实验都在具有以下功能的计算机上实现：Intel I5-2450处理器，4 GB RAM，Window7操作系统。算法部署在MATLAB 2014a中。在这些实验中使用的所有数据集被分成两部分：随机选择整个数据集的80％数据点训练和其余部分用于预测。所有实验中使用的内核都是径向基函数：

，其中通过各种方法的交叉验证来选择。

数据集

在本文中，我们的方法与九个公共可用数据集上的其他方法进行了比较。 它们是声纳，糖尿病，乳腺癌，四级，Svmguide1，Svmguide3和Cod-RNA。

表1中显示了实验中使用的数据集的概要。

表1 实验中的数据集

选定的参数

表2显示了实验中每个数据集使用的参数值。当CNSMO在消除了分类噪声的数据集上运行时，CNSMO中的所有参数都是通过算法1进行的优化。在LibSVM和DTSVM中，包括惩罚参数的参数值通过交叉验证来选择，这是广泛应用于文献[14-15]。

可以观察到，CNSMO中的惩罚参数的值总是被设置为最大值（即256）。 原因在于，消除了分类噪声，使得数据集具有良好的可分离性。较大的值不会限制拉格朗日参数的范围，从而产生具有良好普遍性的决策曲线。

训练过程中的表现与预测准确性的比较

LibSVM，DTSVM和CNSMO算法的性能如表3所示。训练时间包含通过交叉验证搜索最佳参数的时间成本。由于在CNSMO中消除了分类噪声，所以在表3中所有数据集的训练精度达到100％。可以观察到在小数据集和大数据集中训练时间最小。原因在于，在CNSMO中消除了惩罚参数，使得模型更简单并且网格搜索的次数比其他更小。此外，消除了分类噪声，从而避免了CNSMO中的交叉验证。这些优势使C

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

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

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