基于Python实现的决策树模型 I8 n( K+ Q/ _/ r# p4 [
3 O' X# ?) {' `3 o7 O* K
决策树模型 % u& l& |4 C! B: ~8 _目录 , {1 y4 c! O+ y, Q/ r: _) g/ F, ]4 U人工智能第五次实验报告 1- J$ y. `$ s1 l! V0 T
决策树模型 1 7 X# Y" c& ^/ V+ Y* r一 、问题背景 17 ?" y, p5 t2 D2 W
1.1 监督学习简介 1: ?7 |. R% q: W( }, j0 y F( `
1.2 决策树简介 1; k% ~# l6 x c& K2 G& [
二 、程序说明 3 % r6 j3 u! v- @* T7 S2.1 数据载入 3& V; {5 ?* ^( V q1 ~- ]- M
2.2 功能函数 3" i" }# n4 O. r$ H" O3 }
2.3 决策树模型 48 \4 F7 U3 h4 K* Y) E) b+ x
三 、程序测试 59 o8 N5 G9 g, i# g
3.1 数据集说明 5 " t3 @5 n; N# J f t3.2 决策树生成和测试 6 3 D% s; a. N2 P: F: c/ w: Z# S3.3 学习曲线评估算法精度 74 u4 Q" @2 c% Q8 ?3 _3 s& p
四 、实验总结 8 4 Q- Y) Z a- b0 N) W9 m附 录 - 程序代码 8 " |$ H$ S# G7 U( t一 、问题背景$ B8 o+ |+ p* U6 T( }; H4 g0 |8 B: H
1.1监督学习简介. F0 p' ~% [) H4 y5 t3 Y c: n
机器学习的形式包括无监督学习，强化学习，监督学习和半监督学习；学习任务有分类、聚类和回 归等。- I' b$ d+ Y8 c0 s' G/ k
监督学习通过观察“输入—输出”对，学习从输入到输出的映射函数。分类监督学习的训练集为标记 数据，本文转载自http://www.biyezuopin.vip/onews.asp?id=16720每一条数据有对应的”标签“，根据标签可以将数据集分为若干个类别。分类监督学习经训练集生 成一个学习模型，可以用来预测一条新数据的标签。 0 Y2 v; M; v7 t常见的监督学习模型有决策树、KNN算法、朴素贝叶斯和随机森林等。7 i O8 F6 z8 A- D) d
1.2决策树简介7 }/ _, Z. d& t- M- t8 m4 ?$ z( t
决策树归纳是一类简单的机器学习形式，它表示为一个函数，以属性值向量作为输入，返回一个决策。 Z0 |. e' d$ D决策树的组成3 n t( n/ |1 e$ q- y# i
决策树由内节点上的属性值测试、分支上的属性值和叶子节点上的输出值组成。 $ W- a2 [3 y7 b n! ?; H7 d% f& {- s4 j3 M' F
import numpy as np B1 D& I; B, v9 yfrom matplotlib import pyplot as plt 5 L' X" `& }9 @from math import log : w' n5 @; t/ H- J0 h: e0 V, \( Gimport pandas as pd0 V' q- o; P: p, Q6 `8 S
import pydotplus as pdp ! Y% H+ r, u. t- p 9 c4 l* I) S1 |. e1 P""" 9 X* A1 O% F3 }! g2 `7 J0 n19335286 郑有为 5 m+ j, P0 h0 X! N7 q9 x* V) \人工智能作业 - 实现ID3决策树* a! Y6 F2 T D+ O& o- g1 M \$ b7 |
""" - V1 r1 F$ \3 d5 ?8 x, D2 K7 i' `+ d) e/ g( D+ b
nonce = 0 # 用来给节点一个全局ID $ v8 ^. c" Z( [4 L( V* `color_i = 04 [( u: i' L- L
# 绘图时节点可选的颜色, 非叶子节点是蓝色的, 叶子节点根据分类被赋予不同的颜色 2 T7 g! `% x2 T; ]. fcolor_set = ["#AAFFDD", "#DDAAFF", "#DDFFAA", "#FFAADD", "#FFDDAA"]! d, ~- M5 h1 j; u4 u7 L
; `# p( Q# I. ]: L
# 载入汽车数据, 判断顾客要不要买 * E4 h" r* u/ z* I* u5 Fclass load_car:+ c4 |" V6 v1 B4 w& r0 C; G
# 在表格中,最后一列是分类结果* E$ ?' F4 g" Z3 D
# feature_names: 属性名列表; i( y( t7 O! h% n& b- R5 [
# target_names: 标签(分类)名; s0 z* z( T' C% H. V; R
# data: 属性数据矩阵, 每行是一个数据, 每个数据是每个属性的对应值的列表 E2 A6 j5 t) ^1 N$ a # target: 目标分类值列表7 e7 `! r( C. S% @, F( K
def __init__(self): 0 I' M# k+ `1 A1 J b' r( K6 R df = pd.read_csv('../dataset/car/car_train.csv') w2 s# T4 l- C9 I' R labels = df.columns.values) s8 A0 k* T2 A5 R8 ^
data_array = np.array(df[1:])$ ?2 P4 `; S' Y- g
self.feature_names = labels[0:-1]% ^4 d) Q) o! K' {% m
self.target_names = labels[-1]5 k! K& E) m8 B/ y3 ~. U! S" F
self.data = data_array[0:,0:-1] ! o# i3 e- a; U- `( T self.target = data_array[0:,-1]2 b; O7 q4 i# B2 J) k
! k4 y: h" d" j3 |! [! I6 i
# 载入蘑菇数据, 鉴别蘑菇是否有毒' P& I/ m2 d0 f. V# J& T
class load_mushroom: % C3 V4 ^5 S. g, G+ W # 在表格中, 第一列是分类结果: e 可食用; p 有毒.. v k1 {2 M Q# e! ~
# feature_names: 属性名列表 $ l, ~8 A) s/ H # target_names: 标签(分类)名 8 E3 u# {1 R% i, f( {: a4 V # data: 属性数据矩阵, 每行是一个数据, 每个数据是每个属性的对应值的列表 : L) s- l! _3 F! a9 t* u # target: 目标分类值列表 : }. S, t+ ]# T5 s9 W+ t8 {0 } def __init__(self): 4 M3 ]& @3 a- |# p6 Z) |/ P df = pd.read_csv('../dataset/mushroom/agaricus-lepiota.data'). f- A7 @( v5 k
data_array = np.array(df)2 g. p; f; u" \) z
labels = ["edible/poisonous", "cap-shape", "cap-surface", "cap-color", "bruises", "odor", "gill-attachment",; F- K9 h. T6 N' X) T1 O! H: K
"gill-spacing", "gill-size", "gill-color", "stalk-shape", "stalk-root", "stalk-surface-above-ring",! n4 w5 M# {1 K! K/ K
"stalk-surface-below-ring", "stalk-color-above-ring", "stalk-color-below-ring", 5 e, Q" n+ Z+ |7 P. m/ v$ { g "veil-type", "veil-color", "ring-number", "ring-type", "spore-print-color", "population", "habitat"]9 |0 R+ m7 a; U9 f0 y! e4 ^/ {
self.feature_names = labels[1:]2 x5 W5 B+ E- L9 f
self.target_names = labels[0] 3 w7 w9 C. T: }% U2 B, L self.data = data_array[0:,1:] % ^) q4 P, Z5 I5 T. c1 s self.target = data_array[0:,0]7 j+ n7 j# I! ^3 ]# L: U5 n V
2 U1 v1 {) ^ U; l% c# 创建一个临时的子数据集, 在划分测试集和训练集时使用5 [4 T4 n0 s3 L. c+ w9 Z4 L" V S
class new_dataset:- u9 i" t7 l% \6 u
# feature_names: 属性名列表5 o0 Y: J" N) q2 r& N
# target_names: 标签(分类)名3 y7 I$ @: _: I! \( J) h
# data: 属性数据矩阵, 每行是一个数据, 每个数据是每个属性的对应值的列表1 f8 n1 Y" }8 K9 |4 ~3 |/ C7 t/ x4 [! d
# target: 目标分类值列表 ! K6 z+ j( Z. }" ~" @+ u* w def __init__(self, f_n, t_n, d, t): 6 c) y$ t) [$ j4 { self.feature_names = f_n * w1 O: J P, G2 u, ] self.target_names = t_n ) ]0 ^0 u" z$ I3 Y! Q self.data = d! v" b, J( I6 S$ ^3 _. b
self.target = t8 i! ^: T8 A- Y+ z
; r. s, G! L' }4 J
# 计算熵, 熵的数学公式为: $H(V) = - \sum_{k} P(v_k) \log_2 P(v_k)$+ D. G, s0 B7 F2 y' _
# 其中 P(v_k) 是随机变量 V 具有值 V_k 的概率 9 X5 }0 [+ \/ [, r# target: 分类结果的列表, return: 信息熵4 O" b) }8 l8 L3 q
def get_h(target):' G& F: I7 I2 o' x4 Z7 q' f
target_count = {} o$ t# z$ e N+ [- q& U1 f
for i in range(len(target)): ; Q# U8 s0 E" i; T% H1 Y4 { label = target # }/ [6 v9 ~9 Z# d/ k) O, U if label not in target_count.keys(): 4 ?+ S$ T" D3 I$ ^* _: A" t7 P target_count[label] = 1.0 8 b( M/ M* X1 V8 j, M# d else:3 K0 F, \- z9 F
target_count[label] += 1.01 v S9 Q3 A" z* P- x, N
h = 0.0 ) c& J4 E% x1 q0 j; w for k in target_count: ! h0 X1 O6 |* Z$ f+ e8 r p = target_count[k] / len(target)! F3 U+ a9 H8 C
h -= p * log(p, 2)0 j( r6 W' {6 A0 M: S9 w
return h 0 d# q1 L5 h+ I1 ~ ! Y5 r! H& e4 r% R4 L8 B1 W# 取数据子集, 选择条件是原数据集中的属性 feature_name 值是否等于 feature_value! P w" }6 k' ?
# 注: 选择后会从数据子集中删去 feature_name 属性对应的一列 3 ]5 X4 _8 ^' d" D8 Tdef get_subset(dataset, feature_name, feature_value):8 _% T- W2 S2 z6 p2 _
sub_data = []# |0 Q* X1 l* n$ b4 ~
sub_target = []; X9 W+ J5 _, ]; A, H# t6 A! [
f_index = -1; o L/ C% Q9 b0 P" @3 ?
for i in range(len(dataset.feature_names)):. |! _0 L7 m. P0 I: ^
if dataset.feature_names == feature_name: 5 M' c4 [8 L9 ^; z f_index = i * R1 O1 X$ A/ X) d break ! L/ o! k `2 F2 d: q % m: G4 {0 x/ b+ \2 {1 v! W for i in range(len(dataset.data)): 0 y$ J7 g" e9 Q1 g if dataset.data[f_index] == feature_value:& @( ^ l+ [3 b2 p- S8 c
l = list(dataset.data[:f_index]) # g8 g0 c8 t( c9 |9 }/ u l.extend(dataset.data[f_index+1:]) . \# X: I. w, [, J- I% M( ] sub_data.append(l)% Q: l: j! ?/ k& A9 h* L6 X* ~
sub_target.append(dataset.target)- H( x/ p) {4 j6 T; S
' I: N/ e5 z& a7 ~. {1 @ sub_feature_names = list(dataset.feature_names[:f_index])$ s' E5 a3 ]6 q& I. X9 V0 k0 o% R) F
sub_feature_names.extend(dataset.feature_names[f_index+1:])5 ^( n0 a( e5 K: x% z
return new_dataset(sub_feature_names, dataset.target_names, sub_data, sub_target): T1 K% \1 [3 ]9 D: [1 X
& j# F9 o, v& T- n/ }; x# 寻找并返回信息收益最大的属性划分 : a2 f5 c+ h; [# 信息收益值划分该数据集前后的熵减# N& S2 W. J( y a% l
# 计算公式为: Gain(A) = get_h(ori_target) - sum(|sub_target| / |ori_target| * get_h(sub_target))$* G6 Z' N; v2 S! H4 ^
def best_spilt(dataset): * w: ?/ H. `( ? * q3 K8 p# a1 N& y9 d base_h = get_h(dataset.target) w# S" L6 f/ |. r$ _" J best_gain = 0.0" B& i. L3 F2 X! u
best_feature = None 3 ~3 ]0 |! ?8 C: e$ s. l. w6 k( C$ q for i in range(len(dataset.feature_names)):7 P& X/ [ F1 i
feature_range = [] k4 w6 z5 N, c. _* _; v
for j in range(len(dataset.data)):# C- k3 h+ q# `6 C; y% d. V
if dataset.data[j] not in feature_range: 9 a: o" |8 X# x4 w& H! t feature_range.append(dataset.data[j]) ' o+ A1 i* r" V/ f! n3 l- A: `; k a
spilt_h = 0.0 ) w% p2 [& A0 { for feature_value in feature_range: * p0 s1 i. o! g8 Z subset = get_subset(dataset, dataset.feature_names, feature_value)+ @% @4 h M: s3 e- W: m( m) y3 s8 h
spilt_h += len(subset.target) / len(dataset.target) * get_h(subset.target) ! z) P9 _& M8 B" u2 k, m8 R d4 z3 V9 |
if best_gain <= base_h - spilt_h: 3 E$ J& Y& V6 F0 {5 y$ g- d9 f8 N best_gain = base_h - spilt_h$ J+ R, z/ p( Q
best_feature = dataset.feature_names . T& H3 u- z3 N2 o) W% | , t9 Q ?: c- d3 f, c% s$ m return best_feature 3 l% j$ {" Q. C1 l% x- Z9 ?+ b" g$ @7 N/ R
# 返回数据集中一个数据最可能的标签 * ~* e5 h6 A9 P: c# K3 S/ {( G. R' Sdef vote_most(dataset):1 g1 F# P+ `7 h% j& R% r7 i
target_range = {}4 R% K- o/ D+ n* p: V" J
best_target = None ; z* T) k* m( x* q; ? best_vote = 0& W4 V4 T. Z5 Y+ I7 }+ J4 Q. |
' _7 O/ o: U1 ~* Q3 T5 i( u for t in dataset.target: * x9 o F1 \! U! }" p if t not in target_range.keys():6 v- K! c. `. h9 K. M5 k- a
target_range[t] = 1. k: Y* `+ y# @& w$ N& b
else: 5 P4 j0 r0 p- `4 G. u: B target_range[t] += 1 . [ p- L C& C8 d$ _" N5 \ # ~% O ?, _* ]; e" `; U for t in target_range.keys():) M5 U: j6 n4 X
if target_range[t] > best_vote:& r1 }0 f3 N, M) {; k
best_vote = target_range[t] * R& d' E- C+ y" Z best_target = t . G3 ?" C( A( ]; Z$ z) H5 p0 s # C) z1 G, O9 V! ? return best_target5 N5 Z, y1 M+ T: n$ k) \: y" \$ B
9 i( z+ c: ^/ `+ J4 {. C. P: W' ]' i" [# 返回测试的正确率8 {0 E' w& H2 q3 {3 s
# predict_result: 预测标签列表, target_result: 实际标签列表( O' x8 x+ l7 e0 k( i: o
def accuracy_rate(predict_result, target_result):# i* B+ V8 H. U6 x3 J. E/ N! Q8 w0 J
# print("Predict Result: ", predict_result) . K4 D& Z- \8 R' H # print("Target Result: ", target_result)' ], M, _4 x- P1 C8 I6 B1 [
accuracy_score = 0 ) ]+ { L0 B( } for i in range(len(predict_result)): # D/ j: Y" a, |. e if predict_result == target_result: 0 r0 G" Y, y3 h0 B& e( F* m accuracy_score += 1 G' N0 L- i; w6 X
return accuracy_score / len(predict_result) s& Q2 |$ w4 d. B1 O, j # l0 W% ^: u# }0 ~: J6 c# 决策树的节点结构" t* i) t6 v: T- I, K: s
class dt_node: 6 s/ L3 H( T2 ~: f& o % x. l$ t2 t' y1 f def __init__(self, content, is_leaf=False, parent=None):2 q, E' d( E: q" l% B
global nonce, f1 w, ~- H- y4 n9 a
self.id = nonce # 为节点赋予一个全局ID, 目的是方便画图/ l' z& ~ S$ ]* H1 F7 X4 _: Q
nonce += 1) g6 ~" L6 H" M; ?* J. H" M7 p
self.feature_name = None : u5 T/ H1 S3 E8 E+ Z self.target_value = None/ s% i4 }5 t l9 \) Z. o5 K* p
self.vote_most = None # 记录当前节点最可能的标签 o1 i3 j0 H: Y% X( D
if not is_leaf:0 Q: r7 P/ r5 v
self.feature_name = content # 非叶子节点的属性名 % \# h1 j/ v- C$ a: d% X else:' e" O1 d$ ?# H _( k
self.target_value = content # 叶子节点的标签 5 @- [$ M5 P: N% \1 E F5 f8 H 7 G8 W( L" Z0 g self.parent = parent $ h6 W' O4 x6 M3 Z8 @ self.child = {} # 以当前节点的属性对应的属性值作为键值 9 E% U8 ~# b5 E$ V ` u, ?8 ?, W 3 F# x8 r. E$ S) q) \ D$ w' W# 决策树模型 # Y6 R3 F9 z) i3 ]" ^; v" Bclass dt_tree: / Q9 N/ E9 ^5 a; V4 q4 u+ g- ~8 ?: {2 }3 `1 P5 H2 E
def __init__(self):% |4 n. ]* d. ^8 z) v( _
self.tree = None # 决策树的根节点% E3 [+ W4 m4 K8 {, j; O
self.map_str = """, Q0 w# E. J1 @( s8 o2 x
digraph demo{2 t' m# A( D; @# d# W8 n1 H+ R
node [shape=box, style="rounded", color="black", fontname="Microsoft YaHei"]; 9 T5 w$ P( |: O P' c edge [fontname="Microsoft YaHei"];4 q- t" n) v" _+ [5 C1 z
""" # 用于作图: pydotplus 格式的树图生成代码结构 ! ^8 d- P$ A. r: K8 R9 Q3 | self.color_dir = {} # 用于作图: 叶子节点可选颜色, 以标签值为键值2 x2 @# h! W8 \: K. V2 `, ?
+ b8 Q0 s, b- l' G+ Y6 \1 c # 训练模型, train_set: 训练集 - V$ \% p* H% s2 F+ @ def fit(self, train_set): 7 {# j3 T6 b) q% K2 R+ H! T; B# k5 T5 o
if len(train_set.target) <= 0: # 如果测试集数据为空, 则返回空节点, 结束递归 ! J4 w* u0 M7 e# C. }, ? return None T& A) _5 S; r2 f) a1 u' N9 n+ @# I5 t% T+ Z
target_all_same = True ; `8 E" p1 A; | for i in train_set.target: 3 W9 X) G* f# X if i != train_set.target[0]: ; y* |( Q" P" _, X7 `5 K# ^; y1 i0 m target_all_same = False3 b: x+ n& Q' B' \) p
break2 h& w% I7 u+ S! R8 I" `, h5 Q$ d# u6 s& n
0 O8 M' h# q" O! v' h+ _ if target_all_same: # 如果测试集数据中所有数据的标签相同, 则构造叶子节点, 结束递归 6 ` T4 I. y7 L# W( ? node = dt_node(train_set.target[0], is_leaf=True) $ J' m! }; V7 Y' `' c% G$ w if self.tree == None: # 如果根节点为空,则让该节点成为根节点6 x, \8 v5 l' K$ m R0 H) h
self.tree = node . r- u- Q/ @+ p6 ^) } : ?: i, Y1 h9 W3 E # 用于作图, 更新 map_str 内容, 为树图增加一个内容为标签值的叶子节点 ; M5 [8 E2 K2 V( M3 B9 O( P node_content = "标签：" + str(node.target_value) : ?2 E2 e ^8 F, |* S& h% }/ n( \ self.map_str += "id" + str(node.id) + "[label=\"" + node_content + "\", fillcolor=\"" + self.color_dir[node.target_value] + "\", style=filled]\n"6 A8 F3 w( k8 c( z4 x
9 a' e) E: r" `- Z
return node4 c4 r/ g p' C" k2 n
elif len(train_set.feature_names) == 0: # 如果测试集待考虑属性为空, 则构造叶子节点, 结束递归3 P% r2 x& S6 Z, d: w
node = dt_node(vote_most(train_set), is_leaf=True) # 这里让叶子结点的标签为概率上最可能的标签! m( S" n( O- y4 Z) y3 u% ^
if self.tree == None: # 如果根节点为空,则让该节点成为根节点( L- w2 Q6 ~+ R7 T; @3 G6 _& @
self.color_dir[vote_most(train_set)] = color_set[0]8 q5 w2 @" ~, g1 h
self.tree = node* O+ n2 ^) T9 W
IP卡
狗仔卡
发表于 2022-9-12 18:10
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
