在機(jī)器學(xué)習(xí)算法中，決策樹(shù)算法是一種經(jīng)常使用的預(yù)測(cè)算法。今天我們通過(guò)介紹決策樹(shù)算法的實(shí)現(xiàn)和決策樹(shù)算法的優(yōu)缺點(diǎn)，來(lái)了解一下決策樹(shù)算法。
1.算法概述
決策樹(shù)算法是在已知各種情況發(fā)生概率的基礎(chǔ)上，通過(guò)構(gòu)成決策樹(shù)來(lái)求取凈現(xiàn)值的期望值大于等于零的概率，評(píng)價(jià)項(xiàng)目風(fēng)險(xiǎn)，判斷其可行性的決策分析方法。
分類(lèi)算法是利用訓(xùn)練樣本集獲得分類(lèi)函數(shù)即分類(lèi)模型(分類(lèi)器)，從而實(shí)現(xiàn)將數(shù)據(jù)集中的樣本劃分到各個(gè)類(lèi)中。分類(lèi)模型通過(guò)學(xué)習(xí)訓(xùn)練樣本中屬性集與類(lèi)別之間的潛在關(guān)系，并以此為依據(jù)對(duì)新樣本屬于哪一類(lèi)進(jìn)行預(yù)測(cè)。
決策樹(shù)算法是直觀運(yùn)用概率分析的一種圖解法，是一種十分常用的分類(lèi)方法，屬于有監(jiān)督學(xué)習(xí)。
決策樹(shù)是一種樹(shù)形結(jié)構(gòu)，其中每個(gè)內(nèi)部結(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試，每個(gè)分支代表一個(gè)測(cè)試輸出，每個(gè)葉子結(jié)點(diǎn)代表一種類(lèi)別。
決策樹(shù)學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)，它采用自頂向下的遞歸方法，其基本思想是以信息熵為度量構(gòu)造一顆熵值下降最快的樹(shù)，到葉子結(jié)點(diǎn)處的熵值為零，此時(shí)每個(gè)葉子節(jié)點(diǎn)中的實(shí)例都屬于同一類(lèi)。
決策樹(shù)學(xué)習(xí)算法的最大優(yōu)點(diǎn)是，它可以自學(xué)習(xí)，在學(xué)習(xí)的過(guò)程中不需要使用者了解過(guò)多的背景知識(shí)，只需要對(duì)訓(xùn)練實(shí)例進(jìn)行較好的標(biāo)注，就能夠進(jìn)行學(xué)習(xí)。
2.算法種類(lèi)
ID3算法
- ID3算法中根據(jù)信息論的信息增益評(píng)估和選擇特征。每次選擇信息增益最大的候選特征，作為判斷模塊。
- 信息增益與屬性的值域大小成正比。屬性取值種類(lèi)越多，越有可能成為分裂屬性。
- ID3也不能處理連續(xù)分布的數(shù)據(jù)。
C4.5算法
- C4.5算法使用信息增益率代替信息增益，進(jìn)行特征選擇，克服了信息增益選擇特征時(shí)偏向于特征值個(gè)數(shù)較多的不足。
- C4.5算法具體算法步驟與ID3類(lèi)似。
- C4.5能夠完成對(duì)連續(xù)屬性的離散化處理，能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。
C5.0算法
- C5.0算法是Quinlan在C4.5算法的基礎(chǔ)上提出的商用改進(jìn)版本，目的是對(duì)含有大量數(shù)據(jù)的數(shù)據(jù)集進(jìn)行分析。
- C5.0算法與C4.5算法相比有以下優(yōu)勢(shì)：
- 決策樹(shù)構(gòu)建時(shí)間要比C4.5算法快上數(shù)倍，同時(shí)生成的決策樹(shù)規(guī)模也更小，擁有更少的葉子結(jié)點(diǎn)數(shù)
- 使用了提升法(boosting)，組合多個(gè)決策樹(shù)來(lái)做出分類(lèi)，使準(zhǔn)確率大大提高
- 提供可選項(xiàng)由使用者視情況決定，例如是否考慮樣本的權(quán)重、樣本錯(cuò)誤分類(lèi)成本等
CART算法
- CART決策樹(shù)的生成就是遞歸地構(gòu)建二叉決策樹(shù)的過(guò)程。
- CART用基尼系數(shù)最小化準(zhǔn)則來(lái)進(jìn)行特征選擇，生成二叉樹(shù)。
- Gini系數(shù)計(jì)算公式：
3.算法示例
在機(jī)器學(xué)習(xí)中，決策樹(shù)是一種預(yù)測(cè)模型，它代表的是對(duì)象屬性與對(duì)象值之間的一種映射關(guān)系。
決策樹(shù)的目的是擬合一個(gè)可以通過(guò)指定輸入值預(yù)測(cè)最終輸出值得模型。
4.決策樹(shù)構(gòu)建示例
描述
分析
計(jì)算
結(jié)論
5.算法實(shí)現(xiàn)步驟
選擇屬性是構(gòu)建一顆決策樹(shù)非常關(guān)鍵的一步，被選擇的屬性會(huì)成為決策樹(shù)的一個(gè)節(jié)點(diǎn)，并且不斷遞歸地選擇最優(yōu)的屬性就可以最終構(gòu)建決策樹(shù)。
計(jì)算數(shù)據(jù)集S中的每個(gè)屬性的熵 H(xi)選取數(shù)據(jù)集S中熵值最?。ɑ蛘咝畔⒃鲆孀畲?，兩者等價(jià)）的屬性在決策樹(shù)上生成該屬性節(jié)點(diǎn)使用剩余結(jié)點(diǎn)重復(fù)以上步驟生成決策樹(shù)的屬性節(jié)點(diǎn)
6.算法相關(guān)概念
熵
1948年，香農(nóng)提出了“信息熵”的概念，熵是接收的每條信息中所包含信息的平均量，是不確定性的量度，而不是確定性的量度，因?yàn)樵诫S機(jī)的信源的熵越大。熵被定義為概率分布的對(duì)數(shù)的相反數(shù)。
信息熵的公式：
信息增益
“信息增益”是用來(lái)衡量一個(gè)屬性區(qū)分?jǐn)?shù)據(jù)樣本的能力，當(dāng)使用某一個(gè)屬性作為一棵決策樹(shù)的根節(jié)點(diǎn)時(shí)，該屬性的信息增益量就越大。決策樹(shù)會(huì)選擇最大化信息增益來(lái)對(duì)結(jié)點(diǎn)進(jìn)行劃分。
7.算法實(shí)現(xiàn)代碼
import numpy as np
import math
from collections import Counter
# 創(chuàng)建數(shù)據(jù)
def create_data():
X1 = np.random.rand(50, 1)*100
X2 = np.random.rand(50, 1)*100
X3 = np.random.rand(50, 1)*100
def f(x):
return 2 if x > 70 else 1 if x > 40 else 0
y = X1 + X2 + X3
Y = y > 150
Y = Y + 0
r = map(f, X1)
X1 = list(r)
r = map(f, X2)
X2 = list(r)
r = map(f, X3)
X3 = list(r)
x = np.c_[X1, X2, X3, Y]
return x, ['courseA', 'courseB', 'courseC']
# 計(jì)算集合信息熵的函數(shù)
def calculate_info_entropy(dataset):
n = len(dataset)
# 我們用Counter統(tǒng)計(jì)一下Y的數(shù)量
labels = Counter(dataset[:, -1])
entropy = 0.0
# 套用信息熵公式
for k, v in labels.items():
prob = v / n
entropy -= prob * math.log(prob, 2)
return entropy
# 實(shí)現(xiàn)拆分函數(shù)
def split_dataset(dataset, idx):
# idx是要拆分的特征下標(biāo)
splitData = defaultdict(list)
for data in dataset:
# 這里刪除了idx這個(gè)特征的取值，因?yàn)橛貌坏搅? splitData[data[idx]].append(np.delete(data, idx))
return list(splitData.values()), list(splitData.keys())
# 實(shí)現(xiàn)特征的選擇函數(shù)
def choose_feature_to_split(dataset):
n = len(dataset[0])-1
m = len(dataset)
# 切分之前的信息熵
entropy = calculate_info_entropy(dataset)
bestGain = 0.0
feature = -1
for i in range(n):
# 根據(jù)特征i切分
split_data, _ = split_dataset(dataset, i)
new_entropy = 0.0
# 計(jì)算切分后的信息熵
for data in split_data:
prob = len(data) / m
new_entropy += prob * calculate_info_entropy(data)
# 獲取信息增益
gain = entropy - new_entropy
if gain > bestGain:
bestGain = gain
feature = i
return feature
# 決策樹(shù)創(chuàng)建函數(shù)
def create_decision_tree(dataset, feature_names):
dataset = np.array(dataset)
counter = Counter(dataset[:, -1])
# 如果數(shù)據(jù)集值剩下了一類(lèi)，直接返回
if len(counter) == 1:
return dataset[0, -1]
# 如果所有特征都已經(jīng)切分完了，也直接返回
if len(dataset[0]) == 1:
return counter.most_common(1)[0][0]
# 尋找最佳切分的特征
fidx = choose_feature_to_split(dataset)
fname = feature_names[fidx]
node = {fname: {}}
feature_names.remove(fname)
# 遞歸調(diào)用，對(duì)每一個(gè)切分出來(lái)的取值遞歸建樹(shù)
split_data, vals = split_dataset(dataset, fidx)
for data, val in zip(split_data, vals):
node[fname][val] = create_decision_tree(data, feature_names[:])
return node
# 決策樹(shù)節(jié)點(diǎn)預(yù)測(cè)函數(shù)
def classify(node, feature_names, data):
# 獲取當(dāng)前節(jié)點(diǎn)判斷的特征
key = list(node.keys())[0]
node = node[key]
idx = feature_names.index(key)
# 根據(jù)特征進(jìn)行遞歸
pred = None
for key in node:
# 找到了對(duì)應(yīng)的分叉
if data[idx] == key:
# 如果再往下依然還有子樹(shù)，那么則遞歸，否則返回結(jié)果
if isinstance(node[key], dict):
pred = classify(node[key], feature_names, data)
else:
pred = node[key]
# 如果沒(méi)有對(duì)應(yīng)的分叉，則找到一個(gè)分叉返回
if pred is None:
for key in node:
if not isinstance(node[key], dict):
pred = node[key]
break
return pred
8.算法優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：小規(guī)模數(shù)據(jù)集有效
缺點(diǎn)
- 處理連續(xù)變量不好
- 類(lèi)別比較多時(shí)，錯(cuò)誤增加得比較快
- 不能處理大量數(shù)據(jù)
9.算法優(yōu)化
決策樹(shù)算法是一種非常經(jīng)典的算法，其訓(xùn)練過(guò)程中主要依靠獲得數(shù)據(jù)間的熵及信息增益作為劃分依據(jù)，分類(lèi)效果較好。但一般情況下我們訓(xùn)練決策樹(shù)均是在數(shù)據(jù)量較小的數(shù)據(jù)集進(jìn)行，當(dāng)訓(xùn)練分類(lèi)器所用的訓(xùn)練數(shù)據(jù)足夠大時(shí)，決策樹(shù)會(huì)出現(xiàn)樹(shù)身過(guò)高、擬合效果差等問(wèn)題。因此，如何高效準(zhǔn)確的構(gòu)建決策樹(shù)成為模式識(shí)別領(lǐng)域的一項(xiàng)研究熱點(diǎn)。
使用增量訓(xùn)練的方式迭代訓(xùn)練決策樹(shù)
融合Bagging與Boosting技術(shù)訓(xùn)練多棵決策樹(shù)
對(duì)于波動(dòng)不大、方差較小的數(shù)據(jù)集， 可以探尋一種比較穩(wěn)定的分裂準(zhǔn)則作為解決辦法
總結(jié)
到此這篇決策樹(shù)算法的實(shí)現(xiàn)和決策樹(shù)算法的優(yōu)缺點(diǎn)的介紹就介紹到這了,希望大家以后多多支持W3Cschool！
