DAGSVM 多分類技術研究

沈 洋，戴月明

（江南大學物聯網工程學院，無錫 214122）

1 引言

DAG-SVM（Directed Acyclic Graph-Support Vector Machine）是Platt 教授于1999年根據有向無環圖（DAG）提出的另外一種基于SVM 的多類別分類器，它引入了OVO 分類器中利用每兩個類別作為基礎二類分類器的方法，保證了分類的準確率，而且采用了有向無環圖結構，使得每次分類只需要k-1個分類器，大大提升了分類的效率。但是由于采用了層次結構，也保留了層次結構固有的的缺陷：誤差累積，在上層的節點產生的錯誤會一直保留下來，因此，距離根節點越近的節點，對整個結構的分類結果影響越大。而DAG-SVM 的節點選取方式采用了隨機的方式，這就使得最終的分類結果十分的不穩定。另外，由于采用了與一對一相同的訓練方式，使得訓練耗費的時間比較長，這都是需要改進的。

2 有向無環圖支持向量機的原理

DAG-SVM 是一種以SVM 分類器作為基礎分類器，以有向無環圖作為拓撲結構的組合多類別分類器，它通過從全體類別集合中不斷的刪除不可能的類別，得到最終的結果。DAG-SVM 的具體分類過程如如圖1所示，根節點a 表示當前類別集合為全體類別{1，2，3，4}，經過分類器1-vs-4作用后，節點走到第二層，由于排除了一個類別4，因此當前類別集合為{1，2，3}，經過分類器1-vs-2作用后，節點走到了第三層d{1，3}，再經過分類器1-vs-3作用后，走到最后的葉節點類別1，因此，類別1即為最終的結果。

圖1 DAG-SVM拓撲圖

3 有向無環圖支持向量機的缺陷

DAGSVM 雖然通過特殊的層次結構[1]實現了分類速度的提升，但是也由于層次結構，使得它的準確率受到了一定的影響；另外，它在訓練階段使用了與一對一分類器同樣的方式，導致了分類的時間過長，下面將對這兩個問題進行詳細介紹。

3.1 誤差累積

所謂誤差累積，是指高層次所造成的錯誤會一直保留到最后的葉子結點，不會隨著層次的增加而消失，這是所有層次結構的缺陷。目前來說，克服誤差累積有兩種常用的方法：

（1）提高每個二分類器的準確率。因為我們在進行層次分類時，如果沒有特殊的策略，那么每個二分類器最終被放置的位置是隨機的，因此我們沒辦法針對特殊的二分類器進行一些提高準確率的操作，這時候我們只有將所有二分類器的性能都進行優化，使得所有的二分類器都有比較高的準確率，這樣可以保證不管什么樣地排列方式最終的效果都是不錯的。

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

3.2 訓練時間過長

除了誤差累積之外，DAG-SVM 的訓練時間也需要改善，因為DAG-SVM 的基礎分類器采用的是一對一分類器，這就使得每次都要訓練k（k-1）/2個分類器，當類別數目較大時，耗費的時間就會很多。

經過實驗證明：SVM 分類器針對全部樣本訓練一次所需要的時間為：

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

OVO 模式與DAG-SVM 模式訓練時所采用的方式是一樣的，即每兩個類別訓練一個分類器，每次訓練用到2m/k 的樣本，共需訓練k（k-1）/2個分類器，所以它們所用的時間為：

如上所示，當我們的算法采用的是SMO 時，v 的值大約為2，此時公式（3）等于2cmv，也就是代表DAG-SVM 與OVO 訓練所需的時間大約是2次SVM 單獨訓練的時間，與OVR 相比有很大的優勢，但是還是不夠，因為DAG-SVM 處理的對象是大規模數據，所以當類別數很多時，k（k-1）/2的分類器個數還是太過龐大。現在針對于DAGSVM的訓練時間過長沒有太好的解決方法，因為它獨特的有向無環圖結構只能使得分類器個數較多。

4 結束語

本文對于有向無環圖支持向量機的原理進行了闡述，分析了它的優點，并針對它的兩個缺陷進行了詳細的介紹，而且說明了解決的方法。