基于構(gòu)造超平面的兩階段決策樹算法的研究

1、基于構(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, t

2、he 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ī)器

3、學(xué)習(xí)和數(shù)據(jù)采集方面，決策樹已經(jīng)成為一種最廣泛的模型。一些決策樹分類器的算法，比如id33，c4.54，cart等，經(jīng)常被作為評價(jià)其他分類器性能的基準(zhǔn)。它之所以流行，是因?yàn)槠湫问胶唵巍⑴袛嘌杆?、解釋容易和精確度高。 1兩階段決策樹算法 1.1 兩階段構(gòu)造超平面構(gòu)造多變量決策樹的中心問題是，在每個(gè)測試節(jié)點(diǎn)內(nèi)對于連續(xù)的屬性如何研究分割超平面函數(shù)如式（1）：w1x1+w2x2+wnxn+threshold（閾值）=0，這里的x=（x1，x2xn，1）是一個(gè)圖形向量，它是由一個(gè)常數(shù)和n個(gè)描敘實(shí)例的特征組成的。wt=（w1，w2，wn，wn+1）是一個(gè)x的參數(shù)向量，也可以稱為權(quán)向量（本文中假設(shè)wt是一個(gè)單

4、位向量）。為了研究在每個(gè)測試決策樹節(jié)點(diǎn)內(nèi)構(gòu)造超平面的過程，首先調(diào)整方程式（2）：1w1x1+w2x2+wnxn=threshold，權(quán)向量wt=（w1，w2wn）可以看作是用函數(shù)2構(gòu)造的超平面的法線方向，然后我們可以將尋找超平面函數(shù)2的過程分為兩個(gè)步驟：首先找出標(biāo)準(zhǔn)向量wt，然后再找出參數(shù)閾值。使wt中至少有一個(gè)參數(shù)不等于0，得到的超平面就會向特征軸傾斜；使wt中只有一個(gè)參數(shù)不為0，例如wt=（0，0，wi，0），得到的超平面就會與特征軸垂直。顯然，如果在每個(gè)超平面的wt中只有一個(gè)參數(shù)不為0，構(gòu)造的決策樹將會退化為單變量樹。為了深入研究這個(gè)問題，首先我們作了一個(gè)定義1。 定義1設(shè)v=（v1，v

5、2vn）（單位向量）是實(shí)例空間p內(nèi)的一個(gè)方向向量，a=（a1，a2an）是實(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)，?坌ap，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是

6、實(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ù)的過程可以劃

7、分為兩個(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ù)。為了簡化問題

8、分析的復(fù)雜性，步驟1對輸入數(shù)據(jù)集進(jìn)行預(yù)處理。預(yù)處理數(shù)據(jù)集之后，步驟2構(gòu)造一個(gè)使用算法1的構(gòu)造決策樹樹（參見圖1）。一旦決策樹被構(gòu)造，它就會被修剪回來。在修剪階段有兩項(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.54和ccp cart來測試已修剪的構(gòu)造決策樹的性能和修剪

9、算法的影響。 2結(jié)論 在本文中，首先從幾何學(xué)角度重新解釋了構(gòu)造測試節(jié)點(diǎn)的過程，并在此基礎(chǔ)上，提出了兩階段方法來為決策樹的每個(gè)測試節(jié)點(diǎn)構(gòu)造超平面。第一階段尋找基于無監(jiān)督或監(jiān)督方法的合適的法線方向?；谝恍┤缁岷驮鲩L比的標(biāo)準(zhǔn)，第二階段找出在法線方向上的超平面的截距。最后提出了兩階段的構(gòu)造決策樹算法。 參考文獻(xiàn)： 1su，x.g.，tsai，c.-l.，& wang，c.（2009）.tree-structured model diagnostics for linear regression.mach learn 74：111-131. 2vens, c. struyf, j., schietgat, l., dzeroski, s., & blockeel，h.(2008). decision trees for hierarchical multi-label classification.mach learn,73:185-214. 3quinlan，j.r（1979）.discovering rules