沈 洋，戴月明

（江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，無(wú)錫 214122）

1 引言

DAG-SVM（Directed Acyclic Graph-Support Vector Machine）是Platt 教授于1999年根據(jù)有向無(wú)環(huán)圖（DAG）提出的另外一種基于SVM 的多類別分類器，它引入了OVO 分類器中利用每?jī)蓚€(gè)類別作為基礎(chǔ)二類分類器的方法，保證了分類的準(zhǔn)確率，而且采用了有向無(wú)環(huán)圖結(jié)構(gòu)，使得每次分類只需要k-1個(gè)分類器，大大提升了分類的效率。但是由于采用了層次結(jié)構(gòu)，也保留了層次結(jié)構(gòu)固有的的缺陷：誤差累積，在上層的節(jié)點(diǎn)產(chǎn)生的錯(cuò)誤會(huì)一直保留下來(lái)，因此，距離根節(jié)點(diǎn)越近的節(jié)點(diǎn)，對(duì)整個(gè)結(jié)構(gòu)的分類結(jié)果影響越大。而DAG-SVM 的節(jié)點(diǎn)選取方式采用了隨機(jī)的方式，這就使得最終的分類結(jié)果十分的不穩(wěn)定。另外，由于采用了與一對(duì)一相同的訓(xùn)練方式，使得訓(xùn)練耗費(fèi)的時(shí)間比較長(zhǎng)，這都是需要改進(jìn)的。

2 有向無(wú)環(huán)圖支持向量機(jī)的原理

DAG-SVM 是一種以SVM 分類器作為基礎(chǔ)分類器，以有向無(wú)環(huán)圖作為拓?fù)浣Y(jié)構(gòu)的組合多類別分類器，它通過(guò)從全體類別集合中不斷的刪除不可能的類別，得到最終的結(jié)果。DAG-SVM 的具體分類過(guò)程如如圖1所示，根節(jié)點(diǎn)a 表示當(dāng)前類別集合為全體類別{1，2，3，4}，經(jīng)過(guò)分類器1-vs-4作用后，節(jié)點(diǎn)走到第二層，由于排除了一個(gè)類別4，因此當(dāng)前類別集合為{1，2，3}，經(jīng)過(guò)分類器1-vs-2作用后，節(jié)點(diǎn)走到了第三層d{1，3}，再經(jīng)過(guò)分類器1-vs-3作用后，走到最后的葉節(jié)點(diǎn)類別1，因此，類別1即為最終的結(jié)果。

圖1 DAG-SVM拓?fù)鋱D

3 有向無(wú)環(huán)圖支持向量機(jī)的缺陷

DAGSVM 雖然通過(guò)特殊的層次結(jié)構(gòu)[1]實(shí)現(xiàn)了分類速度的提升，但是也由于層次結(jié)構(gòu)，使得它的準(zhǔn)確率受到了一定的影響；另外，它在訓(xùn)練階段使用了與一對(duì)一分類器同樣的方式，導(dǎo)致了分類的時(shí)間過(guò)長(zhǎng)，下面將對(duì)這兩個(gè)問(wèn)題進(jìn)行詳細(xì)介紹。

3.1 誤差累積

所謂誤差累積，是指高層次所造成的錯(cuò)誤會(huì)一直保留到最后的葉子結(jié)點(diǎn)，不會(huì)隨著層次的增加而消失，這是所有層次結(jié)構(gòu)的缺陷。目前來(lái)說(shuō)，克服誤差累積有兩種常用的方法：

（1）提高每個(gè)二分類器的準(zhǔn)確率。因?yàn)槲覀冊(cè)谶M(jìn)行層次分類時(shí)，如果沒(méi)有特殊的策略，那么每個(gè)二分類器最終被放置的位置是隨機(jī)的，因此我們沒(méi)辦法針對(duì)特殊的二分類器進(jìn)行一些提高準(zhǔn)確率的操作，這時(shí)候我們只有將所有二分類器的性能都進(jìn)行優(yōu)化，使得所有的二分類器都有比較高的準(zhǔn)確率，這樣可以保證不管什么樣地排列方式最終的效果都是不錯(cuò)的。

