任冷　周維民

摘要：該文針對(duì)非平衡數(shù)據(jù)多分類算法進(jìn)行研究，傳統(tǒng)的分類器在處理非平衡數(shù)據(jù)多分類時(shí)往往直接將二 分 類 問 題 的 算 法 直 接 擴(kuò) 展 到 多 分 類 問 題 上，忽 視 數(shù) 據(jù) 之 間 的 關(guān) 系 ， 本 文 主 要 基 于 數(shù) 據(jù) 關(guān) 系 對(duì) SVM 算 法 改 進(jìn) 研 究 ， 提 出 一 種 基 于 空 間 擴(kuò) 展 的 SVM 算 法 ， 優(yōu) 化 分 類 器 組 ， 提 高 少 類 樣 本 數(shù) 據(jù) 分 類 精 度。最后通過數(shù)據(jù)集驗(yàn)證改進(jìn)后算法的有效性。

關(guān)鍵詞：SVM；多分類；數(shù)據(jù)關(guān)系；非平衡樣本集；數(shù)據(jù)挖掘

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）05-0218-03

Abstract： The paper focuses on the issue of unbalanced distribution of data muti-classification algorithm research.The traditional classifier often is directly extended from the two classification algorithm to the multi-classification problems in the treatment of unbalanced data multi-classification， ignoring the relationship between data. So a kind of SVM algorithm based on space extension is put forward based on the data relation，to optimize classifier group， improving the minority sample classification accuracy. At last， specific data is used to demonstrate the effectiveness of the improved algorithm.

Key words： SVM ； multi-classification； data relationship ； unbalanced train sets ； data mining

在互聯(lián)網(wǎng)技術(shù)的推動(dòng)下，很多行業(yè)都變成了“互聯(lián)網(wǎng)+”的模式，在這種企業(yè)概念運(yùn)營(yíng)模式下，產(chǎn)生了更多大量的用戶數(shù)據(jù)，它也就推動(dòng)了數(shù)據(jù)挖掘技術(shù)的快速發(fā)展，人們可以利用這種技術(shù)來(lái)提取對(duì)自己有用的信息。但是現(xiàn)實(shí)中常常存在分布非平衡的數(shù)據(jù)，而我們需要的正是少數(shù)類樣本的數(shù)據(jù)，所以就需要更精確的分類器?，F(xiàn)在非平衡數(shù)據(jù)的分類問題已經(jīng)成為數(shù)據(jù)分類領(lǐng)域的重要研究分支。

在非平衡數(shù)據(jù)分類問題中，又分為二分類和多分類問題。本文主要是針對(duì)多分類問題進(jìn)行研究的。在這類大問題中最經(jīng)常用的算法就是支持向量機(jī)SVM算法（Support Vector Machine）。

SVM是Vapnik等人提出的通用高效的機(jī)器學(xué)習(xí)方法。最初是為解決二分類問題提出來(lái)的，所以是一種典型的二分類算法，在解決小樣本二分類問題上有著良好的精度和泛化能力。而對(duì)于多分類問題，是以二分類問題為基礎(chǔ)，結(jié)合分類決策原則，構(gòu)造分類器，以實(shí)現(xiàn)多類分類。而多分類構(gòu)造方法以一對(duì)一方法和一對(duì)多方法以及在二者基礎(chǔ)上改進(jìn)得到的有向圖無(wú)環(huán)圖方法和二叉樹法。經(jīng)典的一對(duì)一方法還存在很多缺點(diǎn)可以改進(jìn)，而本文主要是利用SVM算法與一對(duì)一方法相結(jié)合的前提下，提出一種新的SVM多分類算法。這種算法是在SVM的基礎(chǔ)上針對(duì)一些傳統(tǒng)經(jīng)典的方法提出一個(gè)新的角度新的思路進(jìn)行改進(jìn)，去解決這個(gè)多分類問題，最后利用在數(shù)據(jù)集上的實(shí)驗(yàn)來(lái)驗(yàn)證這個(gè)新算法的效果，是否在少數(shù)類分類的分類效率上有所提高。

1 SMOTE方法

