從零開始構(gòu)造決策樹(python)

zhoutao 發(fā)布于2019-07-30 15:05 / 707人閱讀

摘要：起步本章介紹如何不利用第三方庫(kù)，僅用自帶的標(biāo)準(zhǔn)庫(kù)來構(gòu)造一個(gè)決策樹。構(gòu)造決策樹決策樹中需要一個(gè)屬性來指向樹的根節(jié)點(diǎn)，以及特征數(shù)量。

起步

本章介紹如何不利用第三方庫(kù)，僅用python自帶的標(biāo)準(zhǔn)庫(kù)來構(gòu)造一個(gè)決策樹。不過這可能需要你之前閱讀過這方面的知識(shí)。

前置閱讀

分類算法之決策樹（理論篇）

分類算法之決策樹（應(yīng)用篇）

本文使用將使用《應(yīng)用篇》中的訓(xùn)練集，向量特征僅有 0 和 1 兩種情況。

關(guān)于熵(entropy)的一些計(jì)算

對(duì)于熵，根據(jù)前面提到的計(jì)算公式:

$$ H(X) = -sum_{i=1}^np_ilog_2{(p_i)} $$

對(duì)應(yīng)的 python 代碼:

import math
import collections

def entropy(rows: list) -> float:
    """
    計(jì)算數(shù)組的熵
    """
    result = collections.Counter()
    result.update(rows)
    rows_len = len(rows)
    assert rows_len   # 數(shù)組長(zhǎng)度不能為0
    # 開始計(jì)算熵值
    ent = 0.0
    for r in result.values():
        p = float(r) / rows_len
        ent -= p * math.log2(p)
    return ent

條件熵的計(jì)算

根據(jù)計(jì)算方法：

$$ H(Y|X) = sum_{i=1}^np_iH(Y|X=x_i) $$

對(duì)應(yīng)的 python 代碼:

def condition_entropy(future_list: list, result_list: list) -> float:
    """
    計(jì)算條件熵
    """
    entropy_dict = collections.defaultdict(list)  # {0:[], 1:[]}
    for future, value in zip(future_list, result_list):
        entropy_dict[future].append(value)
    # 計(jì)算條件熵
    ent = 0.0
    future_len = len(future_list)  # 數(shù)據(jù)個(gè)數(shù)
    for value in entropy_dict.values():
        p = len(value) / future_len * entropy(value)
        ent += p

    return ent

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

信息增益

根據(jù)信息增益的計(jì)算方法：

$$ gain(A) = H(D) - H(D|A) $$

對(duì)應(yīng)的python代碼:

def gain(future_list: list, result_list: list) -> float:
    """
    獲取某特征的信息增益
    """
    info = entropy(result_list)
    info_condition = condition_entropy(future_list, result_list)
    return info - info_condition

定義決策樹的節(jié)點(diǎn)

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

class DecisionNode(object):
    """
    決策樹的節(jié)點(diǎn)
    """
    def __init__(self, col=-1, data_set=None, labels=None, results=None, tb=None, fb=None):
        self.has_calc_index = []    # 已經(jīng)計(jì)算過的特征索引
        self.col = col              # col 是待檢驗(yàn)的判斷條件，對(duì)應(yīng)列索引值
        self.data_set = data_set    # 節(jié)點(diǎn)的 待檢測(cè)數(shù)據(jù)
        self.labels = labels        # 對(duì)應(yīng)當(dāng)前列必須匹配的值
        self.results = results      # 保存的是針對(duì)當(dāng)前分支的結(jié)果，有值則表示該點(diǎn)是葉子節(jié)點(diǎn)
        self.tb = tb                # 當(dāng)信息增益最高的特征為True時(shí)的子樹
        self.fb = fb                # 當(dāng)信息增益最高的特征為False時(shí)的子樹

樹的節(jié)點(diǎn)會(huì)有兩種狀態(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é)果集）:

