基於構造超平面的兩階段決策樹演算法的研究
摘要：如何在測試節點裡構造一個恰當的分割超平面是構造決策樹的關鍵，與單變數決策樹不同，多變數（傾斜）決策樹可以找到與特徵軸不垂直的超平面。本文將從幾何學角度說明構造測試節點的過程，提出了一種兩階段決策樹的演算法。
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.
0引言
決策樹有著許多不同的應用，其中包括診斷學裡面的長度衰退[1]、分等級的多級標籤的分類[2]等。在機器學習和資料採集方面，決策樹已經成為一種最廣泛的模型。一些決策樹分類器的演算法，比如ID3[3]，C4.5[4]，CART等，經常被作為評價其他分類器效能的基準。它之所以流行，是因為其形式簡單、判斷迅速、解釋容易和精確度高。
1兩階段決策樹演算法
1.1 兩階段構造超平面構造多變數決策樹的中心問題是，在每個測試節點內對於連續的屬性如何研究分割超平面函式如式（1）：w1x1+w2x2+…+wnxn+threshold（閾值）=0，這裡的X=（x1，x2…xn，1）是一個圖形向量，它是由一個常數和n個描敘例項的特徵組成的。WT=（w1，w2，…，wn，wn+1）是一個X的引數向量，也可以稱為權向量（本文中假設WT是一個單位向量）。為了研究在每個測試決策樹節點內構造超平面的過程，首先調整方程式（2）：1w1x1+w2x2+…+wnxn=threshold，權向量WT=（w1，w2…wn）可以看作是用函式2構造的超平面的法線方向，然後我們可以將尋找超平面函式2的過程分為兩個步驟：首先找出標準向量WT，然後再找出引數閾值。使WT中至少有一個引數不等於0，得到的超平面就會向特徵軸傾斜；使WT中只有一個引數不為0，例如WT=（0，0，…，wi，…，0），得到的超平面就會與特徵軸垂直。顯然，如果在每個超平面的WT中只有一個引數不為0，構造的決策樹將會退化為單變數樹。為了深入研究這個問題，首先我們作了一個定義1。
根據定義1可知，如把V當作標準軸，那麼a′就是V軸上的值。
命題1設H是用函式（2）構造的分割超平面，假設A和H的交點的標準成分是v，那麼v=threshold（閾值）。
證明設a=（a1，a2，…，an）是例項空間內的一點，?坌a∈P，a的標準成分b=∑1?燮i?燮nwiai。設a′=（a，a，…，a）是從a到標準軸的對映點，得到式（3）：b=∑1?燮i?燮nwiai=∑1?燮i?燮nwia。
設t=（t1，t2，…，tn）是A和例項空間P的交點，因為WT是例項空間p內的標準向量，所以t=a′。聯合（3）式，可以得到：b=∑1?燮i?燮nwia=∑1?燮i?燮nwiti=v。根據方程式（2），得到v=threshold（閾值）。
在權重向量WT內，如果只有一個引數不是0，例如WT=（0，0，…，wi，…，0），那麼命題1中法線方向是準確的一個例項空間特徵。因此，單變數決策樹滿足命題1。從這個角度來看，我們的框架是單變數決策樹的延伸。此外，一旦發現有法線方向，就可以簡單地解決超平面閾值：計算每個例項的標準成分作為一維空間值，然後根據一些標準（如基尼），尋找作為函式（2）閾值的最佳分割閾值。
1.2 兩階段決策樹演算法通過在1.1內的分析，尋找超平面函式的過程可以劃分為兩個階段。基於這個，介紹兩階段決策樹演算法，這種演算法通過兩個階段為每個測試節點構造超平面，如圖1。除了步驟2和3，此演算法和其他決策樹演算法沒有什麼區別。步驟2（第一階段），候選超平面的標準列表是用某種研究函式構造的。許多著名的方法可直接用在這裡尋找法線方向，如主成分分析，合作聯盟等。步驟3（第二階段）分為兩個階段：在第一階段中，每個候選超平面閾值是基於一些純判斷標準（如資訊增益率和基尼）。在尋找連續屬性分割點方面，這個階段類似於單變數決策樹演算法。在第二階段，此模型根據判斷標準從候選列表中選出最佳分割超平面。
在圖2中給出了構造兩階段決策樹的控制演算法。許多演算法只能處理一組特定的資料。為了簡化問題分析的複雜性，步驟1對輸入資料集進行預處理。預處理資料集之後，步驟2構造一個使用演算法1的構造決策樹樹（參見圖1）。一旦決策樹被構造，它就會被修剪回來。在修剪階段有兩項措施用以評估每個測試節點：如果它是葉指數，則在測試節點下對一些子樹指標（如錯誤率）和測試節點進行評估。如果是前者且後者滿足一些條件（如後者的錯誤率小於前者），則其根是節點的整個樹，由葉取代。不同的演算法，採用不同的修剪指標。Quinlan使用錯誤率評估基於統計界的評估[4]，BrEiman等人使用成本複雜性評估基於錯誤率和樹的規模（由葉節點數量來衡量）。但是我們採用EBP C4.5[4]和CCP CART來測試已修剪的構造決策樹的效能和修剪演算法的影響。
2結論
在本文中，首先從幾何學角度重新解釋了構造測試節點的過程，並在此基礎上，提出了兩階段方法來為決策樹的每個測試節點構造超平面。第一階段尋找基於無監督或監督方法的合適的法線方向。基於一些如基尼和增長比的標準，第二階段找出在法線方向上的超平面的截距。最後提出了兩階段的構造決策樹演算法。
參考文獻：
[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
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.
0引言
決策樹有著許多不同的應用，其中包括診斷學裡面的長度衰退[1]、分等級的多級標籤的分類[2]等。在機器學習和資料採集方面，決策樹已經成為一種最廣泛的模型。一些決策樹分類器的演算法，比如ID3[3]，C4.5[4]，CART等，經常被作為評價其他分類器效能的基準。它之所以流行，是因為其形式簡單、判斷迅速、解釋容易和精確度高。
1兩階段決策樹演算法
1.1 兩階段構造超平面構造多變數決策樹的中心問題是，在每個測試節點內對於連續的屬性如何研究分割超平面函式如式（1）：w1x1+w2x2+…+wnxn+threshold（閾值）=0，這裡的X=（x1，x2…xn，1）是一個圖形向量，它是由一個常數和n個描敘例項的特徵組成的。WT=（w1，w2，…，wn，wn+1）是一個X的引數向量，也可以稱為權向量（本文中假設WT是一個單位向量）。為了研究在每個測試決策樹節點內構造超平面的過程，首先調整方程式（2）：1w1x1+w2x2+…+wnxn=threshold，權向量WT=（w1，w2…wn）可以看作是用函式2構造的超平面的法線方向，然後我們可以將尋找超平面函式2的過程分為兩個步驟：首先找出標準向量WT，然後再找出引數閾值。使WT中至少有一個引數不等於0，得到的超平面就會向特徵軸傾斜；使WT中只有一個引數不為0，例如WT=（0，0，…，wi，…，0），得到的超平面就會與特徵軸垂直。顯然，如果在每個超平面的WT中只有一個引數不為0，構造的決策樹將會退化為單變數樹。為了深入研究這個問題，首先我們作了一個定義1。
根據定義1可知，如把V當作標準軸，那麼a′就是V軸上的值。
命題1設H是用函式（2）構造的分割超平面，假設A和H的交點的標準成分是v，那麼v=threshold（閾值）。
證明設a=（a1，a2，…，an）是例項空間內的一點，?坌a∈P，a的標準成分b=∑1?燮i?燮nwiai。設a′=（a，a，…，a）是從a到標準軸的對映點，得到式（3）：b=∑1?燮i?燮nwiai=∑1?燮i?燮nwia。
設t=（t1，t2，…，tn）是A和例項空間P的交點，因為WT是例項空間p內的標準向量，所以t=a′。聯合（3）式，可以得到：b=∑1?燮i?燮nwia=∑1?燮i?燮nwiti=v。根據方程式（2），得到v=threshold（閾值）。
在權重向量WT內，如果只有一個引數不是0，例如WT=（0，0，…，wi，…，0），那麼命題1中法線方向是準確的一個例項空間特徵。因此，單變數決策樹滿足命題1。從這個角度來看，我們的框架是單變數決策樹的延伸。此外，一旦發現有法線方向，就可以簡單地解決超平面閾值：計算每個例項的標準成分作為一維空間值，然後根據一些標準（如基尼），尋找作為函式（2）閾值的最佳分割閾值。
1.2 兩階段決策樹演算法通過在1.1內的分析，尋找超平面函式的過程可以劃分為兩個階段。基於這個，介紹兩階段決策樹演算法，這種演算法通過兩個階段為每個測試節點構造超平面，如圖1。除了步驟2和3，此演算法和其他決策樹演算法沒有什麼區別。步驟2（第一階段），候選超平面的標準列表是用某種研究函式構造的。許多著名的方法可直接用在這裡尋找法線方向，如主成分分析，合作聯盟等。步驟3（第二階段）分為兩個階段：在第一階段中，每個候選超平面閾值是基於一些純判斷標準（如資訊增益率和基尼）。在尋找連續屬性分割點方面，這個階段類似於單變數決策樹演算法。在第二階段，此模型根據判斷標準從候選列表中選出最佳分割超平面。
在圖2中給出了構造兩階段決策樹的控制演算法。許多演算法只能處理一組特定的資料。為了簡化問題分析的複雜性，步驟1對輸入資料集進行預處理。預處理資料集之後，步驟2構造一個使用演算法1的構造決策樹樹（參見圖1）。一旦決策樹被構造，它就會被修剪回來。在修剪階段有兩項措施用以評估每個測試節點：如果它是葉指數，則在測試節點下對一些子樹指標（如錯誤率）和測試節點進行評估。如果是前者且後者滿足一些條件（如後者的錯誤率小於前者），則其根是節點的整個樹，由葉取代。不同的演算法，採用不同的修剪指標。Quinlan使用錯誤率評估基於統計界的評估[4]，BrEiman等人使用成本複雜性評估基於錯誤率和樹的規模（由葉節點數量來衡量）。但是我們採用EBP C4.5[4]和CCP CART來測試已修剪的構造決策樹的效能和修剪演算法的影響。
2結論
在本文中，首先從幾何學角度重新解釋了構造測試節點的過程，並在此基礎上，提出了兩階段方法來為決策樹的每個測試節點構造超平面。第一階段尋找基於無監督或監督方法的合適的法線方向。基於一些如基尼和增長比的標準，第二階段找出在法線方向上的超平面的截距。最後提出了兩階段的構造決策樹演算法。
參考文獻：
[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