新决策树例子
rpart包的rpart函数
Iris数据集
library(rpart) #加载rpart包
head(iris) #看看iris数据集里有哪些变量
iris以鸢尾花的特征作为数据来源，数据集包含150个数据，分为3类，每类50个数据，每个数据包含4个属性分别是花萼长度、花萼宽带、花瓣长度、花瓣宽度
用gini度量纯度
iris.rp1=rpart(Species~.,data=iris,method="class",parms=list(split="g ini"))
# 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(iris.rp1, uniform=T, branch=0, margin=0.1,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 Tree
Iris Species by Petal and Sepal Length
branch=0
Classification Tree
Iris Species by Petal and Sepal Length
branch=1
|
Classification T ree
Iris Species by Petal and Sepal Length
branch=0.5
|
（3）margin刻画图的大小，margin越大，决策树越小，上述三幅图的margin=0.1，而当margin=1时，决策树变小了
Classification T ree
Iris Species by Petal and Sepal Length
（4）main是图的标题，其中“\n”是换行的意思
text(iris.rp1, use.n=T, fancy=T, col="blue")
Classification Tree
Iris Species by Petal and Sepal Length
text(iris.rp1, use.n=T, fancy=F, col="blue")
（1） use.n=T ，在每个节点处都会显示落在该节点的观测个数和对应的分类，
use.n=F 时就不显示观测个数了。
（2） fancy=T 、F 的区别见上图
（3） col=“blue”就是写在树上的信息的颜色。
还有另一种画图函数 library(rpart.plot)
rpart.plot(iris.rp1,branch=0,branch.type=2,type=1,extra=1,shadow.col="gray",box.col="green",border.col="blue",split.col="red" ,main="决策树")
Classification Tree
Iris Species by Petal and Sepal Length
Petal.Length< 2.45
Petal.Width< 1.75
setosa 50/0/0
versicolor 0/49/5virginica 0/1/45
决策树
rpart.plot(iris.rp1,branch=0,branch.type=0,type=1,extra=1,shadow.col= "gray",box.col="green",border.col="blue",split.col="red", main="决策树")
决策树
（1） branch.type是分支的形状参数，branch.type=0时画出来的分支跟plot 里的一样，就是一条线，而当branch.type=2时，分支的宽度是数据的标准差，branch.type=1时，是方差
（2） type：type=0只对叶子节点画圆圈。type=1对根节点和叶子节点画圆圈，分裂属性的值会写在节点框的上面。type=2时跟type=1近似，但分裂属性的值会写在节点框的下面。type=3时每个根节点左右分支对应的属性的取值范围都标出来了（之前那些都只标了左分支的属性取值），并且只对叶子节点画圆圈。type=4时，跟type=3近似，但对叶子节点和根节点都画圆圈。
（3） extra是表示在节点处显示的额外信息的种类。当extra=0（缺省值）时，无额外信息。当extra=1，在节点处会显示落在该节点的观测个数和对应的分类（如上图）。当extra=2，在节点处会显示（在该点分类正确的个数/落在该节点的观测个数）。
（4） shadow.col="gray",box.col="green",border.col="blue",split.col="
red"分别是决策树中节点框的阴影颜色、填充颜色、边框颜色、和分类属性的颜色
用信息增益度量纯度
iris.rp2=rpart(Species~.,data=iris,method="class",parms=list(split="i nformation"))
plot(iris.rp2, uniform=T, branch=0, margin=0.1,main="Classification Tree\nIris Species by Petal and Sepal Length")
text(iris.rp2, use.n=T, fancy=T, col="blue")
Classification Tree
Iris Species by Petal and Sepal Length
由上面两幅图可以看出，对于iris数据集，无论是用信息增益（information）还是gini来选择分裂属性，得到的决策树都是一样的。
决策树检验
因为iris数据集比较简单，不需修树，我们可以把原来的150个样本随机分成学习集和测试集，用学习集来生成决策树，然后用测试集验证决策树的准确性。ind <- sample(2, nrow(iris), replace=TRUE, prob=c(0.7, 0.3))
iris.train=iris[ind==1,] #生成训练集
iris.test=iris[ind==2,] #生成测试集
iris.rp2=rpart(Species~., iris.train, method=“class”)
iris.rp3=predict(iris.rp2, iris.test[,-5], type="class")
table(iris.test[,5],iris.rp3)
准确率=1-2/43=95.35%，与原来的96%准确性几乎一样，所以这颗决策树有加好的泛化能力。
我们再考虑另一个复杂一点的例子。
pima=read.table("D:/Grace/pima.indians.diabetes3.txt",header=T)
数据说明：
通过7个变量（分别是怀孕次数npregnant，身体质量指数bmi，葡萄糖水平glucose，心脏血样diastolic.bp，皮下脂肪厚度skinfold thickness，遗传影响pedigree，年龄age）来判断一个人是否患有糖尿病。
set.seed(123)
pima.rp <- rpart(pima[,9] ~., data = pima[,1:7], cp=0.004, parms=list(split="gini"))
数据的第八列和第九列其实是一样的，有糖尿病（diabetic）的记为1，正常的记为0，把第九列的分类属性作为因变量， Pima数据集的前七列作为自变量，用gini来衡量纯度，
结果解释：
以根节点为例，观测总数是532，其中177例糖尿病，355例正常，该节点的分类属性是正常，所以错判例数（loss）是177，（错判率，正确判断率）= (0.33270677 0.66729323)。如果根节点的观测满足glucose>=127.5（即128），则观测值落入左边的分支，否则落入右边的分支。
rpart.plot(pima.rp,branch=0,branch.type=0,type=1,extra=1,shadow.col=" gray",box.col="green",border.col="blue",split.col="red", main="决策树")
决策树
图的解释：
1.每个节点框中的数字是：（落在该节点有糖尿病的个数/正常的个数）
2.每个节点框内的diabetic、normal表示该节点对应的分类属性
printcp(pima.rp) #列出cp值
cp: complexity parameter 复杂性参数，用来修剪树的 当决策树复杂度超过一定程度后，随着复杂度的提高，测试集的分类精确度反而会降低。因此，建立的决策树不宜太复杂，需进行剪枝。该剪枝算法依赖于复杂性参数cp,cp 随树复杂度的增加而减小，当增加一个节点引起的分类精确度变化量小于树复杂度变化的cp 倍时，则须剪去该节点。故建立一棵既能精确分类，又不过度适合的决策树的关键是求解一个合适的cp 值。一般选择错判率最小值对应的cp 值来修树
plotcp(pima.rp)
cp
X -v a l R e l a t i v e E r r o r
0.6
0.70.80.91.01.1
Inf
0.120.0380.0230.0170.0130.0067
1
2
4
6
10
12
15
size of tree
pima.prune=prune(pima.rp,cp=pima.rp$cptable[which.min(pima.rp$cptable [,"xerror"]),"CP"])
修剪决策树
xerror：交叉验证（cross validation）错判率的估计
xstd:交叉验证错判率的标准差
建立树模型要权衡两方面问题，一个是要拟合得使分组后的变异较小，另一个是要防止过度拟合，而使模型的误差过大，前者的参数是CP，后者的参数是Xerror。所以要在Xerror最小的情况下，也使CP尽量小。
Party包的ctree函数
party包的处理方式：它的背景理论是“条件推断决策树”（conditional inference trees）：它根据统计检验来确定自变量和分割点的选择。即先假设所有自变量与因变量均独立。再对它们进行卡方独立检验，检验P值小于阀值的自变量加入模型，相关性最强的自变量作为第一次分割的自变量。自变量选择好后，用置换检验来选择分割点。用party包建立的决策树不需要剪枝，因为阀值就决定了模型的复杂程度。所以如何决定阀值参数是非常重要的（参见ctree_control）。较为流行的做法是取不同的参数值进行交叉检验，选择误差最小的模型参数。
Ctree在Iris数据上的应用
##先载入包party
##构造分类树
iris_ctree<-ctree(Species~.,data=iris)
##画出分类树的图
plot(iris_ctree)
plot(iris_ctree,type="simple")
##比较用分类树预测的结果和实际结果之间的区别
table(predict(iris_ctree),iris$Species)
##由结果可以看出，由该决策树得到的结果的错误率为6/150=4%
Ctree在diabetes数据上的应用
##载入diabetes的数据
data2=read.table("F:\\课件\\讨论班\\研一秋季学期\\我的讲稿\\pima.indians.diabetes3.txt",header=T)
##观察diabetes的数据
head（data2）
##构造分类树
pima_ctree=ctree(class~npregnant+glucose+diastolic.bp+skinfold.thickness+bmi+pedigree+age,d ata=data2)
##画出分类树的图
plot(pima_ctree)
plot(pima_ctree,type="simple")
##计算错判率
##由结果可以看出，由该决策树得到的结果的错误率为109/532=20.5%
##能否修改参数改变模型？
ctree_control(teststat = c("quad", "max"),
testtype = c("Bonferroni", "MonteCarlo",
"Univariate", "Teststatistic"), mincriterion = 0.95, minsplit = 20, minbucket = 7,
stump = FALSE, nresample = 9999, maxsurrogate = 0,
mtry = 0, savesplitstats = TRUE, maxdepth = 0)
teststat a character specifying the type of the test statistic to be applied.
testtype a character specifying how to compute the distribution of the test statistic. mincriterion the value of the test statistic (for testtype == "Teststatistic"), or 1 - p-value (for other values of testtype) that must be exceeded in order to
implement a split.
minsplit the minimum sum of weights in a node in order to be considered for
splitting.
minbucket the minimum sum of weights in a terminal node.
stump a logical determining whether a stump (a tree with three nodes only) is to be computed.
nresample number of Monte-Carlo replications to use when the distribution of the test statistic is simulated.
maxsurrogate number of surrogate splits to evaluate. Note the currently only surrogate splits in ordered covariables are implemented.
mtry number of input variables randomly sampled as candidates at each node for random forest like algorithms. The default mtry = 0 means that no
random selection takes place.
savesplitstats a logical determining if the process of standardized two-sample statistics for split point estimate is saved for each primary split.
maxdepth maximum depth of the tree. The default maxdepth = 0 means that no restrictions are applied to tree sizes.
##
##尝试修改mincriterion=0.6（mincriterion=0.95的结果与原来一样，故0.95应该为默认值）pima_ctree=ctree(class~npregnant+glucose+diastolic.bp+skinfold.thickness+bmi+pedigree+age,d ata=data2,control=ctree_control(mincriterion=0.6))
table(predict(pima_ctree),data2$class)
##计算错判率
##由结果可以看出，由该决策树得到的结果的错误率为97/532=18.2%
plot(pima_ctree)
##此时树变得更复杂了
基于决策树的分类方法研究
南京师范大学 硕士学位论文 基于决策树的分类方法研究 姓名：戴南 申请学位级别：硕士 专业：计算数学（计算机应用方向） 指导教师：朱玉龙 2003.5.1
摘要 厂 ｛数掘挖掘，又称数据库中的知识发现，是指从大型数据库或数据仓库中提取 具有潜在应用价值的知识或模式。模式按其作用可分为两类：描述型模式和预测型模式。分类模式是一种重要的预测型模式。挖掘分娄模式的方法有多种，如决 策树方法、贝叶斯网络、遗传算法、基于关联的分类方法、羊Ｈ糙集和ｋ一最临近方、／ 法等等。，／驴 Ｉ 本文研究如何用决策树方法进行分类模式挖掘。文中详细阐述了几种极具代表性的决策树算法：包括使用信息熵原理分割样本集的ＩＤ３算法；可以处理连续属性和属性值空缺样本的Ｃ４．５算法；依据ＧＩＮＩ系数寻找最佳分割并生成二叉决策树的ＣＡＲＴ算法；将树剪枝融入到建树过程中的ＰＵＢＬＩＣ算法：在决策树生成过程中加入人工智能和人为干预的基于人机交互的决策树生成方法；以及突破主存容量限制，具有良好的伸缩性和并行性的ＳＩ，ｌＱ和ＳＰＲＩＮＴ算法。对这些算法的特点作了详细的分析和比较，指出了它们各自的优势和不足。文中对分布式环境下的决策树分类方法进行了描述，提出了分布式ＩＤ３算法。该算法在传统的ＩＤ３算法的基础上引进了新的数掘结构：属性按类别分稚表，使得算法具有可伸缩性和并行性。最后着重介绍了作者独立完成的一个决策树分类器。它使用的核心算法为可伸缩的ＩＤ３算法，分类器使用ＭｉｃｒｏｓｏｆｔＶｉｓｕａｌｃ＋＋６．０开发。实验结果表明作者开发的分类器可以有效地生成决策树，建树时间随样本集个数呈线性增长，具有可伸缩性。。 ，，荡囊 关键字：数据挖掘１分类规则，决策树，分布式数据挖掘
R语言-决策树算法知识讲解
R语言-决策树算法
决策树算法 决策树定义 首先，我们来谈谈什么是决策树。我们还是以鸢尾花为例子来说明这个问题。 观察上图，我们判决鸢尾花的思考过程可以这么来描述：花瓣的长度小于 2.4cm的是setosa(图中绿色的分类)，长度大于1cm的呢?我们通过宽度来判别，宽度小于1.8cm的是versicolor(图中红色的分类)，其余的就是 virginica(图中黑色的分类) 我们用图形来形象的展示我们的思考过程便得到了这么一棵决策树： 这种从数据产生决策树的机器学习技术叫做决策树学习, 通俗点说就是决策树，说白了，这是一种依托于分类、训练上的预测树，根据已知预测、归类未来。 前面我们介绍的k-近邻算法也可以完成很多分类任务，但是他的缺点就是含义不清，说不清数据的内在逻辑，而决策树则很好地解决了这个问题，他十分好理解。从存储的角度来说，决策树解放了存储训练集的空间，毕竟与一棵树的存储空间相比，训练集的存储需求空间太大了。 决策树的构建 一、KD3的想法与实现 下面我们就要来解决一个很重要的问题：如何构造一棵决策树?这涉及十分有趣的细节。 先说说构造的基本步骤，一般来说，决策树的构造主要由两个阶段组成:第一阶段，生成树阶段。选取部分受训数据建立决策树，决策树是按广度优先建立直到每个叶节点包括相同的类标记为止。第二阶段，决策树修剪阶段。用剩余数据检验决策树，如果所建立的决策树不能正确回答所研究的问题，我们要对决策树进行修剪直到建立一棵正确的决策树。这样在决策树每个内部节点处进行属性值的比较，在叶节点得到结论。从根节点到叶节点的一条路径就对应着一条规则，整棵决策树就对应着一组表达式规则。 问题：我们如何确定起决定作用的划分变量。 我还是用鸢尾花的例子来说这个问题思考的必要性。使用不同的思考方式，我们不难发现下面的决策树也是可以把鸢尾花分成3类的。 为了找到决定性特征，划分出最佳结果，我们必须认真评估每个特征。通常划分的办法为信息增益和基尼不纯指数，对应的算法为C4.5和CART。 关于信息增益和熵的定义烦请参阅百度百科，这里不再赘述。 直接给出计算熵与信息增益的R代码：
Clementine决策树CHAID算法
CHAID算法（Chi-Square Automatic Interaction Detection） CHAID提供了一种在多个自变量中自动搜索能产生最大差异的变量方案。 不同于C＆R树和QUEST节点，CHAID分析可以生成非二进制树，即有些分割有两个以上的分支。 CHAID模型需要一个单一的目标和一个或多个输入字段。还可以指定重量和频率领域。 CHAID分析，卡方自动交互检测，是一种用卡方统计，以确定最佳的分割，建立决策树的分类方法。 1.CHAID方法（卡方自动交叉检验） CHAID根据细分变量区分群体差异的显著性程度（卡方值）的大小顺序，将消费者分为不同的细分群体，最终的细分群体是由多个变量属性共同描述的，因此属于多变量分析。 在形式上，CHAID非常直观，它输出的是一个树状的图形。 1.它以因变量为根结点，对每个自变量（只能是分类或有序变量，也就是离散性的，如果是连续 变量，如年龄，收入要定义成分类或有序变量）进行分类，计算分类的卡方值(Chi-Square-Test)。如果 几个变量的分类均显著，则比较这些分类的显著程度（P值的大小），然后选择最显著的分类法作为子节点。 2.CHIAD可以自动归并自变量中类别，使之显著性达到最大。 3.最后的每个叶结点就是一个细分市场 CHAID 自动地把数据分成互斥的、无遗漏的组群,但只适用于类别型资料。 当预测变量较多且都是分类变量时，CHAID分类最适宜。 2.CHAID分层的标准：卡方值最显著的变量 3.CHAID过程：建立细分模型，根据卡方值最显著的细分变量将群体分出两个或多个群体，对 于这些群体再根据其它的卡方值相对最显著的细分变量继续分出子群体，直到没有统计意义上显著的细分变量可以将这些子群体再继续分开为止。 4.CHAID的一般步骤 -属性变量的预处理 -确定当前分支变量和分隔值 属性变量的预处理： -对定类的属性变量，在其多个分类水平中找到对目标变量取值影响不显著的分类，并合并它们； -对定距型属性变量，先按分位点分组，然后再合并具有同质性的组； -如果目标变量是定类变量，则采用卡方检验 -如果目标变量为定距变量，则采用F检验 （统计学依据数据的计量尺度将数据划分为三大类，即定距型数据（Scale）、定序型数据（Ordinal）和定类型数据（Nominal）。定距型数据通常指诸如身高、体重、血压等 的连续性数据，也包括诸如人数、商品件数等离散型数据；定序型数据具有内在固有大 小或高低顺序，但它又不同于定距型数据，一般可以数值或字符表示。如职称变量可以 有低级、中级和高级三个取值，可以分别用1、2、3等表示，年龄段变量可以有老、中、青三个取值，分别用A、B、C表示等。这里无论是数值型的1、2、3还是字符型的A、B、C，都是有大小或高低顺序的，但数据之间却是不等距的。因为低级和中级职称之间的差距与中级和高级职称之间的差距是不相等的；定类型数据是指没有内在固定大小或高低 顺序，一般以数值或字符表示的分类数据。） F检验：比较两组数据的方差2s， 2 2 s F s 大 小 ，假设检验两组数据没有显著差异，F
决策树算法介绍(DOC)
3.1 分类与决策树概述 3.1.1 分类与预测 分类是一种应用非常广泛的数据挖掘技术，应用的例子也很多。例如，根据信用卡支付历史记录，来判断具备哪些特征的用户往往具有良好的信用；根据某种病症的诊断记录，来分析哪些药物组合可以带来良好的治疗效果。这些过程的一个共同特点是：根据数据的某些属性，来估计一个特定属性的值。例如在信用分析案例中，根据用户的“年龄”、“性别”、“收入水平”、“职业”等属性的值，来估计该用户“信用度”属性的值应该取“好”还是“差”，在这个例子中，所研究的属性“信用度”是一个离散属性，它的取值是一个类别值，这种问题在数据挖掘中被称为分类。 还有一种问题，例如根据股市交易的历史数据估计下一个交易日的大盘指数，这里所研究的属性“大盘指数”是一个连续属性，它的取值是一个实数。那么这种问题在数据挖掘中被称为预测。 总之，当估计的属性值是离散值时，这就是分类；当估计的属性值是连续值时，这就是预测。 3.1.2 决策树的基本原理 1.构建决策树 通过一个实际的例子，来了解一些与决策树有关的基本概念。 表3-1是一个数据库表，记载着某银行的客户信用记录，属性包括“姓名”、“年龄”、“职业”、“月薪”、......、“信用等级”，每一行是一个客户样本，每一列是一个属性（字段）。这里把这个表记做数据集D。 银行需要解决的问题是，根据数据集D，建立一个信用等级分析模型，并根据这个模型，产生一系列规则。当银行在未来的某个时刻收到某个客户的贷款申请时，依据这些规则，可以根据该客户的年龄、职业、月薪等属性，来预测其信用等级，以确定是否提供贷款给该用户。这里的信用等级分析模型，就可以是一棵决策树。在这个案例中，研究的重点是“信用等级”这个属性。给定一个信用等级未知的客户，要根据他/她的其他属性来估计“信用等级”的值是“优”、“良”还是“差”，也就是说，要把这客户划分到信用等级为“优”、“良”、“差”这3个类别的某一类别中去。这里把“信用等级”这个属性称为“类标号属性”。数据集D中“信用等级”属性的全部取值就构成了类别集合：Class={“优”，
基于决策树的分类算法
1 分类的概念及分类器的评判 分类是数据挖掘中的一个重要课题。分类的目的是学会一个分类函数或分类模型（也常常称作分类器），该模型能把数据库中的数据项映射到给定类别中的某一个。分类可用于提取描述重要数据类的模型或预测未来的数据趋势。 分类可描述如下：输入数据，或称训练集（training set）是一条条记录组成的。每一条记录包含若干条属性（attribute），组成一个特征向量。训练集的每条记录还有一个特定的类标签（类标签）与之对应。该类标签是系统的输入，通常是以往的一些经验数据。一个具体样本的形式可为样本向量：(v1,v2,…,…vn:c)。在这里vi表示字段值，c表示类别。 分类的目的是：分析输入数据，通过在训练集中的数据表现出来的特性，为每一个类找到一种准确的描述或者模型。这种描述常常用谓词表示。由此生成的类描述用来对未来的测试数据进行分类。尽管这些未来的测试数据的类标签是未知的，我们仍可以由此预测这些新数据所属的类。注意是预测，而不能肯定。我们也可以由此对数据中的每一个类有更好的理解。也就是说：我们获得了对这个类的知识。 对分类器的好坏有三种评价或比较尺度： 预测准确度：预测准确度是用得最多的一种比较尺度，特别是对于预测型分类任务，目前公认的方法是10番分层交叉验证法。 计算复杂度：计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘中，由于操作对象是巨量的数据库，因此空间和时间的复杂度问题将是非常重要的一个环节。 模型描述的简洁度：对于描述型的分类任务，模型描述越简洁越受欢迎；例如，采用规则表示的分类器构造法就更有用。 分类技术有很多，如决策树、贝叶斯网络、神经网络、遗传算法、关联规则等。本文重点是详细讨论决策树中相关算法。
决策树算法介绍
3.1分类与决策树概述 3.1.1分类与预测 分类是一种应用非常广泛的数据挖掘技术，应用的例子也很多。例如，根据信用卡支付历史记录，来判断具备哪些特征的用户往往具有良好的信用；根据某种病 症的诊断记录，来分析哪些药物组合可以带来良好的治疗效果。这些过程的一个共同特点是：根据数据的某些属性，来估计一个特定属性的值。例如在信用分析案例中，根据用户的“年龄”、“性别”、“收入水平”、“职业”等属性的值，来估计该用户“信用度”属性的值应该取“好”还是“差”，在这个例子中，所研究的属性“信用度”是E—个离散属性，它的取值是一个类别值，这种问题在数 据挖掘中被称为分类。 还有一种问题，例如根据股市交易的历史数据估计下一个交易日的大盘指数，这 里所研究的属性“大盘指数”是一个连续属性，它的取值是一个实数。那么这种 问题在数据挖掘中被称为预测。 总之，当估计的属性值是离散值时，这就是分类；当估计的属性值是连续值时，这就是预测。 3.1.2决策树的基本原理 1. 构建决策树 通过一个实际的例子，来了解一些与决策树有关的基本概念。 表3-1是一个数据库表，记载着某银行的客户信用记录，属性包括“姓名”、“年龄”、“职业”、“月薪”、......、“信用等级”，每一行是一个客户样本，每一列是一个属性（字段）。这里把这个表记做数据集D。 银行需要解决的问题是，根据数据集D,建立一个信用等级分析模型，并根据这个模型，产生一系列规则。当银行在未来的某个时刻收到某个客户的贷款申请时，依据这些规则，可以根据该客户的年龄、职业、月薪等属性，来预测其信用等级，以确定是否提供贷款给该用户。这里的信用等级分析模型，就可以是一棵决策树。在这个案例中，研究的重点是“信用等级”这个属性。给定一个信用等级未知的客户，要根据他/她的其他属性来估计“信用等级”的值是“优”、“良”还是 “差”，也就是说，要把这客户划分到信用等级为“优”、“良”、“差”这3 个类别的某一类别中去。这里把“信用等级”这个属性称为“类标号属性”。数据集D中“信用等级”属性的全部取值就构成了类别集合：Class={ “优”，
新决策树例子
rpart包的rpart函数 Iris数据集 library(rpart) #加载rpart包 head(iris) #看看iris数据集里有哪些变量 iris以鸢尾花的特征作为数据来源，数据集包含150个数据，分为3类，每类50个数据，每个数据包含4个属性分别是花萼长度、花萼宽带、花瓣长度、花瓣宽度 用gini度量纯度 iris.rp1=rpart(Species~.,data=iris,method="class",parms=list(split="g ini")) # 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(iris.rp1, uniform=T, branch=0, margin=0.1,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）时是梯形
如何运用决策树进行分类分析
如何运用决策树进行分类分析 前面我们讲到了聚类分析的基本方法，这次我们来讲讲分类分析的方法。 所谓分类分析，就是基于响应，找出更好区分响应的识别模式。分类分析的方法很多，一般而言，当你的响应为分类变量时，我们就可以使用各种机器学习的方法来进行分类的模式识别工作，而决策树就是一类最为常见的机器学习的分类算法。 决策树，顾名思义，是基于树结构来进行决策的，它采用自顶向下的贪婪算法，在每个结点选择分类的效果最好的属性对样本进行分类，然后继续这一过程，直到这棵树能准确地分类训练样本或所有的属性都已被使用过。 建造好决策树以后，我们就可以使用决策树对新的事例进行分类。我们以一个生活小案例来说什么是决策树。例如，当一位女士来决定是否同男士进行约会的时候，她面临的问题是“什么样的男士是适合我的，是我值得花时间去见面再进行深入了解的？” 这个时候，我们找到了一些女生约会对象的相关属性信息，例如，年龄、长相、收入等等，然后通过构建决策树，层层分析，最终得到女士愿意去近一步约会的男士的标准。 图：利用决策树确定约会对象的条件
接下来，我们来看看这个决策的过程什么样的。 那么，问题来了，怎样才能产生一棵关于确定约会对象的决策树呢？在构造决策树的过程中，我们希望决策树的每一个分支结点所包含的样本尽可能属于同一类别，即结点的”纯度”（Purity ）越来越高。 信息熵（Information Entropy ）是我们度量样本集合纯度的最常见指标，假定当前样本集合中第K 类样本所占的比例为P k ，则该样本集合的信息熵为： Ent (D )=?∑p k |y| k=1 log 2p k 有了这个结点的信息熵，我们接下来就要在这个结点上对决策树进行裁剪。当我们选择了某一个属性对该结点，使用该属性将这个结点分成了2类，此时裁剪出来的样本集为D 1和D 2， 然后我们根据样本数量的大小，对这两个裁剪点赋予权重|D 1||D|?，|D 2||D|?，最后我们就 可以得出在这个结点裁剪这个属性所获得的信息增益（Information Gain ） Gain(D ，a)=Ent (D )?∑|D V ||D |2 v=1Ent(D V ) 在一个结点的裁剪过程中，出现信息增益最大的属性就是最佳的裁剪点，因为在这个属性上，我们获得了最大的信息增益，即信息纯度提升的最大。 其实，决策树不仅可以帮助我们提高生活的质量，更可以提高产品的质量。 例如，我们下表是一组产品最终是否被质检接受的数据，这组数据共有90个样本量，数据的响应量为接受或拒绝，则|y|=2。在我们还没有对数据进行裁剪时，结点包含全部的样本量，其中接受占比为p 1= 7690，拒绝占比为p 2=1490，此时，该结点的信息熵为： Ent (D )=?∑p k |y|k=1log 2p k =-（7690log 27690+1490log 21490）=0.6235
基于决策树的鸢尾花分类
科技论坛 0 引言 图像识别技术，要运用目前流行的机器学习算法，而目前流行的机器学习算法就有十几种，比如支持向量机、神经网络、决策树。机器学习是人工智能发展的重要一部分，它涉及的学科很多，应用也相当广泛，它通过分析、研究、设计让计算机学习知识，从而提高完善自身的性能。但是神经网络学习的速度较慢，传统的支持向量机则不能解决分类多的问题。 本文针对鸢尾花的特征类别少以及种类少的特点，采用决策树算法对课题进行展开，对比与其他人利用支持向量机、神经元网络模型来进行研究，该系统具有模型简单、便于理解、计算方便、消耗资源少的优点。 1 决策树模型和学习 本文采用决策树算法对鸢尾花进行分类，先建立决策树的模型并进行学习训练，在决策树的训练过程中采用是信息论的知识进行特征选择，对选定的特征采用分支的处理，然后再对分支过后的数据集如此反复的递归生成决策树，在一颗决策树生成完后对决策树进行剪枝，以减小决策树的拟合度，来达到一个对鸢尾花较高的分类准确率。 要对鸢尾花进行分类首先需要大量的鸢尾花数据集作为本文的实验数据，本文采用的数据集是来自加州大学欧文分校UCI数据库中的鸢尾花数据集。该数据集中鸢尾花的属性有四个，分别是花萼长度、花萼宽度、花瓣长度和花瓣宽度，鸢尾花的类别则有三种，分别是Iris Setosa，Iris Versicolour，Iris Virginica，用简写Se、Ve和Vi表示这三种花，具体数据如图1所示。 ■1.1 信息论 美贝尔电话研究所的数学家香农是信息论的创始人，1948年香农发表了《通讯的数学理论》,成为信息论诞生的标志。信息论的诞生对信息技术革命以及科学技术的发展起到重要作用。信息论中有两个概念信息增益及信息增益率，都是用于衡量原始数据集在按照某一属性特征分裂之后整体信息量的变化值。这样，本文就可以通过这种指标寻找出最优的划分属性，数据集在经过划分之后，节点的“纯度”越来越高，这里的纯度值得是花朵的类别，当某一节点中花朵全为一类时，该节点已经达到最纯状态，无需再进行划分， 反之继续划分。 图1 鸢尾花数据集 1.1.1 信息熵 信息熵用于描述信源的不确定性。即发生每个事件都有不确定性，为了使不确定性降低，我们需要引入一些相关的信息进行学习，引入信息越多，那么得到的准确率越高，信息熵越高，信源越不稳定。例如一束鸢尾花，它可能是Se,可能是Vi，也有可能是Ve，我们利用数据库中的各种鸢尾花的花瓣长度、花瓣宽度、花萼长度和花萼宽度来预测鸢尾花的类别，引入的鸢尾花种类越多，信息熵就越高。 样本集合D的信息熵Ent(D)以下面的公式进行计算，其中集合里第k类样本所占的比例是k p，k的取值范围是从1到y，y值得是总共有y类样本，通过式（1）可以计算得到原始样本集的信息熵。 ()21 Ent D y k k k p log p = =?∑(1) 1.1.2 信息增益 信息增益即在一个条件下，信源不确定性减少的程度。信息增益用于度量节点的纯度。信息增益对可取值数目较多的属性有所偏好。在鸢尾花数据集的D集合中，属性a取到某一取值情况的概率乘该取值情况的信息熵得到的值记为v D，其中V指的是该属性a可以取值的个数，则属性a 的信息增益为： ()()() 1 Gain D,a Ent D V v v v D Ent D D = =?∑(2) 基于决策树的鸢尾花分类 徐彧铧 （浙江省衢州第二中学，浙江衢州，324000） 摘要：针对传统手工分类的不足，满足不了人们对图片分类的需求，本文利用机器学习算法中的决策树算法进行研究。通过模型简单、便于理解、计算方便、消耗资源少的决策树算法模型，并利用现成的数据库，运用图像识别技术对鸢尾花进行分类，以求方便简单快速地识别出不同类别的鸢尾花。在此过程中，学习到图像识别的一些基本分类操作，为我们实现更复杂的模型提供了帮助。 关键词：决策树信息论特征选择；C4.5算法；CART算法 www ele169 com | 99
完整word版,决策树算法总结
决策树研发二部
目录 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
决策树分类-8页文档资料
基于专家知识的决策树分类 概述 基于知识的决策树分类是基于遥感影像数据及其他空间数据，通过专家经验总结、简单的数学统计和归纳方法等，获得分类规则并进行遥感分类。分类规则易于理解，分类过程也符合人的认知过程，最大的特点是利用的多源数据。 如图1所示，影像+DEM就能区分缓坡和陡坡的植被信息，如果添加其他数据，如区域图、道路图土地利用图等，就能进一步划分出那些是自然生长的植被，那些是公园植被。 图1.JPG 图1 专家知识决策树分类器说明图 专家知识决策树分类的步骤大体上可分为四步：知识（规则）定义、规则输入、决策树运行和分类后处理。 1.知识（规则）定义 规则的定义是讲知识用数学语言表达的过程，可以通过一些算法获取，也可以通过经验总结获得。 2.规则输入
将分类规则录入分类器中，不同的平台有着不同规则录入界面。 3.决策树运行 运行分类器或者是算法程序。 4.分类后处理 这步骤与监督/非监督分类的分类后处理类似。 知识（规则）定义 分类规则获取的途径比较灵活，如从经验中获得，坡度小于20度，就认为是缓坡，等等。也可以从样本中利用算法来获取，这里要讲述的就是C4.5算法。 利用C4.5算法获取规则可分为以下几个步骤： （1）多元文件的的构建：遥感数据经过几何校正、辐射校正处理后，进行波段运算，得到一些植被指数，连同影像一起输入空间数据库；其他空间数据经过矢量化、格式转换、地理配准，组成一个或多个多波段文件。 （2）提取样本，构建样本库：在遥感图像处理软件或者GIS软件支持下，选取合适的图层，采用计算机自动选点、人工解译影像选点等方法采集样本。 （3）分类规则挖掘与评价：在样本库的基础上采用适当的数据挖掘方法挖掘分类规则，后基于评价样本集对分类规则进行评价，并对分类规则做出适当的调整和筛选。这里就是C4.5算法。 4.5算法的基本思路基于信息熵来“修枝剪叶”，基本思路如下： 从树的根节点处的所有训练样本D0开始，离散化连续条件属性。计算增益比率，取GainRatio（C0）的最大值作为划分点V0，将样本分为两个部分D11和D12。对属性C0的每一个值产生一个分支，分支属性值的相应样本子集被移到新生成的子节点上，如果得到的样本都属于同一个类，那么直接得到叶子结点。相应地将此方法应用于每个子节点上，直到节点的所有样本都分区到某个类中。到达决策树的叶节点的每条路径表示一条分类规则，利用叶列表及指向父结点的指针就可以生成规则表。
决策树分类算法
决策树分类算法 决策树是一种用来表示人们为了做出某个决策而进行的一系列判断过程的树形图。决策树方法的基本思想是：利用训练集数据自动地构造决策树，然后根据这个决策树对任意实例进行判定。 1．决策树的组成 决策树的基本组成部分有：决策节点、分支和叶，树中每个内部节点表示一个属性上的测试，每个叶节点代表一个类。图1就是一棵典型的决策树。 图1 决策树 决策树的每个节点的子节点的个数与决策树所使用的算法有关。例如，CART算法得到的决策树每个节点有两个分支，这种树称为二叉树。允许节点含有多于两个子节点的树称为多叉树。 下面介绍一个具体的构造决策树的过程，该方法
是以信息论原理为基础，利用信息论中信息增益寻找数据库中具有最大信息量的字段，建立决策树的一个节点，然后再根据字段的不同取值建立树的分支，在每个分支中重复建立树的下层节点和分支。 ID3算法的特点就是在对当前例子集中对象进行分类时，利用求最大熵的方法，找出例子集中信息量（熵）最大的对象属性，用该属性实现对节点的划分，从而构成一棵判定树。 首先，假设训练集C 中含有P 类对象的数量为p ，N 类对象的数量为n ，则利用判定树分类训练集中的对象后，任何对象属于类P 的概率为p/(p+n)，属于类N 的概率为n/(p+n)。 当用判定树进行分类时，作为消息源“P ”或“N ”有关的判定树，产生这些消息所需的期望信息为： n p n log n p n n p p log n p p )n ,p (I 22++-++- = 如果判定树根的属性A 具有m 个值｛A 1, A 2, …, A m ｝，它将训练集C 划分成｛C 1, C 2, …, C m ｝，其中A i 包括C 中属性A 的值为A i 的那些对象。设C i 包括p i 个类P 对象和n i 个类N 对象，子树C i 所需的期望信息是I(p i , n i )。以属性A 作为树根所要求的期望信息可以通过加权平均得到
决策树实例计算
计算题 一 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 （万元） 比较结果，新建方案最佳。 最大最小后悔决策，是用后悔值计算表进行计算的： 后悔值计算表
决策树算法总结
决策树决策树研发二部
目录 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
(完整word版)项目管理实战利器之八——决策树分析和EMV
项目管理实战利器之八——决策树分析和EMV 作者: 楼政 一、决策者的工具包 “决策就是从多种方案中选择一个行动方针的认知过程。每一个决策过程都会产生一个最终选择。”这是在维基百科所阐述的。但它没有说的是，有些决策必须为未来发生的结果而做出。有数种工具可以用来帮助做出复杂的决策，即决策树分析和预期货币价值。 二、预期货币价值（EMV，Expected Monetary Value） EMV是一种对概率和各种可能情景影响所做的平衡。以下两种方案，哪一种会提供更大的潜在收益呢？ 方案1 最好的情景(Best case)：盈利$180,000的概率为20%。 BC=20%*$180,000=$3 6,000 最坏的情景(Worst case)：损失- $20,000的概率为 15％。 WC= 15%*（- $ 20,000）=-$3,000 最可能的情景(Most likely case)：盈利$75,000元 的概率为65％。 MLC= 65%*$75,000 = $48,750 Total EMV = BC+WC+MLC = $36,000+（-$3,000）+$48,750=$81,750 方案2 最好的情景(Best case)：盈利$200,000的概率为15%。BC=15%*$200,000=$30,00 最坏的情景(Worst case)：盈利$15,000的概率为25％。WC= 25%*$15,000 = $ 3,750 最可能的情景(Most likely case)：盈利$45,000元的概 率为60％。 MLC= 60%*$ 45,000 = $ 27,000 Total EMV = BC+WC+MLC = $30,000+$3,750+$27,000=$60,750 你选择哪种方案？当然选方案一，因为它具有更高的EMV为$81,750。 三、决策树分析（Decision Tree Analysis） 在决策树分析中，一个问题被描述为一个图表，这个图表显示了所有可能行动、事件和回报（成果），在一段时期内不同的时间点对上述内容必须作出的选择。 制造业的一个实例
论贝叶斯分类、决策树分类、感知器分类挖掘算法的优势与劣势
论贝叶斯分类、决策树分类、感知器分类挖掘算法的优势与劣势 摘要本文介绍了在数据挖掘中数据分类的几个主要分类方法，包括：贝叶斯分类、决策树分类、感知器分类，及其各自的优势与劣势。并对于分类问题中出现的高维效应，介绍了两种通用的解决办法。 关键词数据分类贝叶斯分类决策树分类感知器分类 引言 数据分类是指按照分析对象的属性、特征，建立不同的组类来描述事物。数据分类是数据挖掘的主要内容之一，主要是通过分析训练数据样本，产生关于类别的精确描述。这种类别通常由分类规则组成，可以用来对未来的数据进行分类和预测。分类技术解决问题的关键是构造分类器。 一．数据分类 数据分类一般是两个步骤的过程： 第1步：建立一个模型，描述给定的数据类集或概念集（简称训练集）。通过分析由属性描述的数据库元组来构造模型。每个元组属于一个预定义的类，由类标号属性确定。用于建立模型的元组集称为训练数据集，其中每个元组称为训练样本。由于给出了类标号属性，因此该步骤又称为有指导的学习。如果训练样本的类标号是未知的，则称为无指导的学习（聚类）。学习模型可用分类规则、决策树和数学公式的形式给出。 第2步：使用模型对数据进行分类。包括评估模型的分类准确性以及对类标号未知的元组按模型进行分类。 常用的分类规则挖掘方法 分类规则挖掘有着广泛的应用前景。对于分类规则的挖掘通常有以下几种方法，不同的方法适用于不同特点的数据：1．贝叶斯方法 2．决策树方法 3．人工神经网络方法 4．约略集方法 5．遗传算法 分类方法的评估标准： 准确率：模型正确预测新数据类标号的能力。 速度：产生和使用模型花费的时间。 健壮性：有噪声数据或空缺值数据时模型正确分类或预测的能力。 伸缩性：对于给定的大量数据，有效地构造模型的能力。 可解释性：学习模型提供的理解和观察的层次。 影响一个分类器错误率的因素 (1) 训练集的记录数量。生成器要利用训练集进行学习，因而训练集越大，分类器也就越可靠。然而，训练集越大，生成器构造分类器的时间也就越长。错误率改善情况随训练集规模的增大而降低。 (2) 属性的数目。更多的属性数目对于生成器而言意味着要计算更多的组合，使得生成器难度增大，需要的时间也更长。有时随机的关系会将生成器引入歧途，结果可能构造出不够准确的分类器（这在技术上被称为过分拟合）。因此，如果我们通过常识可以确认某个属性与目标无关，则将它从训练集中移走。 (3) 属性中的信息。有时生成器不能从属性中获取足够的信息来正确、低错误率地预测标签（如试图根据某人眼睛的颜色来决定他的收入）。加入其他的属性（如职业、每周工作小时数和年龄），可以降低错误率。 (4) 待预测记录的分布。如果待预测记录来自不同于训练集中记录的分布，那么错误率有可能很高。比如如果你从包含家用轿车数据的训练集中构造出分类器，那么试图用它来对包含许多运动用车辆的记录进行分类可能没多大用途，因为数据属性值的分布可能是有很大差别的。 评估方法 有两种方法可以用于对分类器的错误率进行评估，它们都假定待预测记录和训练集取自同样的样本分布。 (1) 保留方法(Holdout)：记录集中的一部分（通常是2/3）作为训练集，保留剩余的部分用作测试集。生成器使用2/3 的数据来构造分类器，然后使用这个分类器来对测试集进行分类，得出的错误率就是评估错误率。 虽然这种方法速度快，但由于仅使用2/3 的数据来构造分类器，因此它没有充分利用所有的数据来进行学习。如果使用所有的数据，那么可能构造出更精确的分类器。 (2) 交叉纠错方法(Cross validation)：数据集被分成k 个没有交叉数据的子集，所有子集的大小大致相同。生成器训练和测试共k 次；每一次，生成器使用去除一个子集的剩余数据作为训练集，然后在被去除的子集上进行测试。把所有
数据挖掘决策树算法概述
决策树是分类应用中采用最广泛的模型之一。与神经网络和贝叶斯方法相比，决策树无须花费大量的时间和进行上千次的迭代来训练模型，适用于大规模数据集，除了训练数据中的信息外不再需要其他额外信息，表现了很好的分类精确度。其核心问题是测试属性选择的策略，以及对决策树进行剪枝。连续属性离散化和对高维大规模数据降维，也是扩展决策树算法应用范围的关键技术。本文以决策树为研究对象，主要研究内容有：首先介绍了数据挖掘的历史、现状、理论和过程，然后详细介绍了三种决策树算法，包括其概念、形式模型和优略性，并通过实例对其进行了分析研究 目录 一、引言 (1) 二、数据挖掘 (2) (一)概念 (2) (二)数据挖掘的起源 (2) (三)数据挖掘的对象 (3) (四)数据挖掘的任务 (3) (五)数据挖掘的过程 (3) (六)数据挖掘的常用方法 (3) (七)数据挖掘的应用 (5) 三、决策树算法介绍 (5) (一)归纳学习 (5) (二)分类算法概述 (5) (三)决策树学习算法 (6) 1、决策树描述 (7) 2、决策树的类型 (8) 3、递归方式 (8) 4、决策树的构造算法 (8) 5、决策树的简化方法 (9) 6、决策树算法的讨论 (10) 四、ID3、C4.5和CART算法介绍 (10) (一)ID3学习算法 (11) 1、基本原理 (11) 2、ID3算法的形式化模型 (13) （二）C4.5算法 (14) （三）CART算法 (17) 1、CART算法理论 (17) 2、CART树的分支过程 (17) （四）算法比较 (19) 五、结论 (24) 参考文献...................................................................................... 错误！未定义书签。 致谢.............................................................................................. 错误！未定义书签。
机器学习--决策树(ID3)算法及案例
机器学习--决策树(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表示所有的不同类别)