基于SVM-Kd-tree的树型粗分类方法

胡素黎 黄丰喜 刘晓英

摘要：为提高大数据集粗分类识别率，提出一种基于聚类分析的SVM-Kd-tree树型粗分类方法。首先根据数据集特征分布进行k-means两簇聚类，对聚类后的数据集进行类别分析，同时将属于两簇的同一类别样本划分出来;然后使用两簇中剩余样本训练SVM二分类器并作为树型结构根节点，将两簇数据分别合并，将划分出来的样本作为左右子孩子迭代构建子节点，直到满足终止条件后，叶子节点开始训练Kd-tree。实验结果表明，迭代构建树型粗分类方法使训练单- SVM平均时间减少了61.9774%.比Kd-tree同近邻数量的准确率提高了0.03%。在进行大规模数据集粗分类时，使用聚类分析迭代构建组合分类器时间更短、准确率更高

关键词：SVM分类;Kd-tree;树型;组合分类器;K-means;聚类

DOI： 10. 11907/rjdk.191714

开放科学（资源服务）标识码（OSID）：

中图分类号：TP301

文献标识码：A

文章编号：1672-7800（2020）004-0111-04

Tree-based Rough Classification Method Based on SVM-Kd-tree

HU Su -li. HUANG Feng-xi， LIU Xiao-ying

（Beijirzg Xitui Technology Co. ， Ltd. ， Beijing 1 00026 ， China ）

Abstract： In order to improve the rough classif'ication accuracy of large data sets. a SVM-Kd-tree tree classif'ication method based oncluster analysis is proposed. Firstly， cluster the training data sef by K-means according to the feature distribution into two clusters.and the samples of the same category belonging to the two clusters are leaved out. Then remaining samples in the two clusters are usedto train SVM as the root node of the tree structure. The two clusters of data comhined with the Ieaved out samples separately constructthe left and right child nodes. This process is iteratively constructed until iueet the termination condition. and using the samples of leafnode to train Kd-tree. The experimental resuks show that the iterative construction of the tree-hased rough classification method reduc-es the average time for training a single SVM by 61.977 4c7e . ＼vhich is 0.03% higher than the accuracy of' the same neighbors of'Kd-tree. In the large-scale data set for rough classification， using the cluster analvsis iteratively construct ensemble classifiers hasshorter tirue and higher accuracy.Key Words： SVM; Kd-tree; tree; enseruble classifer; K-means; cluster

O 引言

近年來，大数据集分类在人工智能领域应用广泛。集成学习…方法指通过多个互补的基本分类器构建组合分类器以完成分类。集成学习的目标是管理和融合各种基本模型的优势和不足，可获得比单一分类器更优越的泛化、识别能力。其中识别效率较高且常用的基本分类器有SVM分类器[2]、Bavsian分类器[3]、KNN[4]分类器3种，集成分类器通常需考虑如何产生具有差异性的基本分类器，同时，组合基本分类器相互作用之后可得到最优结果。通常构建组合分类器的方法有以下几种：

（1）基于训练数据集的处理，如Bagging[5]、Boosting[6]、Adahoost[7]。Bagging和Boosting通过无放回或有放回抽样选择样本训练基本弱分类器，Boosting通过增加易错分的数据选人训练权重，使数据被划分到弱分类器集合中，进而提升整体识别准确率;Adaboost通过改变训练样本权重，迭代构建基本弱分类器，然后将全部弱分类器构建成组合分类器，通过投票等方法，统计分类结果。

（2）基于输入特征的处理，如以决策树为基础分类器的随机森林[8-9]。决策树是对训练样本特征的处理，常见决策树算法有ID3[10]、C4.5[13]及CART[12]，其算法基本思想是：首先，将整个样本数据集用一个根节点表示，然后把根节点作为起始点，选择一个特征并在每一个节点上进行测试，把各个节点数据（子）集分裂成几个更小的样本数据子集，并用子树的形式表示，直到分裂得到的样本数据子集中所有样本均属于同一个类别时，决策树停止分裂、不再生长。ID3.5是以信息增益为准则的分裂方式，C4.5以信息增益率的信息论为分类准则，但需将全部训练集一次性装入内存，对大数据集训练决策树的内存要求较高。

（3）基于类别号的处理，适用于类别较多的情况，通过将训练集划分成正交的两个子集，分别编码为O和1，然后通过二分法分别迭代两个子集，最后构建成一个组基分类器。通过统计基分类器的投票数完成分类，如错误一纠正输出编码（ Error-correcting Output Coding.ECOC[13]）方法。

