1.ID3、C4.5、CART、SLIQ算法介绍

ID3 算法 ID3 算法以信息增益作为分裂属性的选择标准，选择具有最高信息增益的属性最为最佳分裂属性，这样熵减少的程度最大，使得当前划分后得到的数据集再次划分的时候所需要的信息最小。 举例说明 有房 婚姻状况 是否拖欠贷款 是 单身 否 否 已婚 否 否 单身 否 是 已婚 否 否 离异 是 否 已婚 否 是 离异 否 否 单身 是 否 已婚 否 否 单身 是 整个数据集D有3个是，7个否，其信息量（熵）为： I=Info（3,7）=-3/10*-7/10*=0.8813 假设现在来看有房情况这个属性，那么按照它划分后的信息增益计算如下： 有房 无房 是 0 3 否 3 4 =3/10*Info(0，3)+7/10*Info(3，4)=0.690 =I-=0.8813-0.690=0.1913 同理婚姻状况这个属性： 离异 已婚 单身 是 1 0 2 否 1 4 2 =2/10*Info(1,1)+4/10*Info(0,4)+4/10*Info(2,2)=0.6 =I-=0.8813-0.6=0.2213 >,故选取婚姻状况作为根节点进行分裂