浅谈采样基于分层聚类及重采样大规模数据分类

论文导读：选取策略聚类是无监督学习算法的典型代表之一，它能够按照一定的要求和规律对数据集进行区分，把一个没有类别标记的数据集划分成若干个子集，使相似的数据尽可能地划分到同一子集中。聚类在大规模数据约简中具有广泛的应用。为了约简大规模数据集，同时保证数据集的信息含量，即挑选出最具代表性的训练样本点，本文提出了
摘 要：针对大规模数据的分类问题，将监督学习与无监督学习结合起来，提出了一种基于分层聚类和重采样技术的支持向量机（SVM）分类方法。该方法首先利用无监督学习算法中的kmeans聚类分析技术将数据集划分成不同的子集，然后对各个子集进行逐类聚类，分别选出各类中心邻域内的样本点，构成最终的训练集，最后利用支持向量机对所选择的最具代表样本点进行训练建模。实验表明，所提方法可以大幅度降低支持向量机的学习代价，其分类精度比随机欠采样更优，而且可以达到采用完整数据集训练所得的结果。
关键词：海量数据； 分类； 聚类； 重采样； 支持向量机
0 引言
由于较高的分类精度和良好的泛化能力，基于统计学习理论的支持向量机（Support Vector Machine， SVM）是最有效的分类方法之一。然而，近年来随着社会网络的发展与计算机技术的不断进步，人们能够获得的信息量与日俱增，比如各种大型视频库、图像库、语料库等，其数据规模越来越大。要分类规模如此庞大的数据集，支持向量机在学习过程中需要占用大量内存，寻优速度非常缓慢，因此支持向量机对大规模数据集训练速度慢的瓶颈凸显出来。
为此，学者们进行了大量的研究，试图解决支持向量机对大规模数据集训练速度慢的瓶颈，其方法大致可以分为两类：一类是改进SVM求解算法，比如，Chen等[3]通过引入分而治之的思想，采用序列最小优化算法将SVM的二次规划问题分解为多个子问题，以期提高SVM的训练速度；Huang等[4]结合人工神经网络算法来简化SVM的训练过程；Dong等[5]引入了并行优化步骤，用块对角矩阵近似代替原始的核矩阵，从而加快SVM训练速度。这些方法在某种程度上确实提高了样本训练速度，但对于大规模数据集依然不是很理想。另一类方法是借助一些其他算法来缩减数据规模，约简训练集，比如基于随机采样的SVM算法、基于聚类的SVM算法[6-8]；Cervantes等[9]将聚类与SVM相结合，计算每一类的质心并作为此类的代表样本点，提出了基于最小内附球的SVM快速训练算法；陈光喜等[10]针对SVM对大规模数据集训练速度慢的瓶颈，提出了一种聚簇消减数据集方法。但这些方法在缩减数据规模的同时，忽略了数据样本本身的分布特性，可能导致被选择的分类样本信息含量减少，从而影响分类精度。
本文采用约简训练集的算法思想，提出一种新的学习策略：首先利用kmeans聚类算法将大数据集划分成K个规模减小了的子集，对于各个子集，基于其分布密度，按照某种规则对各个子集块中的每一类进行模糊C均值（Fuzzy CMeans， FCM）聚类，选取出类中心邻域内的样本点进行SVM训练建模。该方法在遵循减少样本点数量的前提下，最大限度地保证了训练数据集的信息含量，同时还加入了原数据样本点的分布信息，将各类样本在原数据分布中的重要性考虑进来。实验结果表明，该方法在保证分类精度的基础上提高了SVM的分类速度。
1 基于分层聚类及重采样的数据分类方法

1.1 基于分层聚类与重采样的样本选取策略

聚类是无监督学习算法的典型代表之一，它能够按照一定的要求和规律对数据集进行区分，把一个没有类别标记的数据集划分成若干个子集，使相似的数据尽可能地划分到同一子集中。聚类在大规模数据约简中具有广泛的应用。
为了约简大规模数据集，同时保证数据集的信息含量，即挑选出最具代表性的训练样本点，本文提出了基于分层聚类与重采样的样本选取方法。基本思想包括两部分：首先，利用kmeans算法将数据集D划分成K块，每一块都是D的子集，即有D=D1∪D2∪…∪DK，且Di∩Dj=（i， j=1，2，…，K， i≠j）。其次，对于每个子集Di，根据其样本分布特性，采用基于密度的FCM算法，对其所含的每一类样本（不妨设为第j类）进行聚类，选出各类中心邻域内的样本点作为第i个子集块Di中第j类的候选训练样本，并将其加入到新的训练集中。
本文提出的样本选取策略的关键在第二步，即采用基于密度的FCM算法来选取适当的样本进行训练。为了更好地选取样本，本文需要解决两个问题：其