[
    [1, 0, 1],
    [0, 1, 1],
    [0, 0, 1],
]

有三條數(shù)據(jù)，三個(gè)特征，那么第一個(gè)特征對(duì)應(yīng)了第一列 [1, 0, 0] ，它的索引是 0 。

遞歸的停止條件

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

def if_split_end(result_list: list) -> bool:
    """
    遞歸的結(jié)束條件，每個(gè)分支的結(jié)果集都是相同的分類
    """
    result = collections.Counter(result_list)
    return len(result) == 1

從訓(xùn)練集中篩選最佳的特征

def choose_best_future(data_set: list, labels: list, ignore_index: list) -> int:
    """
    從特征向量中篩選出最好的特征，返回它的特征索引
    """
    result_dict = {}  # { 索引: 信息增益值 }
    future_num = len(data_set[0])
    for i in range(future_num):
        if i in ignore_index: # 如果已經(jīng)計(jì)算過了
            continue
        future_list = [x[i] for x in data_set]
        result_dict[i] = gain(future_list, labels) # 獲取信息增益
    # 排序后選擇第一個(gè)
    ret = sorted(result_dict.items(), key=lambda x: x[1], reverse=True)
    return ret[0][0]

因此計(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)中的。

class DecisionTreeClass():
    def __init__(self):
        self.future_num = 0      # 特征
        self.tree_root = None    # 決策樹根節(jié)點(diǎn)

創(chuàng)建決策樹

這里需要遞歸來創(chuàng)建決策樹：

def build_tree(self, node: DecisionNode):
    # 遞歸條件結(jié)束
    if if_split_end(node.labels):
        node.results = node.labels[0] # 表明是葉子節(jié)點(diǎn)
        return
    #print(node.data_set)
    # 不是葉子節(jié)點(diǎn)，開始創(chuàng)建分支
    best_index = choose_best_future(node.data_set, node.labels, node.has_calc_index)
    node.col = best_index

    # 根據(jù)信息增益最大進(jìn)行劃分
    # 左子樹
    tb_index = [i for i, value in enumerate(node.data_set) if value[best_index]]
    tb_data_set     = [node.data_set[x] for x in tb_index]
    tb_data_labels  = [node.labels[x] for x in tb_index]
    tb_node = DecisionNode(data_set=tb_data_set, labels=tb_data_labels)
    tb_node.has_calc_index = list(node.has_calc_index)
    tb_node.has_calc_index.append(best_index)
    node.tb = tb_node

    # 右子樹
    fb_index = [i for i, value in enumerate(node.data_set) if not value[best_index]]
    fb_data_set = [node.data_set[x] for x in fb_index]
    fb_data_labels = [node.labels[x] for x in fb_index]
    fb_node = DecisionNode(data_set=fb_data_set, labels=fb_data_labels)
    fb_node.has_calc_index = list(node.has_calc_index)
    fb_node.has_calc_index.append(best_index)
    node.fb = fb_node

    # 遞歸創(chuàng)建子樹
    if tb_index:
        self.build_tree(node.tb)
    if fb_index:
        self.build_tree(node.fb)

根據(jù)信息增益的特征索引將訓(xùn)練集再劃分為左右兩個(gè)子樹。

訓(xùn)練函數(shù)

也就是要有一個(gè) fit 函數(shù):

def fit(self, x: list, y: list):
    """
    x是訓(xùn)練集，二維數(shù)組。y是結(jié)果集，一維數(shù)組
    """
    self.future_num = len(x[0])
    self.tree_root = DecisionNode(data_set=x, labels=y)
    self.build_tree(self.tree_root)
    self.clear_tree_example_data(self.tree_root)

清理訓(xùn)練集

訓(xùn)練后，樹節(jié)點(diǎn)中數(shù)據(jù)集和結(jié)果集等就沒必要的，該模型只要 col 和 result 就可以了：

