1.决策树基本流程

概念：基于树结构来进行决策，体现人类在面临决策问题时一种很自然的处理机制

具备条件：

每个非叶节点表示一个特征属性测试

每个分支代表这个特征属性在某个值域上的输出

每个叶子节点存放一个类别

每个节点包含的样本集合通过属性测试被划分到子节点中，根节点包含样本全集

基本算法：

输入： 训练集D=\{(x_1,y_1),(x_2,y_2),\cdot, (x_m,y_m)\}D={(x1,y1),(x2,y2),⋅,(xm,ym)};

  属性集A={a_1,a_2,\cdot,a_d}A=a1,a2,⋅,ad

过程： 函数TreeGenerate(DD,AA)

(1) 生成结点node

(2) if DD中样本全属于同一类别CC then

(3)  将node标记为CC类叶节点; return

(4) end if

(5) if A=\emptysetA=∅ OR DD中样本在AA上取值相同 then

(6)  将node标记为叶结点，其类别标记为DD中样本数最多的类；return

(7) end if

(8) 从AA中选择最优化分属性a_*a∗;

(9) for a_*a∗的每一个值a_*^va∗v do

(10)  为node生成一个分支；令D_vDv表示DD中在a_*a∗上取值为a_*^va∗v的样本子集;

(11)   if D_vDv为空 then

(12)    将分支结点标记为叶结点，其类别标记为DD中样本最多的类; return

(13)  else

(14)    以TreeGenerate(D_vDv, A \backslash \{ a_* \}A\{a∗})为分支结点

(15)  end if

(16) end for

输出： 以node为根结点的一棵决策树

决策树构造以下为参考链接导图：https://zhuanlan.zhihu.com/p/106594756

当前结点包含的样本全部属于同一类，直接将该结点标记为叶结点，其类别设置该类

当属性集为空，或所有样本在所有属性上取值相同，无法进行划分，将该结点标记为叶结点，其类别设置为其父结点所含样本最多的类别

当前结点包含的样本集合为空，不能划分，将该结点标记为叶结点，其类别设置为其父结点所含样本最多的类别