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

焦樹軍 安志江

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

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

焦樹軍 安志江

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

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

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

0 引言

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

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

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

1 支持向量機(jī)

1.1 支持向量機(jī)基本問題

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

可以被一個(gè)超平面

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

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

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

并且有緊湊形式：

容易驗(yàn)證，將樣本點(diǎn)無錯(cuò)誤分開的超平面（1），其間隔為：

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

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

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

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

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

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

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

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

1.2 支持向量機(jī)反問題

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

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

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

2 基于最大間隔的決策樹歸納學(xué)習(xí)

2.1 算法描述

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

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

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

2.2 實(shí)驗(yàn)結(jié)果

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

實(shí)驗(yàn)結(jié)果如表2所示，算法1代表二叉決策樹歸納算法，算法2代表基于最大間隔的決策樹歸納算法，所用時(shí)間為運(yùn)行算法2所需的時(shí)間。

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

表2 測(cè)試精度對(duì)比表

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

3 總結(jié)

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

決策樹的生成過程是對(duì)結(jié)點(diǎn)進(jìn)行劃分的過程，而支持向量機(jī)反問題研究的是如何尋找具有最大間隔的劃分，因此可以將其應(yīng)用到?jīng)Q策樹歸納過程，用最大margin作為啟發(fā)式來生成決策樹，以提高其泛化能力。本文主要對(duì)基于最大間隔的決策樹歸納學(xué)習(xí)算法進(jìn)行了設(shè)計(jì)與實(shí)現(xiàn)。實(shí)驗(yàn)數(shù)據(jù)表明該算法生成的決策樹的測(cè)試精度比用最小熵做啟發(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］謝競(jìng)博,王熙照.基于屬性間交互信息的ID3算法.計(jì)算機(jī)工程與應(yīng)用,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］王國勝,鐘義信.支持向量機(jī)的理論基礎(chǔ)：統(tǒng)計(jì)學(xué)習(xí)理論.計(jì)算機(jī)工程與應(yīng)用, 2001,19：19-20.

王爽］