Python机器学习之决策树算法

一、决策树原理

决策树是用样本的属性作为结点，用属性的取值作为分支的树结构。
决策树的根结点是所有样本中信息量最大的属性。树的中间结点是该结点为根的子树所包含的样本子集中信息量最大的属性。决策树的叶结点是样本的类别值。决策树是一种知识表示形式，它是对所有样本数据的高度概括决策树能准确地识别所有样本的类别，也能有效地识别新样本的类别。 

决策树算法ID3的基本思想：

首先找出最有判别力的属性，把样例分成多个子集，每个子集又选择最有判别力的属性进行划分，一直进行到所有子集仅包含同一类型的数据为止。最后得到一棵决策树。

J.R.Quinlan的工作主要是引进了信息论中的信息增益，他将其称为信息增益（information gain），作为属性判别能力的度量，设计了构造决策树的递归算法。

举例子比较容易理解：

对于气候分类问题，属性为:
天气(A1) 取值为： 晴，多云，雨
气温(A2)  取值为： 冷 ，适中，热
湿度(A3)  取值为： 高 ，正常
风 (A4)  取值为： 有风， 无风

每个样例属于不同的类别，此例仅有两个类别，分别为P，N。P类和N类的样例分别称为正例和反例。将一些已知的正例和反例放在一起便得到训练集。
由ID3算法得出一棵正确分类训练集中每个样例的决策树，见下图。

决策树叶子为类别名，即P 或者N。其它结点由样例的属性组成，每个属性的不同取值对应一分枝。
若要对一样例分类，从树根开始进行测试，按属性的取值分枝向下进入下层结点，对该结点进行测试，过程一直进行到叶结点，样例被判为属于该叶结点所标记的类别。
现用图来判一个具体例子，
某天早晨气候描述为:
天气：多云
气温：冷
湿度：正常
风： 无风

它属于哪类气候呢?-------------从图中可判别该样例的类别为P类。 

ID3就是要从表的训练集构造图这样的决策树。实际上，能正确分类训练集的决策树不止一棵。Quinlan的ID3算法能得出结点最少的决策树。

ID3算法：

     1. 对当前例子集合，计算各属性的信息增益；
     2. 选择信息增益最大的属性Ak；
     3. 把在Ak处取值相同的例子归于同一子集，Ak取几个值就得几个子集；
     4.对既含正例又含反例的子集，递归调用建树算法；
     5. 若子集仅含正例或反例，对应分枝标上P或N，返回调用处。