分类决策树的毕业论文

[TOC]

分类：确定对象属于哪个 预定义 的目标类（目标类的总体是已知的）。分类问题中，类标号必须是离散属性，这也是区分分类和回归（regression，回归的目标属性是连续的）的关键特征。

分类，classification，通过学习训练样本得到一个目标函数f（target function），把属性集x映射到预先定义的类标号y。

分类模型（classification model）有两个目的：

分类技术特点：适合描述或预测二元或标称类型的数据集，对序数分类不太有效，因为分类技术不考虑隐含在目标类中的序号关系。（即分类器只负责区分元素们属于哪一类，对于某一类中的元素之间的序关系不做表达）

分类方法：决策树分类法、基于规则的分类法、神经网络、支持向量机和朴素贝叶斯分类法。殊途同归，都是通过学习算法（learning algorithm）从训练数据集提炼一种模型拟合输入数据的类标号和属性之间的联系。

泛化 ：在模型的评估中，泛化是一个重要的概念，它表达通过已知数据建立的模型在应用到未知数据上的时候的有效性。这个泛可以理解为广泛、扩大，从特定的已有的数据一般化到所有的未知的数据。

分类过程：$$训练集（training set)\rightarrow学习模型\rightarrow模型\rightarrow应用模型\rightarrow检验集(test set)$$

模型评估 ：通过正确和错误的记录数量评估，列一个混淆矩阵（confusion matrix）可清晰算得相应的新能度量（performance metric）。

分类模型误差：

模型拟合不足（model underfitting），训练和泛化误差都很大，原因是模型尚未学到数据的真实结构。

模型过分拟合（model overfitting），树的规模持续变大，训练误差持续降低，但泛化误差开始增大。

泛化误差估计

处理（避免）决策树归纳中的过分拟合

本章描述对某一个分类器的性能的评估方法。

本章描述两个或多个分类器之间的对比方法，针对不同分类方法在不同规模的数据集上的准确性比较。即得到不同分类方法在忽略数据量下的性能对比。

任务一：决策树-最佳属性划分度量-连续属性划分算法，实现二分划分点选择算法，考虑连续属性的多路划分的划分点选择算法【深入研究切入点：算法】。

任务二：决策树-决策树归纳算法

任务三：尝试树剪枝

目录 一、决策树算法思想 二、决策树学习本质 三、总结 一、决策树（decision tree）算法思想： 决策树是一种基本的分类与回归方法。本文主要讨论分类决策树。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。 它可以看做是if-then的条件集合，也可以认为是定义在特征空间与类空间上的条件概率分布 。决策树由结点和有向边组成。结点有两种类型：内部结点和叶结点，内部结点表示一个特征或属性，叶结点表示一个类。（椭圆表示内部结点，方块表示叶结点）          决策树与if-then规则的关系 决策树可以看做是多个if-then规则的集合。将决策树转换成if-then规则的过程是：由决策树的根结点到叶结点的每一条路径构建一条规则；路径上的内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥且完备。这就是说，每一个实例都被一条路径或一条规则所覆盖，且只被一条路径或一条规则所覆盖。这里的覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。          决策树与条件概率分布的关系 决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分上。将特征空间划分为互不相交的单元或区域，并在每个单元定义一个类的概率分布，就构成一个条件概率分布。决策树的一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。          决策树模型的优点 决策树模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化原则建立决策树模型；预测时，对新的数据，利用决策树模型进行分类 。二、决策树学习本质： 决策树学习是从训练数据集中归纳一组分类规则、与训练数据集不相矛盾的决策树可能有多个，也可能一个没有。我们需要训练一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。从另一个角度看 决策树学习是训练数据集估计条件概率模型 。基于特征空间划分的类的条件概率模型有无穷多个。我们选择的条件概率模型应该是不仅对训练数据有很好的拟合，而且对未知数据有很好的预测。 决策树的学习使用损失函数表示这一目标，通常的损失函数是正则化的极大似然函数。决策树的学习策略是以损失函数为目标函数的最小化。当损失函数确定后，决策树学习问题变为损失函数意义下选择最优决策树的问题。这一过程通常是一个递归选择最优特征，并根据特征对训练数据进行分割，使得对各个子数据集有一个最好分类的过程。这一过程对应着特征选择、决策树的生成、决策树的剪枝。          特征选择 ： 在于选择对训练数据具有分类能力的特征，这样可以提高决策树的学习效率。          决策树的生成 ： 根据不同特征作为根结点，划分不同子结点构成不同的决策树。          决策树的选择 ：哪种特征作为根结点的决策树信息增益值最大，作为最终的决策树（最佳分类特征）。          信息熵 ： 在信息论与概率统计中，熵是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为P(X= ) = ，i=1，2，3...n，则随机变量X的熵定义为         H(X) =  —  ，0 <=  H(X) <= 1，熵越大，随机变量的不确定性就越大。         条件熵（Y|X） ： 表示在已知随机变量X的条件下随机变量Y的不确定性。          信息增益  ： 表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。         信息增益  = 信息熵(父结点熵 ) — 条件熵（子结点加权熵） 三、 总结 ：         优点         1、可解释性高，能处理非线性的数据，不需要做数据归一化，对数据分布没有偏好。         2、可用于特征工程，特征选择。         3、可转化为规则引擎。         缺点         1、启发式生成，不是最优解。         2、容易过拟合。         3、微小的数据改变会改变整个数的形状。         4、对类别不平衡的数据不友好。