基于SODM的支持向量機的多分類器融合算法

宋 磊

（濟南大學管理學院，濟南 250022）

0 引言

支持向量機SVM（Support Vector Machines）是學者Vapnik提出的結(jié)構(gòu)化風險最小的統(tǒng)計學習理論[1～3]，主要研究小樣本情況下的統(tǒng)計學習方法，是目前國際上最為流行的機器學習和模式識別技術(shù)，并在很多領(lǐng)域成功應(yīng)用。但是，隨著企業(yè)信息化水平的逐步推進，需要處理的數(shù)據(jù)急劇增加，而一般的支持向量機技術(shù)在挖掘和分析海量的數(shù)據(jù)時，內(nèi)存開銷大、訓練速度慢的缺點極大阻礙了支持向量機方法的應(yīng)用。因此。許多學者對傳統(tǒng)支持向量機提出許多改進。

一類方法是改進支持向量機的訓練方法，如：Platt[4,5]，Keerthi等[6]提出了基于序列最小優(yōu)化（SMO，Sequence Minimal Optimization），將大的二次規(guī)劃分解為一系列小的二次規(guī)劃，使得SVM處理大樣本數(shù)據(jù)的速度大大提高；Lee等[7]提出隨機選取子集的減少樣本訓練量的方法（RSVM，Reduce Support Vector Machine）；Zhang[8]提出了遞歸支持向量機方法（R-SVM，Recursive Support Vector Machine）去除噪聲點以降低計算強度。劉向東[9]和秦玉平[10]提出FCSVM（Fast Classification Support Vector Machine）采用二分法優(yōu)化分類函數(shù)中的支持向量數(shù)。

另外一類方法是改進樣本處理方法，如：Sch?lkopf等[11]提出了將大樣本分成不同的子樣本的方法；。Osuna[12]提出的工作集算法（Working Set）；Domeniconi等[13]提出多支持向量機分類器的并行學習算法；Collobert[14]提出w-model算法，使用多個支持向量機分類器的組合來解決大樣本分類問題；。Lin[15]也提出了加權(quán)的模糊支持向量機（FSVM）。

本文也是采用多分類模型（MSVMs，Multiple Support Vector Machine）的方法改進樣本處理速度，考慮到采用不同的分類模型的分類結(jié)果有較大差異，且具有互補性，將不同分類器分類結(jié)果進行融合，得到綜合分類結(jié)果可以發(fā)揮各個分類模型在各自空間的分類優(yōu)勢。但目前的多分類器技術(shù)大多采用Borda計數(shù)、貝葉斯方法等，分類時可能產(chǎn)生一些冗余和沖突。因而，多分類器的選擇性融合是最佳選擇。Ivakhnenko[16]提出的自組織數(shù)據(jù)挖掘理論（SODM，Self-Organize Data Mining）構(gòu)造一個多層前饋神經(jīng)元網(wǎng)絡(luò)結(jié)構(gòu)，通過遺傳，進化，變異，選擇和淘汰等一系列操作，來決定系統(tǒng)模型的輸入變量，結(jié)構(gòu)以及參數(shù)，最后通過終止法則來選擇最優(yōu)復(fù)雜度模型[17]。本文將利用自組織數(shù)據(jù)挖掘SODM，將其應(yīng)用于支持向量機多分類器分類算法的優(yōu)化，解決多分類器產(chǎn)生一些冗余和沖突。

1 支持向量機多分類器融合

1.1 基于one-against-all策略的支持向量機的多分類器

支持向量機的多分類器是由兩分類支持向量機擴展來解決多分類問題，通過合并多個兩分類SVM分類器來構(gòu)造MSVM的三類典型方法，即one-against-all，one-against-one，DAGSVM方法。

one-against-all方法是對k類問題構(gòu)造k個分類器，第i個SVM用第i類中的訓練樣本作為正的訓練樣本，將其他的樣本作為負的訓練樣本。

首先，建立k個兩分類SVM分類器。第i個SVM把第i類與其他類分隔開，i=1,2,…,k（第i類樣本的類屬性設(shè)為1，其他樣本的屬性設(shè)為-1），第i個支持向量機解決以下的優(yōu)化問題：

其中，C為罰因子，是允許xj被錯分的松弛因子，通過求解上式，可以得到k個距離函數(shù)：

最終輸出的是于具有最大值的距離函數(shù)的類：

1.2 w-model多分類器融合算法

