優(yōu)缺點(diǎn)和適用范圍：
優(yōu)點(diǎn)：
- 計(jì)算不那么費(fèi)時(shí)
- 便于人類的理解
- 可處理非相關(guān)特征
缺點(diǎn)：
- 容易過擬合（關(guān)于如何盡量避免這種缺點(diǎn)帶來的影響，本篇文章后期（剪枝）有介紹和相關(guān)代碼）
適用范圍：
- 數(shù)值型和非數(shù)值型數(shù)據(jù)均可
決策樹的構(gòu)型其實(shí)也是在模擬人的的思維過程：
一個(gè)人在獲得一個(gè)結(jié)論的過程中總是需要多步判斷。
但是在開始學(xué)習(xí)決策樹之前應(yīng)該先了解一些信息論的知識
假設(shè)x 為一種分類上荡， p(x) 為這種分類在總的分類中出現(xiàn)的概率
1. 信息的概念：
信息是指人類社會中傳播的一切內(nèi)容柠傍。我們顯然需要將信息進(jìn)行量化度量膏萧，香農(nóng)于1948年提出了信息熵（或稱香農(nóng)熵）的概念冒窍，用于量化信息
2. 信息熵：
信息的大小很大程度上依賴于信息的不確定性懒叛。這也是信息論一個(gè)基本的思想烦租，即延赌，一件小概率事件的發(fā)生要比一件大概率事件的發(fā)生提供更多的信息。信息的不確定性越大叉橱，其背后隱藏的信息更大挫以。
3. 信息(或稱“自信息”）的計(jì)算：
信息則被定義為I(x) = -log(p(x)) ，其中l(wèi)og以2為底窃祝。用于表示該標(biāo)簽單獨(dú)的信息大小
4. 信息熵的計(jì)算：
而熵則被定義為 H = SUM(I(x) * p(x)) 即, 對于所有的標(biāo)簽掐松，I(x) * p(x) 的加和。即每一種標(biāo)簽的出現(xiàn)的概率和這種標(biāo)簽下信息的乘積
5. 條件熵：
已知了一種分類條件徐紧，首先計(jì)算在該分類條件下分得的每一類的信息熵 * 這一類出現(xiàn)概率或杠。最后將所有的進(jìn)行加和得到了條件熵负蠕。理論上來講贼穆，不管哪一種分類方式望抽，條件熵都會比樣本的信息熵要小淆九，一是屁使，公式中可以直接看出來猎莲。二是流济，如果將一個(gè)數(shù)據(jù)集進(jìn)行了分類锐锣，顯然數(shù)據(jù)在向著有序的方向在進(jìn)行。但是绳瘟，哪一種分類方式能使得當(dāng)前數(shù)據(jù)的混亂程度最小呢雕憔？？因此引出了 信息增益的概念
6. 信息增益：
信息增益則被定義為 熵 - 條件熵
因此信息增益為正代表著數(shù)據(jù)向著有序的方向進(jìn)行
而決策樹所做的事情就是繪出一個(gè)能讓熵下降最快的樹糖声，因此每次都要選擇在當(dāng)前情況下信息增益最大的分類方法
一. ID3決策樹
有了以上的知識：我們可以開始對于ID3決策樹怎么創(chuàng)建進(jìn)行理解了
決策樹的建立是一個(gè)遞歸的過程斤彼，事實(shí)上如果大家對于樹這種結(jié)構(gòu)有一些了解的話可以很快理解為什么這應(yīng)該是一個(gè)遞歸的過程，因此不再贅述蘸泻。
首先我們拿到了一個(gè)用于訓(xùn)練的樣本集合畅卓，計(jì)算得到了該樣本的信息熵。然后以每一個(gè)feature分別做分類蟋恬，獲得了每種分類的條件熵翁潘。從而計(jì)算得到每一種分類的信息增益，其中信息增益最大的那一種對應(yīng)的就是數(shù)據(jù)混亂程度下降最快的方向歼争，因此使用這一種的分類拜马，這一分類即為這一點(diǎn)上的決策節(jié)點(diǎn)。然后基于這種分類將數(shù)據(jù)劃分成多個(gè)子集合沐绒，分別再將這些子集合進(jìn)行如上操作俩莽。從而建立決策樹
計(jì)算熵的代碼如下：
def calculate_entropy(data_set):
"""
used to calculate entropy
:param data_set: all of labels
:return: entropy
"""
dirc = {}
length = data_set[:, 0].size
label_pos = data_set[0].size -1
# label_list = label_set.tolist()
res = 0
for i in data_set[:, label_pos]:
if i[0, 0] in dirc.keys():
dirc[i[0, 0]] += 1
else:
dirc[i[0, 0]] = 1
for key in dirc.keys():
prob = float(dirc[key])/float(length)
res -= prob * math.log(prob, 2) # 第二個(gè)參數(shù)才是基數(shù)
return res
那么在一系列數(shù)據(jù)中想要知道怎樣決策，熵下降最快乔遮，依靠如下代碼計(jì)算哪一個(gè)特征最適合做數(shù)據(jù)劃分：
思想比較簡單扮超，就是分別根據(jù)每一個(gè)特征進(jìn)行數(shù)據(jù)集的劃分，找到熵最小的蹋肮，這個(gè)就是決策樹的頭節(jié)點(diǎn)
def split_data_set(data_set, condition):
"""
split the data set according to the condition
:param data_set: data set
:param condition: feature number
:return: the data sets after split
"""
dict = {}
length = data_set[:, 0].size
width = data_set[0, :].size
choice = []
for i in range(0, length):
if data_set[i, condition] not in dict.keys():
dict[data_set[i, condition]] = []
choice.append(data_set[i, condition])
dict[data_set[i, condition]].append([data_set[i, j] for j in range(0, width) if j is not condition])
return [np.mat(dict[key]) for key in dict.keys()], choice
def choose_best_conditional_entropy(data_set):
"""
actually it is choose the best condition which makes the increament is biggest
:param data_set: ..
:return: the condition which performs best
"""
width = data_set[0, :].size
length = data_set[:, 0].size
origin_entropy = calculate_entropy(data_set)
condition = -1
increament = 0
for i in range(0, width-1):
cond_entropy = 0
curr_data_sets, choice = split_data_set(data_set, i)
for data in curr_data_sets:
curr_prob = data[:, 0].size/length
cond_entropy += curr_prob * calculate_entropy(data)
if origin_entropy - cond_entropy > increament:
increament = origin_entropy - cond_entropy
condition = i
return condition
創(chuàng)建決策樹：
def most_probably_result(data_set):
"""
when all of features have been considered ,still there are different classification
we just choose the most possible one
:param data_set: the data left
:return: the most possible result
"""
dict = {}
length = data_set[:, 0].size
res = ""
for i in range(0, length):
if data_set[i, 0] not in dict.keys():
dict[data_set[i, 0]] = 0
dict[data_set[i, 0]] += 1
for key in dict.keys():
if res == "" or dict[res] < dict[key]:
res = key
return res
def create_decision_tree(data_set, feature_name):
"""
create decision tree
:param data_set: data set
:param label_set: all of labels
:return: the dictionary of tree
"""
# 出口條件
width = data_set[0, :].size
length = data_set[:, 0].size
flag = 0
if width == 1:
return most_probably_result(data_set)
for i in range(0, length):
if data_set[i, width-1] != data_set[0, width-1]:
flag = 1
break
if flag == 0:
return data_set[0, width-1]
condition = choose_best_conditional_entropy(data_set)
splited_data_set, choice = split_data_set(data_set, condition)
dict = {feature_name[condition]: {}}
len_of_choice = len(choice)
sub_feature_name = [i for i in feature_name if i is not feature_name[condition]]
for i in range(0, len_of_choice):
dict[feature_name[condition]][choice[i]] = create_decision_tree(splited_data_set[i], sub_feature_name)
return dict
效果：
二. C4.5 決策樹
實(shí)際上出刷，ID3決策樹還是存在一些問題的，比如坯辩，假設(shè)有n個(gè)樣本馁龟，如果有一個(gè)特征（比如：編號，1漆魔，2坷檩，3.....n）對于每一個(gè)樣本都不一樣却音。在計(jì)算熵時(shí)候，顯然矢炼，根據(jù)這個(gè)特征獲得的條件熵最小系瓢，信息增益最大，所以編號就會成為這棵樹的根結(jié)點(diǎn)句灌，然后夷陋，這個(gè)結(jié)點(diǎn)會有n個(gè)分支，每一個(gè)分支指向一個(gè)葉子結(jié)點(diǎn)（即一個(gè)樣本）
這顯然不是我們想要的涯塔，因?yàn)檫@樣的決策樹，只適用于測試樣本清蚀，無法適應(yīng)新的樣本匕荸。
為解決這個(gè)問題出現(xiàn)了 C4.5
C4.5 引出了一個(gè)新的概念：
增益率：
前面我們已經(jīng)介紹了信息增益：這里信息增益用表示，其中D表示樣本集合枷邪，a表示所選定的分類標(biāo)準(zhǔn)榛搔。
1. 分類標(biāo)準(zhǔn)（或者說 屬性）的“固有值”（intrinsic value)定義為：
其中：
這種表示方式，表達(dá)的是B這個(gè)集合中元素的數(shù)量
表示的是a這一特征中的取v的樣本的集合
如果定義:
則可以被寫為：
有沒有覺得上式有一些眼熟东揣，沒錯(cuò)践惑，如果a不是分類標(biāo)準(zhǔn)而是樣本的最終類別的話，IV(a)就是信息熵
信息熵用于描述數(shù)據(jù)的不確定性嘶卧，因此尔觉，如果a這一特征下的的數(shù)據(jù)取值數(shù)目越多，IV(a)越大芥吟。舉個(gè)例子：甜度這一屬性：取值為甜侦铜、不甜的 與 取值為 甜、還好钟鸵、不甜的 相比IV(a)更小
2. 增益率定義為：
這樣的設(shè)定之后會發(fā)現(xiàn)钉稍，增益率同時(shí)考慮了信息增益和可取值數(shù)量的問題。但是由于公式的原因棺耍，實(shí)際上贡未，增益率更加偏好可取值數(shù)目少的屬性。因此C4.5 決策樹并沒有直接使用增益率蒙袍，而是先挑出信息增益高于平均值的屬性俊卤，然后在從其中挑出增益率最高的
修改代碼：
def calc_shannon_ent(data_set, pos):
num_entries = len(data_set) # 獲得數(shù)據(jù)量
label_counts = {} # 為標(biāo)簽出現(xiàn)次數(shù)計(jì)數(shù)，字典
for feat_vec in data_set:
current_label = feat_vec[pos] # 獲得數(shù)據(jù)的標(biāo)簽害幅，因?yàn)閿?shù)據(jù)的最后一項(xiàng)是標(biāo)簽
if current_label not in label_counts.keys():
label_counts[current_label] = 0
label_counts[current_label] += 1 # 計(jì)數(shù)
shannon_ent = 0.0
for key in label_counts:
prob = float(label_counts[key])/num_entries # 計(jì)算每一項(xiàng)出現(xiàn)的概率
shannon_ent -= prob * log(prob, 2) # 計(jì)算香農(nóng)熵
return shannon_ent
def calculate_gain_ratio(gain, data_set, feat_pos):
iv = calc_shannon_ent(data_set, feat_pos)
return gain/float(iv)
def choose_best_feature_to_split(data_set):
num_features = len(data_set[0]) - 1
base_entropy = calc_shannon_ent(data_set, -1)
best_gain_ratio = 0.0
best_feature = -1
entropy_list = [0] * num_features
for i in range(num_features):
feat_list = [example[i] for example in data_set]
unique_vals = set(feat_list)
new_entropy = 0.0
for value in unique_vals:
sub_data_set = split_data_set(data_set, i, value)
prob = len(sub_data_set)/float(len(data_set))
new_entropy += prob * calc_shannon_ent(sub_data_set, -1)
info_gain = base_entropy - new_entropy
entropy_list[i] = info_gain
average_info_gain = sum(entropy_list)/float(num_features)
for i in range(num_features):
if entropy_list[i] > average_info_gain:
new_gain_ratio = calculate_gain_ratio(entropy_list[i], data_set, i)
if new_gain_ratio > best_gain_ratio:
best_gain_ratio = new_gain_ratio
best_feature = i
return best_feature
對比ID3和C4.5：
數(shù)據(jù)：
1,young,myope,no,reduced,no lenses
2,young,myope,no,normal,soft
3,young,myope,yes,reduced,no lenses
4,young,myope,yes,normal,hard
5,young,hyper,no,reduced,no lenses
6,young,hyper,no,normal,soft
7,young,hyper,yes,reduced,no lenses
8,young,hyper,yes,normal,hard
9,pre,myope,no,reduced,no lenses
10,pre,myope,no,normal,soft
11,pre,myope,yes,reduced,no lenses
12,pre,myope,yes,normal,hard
13,pre,hyper,no,reduced,no lenses
14,pre,hyper,no,normal,soft
15,pre,hyper,yes,reduced,no lenses
16,pre,hyper,yes,normal,no lenses
17,presbyopic,myope,no,reduced,no lenses
18,presbyopic,myope,no,normal,no lenses
19,presbyopic,myope,yes,reduced,no lenses
20,presbyopic,myope,yes,normal,hard
21,presbyopic,hyper,no,reduced,no lenses
22,presbyopic,hyper,no,normal,soft
23,presbyopic,hyper,yes,reduced,no lenses
24,presbyopic,hyper,yes,normal,no lenses
ID3:
C4.5:
從以上可以清晰的看見C4.5使用增益率的效果
三. CART決策樹
以上兩種決策樹都是通過計(jì)算熵來表現(xiàn)數(shù)據(jù)的混亂程度
而這里即將介紹的是利用“基尼指數(shù)”（Gini index）來選擇劃分屬性
基尼值：隨機(jī)抽取兩個(gè)樣本瘾蛋，其標(biāo)識不一樣的概率
基尼值越小，代表矫限，隨機(jī)抽取兩個(gè)樣本哺哼，其標(biāo)識一樣的概率越大佩抹。因此，數(shù)據(jù)純度越高
基尼指數(shù)：對應(yīng)于條件熵取董，表現(xiàn)在某種分類下的對應(yīng)的尼基值
相比于以上兩種決策樹棍苹，唯一改變的就是計(jì)算方式
因此不再對于代碼贅述
四.剪枝(pruning)處理
剪枝處理分為了：預(yù)剪枝和后剪枝兩種處理方式
- 預(yù)剪枝：在建立樹之前剪枝
- 后剪枝：在建立樹之后剪枝
怎么剪枝？茵汰？
剪枝的思想很簡單枢里，只要判斷如果這個(gè)結(jié)點(diǎn)作為了子樹根結(jié)點(diǎn)相比于直接將這個(gè)結(jié)點(diǎn)處理成葉子結(jié)點(diǎn)的準(zhǔn)確率是否有提升：
如果有提升：這個(gè)結(jié)點(diǎn)將會成為子樹根結(jié)點(diǎn)
如果沒有提升：這個(gè)結(jié)點(diǎn)將會成為該分支下數(shù)據(jù)集的出現(xiàn)最多的類別
預(yù)剪枝：
在即將在這個(gè)點(diǎn)上確定結(jié)點(diǎn)之前，將這個(gè)點(diǎn)是根結(jié)點(diǎn)和這個(gè)點(diǎn)是葉子結(jié)點(diǎn)兩種情況分別建立出來蹂午。然后分別用測試集判斷準(zhǔn)確率栏豺。比較兩種準(zhǔn)確率，哪種的準(zhǔn)確率高豆胸，用哪種奥洼。
后剪枝：
在已經(jīng)建立好的樹中，倒著遍歷每一個(gè)根結(jié)點(diǎn)晚胡，判斷這個(gè)結(jié)點(diǎn)適合是根結(jié)點(diǎn)還是葉子結(jié)點(diǎn)灵奖，對樹做修改
雖然說決策樹大多數(shù)場合適用于離散值情況，但是并不代表不能應(yīng)用于連續(xù)值情況估盘，一般來說瓷患，連續(xù)值情況，決策樹的處理方式是利用二分將連續(xù)值分成兩類遣妥，進(jìn)行決策擅编，此類不再贅述
