決策樹方法

決策樹是一種從無次序、無規則的樣本數據集中推理出決策樹表示形式的分類規則方法。它採用自頂向下的遞歸方式，在決策樹的內部節點進行屬性值的比較並根據不同的屬性值判斷從該節點向下的分支．在決策樹的葉節點得到結論．因此從根節點到葉節點的一條路徑就對應着一條規則．整棵決策樹就對應着一組表達式規則。

分類決策樹模型是一種描述對實例進行分類的樹形結構，決策樹由節點和有向邊組成。節點有兩種類型：內部節點和葉節點。內部節點表示一個特徵或屬性．葉節點表示一個類。用決策樹分類，從根節點開始，對實例的某一特徵進行測試，根據測試結果，將實例分配到其子節點；這時，每一個子節點對應着該特徵的一個取值。如此遞歸地對實例進行測試並分配，直到達到葉節點。最後將實例分到葉節點的類中。決策樹學習算法是以實例為基礎的歸納學習算法，本質上是從訓練數據集中歸納出一組分類規則，與訓練數據集不相矛盾的決策樹可能有多個，也可能一個也沒有。我們需要的是一個與訓練數據集矛盾較小的決策樹，同時具有很好的泛化能力。 ^[1] 

決策樹的節點為方塊、圓圈、和三角，節點間通過直線段連接，如

□一表示決策節點。從它引出的分支叫方案分支，每支代表一個方案。決策節點上標註的數字是所選方案的期望值。

○一表示方案節點。從它引出的分支叫概率分支。分支數反映可能的自然狀態數。分支上註明的數字為該自然狀態的概率。

△一表示結果節點。它旁邊標註的數字為方案在某種自然狀態下的收益值。

應用樹狀圖進行決策的過程，是由右向左逐步前進，計算右端的期望收益值，或損失值，然後對不同方案的期望收益值的大小進行選擇。方案的捨棄稱為剪支。最後決策節點只留下唯一的一個，就是最優的決策方案。 ^[2] 

決策樹法的幾個關鍵步驟是：

(1)畫出決策樹，畫決策樹的過程也就是對未來可能發生的各種事件進行周密思考、預測的過程，把這些情況用樹狀圖表示出來．先畫決策點，再找方案分枝和方案點．最後再畫出概率分枝．

(2)由專家估計法或用試驗數據推算出概率值．並把概率寫在概率分枝的位置上．

(3)計算益損期望值，從樹梢開始，由右向左的順序進行．用期望值法計算．若決策目標是盈利時，比較各分枝，取期望值最大的分枝，其他分枝進行修剪．

用決策樹法可以進行多級決策．多級決策(序貫決策)的決策樹至少有兩個或以上決策點． ^[3] 

決策樹法尤其適用於序貫決策(多級決策)，是描述序貫決策的有力工具．用決策樹來進行決策。具有分析思路清晰、決策結果形象明確的優點． ^[3] 

決策樹方法簡便易學，具有廣泛的實用價值。由於多階段問題由若干單階段問題構成，所以決策樹方法不僅可以解決多階段問題，也可以解決單階段問題。但考慮到它在解決多階段問題上的作用無法被一般方法代替，故將其單獨介紹，不過介紹仍然從單階段問題開始。 ^[4] 

採用傳統的決策樹進行決策或分類存在着侷限性，以變量的某一閾值作為決策或分類的判別條件(如X>Ti)，變量取值在該閾值上下將引起決策或分類的突變(不連續性)，決策或分類結果對於閾值取值很敏感，並且決策樹的知識可理解性較差。克服上述侷限性的改進方法是，對決策或分類的條件和目標變量的取值進行雲離散化表達，基於雲理論的決策樹既增加了知識的可理解性又確保決策或分類結果的連續性。

自20世紀60年代以來，決策樹方法在分類、預測、規則提取等領域有着廣泛應用，特別是在Quilan提出ID3算法以後，在機器學習、知識發現領域得到了進一步應用及發展。決策樹的優點在於它的直觀和易理解性，但在許多應用中變量值是連續和漸變的，並且在許多情況下，並不要求得到精確的輸出預報值，而是能夠將輸出控制在一定的範圍內或作出決策分類。採用傳統的決策樹進行決策或分類存在着侷限性，以變量的某一閾值作為決策或分類的判別條件(如X>正)，變量取值在該閾值上下將引起決策或分類的突變(不連續性)，決策或分類結果對於閾值取值很敏感，並且決策樹的知識可理解性較差。克服上述侷限性的改進方法是，對決策或分類的條件和目標變量的取值進行雲離散化表達，基於雲理論的決策樹既增加了知識的可理解性又確保決策或分類結果的連續性。 ^[5]