（4）基于学习的处理，在同一个训练数据集上多次执行算法可能得到不同的模型，通过多次执行训练生成多个基本分类器。基于学习的处理是在训练集上训练多个不同类型的基本分类器，利用基本分类器的决策层进行组合投票等方法进行融合，但该方法无法避免基本分类器分类误差对整体投票结果的影响。

（5）混合集成分类器处理[14]，即综合使用以上4种方法同时构建组合分类器，多样化基本分类器性能。但是训练基本分类器的时间极易受数据集规模影响，并不适用于大数据分类。

借鉴ECOC对数据集类别号的处理方法，对大规模数据集进行划分并训练基本分类器。文献[15]提出借鉴半监督聚类分析构建集成分类器的方法，使用树型结构对数据集进行分流，缩短基本分类器构建时间;使用基于聚类分析的方法可避免易错分数据的错误累积，易错分数据指不同类别的数据容易被错分成同一类别，在数据分布上表现为不同类别的数据分布在同一区域。针对大数据集中数据量大、类别混淆的情况，需要对原数据集进行数据划分，降低基本分类器分类规模，增大基本分类器识别精度，从而整体上提高组合分类器识别率。

1 相关工作

1.1 支持向量机

支持向量机（ Support Vector Machine，SVM）的作用是基于最大间隔准则，在特征空间或特征的高维映射空间里，通过求解一个凸优化问题获得一个最大间隔分类超平面。在分割数据的超平面两边建立两个互相平行的超平面，建立方向合适的分隔超平面，使两个与之平行的超平面间距离最大化，假定平行超平面间的距离或差距越大，分类器总误差越小。SVM训练的关键问题是凸二次规划求解问题。

假设样本数据集D对应的标签Y= ，其中v， 支持向量機指y需在特征空间中找到一个最优分类超平面wt.x+b=0把数据分开，为找到这个最优分类超平面，需求解如式（1）所示的二次规划问题。利用拉格朗日法把式（1）转化为其对偶问题。

经典SVM主要针对小规模数据，处理大规模数据时，会出现因数据量太大造成组合二分类SVM数据量过大，训练时间久、效率不高、准确率低的问题。文献[16]从理论上证明由于单个分类器的性能，基于权重的集成分类器是简单而有效的集成方法。因此，并行SVM[17]的提出解决了大数据集的问题;文献[18]提出使用多个SVM分类器组合解决大规模数据分类问题，文献[19]提出分层有反馈的SVM学习方法。

并行SVM算法很少考虑实际数据分布信息，根据SVM分类原理，样本之间的分布往往影响计算支持向量的决策面。当进行l：n识别时，若n较大，则算法时间复杂度较高。为缩小搜索范围，提高算法运行效率，有必要对图像或特征作粗分类处理。现有SVM组合分类器的方法无法避免因样本错分带来的误差累积。

1.2 K-means算法

K-means算法[20]度量进行聚类，以k为参数，把n个对象分为k个簇，使簇内具有较高的相似度，且簇间相似度较低，属于非监督学习方法。

1.3 Kd-tree

Kd-tree（K-dimension tree）是一种对k维空间中的实例点进行存储，以实现快速检索的树形数据结构[21]。Kd-tree是一种二叉树，表示对k维空间的一个划分。构造Kd-tree相当于不断地用垂直于坐标轴的超平面切分K维空间，构成一系列K维超矩形区域。Kd树的每个结点对应于一个k维超矩形区域。利用Kd-tree可省去对大部分数据点的搜索，从而减少搜索计算量。

Kd-tree属于二叉查找树（Binarv Search Tree，BST）的一种。二叉查找树的性质包括：①若它的左子树不为空，则左子树上所有结点值均小于其根结点值;②若它的右子树不为空，则右子树上所有结点值均大于其根结点值;③它的左、右子树也分别为二叉排序树。

Kd-Tree构建算法步骤包括：

（1）在K维数据集合中选择具有最大方差的维度k，然后在该维度上选择中值m为pivot，划分该数据集合，得到两个子集合;同时创建一个树结点node，用于存储。

（2）对两个子集合重复上述步骤，直至所有子集合均无法再划分;如果某个子集合不能再划分，则将该子集合中的数据保存到叶子节点中。

Kd-tree方法应用于大数据集检索时，计算量过大，虽然准确率很高，但Kd-tree叶子节点数与数据集大小相同，因此训练Kd-tree需考虑实际存储空间与训练集大小。

2 基于SVM-Kd-tree树型的粗分类方法