def clear_tree_example_data(self, node: DecisionNode):
    """
    清理tree的訓(xùn)練數(shù)據(jù)
    """
    del node.has_calc_index
    del node.labels
    del node.data_set
    if node.tb:
        self.clear_tree_example_data(node.tb)
    if node.fb:
        self.clear_tree_example_data(node.fb)

預(yù)測(cè)函數(shù)

提供一個(gè)預(yù)測(cè)函數(shù):

def _predict(self, data_test: list, node: DecisionNode):
    if node.results:
        return node.results
    col = node.col
    if data_test[col]:
        return self._predict(data_test, node.tb)
    else:
        return self._predict(data_test, node.fb)

def predict(self, data_test):
    """
    預(yù)測(cè)
    """
    return self._predict(data_test, self.tree_root)

測(cè)試

數(shù)據(jù)集使用前面《應(yīng)用篇》中的向量化的訓(xùn)練集：

if __name__ == "__main__":
    dummy_x = [
        [0, 0, 1, 0, 1, 1, 0, 0, 1, 0, ],
        [0, 0, 1, 1, 0, 1, 0, 0, 1, 0, ],
        [1, 0, 0, 0, 1, 1, 0, 0, 1, 0, ],
        [0, 1, 0, 0, 1, 0, 0, 1, 1, 0, ],
        [0, 1, 0, 0, 1, 0, 1, 0, 0, 1, ],
        [0, 1, 0, 1, 0, 0, 1, 0, 0, 1, ],
        [1, 0, 0, 1, 0, 0, 1, 0, 0, 1, ],
        [0, 0, 1, 0, 1, 0, 0, 1, 1, 0, ],
        [0, 0, 1, 0, 1, 0, 1, 0, 0, 1, ],
        [0, 1, 0, 0, 1, 0, 0, 1, 0, 1, ],
        [0, 0, 1, 1, 0, 0, 0, 1, 0, 1, ],
        [1, 0, 0, 1, 0, 0, 0, 1, 1, 0, ],
        [1, 0, 0, 0, 1, 1, 0, 0, 0, 1, ],
        [0, 1, 0, 1, 0, 0, 0, 1, 1, 0, ],
    ]
    dummy_y = [0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0]

    tree = DecisionTreeClass()
    tree.fit(dummy_x, dummy_y)

    test_row = [1, 0, 0, 0, 1, 1, 0, 0, 1, 0, ]
    print(tree.predict(test_row))  # output: 1

附錄

本次使用的完整代碼:

# coding: utf-8
import math
import collections

def entropy(rows: list) -> float:
    """
    計(jì)算數(shù)組的熵
    :param rows:
    :return:
    """
    result = collections.Counter()
    result.update(rows)
    rows_len = len(rows)
    assert rows_len   # 數(shù)組長(zhǎng)度不能為0
    # 開始計(jì)算熵值
    ent = 0.0
    for r in result.values():
        p = float(r) / rows_len
        ent -= p * math.log2(p)
    return ent

def condition_entropy(future_list: list, result_list: list) -> float:
    """
    計(jì)算條件熵
    """
    entropy_dict = collections.defaultdict(list)  # {0:[], 1:[]}
    for future, value in zip(future_list, result_list):
        entropy_dict[future].append(value)
    # 計(jì)算條件熵
    ent = 0.0
    future_len = len(future_list)
    for value in entropy_dict.values():
        p = len(value) / future_len * entropy(value)
        ent += p

    return ent

def gain(future_list: list, result_list: list) -> float:
    """
    獲取某特征的信息增益
    """
    info = entropy(result_list)
    info_condition = condition_entropy(future_list, result_list)
    return info - info_condition


