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