第3章_分类与决策树解析

习题3（第三章 分类技术）1. 在决策树归纳中，选项有：(a)将决策树转化为规则，然后对结果规则剪枝，或(b)对决策树剪枝，然后将剪枝后的树转化为规则。

相对于(b)，(a)的优点是什么？ 解答：如果剪掉子树，我们可以用(b)将全部子树移除掉，但是用方法(a)的话，我们可以将子树的任何前提都移除掉。

方法(a)约束更少。

2. 在决策树归纳中，为什么树剪枝是有用的？使用分离的元组集评估剪枝有什么缺点？解答：决策树的建立可能过度拟合训练数据，这样就会产生过多分支，有些分支就是因为训练数据中的噪声或者离群点造成的。

剪枝通过移除最不可能的分支(通过统计学方法)，来排除这些过度拟合的数据。

这样得到的决策树就会变得更加简单跟可靠，用它来对未知数据分类时也会变得更快、更精确。

使用分离的元组集评估剪枝的缺点是，它可能不能代表那些构建原始决策树的训练元组。

如果分离的元组集不能很好地代表，用它们来评估剪枝树的分类精确度将不是一个很好的指示器。

而且，用分离的元组集来评估剪枝意味着将使用更少的元组来构建和测试树。

3. 画出包含4个布尔属性A,B,C,D 的奇偶函数的决策树。

该树有可能被简化吗？解答：决策树如下，该树不可能被简化。

4. X 是一个具有期望Np 、方差Np(1-p)的二项随机变量，证明X/N 同样具有二项分布且期望为p 方差为p(1-p)/N 。

解答：令r=X/N ，因为Ｘ是二项分布，ｒ同样具有二项分布。

期望，E[r] = E[X/N] = E[X]/N = (Np)/N = p; 方差，E[错误!未找到引用源。

] = E[错误!未找到引用源。

] = E[错误!未找到引用源。

]/错误!未找到引用源。

= Np(1-p)/错误!未找到引用源。

= p(1-p)/N5. 当一个数据对象同时属于多个类时，很难评估分类的准确率。

评述在这种情况下，你将A B C D Class T T T T T T T T F F T T F T F T T F F T T F T T F T F T F T T F F T T T F F F F F T T T F FTTFTF T F T TF T F F FF F T T TF F T F F F F F T F F F F F T使用何种标准比较对相同数据建立的不同分类器。

分类分析--决策树（经典决策树、条件推断树）分类分析--决策树决策树是数据挖掘领域中的常⽤模型。

其基本思想是对预测变量进⾏⼆元分离，从⽽构造⼀棵可⽤于预测新样本单元所属类别的树。

两类决策树：经典树和条件推断树。

1 经典决策树经典决策树以⼀个⼆元输出变量（对应威斯康星州乳腺癌数据集中的良性/恶性）和⼀组预测变量（对应九个细胞特征）为基础。

具体算法如下：(1) 选定⼀个最佳预测变量将全部样本单元分为两类，实现两类中的纯度最⼤化（即⼀类中良性样本单元尽可能多，另⼀类中恶性样本单元尽可能多）。

如果预测变量连续，则选定⼀个分割点进⾏分类，使得两类纯度最⼤化；如果预测变量为分类变量（本例中未体现），则对各类别进⾏合并再分类。

(2) 对每⼀个⼦类别继续执⾏步骤(1)。

(3) 重复步骤(1)~(2)，直到⼦类别中所含的样本单元数过少，或者没有分类法能将不纯度下降到⼀个给定阈值以下。

最终集中的⼦类别即终端节点（terminal node）。

根据每⼀个终端节点中样本单元的类别数众数来判别这⼀终端节点的所属类别。

(4) 对任⼀样本单元执⾏决策树，得到其终端节点，即可根据步骤3得到模型预测的所属类别。

上述算法通常会得到⼀棵过⼤的树，从⽽出现过拟合现象。

结果就是，对于训练集外单元的分类性能较差。

为解决这⼀问题，可采⽤10折交叉验证法选择预测误差最⼩的树。

这⼀剪枝后的树即可⽤于预测。

R中的rpart包⽀持rpart()函数构造决策树，prune()函数对决策树进⾏剪枝。

