- 相關(guān)推薦
基于構(gòu)造超平面的兩階段決策樹算法的研究
摘要:如何在測試節(jié)點(diǎn)里構(gòu)造一個(gè)恰當(dāng)?shù)姆指畛矫媸菢?gòu)造決策樹的關(guān)鍵,與單變量決策樹不同,多變量(傾斜)決策樹可以找到與特征軸不垂直的超平面。本文將從幾何學(xué)角度說明構(gòu)造測試節(jié)點(diǎn)的過程,提出了一種兩階段決策樹的算法。Abstract: How to construct an appropriate partitioning hyperplane in test node is the key to construct a decision tree. Different from decision tree with a single variable, the multi-variable (tilted) decision tree can find a hyperplane which is not perpendicular to the characteristic shaft. This paper will explain the process of constructing the test node and propose a two-stage decision tree algorithm.
關(guān)鍵詞:超平面;兩階段;決策樹
0引言
決策樹有著許多不同的應(yīng)用,其中包括診斷學(xué)里面的長度衰退[1]、分等級的多級標(biāo)簽的分類[2]等。在機(jī)器學(xué)習(xí)和數(shù)據(jù)采集方面,決策樹已經(jīng)成為一種最廣泛的模型。一些決策樹分類器的算法,比如ID3[3],C4.5[4],CART等,經(jīng)常被作為評價(jià)其他分類器性能的基準(zhǔn)。它之所以流行,是因?yàn)槠湫问?u>簡單、判斷迅速、解釋容易和精確度高。
1兩階段決策樹算法
1.1 兩階段構(gòu)造超平面構(gòu)造多變量決策樹的中心問題是,在每個(gè)測試節(jié)點(diǎn)內(nèi)對于連續(xù)的屬性如何研究分割超平面函數(shù)如式(1):w1x1+w2x2+…+wnxn+threshold(閾值)=0,這里的X=(x1,x2…xn,1)是一個(gè)圖形向量,它是由一個(gè)常數(shù)和n個(gè)描敘實(shí)例的特征組成的。WT=(w1,w2,…,wn,wn+1)是一個(gè)X的參數(shù)向量,也可以稱為權(quán)向量(本文中假設(shè)WT是一個(gè)單位向量)。為了研究在每個(gè)測試決策樹節(jié)點(diǎn)內(nèi)構(gòu)造超平面的過程,首先調(diào)整方程式(2):1w1x1+w2x2+…+wnxn=threshold,權(quán)向量WT=(w1,w2…wn)可以看作是用函數(shù)2構(gòu)造的超平面的法線方向,然后我們可以將尋找超平面函數(shù)2的過程分為兩個(gè)步驟:首先找出標(biāo)準(zhǔn)向量WT,然后再找出參數(shù)閾值。使WT中至少有一個(gè)參數(shù)不等于0,得到的超平面就會(huì)向特征軸傾斜;使WT中只有一個(gè)參數(shù)不為0,例如WT=(0,0,…,wi,…,0),得到的超平面就會(huì)與特征軸垂直。顯然,如果在每個(gè)超平面的WT中只有一個(gè)參數(shù)不為0,構(gòu)造的決策樹將會(huì)退化為單變量樹。為了深入研究這個(gè)問題,首先我們作了一個(gè)定義1。
定義1設(shè)V=(v1,v2…vn)(單位向量)是實(shí)例空間P內(nèi)的一個(gè)方向向量,a=(a1,a2…an)是實(shí)例空間P內(nèi)的一點(diǎn)。?坌a,如果a′=∑1?燮i?燮naivi,我們就說a′是a的V成分。
根據(jù)定義1可知,如把V當(dāng)作標(biāo)準(zhǔn)軸,那么a′就是V軸上的值。
命題1設(shè)H是用函數(shù)(2)構(gòu)造的分割超平面,假設(shè)A和H的交點(diǎn)的標(biāo)準(zhǔn)成分是v,那么v=threshold(閾值)。
證明設(shè)a=(a1,a2,…,an)是實(shí)例空間內(nèi)的一點(diǎn),?坌a∈P,a的標(biāo)準(zhǔn)成分b=∑1?燮i?燮nwiai。設(shè)a′=(a,a,…,a)是從a到標(biāo)準(zhǔn)軸的映射點(diǎn),得到式(3):b=∑1?燮i?燮nwiai=∑1?燮i?燮nwia。
設(shè)t=(t1,t2,…,tn)是A和實(shí)例空間P的交點(diǎn),因?yàn)閃T是實(shí)例空間p內(nèi)的標(biāo)準(zhǔn)向量,所以t=a′。聯(lián)合(3)式,可以得到:b=∑1?燮i?燮nwia=∑1?燮i?燮nwiti=v。根據(jù)方程式(2),得到v=threshold(閾值)。
在權(quán)重向量WT內(nèi),如果只有一個(gè)參數(shù)不是0,例如WT=(0,0,…,wi,…,0),那么命題1中法線方向是準(zhǔn)確的一個(gè)實(shí)例空間特征。因此,單變量決策樹滿足命題1。從這個(gè)角度來看,我們的框架是單變量決策樹的延伸。此外,一旦發(fā)現(xiàn)有法線方向,就可以簡單地解決超平面閾值:計(jì)算每個(gè)實(shí)例的標(biāo)準(zhǔn)成分作為一維空間值,然后根據(jù)一些標(biāo)準(zhǔn)(如基尼),尋找作為函數(shù)(2)閾值的最佳分割閾值。
1.2 兩階段決策樹算法通過在1.1內(nèi)的分析,尋找超平面函數(shù)的過程可以劃分為兩個(gè)階段;谶@個(gè),介紹兩階段決策樹算法,這種算法通過兩個(gè)階段為每個(gè)測試節(jié)點(diǎn)構(gòu)造超平面,如圖1。除了步驟2和3,此算法和其他決策樹算法沒有什么區(qū)別。步驟2(第一階段),候選超平面的標(biāo)準(zhǔn)列表是用某種研究函數(shù)構(gòu)造的。許多著名的方法可直接用在這里尋找法線方向,如主成分分析,合作聯(lián)盟等。步驟3(第二階段)分為兩個(gè)階段:在第一階段中,每個(gè)候選超平面閾值是基于一些純判斷標(biāo)準(zhǔn)(如信息增益率和基尼)。在尋找連續(xù)屬性分割點(diǎn)方面,這個(gè)階段類似于單變量決策樹算法。在第二階段,此模型根據(jù)判斷標(biāo)準(zhǔn)從候選列表中選出最佳分割超平面。
在圖2中給出了構(gòu)造兩階段決策樹的控制算法。許多算法只能處理一組特定的數(shù)據(jù)。為了簡化問題分析的復(fù)雜性,步驟1對輸入數(shù)據(jù)集進(jìn)行預(yù)處理。預(yù)處理數(shù)據(jù)集之后,步驟2構(gòu)造一個(gè)使用算法1的構(gòu)造決策樹樹(參見圖1)。一旦決策樹被構(gòu)造,它就會(huì)被修剪回來。在修剪階段有兩項(xiàng)措施用以評估每個(gè)測試節(jié)點(diǎn):如果它是葉指數(shù),則在測試節(jié)點(diǎn)下對一些子樹指標(biāo)(如錯(cuò)誤率)和測試節(jié)點(diǎn)進(jìn)行評估。如果是前者且后者滿足一些條件(如后者的錯(cuò)誤率小于前者),則其根是節(jié)點(diǎn)的整個(gè)樹,由葉取代。不同的算法,采用不同的修剪指標(biāo)。Quinlan使用錯(cuò)誤率評估基于統(tǒng)計(jì)界的評估[4],BrEiman等人使用成本復(fù)雜性評估基于錯(cuò)誤率和樹的規(guī)模(由葉節(jié)點(diǎn)數(shù)量來衡量)。但是我們采用EBP C4.5[4]和CCP CART來測試已修剪的構(gòu)造決策樹的性能和修剪算法的影響。
2結(jié)論
在本文中,首先從幾何學(xué)角度重新解釋了構(gòu)造測試節(jié)點(diǎn)的過程,并在此基礎(chǔ)上,提出了兩階段方法來為決策樹的每個(gè)測試節(jié)點(diǎn)構(gòu)造超平面。第一階段尋找基于無監(jiān)督或監(jiān)督方法的合適的法線方向。基于一些如基尼和增長比的標(biāo)準(zhǔn),第二階段找出在法線方向上的超平面的截距。最后提出了兩階段的構(gòu)造決策樹算法。
參考文獻(xiàn):
[1]Su,X.G.,Tsai,C.-L.,& Wang,C.(2009).Tree-structured model diagnostics for linear regression.Mach Learn 74:111-131.
[2]Vens, C. Struyf, J., Schietgat, L., Dzeroski, S., & Blockeel,H.(2008). Decision trees for hierarchical multi-label classification.Mach Learn,73:185-214.
[3]Quinlan,J.R(1979).Discovering rules by induction from large collection of examples.In D.Michie,editor.
[4]Quinlan J R.(1993).C4.5:Programs for Machine Learning[M].San Mateo,CA:Morgan Kaufman
【基于構(gòu)造超平面的兩階段決策樹算法的研究】相關(guān)文章:
基于minigui的網(wǎng)真機(jī)界面的實(shí)現(xiàn)08-05
基于戰(zhàn)略治理的企業(yè)環(huán)境風(fēng)險(xiǎn)研究08-28
基于BP網(wǎng)遙感影像分類研究與應(yīng)用08-10
基于軍網(wǎng)的雷達(dá)遠(yuǎn)程診斷技術(shù)研究08-10
基于web的異地并行設(shè)計(jì)與制造系統(tǒng)研究06-02
基于知網(wǎng)的翻譯研究方向碩士畢業(yè)論文寫作06-25
《基于繪本的小學(xué)低段激趣作文的研究》開題報(bào)告08-10
基于價(jià)值網(wǎng)的企業(yè)集群式供給鏈治理模式研究04-28
基于J2EE的遠(yuǎn)動(dòng)系統(tǒng)Web實(shí)時(shí)曲線的研究05-11
我國現(xiàn)階段人力資源信息化研究06-04