2 自組織選擇性融合多支持向量機算法

2.1 自組織數(shù)據(jù)挖掘理論

自組織數(shù)據(jù)挖掘（SODM，Self-Organize Data Mining）的基本思想是構(gòu)造一個多層前饋神經(jīng)元網(wǎng)絡(luò)結(jié)構(gòu)，從參考函數(shù)出發(fā)，通過遺傳，進化，變異，選擇和淘汰等一系列操作，來決定系統(tǒng)模型的輸入變量結(jié)構(gòu)以及參數(shù)，最后通過終止法則來選擇最優(yōu)復(fù)雜度模型。SODM的核心技術(shù)是GMDH（Group Method of Data Handling）算法，GMDH算法將觀測樣本數(shù)據(jù)分為訓練集(training set)和測試集(testing set)，建立因變量(系統(tǒng)輸出)和自變量(系統(tǒng)輸出)之間的一般函數(shù)關(guān)系，一般常用K-G（Komogorov-Gabor）多項式：

，，是訓練集上利用最小二乘(LS)估計得到的參數(shù)，通過閾值度量，F(xiàn)1(≤n1)個局部函數(shù)（F1稱為選擇自由度)被選出，并再次以兩兩配對的形式作為第2層的輸入：

不斷重復(fù)以上過程，直到滿足中止法則，得到最優(yōu)復(fù)雜度模型時停止。

中止法則是：當模型的復(fù)雜度逐漸增加時，具有“外補充”性質(zhì)的選擇準則(外準則)中選出一個作目標函數(shù)，外準則的準則值會呈現(xiàn)先減小后增大的變化趨勢，外準則全局極小值對應(yīng)了最優(yōu)復(fù)雜度模型[17]。

在多分類器融合中，融合方案的優(yōu)劣最直接的測度指標就是其融合后的分類誤差，根據(jù)賀昌政[21]選擇外準則為：

(B)表示測試集B上建立的模型對應(yīng)訓練集A中的預(yù)測值，(A)表示測試集A上建立的模型對應(yīng)訓練集B中的預(yù)測值。

2.2 選擇性融合多支持向量機

假設(shè)現(xiàn)在有k個分類器：Ψ(1)，Ψ(2)，…，Ψ(k)，每一個分類器屬于分類：i=M{1 ,2,…,M}，這樣，大樣本集的SVM問題就變成一系列小的二次規(guī)劃問題（QP）。

現(xiàn)在我們分析三個分類器的支持向量機分類問題。由于自適應(yīng)線性神經(jīng)元（Adaline）的數(shù)量m1對GMDH網(wǎng)絡(luò)的影響很大，當層數(shù)增加時，GMDH網(wǎng)絡(luò)的中與預(yù)測無關(guān)的值會大量增加，并直接影響預(yù)測分類預(yù)測的精度。按照PPS準則（prediction sum of squared）和AIC準則（Akaike Information Criterion）.（Tamura，1978）[22]，自適應(yīng)線性神經(jīng)元（Adaline）定義為：

其中，是殘差平方和，是估計值，C是和m相關(guān)的一個常量。

假設(shè)在[0 ,TLC]時間內(nèi)，累積性錯誤被記為隨機計數(shù)過程{N(t),t＞0} ，那么，發(fā)生在[0 ,TLC]間的錯誤總期望V(TLC)為：

s1，s2，s3分別為三個分類器的累積性錯誤標準差。那么，取得min{V(TLC) }的TLC即是運算終止時間，此時對應(yīng)的分類即為最終的分類結(jié)果。

3 仿真實驗

J.A.Mueller和L.Frank開發(fā)了功能強大的自組織數(shù)據(jù)挖掘軟件包KnowledgeMiner，使SODM成功地應(yīng)用于各個領(lǐng)域的建模實踐。本例采用臺灣信用卡數(shù)據(jù)，32個字段，1301068條記錄，利用KnowledgeMiner軟件，分別隨機抽取10%，20%，…，100%，SVM分類器分別選取，高斯核RBF分類器、d維多項式分類器、多層感知器分類器三種，對比單獨使用這三種分類器、w-model多分類器融合算法和本文的自組織選擇性融合多分類器算法（SOSF）的預(yù)測精度如表1。

表1 10個數(shù)據(jù)集上的分類精度比較（%）

4 結(jié)論

