1.6.3　決策樹算法面臨的基本問題

若屬性值的每種組合都在訓練集中出現，而且每種組合都具備唯一的類標號，則Hunt算法是有效的。但對于大多數的實際狀況來說，這一假設并不現實，所以，須要額外的條件來處理如下狀況：

●在第二步中，算法所建立的子節點可能為空，即不存在與這些節點相關聯的記錄數據。若是沒有一個訓練記錄包含與這樣的節點相關聯的屬性組合（這種情形就有可能發生），這時，該節點成為葉子節點，類標號為其父節點所關聯記錄集中類別個數最多的類別。

●在第二步中，若與D相關聯的全部記錄都具備相同的屬性值（類標號除外），則沒有屬性可用于進一步劃分當前記錄集，這時可采用投票原則（少數服從多數）將當前節點強制設為葉子節點，其類標號為該節點所關聯記錄集中類別個數最多的類別。

由Hunt算法的基本思想，我們能夠看到，決策樹算法必須解決如下問題。

1. 如何分割訓練記錄數據集？如何選擇屬性？

記錄數據集的分割對決策樹的構造有巨大影響。它主要由兩個因素決定：一是選擇哪個屬性；二是如何劃分該屬性的值并選擇分割點，這個方面與屬性的數據類型密切相關。

2. 如何處理不同屬性的數據類型？如何設定對應的測試條件？如何評估測試條件的優劣？

每次遞歸都依據屬性測試條件將記錄劃分為更小的子集。為了更好地進行記錄分割，算法必須為不一樣類型的屬性指定不同的測試條件的方法，而且提供評估每一個測試條件優劣的客觀標準。

目前屬性的數據類型主要有以下幾種。

圖1.25　二值類型屬性的劃分示意圖

●二值類型。該類型的可取值只有兩個，因此，其測試條件可以直接采用二分測試方法。例如，如圖1.25所示，將動物根據體溫是否恒定分為冷血和溫血動物。

●標稱值類型（枚舉類型）。標稱值類型也稱為枚舉類型，可取值數目是有限的。因此，可以采用每個取值對應一個測試條件的多路測試方法，或者任意分成兩組，然后利用二分測試方法。例如，如圖1.26所示，可以將婚姻的三種狀態（圖1.26a）中的任意兩個狀態分為一組，從而轉為兩種狀態（圖1.26b）。

●連續值類型。連續屬性的可取值的數目不再有限，因此不能像前面的那些類型一樣對節點進行劃分。因此需要對連續屬性進行離散化處理，常用的離散化方法是二分法或多路劃分方法。例如，如圖1.27所示，年收入為連續值屬性，可以通過單個范圍值離散化（圖1.27a），也可以使用多個范圍值進行離散化（圖1.27b）。

圖1.26　標稱值類型屬性的劃分示意圖

圖1.27　連續值類型屬性的劃分示意圖

●有序值類型。有序值類型的可取值的數目有可能是有限的，也可能是無限的。如果是有限數目，則可以類似于標稱值類型進行處理；如果是無限數目，則可以類似于連續值類型進行處理。例如，如圖1.28所示，衣服的尺碼具有有序的特點，可以將多個相鄰的尺碼進行分組。

圖1.28　有序值類型屬性的劃分示意圖

3. 如何中止分裂？如何避免過擬合？

為了終止決策樹的成長過程，一個可能的策略是分裂節點直到全部的記錄都屬于同一類，或者全部的記錄都具備相同的屬性值。但是這種情況有可能導致過擬合，從而導致決策樹模型的泛化能力不足。盡管這兩個約束條件對于結束決策樹成長是充分的，可是還需要其余的標準來提早中止樹的生長過程。

4. 如何提升決策樹的預測精度？

決策樹基于現有屬性特征進行學習和推理，具有很好的可解釋性。但隨著樣本數量的增加，決策樹的預測精度問題變得比較突出，特別是與其他機器學習方法比較而言沒有明顯優勢。因此，如何提升決策樹的預測精度成為一個重要的研究焦點。