数据挖掘---分类:基本概念、决策树、与模型评估

分类：基本概念、决策树与模型评估 分类任务就是确定对象属于那个预定义的目标类。就是通过学习得到一个目标函数f,把每个属性集映射到一个预先定义的类标号y. 一、预备知识 分类任务的输入数据是记录的集合，每条记录称为实例，用元组（x,y)表示，其中x是属性的集合，y是一个特殊的集合。  描述性建模：分类模型可以作为解释性工具,用于区分不同类中的对象. 预测性建模:分类模型还可以用于预测未知记录的类标号. 二.解决分类问题的一般方法 分类法的例子包括决策树法、基于规则的分类法、神经网络、支持向量机和朴素贝叶斯分类法。 分类模型的性能根据模型正确和错误预测的检验记录计数进行评估，这些计数存放在称作混淆矩阵的表格中。准确性=正确预测数/预测总数。 差错率：错误预测数/预测总数。 三。决策树归纳 1。决策树工作原理 树中包换三种结点： 根结点：它没有入边，但有零条或多条出边。 内部结点：恰有一条入边和两条或多条出边。 叶结点：恰有一条入边，但没有出边。 其中，每个叶结点都赋予一个类标号，非终结点（包括根结点和内部结点）包含属性测试条件，用以分开具有不同特性的记录。一旦构造了决

策树，对检验记录进行分类就是直截了当的，从树的根结点出发，将测试条件用于检验记录，根据测试结果选择适当的分支，沿着该分支或者

达到另一个内部结点，使用新的测试条件或者达到一个叶结点，叶结点的类称号就被赋值给该检验记录。 2。如何建立决策树 对于给定的属性集，可以构造的决策树数目达指数级，找出最佳的决策树在计算上是不可行的，所以通常采用贪心算法，采取一系列局部最优

决策来构造决策树。Hunt算法就是其中一种。 *Hunt算法 Hunt算法通过将训练记录相继划分成较纯的子集，以递归方式建立决策树。 决策树归纳设计问题必须解决以下两个问题：如何分裂训练记录和如何停止分裂过程。 3。表示属性测试条件的方法 二元属性：二元属性的测试条件产生两个可能的输出。 标称属性：由于标称有多个属性值，它的测试条件可以用两种方法表示，多路划分和二元划分（如：CART方法） 充数属性：也可以产生二元或多路划分。 连续属性：测试条件可以具有二元输出的比较测试（A<v)或(A>=v)，也可以是具有形如：vi<=A<vi+1来划分输出的范围查询。 4。选择最佳划分的度量 为了确定测试条件的效果，需要比较父结点（划分前）的不纯程度和子女结点（划分后）的不纯程度，它们的差越大，测试条件的效果就越好

。 5。决策树归纳的特点： *决策树归纳是一种构建分类模型的非参数方法。 *找到最佳的决策树是NP完全问题。 *已开发的构建决策树技术不需要昂贵的计算代价。 *决策树相对容易解释，特别是小型的决策树。 *决策树是学习离散值函数的典型代表。 *决策树对于噪声有良好的鲁棒性。 *冗余属性不会对决策的准确率造成不利的影响。 *存在着数据碎片的问题。 *子树可能在决策树中重复多次。 四。模型的过分拟合 分类模型的误差大致分为两种：训练误差和泛化误差。一个好的分类模型不仅要能够很好地拟合训练数据，而且对未知样本也要能准确地分类

。然而，对训练集数据拟合太好的模型，其泛化误差可能比具有较高训练误差的模型高，这就是所谓的模型过分拟合。 1。噪声导致的过分拟合 也就是训练集中有被错误分类的记录。 2。缺乏代表性样本导致的过分拟合 3。过分拟合与多重比较过程 要增加一个属性测试条件，是从候选的属性集中挑一个使得增益大于某个阈值的一个属性，这样算法就会在模型上增加一些欺骗性的结点，导

致过分拟合。 4。泛化误差估计 *使用再代入估计：假设训练数据集可以很好的代表整体数据，因而可以使用训练误差提供对泛化误差的乐观估计。 *结合模型复杂度：如前所述，模型越是复杂，出现过分拟合的几率就越高，因此我们更喜欢较为简单的模型。这种策略与Occam剃刀或节俭原

则一致，Occam剃刀：给定两个具有相同泛化误差的模型，较简单的模型比较复杂的模型更可取。 五。评估分类器的性能 1。保持方法：将被标记的原始数据划分成两个不相交的集合，分别称为训练集和检验集，在训练集上归纳分类模型，在检验集上评估模型的性

能。 2。随机二次抽样：可以多次重复保持方法来改进对分类器性能的估计。 3。交叉验证：每个记录用于训练的次数相同，并且用于检验恰好一次。