下⾯给出判别细胞为良性或恶性的决策树算法实现。

（1）使⽤rpart()函数创建分类决策树：#⽣成树：rpart()函数可⽤于⽣成决策树library(rpart)set.seed(1234)dtree <- rpart(class ~ ., data=df.train, method="class",parms=list(split="information"))#rpart() 返回的cptable值中包括不同⼤⼩的树对应的预测误差，因此可⽤于辅助设定最终的树的⼤⼩。

分类决策树的基本原理分类决策树是一种常用的机器学习算法，用于解决分类问题。

它的基本原理是通过对数据集进行分割，将数据划分为不同的类别。

这种分割过程是基于一系列特征和阈值来进行的，最终形成一个树状结构，每个节点代表一个特征及其阈值，每个叶子节点代表一个分类结果。

决策树的构建是一个递归的过程。

首先，从根节点开始，选择一个最佳的特征和阈值来进行数据集的分割。

选择最佳特征的方法有很多种，例如信息增益、基尼指数等。

信息增益是衡量特征对分类结果的贡献程度的指标，基尼指数是衡量数据集纯度的指标。

选取最佳特征后，将数据集分为不同的子集，每个子集对应该特征的不同取值。

接下来，对每个子集递归地进行上述过程，直到满足停止条件，例如达到最大深度或数据集纯度达到要求等。

决策树的构建过程中，需要解决的一个重要问题是如何选择最佳特征和阈值。

这需要根据具体的分类问题和数据集的特点进行选择。

在选择特征时，可以使用启发式算法，例如贪心算法，它通过选择当前最佳的特征来进行分割。

对于阈值的选择，一般可以使用二分法或者其他优化算法来确定。

决策树的构建完成后，可以通过对新样本的特征进行判断来进行分类。

从根节点开始，根据样本的特征值和节点的阈值进行判断，进而遍历树的节点，直到达到叶子节点，得到分类结果。

决策树具有很多优点。

首先，决策树易于理解和解释，可以生成直观的规则。

其次，决策树可以处理多类别问题，并且可以处理连续和离散的特征。

此外，决策树可以处理缺失数据，不需要对数据进行预处理。

最后，决策树算法的时间复杂度较低，适合处理大规模的数据集。

然而，决策树也存在一些缺点。

首先，决策树容易出现过拟合问题，特别是当树的深度较大时。

过拟合会导致决策树对训练样本的分类效果很好，但对未知样本的分类效果较差。

为了解决过拟合问题，可以使用剪枝等方法。

其次，决策树对于一些复杂的问题，可能无法找到最优解。

此外，决策树对于数据集中噪声和异常值较为敏感，容易受到干扰。

分类决策树DecisionTreeClassifier详解介绍分类决策树（Decision Tree Classifier）是机器学习中一种常见且易于理解的分类算法。

它通过树状结构来表示实例可能的分类过程，每个内部节点表示一个属性上的判断条件，每个分支代表一个可能的属性值，每个叶节点代表一个分类结果。

下面将详细介绍分类决策树的基本概念、构建过程、优缺点以及实际应用。

一、基本概念1. 决策树：决策树是一种树形结构，其中每个内部节点表示在一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。

2. 根节点：决策树的顶部节点，包含对整个数据集的第一次划分。

3. 内部节点：决策树中的节点，它根据某个属性的值将数据集划分成子集，并且还有子节点。

4. 叶节点：决策树中没有子节点的节点，它表示一个类别或者决策结果。

5. 剪枝：为了防止过拟合，通过去掉决策树的一些分支来简化模型的过程。

二、构建过程分类决策树的构建通常包括以下步骤：1. 特征选择：选择合适的特征进行数据集的划分。

常见的特征选择算法有信息增益、增益率、基尼指数等。

2. 决策树生成：根据选择的特征评估标准，递归地生成决策树。

从根节点开始，对数据集进行划分，生成子节点。

重复此过程，直到满足停止条件（如达到最大深度、节点中样本数小于预设值等）。

3. 决策树剪枝：通过去掉决策树的一些分支来简化模型，防止过拟合。

剪枝策略包括预剪枝和后剪枝。

三、优缺点1. 优点：- 易于理解和解释：决策树的结构直观，易于理解和解释，适合非专业人士使用。

