亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

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

        2011-12-21 01:18:06焦樹軍安志江
        科技視界 2011年22期
        關(guān)鍵詞:超平面決策樹間隔

        焦樹軍 安志江

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

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

        焦樹軍 安志江

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

        決策樹歸納是歸納學(xué)習(xí)的一種。由于NP困難,尋找最優(yōu)的決策樹是不現(xiàn)實(shí)的,從而探索各種啟發(fā)式算法去產(chǎn)生一個高精度的決策樹變成了這類研究的焦點(diǎn)。考慮到支持向量機(jī)(SVM)的分類間隔與泛化能力的關(guān)系,可以使用SVM的最大間隔作為生成決策樹的啟發(fā)式信息,使得決策樹有較強(qiáng)的泛化能力。本文針對實(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算法是一個典型代表,這種方法生成的決策樹規(guī)模小且計(jì)算復(fù)雜度低,但其泛化能力(generalization)不佳。

        統(tǒng)計(jì)學(xué)習(xí)理論(Statistical Learning Theory或SLT)是一種專門研究小樣本情況下機(jī)器學(xué)習(xí)規(guī)律的理論,它是建立在一套較堅(jiān)實(shí)的理論基礎(chǔ)之上的,為解決有限樣本學(xué)習(xí)問題提供了一個統(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ì)量的決策樹,最大限度地提高決策樹對新觀察事例的預(yù)測準(zhǔn)確性;另一方面,理論上它將兩種重要的歸納方法互補(bǔ)地結(jié)合在一起(支持向量機(jī)泛化能力強(qiáng)但得到的知識即超平面不易理解,決策樹泛化能力一般但歸納出的知識容易理解)。

        1 支持向量機(jī)

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

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

        可以被一個超平面

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

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

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

        并且有緊湊形式:

        容易驗(yàn)證,將樣本點(diǎn)無錯誤分開的超平面(1),其間隔為:

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

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

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

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

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

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

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

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

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

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

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

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

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

        2.1 算法描述

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

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

        以兩類問題為例,具體算法為:

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

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

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

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

        表2 測試精度對比表

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

        3 總結(jié)

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

        決策樹的生成過程是對結(jié)點(diǎn)進(jìn)行劃分的過程,而支持向量機(jī)反問題研究的是如何尋找具有最大間隔的劃分,因此可以將其應(yīng)用到?jīng)Q策樹歸納過程,用最大margin作為啟發(fā)式來生成決策樹,以提高其泛化能力。本文主要對基于最大間隔的決策樹歸納學(xué)習(xí)算法進(jìn)行了設(shè)計(jì)與實(shí)現(xiàn)。實(shí)驗(yà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算法.計(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.

        王爽]

        猜你喜歡
        超平面決策樹間隔
        全純曲線的例外超平面
        涉及分擔(dān)超平面的正規(guī)定則
        間隔問題
        一種針對不均衡數(shù)據(jù)集的SVM決策樹算法
        間隔之謎
        以較低截?cái)嘀財(cái)?shù)分擔(dān)超平面的亞純映射的唯一性問題
        決策樹和隨機(jī)森林方法在管理決策中的應(yīng)用
        電子制作(2018年16期)2018-09-26 03:27:06
        基于決策樹的出租車乘客出行目的識別
        數(shù)學(xué)年刊A輯(中文版)(2015年1期)2015-10-30 01:55:44
        基于肺癌CT的決策樹模型在肺癌診斷中的應(yīng)用
        丝袜av乱码字幕三级人妻| 国偷自产av一区二区三区| 国产高清吃奶成免费视频网站| 午夜无码国产18禁| 久久国产精品免费专区| 精品偷自拍另类在线观看| 国产一区二区三精品久久久无广告| 日韩爱爱网站| 99精品国产成人一区二区在线| 亚洲精品岛国av一区二区| 亚洲av首页在线| 久久久久国产精品免费免费搜索 | 国产精品国产三级国产aⅴ下载| 国产美女在线精品免费观看| 91精品国产丝袜在线拍| 日韩人妻有码中文字幕| 亚洲国产精品一区二区成人av| 免费看黄a级毛片| 久久AV中文一区二区三区| 亚洲一区二区三区乱码在线| 少妇激情一区二区三区99| 熟女少妇在线视频播放| 久久半精品国产99精品国产| 国产网友自拍视频在线观看| 久久亚洲av成人无码国产最大| 白又丰满大屁股bbbbb| 久久国产国内精品对话对白| 亚洲精品一区二区三区四区| 国产精品情侣呻吟对白视频| 成年无码av片完整版| 99成人无码精品视频| 特级黄色大片性久久久| 美女高潮黄又色高清视频免费| 7777精品久久久大香线蕉| 蜜桃av噜噜一区二区三区香| 精品人妻久久一区二区三区| 亚洲人午夜射精精品日韩 | 完整在线视频免费黄片| 亚洲一区二区刺激的视频| 国自产精品手机在线观看视频| 国产精品理人伦国色天香一区二区 |