一、确定每个子类中选取的样本数；其二，确定类中心邻域。首先给出类中心邻域的定义。

定义1 类中心邻域。对于给定的某个样本类，类摘自：毕业论文格式范文{#G论文导读：持向量个数少于方法一和方法二。在训练时间上，方法一和本文方法都采用了采样策略，训练时间明显少于方法二。由于本文方法运用了分层聚类重采样的策略，因此在训练时间上要高于应用随机采样策略的方法一。总的来说，在训练样本数相同的情况下，分层聚类重采源于：毕业设计论文总结www.7ctime.com样算法的分类精度明显高于随机采
etFullDomain}
中心标记为v，mean_dist表示类间样本平均距离，则以v为中心，mean_dist为半径的圆形区域，称为类中心邻域。落在其邻域内的样本点的数目称为类中心密度，记为density（v）。density（v）计算如下：
明确了类中心邻域后，算法还需确定每个子类中选取的样本数。显然，为了保证提出方法的有效性，所选取的样本不仅要包含丰富的信息，而且还要尽量不影响数据的分布特性。为此，给出了第i个子集Di中第j类应选取的样本数li j为
其中：n为数据集D的样本总数，nt为预选取的训练样本数，mi j为第i个子集Di中第j类的样本数目。在对子集Di的第j类进行FCM聚类时，如果样本数目足够多，则以式（2）计算所得的li j为聚类数。显然，这个聚类数是根据样本分布特性自适应选取的。在第j类进行FCM聚类后，将形成li j个聚类中心，把每个聚类中心邻域内的density（v）个样本点都加入到候选训练集中。
图1和图2以wine数据集为例，对比说明了上述处理前后的数据分布情况。利用本文方法从wine数据集中选取了60个样本。从图2可以看出，经过本文的选取方法，不仅有效地减少了训练样本的数量，同时还较好地保持了数据集的原始分布信息。

1.2 算法描述

给定一个包含n个样本的数据集D，根据上述的思想，本文提出了一个基于分层聚类与重采样的SVM分类算法，具体描述如算法1所示。
2 实验结果与分析
2.1 实验环境及数据集 为了分析提出的样本选择策略的有效性，将本文方法与随机采样和无采样进行了实验对比，分类方法都基于LIBSVM工具箱[11]实现。在实验中，对SVM的参数c和g使用网格搜索法进行寻优，寻优范围设置为[2-10， 210]。为了实验对比，三个算法均通过5折交叉验证方法获得其均值，且事先为每个数据集选用了相同的测试集。对于分层聚类中的FCM算法，本文将其模糊因子设置为2。

2.2 实验结果与分析