- 对数据预处理要求较低：决策树算法能够处理数值型和离散型数据，不需要过多的数据预处理。

- 能够处理非线性关系：决策树能够自动捕捉特征与目标变量之间的非线性关系。

- 对异常值和缺失值不敏感：决策树算法在一定程度上对异常值和缺失值具有鲁棒性。

2. 缺点：- 容易过拟合：决策树在生成过程中可能会过于复杂，导致过拟合现象。

决策树分类算法⼀、决策树原理决策树是⽤样本的属性作为结点，⽤属性的取值作为分⽀的树结构。

决策树的根结点是所有样本中信息量最⼤的属性。

树的中间结点是该结点为根的⼦树所包含的样本⼦集中信息量最⼤的属性。

决策树的叶结点是样本的类别值。

决策树是⼀种知识表⽰形式，它是对所有样本数据的⾼度概括决策树能准确地识别所有样本的类别，也能有效地识别新样本的类别。

决策树算法ID3的基本思想：⾸先找出最有判别⼒的属性，把样例分成多个⼦集，每个⼦集⼜选择最有判别⼒的属性进⾏划分，⼀直进⾏到所有⼦集仅包含同⼀类型的数据为⽌。

最后得到⼀棵决策树。

J.R.Quinlan的⼯作主要是引进了信息论中的信息增益，他将其称为信息增益（information gain），作为属性判别能⼒的度量，设计了构造决策树的递归算法。

举例⼦⽐较容易理解：对于⽓候分类问题，属性为:天⽓(A1) 取值为：晴，多云，⾬⽓温(A2) 取值为：冷，适中，热湿度(A3) 取值为：⾼，正常风 (A4) 取值为：有风，⽆风每个样例属于不同的类别，此例仅有两个类别，分别为P，N。

P类和N类的样例分别称为正例和反例。

将⼀些已知的正例和反例放在⼀起便得到训练集。

由ID3算法得出⼀棵正确分类训练集中每个样例的决策树，见下图。

决策树叶⼦为类别名，即P 或者N。

其它结点由样例的属性组成，每个属性的不同取值对应⼀分枝。

若要对⼀样例分类，从树根开始进⾏测试，按属性的取值分枝向下进⼊下层结点，对该结点进⾏测试，过程⼀直进⾏到叶结点，样例被判为属于该叶结点所标记的类别。

现⽤图来判⼀个具体例⼦，某天早晨⽓候描述为:天⽓：多云⽓温：冷湿度：正常风：⽆风它属于哪类⽓候呢?-------------从图中可判别该样例的类别为P类。

ID3就是要从表的训练集构造图这样的决策树。

实际上，能正确分类训练集的决策树不⽌⼀棵。

Quinlan的ID3算法能得出结点最少的决策树。

ID3算法：⒈对当前例⼦集合，计算各属性的信息增益；⒉选择信息增益最⼤的属性A k；⒊把在A k处取值相同的例⼦归于同⼀⼦集，A k取⼏个值就得⼏个⼦集；⒋对既含正例⼜含反例的⼦集，递归调⽤建树算法；⒌若⼦集仅含正例或反例，对应分枝标上P或N，返回调⽤处。

决策树分类的基本原理决策树分类是一种常用的机器学习方法，它使用树状结构来对数据进行分类。

决策树分类的基本原理是根据已有的数据样本，通过构建一个树状模型来预测新的数据样本的类别。

决策树分类的过程可以分为三个步骤：特征选择、树的构建和分类。

特征选择是决策树分类的关键步骤。

在特征选择中，我们需要选择最具有分类能力的特征进行分类。

常用的特征选择方法有信息增益、信息增益比、基尼指数等。

信息增益是根据信息熵的变化来选择最佳特征，信息增益比是在信息增益的基础上对特征进行归一化处理，基尼指数则是通过计算数据集的不纯度来选择最佳特征。

树的构建是根据选择的特征来构建决策树模型。

决策树是一种有根有向无环图，它由节点和边组成。

节点分为内部节点和叶节点，内部节点表示特征，叶节点表示类别。

树的构建过程是递归的，从根节点开始，根据选择的特征将数据划分为不同的子集，然后对每个子集递归地构建子树，直到满足停止条件。

