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