首先给出了本文方法的一些实验结果，如表2所示，分别给出了预选取的训练样本数，经过本文算法后实际选取的训练样本数，在获取最好分类精度时kmeans划分的块数、支持向量数和分类精度。
其次，将本文方法与随机采样和无采样进行了实验对比，实验结果如表3所示。其中随机采样方法是按照一定的比例从大规模数据集中随机选取样本，然后再用SVM进行训练和测试，称为方法一；无采样方法是指不对
原始训练样本进行采样，而直接用SVM进行训练和测试，称为方法二；本文方法先基于分层聚类重采样，然后再用SVM进行训练和测试。表3给出了三种方法的支持向量数、分类精度和训练时间三个指标。对于分层聚类重采样，本文选取kmeans划分不同块数实验结果的平均值，对于letter、adult、covtype*三个大规模数据集，采用完整训练集直接进行SVM训练时，时间代价远远大于另外两种方法，这里不列入对比，以“—”表示。
从表3中可以发现，本文方法除了在statlog数据集上的分类精度略差于方法二之外，在其他5个数据集上都得到了较好的分类精度。在支持向量个数方面，本文方法在covtype*数据集上的支持向量个数明显多于方法一，但在其他数据集上支持向量个数少于方法一和方法二。在训练时间上，方法一和本文方法都采用了采样策略，训练时间明显少于方法二。由于本文方法运用了分层聚类重采样的策略，因此在训练时间上要高于应用随机采样策略的方法一。总的来说，在训练样本数相同的情况下，分层聚类重采源于：毕业设计论文总结www.7ctime.com
样算法的分类精度明显高于随机采样算法，其支持向量数目与训练时间均大大低于采用完整训练集训练的结果。通过表2与表3的对比可以发现，通过选取适当的采样数目和kmeans划分块数，分层聚类重采样算法的分类准确率完全能达到完整训练集训练的结果论文导读：，16（6）：1651-1663.DONGJX，KRZYZA，SUENCY.FastSVMtrainingalgorithmwithdecompositiononverylargedatasets.IEEETransactionsonPatternAnalysisandMachineIntelligence，2005，27（4）：603-618.CHENGX，CHENGY，XUJ.Clusterreductionsupportvectormachineforlargescaled
，甚至更优。
3 结语
本文尝试采用约简训练集的方法来解决SVM对于大规模数据集的分类瓶颈问题。对训练集进行约简，主要依据两个条件：1）保证使用它训练时代价不高；2）保证使用它训练出的分类器有一定的分类精度。文中提出的基于分层聚类重采样约简策略在保证数据分布区域不变的情况下，对高密度区域数据进行约简，不会对支持向量的分布构成太大的影响。实验结果证实本文方法能够在降低学习代价的同时，很好地保证分类器的分类精度，其分类速度得到了较大的提高；另外，本文算法也在一定程度上抑制了过拟合的过学习现象。
参考文献：
邓乃扬，田英杰. 数据挖掘中的新方法——支持向量机[M]. 北京：科学出版社， 2004.
李红莲，王春花，袁保宗，等.针对大规模训练集的支持向量机的学习策略[J]. 计算机学报， 2004， 27（5）： 715-719.
[3] CHEN P H， FAN R E， LIN C J. A study on Otype decomposition methods for support vector machines [J]. IEEE Transactions on Neural Networks， 2006， 17（4）： 893-908.
[4] HUANG G B， MAO K Z， SIEW C K， et al. Fast modular network implementation for support vector machines [J]. IEEE Transactions on Neural networks， 2005， 16（6）： 1651-1663.
[5] DONG J X， KRZYZ A， SUEN C Y. Fast SVM training algorithm with decomposition on very large data sets [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2005， 27（4）： 603-618.
[6] CHEN G X， CHENG Y， XU J. Cluster reduction support vector machine for largescale data set [C]// Proceedings of the 2008 IEEE PacificAsia Workshop on Computational Intelligence and Industrial Application. Piscataway： IEEE， 2008： 8-12.
[7] CERVANTES J， LI X， YU W. Support vector machine classification based on fuzzy clustering for large data sets [C]// MICAI06： Proceedings of the 5th Mexican International Conference on Artificial Intelligence， LNCS 429

3. Berlin： Springer， 2006： 572-582.

[8] LI D C， FANG Y H. An algorithm to cluster data for efficient classification of support vector machines [J]. Expert Systems with Applications， 2008， 34（3）： 20132018.
[9] CERVANTES J， LI X， YU W， et al. Multiclass support vector machine for large data sets via minimum enclosing ball clustering [C]// Proceeding of the 4th International Conference on Electrical and Electronics Engineerin论文导读：g.Piscataway：IEEE，2007：146-149.陈光喜，徐健，成彦.一种聚簇消减大规模数据的支持向量分类算法.计算机科学，2009，36（3）：184-187.CHANGCC，LINCJ.LIBSVM：alibraryforsupportvectormachines..http：//.cn/soft/ACRD4CHS.EXE">PDF浏览器用户请先下载安装上一页1234
g. Piscataway： IEEE， 2007： 146-149.
[10] 陈光喜， 徐健， 成彦. 一种聚簇消减大规模数据的支持向量分类算法 [J]. 计算机科学， 2009， 36（3）： 184-187.
[11] CHANG C C， LIN C J. LIBSVM： a library for support vector machines [CP/OL]. [20121010].http：//.cn/soft/ACRD4CHS.EXE">PDF浏览器用户请先下载安装