Python機器學習算法實作
Author：louwill
作為機器學習中的一大類模型，樹模型一直以來都頗受學界和業界的重視。目前無論是各大比賽各種大殺器的XGBoost、lightgbm還是像随機森林、Adaboost等典型內建學習模型，都是以決策樹模型為基礎的。傳統的經典決策樹算法包括ID3算法、C4.5算法以及GBDT的基分類器CART算法。
三大經典決策樹算法最主要的差別在于其特征選擇準則的不同。ID3算法選擇特征的依據是資訊增益、C4.5是資訊增益比，而CART則是Gini指數。作為一種基礎的分類和回歸方法，決策樹可以有如下兩種了解方式。一種是我們可以将決策樹看作是一組if-then規則的集合，另一種則是給定特征條件下類的條件機率分布。關于這兩種了解方式，讀者朋友可深入閱讀相關教材進行了解，筆者這裡補詳細展開。
根據上述兩種了解方式，我們既可以将決策樹的本質視作從訓練資料集中歸納出一組分類規則，也可以将其看作是根據訓練資料集估計條件機率模型。整個決策樹的學習過程就是一個遞歸地選擇最優特征，并根據該特征對資料集進行劃分，使得各個樣本都得到一個最好的分類的過程。
ID3算法理論
是以這裡的關鍵在于如何選擇最優特征對資料集進行劃分。答案就是前面提到的資訊增益、資訊增益比和Gini指數。因為本篇針對的是ID3算法，是以這裡筆者僅對資訊增益進行詳細的表述。
在講資訊增益之前，這裡我們必須先介紹下熵的概念。在資訊論裡面，熵是一種表示随機變量不确定性的度量方式。若離散随機變量X的機率分布為：
則随機變量X的熵定義為：
同理，對于連續型随機變量Y，其熵可定義為：
當給定随機變量X的條件下随機變量Y的熵可定義為條件熵H(Y|X)：
所謂資訊增益就是資料在得到特征X的資訊時使得類Y的資訊不确定性減少的程度。假設資料集D的資訊熵為H(D)，給定特征A之後的條件熵為H(D|A)，則特征A對于資料集的資訊增益g(D,A)可表示為：
g(D,A) = H(D) - H(D|A)
資訊增益越大，則該特征對資料集确定性貢獻越大，表示該特征對資料有較強的分類能力。資訊增益的計算示例如下：
1).計算目标特征的資訊熵。
2).計算加入某個特征之後的條件熵。
3).計算資訊增益。
以上就是ID3算法的核心理論部分，至于如何基于ID3構造決策樹，我們在代碼執行個體中來看。
ID3算法實作
先讀入示例資料集：
import numpy as np
import pandas as pd
from math import log
df = pd.read_csv('./example_data.csv')
df 定義熵的計算函數：
def entropy(ele):
'''
function: Calculating entropy value.
input: A list contain categorical value.
output: Entropy value.
entropy = - sum(p * log(p)), p is a prob value.
'''
# Calculating the probability distribution of list value
probs = [ele.count(i)/len(ele) for i in set(ele)]
# Calculating entropy value
entropy = -sum([prob*log(prob, 2) for prob in probs])
return entropy 計算示例：
然後我們需要定義根據特征和特征值進行資料劃分的方法：
def split_dataframe(data, col):
'''
function: split pandas dataframe to sub-df based on data and column.
input: dataframe, column name.
output: a dict of splited dataframe.
'''
# unique value of column
unique_values = data[col].unique()
# empty dict of dataframe
result_dict = {elem : pd.DataFrame for elem in unique_values}
# split dataframe based on column value
for key in result_dict.keys():
result_dict[key] = data[:][data[col] == key]
return result_dict 根據temp和其三個特征值的資料集劃分示例：
然後就是根據熵計算公式和資料集劃分方法計算資訊增益來選擇最佳特征的過程：
def choose_best_col(df, label):
'''
funtion: choose the best column based on infomation gain.
input: datafram, label
output: max infomation gain, best column,
splited dataframe dict based on best column.
'''
# Calculating label's entropy
entropy_D = entropy(df[label].tolist())
# columns list except label
cols = [col for col in df.columns if col not in [label]]
# initialize the max infomation gain, best column and best splited dict
max_value, best_col = -999, None
max_splited = None
# split data based on different column
for col in cols:
splited_set = split_dataframe(df, col)
entropy_DA = 0
for subset_col, subset in splited_set.items():
# calculating splited dataframe label's entropy
entropy_Di = entropy(subset[label].tolist())
# calculating entropy of current feature
entropy_DA += len(subset)/len(df) * entropy_Di
# calculating infomation gain of current feature
info_gain = entropy_D - entropy_DA
if info_gain > max_value:
max_value, best_col = info_gain, col
max_splited = splited_set
return max_value, best_col, max_splited 最先選到的資訊增益最大的特征是outlook：
決策樹基本要素定義好後，我們即可根據以上函數來定義一個ID3算法類，在類裡面定義構造ID3決策樹的方法：
class ID3Tree:
# define a Node class
class Node:
def __init__(self, name):
self.name = name
self.connections = {}
def connect(self, label, node):
self.connections[label] = node
def __init__(self, data, label):
self.columns = data.columns
self.data = data
self.label = label
self.root = self.Node("Root")
# print tree method
def print_tree(self, node, tabs):
print(tabs + node.name)
for connection, child_node in node.connections.items():
print(tabs + "\t" + "(" + connection + ")")
self.print_tree(child_node, tabs + "\t\t")
def construct_tree(self):
self.construct(self.root, "", self.data, self.columns)
# construct tree
def construct(self, parent_node, parent_connection_label, input_data, columns):
max_value, best_col, max_splited = choose_best_col(input_data[columns], self.label)
if not best_col:
node = self.Node(input_data[self.label].iloc[0])
parent_node.connect(parent_connection_label, node)
return
node = self.Node(best_col)
parent_node.connect(parent_connection_label, node)
new_columns = [col for col in columns if col != best_col]
# Recursively constructing decision trees
for splited_value, splited_data in max_splited.items():
self.construct(node, splited_value, splited_data, new_columns) 根據上述代碼和示例資料集構造一個ID3決策樹：
以上便是ID3算法的手寫過程。sklearn中tree子產品為我們提供了決策樹的實作方式，參考代碼如下：
from sklearn.datasets import load_iris
from sklearn import tree
import graphviz
iris = load_iris()
# criterion選擇entropy，這裡表示選擇ID3算法
clf = tree.DecisionTreeClassifier(criterion='entropy', splitter='best')
clf = clf.fit(iris.data, iris.target)
dot_data = tree.export_graphviz(clf, out_file=None,
feature_names=iris.feature_names,
class_names=iris.target_names,
filled=True,
rounded=True,
special_characters=True)
graph = graphviz.Source(dot_data)
graph 以上便是本篇的全部内容，完整版代碼和資料請移步本人github：
https://github.com/luwill/machine-learning-code-writing
參考資料：
李航 統計學習方法
https://github.com/heolin123/id3/blob/master