決策樹的構(gòu)造
我的微信公眾號： s406205391; 歡迎大家一起學習捎废，一起進步！Ｖ略铩登疗！
?????????有一個二十個問題的小游戲，游戲規(guī)則很簡單：參與游戲的一方在腦海了想某個事物嫌蚤，其他參與者向他提出問題辐益，只允許提問20個問題，問題的答案也只能用對和錯來回答脱吱。問問題的人通過推斷分解智政，逐步縮小猜測事物的范圍。決策樹的工作原理與20個問題類似急凰，用戶輸入一系列數(shù)據(jù)女仰，然后給出游戲的答案猜年。
????????我們經(jīng)常使用決策樹處理分類問題抡锈，近來的調(diào)查表明決策樹也是最經(jīng)常使用的數(shù)據(jù)挖掘算法。決策樹流行的很重要的原因就是他的工作很簡單乔外，不需要了解機器學習的知識床三。下圖所示的流程圖就是一個決策樹。圖中構(gòu)造了一個假象的郵件分類系統(tǒng)杨幼，它首先檢測發(fā)送郵件的域名地址撇簿。如果地址為：myEmployer.com，則將其放在“無聊時需要閱讀的郵件”中差购，如果郵件不是來自這個域名四瘫，則檢查郵件內(nèi)容里是否包含單詞曲棍球，如果包含則將郵件歸類到“需要及時處理的朋友郵件”欲逃，如果不包含找蜜，則將郵件歸類到“無需閱讀的垃圾郵件”。
????????決策樹的主要優(yōu)勢再與數(shù)據(jù)形式非常容易理解稳析。決策樹的一個重要任務(wù)是為了理解數(shù)據(jù)中所蘊含的知識信息洗做，因此決策樹可以使用不熟悉的數(shù)據(jù)集合弓叛，并從中提取出一系列規(guī)則，這些機器根據(jù)數(shù)據(jù)集創(chuàng)建規(guī)則的過程诚纸，就是機器學習的過程撰筷。專家系統(tǒng)中經(jīng)常使用決策樹，而且決策樹給出的結(jié)果往往可以匹敵在當前領(lǐng)域具有幾十年工作經(jīng)驗的人類專家畦徘。
決策樹的一般流程
?????????決策樹的優(yōu)點是計算復雜度不高毕籽，輸出結(jié)果易于理解，對中間值的缺失不敏感井辆，可以處理不相干特征數(shù)據(jù)影钉。缺點是可能會產(chǎn)生過度匹配問題。適用數(shù)據(jù)為數(shù)值型和標稱型掘剪。
????????在構(gòu)造決策樹時平委，首先需要解決的問題是，當前數(shù)據(jù)集上夺谁，哪個特征在劃分數(shù)據(jù)集中起決定性作用廉赔。為了找到?jīng)Q定性特征，劃分出最好的結(jié)果匾鸥，我們必須評估每個特征蜡塌。完成測試之后，原始數(shù)據(jù)集就被劃分為幾個數(shù)據(jù)子集勿负。這些數(shù)據(jù)子集會分布在第一個決策點的所有分支上馏艾。
決策樹構(gòu)建的偽代碼如下：
檢測數(shù)據(jù)集中的每個子項是否屬于同一分類：
????????if so return 類標簽
????????else
????????????????尋找劃分數(shù)據(jù)集的最好特征
????????????????劃分數(shù)據(jù)集
????????????????創(chuàng)建分支節(jié)點
????????????????for 每個劃分的子集
????????????????遞歸調(diào)用本函數(shù)，并增加返回結(jié)果到分支節(jié)點中
????????return 分支節(jié)點
為了解決尋找劃分數(shù)據(jù)集的最好特征問題奴愉，就需要引入信息增益的概念琅摩。
信息增益
????????劃分數(shù)據(jù)的最大原則是：將無序的數(shù)據(jù)變得更加有序。在劃分數(shù)據(jù)集之前之后信息發(fā)生的變化成為信息增益锭硼，知道如何計算信息增益房资，我們就可以計算每個特征值劃分數(shù)據(jù)集獲得的信息增益，獲得信息增益最高的特征就是最好的選擇檀头。這就得引入熵的概念轰异。
?????????集合信息的度量方式成為香農(nóng)熵或者簡稱為熵。熵定義為信息的期望值暑始。如果待分類的事物可能劃分在多個分類之中搭独，則符號xi的信息定義為：
其中p(xi)是選擇該分類的概率。那么其所有類別所有可能值包含的信息期望值的計算公式就為：
其中廊镜，n是分類數(shù)目牙肝。
我們首先定義一個函數(shù)，來計算數(shù)據(jù)集的香農(nóng)熵
from math import log
def calc_shannon(data_set):
"""calculation shannon entropy"""
# 默認數(shù)據(jù)集的最后一列是標簽列
feat_vec = [f[-1] for f in data_set]
label_counts = Counter(feat_vec)
# 使用信息期望值的計算公式，計算香農(nóng)熵
prob_list = [value / len(data_set) for key, value in label_counts.items()]
shannon_ent = sum([-(prob * log(prob, 2)) for prob in prob_list])
return shannon_ent
????????熵越高惊奇，則混合的數(shù)據(jù)也越多互躬。在得到熵之后，我們就可以按照獲取最大信息增益的方法劃分數(shù)據(jù)集颂郎。
????????另一個度量集合無需程度的方法是基尼不純度（Gini impurity）吼渡，簡單地說就是沖一個數(shù)據(jù)集中隨機選取子項，度量其被錯誤風雷刀其他分組的概率乓序。
劃分數(shù)據(jù)集
????????分類算法除了需要測量信息熵寺酪，還需要劃分數(shù)據(jù)集，度量劃分數(shù)據(jù)集的熵替劈，以便判斷當前是否正確地劃分了數(shù)據(jù)集寄雀。下面的函數(shù)將對每個特征劃分數(shù)據(jù)集的結(jié)果計算一次信息熵， 然后判斷按照那個特征劃分數(shù)據(jù)集是最好的方式陨献。
def split_data_set(data_set, axis, value):
"""按照給定特征劃分數(shù)據(jù)集
從待劃分的數(shù)據(jù)集中盒犹，返回特征值列為value的數(shù)據(jù)集
:param data_set: 待劃分的數(shù)據(jù)集
:param axis: 劃分數(shù)據(jù)集的特征所在列的索引
:param value: 需要返回的特征值
"""
ret_data_set = [feat_vec[: axis] + feat_vec[axis+1:] for feat_vec in data_set if feat_vec[axis] == value]
return ret_data_set
選擇最好的數(shù)據(jù)集劃分方式
?????????在了解了如何劃分數(shù)據(jù)集合求信息熵之后眨业，就可以通過信息增益來選擇最好的數(shù)據(jù)集劃分方式了急膀。首先，我們會求整個數(shù)據(jù)集的原始信息熵龄捡，然后遍歷沒一個特征值卓嫂，對特征值下的所有特征求一遍信息熵，其和就是該特征值的信息熵聘殖。原始信息熵與該特征值的信息熵的差就是該特征值的信息增益晨雳。信息增益越大，則該特征值越好劃分奸腺。
def choose_best_feature_to_split(data_set):
"""選擇最好的數(shù)據(jù)劃分方式
函數(shù)調(diào)用需要滿足要求：
1. 數(shù)據(jù)必須是由一種列表元素組成的列表餐禁，且所有的列表元素都具有相同的數(shù)據(jù)長度
2. 數(shù)據(jù)的最后一列或者每個實例的最后一個元素時當前實例的類別標簽
"""
num_feature = len(data_set[0]) - 1 # 確定特征的數(shù)量
base_ent = calc_shannon(data_set) # 計算原始的信息熵
# 遍歷所有的特征以及特征值，確定最好的劃分數(shù)據(jù)集的特征
best_info_gain = 0
best_feature = -1
for i in range(num_feature):
new_ent = 0
# 計算該特征的信息熵
for value in set([ex[i] for ex in data_set]):
sub_data_set = split_data_set(data_set, i, value)
prob = len(sub_data_set) / len(data_set)
new_ent += prob * calc_shannon(sub_data_set)
# 計算信息增益洋机，確定最好的特征
info_gain = base_ent - new_ent
if info_gain > best_info_gain:
best_info_gain = info_gain
best_feature = i
return best_feature
遞歸構(gòu)建決策樹
????????現(xiàn)在坠宴，我們可以通過前面的函數(shù)，來構(gòu)建決策樹了绷旗。其工作原理如下：得到原始數(shù)據(jù)集，然后基于最好的屬性值劃分數(shù)據(jù)集副砍，由于特征值可能多于兩個衔肢，因此可能存在大于兩個分支的數(shù)據(jù)集劃分。第一次劃分后豁翎，數(shù)據(jù)將被向下傳遞到樹分支的下一個節(jié)點角骤，在這個節(jié)點上，我們可以再次劃分數(shù)據(jù)。因此我們可以采用遞歸的原則處理數(shù)據(jù)集邦尊。遞歸結(jié)束的條件是：程序遍歷完所有劃分數(shù)據(jù)集的屬性背桐，或者每個分支下的所有實例都具有相同的分類。如果所有實例具有相同的分類蝉揍，則得到一個葉子節(jié)點或者終止塊链峭。如果遍歷完所有屬性，但是類標簽仍然不是唯一的又沾，那么就采用多數(shù)表決的方法弊仪，決定該葉子節(jié)點的分類。
def create_tree(data_set, labels):
"""構(gòu)建決策樹
遞歸函數(shù)終止條件：
1. 遍歷完所有的特征杖刷，返回數(shù)量最多的標簽作為葉子節(jié)點
2. 所有的類標簽完全相同励饵，直接返回包含唯一類別的分組
"""
# 遞歸函數(shù)終止條件
class_list = [ex[-1] for ex in data_set]
if len(set(class_list)) == 1:
return class_list[0]
if len(data_set[0]) == 1:
return Counter(class_list).most_common(1)[0][0]
# 尋找最好的特征屬性
best_feat = choose_best_feature_to_split(data_set)
best_feat_label = labels[best_feat]
my_tree = {best_feat_label: {}}
del(labels[best_feat])
# 遞歸構(gòu)建決策樹
for value in set([ex[best_feat] for ex in data_set]):
sub_labels = labels[:]
my_tree[best_feat_label][value] = create_tree(split_data_set(data_set, best_feat, value), sub_labels)
return my_tree
使用決策樹執(zhí)行分類
?????????依靠訓練數(shù)據(jù)構(gòu)造了決策樹之后，就可以將它用于實際數(shù)據(jù)的分類了滑燃。下面的函數(shù)役听，可以根據(jù)輸入的測試數(shù)據(jù)集構(gòu)建決策樹，并預測測試向量的所屬分類
def classify(input_tree, feat_labels, test_vec):
"""使用決策樹進行分類"""
first_str = list(input_tree.keys())[0]
second_dict = input_tree[first_str]
feat_index = feat_labels.index(first_str)
class_label = "unknown"
for key in second_dict.keys():
if test_vec[feat_index] == key:
if type(second_dict[key]).__name__ == 'dict':
class_label = classify(second_dict[key], feat_labels, test_vec)
else:
class_label = second_dict[key]
return class_label
示例： 使用決策樹預測隱形眼鏡類型
????????接下來表窘，我們通過一個例子講解如何預測患者需要佩戴的隱形眼鏡類型禾嫉。數(shù)據(jù)集見lenses.txt(提取碼為：uhww)。數(shù)據(jù)一共分為五列蚊丐，前四列為特征列熙参，最后一列是分類標簽。
#!/usr/bin/env python3
# coding: utf-8
# Author：Shen Yi
# Date ：2020/2/15 2:35
"""機器學習實戰(zhàn) 決策樹的python實現(xiàn)"""
from collections import Counter
from math import log
def calc_shannon(data_set):
"""計算香農(nóng)熵"""
feat_vec = [f[-1] for f in data_set]
label_counts = Counter(feat_vec)
prob_list = [value / len(data_set) for key, value in label_counts.items()]
shannon_ent = sum([-(prob * log(prob, 2)) for prob in prob_list])
return shannon_ent
def split_data_set(data_set, axis, value):
"""按照給定特征劃分數(shù)據(jù)集"""
ret_data_set = [feat_vec[: axis] + feat_vec[axis+1:] for feat_vec in data_set if feat_vec[axis] == value]
return ret_data_set
def choose_best_feature_to_split(data_set):
"""選擇最好的數(shù)據(jù)劃分方式"""
num_feature = len(data_set[0]) - 1
base_ent = calc_shannon(data_set)
best_info_gain = 0
best_feature = -1
for i in range(num_feature):
new_ent = 0
for value in set([ex[i] for ex in data_set]):
sub_data_set = split_data_set(data_set, i, value)
prob = len(sub_data_set) / len(data_set)
new_ent += prob * calc_shannon(sub_data_set)
info_gain = base_ent - new_ent
if info_gain > best_info_gain:
best_info_gain = info_gain
best_feature = i
return best_feature
def create_tree(data_set, labels):
"""構(gòu)建決策樹"""
class_list = [ex[-1] for ex in data_set]
if len(set(class_list)) == 1:
return class_list[0]
if len(data_set[0]) == 1:
return Counter(class_list).most_common(1)[0][0]
best_feat = choose_best_feature_to_split(data_set)
best_feat_label = labels[best_feat]
my_tree = {best_feat_label: {}}
del(labels[best_feat])
for value in set([ex[best_feat] for ex in data_set]):
sub_labels = labels[:]
my_tree[best_feat_label][value] = create_tree(split_data_set(data_set, best_feat, value), sub_labels)
return my_tree
def classify(input_tree, feat_labels, test_vec):
"""使用決策樹進行分類"""
first_str = list(input_tree.keys())[0]
second_dict = input_tree[first_str]
feat_index = feat_labels.index(first_str)
class_label = "unknown"
for key in second_dict.keys():
if test_vec[feat_index] == key:
if type(second_dict[key]).__name__ == 'dict':
class_label = classify(second_dict[key], feat_labels, test_vec)
else:
class_label = second_dict[key]
return class_label
def demo_predict_glass():
fr = open('data\\Ch03\\lenses.txt')
lenses = list(map(lambda line: line.strip().split('\t'), fr))
lenses_label = ['age', 'prescript', 'astigmatic', 'tearRate']
lenses_tree = create_tree(lenses, lenses_label)
test_age = input("age: ")
test_prescript = input("prescript: ")
test_astigmatic = input("astigmatic: ")
test_tear_rate = input("tearRate: ")
lenses_label = ['age', 'prescript', 'astigmatic', 'tearRate']
class_label = classify(lenses_tree, lenses_label, [test_age, test_prescript, test_astigmatic, test_tear_rate])
print(class_label)
if __name__ == '__main__':
demo_predict_glass()
