本节内容：
决策树简介
在数据集中度量的一致性
使用递归构造决策树
使用Matplotlib绘制树形图
决策树一般用来处理分类问题，很多人都玩过猜数字的游戏：约定一个数字，当玩家对约定数字进行猜测的时候，游戏给出太大了 请往小猜或者猜小了往大的数字猜，知道最终锁定给出的约定数。在上一篇中介绍的K邻近算法能够完成很多分类任务，但是它最大的缺点就是无法给出数据的内在含义，决策树的主要优势就在于数据形式非常容易理解。垃圾邮件的判定就很好的应用到了决策树树算法。如图所示：
垃圾邮件判定预览
构造的决策树算法能够读取数据集合，决策时的一个重要任务是为了理解数据中所蕴含的知识信息，因决策树可以使用不熟悉的数据集合，并从中提取出一系列规则，这些机器根据数据集创建规则的过程，就是机器学习的过程。专家系统中经常使用决策树，而且决策树给出结果往往可以匹敌在当前领域具有几十年工作经验的人类专家。
1.决策树的构造
首要考虑的是，当前数据集上哪个特征在划分数据分类时起到决定性作用。为了找到决定性特征，划分最好的结果，我们必须评估每一个特征。完成测试之后，原始数据被划分为几个数据子集，这些数据子集会分布在第一个决策点的所有分支上。这是一个重复的过程。创建分支伪代码函数CreateBranch（）如下所示：
if so return //类标签else寻找划分数据集的最好特征划分数据集创建分支节点 for 每个划分的子集 调用函数CreateBranch并增加返回结果的分支节点中return 分支节点
1.1 信息增益
划分数据的最大原则是：将无序数据变得更加有序。可以使用多种划分数据集，但是每种各自的优缺点组织杂乱无章数据的一种方法就是使用信息论度量。在数据划分前后的信息改变称之为信息增益。在这里使用的事香浓熵的方法去计算信息增益。示例：
计算给定数据的香浓熵def calcShannonEnt(dataSet): numEntries = len(dataSet) labelCounts = {} for featVec in dataSet: #the the number of unique elements and their occurance currentLabel = featVec[-1] if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0 labelCounts[currentLabel] += 1 shannonEnt = 0.0 for key in labelCounts: prob = float(labelCounts[key])/numEntries shannonEnt -= prob * log(prob,2) #log base 2 return shannonEnt2 划分数据集
按照给定特征划分数据集def splitDataSet(dataSet, axis, value): retDataSet = [] for featVec in dataSet: if featVec[axis] == value: reducedFeatVec = featVec[:axis] #chop out axis used for splitting reducedFeatVec.extend(featVec[axis+1:]) retDataSet.append(reducedFeatVec) return retDataSet
补充：extend（）和append（）的区别
a=[1,2,3]b=[4,5,6]a.append(b)a=[1,2,3,[4,5,6]]a.extend(b)a=[1,2,3,4,5,6]
分享到:
閱讀更多 一兒口山石 的文章
