问题 问答题 简答题

简述ID3算法的基本思想及其主算法和建树算法的基本步骤。

答案

参考答案:

首先找出最有判别力的因素,然后把数据分成多个子集,每个子集又选择最有判别力的因素进一步划分,一直进行到所有子集仅包含同一类型的数据为止。最后得到一棵决策树,可以用它来对新的样例进行分类。

主算法包括如下几步:

①从训练集中随机选择一个既含正例又含反例的子集(称为窗口);

②用“建树算法”对当前窗口形成一棵决策树;

③对训练集(窗口除外)中例子用所得决策树进行类别判定,找出错判的例子;

④若存在错判的例子,把它们插入窗口,重复步骤②,否则结束。

建树算法的具体步骤如下:

①对当前例子集合,计算各特征的互信息;

②选择互信息最大的特征Ak

③把在Ak处取值相同的例子归于同一子集,Ak取几个值就得几个子集;

④对既含正例又含反例的子集,递归调用建树算法;

⑤若子集仅含正例或反例,对应分枝标上P或N,返回调用处。

单项选择题
多项选择题