决策树原理，设计过程，实例.docx-资料库

qq_43165081-12689188-16359647484275764620.docx.pdf-第1页.png

第1页 / 共9页

qq_43165081-12689188-16359647484275764620.docx.pdf-第2页.png

第2页 / 共9页

qq_43165081-12689188-16359647484275764620.docx.pdf-第3页.png

第3页 / 共9页

qq_43165081-12689188-16359647484275764620.docx.pdf-第4页.png

第4页 / 共9页

qq_43165081-12689188-16359647484275764620.docx.pdf-第5页.png

第5页 / 共9页

qq_43165081-12689188-16359647484275764620.docx.pdf-第6页.png

第6页 / 共9页

qq_43165081-12689188-16359647484275764620.docx.pdf-第7页.png

第7页 / 共9页

qq_43165081-12689188-16359647484275764620.docx.pdf-第8页.png

第8页 / 共9页

决策树 1.1原理决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系，决策树是一种树形结构，树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。从根节点开始一步步走到叶子节点，从形式上比较像条件语句，从判断模块开始出发，通过分支可能到达终止模块或判断模块，这个分支的选择激活只能是“是”或“否”，所有的数据最终都会落到叶子节点。 1.2优缺点优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。缺点：可能会产生过度匹配问题适用数据类型：数值型和标称型 1.3组成根节点：第一个选择点非叶子节点于分支：中间过程叶子节点：最终的决策结果决策树的分类：主要取决于它目标变量的类型。离散性决策树：离散性决策树，其目标变量是离散的，如性别：男或女等；连续性决策树：连续性决策树，其目标变量是连续的，如工资、价格、年龄等；决策树相关概念：（1）根结点(Root Node)：它表示整个样本集合，并且该节点可以进一步划分成两个或多个子集。（2）拆分(Splitting)：表示将一个结点拆分成多个子集的过程。（3）决策结点(Decision Node)：当一个子结点进一步被拆分成多个子节点时，这个子节点就叫做决策结点。（4）叶子结点(Leaf/Terminal Node)：无法再拆分的结点被称为叶子结点。（5）剪枝(Pruning)：移除决策树中子结点的过程就叫做剪枝，跟拆分过程相反。（6）分支/子树(Branch/Sub-Tree)：一棵决策树的一部分就叫做分支或子树。

（7）父结点和子结点(Paren and Child Node)：一个结点被拆分成多个子节点，这个结点就叫做父节点；其拆分后的子结点也叫做子结点。 1.4决策树的构造过程决策树的构造过程一般分为3个部分，分别是特征选择、决策树生产和决策树裁剪。（1）特征选择：特征选择表示从众多的特征中选择一个特征作为当前节点分裂的标准，如何选择特征有不同的量化评估方法，从而衍生出不同的决策树，如ID3（通过信息增益选择特征）、 C4.5（通过信息增益比选择特征）、CART（通过Gini指数选择特征）等。目的（准则）：使用某特征对数据集划分之后，各数据子集的纯度要比划分钱的数据集 D的纯度高（也就是不确定性要比划分前数据集D的不确定性低）（2）决策树的生成根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止生长。这个过程实际上就是使用满足划分准则的特征不断的将数据集划分成纯度更高，不确定行更小的子集的过程。对于当前数据集的每一次划分，都希望根据某个特征划分之后的各个子集的纯度更高，不确定性更小。（3）决策树的裁剪决策树容易过拟合，一般需要剪枝来缩小树结构规模、缓解过拟合。创建分支的伪代码函数creatBranch（）：检测数据集中的每一个子项是否属于同一分类： If so return 类标签；

Else 寻找划分数据集的最好特征划分数据集创建分支节点 For 每个划分的子集调用函数creatBranch（）并增加返回结果到分支节点中 Return 分支节点 1.4特征划分应该使根节点就像老大，根节点下面的节点就像老二，老大应该比老二能更好的切分数据。选择一种衡量标准，来计算通过不同特征进行分支选择后的分类情况，找出来最好的就作为我们的根节点，以此类推确定所有的节点的划分标准。在这里使用ID3算法 1.5信息增益划分数据集之前之后信息发生的变化叫信息增益，计算每个特征值划分数据集获得信息增益，其最高的特征就是最好的选择。集合信息的度量方式叫香农熵，熵定义为信息的期望值。首先待分类的事务可能划分在多个分类中，则符号 ix 的信息定义为： ( I x i )   log ( p x i ) 2 熵就是所有类别所有可能值包含的信息期望值： H   n 1 i  ( p x i )log 2 ( p x i ) 条件熵：设有随机变量（X, Y），其联合概率分布为： ( , P X x Y  i  y i )  , p i ij  1,2,..., , n j  1,2,..., m 条件熵H(Y|X)表示在已知随机变量X的条件下，随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望： H Y X ( | )  n  i 1  p H Y X x i  ( | ) i 当熵和条件熵中的概率由数据估计得到时（如极大似然估计），所对应的熵与条件熵分别称为经验熵和经验条件熵。信息增益表示由于得知特征A的信息后儿时的数据集D的分类不确定性减少的程度，定义为：

