数据挖掘之决策树与决策规则

基于决策树模型及其规则的构建，在实际应用中解决分类问题的数据挖掘方法具有显著优势。通常情况下，在数据挖掘领域中进行分类任务时会涉及到构建一个映射关系X \rightarrow Y（其中X代表输入属性值向量集合），该映射关系旨在将每一个实例（即特定属性值向量）与对应的类别目标建立联系。对于给定属性值向量以及对应的目标类别，在采用归纳学习算法的情况下，每个实例会被分配到该样本集中的特定类别。换句话说，在数据挖掘中进行分类时会根据属性值预测某个实体所属的具体类别。

2. 具有N个特征的数据集可被视为N维空间中的离散点集。

3. 决策树
   基于数据生成分类器的一种高效方法是构建决策树——通过输入输出样本对决策树进行有指导学习构建的过程非常有效——它是一种非参数化模型——它通过一系列检验函数建立分支结构以识别局部区间——这种模型没有对类分布做出任何假设参数形式——典型的决策树学习系统采用自上而下的搜索策略——在有限搜索空间中寻求解决方案——该方法能够保证找到一个简单有效的决策树——但未必是最简单的
   一种著名的一元分支决策树构建算法是ID3算法——其改进版本C4.5算法采用贪婪搜索策略用于构建决策树结构——通常应用于这类算法以探测可行模型的空间
   当运行ID3算法时，默认所有训练样本位于决策树的根节点位置——该算法选择一个属性来区分这些样本并为每个属性创建一个分支子节点——如果某样本自身属性值等于分支指定值则该样本移至相应子节点上——递归应用此过程直到某个子节点仅包含同一类样本为止
   ID3算法的扩展版本C4.5将分类范围从类别属性扩展到了数值属性

4. 为了应用基于归纳学习的方法，则需要满足若干关键条件
   属性值的具体表示方式决定了分析数据必须呈现平面稳健形式
   每个样本的所有信息都必须通过固定的属性集合来进行描述
   预先设定类别时，则需确保样本能够被精确划分到相应的类别中
   明确分类规则的前提下，则需保证充足的样本数据
   能够有效地归纳总结出规律性的模式
   仅能通过决策树或决策规则的形式来进行分类器的设计

5. C4.5算法
   C4.5算法最重要的部分是由训练样本集生成初始决策树的过程，该算法生成了一个决策树形式的分类器，决策树是具有两类节点的结构：叶节点表示一个类，决策节点指定要在单个属性值上进行检验，对检验的每个可能输出都有一个分支或子树
   决策树可以用来对新样本进行分类，这种分类从属的根节点开始移动样本，直至移动到叶节点为止，在每个非叶决策节点处，都要确定该节点的特征检验结果，然后考虑所选子树的根节点
   C4.5一般包含三种类型的检验结构：
   A：离散属性的“标准”检验，对属性的每个可能值有一个分支和输出
   B: 如果属性Y有连续的数值，则比较该值和阈值
   C: 更复杂的检验也基于离散值，在该检验中，属性的每个可能值都分配到数量可变的组中，每组都有一个输出和分支
   6.未知属性值
   C4.5算法的前一个版本基于一个假设，：所有属性值都已确定，但在数据集中，经常会缺少某些样本的一些属性值，这种不完全性在实际应用中非常常见，其原因是属性值和某个样本是不相关的，或搜集数据时没有记录，或把数据输入数据库时有人为的误差，为了解决丢失值，有两种选择：
   A: 抛弃数据库中有丢失数据的样本
   第一个解决方法很简单，但是如果样本集中存在大量的丢失值时，不能采用这种方法
   B: 定义新的算法，或改进现有的算法，来处理丢失的数据
   在试图解决丢失值时，总是会引发一些问题，丢失数据的几种通类方法通常是用最可能的值替代缺失值，或考虑该属性的所有值的概率分布，但是所有的这些方法都不太好，在C4.5算法中，普遍使用的法则是有未知值的样本按照已知值的相对频率随机分布

6. 修剪决策树
   决策树剪枝的主要目标是去除部分子树，并以叶子节点替代这些子树以简化整个决策树结构，在剪裁子树并以叶子节点替代的过程中, 算法应尽量降低预测误差率, 提高分类模型的质量.
   构建决策树的基本思路在于去除那些对未知测试样本分类精度无显著帮助的分支, 从而生成一个更为简单易懂的模型, 并且有两种改进型递归分割方法:
   A: 在某些特定情况下, 不进行样本集的细致分割
   剪裁准则通常基于一些统计检验标准, 当分割前后分类精度差异不明显时, 就将当前节点标记为叶子节点. 由于剪裁操作是在分割前执行的, 因此该方法属于预剪枝过程.
   B: 在构建好一棵完整的决策树之后, 再通过选定的误差评估标准进行反向逐步剪裁某些节点
   这种剪裁操作是在构建完成后进行的, 因此被称为后剪枝过程.
   C4.5算法采用的是后剪枝策略, 并且采用了特殊的方法来估计预测误差率, 这种策略被称为悲观性剪枝.

7. C4,5算法：生成决策规则
   虽然修剪后的决策树比原来的更简洁，他们仍然非常复杂，大决策树很难理解，因为每个节点都有根据先行节点的检验结果建立的具体环境，为了使决策树模型更易读，可以把到达每个叶的路径转换成IF-THEN生成规则
   9.C5.0算法
   相比于C4.5，提供了推进技术的一个实体，他会构建全套的分类器，再选择出最终的分类，同时，包含了新的数据类型，例如日期，可以处理“不适用的”值，提出了可变误分类成本的概念，提供了预过滤属性机制

8. CART算法和Gini指标
   分类回归树（CART），同样适用于构建决策树的方法也用于CART（即分而治之的基本方法），其主要区别在于树的结构、分区准则、修剪方法以及处理缺失值的方式。
   CART构建的树仅限于二元分割，在这种限制下简化了分区准则的应用场景（因为无需考虑多元分割）。然而，在某些情况下同一属性可能在不同的层级上被多次分割（这使得模型解释起来更加复杂）。此外，在选择划分准则时使用的是Gini多样性指数（代替基于信息增益的方法），这种替代使模型能够更好地考虑对称误判成本，并且计算效率更高。

9. 决策树决策规则的局限性
   基于决策规则和决策树模型的优点在于其简单易懂且生成速度非常快；其核心优势在于不受属性值分布或属性独立性假设的影响；这种方法在实际应用中往往比其他多数统计方法更为可靠；然而也需要注意以下几点：正确的模型选择对于数据挖掘的成功至关重要；
   如果将数据样本绘制到N维空间中进行分析（其中N表示特征数量）