决策树（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阀值 ε \varepsilon ε
输出：决策树T
(1)若D中所有实例属于同一类 C k C_k Ck,则T为单节点树，并将 C k C_k Ck作为该节点的类标记，返回T；
(2)若A= ∅ \varnothing ∅，则T为单节点树，并将D中实例数最大的类 C k C_k Ck作为该节点的类标记，返回T；
(3)否则，需要计算A中各特征对D的信息增益，选择信息增益最大的特征 A g A_g Ag；
(4)如果 A g A_g Ag的信息增益小于阀值 ε \varepsilon ε，则置T为单节点树，并将D中实例数最大的类 C k C_k Ck作为该节点的类标记，返回T；
(5)否则，对 A g A_g Ag的每一可能值 a i a_i ai,依 A g = a i A_g=a_i Ag=