決策樹算法簡介
決策樹算法特點及應用
資訊概念介紹
生成決策樹
總結
參考

1.決策樹算法簡介

決策樹概念介紹

決策樹算法是監督學習算法的其中一種，用于根據已有資料訓練資料針對未知資料進行分類的一種算法，該算法的核心理念是通過不斷的判斷，遞歸，判斷，來計算資料的分類。

舉例說明

概念可能不大好了解，舉例就會清楚直覺了，相信大多數人都有過生病的體驗，找醫生看病的時候，醫生就會讓你伸出舌頭看看，摸摸你的額頭等，這就是根據症狀來判斷是什麼病，如果你患了感冒，醫生會首先問你是否有腹瀉，然後讓你伸出舌頭，看看你的舌苔，之後會問你是否頭痛，發冷，根據這一系列的資料，醫生便可以推斷你的感冒類型，對症下藥。

發熱	腹瀉	舌苔黃	頭痛	畏寒	感冒類型
是	否	輕微	是	輕微	風熱型感冒
是	否	否	是	是	風寒型感冒
是	是	輕微	是	是	暑濕型感冒
是	否	是	是	是	時行感冒

2.決策樹算法特點及應用

特點：

計算複雜度不高
輸出結果便于了解
适用于分類，适合标稱數值

應用：

之前在微信裡，朋友發給我一個連結，點進去是一個機器人來根據你的問題答案猜測是哪位明星的問題，當時覺得非常的神奇，在學習了決策樹之後，才明白了其中的道理，當然這也是我猜測，首先，這個網站會收藏很多的問題作為特征值，并收集很多明星的資訊，把該資訊錄入本地資料集，例如上面的發熱，腹瀉等特征，然後抽取問題1，根據答案來選擇下一個提出的問題(如果選擇不知道則忽略該特征)，直到指定特征被用完(答完10個問題)，根據最後結果集中出現次數最多作為答案。

3.資訊概念介紹

資訊概念：

資訊是反映一個事件出現機率的機關(曾經在大學學的通信原理已經忘得一幹二淨)，首先列出公式，下面再分析。

- 資訊 = log2(機率)

上述的發熱症狀，無論哪種感冒都存在發熱現象，那麼這個資訊其實對我們分析病情是無關緊要，是以他的資訊是0，也許大家不能了解這個公式的計算方式，但我們并不準确需要這個值，我們隻需要資訊與機率的對應關系，無論是log3或者log4，對資料分類不造成影響，如果出現機率不為1的話，機率越大，資訊量也就越小。

資訊熵概念：

資訊熵是反映一組資料的不确定性，就好比擲骰子，扔12面的骰子比6面的骰子結果不确定性就會高很多，資訊熵就是用來反映這個不确定性的機關，計算公式如下：

- 資訊熵 = sum(-機率1*log2(機率1), -機率2*log2(機率2)，……)

從公式可能不太容易看出什麼，不如我們用數值代入，6面骰子，有6種情況，每一種都是1/6，那麼結果就是log2(6)=0.778，12面骰子就是log2(12)=1.079，不确定性高了之後，資訊熵也得到了上漲，下面列出計算資訊熵的python代碼。

from math import log
from collections import Counter

def calc_shannon_ent(data_set):
    last_item_set = [item[-] for item in data_set] # 抽取需要計算資訊熵的列，這裡直接取最後一列來計算
    data_length = len(last_item_set) # 計算資料集的長度
    counter_data = Counter(last_item_set) # 使用Counter來計算出現機率，counter_data的值是字典，例如{'a': 5, 'b': 2}

    shannon_ent = 
    for item_s in counter_data.iteritems():
        probability = item_s[] / float(data_length)
        info = log(probability, )
        shannon_ent -= info * probability
    return shannon_ent
>>> data = [[, , 'yes'], [, , 'unknown'], [, , 'no'], [, , 'no'], [, , 'yes'], [, , 'unknown']]
>>> calc_shannon_ent(data)

資訊增益：

