R语言-决策树算法
决策树算法 决策树定义 首先，我们来谈谈什么是决策树。我们还是以鸢尾花为例子来说明这个问题。 观察上图，我们判决鸢尾花的思考过程可以这么来描述：花瓣的长度小于 2.4cm的是setosa(图中绿色的分类)，长度大于1cm的呢?我们通过宽度来判别，宽度小于1.8cm的是versicolor(图中红色的分类)，其余的就是 virginica(图中黑色的分类) 我们用图形来形象的展示我们的思考过程便得到了这么一棵决策树： 这种从数据产生决策树的机器学习技术叫做决策树学习, 通俗点说就是决策树，说白了，这是一种依托于分类、训练上的预测树，根据已知预测、归类未来。 前面我们介绍的k-近邻算法也可以完成很多分类任务，但是他的缺点就是含义不清，说不清数据的内在逻辑，而决策树则很好地解决了这个问题，他十分好理解。从存储的角度来说，决策树解放了存储训练集的空间，毕竟与一棵树的存储空间相比，训练集的存储需求空间太大了。 决策树的构建 一、KD3的想法与实现 下面我们就要来解决一个很重要的问题：如何构造一棵决策树?这涉及十分有趣的细节。 先说说构造的基本步骤，一般来说，决策树的构造主要由两个阶段组成:第一阶段，生成树阶段。选取部分受训数据建立决策树，决策树是按广度优先建立直到每个叶节点包括相同的类标记为止。第二阶段，决策树修剪阶段。用剩余数据检验决策树，如果所建立的决策树不能正确回答所研究的问题，我们要对决策树进行修剪直到建立一棵正确的决策树。这样在决策树每个内部节点处进行属性值的比较，在叶节点得到结论。从根节点到叶节点的一条路径就对应着一条规则，整棵决策树就对应着一组表达式规则。 问题：我们如何确定起决定作用的划分变量。 我还是用鸢尾花的例子来说这个问题思考的必要性。使用不同的思考方式，我们不难发现下面的决策树也是可以把鸢尾花分成3类的。 为了找到决定性特征，划分出最佳结果，我们必须认真评估每个特征。通常划分的办法为信息增益和基尼不纯指数，对应的算法为C4.5和CART。 关于信息增益和熵的定义烦请参阅百度百科，这里不再赘述。 直接给出计算熵与信息增益的R代码：
决策树示例 %************************************************************** %* mex interface to Andy Liaw et al.'s C code (used in R package randomForest) %* Added by Abhishek Jaiantilal ( abhishek.jaiantilal@https://www.doczj.com/doc/ac7428969.html, ) %* License: GPLv2 %* Version: 0.02 % % Calls Regression Random Forest % A wrapper matlab file that calls the mex file % This does training given the data and labels % Documentation copied from R-packages pdf % https://www.doczj.com/doc/ac7428969.html,/web/packages/randomForest/randomForest.pdf % Tutorial on getting this working in tutorial_ClassRF.m %%************************************************************** % function model = classRF_train(X,Y,ntree,mtry, extra_options) % %___Options % requires 2 arguments and the rest 3 are optional % X: data matrix % Y: target values % ntree (optional): number of trees (default is 500). also if set to 0 % will default to 500 % mtry (default is floor(sqrt(size(X,2))) D=number of features in X). also if set to 0 % will default to 500 % % % Note: TRUE = 1 and FALSE = 0 below % extra_options represent a structure containing various misc. options to % control the RF % extra_options.replace = 0 or 1 (default is 1) sampling with or without % replacement % extra_options.strata = (not Implemented) % extra_options.sampsize = Size(s) of sample to draw. For classification, % if sampsize is a vector of the length the number of strata, then sampling is stratified by strata, % and the elements of sampsize indicate the numbers to be drawn from the strata. I don't yet know how this works. % extra_options.nodesize = Minimum size of terminal nodes. Setting this number larger causes
决策树 1. 原理 1.1 模型简介 决策树是一种基本的回归和分类算法。在分类问题中，可以认为是一系列if-then 规则的几何。决策树学通常包括三个步骤：特征选择，决策树的生成，决策树的修剪。 定义：决策树由结点和有向边组成，内部节点表示一个特征和属性，叶子结点表示一个类。 性质：决策树路径（或者对应的if-then 规则）具有互斥且完备性：每一个实例都被一条路径或规则所覆盖，而且只被这条路径或规则所覆盖。 决策树学习：能够正确对数据集进行分类的决策树可能有多个，也可能一个也没有，我们的目的是找到一个与训练数据集矛盾较小的，同时具有很好泛化能力的决策树。 特征选择：一种是在决策树学习开始的时候，对特征进行选择，只留下对训练数据有足够分类能力的特征，一种是在学习过程中对训练数据分割成自己的时候，选择最优的特征进行分割。 决策树生成：一般这是一个递归的规程。 决策树的剪枝：提高决策树的泛化能力。 1.2 特征选择 特征选择的准则一般是：信息增益和信息增益比 1.2.1 信息增益 a.信息增益：信息增益大的特征具有更强的分类能力，即选择信息增益值大的特征作为最优特征。 b.信息熵：表示变量的不确定性（在得知特征X 的信息时，使得Y 的信息不确定性减少的程度），熵越大，变量的不确定性越大。设X 是一个取有限值的离散型随机变量，其概率分布为： ()i i p X x p == 则随机变量X 的熵定义为：
1()log n i i i H X p p ==-∑ 注：若p i =0,定义0log 00=。其中若对数以2为底，熵的单位称为比特，若以e 为底，单位称为纳特。 c.条件熵：随机变量X 在给定条件下随机变量Y 的条件熵H （Y|X ）表示：X 给定条件下Y 的条件概率分布的熵 关于X 的数学期望： 1(|)(|)n i i i H Y X p H Y X x ===∑ 其中，()i i p X x p ==。 当熵和条件熵有数据估计（特别是极大似然估计）得到时，被分别称为经验熵和经验条件熵。 信息增益： 特征A 对训练数据集D 的信息增益g(D|A)定义为： (,)()(|)g D A H D H D A =- 其中，()H D 为集合D 的经验熵，(|)H D A 为特征A 给定条件下D 的经验条件熵。 d.信息增益的计算方法。 设： 训练数据集D ，个数为|D|。 K 个类，分别为C k..每个类内个数|C k | 根据特征A ，能够将训练集划分为n 个子集：D 1，D 2，…D n 。|D I |为该子集的样本个数。 子集D i 中属于类C k 的个数|D ik |。 则计算信息增益的公式为： 数据集D 的信息熵： i 1||||()log()||||k K K C C H D D D ==-∑ 特征A 对数据集D 的经验条件熵： 111||||||||(|)()log()||||||||n n K i i ik ik i i i k i i D D D D H D A H D D D D D =====∑∑∑ 注：此公式意义：在特征A 作用下，将数据集D 分为多个D i 。这时关于D 的熵等于关于D i 熵的均值。 计算信息增益。
rpart包的rpart函数 Iris数据集 library(rpart) #加载rpart包 head(iris) #看看iris数据集里有哪些变量 iris以鸢尾花的特征作为数据来源，数据集包含150个数据，分为3类，每类50个数据，每个数据包含4个属性分别是花萼长度、花萼宽带、花瓣长度、花瓣宽度 用gini度量纯度 =rpart(Species~.,data=iris,method="class",parms=list(split="gini")) # rpart(formula, data, method, parms, ...)得到决策树对象，其中 （1）formula是回归方程的形式，y~x1+x2+…，iris一共有5个变量，因变量是Species,自变量是其余四个变量，所以formula可以省略为Species~. （2）data是所要学习的数据集 （3）method根据因变量的数据类型有如下几种选择：anova（连续型），poisson（计数型），class（离散型），exp（生存型），因为我们的因变量是花的种类，属于离散型，所以method选择class （4）parms可以设置纯度的度量方法，有gini（默认）和information（信息增益）两种。 plot, uniform=T, branch=0, margin=,main="Classification Tree\nIris Species by Petal and Sepal Length") #plot的对象是由rpart得到的决策树对象，可以把这课决策树画出来，其中 （1） uniform可取T，F两个值，T表示图形在空间上均匀分配 （2） branch刻画分支的形状，取值在0和1之间，branch=0是倒v型，branch=1是直角型，而当branch属于（0,1）时是梯形 Classification T ree Iris Species by Petal and Sepal Length branch=0.5 | （3）margin刻画图的大小，margin越大，决策树越小，上述三幅图的margin=，而当margin=1时，决策树变小了
项目6 决策树和决策规则 6.1 实验目的 （1）掌握使用决策树进行分类决策的操作方法，并学会对结果进行解释、提取合理的分类规则； （2）理解决策树模型相对于其他预测模型（如神经网络）的优势所在，如它的决策模型可以为自然语言构成的规则或为逻辑陈述； （3）了解较为流行的决策树模型的不同特征，如CHAID和CART； （4）了解决策树模型中的替代规则对于处理缺失值的优势，掌握操作方法； （5）学会使用决策树模型进行变量选择。 6.2 实验原理 数据库内容丰富，蕴藏大量信息，可以用来作出智能的决策。分类和预测是数据分析的两种形式，可以用来提取描述重要数据类的模型或预测未来的数据趋势。分类是预测分类标号，而预测建立连续值函数模型。在本章中，我们将学习利用决策树进行数据分类的技术。 决策树是一个类似于流程图的树结构，其中每个内部节点表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶节点代表类或类分布。树的最顶层节点是根节点。有些决策树算法只产生二叉树，而另一些决策树算法可以产生非二叉树。 对于一个需要进行分类的数据，我们可以利用该数据的各个属性的值，在决策树的包括根节点在内的节点上对相应的数据的属性进行测试，这样就形成了一条由顶到底的或从根节点到某个叶子节点的路径。该数据所到达的叶子节点给出了该数据所应归属的类。 决策树容易转换成为分类规则。我们可以根据需要分类的数据在决策树中所经过的所有可能的路径得到一组分类规则，并利用分类规则对数据进行分类。 决策树的构造不需要任何领域知识或参数设置，因此适合于探测式知识发现。决策树可以处理高维数据。获取的知识用树的形式表示是直观的，并且容易理解。 决策树建立时，许多分枝可能反映的是训练数据中的噪声或离群点。树剪枝试图识别并剪去这种分枝，以提高对未知数据分类的准确性。 6.2.1 决策树归纳 目前比较有名的决策树算法大概有上百种，其中，最有影响的当属ID3、C4.5、C5.0，
决策树决策树研发二部
目录 1. 算法介绍 (1) 1.1. 分支节点选取 (1) 1.2. 构建树 (3) 1.3. 剪枝 (10) 2. sk-learn 中的使用 (12) 3. sk-learn中源码分析 (13)
1. 算法介绍 决策树算法是机器学习中的经典算法之一，既可以作为分类算法，也可以作 为回归算法。决策树算法又被发展出很多不同的版本，按照时间上分，目前主要包括，ID3、C4.5和CART版本算法。其中ID3版本的决策树算法是最早出现的，可以用来做分类算法。C4.5是针对ID3的不足出现的优化版本，也用来做分类。CART也是针对 ID3优化出现的，既可以做分类，可以做回归。 决策树算法的本质其实很类似我们的if-elseif-else语句，通过条件作为分支依据，最终的数学模型就是一颗树。不过在决策树算法中我们需要重点考虑选取分支条件的理由，以及谁先判断谁后判断，包括最后对过拟合的处理，也就是剪枝。这是我们之前写if语句时不会考虑的问题。 决策树算法主要分为以下3个步骤： 1. 分支节点选取 2. 构建树 3. 剪枝 1.1. 分支节点选取 分支节点选取，也就是寻找分支节点的最优解。既然要寻找最优，那么必须要有一个衡量标准，也就是需要量化这个优劣性。常用的衡量指标有熵和基尼系数。 熵：熵用来表示信息的混乱程度，值越大表示越混乱，包含的信息量也就越多。比如，A班有10个男生1个女生，B班有5个男生5个女生，那么B班的熵值就比A班大，也就是B班信息越混乱。 Entropy = -V p ” 基尼系数：同上，也可以作为信息混乱程度的衡量指标。 Gini = 1 - p： l-L
机器学习CART算法 导读：人工智能机器学习有关算法内容，今天我们重点探讨一下CART算法。继上两篇决策树算法之ID3算法和ID3的改进算法－C4．5算法后，本文继续讨论另一种二分决策树算法－CART算法。我们知道十大机器学习中决策树算法占有两席位置，即C4．5算法和CART算法，可见CART算法的重要性。下面重点介绍CART算法。 不同于ID3与C4．5，CART为一种二分决策树，是满二叉树。CART算法由Breiman等人在1984 年提出，它采用与传统统计学完全不同的方式构建预测准则，它是以二叉树的形式给出，易于理解、使用和解释。由CART 模型构建的预测树在很多情况下比常用的统计方法构建的代数学预测准则更加准确，且数据越复杂、变量越多，算法的优越性就越显著。 CART算法既可用于分类也可用于回归。CART算法被称为数据挖掘领域内里程碑式的算法。 CART算法概念：CART（ClassificaTIon andRegression Tree）分类回归树是一种决策树构建算法。CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值为是和否，左分支是取值为是的分支，右分支是取值为否的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。 CART算法既可以处理离散型问题，也可以处理连续型问题。这种算法在处理连续型问题时，主要通过使用二元切分来处理连续型变量，即特征值大于某个给定的值就走左子树，或者就走右子树。 CART算法组成：1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；自上而下从根开始建立节点，在每个节点处要选择一个最好（不同算法使用不同指标来定义＂最好＂）的属性来分裂，使得子节点中的训练数据集尽量的纯。
计算题 一 1.为生产甲产品，小行星公司设计了两个基本方案：一是建大工厂，二是建小工厂。如果销路好，3年以后考虑扩建。建大工厂需投资300万元，建小工厂需投资160万元，3年后扩建另需投资140万元。扩建后可使用7年，其年度损益值与大工厂相同。每种自然状态的预测概率及年度损益值如下表： 前 3 年 后 7 年 根据上述资料试用决策树法做出决策。 四、计算题（15分）
答：建大厂收益=581-300=281 建小厂收益=447-160=287 所以应选择建小厂方案。 二 山姆公司的生产设备已经落后，需要马上更新。公司有人认为，目前产品销路增长，应在更新设备的同时扩大再生产的规模。但也有人认为，市场形势尚难判断，不如先更新设备，3年后再根据形势变化考虑扩大再生产的规模问题。这样，该公司就面临着两个决策方案。决策分析的有关资料如下： A、现在更新设备，需投资35万元， 3年后扩大生产规模，另需投资40万元。 B、现在更新设备的同时扩大再生产的规模，需投资60万元。 C、现在只更新设备，在销售情况良好时，每年可获利6万元；在销售情况不好时，每年可获利4、5万元。 D、如果现在更新与扩产同时进行，若销售情况好，前3年每年可获利12万元；后7年每年可获利15万元；若销售情况不好，每年只获利3万元。 E、每种自然状态的预测概率如下表
前 3 年 后 7 年 根据上述资料试用决策树法做出决策。 答案：
结点7收益值=0、85×7 × 15+0、15 ×7 ×3=92、4（万元）
结点8收益值=0、85×7 ×6+0、15 ×7 ×4、5=40、4（万元） 结点9收益值=0、1×7 × 15+0、9 ×7 ×3=29、4（万元） 结点10收益值=0、1×7 × 6+0、9 ×7 ×4、5=32、6（万元） 结点1收益值=0、7×[52、4+（3 × 6）]+0、3 ×[32、6+（3 × 4、5）]=63、1（万元） 结点2收益值=0、7×[92、4+（3 × 12）]+0、3 ×[29、4+（3 × 3）]=101、4（万元） 答：用决策树法进行决策应选择更新扩产方案，可获得收益41、4万元。 三 某厂准备生产Y种新产品，对未来的销售前景预测不准，可能出现高需求、中需求、低需求三种自然状态。组织有三个方案可供选择：新建一个车间；扩建原有车间；对原有车间的生产线进行局部改造。三个方案在5年内的经济效益见下表（单位：万元）： 0 1 请分别用悲观决策法、乐观决策法、最大最小后悔决策法做出决策。 悲观决策法指当存在几种自然状态的情况下，宁可把情况估计得坏一 些，从中选择一个收益最大的方案，决策稳妥可靠。按此准则，在低需求的自然状态下，5年内新建方案亏损160万，扩建方案保本，改造方案获利80万。改造方案最佳。 乐观决策法： 新建E=（0、7X600）+（1-0、7）X（-160）=372（万元） 扩建E=（0、7X400）+ （1-0、7）X0=280 （万元） 改造E=（0、7X300）+ （1-0、7）X80=234 （万元） 比较结果，新建方案最佳。 最大最小后悔决策，是用后悔值计算表进行计算的： 后悔值计算表
3.1 分类与决策树概述 3.1.1 分类与预测 分类是一种应用非常广泛的数据挖掘技术，应用的例子也很多。例如，根据信用卡支付历史记录，来判断具备哪些特征的用户往往具有良好的信用；根据某种病症的诊断记录，来分析哪些药物组合可以带来良好的治疗效果。这些过程的一个共同特点是：根据数据的某些属性，来估计一个特定属性的值。例如在信用分析案例中，根据用户的“年龄”、“性别”、“收入水平”、“职业”等属性的值，来估计该用户“信用度”属性的值应该取“好”还是“差”，在这个例子中，所研究的属性“信用度”是一个离散属性，它的取值是一个类别值，这种问题在数据挖掘中被称为分类。 还有一种问题，例如根据股市交易的历史数据估计下一个交易日的大盘指数，这里所研究的属性“大盘指数”是一个连续属性，它的取值是一个实数。那么这种问题在数据挖掘中被称为预测。 总之，当估计的属性值是离散值时，这就是分类；当估计的属性值是连续值时，这就是预测。
3.1.2 决策树的基本原理 1.构建决策树 通过一个实际的例子，来了解一些与决策树有关的基本概念。 表3-1是一个数据库表，记载着某银行的客户信用记录，属性包括“姓名”、“年龄”、“职业”、“月薪”、......、“信用等级”，每一行是一个客户样本，每一列是一个属性（字段）。这里把这个表记做数据集D。 银行需要解决的问题是，根据数据集D，建立一个信用等级分析模型，并根据这个模型，产生一系列规则。当银行在未来的某个时刻收到某个客户的贷款申请时，依据这些规则，可以根据该客户的年龄、职业、月薪等属性，来预测其信用等级，以确定是否提供贷
款给该用户。这里的信用等级分析模型，就可以是一棵决策树。 在这个案例中，研究的重点是“信用等级”这个属性。给定一个信用等级未知的客户，要根据他/她的其他属性来估计“信用等级”的值是“优”、“良”还是“差”，也就是说，要把这客户划分到信用等级为“优”、“良”、“差”这3个类别的某一类别中去。这里把“信用等级”这个属性称为“类标号属性”。数据集D中“信用等级”属性的全部取值就构成了类别集合：Class={“优”，“良”，“差”}。 在决策树方法中，有两个基本的步骤。其一是构建决策树，其二是将决策树应用于数据库。大多数研究都集中在如何有效地构建决策树，而应用则相对比较简单。构建决策树算法比较多，在Clementine中提供了4种算法，包括C&RT、CHAID、QUEST和C5.0。采用其中的某种算法，输入训练数据集，就可以构造出一棵类似于图3.1所示的决策树。
机器学习--决策树(ID3)算法及案例 1基本原理 决策树是一个预测模型。它代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，每个分支路径代表某个可能的属性值，每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。一般情况下，决策树由决策结点、分支路径和叶结点组成。在选择哪个属性作为结点的时候，采用信息论原理，计算信息增益，获得最大信息增益的属性就是最好的选择。信息增益是指原有数据集的熵减去按某个属性分类后数据集的熵所得的差值。然后采用递归的原则处理数据集，并得到了我们需要的决策树。 2算法流程 检测数据集中的每个子项是否属于同一分类： If 是，则返回类别标签； Else 计算信息增益，寻找划分数据集的最好特征 划分数据数据集 创建分支节点（叶结点或决策结点） for 每个划分的子集 递归调用，并增加返回结果到分支节点中
return 分支结点 算法的基本思想可以概括为： 1）树以代表训练样本的根结点开始。 2）如果样本都在同一个类．则该结点成为树叶，并记录该类。 3）否则，算法选择最有分类能力的属性作为决策树的当前结点． 4 ）根据当前决策结点属性取值的不同，将训练样本根据该属性的值分为若干子集，每个取值形成一个分枝，有几个取值形成几个分枝。匀针对上一步得到的一个子集，重复进行先前步骤，递归形成每个划分样本上的决策树。一旦一个属性只出现在一个结点上，就不必在该结点的任何后代考虑它，直接标记类别。 5）递归划分步骤仅当下列条件之一成立时停止： ①给定结点的所有样本属于同一类。 ②没有剩余属性可以用来进一步划分样本．在这种情况下．使用多数表决，将给定的结点转换成树叶，并以样本中元组个数最多的类别作为类别标记，同时也可以存放该结点样本的类别分布[这个主要可以用来剪枝]。 ③如果某一分枝tc，没有满足该分支中已有分类的样本，则以样本的多数类生成叶子节点。 算法中2)步所指的最优分类能力的属性。这个属性的选择是本算法种的关键点，分裂属性的选择直接关系到此算法的优劣。 一般来说可以用比较信息增益和信息增益率的方式来进行。 其中信息增益的概念又会牵扯出熵的概念。熵的概念是香农在研究信息量方面的提出的。它的计算公式是： Info(D)=-p1log(p1)/log(2.0)-p2log(p2)/log(2.0)-p3log(p3)/log(2.0)+...-pNlog(pN) /log(2.0) (其中N表示所有的不同类别)
决策树研发二部
目录 1. 算法介绍 (1) 1.1.分支节点选取 (1) 1.2.构建树 (3) 1.3.剪枝 (10) 2. sk-learn中的使用 (12) 3. sk-learn中源码分析 (13)
1.算法介绍 决策树算法是机器学习中的经典算法之一，既可以作为分类算法，也可以作为回归算法。决策树算法又被发展出很多不同的版本，按照时间上分，目前主要包括，ID3、C4.5和CART版本算法。其中ID3版本的决策树算法是最早出现的，可以用来做分类算法。C4.5是针对ID3的不足出现的优化版本，也用来做分类。CART也是针对ID3优化出现的，既可以做分类，可以做回归。 决策树算法的本质其实很类似我们的if-elseif-else语句，通过条件作为分支依据，最终的数学模型就是一颗树。不过在决策树算法中我们需要重点考虑选取分支条件的理由，以及谁先判断谁后判断，包括最后对过拟合的处理，也就是剪枝。这是我们之前写if语句时不会考虑的问题。 决策树算法主要分为以下3个步骤： 1.分支节点选取 2.构建树 3.剪枝 1.1.分支节点选取 分支节点选取，也就是寻找分支节点的最优解。既然要寻找最优，那么必须要有一个衡量标准，也就是需要量化这个优劣性。常用的衡量指标有熵和基尼系数。 熵：熵用来表示信息的混乱程度，值越大表示越混乱，包含的信息量也就越多。比如，A班有10个男生1个女生，B班有5个男生5个女生，那么B班的熵值就比A班大，也就是B班信息越混乱。 基尼系数：同上，也可以作为信息混乱程度的衡量指标。
有了量化指标后，就可以衡量使用某个分支条件前后，信息混乱程度的收敛效果了。使用分支前的混乱程度，减去分支后的混乱程度，结果越大，表示效果越好。 #计算熵值 def entropy(dataSet): tNum = len(dataSet) print(tNum) #用来保存标签对应的个数的，比如,男：6，女：5 labels = {} for node in dataSet: curL = node[-1] #获取标签 if curL not in labels.keys(): labels[curL] = 0 #如果没有记录过该种标签，就记录并初始化为0 labels[curL] += 1 #将标签记录个数加1 #此时labels中保存了所有标签和对应的个数 res = 0 #计算公式为-p*logp，p为标签出现概率 for node in labels: p = float(labels[node]) / tNum res -= p * log(p, 2) return res #计算基尼系数 def gini(dataSet): tNum = len(dataSet) print(tNum) # 用来保存标签对应的个数的，比如,男：6，女：5 labels = {} for node in dataSet: curL = node[-1] # 获取标签 if curL not in labels.keys(): labels[curL] = 0 # 如果没有记录过该种标签，就记录并初始化为0 labels[curL] += 1 # 将标签记录个数加1 # 此时labels中保存了所有标签和对应的个数 res = 1
数据挖掘算法---CART 1. 前言 分类与回归树（Classification and Regression Trees, CART）是由四人帮Leo Breiman, Jerome Friedman, Richard Olshen与Charles Stone 于1984年提出，既可用于分类也可用于回归。本文将主要介绍用于分类的CART。CART被称为数据挖掘领域内里程碑式的算法。 不同于C4.5，CART本质是对特征空间进行二元划分（即CART生成的决策树是一棵二叉树），并能够对标量属性（nominal attribute）与连续属性（continuous attribute）进行分裂。 2. CART生成 前一篇提到过决策树生成涉及到两个问题：如何选择最优特征属性进行分裂，以及停止分裂的条件是什么。 特征选择 CART对特征属性进行二元分裂。特别地，当特征属性为标量或连续时，可选择如下方式分裂： An instance goes left if CONDITION, and goes right otherwise 即样本记录满足CONDITION则分裂给左子树，否则则分裂给右子树。 标量属性 进行分裂的CONDITION可置为不等于属性的某值；比如，标量属性Car Type取值空间为{Sports, Family, Luxury}，二元分裂与多路分裂如下： 连续属性 CONDITION可置为不大于ε；比如，连续属性Annual Income，ε取属性相邻值的平均值，其二元分裂结果如下： 接下来，需要解决的问题：应该选择哪种特征属性及定义CONDITION，才能分类效果比较好。CART采用Gini指数来度量分裂时的不纯度，之所以采用Gini指数，是因为较于熵而言其计算速度更快一些。对决策树的节点t，Gini指数计算公式如下： Gini(t)=1?∑k [p(c k |t)] 2 (1) Gini指数即为1与类别c k的概率平方之和的差值，反映了样本集合的不确定性程度。Gini指数越大，样本集合的不确定性程度越高。分类学习过程的本质是样本不确定性程度的减少（即熵减过程），故应选择最小Gini指数的特征分裂。父节点对应的样本集合为D，CART选择特征A 分裂为两个子节点，对应集合为D L与D R；分裂后的Gini指数定义如下： G(D,A)=|D L ||D| Gini(D L )+|D R ||D| Gini(D R ) (2) 其中，|?|表示样本集合的记录数量。
决策树算法 决策树定义 首先，我们来谈谈什么是决策树。我们还是以鸢尾花为例子来说明这个问题。 观察上图，我们判决鸢尾花的思考过程可以这么来描述：花瓣的长度小于2.4cm的是setosa(图中绿色的分类)，长度大于1cm的呢?我们通过宽度来判别，宽度小于1.8cm的是versicolor(图中红色的分类)，其余的就是virginica(图中黑色的分类) 我们用图形来形象的展示我们的思考过程便得到了这么一棵决策树： 这种从数据产生决策树的机器学习技术叫做决策树学习, 通俗点说就是决策树，说白了，这是一种依托于分类、训练上的预测树，根据已知预测、归类未来。 前面我们介绍的k-近邻算法也可以完成很多分类任务，但是他的缺点就是含义不清，说不清数据的在逻辑，而决策树则很好地解决了这个问题，他十分好理解。从存储的角度来说，决策树解放了存储训练集的空间，毕竟与一棵树的存储空间相比，训练集的存储需求空间太大了。 决策树的构建 一、KD3的想法与实现 下面我们就要来解决一个很重要的问题：如何构造一棵决策树?这涉及十分有趣的细节。 先说说构造的基本步骤，一般来说，决策树的构造主要由两个阶段组成:第一阶段，生成树阶段。选取部分受训数据建立决策树，决策树是按广度优先建立直到每个叶节点包括相同的类标记为止。第二阶段，决策树修剪阶段。用剩余数据检验决策树，如果所建立的决策树不能正确回答所研究的问题，我们要对决策树进行修剪直到建立一棵正确的决策树。这样在决策树每个部节点处进行属性值的比较，在叶节点得到结论。从根节点到叶节点的一条路径就对应着一条规则，整棵决策树就对应着一组表达式规则。 问题：我们如何确定起决定作用的划分变量。 我还是用鸢尾花的例子来说这个问题思考的必要性。使用不同的思考方式，我们不难发现下面的决策树也是可以把鸢尾花分成3类的。 为了找到决定性特征，划分出最佳结果，我们必须认真评估每个特征。通常划分的办法为信息增益和基尼不纯指数，对应的算法为C4.5和CART。 关于信息增益和熵的定义烦请参阅百度百科，这里不再赘述。 直接给出计算熵与信息增益的R代码： 1、计算给定数据集的熵 calcent<-function(data){ nument<-length(data[,1])