用Python從零開始構(gòu)造決策樹
起步
本章介紹如何不利用第三方庫，僅用python自帶的標(biāo)準(zhǔn)庫來構(gòu)造一個決策樹。
熵的計算公式:
對應(yīng)的 python 代碼:
條件熵的計算
根據(jù)計算方法：
對應(yīng)的 python 代碼:
其中參數(shù) future_list 是某一特征向量組成的列表，result_list 是 label 列表。
信息增益
根據(jù)信息增益的計算方法：
對應(yīng)的python代碼:
..
定義決策樹的節(jié)點
作為樹的節(jié)點，要有左子樹和右子樹是必不可少的，除此之外還需要其他信息:
樹的節(jié)點會有兩種狀態(tài)，葉子節(jié)點中 results 屬性將保持當(dāng)前的分類結(jié)果。非葉子節(jié)點中， col 保存著該節(jié)點計算的特征索引，根據(jù)這個索引來創(chuàng)建左右子樹。
has_calc_index 屬性表示在到達此節(jié)點時，已經(jīng)計算過的特征索引。特征索引的數(shù)據(jù)集上表現(xiàn)是列的形式，如數(shù)據(jù)集（不包含結(jié)果集）:
有三條數(shù)據(jù)，三個特征，那么第一個特征對應(yīng)了第一列 [1, 0, 0] ，它的索引是 0 。
遞歸的停止條件
本章將構(gòu)造出完整的決策樹，所以遞歸的停止條件是所有待分析的訓(xùn)練集都屬于同一類:
從訓(xùn)練集中篩選最佳的特征
因此計算節(jié)點就是調(diào)用 best_index = choose_best_future(node.data_set, node.labels, node.has_calc_index) 來獲取最佳的信息增益的特征索引。
構(gòu)造決策樹
決策樹中需要一個屬性來指向樹的根節(jié)點，以及特征數(shù)量。不需要保存訓(xùn)練集和結(jié)果集，因為這部分信息是保存在樹的節(jié)點中的。
創(chuàng)建決策樹
這里需要遞歸來創(chuàng)建決策樹：
根據(jù)信息增益的特征索引將訓(xùn)練集再劃分為左右兩個子樹。
訓(xùn)練函數(shù)
也就是要有一個 fit 函數(shù):
清理訓(xùn)練集
訓(xùn)練后，樹節(jié)點中數(shù)據(jù)集和結(jié)果集等就沒必要的，該模型只要 col 和 result 就可以了：
預(yù)測函數(shù)
提供一個預(yù)測函數(shù):
測試
數(shù)據(jù)集使用前面《應(yīng)用篇》中的向量化的訓(xùn)練集：
