- 相關(guān)推薦
基于構造超平面的兩階段決策樹(shù)算法的研究
摘要：如何在測試節點(diǎn)里構造一個(gè)恰當的分割超平面是構造決策樹(shù)的關(guān)鍵，與單變量決策樹(shù)不同，多變量（傾斜）決策樹(shù)可以找到與特征軸不垂直的超平面。本文將從幾何學(xué)角度說(shuō)明構造測試節點(diǎn)的過(guò)程，提出了一種兩階段決策樹(shù)的算法。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)鍵詞：超平面；兩階段；決策樹(shù)
0引言
決策樹(shù)有著(zhù)許多不同的應用，其中包括診斷學(xué)里面的長(cháng)度衰退[1]、分等級的多級標簽的分類(lèi)[2]等。在機器學(xué)習和數據采集方面，決策樹(shù)已經(jīng)成為一種最廣泛的模型。一些決策樹(shù)分類(lèi)器的算法，比如ID3[3]，C4.5[4]，CART等，經(jīng)常被作為評價(jià)其他分類(lèi)器性能的基準。它之所以流行，是因為其形式簡(jiǎn)單、判斷迅速、解釋容易和精確度高。
1兩階段決策樹(shù)算法
1.1 兩階段構造超平面構造多變量決策樹(shù)的中心問(wèn)題是，在每個(gè)測試節點(diǎn)內對于連續的屬性如何研究分割超平面函數如式（1）：w1x1+w2x2+…+wnxn+threshold（閾值）=0，這里的X=（x1，x2…xn，1）是一個(gè)圖形向量，它是由一個(gè)常數和n個(gè)描敘實(shí)例的特征組成的。WT=（w1，w2，…，wn，wn+1）是一個(gè)X的參數向量，也可以稱(chēng)為權向量（本文中假設WT是一個(gè)單位向量）。為了研究在每個(gè)測試決策樹(shù)節點(diǎn)內構造超平面的過(guò)程，首先調整方程式（2）：1w1x1+w2x2+…+wnxn=threshold，權向量WT=（w1，w2…wn）可以看作是用函數2構造的超平面的法線(xiàn)方向，然后我們可以將尋找超平面函數2的過(guò)程分為兩個(gè)步驟：首先找出標準向量WT，然后再找出參數閾值。使WT中至少有一個(gè)參數不等于0，得到的超平面就會(huì )向特征軸傾斜；使WT中只有一個(gè)參數不為0，例如WT=（0，0，…，wi，…，0），得到的超平面就會(huì )與特征軸垂直。顯然，如果在每個(gè)超平面的WT中只有一個(gè)參數不為0，構造的決策樹(shù)將會(huì )退化為單變量樹(shù)。為了深入研究這個(gè)問(wèn)題，首先我們作了一個(gè)定義1。
定義1設V=（v1，v2…vn）（單位向量）是實(shí)例空間P內的一個(gè)方向向量，a=（a1，a2…an）是實(shí)例空間P內的一點(diǎn)。?坌a，如果a′=∑1?燮i?燮naivi，我們就說(shuō)a′是a的V成分。
根據定義1可知，如把V當作標準軸，那么a′就是V軸上的值。
命題1設H是用函數（2）構造的分割超平面，假設A和H的交點(diǎn)的標準成分是v，那么v=threshold（閾值）。
證明設a=（a1，a2，…，an）是實(shí)例空間內的一點(diǎn)，?坌a∈P，a的標準成分b=∑1?燮i?燮nwiai。設a′=（a，a，…，a）是從a到標準軸的映射點(diǎn)，得到式（3）：b=∑1?燮i?燮nwiai=∑1?燮i?燮nwia。
設t=（t1，t2，…，tn）是A和實(shí)例空間P的交點(diǎn)，因為WT是實(shí)例空間p內的標準向量，所以t=a′。聯(lián)合（3）式，可以得到：b=∑1?燮i?燮nwia=∑1?燮i?燮nwiti=v。根據方程式（2），得到v=threshold（閾值）。
在權重向量WT內，如果只有一個(gè)參數不是0，例如WT=（0，0，…，wi，…，0），那么命題1中法線(xiàn)方向是準確的一個(gè)實(shí)例空間特征。因此，單變量決策樹(shù)滿(mǎn)足命題1。從這個(gè)角度來(lái)看，我們的框架是單變量決策樹(shù)的延伸。此外，一旦發(fā)現有法線(xiàn)方向，就可以簡(jiǎn)單地解決超平面閾值：計算每個(gè)實(shí)例的標準成分作為一維空間值，然后根據一些標準（如基尼），尋找作為函數（2）閾值的最佳分割閾值。
1.2 兩階段決策樹(shù)算法通過(guò)在1.1內的分析，尋找超平面函數的過(guò)程可以劃分為兩個(gè)階段�；谶@個(gè)，介紹兩階段決策樹(shù)算法，這種算法通過(guò)兩個(gè)階段為每個(gè)測試節點(diǎn)構造超平面，如圖1。除了步驟2和3，此算法和其他決策樹(shù)算法沒(méi)有什么區別。步驟2（第一階段），候選超平面的標準列表是用某種研究函數構造的。許多著(zhù)名的方法可直接用在這里尋找法線(xiàn)方向，如主成分分析，合作聯(lián)盟等。步驟3（第二階段）分為兩個(gè)階段：在第一階段中，每個(gè)候選超平面閾值是基于一些純判斷標準（如信息增益率和基尼）。在尋找連續屬性分割點(diǎn)方面，這個(gè)階段類(lèi)似于單變量決策樹(shù)算法。在第二階段，此模型根據判斷標準從候選列表中選出最佳分割超平面。
在圖2中給出了構造兩階段決策樹(shù)的控制算法。許多算法只能處理一組特定的數據。為了簡(jiǎn)化問(wèn)題分析的復雜性，步驟1對輸入數據集進(jìn)行預處理。預處理數據集之后，步驟2構造一個(gè)使用算法1的構造決策樹(shù)樹(shù)（參見(jiàn)圖1）。一旦決策樹(shù)被構造，它就會(huì )被修剪回來(lái)。在修剪階段有兩項措施用以評估每個(gè)測試節點(diǎn)：如果它是葉指數，則在測試節點(diǎn)下對一些子樹(shù)指標（如錯誤率）和測試節點(diǎn)進(jìn)行評估。如果是前者且后者滿(mǎn)足一些條件（如后者的錯誤率小于前者），則其根是節點(diǎn)的整個(gè)樹(shù)，由葉取代。不同的算法，采用不同的修剪指標。Quinlan使用錯誤率評估基于統計界的評估[4]，BrEiman等人使用成本復雜性評估基于錯誤率和樹(shù)的規模（由葉節點(diǎn)數量來(lái)衡量）。但是我們采用EBP C4.5[4]和CCP CART來(lái)測試已修剪的構造決策樹(shù)的性能和修剪算法的影響。
2結論
在本文中，首先從幾何學(xué)角度重新解釋了構造測試節點(diǎn)的過(guò)程，并在此基礎上，提出了兩階段方法來(lái)為決策樹(shù)的每個(gè)測試節點(diǎn)構造超平面。第一階段尋找基于無(wú)監督或監督方法的合適的法線(xiàn)方向�；谝恍┤缁岷驮鲩L(cháng)比的標準，第二階段找出在法線(xiàn)方向上的超平面的截距。最后提出了兩階段的構造決策樹(shù)算法。
參考文獻：
[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
【基于構造超平面的兩階段決策樹(shù)算法的研究】相關(guān)文章：
粗決策樹(shù)動(dòng)態(tài)規則提取算法研究及應用03-17
基于DCT變換域自適應水印算法的研究03-07
基于決策樹(shù)方法的員工素質(zhì)與績(jì)效關(guān)聯(lián)分析研究11-18
基于NNVD的網(wǎng)絡(luò )化軟件多步控制算法研究03-11
基于BP算法紅外遙感圖像去條帶方法研究03-07