資訊增益是通過其他條件來降低這一組資料的不确定性，就好比朋友養了一條小狗，朋友告訴你這條狗是薩摩耶，吉娃娃，京巴，二哈，阿拉斯加和中華田園犬中的一種，讓你去猜，如果直接猜，猜中的幾率是1/6，但是如果知道這條狗的毛發顔色，那麼猜中的幾率就會提高，白色是薩摩耶，黃色是京巴，吉娃娃和中華田園犬，黑白配是二哈和阿拉斯加，這個條件所降低的不确定性則是資訊增益，計算公式如下。

定義:

資訊增益 = B - sum(P1*S1, P2*S2，……)

Px指類型x在該組資料中占到的比例(例如黑白配有2種(二哈和阿拉斯加)，一共有6種犬類，比例就是1/3)。

Sx當類型為x，得到的資訊熵。

B無任何分類時的資訊熵(6種犬類，和上面6面骰子的資訊熵一樣)。

最優分類(最大資訊增益)：

接着上面的例子，小狗我們可以根據毛發顔色，體型，甚至眉心是否有火字印記(這是區分二哈和阿拉斯加的條件)等條件來對這幾種犬分類，如果朋友隻能回答你一個問題，讓你猜測犬類，那麼你就需要一個最優分類，通過計算這幾種分類方式帶來的資訊增益，選擇最大者則是最大資訊增益，該分類方式則是最優分類。

以下是python計算最佳分類的方法：

from calc_shannon_ent import calc_shannon_ent


"""該方法是根據選中某一列的值來劃分資料集，例如資料為[[1, 1, 'yes'], [2, 2, 'yes'], [3, 3, 'no'], [4, 4, 'unknown']]，那麼根據第2列，值為yes來劃分得到的資料為[[1, 1], [2, 2]]"""
def split_data_by_value(data_set, axis, value):
    sub_data_set = []

    for item in data_set:
        if item[axis] == value:
            sub_item = item[:axis] + item[axis + :] # 拆分再組合 把[1, 2, 3]組合成[1, 3]
            sub_data_set.append(sub_item)
    return sub_data_set


def choose_best_feature(data_set):
    feature_nums = len(data_set[]) # 擷取特征數(就是資料集的列數)

    base_ent = calc_shannon_ent(data_set) # 計算基礎資訊熵
    base_gain = 
    base_choose = -

    for i in range(feature_nums): # 對所有特征進行周遊
        feature_values = [item[i] for item in data_set] # 取出特征列所有值
        unique_values = set(feature_values) # 去除重複值
        sub_ent = 
        for item_unq in unique_values: # 對唯一特征值進行周遊
            sub_data_set = split_data_by_value(data_set, i, item_unq) #根據該特征值劃分資料集
            sub_data_ent = calc_shannon_ent(sub_data_set) # 對子資料集計算資訊熵
            probability = len(sub_data_set) / float(len(data_set)) # 計算該特征值在所有特征值中的比例
            sub_ent += sub_data_ent * probability # 累加計算總資訊熵
        data_gain = base_ent - sub_ent # 計算資訊增益
        if data_gain > base_gain: # 計算最大資訊增益
            base_gain = data_gain
            base_choose = i
    return base_choose # 傳回最大資訊增益的特征列
>>> data = [[, , 'yes'], [, , 'unknown'], [, , 'no'], [, , 'no'], [, , 'yes'], [, , 'unknown']]
>>> choose_best_feature(data)
 # 第一列是最佳列，因為該列為2時，最後一列2個都為unknown
>>> data = [[, , 'yes'], [, , 'unknown'], [, , 'no'], [, , 'no'], [, , 'yes'], [, , 'unknown']]
>>> choose_best_feature(data)
 # 修改了一下data，讓最後一列與倒數第二列建立對應關系，最後一列成為最佳分類

4.生成決策樹

生成方法：

本文中選用ID3方法生成決策樹，生成方法大緻為：根據資料集計算最優分類列，根據該類的每一個值作為key，對應的value通過該方法遞歸生成。

當根據某一個特征值劃分出來的資料是全部重複的資料，程式不存在繼續劃分的意義，遞歸停止，當所有特征值已經使用完，仍有多樣資料時，取資料集中出現頻率最高值作為分類結果。

直接上代碼：

import json