分类是将新的数据样本根据构建的决策树模型进行分类。

从根节点开始，根据特征的取值选择相应的子树，直到到达叶节点，然后将叶节点的类别作为预测结果。

决策树分类有以下优点：1. 简单直观：决策树模型易于理解和解释，可以直观地表示数据样本的分类过程。

2. 数据预处理要求低：决策树分类对数据的预处理要求较低，可以处理包含缺失值和离散特征的数据。

3. 可处理多分类问题：决策树分类可以处理多分类问题，不需要额外的修改。

4. 可处理非线性关系：决策树分类可以处理非线性关系的数据，不需要对数据进行线性化处理。

决策树分类也存在一些缺点：1. 容易过拟合：决策树分类容易生成过于复杂的模型，导致过拟合问题。

过拟合会导致模型在训练集上表现良好，但在测试集上表现较差。

2. 不稳定性：决策树分类对数据的微小变化敏感，数据的轻微扰动可能会导致模型发生较大变化。

3. 忽略属性之间的相关性：决策树分类基于特征的独立性假设，忽略了属性之间的相关性。

这可能导致模型对相关性强的特征进行重复划分，造成冗余。

基于专家知识的决策树分类概述基于知识的决策树分类是基于遥感影像数据及其他空间数据，通过专家经验总结、简单的数学统计和归纳方法等，获得分类规则并进行遥感分类。

分类规则易于理解，分类过程也符合人的认知过程，最大的特点是利用的多源数据。

如图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。

决策树及贝叶斯分类实验总结哎呀，说到决策树和贝叶斯分类，简直就像聊一顿大餐，光听名字就已经有点让人捉摸不透。

不过别担心，我们今天就来给它们通通“拆解”了，看它们到底是啥滋味。

先说说决策树。

哎呀，这玩意儿其实不难，想象一下，你有一个复杂的选择，面对一个又一个的问题。

比如你站在商场门口，想决定买不买一双新鞋。

第一个问题是：“这鞋子好不好看？”好看，那就进入下一步；不好看，直接放弃。

可能会问：“这鞋子舒不舒服？”舒适，那就继续走；不舒服，可能就再找找其他的。

这样一层层的筛选，最后就能决定到底买不买。

这不就是决策树的原理嘛！每一个问题就是树上的一个“节点”，而答案就是从这个节点往下走的“分支”。

是不是感觉它特别像是在跟自己对话，一点一点地把选择弄清楚？而贝叶斯分类呢，哎哟，这个就稍微有点像猜谜了。

你可以这么理解，贝叶斯就是一种“相信过去的经验”的方法。

你比如说，假设你每次吃辣椒都会有点胃痛，那下次再看到辣椒时，你的脑袋里就会立马警告：“哎，记住了，这玩意儿对你胃不好哦！”贝叶斯分类也是类似的，它会根据已有的经验数据，不断更新对事物的判断。

就好像每一次你都用历史的经验去做决策，反正就是“过去的事情影响未来”，有点道理吧？我记得做这个实验的时候，我差点就把决策树弄得像个迷宫一样，哈哈！因为每次做出一个选择，心里就开始怀疑：“我这一步走对了吗？”不过慢慢来，发现其实它就是这么简单：从根节点开始，然后一步一步推算，每个问题都像是路标，帮你指引着前进。

只要确定了每一步的规则，整个过程就像是顺风顺水，啥都不难了。

其实最有意思的地方在于，它让你意识到，很多复杂的问题，最后能被拆解成一系列简单的“是”或“否”问题，这种逐步推理的方式，真是妙不可言。

而说到贝叶斯分类，我最初其实有点懵，觉得这个方法就像一位固执的老人，非得把过去的经验拿出来说三道四。

刚开始做实验时，我也总是弄不清楚，怎么用概率来判断这个分类是不是合适。

直到有一天，我忽然意识到：哎，这贝叶斯就跟你打牌一样，你每次看到别人出牌，心里就有一个小算盘：他上次出那张牌是有原因的，那么这次他是不是也会出类似的牌呢？这种基于历史的推测，果然是一个“精准猜测”的好办法！不过，最难的部分还是在于理解它是怎么通过“先验概率”和“后验概率”来计算的。

