基于最大間隔的決策樹歸納算法

焦樹軍 安志江

(河北華航通信技術有限公司 河北 石家莊 050031)

基于最大間隔的決策樹歸納算法

焦樹軍 安志江

(河北華航通信技術有限公司 河北 石家莊 050031)

決策樹歸納是歸納學習的一種。由于NP困難，尋找最優(yōu)的決策樹是不現(xiàn)實的，從而探索各種啟發(fā)式算法去產生一個高精度的決策樹變成了這類研究的焦點。考慮到支持向量機(SVM)的分類間隔與泛化能力的關系，可以使用SVM的最大間隔作為生成決策樹的啟發(fā)式信息，使得決策樹有較強的泛化能力。本文針對實值型數(shù)據(jù)，提出了一種基于最大間隔的決策樹歸納算法。實驗結果表明了本文算法的有效性。

支持向量機；支持向量機反問題；間隔；決策樹歸納

0 引言

決策樹歸納是歸納學習中最實用最重要的學習和推理方法,由于構造最優(yōu)的決策樹問題已經被證明是NP完全問題[2,3,4],因此典型的決策樹學習算法都是在完全假設空間的自頂向下的貪心搜索算法，但各搜索算法所采用的啟發(fā)式有所不同。其中選用最小信息熵為啟發(fā)式信息的ID3算法是一個典型代表，這種方法生成的決策樹規(guī)模小且計算復雜度低，但其泛化能力(generalization)不佳。

統(tǒng)計學習理論(Statistical Learning Theory或SLT)是一種專門研究小樣本情況下機器學習規(guī)律的理論，它是建立在一套較堅實的理論基礎之上的,為解決有限樣本學習問題提供了一個統(tǒng)一的框架。V.Vapnik等人從六、七十年代開始致力于此方面研究[5]，到九十年代中期,隨著其理論的不斷發(fā)展和成熟，也由于神經網絡等學習方法在理論上缺乏實質性進展，統(tǒng)計學習理論開始受到越來越廣泛的重視[7,8]。在這一理論基礎上發(fā)展了一種新的通用學習方法——支持向量機(Support Vector Machine或SVM),它已初步表現(xiàn)出很多優(yōu)于已有方法的性能，尤其是較強的泛化能力。

根據(jù)統(tǒng)計學習理論，SVM分類間隔越大，泛化能力越強，考慮到這一關系，我們可以用最大間隔作為決策樹歸納的啟發(fā)式信息，以此來劃分決策樹結點，構造決策樹。一方面，可以從原始數(shù)據(jù)中產生高質量的決策樹，最大限度地提高決策樹對新觀察事例的預測準確性；另一方面，理論上它將兩種重要的歸納方法互補地結合在一起（支持向量機泛化能力強但得到的知識即超平面不易理解，決策樹泛化能力一般但歸納出的知識容易理解）。

1 支持向量機

1.1 支持向量機基本問題

支持向量機是由Vapnik等人提出并以統(tǒng)計學習理論為基礎的一種新的學習機器。其基本問題描述如下：設有訓練數(shù)據(jù)

可以被一個超平面

分開。如果這個向量集合被超平面沒有錯誤的分開，并且離超平面最近的向量與超平面之間的距離是最大的，則我們說這個向量集合被這個最優(yōu)超平面（或最大間隔超平面）分開。如圖1所示。

圖1 最優(yōu)分類超平面是以最大間隔將數(shù)據(jù)分開的超平面

我們使用下面的形式；來描述分類超平面：

并且有緊湊形式：

容易驗證，將樣本點無錯誤分開的超平面（1），其間隔為：

由統(tǒng)計學習理論可知，一超平面的泛化能力，即對未知樣本準確預測能力，取決于超平面的間隔margin，從而最優(yōu)超平面就是滿足條件（2）并且使得

最小化的超平面。并且通過解決下述優(yōu)化問題來構造最優(yōu)超平面：

最優(yōu)超平面是在線性可分的前提下討論的，在線性不可分的情況下，可以在條件中加入一個松弛變量ξi≥0，這時的最優(yōu)超平面稱為廣義最優(yōu)超平面，通過解決如下問題得到：

其中C是一個常數(shù)。最優(yōu)超平面可通過解下面對偶問題得到：

最優(yōu)分割超平面有如下形式：

事實上，對于大多數(shù)實際問題，樣本點在原空間中一般不是線性可分的，所以用上述方法往往得不到好的決策函數(shù)（最優(yōu)超平面）。為此，Vapnik將支持向量機從原空間中推廣至特征空間。其基本思想如下：支持向量機通過某種事先選擇的非線性映射將輸入向量x映射到一個高維特征空間Z，在這個高維特征空間中構造最優(yōu)分類超平面。如圖2。

圖2 支持向量機通過非線性映射將輸入空間映射到一個高維特征空間，在這個高維特征空間中構造最優(yōu)超平面

