决策树演算法

©TheMcGraw-HillCompanies,Inc.,2008第8章決策樹演算法8-2©TheMcGraw-HillCompanies,Inc.,2008大綱說明決策樹演算法的概念討論有趣決策規則的概念用一個實例來展示決策樹的規則探討決策樹的實際應用展示在龐大的資料集中如何應用決策樹在附錄中展示See5的決策樹分析過程8-3©TheMcGraw-HillCompanies,Inc.,2008決策樹在資料探勘的領域中，決策樹（decisiontrees）被認為是一種樹狀結構的規則（經常被稱為關聯性規則）。決策樹資料探勘包含了蒐集分析者認為與決策有關的變數，以及分析這些變數對預測結果的能力。決策樹提供了一種以規則為基礎的演算法：ID3決策樹以啟發式方法（entropyheuristic）來選擇哪個屬性適合成為下一個節點，這是與其他資料探勘工具在選擇分支上的不同處。8-4©TheMcGraw-HillCompanies,Inc.,2008決策樹的運作表8.1各種屬性值的組合8-5©TheMcGraw-HillCompanies,Inc.,2008決策樹的運作表8.2第一個規則8-6©TheMcGraw-HillCompanies,Inc.,2008決策樹的運作圖8.1貸款者的部分樹狀結構此結構使用了分類資料，這樣型態的樹被稱為分類樹。在做預估及預測的情況中，如果資料有連續的結果也可用樹狀結構來表示，這些樹就被稱為迴歸決策樹（regressiontree）。8-7©TheMcGraw-HillCompanies,Inc.,2008有趣的規則規則的有用性是用信任度和支持度來衡量。關聯規則的支持度（support）代表的是，在資料庫中此規則的變數在同一筆記錄出現的比率。最小信任度（confidencelevel）及支持度可以用來決定由決策樹方法所產生的規則（或其他關聯性規則）是否要加以保留。利用資料探勘找出意外的資訊（知識探索）具有極高的興趣度（interestingness）。8-8©TheMcGraw-HillCompanies,Inc.,2008機器學習機器學習（machinelearning）剛開始並沒有任何的假設，僅針對輸入資料與分類結果進行分析。雖然不考慮專家的判斷可能會被認為效率比較差，但是卻可避免人為的偏見。反覆的分割可以將資料分成更細微的小集合，最後的結果就是一株決策樹。8-9©TheMcGraw-HillCompanies,Inc.,2008機器學習表8.3過去20位貸款者的資料8-10©TheMcGraw-HillCompanies,Inc.,2008機器學習表8.4資料分組8-11©TheMcGraw-HillCompanies,Inc.,2008機器學習表8.5結果8-12©TheMcGraw-HillCompanies,Inc.,2008機器學習大多數的資料探勘軟體使用熵值（entropy）衡量每個變數的區別能力。由Koonce所提出的熵值公式8-13©TheMcGraw-HillCompanies,Inc.,2008機器學習表8.6年齡類別的熵值8-14©TheMcGraw-HillCompanies,Inc.,2008機器學習第一條規則第二條規則8-15©TheMcGraw-HillCompanies,Inc.,2008機器學習表8.7計算機率8-16©TheMcGraw-HillCompanies,Inc.,2008機器學習表8.8重算後的機率8-17©TheMcGraw-HillCompanies,Inc.,2008機器學習第三條規則表8.9以三條規則預測正確率8-18©TheMcGraw-HillCompanies,Inc.,2008機器學習第四條規則表8.10以四條規則預測正確率8-19©TheMcGraw-HillCompanies,Inc.,2008機器學習機器演算學習規則8-20©TheMcGraw-HillCompanies,Inc.,2008機器學習表8.11規則應用測試結果8-21©TheMcGraw-HillCompanies,Inc.,2008機器學習圖8.2規則組的決策樹8-22©TheMcGraw-HillCompanies,Inc.,2008機器學習表8.12規則組的錯差矩陣8-23©TheMcGraw-HillCompanies,Inc.,2008決策樹的應用存貨預測資料探勘模式是由歸納來產生規則。臨床醫療資料庫探勘根據約略集合理論（roughsettheory）發展一個以機率規則為基礎的歸納系統。軟體發展品質知識發掘的目標在於從過去發展模組的資料中發現樣式，如此可以對會發生錯誤的軟體模組有更好的預測。8-24©TheMcGraw-HillCompanies,Inc.,2008軟體發展品質第一個被CART演算法所辨認出的模式有以下規則8-25©TheMcGraw-HillCompanies,Inc.,2008軟體發展品質第二個被CART演算法所辨認出的模式有以下規則8-26©TheMcGraw-HillCompanies,Inc.,2008軟體發展品質—評估表8.13測試資料的軟體品質錯差矩陣表8.14測試資料的軟體品質錯差矩陣8-27©TheMcGraw-HillCompanies,Inc.,2008貸款系統資料表8.15針對低齡的分群資料8-28©TheMcGraw-HillCompanies,Inc.,2008貸款系統資料表8.16針對壯年的分類資料8-29©TheMcGraw-HillCompanies,Inc.,2008貸款系統資料表8.17針對高齡的分群資料8-30©TheMcGraw-HillCompanies,Inc.,2008貸款系統資料表8.18組合結果8-31©TheMcGraw-HillCompanies,Inc.,2008貸款系統資料表8.19年齡的熵值計算8-32©TheMcGraw-HillCompanies,Inc.,2008貸款系統資料第一條規則8.20第一規則的錯差矩陣8-33©TheMcGraw-HillCompanies,Inc.,2008貸款系統資料第二條規則表8.21案例的機率8-34©TheMcGraw-HillCompanies,Inc.,2008貸款系統資料表8.22前兩個規則的錯差矩陣表8.23重算後的機率8-35©TheMcGraw-HillCompanies,Inc.,2008貸款系統資料第三條規則表8.24三條規則的期望準確率8-36©TheMcGraw-HillCompanies,Inc.,2008貸款系統資料表8.25三條規則的錯差矩陣機器學習演算法停在8-37©TheMcGraw-HillCompanies,Inc.,2008貸款系統資料表8.26由均衡資料集得到的結果8-38©TheMcGraw-HillCompanies,Inc.,2008保險欺騙資料模式表8.27See5詐欺模式的錯差矩陣8-39©TheMcGraw-HillCompanies,Inc.,2008求職者資料使用前300個類別型觀察值當作訓練資料，規則如下：8-40©TheMcGraw-HillCompanies,Inc.,2008求職者資料表8.28求職者類別型測試資料的模式錯差矩陣8-41©TheMcGraw-HillCompanies,Inc.,2008求職者資料標準化的連續型資料集以See5的決策樹進行分析，產生的決策樹如下：8-42©TheMcGraw-HillCompanies,Inc.,2008求職者資料表8.29求職者分類模式的測試資料的錯差矩陣8-43©TheMcGraw-HillCompanies,Inc.,2008See5決策樹分析：資料清理表8A.1消費資料的變數8-44©TheMcGraw-HillCompanies,Inc.,2008資料清理表8A.2Cloth2的前5個觀察值8-45©TheMcGraw-HillCompanies,Inc.,2008資料探勘程序圖8A.1找出要載入的資料圖8A.2資料已載入8-46©TheMcGraw-HillCompanies,Inc.,2008資料探勘程序圖8A.3選擇分類的建構方式圖8A.4建構設定8-47©TheMcGraw-HillCompanies,Inc.,2008資料探勘程序圖8A.5經過訓練後的決策樹圖8A.6選擇使用分類8-48©TheMcGraw-HillCompanies,Inc.,2008資料探勘程序圖8A.7輸入樣本資料圖8A.8預測結果8-49©TheMcGraw-HillCompanies,Inc.,2008總結決策樹是非常有效且有用的資料探勘方法，是自動機器學習的一種應用。非常穩定，不會全然地受到雜訊和錯失資料的影響。可以處理大資料集，也可處理類別或數字型態的資料。對得到的結論有很好的解釋能力（規則可用自然語言表示，所以很容易和經理人員溝通）。