什麼是決策樹？

決策樹是一種類似流程圖的樹形機制，其中每個內部節點表示對屬性的測試，每個分支定義測試的結果，葉子節點描述類別或類別分佈。樹中最高的節點是根節點。

學習決策樹的演算法

演算法 − 從給定的訓練資訊中建立決策樹。

輸入 − 由離散值屬性描述的訓練樣本；屬性集，屬性列表。

輸出 − 決策樹。

方法

  • 建立一個節點 N；

  • 如果樣本全部屬於同一類別 C，則

  • 將 N 返回為標記為類別 C 的葉子節點

  • 如果屬性列表為空，則

  • 將 N 返回為標記為樣本中最常見類別的葉子節點。 // 多數投票

  • 選擇測試屬性，即屬性列表中資訊增益最高的屬性。

  • 用測試屬性標記節點 N。

  • 對於測試屬性的每個已知值 ai // 分割槽樣本。

  • 為條件測試屬性 = ai 從節點 N 增長一個分支。

  • 令 si 為樣本中測試屬性 = ai 的樣本集。

  • 如果 si 為空，則

  • 它可以連線一個標記為樣本中最常見類別的葉子。

  • 否則，附加由生成決策樹 (si，屬性列表 - 測試屬性) 返回的節點

決策樹歸納

例如，決策規則的自動生成被稱為規則歸納或自動規則歸納。它可以建立決策樹隱式設計中的決策規則也經常被稱為規則歸納，但是術語樹歸納或決策樹歸納經常被選擇。

決策樹歸納的基本演算法是一種貪婪演算法。它用於以自上而下遞迴分治的方式生成決策樹。學習決策樹的基本演算法是 ID3 的一種形式，一種著名的決策樹歸納演算法。

基本方法如下：

  • 樹開始時是一個單獨的節點，定義訓練樣本。

  • 如果樣本全部屬於相同的類別，則該節點變為葉子節點，並用該類別標記。

  • 該演算法應用一種基於熵的度量，稱為資訊增益，作為選擇將樣本劃分為單個類別的屬性的啟發式方法。此屬性成為節點的“測試”或“決策”屬性。在這種演算法形式中，所有屬性都是分類的，即離散值的。連續值屬性應離散化。

  • 為測試屬性的每個已知值生成一個分支，並相應地劃分樣本。

  • 該演算法使用類似的迴圈過程來為每個分支的樣本形成決策樹。因為一個屬性已出現在一個節點上，所以它不需要在其一些後代節點中處理。

更新於：2021年11月22日

3K+ 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始學習
廣告