基于球結構的完全二叉樹ＳＶＭ多類分類算法
2008-12-31 00:00:00謝志強高麗楊靜
計算機應用研究 2008年11期
(1.哈爾濱理工大學 計算機科學與技術學院， 哈爾濱 150080； 2.哈爾濱工程大學 計算機科學與技術學院，哈爾濱 150001)
摘要：針對一般的SVM方法不能有效地處理不平衡樣本數據及現有的偏二叉樹結構SVM分類器速度慢的這兩個問題，提出了一種基于球結構的完全二叉樹SVM多分類算法。該算法利用球結構的SVM考慮了每個類的分布情況，能有效地處理不平衡樣本數據；構建完全二叉樹結構，使得同層節點所代表的SVM分類器可以并行工作，能提高其訓練和分類速度，分類速度相當于折半查找。實例驗證兩者結合后的算法可實現準確且高效的多類分類。
關鍵詞：球結構； 支持向量機； 完全二叉樹； 多類分類
中圖分類號：TP391文獻標志碼：A
文章編號：1001-3695(2008)11-3268-03
SVM multi-class classification algorithmbased on full-binary tree of sphere-structured
XIE Zhi-qiang1， GAO Li1， YANG Jing2
(1.School of Computer Science Technology， Harbin University of Science Technology， Harbin 150080， China； 2.College of Computer Science Technology， Harbin Engineering University， Harbin 150001， China）
Abstract:Aiming at the two problems which are generic SVM algorithm can not effectively dispose training sets with uneven class sizes and SVM classifiers of existing partial-binary trees have lower velocity， proposed a SVM multi-class classification algorithm based on full-binary tree of sphere-structured. Sphere-structured SVM of this algorithm can dispose unbalanced samples data because it considered the distribution of each class. To build the structure of full-binary tree， it made SVM classifiers which were denoted by the same hiberarchy nodes work at one time， which speeded up training and classification of SVM classifiers and the speed of classification was the same as bisearch. The results of example show that the proposed method can implement more exact and effective classification.
Key words：sphere-structured; support vector machine(SVM); full-binary tree; multi-class classification
支持向量機(SVM)方法[1]最初是針對兩類別的分類問題而提出的，如何將其有效地推廣到多類別分類仍是當前支持向量機研究的重要內容之一。然而，一般的SVM有一個最明顯的缺點就是沒有考慮每個類的分布情況，在處理不平衡樣本數據時，其分類器預測具有傾向性，嚴重影響分類的準確度。本文引入球結構的SVM考慮了每個類的分布情況，以及球體的中心和半徑，能有效地處理不平衡樣本數據，提高分類精度。
目前，對于多類分類問題，SVM的解決途徑有很多。其中，一次性求解法[2]因計算復雜度過高而不實用，1-a-1(one-against-one)[3]和1-a-r(one-against-rest)方法[4]是當前最為常用的兩種SVM多類分類方法，但這兩種方法存在大量的不可分區域且速度都較低。基于二叉樹的層次SVM方法[5]是一種廣泛采用的多類分類方法，但二叉樹的結構對SVM多類分類器的性能有很大的影響，如何有效地設計二叉樹的結構就顯得非常重要。針對偏二叉樹結構的SVM分類器訓練和分類速度都比較慢的問題，本文提出了一種基于球結構的完全二叉樹支持向量機多分類算法，實現快速的多類分類，并通過實例來驗證兩者結合的優越性。
1基于球結構的完全二叉樹SVM多分類方法分析
11超球結構SVM與一般SVM性能分析
一般SVM方法的思想是在兩類之間構造最大分割面，用一個決策邊界將它們分開，使得屬于同一類的點位于決策邊界的同側，同時保證分隔邊緣最大。然而，不平衡數據分布是分類問題常見的現象，一般的SVM算法沒有考慮每類樣本的分布情況，其分類器預測表現出一定的傾向性，得到決策邊界總是位于邊緣（magin）的中間。這對不平衡樣本數據中樣本數少的類別很不公平，因此嚴重影響分類的精度[6]，樣本數量多的類別，其分類誤差小。而樣本數量少的類別，其分類誤差大。從貝葉斯分類器的觀點來看，最優分類函數被定義為使錯誤概率最小并且偏離半徑小的類的程度較小。與一般SVM相比，基于球結構的SVM[7，8]在特征空間中，通過求解一個對偶問題得到一個超球體的中心和半徑，對于N類問題就可以構造出N個超球體。另外，球結構的SVM考慮了每個球體的中心和半徑，考慮了每個類的分布情況，因此建立的分類函數與最優貝葉斯分類器更類似。
12基于球結構的完全二叉樹生成算法與其他方法比較
1-a-1方法對于N類問題（N＞2)，在每兩類之間訓練一個分類器，需要構造N(N-1)/2個兩類SVM分類器；分類時每個分類器都對其類別進行判斷，并為相應的類別投上一票，最后得票最多的類別即作為該未知樣本的類別。1-a-r方法是將N類問題轉換為N個兩類問題，即在訓練某一類別的樣本時將其余N-1個類別的所有樣本作為它的反例，這樣可得到N個分類函數；分類時將未知樣本分類為具有最大分類函數值的那類。然而，以上兩種算法都存在大量不可分區域。將二叉樹的思想引入多類分類問題，可以有效地解決1-a-1及1-a-r方法存在的不可分區域。對于N類問題，該方法只需要構造N-1個分類器，分類時也不需要遍歷所有N-1個分類器就能得到分類結果，因此分類的速度相當快。但不同的二叉樹結構對SVM多類分類器的性能有很大的影響。
目前的偏二叉樹結構的生成算法，如距離法[9，10]是將兩類樣本的最短距離作為兩類的距離，從而生成一個二叉樹，這種方法沒有考慮類內樣本的分布情況；超球體或超長方體的最小包含算法[11]按照類內樣本的分布區域最廣原則將擁有最大體積的那類先分離出來，這種算法只考慮類內樣本的分布范圍，而忽視了類內各樣本的密度和類間距離。超球結構二叉樹生成算法[12]雖然利用球結構考慮了樣本的分布情況，但仍沒有擺脫偏二叉樹的結構。以上這些算法的訓練和測試速度都比較慢。另外，IMST算法[13]沒有考慮噪聲或孤立點數據。本文基于球結構設計了一種完全二叉樹生成算法用于多類分類問題，考慮了類的分布情況，利用球體的中心和半徑來建立相似性度量函數，可以更好地解決這個問題。在訓練階段，完全二叉樹結構可使得同層節點所代表的分類器并行地建立決策邊界，分類時也不需要遍歷所有的決策節點，其速度相當于折半查找。因此，SVM分類器的訓練和分類速度有很大的提高。
13球結構支持向量機與完全二叉樹結構相結合優點分析
球結構的SVM[8]對不平衡樣本數據有很好的處理能力，但它是用一次性求解法來解決一個多類問題，因其規模大太而顯得不太實用。基于支持向量機數據描述算法的SVM多分類方法(S-MSVM)[14]是針對相交區域性的樣本點而提出的，然而，實際的球體分布并不一定都相交。基于二叉樹的一般SVM[10~12，15]雖然用二叉樹結構將一個大規模的多類問題轉換為多個兩類問題來解決，縮小了計算規模，但它們仍采用一般SVM進行分類器的訓練和預測，顯然不能很好地處理不平衡樣本數據。本文考慮了以上兩種方案在解決多類問題時表現出的優缺點，提出將二叉樹的結構用于球結構的SVM上解決多類分類問題。另外，由于偏二叉樹結構SVM的訓練和分類速度遠遠低于完全二叉樹結構，本文設計了一種完全二叉樹或近似完全二叉樹生成算法。
基于以上分析，兩者結合可有效處理不平衡樣本數據以減少錯分樣本的個數，從而實現準確且高效的多類分類。
2基于球結構的完全二叉樹SVM多分類算法設計與實現
21構造合理的二叉樹結構
二叉樹結構的分類器可以把一個復雜的多類問題轉換為多個兩類問題來解決，一個多類別分類問題轉換為兩類問題的形式是多種多樣的，對應的二叉樹結構也各不相同，不同的二叉樹結構對分類精度有很大的影響。為了讓多類分類算法具備較好的推廣能力，就必須設計出合理的二叉樹結構。已有人提出了構造完全二叉樹或近似完全二叉樹算法[16]。該方法通過求解一個優化問題尋求使準則函數達到最優的解來構造二叉樹，但這種方法需要對每個決策節點求解一個優化問題，因此復雜性過高。本文提出了一種簡單的完全二叉樹構造方法。
22相似性度量函數
歐氏距離是廣泛釆用的度量類間相似性的方法，但兩個類中心的歐氏距離并不能準確地反映出兩類的相似性。如圖1所示的兩類，它們的類中心距離相同，但兩類的位置關系卻不同。其中，(a)為兩類相交；(b)為兩類相離。顯然(a)比(b)具有更高的相似性。因此，不能只以類中心歐氏距離作為相似性度量函數，還需要考慮類內樣本的分布情況。球結構的SVM能構造出使半徑最小且盡可能包含該類所有樣本的球體，因此球體的半徑可以用來度量類內樣本的分布。
由上分析，用下面的距離計算方法[14]作為類i與j間相似性度量：
dij=‖(ai-aj)‖2-(Ri+Rj)（1）
其中：ai，aj，Ri，Rj分別是第i類和第j類的中心和半徑。當dij≥0時表明第i類與第j類沒有相交區域。dij的值越大說明第i類與第j類的可分性越強；dij的值越小說明兩類越相似。
23算法描述
對于N類問題，當N滿足N=2e 時可以構造出一個滿二叉樹的結構；否則，滿二叉樹的結構是不存在的，這時可以構造一個完全二叉樹或近似完全二叉樹。為了獲得較高的分類精度和速度，本文設計的二叉樹結構中各決策節點的左右子類所包含的類別數目之差可能取值是0或1。考慮到兩類相交的情況，dij可以為負；另外，集合S、S1和S2中所包含的類標號個數分別記為Ns，Ns1，Ns2。具體的算法如下：
a)對于N類問題，選擇合適的核函數，由文獻[8]中的式(10)(15)可得到每一類樣本所在超球體的中心ai和半徑Ri（i=1，2，…，N），并將每個球體所代表的類標號按從小到大順序置入一個集合S中。
b)If Ns =2，則把類標號小的類作為左子類，另一個作為右子類，結束。
c)利用式（1）給出的距離函數，從集合S中選出dij值最小的兩類i和j，將它們按類標號大小置入集合S1，在其余類中找出與集合S1中各類距離和最大的類k，將其置入集合S2，令S=S-(S1∪S2)。IfNs=0 即S=，則轉到f)。
d)計算集合S中各類與集合S2中各類的距離，從S中選出與S2中各類距離的和最小的那一類，將其依此置入集合S2中，令S=S-( S1∪S2)。
IfS=
轉f)；
ElseifNs=1
(a)計算S中最后的這個類h與集合S1和S2中各類的距離和，將其置入所得距離和最小的那類;
(b)比較集合S1和S2中所包含的類個數，若將Ns1＞Ns2，則集合S1和S2內所有的類標號交換，即原來S1內的類標號放到集合S2中，原來S2內的類標號放到集合S1中;
(c)轉f)
Else計算集合S中各類與集合S1中各類的距離，從S中選出與S1中各類距離的和最小的那一類，將其依此置入集合S1中，令S=S-(S1∪S2)。
e)重復d)。
f)令S1和S2分別作為二叉樹的左右子樹，至此，一個決策節點的左右子類已形成。
g)將左子類進一步分割為兩個次級子類，方法是令S=S1，返回b)，直到每個類別都成為二叉樹中的葉子節點。
h)同樣，將右子類進一步分割為兩個次級子類，方法同上，令S= S2，返回b)，直到每個類別都成為二叉樹中的葉子節點。
經過上面的步驟，一個N類問題可以通過構造一個完全二叉樹或近似完全二叉樹結構轉換為多個兩類問題來解決。每個決策節點對應一個SVM，對N類問題需N-1個分類器，在訓練某一個決策節點時，將該決策節點所含類別依據其左右子樹分為兩類，利用球結構SVM算法[8]中的公式（16）求解m=2時的一個二次規劃問題，最后利用決策函數：
f(x，α)=arg maxm μm(x)
建立左右子類的決策邊界。隨著樹層次的增加，每個分類器訓練的樣本數據會越來越少。
對未知樣本x的分類過程為：從根節點開始，根據其決策函數的大小來判定x的流向，對x所遍歷的每個決策節點依次進行這樣的判斷，直到x被完全分到某一類。對未知樣本的分類并不需要計算所有的決策函數，從而可節省測試時間。另外，由于每層的SVM樣本數據彼此獨立，沒有什么依賴關系，它們可以并行處理。
24復雜性分析
假設訓練一個SVM所需時間T=cmγ[15]。其中：c為一常數；γ與具體的支持向量算法有關。對于N類分類問題，設總訓練樣本數為m，若每個類包含相同的樣本數m/N，在訓練階段，偏二叉樹的訓練時間為TPt=c∑N-1i=1(m(N-i+1)/N)r；本文提出的完全二叉樹的訓練時間為TFt=c∑ei=12i-1｜m/2i-1｜r。顯然TPt＜TFt。因此，具有完全二叉樹結構的分類器訓練速度最快。
SVM多類分類器的分類速度取決于兩個因素：a)分類時使用的SVM數目；b)各分類器所包含的支持向量數。假設每個二值SVM分類器訓練樣本中的支持向量的比例為β，在分類階段，偏二叉樹結構使用的平均分類器數目為(N+1)/2-1/N，因此分類時間為PPt=((N+1)/2-1/N)βm，完全二叉樹結構使用的平均分類器數目為log2 N，本文提出的完全二叉樹的分類時間為PFt=log2 Nβm。分析可知，完全二叉樹所需分類時間是最少的，因此具有較少支持向量的完全二叉樹的分類速度也是較快的。
3實例分析
當N滿足N=2e時，依據本文算法可以構造出滿二叉樹，滿二叉樹屬于特殊的完全二叉樹；否則，當N為奇數時，可構造出完全二叉樹，當N為偶數時可構造出近似完全二叉樹。為了便于討論，在二維空間中假定每個球的半徑相等，即不考慮不平衡樣本的情況。實際上，球結構的SVM對不平衡樣本有更好的處理能力。下面以N=7為例來詳細說明完全二叉樹的構造過程，同時與基于球結構的偏二叉樹生成算法[12]作一對比。如圖2所示的七類樣本在二維空間中的球結構分布圖，表1為每個球體的中心。
由圖2中樣本的分布，假定各球體半徑為0.65，表2是通過計算得到的各球體中心距離，根據式(1)可計算出各球體間的距離。
圖3是用本文算法構造的完全二叉樹。圖4是根據文獻[10，12]的算法得到的偏二叉樹。由圖2的N=7時各類樣本分布情況可知，ABCD與EFG之間顯然最容易分割，用本文的算法可以將ABCD與EFG分別置于集合S1、S2中，從而在它們之間建立決策邊界，對各決策節點按同樣的算法分別作進一步分割，這樣得到的二叉樹結構更接近樣本的真實分布。然而，圖4先將類D分割出來，從而在D與其余各類之間建立決策邊界。顯然D與其余各類的可分性不是很明顯，若在它們之間建立決策邊界，很容易對下面決策節點的分割產生誤差積累。另外，一般SVM對不平衡樣本沒有作相應的處理，偏二叉樹結構更加劇了這種情況的發生，因此，其分類準確度遠遠低于本文提出的基于球結構的完全二叉樹SVM；并且由復雜性分析可知基于完全二叉樹結構的SVM的訓練和分類時間都比基于偏二叉樹結構的SVM要少得多。考慮到本文完全二叉樹的構造算法簡單且理論比較完備等特點，可將它作為一種有效的完全二叉樹算法加以應用。
4結束語
本文提出了一種基于球結構的完全二叉樹支持向量機多分類算法。球結構的支持向量機能有效地處理不平衡樣本數據，提高分類的精度，且更容易將兩類問題擴展到多類問題。在此基礎上，本文給出了一種設計完全二叉樹結構的新方法，充分考慮了類內樣本的分布及類間距離，得到的二叉樹結構更符合樣本的真實分布。通過對其復雜性分析可知，該方法的訓練和分類速度都有所提高。因此，兩者結合能實現準確高效的多類分類。本文設計的是一個近似的或完全的二叉樹，如何在保證分類精度的前提下，構造出效率更高的完全二叉樹是本文下一步研究的問題。
參考文獻：
［1］VAPNIK V. Statistical learning theory[M] . New York:Wiley， 1998.
[2]WESTON J， WATKINS C. Multi-class support vector machines[C]//Proc of ESANN’99.Brussels:[s.n.]， 1999:233-265.
[3]KREBEL U. Pairwise classification and support vector machines[C]//SCHOLKOPF B， BURGES C J C， SMDLA A J. Advances in Kernel Methods: Support Vector Learning. MA:MIT Press， 1999:255-268.
[4]BOTTOU L， CORTES C， DENKER J， et al. Comparison of classifier methods: a case study in handwriting digit recognition[C]//Proc of Int Conf onPattern Recognition. 1994:77-87.
[5]LEI Han-sheng， VENU G. Half-against-half multi-class support vector machines[C]//Proc of the 6th International Workshop on MCS’05. Berlin， Heidelberg:Springer-Verlag， 2005:156-164.
[6]吳洪興，彭宇，彭喜元. 適用于不平衡樣本數據處理的支持向量機方法[J]. 電子學報，2006，34(12A):2395-2398.
[7]朱美琳，劉向東，陳世福. 用球結構的支持向量機解決多分類問題[J].南京大學學報：自然科學版，2003，39(2):153-158.
[8]HAO Pei-yi ， LIN Y H. A new multi-class support vector machine with multi-sphere inthe feature space[C]//Lecture Notes in Compu-ter Science， vol 4570. Berlin， Heidelberg:Springer-Verlag， 2007:756-765.
[9]XIA Si-yu， LI Jiu-xian， XIA Liang-zheng， et al. Tree-structured support vector machines for multi-class classification[C]//Lecture Notes in Computer Science， vol 4493. Berlin， Heidelberg:Springer-Verlag， 2007:392-398.
[10]唐發明，王仲東，陳綿云. 一種新的二叉樹多類支持向量機算法[J].計算機工程與應用， 2005，41(7):24-26.
[11]唐發明，王仲東，陳綿云. 支持向量機多類分類算法研究[J].控制與決策，2005，20(7):746-749.
[12]張曉平，楊潔明. 一種新的支持向量機多類分類二叉樹生成算法[J].機械工程與自動化，2007(3):1-3.
[13]XIE Zhi-qiang， YU Liang， YANG Jing. A clustering algorithm based improved minimum spanning trees for gene expression[C]//Proc of the 4th International Conference on Fuzzy Systems and Knowledge Discovery. 2007:396-400.
[14]張貝貝，何中市. 基于支持向量機數據描述算法的SVM多分類新方法[J].計算機應用研究，2007，24(11):46-48.
[15]PLATT J. Fast training of support vector machines using sequential minimal optimization[C]//SCHOLKOPF B， BURGES C J C， SMOLA A J. Advances in Kenel Methods:Support Vector Learning. MA: MIT Press， 1999:185-208.
[16]趙暉，榮莉莉，李曉. 一種設計層次支持向量機多類分類器的新方法[J].計算機應用研究，2006，23(6):34-37.
