决策树（Decison Tree）—有监督学习方法、概率模型、生成模型、非线性模型、非参数化模型、批量学习

定义

ID3算法
输入：训练数据集（T= { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } \left\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\right\} {(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}），特征集A阀值$\epsilon$

输出：决策树T

(1)若D中所有实例属于同一类$C_k$,则T为单节点树，并将$C_k$作为该节点的类标记，返回T；

(2)若A=$\varnothing$，则T为单节点树，并将D中实例数最大的类$C_k$作为该节点的类标记，返回T；

(3)否则，需要计算A中各特征对D的信息增益，选择信息增益最大的特征$A_g$；

(4)如果$A_g$的信息增益小于阀值$\epsilon$，则置T为单节点树，并将D中实例数最大的类$C_k$作为该节点的类标记，返回T；

(5)否则，对$A_g$的每一可能值$a_i$,依$A_g=$