SMOTE是Chawla.N提出的一種過采樣方法，它不同于傳統(tǒng)的過采樣技術(shù)，是基于樣本簡(jiǎn)單的復(fù)制的。其主要思想是：在一些臨近的位置相似的少數(shù)類樣本中插入新樣本，達(dá)到改善分類樣本不平衡的狀況。這種方法對(duì)數(shù)據(jù)樣本的預(yù)處理有更為明顯的效果，由于不是隨機(jī)的簡(jiǎn)單復(fù)制已有的樣本，而是增加不存在的新樣本，所以就避免了過度擬合的風(fēng)險(xiǎn)。這種方法所產(chǎn)生的新樣本都集中在原始數(shù)據(jù)所屬區(qū)域，只是單純的增加了少類樣本的密度，并沒有達(dá)到向外擴(kuò)展的要求。

2 SVM算法

支持向量機(jī)（Support Vector Machine，SVM）是一類機(jī)器學(xué)習(xí)方法，在統(tǒng)計(jì)學(xué)學(xué)習(xí)理論和神經(jīng)網(wǎng)絡(luò)技術(shù)相結(jié)合的基礎(chǔ)上，區(qū)別于傳統(tǒng)方法，將結(jié)構(gòu)風(fēng)險(xiǎn)最小化。SVM算法原理在于找到一個(gè)最優(yōu)超平面，使得邊界數(shù)據(jù)到超平面的垂直距離最大，也就是尋找一個(gè)分類面。通過數(shù)據(jù)集在高維特征空間建立一個(gè)線性可分，通過最大化邊界距離來(lái)區(qū)分兩類。以上是對(duì)于線性可分的情況，而針對(duì)線性不可分的問題，SVM通過核函數(shù)將低維空間里面的向量轉(zhuǎn)換到高維空間，從而在高維空間中求出最優(yōu)分類面。

把經(jīng)典的多分類方法一對(duì)一算法與SVM算法相結(jié)合構(gòu)成SVM多分類算法。一對(duì)一方法：在K類問題中進(jìn)行兩兩組合，使用每?jī)深惖挠?xùn)練樣本，構(gòu)建類對(duì)間的最優(yōu)超平面。其中涉及到的決策函數(shù)最終都轉(zhuǎn)化為為此規(guī)劃問題求解，對(duì)于這個(gè)K類問題，共有K（K-1）/2個(gè)不同的決策函數(shù)，將K類問題劃分為多個(gè)兩類分類問題進(jìn)行解決，最終可求得任意類之間的分類界面。歸結(jié)為一句就是“投票機(jī)制”，即多數(shù)獲勝，每個(gè)分類器為它的第一選擇類投一票，最終結(jié)果就是擁有票數(shù)最多的類，就是樣本所屬的類。

3 算法的改進(jìn)思想

本文主要是面向非平衡訓(xùn)練樣本進(jìn)行分類器的設(shè)計(jì)，分類器的設(shè)計(jì)將通過幾個(gè)指標(biāo)并且與幾個(gè)經(jīng)典算法進(jìn)行仿真結(jié)果的比較來(lái)區(qū)分分類器的優(yōu)劣。

非平衡數(shù)據(jù)的分類問題不同于平衡數(shù)據(jù)問題，因?yàn)樵诤笳咧袝?huì)更多的注重多數(shù)類樣本，而忽視少數(shù)類樣本，很可能會(huì)被覆蓋掉。所以對(duì)于一些算法可能總體分類精度很高，可是少數(shù)類分類的精度卻不能達(dá)到滿意的效果。在SVM分類過程中，影響分類準(zhǔn)確率的最重要因素是分類界面的選擇也就是支持向量的選取。SVM算法是解決二分類問題的經(jīng)典算法，雖然多分類問題是基于二分類的，但是不能直接套用?？紤]到多分類問題應(yīng)該提出對(duì)應(yīng)的解決方案。

本文中正對(duì)非平衡多分類問題提出的算法是將SVM算法與多分類構(gòu)造方法即一對(duì)一方法相結(jié)合進(jìn)行研究改進(jìn)的。一對(duì)一方法存在的明顯的缺點(diǎn)有二：一是非平衡問題，解決這個(gè)問題就要降低數(shù)據(jù)分布的不平衡度。那么在數(shù)據(jù)預(yù)處理過程成采用smote算法來(lái)解決這個(gè)問題。二是多分類問題用SVM算法涉及到多個(gè)分類界面的問題，如果直接套用二分類的方法那么會(huì)出現(xiàn)數(shù)據(jù)冗余，分類界面雜亂交錯(cuò)，支持向量分布密集難以達(dá)到分類的效果。為解決這個(gè)問題，考慮出現(xiàn)這個(gè)問題的原因就是缺乏重視數(shù)據(jù)內(nèi)部之間的關(guān)系，所以本文針對(duì)這個(gè)角度提出一個(gè)新的SVM多分類算法，就是基于數(shù)據(jù)關(guān)系的SVM多分類算法。