將自組織數(shù)據(jù)挖掘理論引入支持向量機多分類器融合的學習中，實現(xiàn)選擇性多分類器融合，PPS準則和AIC準則，以累積性錯誤總期望V(TLC)最小為分類終止條件，有效解決大樣本多分類器融合受子樣本分布狀態(tài)影響、各分類器學習能力相差過大的缺點，從而提高了訓練效率和分類效率。在本文的信用卡數(shù)據(jù)實驗中發(fā)現(xiàn)，在樣本量較小的情況下單一分類器分類誤差和多分類器分類誤差差別不大，而隨著樣本容量的逐步增大，多分類器分類誤差有明顯提高，特別是本文的自組織選擇性融合多分類器算法（SOSF）優(yōu)于w-model多分類器融合算法。

[1]Vapnik V,Lerner A.Pattern Recognition Using Generalized Portrait Method[J].Automation and Remote Control,1963,24(6).

[2]Vapnik V.The Nature of Statistical Learning[M].New York:Springer,1995.

[3]Vapnik V.Theory of Support Vector Machines[D].Royal Holloway;University of London,1996.

[4]Platt J.Sequential Minimal Optimization:A Fast Algorithm for Training Support Vector Machines[J].Advances in Kernel Methods Support Vector Learning,1998,208.

[5]Platt J C.Fast Training of Support Vector Machines Using Sequential Minimal Optimization[C].MIT Press,1999.

[6]Keerthi S S,Shevade S K,Bhattacharyyc C,et al.Improvements to Platt's SMO Algorithm for SVM Classifier Design[J].Neural Computation,2001,13(3).

[7]Lee y J,Mangasarian O L.Rsvm:Reduced Support Vector Machines[R].Wisconsin:Data Mining Institute,Computer Sciences Department,University of Wisconsin,2000.

[8]Zhang x,Lu x,Shi Q,et al.Recursive SVM Feature Selection and Sample Classification for Mass-spectrometry and Microarray Data[J].BMC Bioinformatics,2006,7(1).

[9]劉向東,陳兆乾.一種快速支持向量機分類算法的研究[J].計算機研究與發(fā)展,2004,41(8).

[10]秦玉平,王秀坤.一種改進的快速支持向量機分類算法研究[J].大連理工大學學報,2007,47(2).

[11]Sch Lkopf B,Chris Burges,Vapnik V.Extracting Support Data for a Given Task;Proceedings of the First International Conference on Knowledge Discovery and Data Mining,Menlo Park,Canada[C].AAAI Press,1995.

[12]Osuna E,Freund R,Girosi F.Improved Training Algorithm for Support Vector Machines;Proceedings of the Procedings of the Ieee Nnsp[C].Amelia Island,1997.

[13]DomeniconI C,Gunopulos D.Incremental Support Vector Machine Construction;Proceedings of the In Proceedings of of International Conference on Data Mining,Califomia,USA[C].IEEE,2002.

[14]Collobert R,Bengio S,Bengio Y.A Parallel Mixture of Svms for very Large Scale Problems[J].Neural Computation,2002,14(5).

[15]Lin C F.Fuzzy Support Vector Machines[J].Neural Networks,IEEE Transactions on Neural Networks,2002,13(2).

[16]Ivakhnenko A G.Heuristic Self-organization in Problems of Engineering Cybernetics[J].Automatica,1970,6(2).

[17]Mueller J A,Lemke F.Self-organising Data Mining:An Intelligent Approach To Extract Knowledge From Data[M].Hamburg:Libri,1999.

[18]Yan W W,Chen Z G,Shao H H.Multi Support Vector Machines Decision Model and its Application[J].Journal of Shanghai Jiaotong University(Science),2002,7(2).

[19]Platt J C,Cristianini N,Shawe-taylor J.Large Margin DAGs for Multiclass Classification.Advances in Neural Information Processing Systems[M].Cambridge,MA:MIT Press,2000.

[20]Anastasio P L,Pan h,Liang Z,et al.A Hybrid Nn-Bayesian Architecture For Information Fusion;Proceedings of the Proceedings of ICIP98[C].Citeseer,1998.

[21]賀昌政.自組織數(shù)據(jù)挖掘與經(jīng)濟預(yù)測[M].北京:科學出版社,2005.

[22]Tamura H,Kondo T.Revised GMDH Algorithm Using Prediction Sum of Squared(PSS)as a Criterion for Models Selection[J].Trans Instrument and Control Engineering,1978,（14）.