決策樹是一種常見的機器學習方法，非常有名。決策樹可用于分類與回歸任務，在很多領域得到普遍應用。以分類任務為例，其目的是根據樣例的屬性預測其類别。決策樹分類器與人們日常決策時采用的邏輯非常相似。

以是否進行高爾夫運動為例，人們會根據天氣、溫度、濕度、風況等決定是否去打球。例如某人的決策邏輯為：如果天氣為陰天，則打球；如果天氣為晴天，還要看濕度情況，如果濕度較低則打球；如果天氣為雨天，… 。這一決策過程可以用樹狀結構表示：

在現實中你并不知道此人的決策邏輯，隻是收集到他的一些曆史數據，比如某天的天氣、溫度、濕度，以及他是否打了高爾夫。是否可以根據曆史數據将他的決策邏輯倒推出來，這才是機器學習該做的事情。

在數據挖掘中，對于類标簽未知的實例，通過回答一系列關于屬性的問題可以判定其類别，将一系列關于屬性的問題及回答組織成一顆決策樹。決策樹是一個分層結構，它有三種類型的節點：

• 根節點 決策問題的起點，一顆決策樹至少有一個根節點，它覆蓋全部樣例。
• 内部節點 内部節點對應一個屬性測試，屬性測試的每個結果用一條分支表示，該節點所包含的樣例集根據屬性測試結果劃分為多個子集，對應到它的各子節點中。
• 葉節點（終端節點） 葉節點對應決策結果，與一個類标簽相關聯。

決策樹構建完成後，對于任何一個樣例，存在從根節點到葉節點的一條路，對應一個屬性判定序列，根據判定結果将該樣例歸為某一類别。

決策樹形式簡潔、比較直觀、具有解釋性，對很多分類問題有較高的準确率，目前得到廣泛應用。

根據目标屬性的數據類型，決策樹大緻分為分類樹（classification tree）與回歸樹（regression tree）。目标屬性為标稱型的數據使用分類樹,目标屬性是連續數值型使用回歸樹，也有一些決策樹如分類與回歸樹（CART， Classification and Regression Tree），既能用于分類也能用于回歸。在集成學習方法中，可以構建多顆決策樹進行數據挖掘，比較著名的算法有随機森林。

決策樹已經得到廣泛而深入的研究。作為一種機器學習方法，決策樹的核心問題是如何根據訓練集構造一棵泛化能力強的決策樹。最早的決策樹算法是Hunt等人1966年提出。20世紀70年代著名機器學習專家Quinlan提出了決策樹歸納算法ID3，Quinlan後來對ID3做了一些改進，提出C4.5算法，後續還發展了商業化版本See5/C5.0。1986年統計學家Breiman等在其著作《Classification and Regression Tree》中提出CART算法。Kass于1980年提出了卡方自動交互檢測（CHAID），CHAID是一種基于調整後的顯着性檢驗（Bonferroni檢驗）的決策樹技術，可以産生多分支決策樹。CHAID可以用于回歸與分類，以及檢測變量之間的相互作用。決策樹也可作為基本模塊與集成方法結合起來，如随機森林、梯度提升決策樹（GBDT）等。

根據數據集構建決策樹有很多算法，著名的ID3、C4.5、CART等算法都采用貪心策略，自頂向下以遞歸方式構造決策樹。

在決策樹構造算法中有兩個關鍵問題：

（1）分裂準則。對非葉節點必須從多個屬性中選擇一個“最優”屬性，根據屬性測試結果将樣例集劃分為幾個子集。根據何種準則選擇“最優”屬性，使得決策樹的泛化能力較強，并且決策樹的構造簡單快速，是決策樹算法中的重要問題。

（2）終止條件。理想情況下，當節點包含的樣例都具有同樣的類标簽時，算法停止擴展。但是如果數據集有兩個以上的樣例具有同樣的屬性但類别不同，則不可能達到理想的終止條件。另外，為了追求算法效率或控制決策樹的規模，即使當前節點包含的樣例類标簽不一緻也有可能停止擴展，這樣的情形有多種，需要根據實際需要形成終止條件。