from collections import Counter

from split_best_feat import choose_best_feature, split_data_by_value


def create_tree_data(): # 這是我在網上找到的關于犬類 體型 食量 壽命的對應關系
    data = [
        ['small', 'large', ],
        ['big', 'big', ],
        ['big', 'big', ],
        ['small', 'small', ],
        ['small', 'small', ],
        ['medium', 'small', ],
        ['big', 'medium', ],
        ['medium', 'medium', ],
        ['medium', 'big', ],
        ['medium', 'small', ],
    ]
    labels = ['體型', '食量', '壽命']

    return data, labels

def count_most_data(data_set): # 計算一個資料集中，出現頻率最高的值
    class_count = {}
    for item in data_set:
        class_count[item[]] = class_count.get(item[], ) + 
    sort_count = sorted(class_count.iteritems(), key=lambda x: x[], reverse=True)
    return sort_count[][]


def strategy_tree(data, labels):
    temp_data_list = [item[-] for item in data]
    if len(Counter(temp_data_list)) == :
        return temp_data_list[] # 如果數值全部統一，則停止遞歸
    if len(data[]) == : 
        return count_most_data(data) # 如果特征已經用完，則停止遞歸
    best_feature = choose_best_feature(data) # 選擇最優分類列
    data_list = [item[best_feature] for item in data] # 取最優分類列的各個數值
    label = labels[best_feature] # 取最優分類列的标簽
    labels.remove(label) # 移除該标簽，用于下次遞歸
    sub_labels = labels[:]
    unique_values = set(data_list) # 取最優分類列的唯一值

    ret_data = {}
    ret_data[label] = {}

    for unq_item in unique_values:
        sub_data_set = split_data_by_value(data, best_feature, unq_item) # 根據最優分類列的值切分子資料集
        ret_data[label][unq_item] = strategy_tree(sub_data_set, sub_labels[:]) # 對子資料集遞歸處理
    return ret_data
>>> data, label = create_tree_data()
>>> tree = strategy_tree(data, label)
 # 第一列是最佳列，因為該列為2時，最後一列2個都為unknown
>>> json.dumps(tree, ensure_ascii=False)
{
    "壽命": {
        "10": "big",
        "11": {
            "食量": {
                "big": "medium",
                "medium": "medium"
            }
        },
        "12": {
            "體型": {
                "small": "large",
                "medium": "small"
            }
        },
        "13": "small",
        "15": {
            "體型": {
                "small": "small",
                "big": "medium"
            }
        }
    }
}

5.總結

本文介紹了決策樹的相關概念，并介紹了有關資訊等概念，以及如何建立決策樹。
下一篇文章會介紹如何使用matplotlib根據決策圖繪制圖形，以及如何使用決策樹進行分類。
本文中，沒有強制要求結果為哪一列，是以資料都是以最後一列來劃分，如果有指定列，計算最優分類時，指定該列即可。
當分類資料過多且不确定性較高時，決策樹比對消耗的時間較多，當資料變動性不大時，可以将決策樹進行存儲，在需要時取出樹進行分析，下一篇文章會介紹如何使用pickle存儲決策樹。

6.參考

[機器學習實戰]

機器學習值決策樹算法(上)-ID3實作1.決策樹算法簡介2.決策樹算法特點及應用3.資訊概念介紹4.生成決策樹5.總結6.參考

1.決策樹算法簡介

2.決策樹算法特點及應用

3.資訊概念介紹

4.生成決策樹

5.總結

6.參考

繼續閱讀

libsvm for python 安裝

學習軟體測試基礎測試第七天

Zeppelin 配置通路 REST APIApache Zeppelin Configuration REST API

【Torch】最簡潔logging使用指南

筆試面試題目：滑動視窗(二)

27. Remove Element(清單)題目代碼

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Cloud Studio初體驗

使用 ctypes 進行 Python 和 C 的混合程式設計

【python】【資料處理】畫多元資料分布圖

【python】netconf協定對接管理裝置

「Python 網絡自動化」NETCONF —— Python 使用 NETCONF 管理配置 H3C 網絡裝置

在python中建立excel并寫入

hdu7108哈希