class DecisionNode(object):
    """
    決策樹的節(jié)點(diǎn)
    """
    def __init__(self, col=-1, data_set=None, labels=None, results=None, tb=None, fb=None):
        self.has_calc_index = []    # 已經(jīng)計(jì)算過的特征索引
        self.col = col              # col 是待檢驗(yàn)的判斷條件，對(duì)應(yīng)列索引值
        self.data_set = data_set    # 節(jié)點(diǎn)的 待檢測(cè)數(shù)據(jù)
        self.labels = labels        # 對(duì)應(yīng)當(dāng)前列必須匹配的值
        self.results = results      # 保存的是針對(duì)當(dāng)前分支的結(jié)果，有值則表示該點(diǎn)是葉子節(jié)點(diǎn)
        self.tb = tb                # 當(dāng)信息增益最高的特征為True時(shí)的子樹
        self.fb = fb                # 當(dāng)信息增益最高的特征為False時(shí)的子樹

def if_split_end(result_list: list) -> bool:
    """
    遞歸的結(jié)束條件，每個(gè)分支的結(jié)果集都是相同的分類
    :param result_list:
    :return:
    """
    result = collections.Counter()
    result.update(result_list)
    return len(result) == 1

def choose_best_future(data_set: list, labels: list, ignore_index: list) -> int:
    """
    從特征向量中篩選出最好的特征，返回它的特征索引
    """
    result_dict = {}  # { 索引: 信息增益值 }
    future_num = len(data_set[0])
    for i in range(future_num):
        if i in ignore_index: # 如果已經(jīng)計(jì)算過了
            continue
        future_list = [x[i] for x in data_set]
        result_dict[i] = gain(future_list, labels) # 獲取信息增益
    # 排序后選擇第一個(gè)
    ret = sorted(result_dict.items(), key=lambda x: x[1], reverse=True)
    return ret[0][0]


class DecisionTreeClass():
    def __init__(self):
        self.future_num = 0      # 特征
        self.tree_root = None    # 決策樹根節(jié)點(diǎn)

    def build_tree(self, node: DecisionNode):
        # 遞歸條件結(jié)束
        if if_split_end(node.labels):
            node.results = node.labels[0] # 表明是葉子節(jié)點(diǎn)
            return
        #print(node.data_set)
        # 不是葉子節(jié)點(diǎn)，開始創(chuàng)建分支
        best_index = choose_best_future(node.data_set, node.labels, node.has_calc_index)
        node.col = best_index

        # 根據(jù)信息增益最大進(jìn)行劃分
        # 左子樹
        tb_index = [i for i, value in enumerate(node.data_set) if value[best_index]]
        tb_data_set     = [node.data_set[x] for x in tb_index]
        tb_data_labels  = [node.labels[x] for x in tb_index]
        tb_node = DecisionNode(data_set=tb_data_set, labels=tb_data_labels)
        tb_node.has_calc_index = list(node.has_calc_index)
        tb_node.has_calc_index.append(best_index)
        node.tb = tb_node

        # 右子樹
        fb_index = [i for i, value in enumerate(node.data_set) if not value[best_index]]
        fb_data_set = [node.data_set[x] for x in fb_index]
        fb_data_labels = [node.labels[x] for x in fb_index]
        fb_node = DecisionNode(data_set=fb_data_set, labels=fb_data_labels)
        fb_node.has_calc_index = list(node.has_calc_index)
        fb_node.has_calc_index.append(best_index)
        node.fb = fb_node

        # 遞歸創(chuàng)建子樹
        if tb_index:
            self.build_tree(node.tb)
        if fb_index:
            self.build_tree(node.fb)

    def clear_tree_example_data(self, node: DecisionNode):
        """
        清理tree的訓(xùn)練數(shù)據(jù)
        :return:
        """
        del node.has_calc_index
        del node.labels
        del node.data_set
        if node.tb:
            self.clear_tree_example_data(node.tb)
        if node.fb:
            self.clear_tree_example_data(node.fb)

    def fit(self, x: list, y: list):
        """
        x是訓(xùn)練集，二維數(shù)組。y是結(jié)果集，一維數(shù)組
        """
        self.future_num = len(x[0])
        self.tree_root = DecisionNode(data_set=x, labels=y)
        self.build_tree(self.tree_root)
        self.clear_tree_example_data(self.tree_root)

    def _predict(self, data_test: list, node: DecisionNode):
        if node.results:
            return node.results
        col = node.col
        if data_test[col]:
            return self._predict(data_test, node.tb)
        else:
            return self._predict(data_test, node.fb)

    def predict(self, data_test):
        """
        預(yù)測(cè)
        """
        return self._predict(data_test, self.tree_root)


