数据挖掘 决策树算法 ID3 通俗演绎

决策树是对数据进行分类，以此达到预测的目的。该决策树方法先根据训练集数据形成决策树，如果该树不能对所有对象给出正确的分类，那么选择一些例外加入到训练集数据中，重复该过程一直到形成正确的决策集。决策树代表着决策集的树形结构。

决策树由决策结点、分支和叶子组成。决策树中最上面的结点为根结点，每个分支是一个新的决策结点，或者是树的叶子。每个决策结点代表一个问题或决策，通常对应于待分类对象的属性。每一个叶子结点代表一种可能的分类结果。沿决策树从上到下遍历的过程中，在每个结点都会遇到一个测试，对每个结点上问题的不同的测试输出导致不同的分支，最后会到达一个叶子结点，这个过程就是利用决策树进行分类的过程，利用若干个变量来判断所属的类别。

本文是我在 某保险公司和某运营商数据挖掘导论的讲义，感兴趣可以留下email索要PPT。

背景:

XXX 保险公司使用电话推销车险。 为了节约呼叫成本，通过数据挖掘技术对客户进行分类， 优先拨打有购买可能性的电话名单。


算法（ID3算法）

输入：训练数据集D，特征集A，阈值? ?
输出：决策树T
(1) 若D中所有实例属于同一类C k  Ck ，则T为单结点树，并将类C k  Ck 作为该结点的类标记，返回T；
(2) 若A=? A=? ，则T为单结点树，并将D中实例数最大的类C k  Ck 作为该结点的类标记，返回T；
(3) 否则，计算A中各特征对D的信息增益，选择信息增益最大的特征A g  Ag ;
(4) 如果A g  Ag 的信息增益小于阈值? ? ，则置T为单结点树，并将D中实例数最大的类C k  Ck 作为该结点的类标记，返回T；
(5) 否则，对A g  Ag 的每一个可能值a i  ai ，依A g =a i  Ag=ai 将D分割为若干非空子集D i  Di ，将D i  Di 中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T；
(6) 对第i个子子结点，以D i  Di 为训练集，以 A?{A g } A?{Ag} 为特征集，递归地调用步(1)~(5)，得到子树T i  Ti ，返回T i  Ti ；