基于层次聚类的支持向量机分类算法

李兵 田元 赵明华 李剑波

摘要

针对支持向量机在大规模样本学习时，学习速度慢，需要存储空间大等问题，提出了一种基于层次聚类的支持向量机训练算法，即在标准SVM向量算法中加入CURE聚类算法。该方法首先通过聚类方法从簇中选择分散的对象，根据一个收缩因子收缩或移动它们，从而产生最有可能成为支持向量的一组向量组成训练子集，接下来再用SVM训练方法构建一个最优SVM分类器。实验证明，该算法使SVM训练时间大为缩短，在不影响精确度的前提下使算法的效率得到大幅度的提高。

【关键词】支持向量机 聚类 CURE聚类算法

1 引言

支持向量机理论最早由Vapnik[1]提出，是一种基于统计学习理论中VC维理论和结构风险最小理论的通用学习方法。它可以解决小样本学习问题，而且对数据的维数、多变性不敏感，可以实现多种传统分类方法，能够较好地进行模型选择，并具有较好的推广能力。目前已经在许多智能信息获取与处理领域都取得了成功的应用[2]。

支持向量机的算法实现有赖于解决一个二次规划问题，当样本数目较多时，传统的二次规划方法及其软件在计算时间、占用内存和计算精度上都出现问题[3]。为了解决这些问题，国内外许多科研工作者投入很多的精力来解决如何快速有效的提高SVM的训练方法。

实际应用中支持向量在样本训练集中只占一小部分[4]，据此本文借用聚类算法能够有效减少非支持向量的特点，在分析其它类似算法的基础上，提出了基于层次聚类的支持向量机分类算法SVM-HC。该算法同传统的SVM训练算法相比不仅保持了SVM的训练精度，同时缩短了训练时间。

本文第一部分阐述支持向量机的基本原理;第二部分详细介绍基于层次聚类的支持向量机分类算法SVM-HC;第三部分介绍实验结果;第四部分为结论。

2 支持向量机原理

支持向量机最初用于数据分类问题的处理。下面针对训练样本集：两类线性、两类非线性两种情况分别加以讨论。

对于两类线性可分问题，已知：训练集包含1个样本点：

其中x_i是输入指标向量，或称输入、模式，其分量称为特征，或属性、或输入指标;Y是输出指标，或称输出。支持向量就是寻求一个平面ω·x+b=0，使得训练数据点距离这个平面尽量的远。这种极大化“间隔”的思想导致求解下列对变量ω和b的最优问题：

为求解原始问题，根据最优化理论，转化为对偶问题来求解：解上述问题后得到的分类规则函数是：

对于两类线性不可分问题，为第i个训练点（x_i，y_i）引入松弛变量（Slack Variable）ξ_i≥0，把约束条件放松到y_i{（ω·x_i）+b}+ξ_i≥1，i=1，…n（即“软化”约束条件）。显然ξ_i可以描述为训练集错划的程度。现在就有两个目标：希望超平面间隔最大，即（最大），又希望训练集错划程度尽可能小，所以引入惩罚参数C。在实际使用时，我们可以选择C来修改这两个目标的权重。这样新的目标函数成为：体现了经验风险，而‖w‖则体现了表达能力。所以惩罚参数C实质上是财经验风险和表达能力匹配一个裁决。当C→∞时，线性不可分的原始问题退化为线性可分。

对于非线性分类，通过引入核函数，将原空间样本数据通过非线性变换映射到高维特征空间H：Φ：R^d→H。在这高维空间中求最优或广义最优分类面。

常用的核函数为：

2.1 多项式核函数

2.2 RBF（径向基radial basis function）核函数

2.3 Sigmoid核函数

K（x，x_i）=tanh（b（x·x_i）-c），式中b，c為常数。

这样对于非线性分类问题，最终归结为一个二次规划问题：

3 基于层次聚类的支持向量机分类算法

目前，已经提出了很多基于聚类的算法的。文献[5]提出的算法可以有效减少训练次数，但对于出现两类点集交叉情况较多的时候，这种方法就会显示出它的缺陷[6]。文献[6]、[7]提出的算法可以有效解决该问题并且具有收敛速度快的优点。

上面提到算法擅长处理凸形分布、大小相近、密度相近的聚类，但对于处理形状比较复杂的簇还存在不足。另外，初始聚类中心的选择和噪声数据会对这些算法产生很大的影响。同时[6]、[7]的方法为了达到全局最优，会要求穷举所有的训练点，对于大数据量的训练集来说将是一个非常耗时的过程。本文受到这些算法的启发，借用CURE聚类算法[8]的思想提出了基于层次聚类支持向量机。

该算法的核心思想是：首先借用CURE聚类算法对数据集进行聚类，通过聚类算法减少非支持向量，从而提高支持向量的训练速度。关于CRUE聚类算法的原理，文献[8]有详细论述，本文不再叙述.

借用CURE聚类算法是因为该算法具有以下优点：