Gain D A ,    H D H D A  |     即集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(H|A)之差。 1.6ID3算法输入：训练集，特征集，阈值。输出：决策树 1. 若训练集所有实例同属于一类，则决策树为单结点树，并将该类作为该节点的类标记，返回决策树。 2. 若特征集为空，则决策树为单结点树，并将训练集中实例最大的类作为该节点的类标记。 3. 以上两种情况都不是的话，计算特征集中特征对训练集的信息增益，选择信息增益最大的特征。 4. 如果这个信息增益最大的特征的信息增益小于阈值，则决策树为单节点树，并将训练集中实例数最大的类作为该节点的类标记，返回决策树。 5. 否则，对这个信息增益最大的特征的每一种可能值，依据该可能值将训练集分割为若干个非空子集，将子集中实例最大的类作为标记，构建子结点，由结点及其子树构成决策树，返回决策树。 6. 对第n个子节点，以子集为训练集，以除去涉及该子集的剩余特征集为特征集，递归调用1-5步，得到第n个子树，返回第n个决策树。计算给定数据集的香农熵说明：用创建的字典来记录类别标签出现的次数，以用来求出类别出现的概率，用这个概率计算香农熵。

按照给定特征划分数据集说明：创建一个新的列表，遍历整个数据集，发现符合要求的值，就把它加入到新的列表中，也就是说这是在以特征值进行划分数据集，将符合要求的数据集抽取出来。选择最好的划分方式说明：先判断有多少个特征属性，然后保存最初无序度量值，用于划分完之后的数据集

计算的熵值进行比较，第一个for循环遍历数据集中的所有特征，使用列表推导式创建i 新的列表，将数据集中的所有的特征值写入新列表中，然后使用set集合，可以得到列表中唯一元素值，遍历特征的唯一属性值，对每一个特征划分一次数据集，，然后计算数据集的熵值，并对所有唯一特征值得到熵求和，计算信息增益，比较所有特征中的信息增益，返回最好特征划分的索引值。创建决策树说明：依据特征值划分数据集，第一次划分后，数据被向下传递到树分支的下一个节点，这里还要再次划分数据，可以采用递归的办法，什么时候递归结束，也就是遍历完所有的数据集的属性，或者各个分支下的实例都有相同的分类，则得到一个叶子节点或者终止块。但是如何和决定叶子节点的分类呢，这里创建一个键值是唯一值的数据字典，存储每个类别标签出现的频率，最后用operato排序字典，并返回出现次数最多的分类名称。递归函数停止的第一个条件是所有的类标签相同，则返回该类标签，第二个条件是使用完所有的特征，返回次数出现最多的类别。返回值插入字典变量中，得到嵌套很多代表叶子节点信息的字典数据。如果关键字的值是类标签，则该节点是叶子节点，如果关键字的值是数据字典，则子节点是判断节点。使用matplotlib创建决策树

构造注解树说明：确定叶节点数目和树的层数。测试节点的数据类型是否为字典，用type（）函数判断，若子节点是字典类型，则该节点也是判断节点，递归调用getNumLeafs（）函数遍历整颗树，累计叶子节点的个数，并返回该值。第二个函数getTreeDepth（）函数计算遍历过程遇到判断节点的个数，该函数的终止条=条件是叶子节点，一旦达到叶子节点，则从递归调用返回，并将计算树的深度加一。使用决策树分类说明：plottree（）计算树的宽和高，totalw存储宽度，totald存储树的深度，存储决策树将标签字符串转换为索引，使用index方法查找当前列表中的第一个匹配firststr变量的元素，遍历整颗树，比较testvec变量中的值与树节点的值，如果达到叶子节点，则返回当前节点的分类标签。

实例：使用决策树预测隐形眼镜类型

资料库

决策树原理，设计过程，实例.docx

相关推荐

行业

热门标签

最新资料