if __name__ == "__main__":
    dummy_x = [
        [0, 0, 1, 0, 1, 1, 0, 0, 1, 0, ],
        [0, 0, 1, 1, 0, 1, 0, 0, 1, 0, ],
        [1, 0, 0, 0, 1, 1, 0, 0, 1, 0, ],
        [0, 1, 0, 0, 1, 0, 0, 1, 1, 0, ],
        [0, 1, 0, 0, 1, 0, 1, 0, 0, 1, ],
        [0, 1, 0, 1, 0, 0, 1, 0, 0, 1, ],
        [1, 0, 0, 1, 0, 0, 1, 0, 0, 1, ],
        [0, 0, 1, 0, 1, 0, 0, 1, 1, 0, ],
        [0, 0, 1, 0, 1, 0, 1, 0, 0, 1, ],
        [0, 1, 0, 0, 1, 0, 0, 1, 0, 1, ],
        [0, 0, 1, 1, 0, 0, 0, 1, 0, 1, ],
        [1, 0, 0, 1, 0, 0, 0, 1, 1, 0, ],
        [1, 0, 0, 0, 1, 1, 0, 0, 0, 1, ],
        [0, 1, 0, 1, 0, 0, 0, 1, 1, 0, ],
    ]
    dummy_y = [0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0]

    tree = DecisionTreeClass()
    tree.fit(dummy_x, dummy_y)

    test_row = [1, 0, 0, 0, 1, 1, 0, 0, 1, 0, ]
    print(tree.predict(test_row))

云服務(wù)器 GPU云服務(wù)器決策樹python 決策樹 python python從零開始 python畫決策樹

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/41031.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

zhoutao

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

2021世界智能網(wǎng)聯(lián)汽車大會(huì)觀感

閱讀 1674·2021-09-28 09:35
前端技術(shù)演進(jìn)（三）：前端安全

閱讀 1141·2019-08-30 15:54
New CSS Logical Properties! - The Next Step of CSS

閱讀 1669·2019-08-30 15:44
面試刷題總結(jié)

閱讀 3373·2019-08-30 14:09
BFC！Repaint！Reflow

閱讀 504·2019-08-29 14:05
d3js中級(jí)教程之漂浮的卡牌效果(data的key函數(shù)進(jìn)階)

閱讀 2670·2019-08-28 17:53
前端小報(bào) - 201903月刊

閱讀 1996·2019-08-26 13:41
angular源碼分析之platformBrowserDynamic

閱讀 1726·2019-08-26 13:26

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

從零開始構(gòu)造決策樹(python)

相關(guān)文章

**如何在Python中從零開始實(shí)現(xiàn)隨機(jī)森林**

**決策樹的Python實(shí)現(xiàn)（含代碼）**

第7期 Datawhale 組隊(duì)學(xué)習(xí)計(jì)劃

發(fā)表評(píng)論

0條評(píng)論

zhoutao

男|高級(jí)講師

TA的文章

2021世界智能網(wǎng)聯(lián)汽車大會(huì)觀感

前端技術(shù)演進(jìn)（三）：前端安全

New CSS Logical Properties! - The Next Step of CSS

面試刷題總結(jié)

BFC！Repaint！Reflow

d3js中級(jí)教程之漂浮的卡牌效果(data的key函數(shù)進(jìn)階)

前端小報(bào) - 201903月刊

angular源碼分析之platformBrowserDynamic

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

從零開始構(gòu)造決策樹(python)

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！