（1）它不用单个质心来代表一个簇，而是选择数据空间中固定数目的具有代表性的点。这些点是边界点和质心点的折衷，也就是说在尽可能减少训练点的基础上尽可能的发现任意形状的类，同时可以有效处理孤立点或噪点[9]。

（2）试验和分析表明[8]，适当数量的随机样本具备一定精度的关于簇的几何信息，因此该算法开始聚类时随机抽取一定数量的样本而不是所有样本进行聚类，这将会大幅缩短训练时间。

（3）通过收缩因子α和代表点的数量C就可以调节该算法的精度。当收缩因子α=1时，该算法就与[5]的算法性质相同，即基于聚类中心点的支持向量机算法;当收缩因子α趋于0时，该算法的性质接近[6]的算法，即基于聚类边界点的支持向量机算法。

下面介绍基于层次聚类的支持向量机分类算法：

Stepl：设置收缩因子α参数、随即样本S的数量以及划分聚类数量Ko

Step2：随机抽取S个样本，并将样本划分为p个部分，每个部分得数据量为S/p。

Step3：在每个划分中，划分S/pq？个局部聚类。

Step4通过随机取样去除孤立点或噪点。如果一个簇增长的太慢，去掉这个簇。

Steps：对局部聚类进行合并。对每个新生成簇代表点根据收缩因子收缩或向簇中心移动。

Step6：使用标准SVM训练算法寻找最优分类超平面

通过上述分析可以看出，如果减少收缩因子α，那么本文提出的SVM-HC算法在聚类阶段得到的代表点与文献[6]提出的SVM-DC算法在聚类阶段得到的边缘点都能精确反映簇的位置和形状。另一方面，SVM-DC算法的复杂度为O（n（mlogm+1¹）），而本文提出的SVM-HC算法复杂度为O（n（m+1¹））。这样可以看出，本文提出SVM-HC算法在保持训练精度的同时能够大幅缩小训练时间。

4 试验结果及分析

为了验证本文对基于聚类的支持向量机算法改进的有效性，在公共测试数据库UCIAdult和Web数据集上对SVM-DC算法、SVM-HC算法进行了五组测试。试验中SVM-HC算法的参数按照[8]的建议，即抽样数s=1，220;分区数p=50，代表样本点数c=10。综合考虑训练速度和训练精度，把SVM-DC算法中的参数设置为：ε=0.2，0=8，η=0.8。表1给出试验结果。两种算法均采用标准C++实现，使用RBF核函数：，用Microsott VisualC++6.0，缺省编译器优化选项进行编译。系统平台为2.66GHZ Pentium4处理器，Windows2000标准版，256MBRAM。所有算法均没有采取任何其它优化措施，核函数均为RBF核函数：其核参数的设置为：σ¹=10，C=1。

如表I所示，从试验结果可以看出，对于同一个样本数据集， SVM-HC利用寻找代表点时间短的优点，有效提高了支持向量机的训练速度，同时训练的精确度基本没有改变。SVM-HC训练精确度基本在SVM-DC精确度上下小幅浮动。根据理论分析和试验结果，可以得出SVM-HC的可行性和有效性：即该算法充分利用了CURE聚类算法的优点，在保证支持向量机训练算法精度没有降低的情况下，有效提高了支持向量机训练速度。

5 结论

本文首先介绍了目前几种基于聚类支持向量算法的优缺点。分析CRUE聚类算法的优点，通过借用其思想提出了SVM-HC算法。实验表明，这种方法在保持支持向量机训练精度不改变的情况下明显缩短学习时间。

参考文献

[1]Vladimir N.Vapnik.The Nature ofStatistical Learning Theory.Springer，New York，1995.

[2]SANCHEZ A D.Advanced support vectormachines and kernel methods[J].Neurocomput ing，2003，55（01）：5-20

[3]吴翔，谭李.提高大规模SVM训练计算速度的研究[J].模式识别与人工智能，2003，16（01）：46-49.

[4]Joachims T.Making Large-scale SupportVector Machine Learning Practical[A].B Scholkoph，C B urges，A Smola.Advances in Kernel Methods SupportVector Learning[C].Cambridge.MA：MITPress，1999，169-184.

[5]李曉黎，刘继敏，史忠植.基于支持向量机与无监督聚类相结合的中文网页分类器[J].计算机学报，2002，24（01）：62-68.

[6]武方方，赵银亮，蒋泽飞.基于密度聚类的支持向量机分类算法[J].西安交通大学学报，2005（12）.

[7]孔波，刘小茂，张钧.基于中心距离比值的增量支持向量机[J].计算机应用，2006（06）.

[8]Guha S，Rastogi R，Shim K.CURE：AnEfficient Clustering Algorithmfor Large Databases[C].Seattle：Proceedings of the ACM SIGMODConference，1998：73-84.

[9]Jiawei Ha n，Micheline Kamber.DateMining：concepts and Techniques [M].Copyright 2001 by Morgan KaufmannPublishers，Inc.，2001.

[10]Murphy P M，Aha Irvine D W.CA：University of California，Departmentof Information and ComputerScience[EB/OL].http：//www.ics.uci.edu/～mlearn/MLRepository.html，1994.