<jupyter_start><jupyter_text>决策树的构造 决策树的优缺点- 优点：计算复杂度不高，输出结果易于理解，对中间值缺失不敏感，可以处理不相关特征数据。- 缺点：可能会产生过度匹配的问题。- 适用的数据类型：数值型和标称型。 在构造决策树时，需要解决的第一个问题就是，当前数据集上哪个特征在划分数据分类时起决定性作用。 创建分支的伪代码函数createBranch()如下所示：    检测数据集中每个子项是否属于同一分类：        if so            return 类标签        else            寻找划分数据集的最好特征            划分数据集            创建分支节点                for 每个划分的子集                    调用函数createBranch并增加返回结果到分支节点中            return 分支节点 决策树的一般流程(1) 收集数据：可以使用任何方法。  (2) 准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化。  (3) 分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。  (4) 训练算法：构造树的数据结构。  (5) 测试算法：使用经验树计算错误率。  (6) 使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。   本章采用的决策树算法是ID3算法，用它来划分数据集，该算法处理如何划分数据集，何时停止划分数据集。**每次划分数据集时我们只选取一个特征属性**。  信息增益 划分数据集的大原则是：**将无序的数据变得更加有序**。  在划分数据集之前之后信息发生的变化称为信息增益。对于每个特征而言，划分数据集之后获得信息增益最高的特征就是最好的选择。熵(entropy)定义为信息的期望值。如果待分类的事务可能划分在多个分类中，则符号$x_{i}$的信息定义为：  $$l(x_{i}) = -log_{2}p(x_{i})$$  其中，$p(x_{i})$是选择该分类的概率。信息熵是所有类别所有可能值包含的信息期望值，公式如下：$$H = - \sum_{i=1}^{n}p(x_{i})log_{2}p(x_{i})$$其中n是分类的数目。<jupyter_code>import trees
myDat, labels = trees.createDataSet()
myDat
labels
trees.calcShannonEnt(myDat)
myDat[0][-1] = 'maybe'
myDat
trees.calcShannonEnt(myDat)<jupyter_output><empty_output><jupyter_text>另一个度量集合无序程度的方法是**基尼不纯度(Gini impurity)** ,简单地说就是从一个数据集中随机选取子项，度量其被错误分类到其他分组里的概率。   划分数据集<jupyter_code>a = [1,2,3]
b = [4,5,6]
a.append(b)
a
a = [1,2,3]
a.extend(b)
a
reload(trees)
myDat, labels = trees.createDataSet()
myDat
trees.splitDataSet(myDat, 0, 0)
trees.splitDataSet(myDat, 0, 1)<jupyter_output><empty_output><jupyter_text>信息增益是熵的减少或者是数据无序度的减少。<jupyter_code>reload(trees)
myDat, labels = trees.createDataSet()
trees.chooseBestFeatureToSplit(myDat)
myDat<jupyter_output><empty_output><jupyter_text>递归构建决策树 **从数据集构造决策树的工作原理如下**：  得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分后，数据将被向下传递到树分支的下一个节点，在这个节点上，我们可以再次划分数据。**递归结束的条件是**：  程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的属性。第一个结束条件使得算法可以终止，我们甚至可以设置算法可以划分的最大分组数目。后续章节介绍的其他决策树算法如C4.5和CART算法，在运行时并不总是在每次划分分组时都会消耗特征。**由于特征数目并不是在每次划分数据分组时都减少，因此这些算法在实际使用时可能引起一定的问题**。类标签不唯一时采用**多数表决**的方法来确定该叶子节点的分类。<jupyter_code>reload(trees)
myDat, labels = trees.createDataSet()
myTree = trees.createTree(myDat, labels)
myTree<jupyter_output><empty_output><jupyter_text>在Python中使用Matplotlib注解绘制树形图 **Matplotlib库提供了一个注解工具annotations，可以在数据图形上添加文本注释。**  注解通常用于解释数据的内容。<jupyter_code>import treePlotter
reload(treePlotter)
treePlotter.createPlotOrigin()<jupyter_output>yes
create
create 1<jupyter_text>这里在使用matplotlib的annotation的时候出现了中文乱码，在代码中加入以下两行之后，添加了对应的字体就可以找到中文了。    from pylab import *      mpl.rcParams['font.sans-serif'] = ['SimHei']<jupyter_code>treePlotter.retrieveTree(1)
myTree = treePlotter.retrieveTree(0)
treePlotter.getNumLeafs(myTree)
treePlotter.getTreeDepth(myTree)<jupyter_output><empty_output><jupyter_text>绘制图形的x轴有效范围是0.0到1.0，y轴有效范围是0.0到1.0。<jupyter_code>treePlotter.createPlot(myTree)
myTree['no surfacing'][3] = 'maybe'
myTree
reload(treePlotter)
treePlotter.createPlot(myTree)<jupyter_output><empty_output><jupyter_text>测试和存储分类器<jupyter_code>myDat, labels = trees.createDataSet()
labels
myTree = treePlotter.retrieveTree(0)
myTree
trees.classify(myTree, labels, [1,0])
trees.classify(myTree, labels, [1,1])<jupyter_output><empty_output><jupyter_text>构造决策树非常耗时，为了节省计算时间，最好能够在每次执行分类时调用已经构造好的决策树。使用Python的pickle模块序列化对象，可以快速读取保存在磁盘上的对象。<jupyter_code>trees.storeTree(myTree, 'classifierStorage.txt')
trees.grabTree('classifierStorage.txt')<jupyter_output><empty_output><jupyter_text>训练好的决策树可以保存在磁盘上，这也是其优点之一，k-近邻算法就无法持久化分类器。  示例：使用决策树预测隐形眼镜类型<jupyter_code>fr = open('lenses.txt')
lenses = [inst.strip().split('\t') for inst in fr.readlines()]
lenses
lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']
lensesTree = trees.createTree(lenses, lensesLabels)
lensesTree
treePlotter.createPlot(lensesTree)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1273349118652986, 'fraction_numerical': 0.01157590107866351, 'mean_word_length': 9.893982808022923, 'pattern_counts': {'":': 0, '<': 40, '<?xml version=': 0, '>': 40, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '10', 'dir': 'jupyter-structured-clean-dedup', 'id': '157304', 'license': 'MIT', 'n_tokens_mistral': 2314, 'n_tokens_neox': 2548, 'n_words': 146, 'path': 'Ch03_Decision_Tree/trees.ipynb', 'repo_name': 'jhljx/MachineLearningInAction', 'size': '3801'}