基于Python实现的决策树模型 6 G" |4 F3 ^+ V+ X @; } N3 ~, ?% X% H9 ?
决策树模型, Z+ x0 C7 B3 z2 ] D
目录# T7 Z) t4 G$ K) b7 A% Q3 X) v
人工智能第五次实验报告 1 " U0 V9 p; z( v; a6 T6 y决策树模型 1 0 A0 R1 e+ C1 |2 {$ i r一 、问题背景 1! X4 J+ [; `4 }
1.1 监督学习简介 1 ' f0 i5 q! K% J! {- D" U* \1.2 决策树简介 1 " }# M8 C! m, l& t/ j' k1 `( N二 、程序说明 3 1 y8 ^, Z3 ?. G7 [" w. h2.1 数据载入 3 ! \' K% n' K" k2 r- k m2.2 功能函数 31 u. o3 U4 ?+ I3 A: ]' D
2.3 决策树模型 4 3 J5 {) y* r4 ]& u三 、程序测试 5 $ u5 l& Q; j4 u1 {" D7 C! \' ^3.1 数据集说明 5/ w* H t0 U w9 P; {9 V$ w
3.2 决策树生成和测试 6 % H( U3 W0 m$ ~$ }' A# `1 X0 F3.3 学习曲线评估算法精度 7 . F8 l. F# b0 p3 B8 n+ I四 、实验总结 8 ( `/ _6 x# K. H1 l/ E6 T附 录 - 程序代码 8, I5 p0 ?% Q5 f' s% M& \* A5 J
一 、问题背景 * w" Z) b* J% z4 h1.1监督学习简介 , K! @1 q% f1 l, M2 e机器学习的形式包括无监督学习,强化学习,监督学习和半监督学习;学习任务有分类、聚类和回 归等。- o3 y. c" X) D
监督学习通过观察“输入—输出”对,学习从输入到输出的映射函数。分类监督学习的训练集为标记 数据,本文转载自http://www.biyezuopin.vip/onews.asp?id=16720每一条数据有对应的”标签“,根据标签可以将数据集分为若干个类别。分类监督学习经训练集生 成一个学习模型,可以用来预测一条新数据的标签。- t# \6 x/ O: w8 B) c K# p
常见的监督学习模型有决策树、KNN算法、朴素贝叶斯和随机森林等。 " W+ Z+ i1 m4 w3 L# L' w1.2决策树简介 n3 I* Z- a4 J' w; _
决策树归纳是一类简单的机器学习形式,它表示为一个函数,以属性值向量作为输入,返回一个决策。& H' G4 g6 U% e
决策树的组成: Z/ h1 u4 ]1 `* u+ I3 `' f, a9 D
决策树由内节点上的属性值测试、分支上的属性值和叶子节点上的输出值组成。 7 I- y% |4 N- Y5 i9 ^& Q # R! r" S7 \+ y$ d7 g: zimport numpy as np - o6 z! j! _3 M0 ?, k2 @from matplotlib import pyplot as plt / p2 M8 |$ c" \: y, h, H1 Hfrom math import log 2 i+ T6 @ A5 f% H0 yimport pandas as pd% f8 v3 d4 w8 k0 ~' c9 N
import pydotplus as pdp % {7 I1 b! s( ], i9 H 7 N- F" G# L; s9 w+ W1 r""" 1 P A- s _% w1 ~8 ~/ M6 _19335286 郑有为. {2 P; W7 b0 G* G6 T
人工智能作业 - 实现ID3决策树. B' F1 L0 K: @: m/ G, c
"""3 y9 P9 l% |' k6 e- z0 b1 P
. V$ s Q+ l) @- {
nonce = 0 # 用来给节点一个全局ID 8 v/ g$ o" |" E; gcolor_i = 0 $ [1 C4 w( Y N l( v2 {* D+ g# 绘图时节点可选的颜色, 非叶子节点是蓝色的, 叶子节点根据分类被赋予不同的颜色. n. L$ [" T4 y" G
color_set = ["#AAFFDD", "#DDAAFF", "#DDFFAA", "#FFAADD", "#FFDDAA"] 8 _ k# z9 z* j I& A5 {" H " z; d3 R5 G+ e$ w. f% N# 载入汽车数据, 判断顾客要不要买 9 h8 m( T" u, P' M# r2 pclass load_car: h8 |" C2 S6 c1 o- ]" m2 y
# 在表格中,最后一列是分类结果 ) S U# x8 Q- p" L6 I # feature_names: 属性名列表 " p8 R5 E* P+ R, E% K! \ # target_names: 标签(分类)名5 d7 I5 i( \6 H5 o1 e; E E" ~
# data: 属性数据矩阵, 每行是一个数据, 每个数据是每个属性的对应值的列表 ; I) C& f; T$ ?- x) w # target: 目标分类值列表 ]3 L5 w% o, o" v# n0 P* p( k$ H
def __init__(self):7 T5 l- @7 J ^7 `9 |, S* {
df = pd.read_csv('../dataset/car/car_train.csv')! }- I+ w. Z9 ~/ }
labels = df.columns.values 0 C8 u4 k* z# @4 J. c# O data_array = np.array(df[1:]) 7 \& l' `% u5 I5 P$ {1 H2 ]1 v( ^ self.feature_names = labels[0:-1]: A1 d J- B _& [& D& s
self.target_names = labels[-1]# }9 g o& u' i; S1 L4 e, {3 N: @5 q
self.data = data_array[0:,0:-1] ; J J9 u( U9 }; a+ P( m self.target = data_array[0:,-1]! s1 R( ~, T) ~3 G# Z
- c# }' [4 z( E0 ]# 载入蘑菇数据, 鉴别蘑菇是否有毒 ' s. {& o0 M* S f/ F& Dclass load_mushroom: ( p: t( F' i2 c) V9 X. y # 在表格中, 第一列是分类结果: e 可食用; p 有毒.- R1 I ]- X, g; L$ e# v
# feature_names: 属性名列表$ \9 M+ W6 S) [( E! B
# target_names: 标签(分类)名 6 }" S+ c8 y+ b# b2 C # data: 属性数据矩阵, 每行是一个数据, 每个数据是每个属性的对应值的列表2 y9 p$ P3 W4 ^6 C" r( U
# target: 目标分类值列表 1 T/ U2 V- d8 q6 a7 `# o2 p def __init__(self):8 ?- S) M L) U( C+ N' D* d
df = pd.read_csv('../dataset/mushroom/agaricus-lepiota.data')& C- n8 y; x8 P& v- l
data_array = np.array(df): g; j$ C% y0 r9 g
labels = ["edible/poisonous", "cap-shape", "cap-surface", "cap-color", "bruises", "odor", "gill-attachment", ) |6 X* C7 _+ ~( L0 n "gill-spacing", "gill-size", "gill-color", "stalk-shape", "stalk-root", "stalk-surface-above-ring", 7 o" C0 E1 [2 v, j8 v3 Y "stalk-surface-below-ring", "stalk-color-above-ring", "stalk-color-below-ring", c% @7 f( l- w( Z4 b6 R) r
"veil-type", "veil-color", "ring-number", "ring-type", "spore-print-color", "population", "habitat"]+ ? n( e- o" W9 M' L( w
self.feature_names = labels[1:] 1 k/ b* n. K' o6 H8 v8 c self.target_names = labels[0] 8 y8 I! n. y; n6 B4 c self.data = data_array[0:,1:] - Q! L" Z, d5 ^0 p& J self.target = data_array[0:,0]0 u$ ^, o0 C' t5 U" A `9 {. S
8 b5 j8 r1 M8 T3 x& D# 创建一个临时的子数据集, 在划分测试集和训练集时使用 6 n0 f. B, }) Xclass new_dataset:( T/ `7 {0 u; J( I9 k
# feature_names: 属性名列表2 `. r, e: [1 G1 @5 t5 D
# target_names: 标签(分类)名1 k9 D! E% k8 V! A9 `
# data: 属性数据矩阵, 每行是一个数据, 每个数据是每个属性的对应值的列表 - I: M( N: S5 ~) V% K6 l- D' j7 g8 i; i # target: 目标分类值列表$ \5 N9 f3 b" I) d; r! m+ B
def __init__(self, f_n, t_n, d, t):& z/ N, P8 w" k" m# i
self.feature_names = f_n % T0 ]) H: A/ u* I8 n$ t3 f& t self.target_names = t_n2 B) M8 v z$ O
self.data = d 0 h) F$ {5 z4 X7 f6 C/ e; G self.target = t ) Y0 }) ?. F, B+ `% O5 X & L; l; g" t" h* n+ J9 n# O# 计算熵, 熵的数学公式为: $H(V) = - \sum_{k} P(v_k) \log_2 P(v_k)$ 3 A% y* M: D& T# 其中 P(v_k) 是随机变量 V 具有值 V_k 的概率 & `. c2 g* _% E e# target: 分类结果的列表, return: 信息熵 & C7 h, ^: \! o( h+ }3 h6 ddef get_h(target):- ~; D0 T+ [ W. v' e* p
target_count = {}5 B+ b! X6 |) p a1 q. K: ]) l+ j. r
for i in range(len(target)):+ s7 ^! k4 G, M
label = target 2 [) q& _5 D. {6 i8 B2 v" v if label not in target_count.keys():" z* d O' v& @- f- n" A
target_count[label] = 1.0 / Z) P* p' ?) d else: - X5 d& V+ R( v( l$ [ target_count[label] += 1.0 3 k0 Z$ g. F F6 n) h0 d h = 0.0 3 r- W2 o& m, v for k in target_count:6 b, Q: `. [2 w8 ]9 Y8 C
p = target_count[k] / len(target) 8 J, `# y: c9 C' h h -= p * log(p, 2)1 \/ R2 M ~+ t/ |3 @
return h ( Q) U8 u5 X k* b! V9 _ * p2 v+ N+ @( M$ s7 r8 Q# {5 N+ h# 取数据子集, 选择条件是原数据集中的属性 feature_name 值是否等于 feature_value ; {7 Q: T- h6 ^8 X( Y, f( x# 注: 选择后会从数据子集中删去 feature_name 属性对应的一列 $ V9 R! T2 M6 Q9 `def get_subset(dataset, feature_name, feature_value): s6 q) [* W- H6 m6 m2 e
sub_data = [] 4 [$ E& `9 ^. g sub_target = [] R. w2 _& p4 F! R- X7 @& F f_index = -1 ( P. p1 K$ `2 L7 t0 Y1 I3 x for i in range(len(dataset.feature_names)):- f) r8 c! p5 y8 M2 F8 M
if dataset.feature_names == feature_name: , u. V4 \, q% q f_index = i* G6 M3 T) C# f/ q& M" k
break$ ]1 h8 K3 E$ S6 g2 M
$ D- ]6 t1 s8 W
for i in range(len(dataset.data)):5 s1 e k5 D$ ?9 Z5 B& E) f6 E% y
if dataset.data[f_index] == feature_value:, `7 T" C* U1 l/ X7 s) L
l = list(dataset.data[:f_index]) 4 y. R4 C/ }) o l.extend(dataset.data[f_index+1:]) 5 o& i7 ]* `0 r: I { sub_data.append(l) 3 k% X/ q! z4 | sub_target.append(dataset.target)5 k+ B' y8 q6 L9 o
! q5 o& `: e2 L* y
sub_feature_names = list(dataset.feature_names[:f_index])+ @6 l* P$ p9 j& ^2 X
sub_feature_names.extend(dataset.feature_names[f_index+1:])* ]7 _5 D3 ]; V4 m/ i6 e
return new_dataset(sub_feature_names, dataset.target_names, sub_data, sub_target) ' n0 t# u( m: F5 v ' C& }4 v1 s) `# 寻找并返回信息收益最大的属性划分 ; `$ w, R1 g0 _* Y& o1 D2 K, l# 信息收益值划分该数据集前后的熵减 9 w g: ~: N, `8 h- z0 ]; _) _: ?# 计算公式为: Gain(A) = get_h(ori_target) - sum(|sub_target| / |ori_target| * get_h(sub_target))$& Z8 y' U ^8 A+ a2 T" c; j
def best_spilt(dataset):# K2 S5 a% r* w9 g5 X* z4 x7 U
! L i7 M% \5 ? base_h = get_h(dataset.target). W2 t3 o$ b7 d' e, @
best_gain = 0.0 ) C' X* }! a" } best_feature = None 5 e* y5 `8 W! v for i in range(len(dataset.feature_names)):1 N3 J q, x1 p) [
feature_range = []$ C* V0 x1 b' Z4 j7 A
for j in range(len(dataset.data)): 5 f7 V7 m/ h0 N. d' a% { if dataset.data[j] not in feature_range: 1 J. G# F2 ?+ |8 s, I feature_range.append(dataset.data[j])" @. |/ L5 O+ }4 I& }- }
& `; x5 v( F/ \& a! F" c
spilt_h = 0.0% s* K/ k7 ~7 @0 [3 H! I n
for feature_value in feature_range: 8 T7 @/ v9 {0 V# L6 ~) l subset = get_subset(dataset, dataset.feature_names, feature_value)5 S9 S# L/ s' v R
spilt_h += len(subset.target) / len(dataset.target) * get_h(subset.target) - t$ _! U# b% p& N , g+ R/ h0 t9 C; }+ h- w if best_gain <= base_h - spilt_h:- h/ D2 k0 Z3 W. z
best_gain = base_h - spilt_h# M( s' } A) H- p
best_feature = dataset.feature_names' V. ?+ B( t9 n1 ~$ }& h8 L
6 i4 q( {# t+ z return best_feature' g- P$ |* d' Z' C T! Y* m
5 j' {0 A3 x0 M8 v0 z; w! j8 V. q& Q
# 返回数据集中一个数据最可能的标签 m8 J9 E4 x/ S: \2 ^6 y g; a; Rdef vote_most(dataset):9 l9 D( N" O# e: S+ Q' Q, v
target_range = {} ! W! U. X3 w) B4 g% t best_target = None 9 K7 y& P" `1 ?% S' V best_vote = 0* o& c O: k& L [
& v$ S6 |, I3 E6 t- h for t in dataset.target:- }# u! |4 u* ^# R3 u6 V. v
if t not in target_range.keys(): " b: T- \2 i0 q* k7 Z2 X5 Y1 `& M target_range[t] = 11 d* U" ?9 a! G* m& F3 _: @/ J
else:$ u) E4 L+ t7 c
target_range[t] += 1 & V/ C0 [* T6 V( }% I9 Y/ w W& ?1 {- j/ v- ^1 Q for t in target_range.keys(): ( r: z# z0 G( { if target_range[t] > best_vote: 6 h$ V+ A% q$ u- D best_vote = target_range[t] 7 ~4 n' Z, }2 h! d3 o T& V best_target = t * ^5 y/ C! u2 q r! X2 B. R2 N3 t. P/ a: Q2 _$ k9 ~
return best_target 3 Q4 e+ K/ { W( y! ]7 U- j1 @1 H$ ~: L- o
# 返回测试的正确率 J% n1 b7 K+ P" L; f: Q! Y
# predict_result: 预测标签列表, target_result: 实际标签列表# q$ H8 P. y4 S+ h; @. i2 f+ Y! C6 o
def accuracy_rate(predict_result, target_result): 6 w7 i5 s! ?( k3 E # print("Predict Result: ", predict_result) 8 q: N$ H: ~' k& H# f3 _- F- x # print("Target Result: ", target_result)( s1 J/ q7 M3 @) C9 @0 ?! L( N9 g# K
accuracy_score = 02 R; L! a3 s! C$ {9 B
for i in range(len(predict_result)): 1 b( \% A1 g: E1 v+ ~3 @) c1 I" | if predict_result == target_result: 6 Z3 {& R C5 h3 m) D) Z6 P8 J, n& C- | accuracy_score += 1. R! Z% J- X: {0 O% `/ M/ J
return accuracy_score / len(predict_result)! M! n' [- p4 r0 T8 D, Z( N# [
8 P* [& T4 V0 F# 决策树的节点结构 & r. P6 ~9 S9 v4 ^7 }% G# nclass dt_node: 2 k$ w4 i# Y/ e, ~ 0 j" D& \; ^0 \" c0 ?" | def __init__(self, content, is_leaf=False, parent=None): 0 b' y1 x. p4 ]/ L6 a7 O global nonce6 R* O2 E8 }! D# Y# x# f' r- x6 f. Y. r% m
self.id = nonce # 为节点赋予一个全局ID, 目的是方便画图 $ X" _6 m7 E! S' ^& D: u" _ nonce += 1 " w \) R6 w8 Q& G- i& H self.feature_name = None + N u5 J$ R6 e+ _ self.target_value = None; `8 Y+ I9 T* f
self.vote_most = None # 记录当前节点最可能的标签 & B$ L( [( k+ t' T; A if not is_leaf:% f, m* q" c8 t. I' t ]/ T% |
self.feature_name = content # 非叶子节点的属性名7 b. W- p2 t2 L% n
else:, S2 M- k0 ^" n8 J$ K7 S
self.target_value = content # 叶子节点的标签* Z8 U7 Y/ R3 w
) G4 ^, |6 K1 ^6 y& g
self.parent = parent - [3 \4 Z8 r1 r1 h, c/ Z self.child = {} # 以当前节点的属性对应的属性值作为键值( F; l- C1 H2 W
- S' n K+ W. q6 T( \" }+ x6 j
# 决策树模型: J* }' C4 }' M, E
class dt_tree: 8 M3 G, G, }0 V0 z) @) H6 P: N
def __init__(self):$ k5 U5 R% U X+ d* G' E
self.tree = None # 决策树的根节点$ }$ `0 W# p8 y. A% }
self.map_str = """ & V. m% Y& M1 l. Q2 s6 a digraph demo{ ) I \1 x" g9 h' S2 x3 ? node [shape=box, style="rounded", color="black", fontname="Microsoft YaHei"]; 2 t" W- a# c1 n1 J6 Y/ |4 l edge [fontname="Microsoft YaHei"];7 m" R7 m) d- x# U* c: M* m4 e( J
""" # 用于作图: pydotplus 格式的树图生成代码结构 ' Z( l- O/ E1 { self.color_dir = {} # 用于作图: 叶子节点可选颜色, 以标签值为键值 ! [3 D( b! H* s$ i. [( J0 T9 @! M 4 @ C* `, m2 u4 v* @7 @1 n) V # 训练模型, train_set: 训练集6 w* n% E8 u; `; g+ U
def fit(self, train_set): $ D, u( |8 T' |1 E, k E " ~1 Q L4 n g+ I9 P if len(train_set.target) <= 0: # 如果测试集数据为空, 则返回空节点, 结束递归$ p7 \ K3 d; Z
return None% S0 O# s% ? g. y$ m1 x. m
$ o/ a; x" R# }/ C" A4 n target_all_same = True) C4 c& c& l$ `. V3 m% L
for i in train_set.target:$ U6 _: w: h- \- t& W
if i != train_set.target[0]:, ]5 ]0 c; E- V0 k4 _3 m# |+ o
target_all_same = False ) @# @7 J2 U! |' |% N& _) D0 y break2 I4 f$ a( ?7 N; G, i
# W' R# a, j) C/ P' ~
if target_all_same: # 如果测试集数据中所有数据的标签相同, 则构造叶子节点, 结束递归 ( v* l% h: }2 ^1 _ node = dt_node(train_set.target[0], is_leaf=True)9 S6 B. O1 p' l9 F
if self.tree == None: # 如果根节点为空,则让该节点成为根节点 9 N# s: w. t) z' a& D self.tree = node * ^$ \1 N1 ~8 U& b" a/ S . g4 x( J, ]' {# T4 x # 用于作图, 更新 map_str 内容, 为树图增加一个内容为标签值的叶子节点+ L/ R, ?1 t# Z% J! T
node_content = "标签:" + str(node.target_value)8 V0 a# H' e1 F. i
self.map_str += "id" + str(node.id) + "[label=\"" + node_content + "\", fillcolor=\"" + self.color_dir[node.target_value] + "\", style=filled]\n" ( W# C, \# t1 V1 J7 ]+ ?6 { 7 g& L% u0 ]- z9 V3 A6 g) d% Y return node * a6 l# K2 p: Q elif len(train_set.feature_names) == 0: # 如果测试集待考虑属性为空, 则构造叶子节点, 结束递归, W% P7 ~+ t$ u3 t
node = dt_node(vote_most(train_set), is_leaf=True) # 这里让叶子结点的标签为概率上最可能的标签 2 A& G% `; s5 q3 ~, x4 R6 j if self.tree == None: # 如果根节点为空,则让该节点成为根节点 9 {% d) u2 X0 r, K4 Z self.color_dir[vote_most(train_set)] = color_set[0] ! T1 p5 R+ Z/ { self.tree = node( D& I7 d# O% ~5 j- {4 |8 f/ j: A
! L7 A( q! z- W* O7 ~: M% q6 H, |
# 用于作图, 更新 map_str 内容, 为树图增加一个内容为标签值的叶子节点 : H" ^ v; e5 a4 c1 g node_content = "标签:" + str(node.target_value) 9 z+ G- K0 G5 m! j; h$ C$ Q. R self.map_str += "id" + str(node.id) + "[label=\"" + node_content + "\", fillcolor=\"" + self.color_dir[node.target_value] + "\", style=filled]\n"( C5 N) p- b4 O5 y, D+ H
& t! _3 k& Y) r5 x! m return node/ p( _; J9 ?, c4 D$ L% N0 Z
else: # 普通情况, 构建一个内容为属性的非叶子节点* [9 j; M6 o% e- |+ k
best_feature = best_spilt(train_set) # 寻找最优划分属性, 作为该结点的值 ; k$ r7 Q+ n$ h/ ?' ^# h4 i best_feature_index = -1 0 a; n9 g0 C) t; L2 `& ], J" _ for i in range(len(train_set.feature_names)):$ f5 p9 C: f% C7 [& L
if train_set.feature_names == best_feature:* n9 Q, Y4 D) O% ? }
best_feature_index = i 5 b8 [+ {$ i+ U# N break ; A p9 F* o9 U 7 `( r1 Y+ B( {; L* ^3 i node = dt_node(best_feature) + X# P+ m& x4 `3 y6 I1 d" f node.vote_most = vote_most(train_set)" i8 f) T. {1 J5 E
if self.tree == None: # 如果根节点为空,则让该节点成为根节点 . i' R3 n; h6 Z4 r6 G# i self.tree = node 5 |0 { ]* ]% d8 y8 r# n: N3 ^1 j # 用于作图, 初始化叶子节点可选颜色- K, l8 i# y- z/ x
for i in range(len(train_set.target)): 8 c' z8 z" B! E if train_set.target not in self.color_dir: % G8 z1 C9 k2 w% W8 C4 j global color_i 5 [, g6 R) L- v5 R6 p3 A( c$ Q self.color_dir[train_set.target] = color_set[color_i]; l7 i9 |5 y3 }0 O
color_i += 1 5 V2 a. Q Q: a color_i %= len(color_set) ( `$ @+ F. X% ~) L# j8 q, g7 J+ Q4 D2 j0 ~9 E! M' T
feature_range = [] # 获取该属性出现在数据集中的可选属性值 ( F; @ G; L% I5 }1 {, `$ X for t in train_set.data: 8 m* |( o5 E& ?" l$ G if t[best_feature_index] not in feature_range: 3 [; n3 f \' x9 Q0 U* o3 E: A feature_range.append(t[best_feature_index]) 2 T, N3 a) |5 _3 m* c% A8 X) {! ]2 Z t& l: f6 q
# 用于做图, 创建一个内容为属性的非叶子节点" F$ t4 E; j" r$ g: ^( S+ Q
node_content = "属性:" + node.feature_name# n8 j" @' H, s0 ]2 s
self.map_str += "id" + str(node.id) + "[label=\"" + node_content + "\", fillcolor=\"#AADDFF\", style=filled]\n") m7 o0 ^4 Q# M
! f: O* e) ^ O7 ]6 A$ g) ^
for feature_value in feature_range:0 P% M8 G+ @! I1 q ]/ z7 M) Z- R: z
subset = get_subset(train_set, best_feature, feature_value) # 获取每一个子集 / s# A& c( Y& j$ X9 B. f* _ node.child[feature_value] = self.fit(subset) # 递归调用 fit 函数生成子节点 8 I N. T+ ?1 w5 R if node.child[feature_value] == None:; L M6 `2 D: H. O. j3 `# q
# 如果创建的子节点为空, 则创建一个叶子节点作为其子节点, 其中标签值为概率上最可能的标签/ c" z" Y& B, G4 c" f" p5 o( u1 k
node.child[feature_value] = dt_node(vote_most(train_set), is_leaf=True) 1 k7 O0 F- a* J* z6 N node.child[feature_value].parent = node' S; ?& l0 K U' S3 G7 k