起步

本章介紹如何不利用第三方庫，僅用python自帶的標準庫來構造一個決策樹。

熵的計算公式:

對應的 python 代碼:

條件熵的計算

根據計算方法：

對應的 python 代碼:

其中參數 future_list 是某一特征向量組成的列表，result_list 是 label 列表。

信息增益

根據信息增益的計算方法：

對應的python代碼:

..

定義決策樹的節點

作為樹的節點，要有左子樹和右子樹是必不可少的，除此之外還需要其他信息:

樹的節點會有兩種狀態，葉子節點中 results 屬性將保持當前的分類結果。非葉子節點中， col 保存著該節點計算的特征索引，根據這個索引來創建左右子樹。

has_calc_index 屬性表示在到達此節點時，已經計算過的特征索引。特征索引的數據集上表現是列的形式，如數據集（不包含結果集）:

有三條數據，三個特征，那么***個特征對應了***列 [1, 0, 0] ，它的索引是 0 。

遞歸的停止條件

本章將構造出完整的決策樹，所以遞歸的停止條件是所有待分析的訓練集都屬于同一類:

從訓練集中篩選***的特征

因此計算節點就是調用 best_index = choose_best_future(node.data_set, node.labels, node.has_calc_index) 來獲取***的信息增益的特征索引。

構造決策樹

決策樹中需要一個屬性來指向樹的根節點，以及特征數量。不需要保存訓練集和結果集，因為這部分信息是保存在樹的節點中的。

創建決策樹

這里需要遞歸來創建決策樹：

根據信息增益的特征索引將訓練集再劃分為左右兩個子樹。

訓練函數

也就是要有一個 fit 函數:

清理訓練集

訓練后，樹節點中數據集和結果集等就沒必要的，該模型只要 col 和 result 就可以了：

預測函數

提供一個預測函數:

測試

數據集使用前面《應用篇》中的向量化的訓練集：