K-means聚类算法根据样本距离选择中心点距离并判断样本所属簇类，当样本位于两簇类的连接地带时，错分样本的概率较大;当聚簇中属于同一类别的样本完全位于同一个簇中时，样本容易区分，根据簇编号分别置于左右子孩子中;同时属于多个簇中的数据则作为易错分样本，分别加入到左右子孩子中，待下一步细分。利用二叉树生长方式将数据集细分到叶子节点时，将Kd-tree高效的检索效率与SVM相结合，构建集成分类器进行粗分类。

利用K-means无监督学习的特征，根据距离把相近数据聚成若干簇（以二分类为例进行说明）。K-ineans聚类结束后，把分得的两簇分别标记为0和l两个标签，然后对这个两簇标签的数据进行类别分析，使同一类别的样本完全属于同一个簇，同时将属于0.1簇的样本划分到标签为2的簇中，然后用这两簇有标签的数据训练一个SVM二分类器。将SVM正确分开的数据分割成左右两个子节点的训练数据，把SVM预测错误的数据与属于第2簇的数据同时添加到左右两个子节点的数据中，形成两个子节点的训练数据。

預测时指定Kd-tree搜索范围，将测试样本输入树型结构中，根据到达叶子节点的类型进行预测识别：①当叶子节点为单一类别的数据时，返回该类别作为测试样本类别标签;②当叶子节点为个数小于阈值的复合Kd-tree时，返回该Kd-tree的前N个近邻。

取N个近邻中类别个数最多的类别作为测试样本类别标签。步骤为：

步骤1：在根节点用K-means聚类算法把数据聚成两簇，分别标记为O和1。对簇内样本进行类别分析，将每个类别中样本完全属于簇0的类别标记为0，将完全属于簇1的类别标记为1，同时将划分到簇0和簇1里的类别标记为2。

步骤2：如果属于簇2的样本数目远远大于属于簇l和簇0的数目总和，则对样本维度进行抽样选择，对抽样选择的样本维度按照步骤1进行聚类。

步聚3：利用上述步骤得到的两类数据训练一个SVM分类器，用训练得到的SVM分类器预测训练数据，根据预测结果重新划分0和1数据集，然后用得到的新0和1数据集分别合并类别标记为2的数据集。

步骤4：0数据集与1数据集分别重复步骤1-3，直到数据量小于阈值或只有单一类别的样本则停止分裂。

步骤5：利用小于阈值的样本集合训练Kd-tree。预测时指定Kd-tree搜索范围，根据叶子节点上保存的标签信息完成粗分类预测。如果叶子节点有类别标签信息，则返回该类别标签作为测试结果;否则使用该叶子节点的Kd-tree进行预测。取指定的K个最近邻中，比重最大的类别标签作为测试样本预测标签。迭代构建组合分类器流程如图1所示。

3 实验结果与分析

将本文粗分类方法应用在指静脉与人脸识别中，以LFW人脸数据库为例，LFW数据集是为研究非限制环境下人脸识别问题而建立，该集合包含超过13000张人脸图像。本文实验选出LFW中1000个人脸数据，每个人脸图片提取一个1024维度的特征向量，共计7606个样本特征。使用本文粗分类方法对测试集合进行粗分类时，最后到达叶子节点时使用Kd-tree进行小范围预测，使用前100个近邻预测时的准确率为99.59%，前150个近邻预测准确率为99.59%。实验结果如表1所示。

对比同等数据量下，将使用多个二分类SVM构建组合分类器的方法与本文方法进行平均时间对比，如表2所不。

对比使用SVM-Kd-tree与仅使用Kd-tree方法的准确率，其中训练Kd-tree时将每一类人脸特征的中心点作为训练数据，以降低训练Kd-tree计算量。从表3可看出，仅使用Kd-tree预测时的准确率低于本文方法准确率。

4结语

针对大数据集分类问题，粗分类的目的是减少分类基数，缩小搜索范围。本文使用基于SVM-Kd-tree的方法对数据集进行迭代拆分，分别训练SVM分类器，直到满足终止条件后，叶子节点训练Kd-tree进行粗分类检索。本文方法使用基于聚类分析的方法，将易分错数据多次加入子集中，避免集成分类因错分导致的误差累积，提高了集成分类器识别准确率;根据树型结构逐层划分缩小数据集规模，降低了基础分类器训练时耗。训练数据个数小于一定阈值后使用Kd-tree进行预测，与仅使用Kd-tree的方法相比，识别准确率明显提升。下一步将重点研究特征选取对构建集成分类器的影响。

参开文献

[1]YAN Y. ZHU 0， SHYL M L. et al. A classifier ensemble framework

for multimedia big data classification [c].IEEE International Confer-

