ID3 C4.5 CART 比較
ID3（以信息增益為準(zhǔn)則選擇信息增益最大的屬性）
- 缺點(diǎn)
- 信息增益對(duì)==可取值數(shù)目較多的屬性==有所偏好，比如通過(guò)ID號(hào)可將每個(gè)樣本分成一類，但是沒(méi)有意義逢渔。（具體原因請(qǐng)查信息增益的數(shù)學(xué)公式）
- ID3只能對(duì)離散屬性（標(biāo)稱型數(shù)據(jù)）的數(shù)據(jù)集構(gòu)造決策樹(shù)，即只能應(yīng)用于分類問(wèn)題。
- ID3對(duì)缺失值敏感
C.5(以信息增益率為準(zhǔn)則選擇信息增益率最大的屬性)
- 對(duì)ID3的改進(jìn)
- 對(duì)于離散值處理與ID3一致宽闲；可以處理連續(xù)數(shù)值型屬性，方法：
- C4.5可以允許變量存在缺失值握牧，會(huì)把缺失值單獨(dú)作為一類或者按概率分到每一個(gè)子樹(shù)上容诬。
CART Classification and Regression tree (以基尼不純度為準(zhǔn)則選擇基尼增益最大的屬性)
- 決策樹(shù)分為分類樹(shù)和回歸樹(shù)，即可以處理分類問(wèn)題沿腰，也可以處理回歸問(wèn)題览徒。
- 實(shí)際場(chǎng)合中CART 用的較多。
決策樹(shù)的遞歸構(gòu)建
- 終止條件（滿足任意一個(gè)）：
遍歷完所有劃分?jǐn)?shù)據(jù)集的屬性
-
每個(gè)分支下的所有實(shí)例都具有相同的分類（熵為0）
注明：遍歷完所有劃分?jǐn)?shù)據(jù)集的屬性颂龙，類標(biāo)簽仍不唯一习蓬，一般采用多數(shù)表決的方法決定該葉子節(jié)點(diǎn)的分類
決策樹(shù)過(guò)擬合問(wèn)題
- 表現(xiàn)：訓(xùn)練誤差較低但泛化誤差卻比較大的情況
- 原因：出現(xiàn)噪聲數(shù)據(jù)纽什；缺乏有代表性的樣本
- 解決辦法：剪枝（預(yù)剪枝，后剪枝）
- 預(yù)剪枝：在構(gòu)造過(guò)程中躲叼，當(dāng)某個(gè)節(jié)點(diǎn)滿足剪枝條件芦缰，則直接停止此分支的構(gòu)造
- 設(shè)置閾值：當(dāng)觀察到的不純性度量的增益（或估計(jì)的泛化誤差的改進(jìn)）低于某個(gè)確定的閾值時(shí)就停止擴(kuò)展葉節(jié)點(diǎn)
- 設(shè)置樹(shù)的深度限制，設(shè)置samles個(gè)數(shù)限制
- ==問(wèn)題==：閾值太高將導(dǎo)致擬合不足的模型枫慷，而閾值太低就不能充分的解決過(guò)擬合的問(wèn)題
- 后剪枝：先構(gòu)造完整的決策樹(shù)让蕾，再通過(guò)某些條件==自底向上的方式==修剪決策樹(shù)。
- 若該結(jié)點(diǎn)對(duì)應(yīng)的子樹(shù)替換為葉結(jié)點(diǎn)能提升決策樹(shù)的泛化能力流礁，則將改子樹(shù)替換為葉結(jié)點(diǎn)涕俗。
決策樹(shù)的局限和優(yōu)勢(shì)
局限
- 精確度相比其他方法較低
- 樹(shù)可能非常不健壯：訓(xùn)練集出現(xiàn)小的波動(dòng)，影響決策結(jié)果
- 學(xué)習(xí)最優(yōu)決策樹(shù)的問(wèn)題被認(rèn)為是 NP-complete的：利用啟發(fā)式算法神帅，貪婪算法再姑，容易出現(xiàn)局部最優(yōu)解，非全局最優(yōu)解找御。
- 容易出現(xiàn)過(guò)擬合的問(wèn)題：決策樹(shù)學(xué)習(xí)者可以創(chuàng)建過(guò)于復(fù)雜的樹(shù)元镀，從訓(xùn)練數(shù)據(jù)中不能很好地推廣。
優(yōu)勢(shì)
- 易于理解和解釋：人們能夠通過(guò)簡(jiǎn)單的解釋理解決策樹(shù)模型霎桅。樹(shù)也可以以非專家易于解釋的方式以圖形顯示
- 能夠處理回歸和分類問(wèn)題栖疑。
- 需要很少的數(shù)據(jù)準(zhǔn)備
- 使用白盒模型：如果一個(gè)給定的情況在模型中是可觀察的，那么這個(gè)條件的解釋可以用布爾邏輯來(lái)解釋
- 可以使用統(tǒng)計(jì)測(cè)試來(lái)驗(yàn)證模型
- 用大數(shù)據(jù)集執(zhí)行效果很好
- 比其他方法更能反映人類的決策
python 實(shí)現(xiàn)DT
# -*- coding: utf-8 -*-
"""
Created on 2017/12/27
@author: donghao
"""
import numpy as np
from math import log
import operator
def create_dataset():
dataset = [[1, 1, 'y'],
[1, 1, 'y'],
[1, 0, 'n'],
[0, 1, 'n'],
[0, 1, 'n']]
labels = ['no surfacing', 'flippers'] # features_name
return dataset, labels
def calc_shannon_ent(dataset):
"""
# 計(jì)算數(shù)據(jù)集的熵
:param dataset: 待劃分?jǐn)?shù)據(jù)集
:return: 熵
"""
num_entries = len(dataset)
label_counts = {}
for line in dataset:
current_label = line[-1]
if current_label not in label_counts.keys():
label_counts[current_label] = 0
label_counts[current_label] += 1
shannon_ent = 0.0
for key in label_counts:
prob = float(label_counts[key])/num_entries
shannon_ent -= prob*log(prob, 2)
return shannon_ent
def split_dataset(dataset, axis, value):
"""
按照給定的特征劃分?jǐn)?shù)據(jù)集
:param dataset: 待劃分?jǐn)?shù)據(jù)集
:param axis: 劃分?jǐn)?shù)據(jù)集的特性（f1 or f2）
:param value: 需要返回的特征值（比如axis取f1時(shí)滔驶，是返回f1=0 or f1=1）
:return: 返回按axis分遇革，屬于value的子數(shù)據(jù)集
"""
ret_dataset = []
for line in dataset:
if line[axis] == value:
reduced_line = line[:axis]
reduced_line.extend(line[axis + 1:])
ret_dataset.append(reduced_line) # append and extend
return ret_dataset
def choose_best_feature_to_split(dataset):
"""
# 分別計(jì)算按每個(gè)feature的分裂之后的信息增益（ID3），選擇最大的
:param dataset:
:return:
"""
num_features = len(dataset[0]) - 1
base_entropy = calc_shannon_ent(dataset)
best_info_gain = 0.0
best_feature = -1
for i in range(num_features):
# 將dataset 的第i列放在一個(gè)list中
feat_list = [example[i] for example in dataset]
# list 中不重復(fù)的數(shù)據(jù)
unique_vals = set(feat_list)
new_entropy = 0.0
for value in unique_vals:
sub_dataset = split_dataset(dataset, i, value)
prob = len(sub_dataset)/float(len(dataset))
new_entropy += prob * calc_shannon_ent(sub_dataset)
info_gain = base_entropy - new_entropy
if info_gain>best_info_gain:
best_info_gain = info_gain
best_feature = i
return best_feature
def majority_cnt(class_list):
"""
多數(shù)判決（所有features都使用完了）
:param class_list:
:return:
"""
class_count = {}
for vote in class_list:
if vote not in class_count.keys():
class_count[vote] = 0
class_count[vote] += 1
sorted_class_count = sorted(class_count.items(),
key=operator.itemgetter(1),
reverse=True)
return sorted_class_count[0][0]
def create_tree(dataset, labels):
class_list = [example[-1] for example in dataset]
# 類別完全相同 停止繼續(xù)劃分
if class_list.count(class_list[0]) == len(class_list):
return class_list[0]
# 遍歷完所有特征時(shí)返回出現(xiàn)次數(shù)最多的類別揭糕，比如剩('yes'),('yes'),('no')
if len(dataset[0]) == 1:
return majority_cnt(class_list)
best_feature = choose_best_feature_to_split(dataset)
best_feature_label = labels[best_feature]
my_tree = {best_feature_label: {}}
del (labels[best_feature])
feature_values = [example[best_feature] for example in dataset]
unique_values = set(feature_values)
for value in unique_values:
sub_labels = labels[:]
my_tree[best_feature_label][value] = create_tree(
split_dataset(dataset, best_feature, value),
sub_labels)
return my_tree
if __name__=='__main__':
dataset, labels = create_dataset()
# calc_shannon_ent test
print(calc_shannon_ent(dataset))
# split_dataset test
print(split_dataset(dataset, 1, 1))
print(split_dataset(dataset, 1, 0))
# choose_best_feature_to_split test
print(choose_best_feature_to_split(dataset))
# create_tree test
print(create_tree(dataset, labels))
