起步

本章介紹如何不利用第三方庫，僅用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)練集：