本文采用基于數(shù)據(jù)關(guān)系SVM的多分類方法是將SVM分類原理上與數(shù)據(jù)本身的內(nèi)在關(guān)系相結(jié)合，提出將支持向量機(jī)（Support Vector Machine， SVM）算法與空間擴(kuò)展的思想相結(jié)合的新的學(xué)習(xí)算法，稱為NSVM算法。NSVM方法在多維歐式空間中通過空間擴(kuò)展的方法對(duì)少類數(shù)據(jù)進(jìn)行上釆樣，以減少非平衡分布的影響，同時(shí)結(jié)合按照歐式空間內(nèi)少類數(shù)據(jù)樣本的邊界閾值對(duì)多類數(shù)據(jù)樣本進(jìn)行約減的方法，已達(dá)到優(yōu)化分類器的目的，然后再由SVM 一對(duì)一方法訓(xùn)練出分類器，最終得到較為高效的分類器組合。

3.1 改進(jìn)算法的步驟

5 結(jié)束語(yǔ)

本文根據(jù)數(shù)據(jù)之間的空 間 關(guān) 系 提 出 了 一種空間擴(kuò)展的SVM分類算法，通過這種 歐 式 空 間 內(nèi) 的 空 間 關(guān) 系 擴(kuò) 展 少 類 數(shù) 據(jù) 的 方 法，解 決 了 少 數(shù) 類的數(shù)據(jù)的分布不平衡的問題，減少了被多類覆蓋的風(fēng)險(xiǎn)，增加了少類的分類效率。與傳統(tǒng)的方法相比，本文提出的這種新的SVM算法在處 理 少 類 分 類 要 求 要 的 問 題 中 更 有 效 果。本文對(duì)此進(jìn)行了驗(yàn)證，說(shuō)明了這種新算法的有效性，也為非平衡多分類問題提出了一個(gè)新的視角，可以研究應(yīng)用的到實(shí)際的問題中。

參考文獻(xiàn)：

[1] 許曉峰，海量數(shù)據(jù)關(guān)鍵分類挖掘算法.復(fù)旦大學(xué)碩士論文[D]：上海：計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，2010.

[2] Maciejewski T， Stefanowski J. Local neighbourhood extension of SMOTE for mining imbalanced data .Computational Intelligence and Data Mining （CIDM）， 2011 IEEE Symposium on Paris，2011.

[3] Knerr U.H.. Pairwise classification and support vector machines[M].MA： MIT Press， 1999， 255-268.

[4] 孫濤，吳海峰.SMOTE算法在不平衡數(shù)據(jù)中的應(yīng)用[J].北京生物工程，2012，5（32）：14-16.

[5] 陳中杰，蔣剛.基于SVM一對(duì)一多分類算法的二次細(xì)分法研究[J].傳感器與微系統(tǒng)，2013，32（4）：7-8.

[6] 韓敏，朱新榮.不平衡數(shù)據(jù)分類的混合算法[J].控制理論與應(yīng)用，2011，28（10）：1485-1489.

[7] 梁志.基于數(shù)據(jù)關(guān)系的SVM多分類方法研究.山西大學(xué)碩士論文[D].山西.計(jì)算機(jī)與信息學(xué)院，2013.

[8]He H.B.， Garcia E.A. Learning from imbalanced data[J]. IEEE Transaction Knowledge and Data Engineering，2009， 21（9）：1263-1284.

[9]Xue Zhenxia， Liu Sanyang， Liu Wanli. Unbalanced squares support vector machines[J]. System Simulation .2009（21）.

[10] Y. Tang， Y. Q. Zhang， N. Chawla， and S. Krasser， "SVMs modeling for highly imbalanced classification，" Systems， Man， and Cybernetics， Part B： Cybernetics， IEEE Transactions on， vol. 39， pp. 281 -288，2009.