决策树分为两部分,第一部分是创立决策树字典,第二部分是绘制决策树,可以看成是递归的练习,好多递归调用 /(ㄒ o ㄒ)/~~
2.1.1 选取最佳特征
首先要理解上面关于香农熵的概念,之后据此选取最佳特征作为决策节点,大体思路是利用了循环嵌套,对于每个特征比较各个特征值作用下的熵,看那个增益最大,找特征值时用了 set 相当于 MATLAB 里面的 unique
2.1.2 创建字典
递归开始爆发了!
神奇之处就是创建了个 keys 值为字典的字典的字典的字典……
看下式
myTree = {bestFeatLabel:{}}
即:
先将特征为字典的 keys
然后将特征的特征值作为新字典的特征,如果有不同的特征值就可能有多个新字典
- myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
递归啥时候结束呢,1 全部分类相同时就不需要在分类了,2 全部遍历完了所有的特征都考虑了,注意这个时候可能相同的特征不同的结果如四个特征值都为 1111 但是其分类却是 nononoyes 此时一般选取多的返回
主要用的函数有:extend append count 列表推导 sorted
2.2.1 整体思路
将字典利用 Python 的 annotate 功能绘制成树状图。
2.2.2 具体实施
因为绘制每一个树枝用的方法相近,所以可以使用递归调用,绘制每个决策节点和叶子节点。
- 利用 annatate 时需要的带求参数有坐标及注解内容
坐标的选取很有技巧性,看下图:
对于纵坐标比较好选,按照深度 d, 每次下沉 1/d。对于横坐标的选取利用以下公式:
来源: http://lib.csdn.net/article/machinelearning/42043