—47—
王国胜
(1. 德州学院计算机系，德州 253023；2. 北京邮电大学信息工程学院，北京 100876)
摘 要：分析NPA 训练算法，指出其不足并提出改进措施。在第1类子循环的前半阶段采用Gilbert 迭代，后半阶段采用NPA 迭代，并提出界定这2个阶段的方法，利用中间计算结果优化了第2类子循环中的迭代过程。在不增加计算量的条件下，提高了算法收敛速度。基于该算法开发的自动分类模拟系统获得了较好的分类结果。 关键词：数据挖掘；支持向量机；NPA 算法；分类磷化铝
Research on Data Mining Based on Support Vector Machine
WANG Guo-sheng
(1. Computer Department of Dezhou University, Dezhou 253023;
2. College of Information Engineering, Beijing University of Posts and Telecommunications, Beijing 100876)
【Abstract 】This paper investigates the NPA algorithm suggested by Keerthi et al commonly used in support vector training, points out its defects,and presents a modification. It takes Gilbert iteration in the early stage of type-Ⅰloop and NPA iteration in the later stage, and proposes a strategy of how to determine these two stages. It optimizes the NPA iteration in type-Ⅱloop by employing previously obtained computation results. In comparison with NPA, the modified version results in a remarkably accelerate convergence without increasing in computational complexity. By virtue of it, an experimental automated classifier is developed, which shows satisfactory performance. 【Key words 】data mining; support vector machine; NPA algorithm; classification
计 算 机 工 程Computer Engineering 第34卷 第8期
Vol.34 No.8 2008年4月
April 2008
·软件技术与数据库· 文章编号：1000—3428(2008)08—0047—03
文献标识码：A
中图分类号：TP181
1 概述
随着数据库技术的迅速发展以及数据库管理系统的广泛应用，积累的数据越来越多。激增的数据背后隐藏着许多重要信息，人们希望能够对其进行更高层次的分析，以便更好地利用这些数据。目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，不能根据现有的数据预测未来的发展趋势。由于缺乏挖掘数据背后隐藏的知识的手段，因此出现了“数据爆炸但知识贫乏”的现象。数据挖掘在技术上的含义是，从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。
从广义上理解，数据、信息也是知识的表现形式，通常把概念、规则、模式、规律和约束等看作知识，而把数据看作是形成知识的源泉。数据挖掘的任务包括[1]：
(1)自动预测趋势和行为。从历史和当前的数据中发现规律性的东西，对未来的发展趋势和行为做出合理的预测。
(2)分类。根据数据的特征，把它划归到事先确定的若干类的某一个之中。
(3)聚类。如通常所说的“物以类聚”，把一组个体按照
相似性归成若干类别。同一类内部的数据具有较高的相似度，不同类之间的数据差别较大。聚类的目的是挖掘数据潜在的自然分组结构和关系。
(4)关联分析。若2个或多个变量的取值之间存在某种规律性，就称为关联。 它反映一个事件和其他事件之间依赖或关联的知识。关联可分为简单关联、时序关联、因果关联。关联分析的目的是出数据库中隐藏的关联网。
(5)概念描述。对某类对象的内涵进行描述，并概括这类对象的有关特征。概念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述不同类对象之间的区别。
数据挖掘的常用技术有[1]：人工神经网络，决策树，遗传算法，规则推导等。数据挖掘系统的构成如图1所示。
本文将支持向量机应用于数据挖掘。支持向量机是一种通用的学习机，作为机器学习的主流技术之一，按照该技术方案构建的数据挖掘系统通用性好，在此基础上构建数据挖掘系统具有先进性。
2 支持向量机
支持向量机属于人工智能中的计算学习范畴，是20世纪
90年代中期发展起来的机器学习技术[2-3]
，与传统的学习技术相比，它有坚实的理论基础，从大量应用看，性能优越，在手写体数字识别、文本分类等多个具体问题上创造和保持着最好记录，涉及模式识别、回归估计、数据挖掘、信息检索、智能信号处理、智能控制、非线性模式重建等领域。
支持向量机的理论基础是统计学习理论，有严密的数学
基金项目：山东省教育厅科技计划基金资助项目(J03P52)
2 8原则作者简介：王国胜(1966－)，男，副教授、博士研究生，主研方向：模式识别，计算智能
收稿日期：2007-04-30 E-mail ：wgs@dzu.edu
—48—
基础。该理论的研究始于20世纪60年代末，此后近30年时间里，前苏联学者Vapnik 做了大量开创性、奠基性的工作，提出了“结构风险最小化”原理。这个时期的工作主要是纯理论性的。1995年，文
献[2]首次提出支持向量机，它是“结构风险最小化”原理的实现。依此原理，不但能很好地拟合已知的训练数据，还能很好地拟合未知的、尚未出现的数据，两者兼顾，因此有很强的泛化能力。支持向量机本质上是一种非线性的数据处理方法。
本文讨论具二次惩罚项的支持向量机。设k x 表示输入向量，F 是特征空间(高维内积空间)，特征向量k F ∈z ,
()k k Φ=z x ，Φ是特征映射。核函数(,)()()k l k l K ΦΦ=⋅x x x x ，
其中，“.”表示F 中的内积。设1{}m k k =x 是训练集，,I J 分别是第1、第2类模式的指标集，,,{1,2,,}I J I J m φφ≠≠∪=⋅⋅⋅。{k z }线性可分(Non-Violation)时与支持向量机相关的优化问题是
min 1/22
w
s. t. 1,;1,i j w b i I w b j J ⋅+∀∈⋅+−∀∈≥≤z z
{k z }非线性可分时，采用二次惩罚(Violation- Quadratic)，相关的优化问题是
min 1/22
22k k
c
w ξ+
∑ s. t. 1,;1,i i j j w z b i I w z b j J ξξ⋅+−∀∈⋅+−+∀∈≥≤
设,(1,2,,)i i m α=⋅⋅⋅是其对偶问题的解，若0i α≠，称相应的i x 为支持向量。判别函数sign[(,)]i i i i x SV
y y k x b α∈=+∑x ，称为
支持向量机。
支持向量机由训练样本与核函数刻画。支持向量机示意图见图2。
输出空间
特征空间
输入空间
K (x 1, x )
(a)支持向量机原理 (b)支持向量机结构
图2 支持向量机示意图
支持向量机具有以下功能：分类(识别)，预测，聚类，
异常检测(新颖性检测)，密度估计等。支持向量机的工作方式如下：(1)收集训练样本，选择核函数；(
2)利用训练算法，自动构造出支持向量机；(3)把未知的(新出现的)数据输入支持向量机，根据输出进行识别、预测等。
3 支持向量机训练算法
支持向量机的训练归结为解二次规划问题，但该问题的Hessian 矩阵通常是稠密的，所以处理大规模问题时存储代价很高，例如当样本个数达4 000时，128 MB 的内存就不够了，因此经典的优化方法不适用。开发耗时短且占用内存少的算法成为追求的目标。1998年，文献[4]提出一个迭代算法，称为SMO 算法(Sequential Minimal Optimization)，基本思想是运用分解法，把一个大的二次规划问题，分解成一系列小的子问题。
2001年，文献[5]提出NPA 算法(Nearest Point Algorithm)，它基于以下事实：支持向量机的优化问题等价于2个凸多面体之间的最近点问题。Keerthi 等人的工作是把求最近点问题的Gilbert 算法和MDM 算法[6-7]结合在一起。NPA 与SMO 相比，训练速度更快。通过分析发现，NPA 算法在设计上有几个不合理之处，影响了算法的速度。对此，本文提出了相应的改进措施，改进后的训练速度显著提高。
3.1 NPA 算法的主要思想及存在的问题
NPA 算法每轮循环由2个检验环节和1个迭代环节构成。首先进行第1类检验，在非支持向量中寻不
满足终止条件的指标k ，第2类检验在支持向量中寻不满足终止条件的指标k ，如果在某个检验过程中到了这样的k ，则进入迭代环节；之后进入下一轮循环。如此继续，直至某轮循环中不到不满足终止条件的指标k 为止。为减少计算代价，每轮循环中只进行1次第1类检验，而第2类检验连续进行多次直到支持向量中不存在不满足终止条件的k ，或检验次数达到某个预先设定的阈值为止，即在支持向量上再形成一个子循环。这一点对提高算法的整体性能非常重要。
NPA 算法的迭代环节分以下4
种情形(见图3)分别进行不同的处理，详见文献[4]。
C
(a)情形1 (b)情形2 (c)情形3 (d)情形4
图3 迭代环节的4种情形
笔者用NPA 算法做了大量实验，结果显示，随着惩罚系数逐渐增大，第2类检验及其迭代的累积次数几十倍几百倍地增加，而第1类检验及其迭代的累积次数却相对稳定。这说明第1类检验主要集中在整个学习过程的初始阶段，其余大部分时间消耗在第2类检验及其迭代环节上。在这种情况下，2类检验下共用同一个迭代过程并非上策。如果把第2类检验下的迭代过程进一步优化，NPA 的性能将得到改善。在第2类检验中，虽然进行了更细致的计算，获得了更多信息，但在其后的迭代过程中，并没有把这些信息全部利用 起来。
3.2 改进措施
rvd改进措施针对2类检验下的迭代过程。
(1)第2类检验下的迭代过程。在情形3中，之所以选择求线段uA 和vD ′之间的最近点，一方面是为了保证u v −呈下降趋势，另一方面是及时去掉V 中不必要的支撑向量(如D )，然而这样做并不能有效地去掉V 中不必要的支撑向量。
需要注意的是，D ′的凸组合中不含D ，而B 在某种意义上比v 更靠近U ，B 在第2类检验中既已求出，若把D ′和B 两点连接起来，则线段D B ′上的点既与D 无关又与U 靠近，所以用D B ′代替vD ′(如图4所示)。但是这样不能保证u v −连续下降，无法保证算法的收敛性。笔者把原来的情形3的
处理修改成：计算v 到线段uA 的最近点u
和最近距离1d ，u 到线段D B ′的最近点v
和最近距离2d ，如果12d d <，令u u
= (v 不变)；否则v v = (u 不变)。同理在情形4，如图5所示，计算u 到线段vB 的最近点v 和最近距离1d ，v 到线段C A ′的最近点u
和最近距离2d ，如果12d d <，令v v = (u 不变)；否则u u
= (v 不变)。
C
B
图4 情形3的处理图5 情形4的处理
(2)第1类检验下的迭代过程。这里提出粗处理与细处理
相互配合、各取所长的思想。事实上，NPA算法中使用的迭
代比Gilbert或MDM迭代细致得多，它总是试图到距离更
小的两点u和v，这种细处理手段在算法运行的后期即,u v接
近*,*gmd
u v时非常必要，但在初始阶段并不适合。每轮循环中首
先在非支持向量中进行一遍第1类检验和迭代，其目的之一
是做粗略的过滤，为后面的细处理勾画一个大致的轮廓，NPA
算法没能充分考虑并利用初始阶段与后期的不同特点，处理
手段单一。在初始阶段过分追求细节，反而事倍功半。
因为Gilbert算法非常简单，具有在初始阶段收敛快的特
点，所以在第1类检验下，在初始阶段应选择Gilbert迭代，
但在后半阶段Gilbert算法收敛缓慢且每进行一次检验要付
出很高的计算代价，不宜再使用，最好选择NPA迭代过程。
4 实验比较与模拟
4.1 实验比较
算法用C++语言实现，使用Visual C++ 6.0编译，在AMD
Duron 750 MHz微机上运行，内存128 MB 。使用与文献[5]
相同的3组标准样本数据：Checkers[5], Adult_1和Adult_4[4] ，
采用高斯核函数22
(,)exp(0.5/)
i j i j
Kσ
=−−
x x x x，实验参数
2
σ、训练样本的维数n和样本容量m见表1。
表1实验参数
2
σn m
Checkers 0.
5 2 465
Adult_1 10. 0 123 1 605
Adult_4 10. 0 123 4 781
针对不同的惩罚系数c ，实验进行了若干次，训练初值
取每类在训练集中第1个出现的样本。实验除考察训练时间
T(CPU时间：s)之外，还有支撑向量机的margin和支撑向量
个数#SV。对相同的c ，改进的NPA与NPA得到几乎相同
的margin和#SV，因此，这2项结果未在此列出。训练时间
T有明显差别，具体结果见表2。
表 2 Checkers比较结果
c 0. 03 0. 1 0. 2 0. 3 0. 6 1. 0 2. 0 3. 0 5. 0 10 50 100500103
NPA/s 72 68 72 71 79 87 93 102 116 143 238 320509634江西城市学院
改进的
NPA/s
56 57 59 58 65 64 80 76 90 96 214 251351463
表3 Adult_1比较结果
c 10 50 100 500 103 104 105 106 107108
NPA/s 2 3 5 10 1328 56 83 6685
改进的
NPA/s
2 3 3 8 1221 39 37 4443
表4 Adult_4比较结果
c 0. 03 0. 1 0. 2 0. 3 0. 6 1. 0 2. 0 3. 0 5. 0 10 50 100500103
NPA/s 586 573 636 688 808 861 949994 1181 1519 3158 3957865212449
改进的
NPA/s
542 486 520 547 833 696 837845 852 1152 2438 306866099555
从实验结果看出，与NPA相比，新算法在没有增加计算
复杂度的情况下(在惩罚系数相同时)得到几乎相同的支持向
量个数，训练时间却减少了。在惩罚系数较小时，平均训练
时间减少了20%，惩罚系数增大时减幅达30%左右，效果显
著。每组实验都呈现同样特点，说明新算法的性能是稳定的。
4.2实验模拟
根据上述算法开发了模拟系统，可以实现对两类不同数
据的自动分类。通过点击鼠标的方式来输入训练数据，即屏
幕上的点，其中“小方框”属于第1类，“圆圈”属于第2类
(如图6所示)。训练后，曲线把两类模式自动划分开。图中
实心数据是支持向量，它们是一些关键数据。从图中看出，
分类结果令人满意。
(a)分类结果1 (b)分类结果2
(c)分类结果3 (d)分类结果4
图6 支持向量机自动分类模拟实验
5 结束语
支持向量机是当前机器学习领域的一个研究热点，它不
仅能用来分类，还能够进行预测和新颖性检测等，与其他方
法相比，具有泛化能力强、结构简单等优点。支持向量机训
练算法是支持向量机的关键技术之一，是应用的前提，支持
向量机中的其他问题，如模型选择也与训练算法有关，研究
支持向量机训练算法，既有理论意义又有应用价值。本文提
出的训练算法在没有增加计算复杂度的条件下，提高了训练
速度。所开发的模拟系统，很容易转化成实用的数据挖据
系统。
参考文献
[1] Han Jiawei, Kamber M. Data Mining: Concepts and Techniques[M].
San Diego, CA, USA: Academic Press, 2001.
[2] Vapnik C V. Support Vector Networks[J]. Machine Learning, 1995,
20(2): 273-297.
[3] Vapnik V. The Nature of Statistical Learning Theory[M]. New York,
USA: Sprinter-Verlag, 1995.
[4] Platt J C. Fast Training of Support Vector Machines Using
Sequential Minimal Optimization[M]. Cambridge, MA, USA: MIT
Press, 1998: 185-208.
[5] Keerthi S S, Shevacle S K, Bhattacharyya C, et al. A Fast Iterative
Nearest Point Algorithm for Support Vector Machine Classifier
Design[J]. IEEE Tran. on Neur. Networks, 2000, 11(1): 124-136.
[6] Gilbert E G. Minimizing the Quadratic Form on a Convex Set[J].有机锡化合物
SIAM J. of Contr., 1966, 4(1): 61-79.
[7] Mitchell B F, Demyanov V F, Malozemov V N. Finding the Point of
a Polyhedron Closest to the Origin[J]. SIAM J. Contr., 1974, 12(1):
19-26.
—49—
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议