决策树算法应用和结果解读
决策树算法是一种常见的机器学习算法，广泛应用于分类和回归问题中。

该算法通过构建一棵树形结构，对数据进行有序、层次化的划分，以预测输出结果。

以下是决策树算法的应用和结果解读：
应用：
1. 分类问题：决策树算法可应用于二分类或多分类问题。

通过构建决策树模型，将数据集划分为不同的类别，根据树的节点和分支规则，对新的输入数据进行分类预测。

2. 回归问题：除了分类问题外，决策树算法也可应用于回归问题。

通过构建决策树模型，对连续的输出变量进行预测，根据树的节点和分支规则，对新的输入数据进行回归分析。

结果解读：
1. 树形结构：决策树算法的结果通常以树形结构的形式展示，树中的每个节点代表一个特征或属性测试，分支代表测试结果，叶子节点代表最终的分类或回归结果。

2. 特征重要性：在决策树模型中，每个特征在决策树中的位置和重要性可以被评估和解读。

特征的重要性通常可以通过特征的分裂信息、基尼不纯度等指标来衡量。

3. 分类结果：对于分类问题，决策树的结果可以展示各类别在每个节点上的分布情况，以及每个分支所代表的类别。

通过观察树的节点和分支规则，可以了解不同类别之间的划分依据。

4. 回归结果：对于回归问题，决策树的结果可以展示每个节点的预测值和实际值之间的差异，以及每个分支所代表的预测值范围。

通过观察树的节点和分支规则，可以了解预测值与实际值之间的关系。

总之，决策树算法的应用广泛，结果易于解读。

通过观察决策树的树形结构和特征重要性、分类或回归结果，可以对数据集进行有效的分析和预测。

决策树（三）分类算法⼩结引⾔ 本⽂主要是对分类型决策树的⼀个总结。

在分类问题中，决策树可以被看做是if-then规则的结合，也可以认为是在特定特征空间与类空间上的条件概率分布。

决策树学习主要分为三个步骤：特征选择、决策树的⽣成与剪枝操作。

本⽂简单总结ID3和C4.5算法，之后是决策树的修剪。

ID3算法 ID3算法和核⼼是：在决策树各级节点上选择属性时，⽤信息增益（information gain）作为属性的选择标准，具体做法是：检测所有的属性，选择信息增益最⼤的属性产⽣决策树节点，由该属性的不同取值建⽴分⽀，再对各分⽀循环调⽤该⽅法建⽴决策树节点的分⽀，直到所有⼦集仅包含同⼀类别为⽌。

信息增益 了解信息增益，⾸先介绍熵与条件熵的概念。

熵表⽰随机变量不确定性的度量。

设X是⼀个取有限值的离散随机变量，其概率分布为：p(X=x i)=p i则随机变量X的熵定义为:H(X)=−n∑i=1p i logp i，i=1,2,n由定义可知，熵只依赖于X的分布，⽽与X的取值⽆关。

熵越⼤，随机变量的不确定性越⾼，并且：0⩽当随机变量只有两个取值时，例如0，1，则X的分布为：p(X=1)=p，p(X=0)=1-p， 0\leqslant{p}\leqslant1熵为：H(p)=-plog_2p-(1-p)log_2(1-p)当p=0或p=1时，H(p)=0，随机变量完全没有不确定性，当p=0.5时，H(p)=1，熵取最⼤值，随机变量的不确定性最⼤。

条件熵 设随即变量(X,Y)，其联合概率分布为：P(X=x_i,Y=y_i)=p_{ij},i=1,2,\dots,n;j=1,2,\dots,n条件熵H(Y|X)表⽰在已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵H(Y|X)，定义为X给定的条件下Y的条件概率分布的熵对X的数学期望：H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i)这⾥，p_i=P(X=x_i)信息增益 特征A对训练数据集D的信息增益，定义为集合A的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差：g(D,A)=H(D)-H(D|A)⼩结 ID3算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最⼤的属性进⾏分裂. 其核⼼是：决策树各级结点上选择属性时，⽤信息增益（information gain）作为属性的选择标准，以使得在每⼀个⾮叶结点进⾏测试时，能获得关于被测试记录最⼤的类别信息。