基于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-），男，博士，北京細推科技有限公司工程師，研究方向為生物

識別。本文通訊作者：胡素黎。