Vapnik等人發(fā)現(xiàn)，在特征空間中構造最優(yōu)超平面并不需要以顯示形式來考慮特征空間，而只需要能夠計算支持向量與特征空間中向量的內積。根據(jù)Hilbert-Schmidt定理，在Hilbert空間中兩個點的內積有下面的等價形式：

1.2 支持向量機反問題

對于給定的一組沒有決策屬性的樣本點，我們可以隨機的把其分為兩類。此時我們可以利用前面的知識來求出最優(yōu)分割超平面，并計算出最大間隔。若劃分為兩類的樣本點線性不可分，間隔計為0。顯然，間隔的大小取決于對原樣本點的隨機劃分，支持向量機反問題就是如何對樣本點進行劃分，才能使最優(yōu)分割超平面的間隔達到最大。支持向量機反問題是一個優(yōu)化問題，其數(shù)學描述如下：設S＝｝為一樣本集，其中 xi∈Rn，i＝1，2，..，N，Ω表示從S到{-1,1}的函數(shù)全體。對于給定的一個函數(shù)f∈Ω,集合S被劃分為兩個子

其中K(x1,x2)式滿足下面條件的對稱函數(shù)，也成為核函數(shù)。

所以有分割超平面有如下形式：集，并可以計算出其相應的間隔。我們用Margin(f)表示由函數(shù)f所決定的間隔（泛函），那么反問題就是要解決如下問題：

2 基于最大間隔的決策樹歸納學習

2.1 算法描述

考慮到支持向量機較強的泛化能力，我們可以將支持向量機反問題應用于決策樹的歸納過程，即在歸納過程中用最大margin來作為啟發(fā)式。

其設計思想為：對于一個給定的各屬性取值為連續(xù)型數(shù)據(jù)的訓練樣本集，一開始我們不考慮樣本的類別，通過求解SVM反問題，可以得到該樣本集的一個具有最大margin的劃分，即將樣本集分為兩個子集。這些子集被作為決策樹的分支，被標記為-1的樣本集合作為左支，被標記為+1的樣本集合作為右支，和這一劃分相對應的超平面被作為該結點處的決策函數(shù)。當我們對新來的樣本進行測試時，將其代入決策函數(shù)，取值為負被分到左支，取值為正被分到右支。

以兩類問題為例，具體算法為：

2.2 實驗結果

用最大間隔作為啟發(fā)式來生成決策樹和用最小熵作為啟發(fā)式生成二叉決策樹針對的均為實值型數(shù)據(jù)，我們從UCI數(shù)據(jù)庫中挑選了Iris，Rice，Pima，Image Segment四個實值型數(shù)據(jù)庫（表1列出了各個數(shù)據(jù)庫的特征），進行了實驗，對比了生成決策樹的測試精度。對于多類數(shù)據(jù)庫，只選取了其中的兩類來進行實驗。

實驗結果如表2所示，算法1代表二叉決策樹歸納算法，算法2代表基于最大間隔的決策樹歸納算法，所用時間為運行算法2所需的時間。

表1 數(shù)據(jù)庫特征表

表2 測試精度對比表

從實驗結果中可以看出，用最大margin做啟發(fā)式，將SVM的相關理論用于決策樹歸納過程，使決策樹的泛化能力在一定程度上得到了提高。

3 總結

啟發(fā)式算法是決策樹歸納學習的重要研究課題，由于NP困難，尋找最優(yōu)的決策樹是不現(xiàn)實的，從而探索各種啟發(fā)式算法去產生一個高精度的決策樹變成了這類研究的焦點。

決策樹的生成過程是對結點進行劃分的過程，而支持向量機反問題研究的是如何尋找具有最大間隔的劃分，因此可以將其應用到決策樹歸納過程，用最大margin作為啟發(fā)式來生成決策樹，以提高其泛化能力。本文主要對基于最大間隔的決策樹歸納學習算法進行了設計與實現(xiàn)。實驗數(shù)據(jù)表明該算法生成的決策樹的測試精度比用最小熵做啟發(fā)式的二叉決策樹有一定提高。

［1］Tom M.Mitchell,Machine Learning,The Mcgraw-Hill Companies Inc, Singapore,1997.

［2］Hyafil L,Rivest R L.Constructing Optimal Binary Decision Trees Is NPComplete[J].Info Proc Letters,1976,5(1)：15-17.

［3］Hong JR.AE1：An extension approximate method for general covering problem [J].International Journal of Computer and Information Science,1985,14(6)：421-437.

［4］謝競博,王熙照.基于屬性間交互信息的ID3算法.計算機工程與應用,2004：93-94.

［5］Vladimir N.Vapnik.Estimation of dependences based on empirical data.New York：Springer-Verlag,1982.

［6］Vladimir N.Vapnik.The nature of statistical learning theory.Berlin：Springer-Verlag,1995.

［7］Vladimir N.Vapnik.An overview of statistical learning theory,IEEE Trans.Neural Networks,1999,10(5)：88-999.

［8］王國勝,鐘義信.支持向量機的理論基礎：統(tǒng)計學習理論.計算機工程與應用, 2001,19：19-20.

王爽］