ence on Information Reuse &. Integration ， 2016 ： 615-622.

[2]CORTES C，VAPNIK V. Support vector networks[J]. Machine Learn-ing，1995，20（3） ： 273-297.

[3]DELGOSHA F， MENHAJ M B. Fuzzy probahilistic： neural netwr）rks：a practical approach to the implementation of Baysian classifier[c]Internatinnal Conferene e on Computational Intelligenc.e ， 200I ： 76-85.

[4]TIEhr BUI D， NGLYE＼r O P， HOANG Nr D. et al. A novel fuzzyK-nearest neighbnr inference model with differential evolution for spa-tial predictirin of rainfall-induced shallow landslides in a tropical hillyarea using CIS[J]. Landslides ， 2017， 14（1） ： 1-17.

[5]YU W. CHENC D L. Learning hy Bagging and Adahnost hased nn sup-port vector machine [C] . Vienna ： IEEE Internatinnal Conference on In-dustrial Informatics ， 2007.

[6]JUNIOR J R B， NICOLETTI M D C. An iterative hoosting-based en-semble for streaming data classification[J]. Information Fusion.2019.45 ： 66-78.

[7]LIU X. CANG C， GAO W. et al. CA-AdaBoost SVM classifier em-powered wireless network diagnosis [J]. Eurasip Journal on WirelessCommunicatir）ns & Networking， 2018， 2018（1） ： 77.

[8]CUTLER A， CULTER D R. STEVENS J R. Random forests[J]. Ma-chine Learning， 2004. 45（I） ： 157-176.

[9]KAhrC B. NGUYEN T Q. Random forest with learned representationsfor semantic segmentation[EB/OL] .

https ： //arxiv.org/pdf/ 1901 .07828. pdf.

[10]PHL V N， TRAN V T N， CHAU V T N. et al. A decision tree usingID3 algorithm for English semantic analysis FJl. Internatir，nal Jour-nal of Speech Technology ， 2017 ， 20（4） ： 1-21.

[11]赵建民 .黄珊 .王梅 ，等.改进的 C4.5算法的究与应用[J]. 计算机与数字工程 .2019， 47（2） ： 261-265.

[12]RUTKOWSKI L. JAWORSKl M ， PIETRL CZUK L. et al. The CARTdecision tree for mining data streams [J]. Information Sciences，2014. 266（5） ： 1-15.

[13]LOO， WEN Y， TAO D. Heterogeneous multitask metric learningacross multiple domains [J] . IEEE Transactions on hreural Networksand Learning< Systems. 2017 . 29（ 9） ： 405 1-4064.

[14] FAhr X. LUNG C H， AJILA S A. An adaptive diversiw-based en-semhle method for hinarv classification [C].2017 IEEE 4lst AnnualComputer Software and Applications Conference ， 2017 ： 822-827.

[15]GIPTA R ， GUPTA H. A review of cluster oriented ensemble classifi-er for improving performance of stream data classification [J] . Inter-national Journal of Computers &. Technology， 2013 ， 8（3） .

[16]WANC H， FAN W， YU PS. et al. Mining concept-drifting datastreams using ensemhle classifiers [C]. Proceedings of the 9th ACMSIGKDD International Conference on Knowledge Discovery and DataMining， 2003 ： 226-235.

[17]KIM H C . PANG S . JE H M ， et al. Support vector machine ensem-ble with Bagging [J]. Pattern Recognition with Support Vector Ma-chines. 2002. 2388 ： 397-407.

[18]COLLOBERT R ， BENGIO S， BENGIL Y. A parallel mixture of SVMsfor very large scale prohlems FJl. Neural Computation， 2014. 14（5） ： 1105-1114.

[19]JING Y. An improved cascade SVM training algorithm "-ith crossedfeedhacks[C]. Hanzhou： International Multi-smposiums on Com-puter& Computational Science . 2006.

[20]CHIEhr Y. Pattern classification and scene analysis [J]. Artificial In-telligence，1973， 42） ： 139-143.

[21]BENTLEY J L. Multidimensional hinary search trees used for associa-

tive searching[J].COmmunications of the ACM.18（9） ： 509-517.

收稿日期：2019-06-06

基金項目：青海省科技厅科技成果转化专项项目（2017-SF-160）

作者简介：胡素黎（1988-），女，硕士，北京细推科技有限公司工程师，研究方向为模式识别;黄丰喜（1984-），男，硕士，北京细推科技有

限公司工程师，研究方向为计算数学与机器学;刘晓英（1967-），男，博士，北京细推科技有限公司工程师，研究方向为生物

识别。本文通讯作者：胡素黎。