国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

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

zhoutao / 696人閱讀

摘要：起步本章介紹如何不利用第三方庫，僅用自帶的標準庫來構造一個決策樹。構造決策樹決策樹中需要一個屬性來指向樹的根節點，以及特征數量。

起步

本章介紹如何不利用第三方庫，僅用python自帶的標準庫來構造一個決策樹。不過這可能需要你之前閱讀過這方面的知識。

前置閱讀

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

分類算法之決策樹（應用篇）

本文使用將使用《應用篇》中的訓練集，向量特征僅有 0 和 1 兩種情況。

關于熵(entropy)的一些計算

對于熵，根據前面提到的計算公式:

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

對應的 python 代碼:

import math
import collections

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

根據計算方法：

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

對應的 python 代碼:

def condition_entropy(future_list: list, result_list: list) -> float:
    """
    計算條件熵
    """
    entropy_dict = collections.defaultdict(list)  # {0:[], 1:[]}
    for future, value in zip(future_list, result_list):
        entropy_dict[future].append(value)
    # 計算條件熵
    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

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

信息增益

根據信息增益的計算方法：

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

對應的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
定義決策樹的節點

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

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

樹的節點會有兩種狀態，葉子節點中 results 屬性將保持當前的分類結果。非葉子節點中， col 保存著該節點計算的特征索引，根據這個索引來創建左右子樹。

has_calc_index 屬性表示在到達此節點時，已經計算過的特征索引。特征索引的數據集上表現是列的形式，如數據集（不包含結果集）:

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

有三條數據，三個特征，那么第一個特征對應了第一列 [1, 0, 0] ，它的索引是 0 。

遞歸的停止條件

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

def if_split_end(result_list: list) -> bool:
    """
    遞歸的結束條件，每個分支的結果集都是相同的分類
    """
    result = collections.Counter(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: # 如果已經計算過了
            continue
        future_list = [x[i] for x in data_set]
        result_dict[i] = gain(future_list, labels) # 獲取信息增益
    # 排序后選擇第一個
    ret = sorted(result_dict.items(), key=lambda x: x[1], reverse=True)
    return ret[0][0]

因此計算節點就是調用 best_index = choose_best_future(node.data_set, node.labels, node.has_calc_index) 來獲取最佳的信息增益的特征索引。

構造決策樹

決策樹中需要一個屬性來指向樹的根節點，以及特征數量。不需要保存訓練集和結果集，因為這部分信息是保存在樹的節點中的。

class DecisionTreeClass():
    def __init__(self):
        self.future_num = 0      # 特征
        self.tree_root = None    # 決策樹根節點
創建決策樹

這里需要遞歸來創建決策樹：

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

    # 根據信息增益最大進行劃分
    # 左子樹
    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

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

根據信息增益的特征索引將訓練集再劃分為左右兩個子樹。

訓練函數

也就是要有一個 fit 函數:

def fit(self, x: list, y: list):
    """
    x是訓練集，二維數組。y是結果集，一維數組
    """
    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)
清理訓練集

訓練后，樹節點中數據集和結果集等就沒必要的，該模型只要 col 和 result 就可以了：

def clear_tree_example_data(self, node: DecisionNode):
    """
    清理tree的訓練數據
    """
    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 _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):
    """
    預測
    """
    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))  # output: 1
附錄

本次使用的完整代碼:

# coding: utf-8
import math
import collections

def entropy(rows: list) -> float:
    """
    計算數組的熵
    :param rows:
    :return:
    """
    result = collections.Counter()
    result.update(rows)
    rows_len = len(rows)
    assert rows_len   # 數組長度不能為0
    # 開始計算熵值
    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:
    """
    計算條件熵
    """
    entropy_dict = collections.defaultdict(list)  # {0:[], 1:[]}
    for future, value in zip(future_list, result_list):
        entropy_dict[future].append(value)
    # 計算條件熵
    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):
    """
    決策樹的節點
    """
    def __init__(self, col=-1, data_set=None, labels=None, results=None, tb=None, fb=None):
        self.has_calc_index = []    # 已經計算過的特征索引
        self.col = col              # col 是待檢驗的判斷條件，對應列索引值
        self.data_set = data_set    # 節點的 待檢測數據
        self.labels = labels        # 對應當前列必須匹配的值
        self.results = results      # 保存的是針對當前分支的結果，有值則表示該點是葉子節點
        self.tb = tb                # 當信息增益最高的特征為True時的子樹
        self.fb = fb                # 當信息增益最高的特征為False時的子樹

def if_split_end(result_list: list) -> bool:
    """
    遞歸的結束條件，每個分支的結果集都是相同的分類
    :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: # 如果已經計算過了
            continue
        future_list = [x[i] for x in data_set]
        result_dict[i] = gain(future_list, labels) # 獲取信息增益
    # 排序后選擇第一個
    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    # 決策樹根節點

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

        # 根據信息增益最大進行劃分
        # 左子樹
        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

        # 遞歸創建子樹
        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的訓練數據
        :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是訓練集，二維數組。y是結果集，一維數組
        """
        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):
        """
        預測
        """
        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))

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/41031.html

相關文章

  • 如何在Python中從零開始實現隨機森林

    摘要：在本教程中，您將了解如何在中從頭開始實現隨機森林算法。如何將隨機森林算法應用于預測建模問題。如何在中從頭開始實現隨機森林圖片來自，保留部分權利。這被稱為隨機森林算法。如何更新決策樹的創建以適應隨機森林過程。 歡迎大家前往云+社區，獲取更多騰訊海量技術實踐干貨哦~ 決策樹可能會受到高度變異的影響，使得結果對所使用的特定測試數據而言變得脆弱。 根據您的測試數據樣本構建多個模型（稱為套袋）可...

    MasonEast 評論0 收藏0

  • 決策樹的Python實現（含代碼）

    摘要：也就是說，決策樹有兩種分類樹和回歸樹。我們可以把決策樹看作是一個規則的集合。這樣可以提高決策樹學習的效率。解決這個問題的辦法是考慮決策樹的復雜度，對已生成的決策樹進行簡化，也就是常說的剪枝處理。最后得到一個決策樹。 一天，小迪與小西想養一只寵物。 小西：小迪小迪，好想養一只寵物呀，但是不知道養那種寵物比較合適。 小迪：好呀，養只寵物會給我們的生活帶來很多樂趣呢。不過養什么寵物可要考慮好...

    yanest 評論0 收藏0

  • 第7期 Datawhale 組隊學習計劃

    馬上就要開始啦這次共組織15個組隊學習 涵蓋了AI領域從理論知識到動手實踐的內容 按照下面給出的最完備學習路線分類 難度系數分為低、中、高三檔 可以按照需要參加 - 學習路線 - showImg(https://segmentfault.com/img/remote/1460000019082128); showImg(https://segmentfault.com/img/remote/...

    dinfer 評論0 收藏0

發表評論

0條評論

zhoutao

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<