（2）優(yōu)化節(jié)點(diǎn)的選擇順序。不管是有向無(wú)環(huán)圖結(jié)構(gòu)，還是樹結(jié)構(gòu)[2]，它們的特點(diǎn)都是從根結(jié)點(diǎn)向下進(jìn)行深度搜索，這就使得節(jié)點(diǎn)越靠上，被使用的幾率越大，例如，根節(jié)點(diǎn)每次分類都要被用到，使用率為1；而葉子結(jié)點(diǎn)只有最終歸屬該類別才會(huì)被使用到，（k 為類別總數(shù)）所以它的使用率為1/k。因此，我們只要對(duì)層次結(jié)構(gòu)節(jié)點(diǎn)的選擇順序進(jìn)行優(yōu)化[3]，在那些經(jīng)常被使用的位置上放置正確率比較高的二分類器就會(huì)使得整個(gè)的分類器模型具有不俗的分類效果。但是，傳統(tǒng)的DAGSVM 恰恰對(duì)于節(jié)點(diǎn)的劃分沒(méi)有制定任何的規(guī)則，只是隨意組合，這也導(dǎo)致了最終的結(jié)果高低不一。

3.2 訓(xùn)練時(shí)間過(guò)長(zhǎng)

除了誤差累積之外，DAG-SVM 的訓(xùn)練時(shí)間也需要改善，因?yàn)镈AG-SVM 的基礎(chǔ)分類器采用的是一對(duì)一分類器，這就使得每次都要訓(xùn)練k（k-1）/2個(gè)分類器，當(dāng)類別數(shù)目較大時(shí)，耗費(fèi)的時(shí)間就會(huì)很多。

經(jīng)過(guò)實(shí)驗(yàn)證明：SVM 分類器針對(duì)全部樣本訓(xùn)練一次所需要的時(shí)間為：

式中，v 是一個(gè)常數(shù)，它取決于SVM 分類器采用的是那種分類算法；m 代表當(dāng)前樣本的總數(shù)；c 也表示一個(gè)常數(shù)。OVR 模式由于訓(xùn)練每個(gè)分類器都要用到所有的樣本，那么訓(xùn)練k 個(gè)分類器一共所耗費(fèi)的時(shí)間為：

OVO 模式與DAG-SVM 模式訓(xùn)練時(shí)所采用的方式是一樣的，即每?jī)蓚€(gè)類別訓(xùn)練一個(gè)分類器，每次訓(xùn)練用到2m/k 的樣本，共需訓(xùn)練k（k-1）/2個(gè)分類器，所以它們所用的時(shí)間為：

如上所示，當(dāng)我們的算法采用的是SMO 時(shí)，v 的值大約為2，此時(shí)公式（3）等于2cmv，也就是代表DAG-SVM 與OVO 訓(xùn)練所需的時(shí)間大約是2次SVM 單獨(dú)訓(xùn)練的時(shí)間，與OVR 相比有很大的優(yōu)勢(shì)，但是還是不夠，因?yàn)镈AG-SVM 處理的對(duì)象是大規(guī)模數(shù)據(jù)，所以當(dāng)類別數(shù)很多時(shí)，k（k-1）/2的分類器個(gè)數(shù)還是太過(guò)龐大?，F(xiàn)在針對(duì)于DAGSVM的訓(xùn)練時(shí)間過(guò)長(zhǎng)沒(méi)有太好的解決方法，因?yàn)樗?dú)特的有向無(wú)環(huán)圖結(jié)構(gòu)只能使得分類器個(gè)數(shù)較多。

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

本文對(duì)于有向無(wú)環(huán)圖支持向量機(jī)的原理進(jìn)行了闡述，分析了它的優(yōu)點(diǎn)，并針對(duì)它的兩個(gè)缺陷進(jìn)行了詳細(xì)的介紹，而且說(shuō)明了解決的方法。