分类、决策树与模型评估

• 分类
• 决策树
• 分类算法

分类

分类就是通过学习一个目标函数F，把每个属性集x映射到一个预先定义好的类标号y上。目标函数也被称为分类模型。

建模分为两种目的，一种是描述性建模一种是预测性建模。


对于学习算法，我们将一部分数据分为训练集和测试集，一般训练集占比70%测试集占总体数据集的30%。通过对训练集的学习训练建立一个适合处理对应一类数据的模型，然后将这个模型套用到测试集上，来观察数据的处理效果，根据是否能得到预期重新评价模型，决定是否要继续训练或者改变训练集比例。
混淆矩阵是一个用来测试训练准确性的工具之一。
只有预测结果和实际结果一致，才证明这是一个好的分类。
那么现在来介绍最基本的一些分类方法，主要内容来源于教材数据挖掘导论。

决策树

分类算法

分类
基本概念
分类：一种数据分析形式，它提取刻画重要数据类的模型。这种模型叫分类器，进而预测分类的（离散的、无序的）类标号。

相关概念解释

训练集：由数据库元组和与它们相关联的类标号组成。
元组X用n维属性向量x=x1,x2,x3……xn)表示，分别描述元组在n维数据库中的n个属性值的集合。
每个元组都可预先定义为一个类，由一个称为类标号属性的数据库属性确定。
类标号属性：是离散的和无序的。它是分类的（标称的。标称属性的值仅仅只是不同的名字，以区分不同对象）。因为每个值充当一个类别或类。
数据元组也称为：样本、记录、实例、对象、数据点。
属性值也称：变量、特征、字段、维。
属性的数量称为维度。
由训练集所得到的学习模型：可用分类规则、决策树、数学公式的形式表示。
第一步 建立模型（可看作学习一个函数y=fx)，它可预测给定元组X的类标号y。）

第二步 检验模型并用于新的分类（由检验集评估分类器的准确率，再应用于新的数据进行分类）

如上图分类的预测任务，首先通过已有的数据集（训练集）进行训练学习，得到一个目标函数（学习模型或分类规则），再通过检验集的数据对该模型的准确度评估，若通过评估，则该规则应用于新的数据元组分类。

分类器在给定检验集上的准确率是指分类器正确分类的检验元组所占的百分比。通过每个检验元组的类标号与学习模型对该元组的类预测进行比较。

监督学习 （用于分类）
即分类器的学习，是在已知每个训练元组的类别的“监督下”进行的。
无监督学习（用于聚类）
每个训练元组的类标号未知，并且学习的类的个数和集合也可能是事先未知的。

什么是决策树？
类似于流程图的树结构
每个内部节点表示在一个属性上的测试
每个分枝代表一个测试输出
每个树叶节点存放一个类编号
决策树：Buys_computer

决策树是如何分类的？
给定一个类标号未知的元组X，在决策树上测试元组的属性值，跟踪一条由根到叶节点的路径，叶节点存放该元组的类预测。
决策树的生成由两个阶段组成
决策树构建
1.) 使用属性选择度量来选择属性，使元组能最好的划分为不同的类。
2.) 递归的通过选定属性，来划分样本（必须是离散值）。
树剪枝
1.) 决策树建立时，许多分枝反映的是训练数据中的噪声和离群点点，树剪枝试图识别并剪去这种分枝，以提高对未知数据分类的准确性。
决策树的基本算法

算法主要步骤：
以训练样本的单个节点N开始；
如果样本都在同一类，则该节点成为树叶，并用该类标记。
否则，算法调用Attribute_selection_method（属性选择度量），选择能够最好的将样本分类的属性，确定“分裂准则”，指出“分裂点”或“分裂子集”；
对测试属性每个已知的值，创建一个分支，并以此划分元组；
算法使用同样的过程，递归的形成每个划分上的元组决策树。一旦一个属性出现在一个节点上，就在该节点的子节点上删除；
递归划分步骤停止的条件

情形1)：划分D（在N节点提供）的所有元组属于同一类
情形2)：当前属性集为空，或所有样本在所有属性上取值相同，无法划分。
情形3)：没有剩余的样本。
给定分支没有元组，则以D中多数类创建一个树叶
注：整个决策树建立的关键是：属性选择的度量，也是算法的核心

1. 属性选择度量（分裂准则）

问题： 如何选择元组的属性进行优先建树，使得将所有训练元组能最好的划分？？（也即使决策树简单）。
eg. 女生约会是否见男生。eg. 明天是否打球案例。

理想的划分是，使每个划分都是“纯”的，即落在给定划分内的元组都属于同一类。
2. 常用的属性选择度量

信息增益
增益率
Gini指数
3. 使用符号如下：
设数据分区D为标记类元组的训练集，类标号属性具有m个不同值，定义了m个不同类Cii=1,2,3…，m)，设Ci, D 是D中Ci类元组的集合，|D|和|Ci, D|分别是D和Ci, D中元组的个数。

信息增益
ID3算法使用信息增益作为属性选择度量。它是基于香农的信息论，对信息进行度量的方法。（可参考信息论的文章xxx）。
设节点N存放分区D的元组，选择具有最高信息增益的属性作为节点N的分裂属性。该属性使最终的结果分区中对元组分类所需要的信息量最小。这种方法使得对一个元组进行分类的测试数目最小，并确保找到一颗简单的树。

对D中元组分类所需要的期望信息由下式计算：

其中，Pi是D中任意元组属于类Ci的非零概率，用|Ci, D|/|D|估计。用到信息论里面的自信息量公式，表示事件x发生前，事件发生的不确定性，或事件发生后，所得到信息量。
Info（D）是对D中所有元组分类所需要的期望信息（平均信息量）。也称为D的熵。熵是随机变量平均不确定度的度量，同时它也代表了消除随机变量不确定度所需获得的信息量。

若我们对属性A进行划分元组D，其中A具有v个不同值{a1,a2,a3…，av}，若A是离散值，则对应有v个输出，可以用属性A将D划分为v个分区或子集{D1,D2,D3,…Dv}，Dj包含D中的元组，它们的属性值都为aj。为了得到准确分类，还需要多少信息量？由下式计算：

是第j个分区的权重。
是基于按A划分对D的元组分类所需要的期望信息。

信息增益：原来的信息需求与新的信息需求（对A划分后）之间的差。
Gain（A）=Info（D）-InfoA（D），即对A划分后所获得的信息量。所以选择最高信息增益Gain（A）的属性A作为节点N的分裂属性。等价于在“能做最佳分类”的属性A上划分，使得完成剩余元组的划分所需要的信息量最小。

例题：

-|
分类算法|
NBC算法|
LR算法|
SVM算法|
ID3算法|
C4.5 算法|
C5.0算法|
KNN 算法|
ANN 算法|
分类算法|
分类是在一群已经知道类别标号的样本中，训练一种分类器，让其能够对某种未知的样本进行分类。分类算法属于一种有监督的学习。分类算法的分类过程就是建立一种分类模型来描述预定的数据集或概念集，通过分析由属性描述的数据库元组来构造模型。分类的目的就是使用分类对新的数据集进行划分，其主要涉及分类规则的准确性、过拟合、矛盾划分的取舍等。分类算法分类效果如图所示。

常用的分类算法包括：NBC（Naive Bayesian Classifier，朴素贝叶斯分类）算法、LR（Logistic Regress，逻辑回归）算法、ID3（Iterative Dichotomiser 3 迭代二叉树3 代）决策树算法、C4.5 决策树算法、C5.0 决策树算法、SVM（Support Vector Machine，支持向量机）算法、KNNK-Nearest Neighbor，K 最近邻近)算法、ANN（Artificial Neural Network，人工神经网络）算法等。

NBC算法
NBC 模型发源于古典数学理论，有着坚实的数学基础。该算法是基于条件独立性假设的一种算法，当条件独立性假设成立时，利用贝叶斯公式计算出其后验概率，即该对象属于某一类的概率，选择具有最大后验概率的类作为该对象所属的类。
NBC算法的优点

NBC算法逻辑简单，易于实现；
NBC算法所需估计的参数很少；
NBC 算法对缺失数据不太敏感；
NBC 算法具有较小的误差分类率；
NBC 算法性能稳定，健壮性比较好；
NBC算法的缺点
1.在属性个数比较多或者属性之间相关性较大时，NBC 模型的分类效果相对较差；
2.算法是基于条件独立性假设的，在实际应用中很难成立，故会影响分类效果

LR算法
LR 回归是当前业界比较常用的机器学习方法，用于估计某种事物的可能性。它与多元线性回归同属一个家族，即广义线性模型。简单来说多元线性回归是直接将特征值和其对应的概率进行相乘得到一个结果，逻辑回归则是在这样的结果上加上一个逻辑函数。在此选择LR 作为回归分析模型的代表进行介绍。
LR算法的优点
1.对数据中小噪声的鲁棒性好；
2.LR 算法已被广泛应用于工业问题中；
3.多重共线性并不是问题，它可结合正则化来解决。

LR算法的缺点
1.对于非线性特征，需要转换
2.当特征空间很大时，LR的性能并不是太好

SVM算法
SVM 算法是建立在统计学习理论基础上的机器学习方法，为十大数据挖掘算法之一。通过学习算法，SVM 可以自动寻找出对分类有较好区分能力的支持向量，由此构造出的分类器可以最大化类与类的间隔，因而有较好的适应能力和较高的分准率。SVM 算法的目的在于寻找一个超平面H，该超平面可以将训练集中的数据分开，且与类域边界的沿垂直于该超平面方向的距离最大，故SVM 法亦被称为最大边缘算法。

SVM算法的优点
1.SVM 模型有很高的分准率；
2. SVM 模型有很高的泛化性能；
3. SVM 模型能很好地解决高维问题；
4. SVM 模型对小样本情况下的机器学习问题效果好。

SVM算法的缺点
1.SVM 模型对缺失数据敏感；
2.对非线性问题没有通用解决方案，得谨慎选择核函数来处理。

ID3算法
ID3 算法是一种基于决策树的分类算法，该算法是以信息论为基础，以信息熵和信息增益为衡量标准，从而实现对数据的归纳分类。信息增益用于度量某个属性对样本集合分类的好坏程度。ID3 算法的时间复杂度为On*|D|*log|D|)。

ID3算法的优点

ID3 算法建立的决策树规模比较小；
查询速度快。
ID3算法的缺点
1.不适合处理连续数据；
2.难以处理海量数据集；
3.建树时偏选属性值较大的进行分离，而有时属性值较大的不一定能反应更多的数据信息。

C4.5 算法
C4.5 算法是ID3 算法的修订版，采用信息增益率来加以改进，选取有最大增益率的分割变量作为准则，避免ID3 算法过度的适配问题。

C4.5算法优点
1.C4.5 继承了ID3 优点；
2.在树构造过程中进行剪枝；
3.能对不完整数据进行处理；
4.能够完成对连续属性的离散化处理；
5.产生的分类规则易于理解，准确率较高；
6.用增益率来选择属性，克服了用增益选择属性时偏向选择取值多的属性。

C4.5 算法缺点
1.构造树时，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效；
2.只适合于能驻留于内存的数据集，当训练集达到内存无法容纳时程序无法运行。

C4.5 用于遥感分类过程中，首先依据通常的方式建立第一个模型。随后建立的第二个模型聚焦于被第一个模型错误分类的记录。以此类推，最后应用整个模型集对样本进行分类，使用加权投票过程把分散的预测合并成综合预测。Boosting 技术对于噪声不大的数据，通常通过建立的多模型来减少错误分类的影响，提高分类精度。

C5.0算法
C5.0 算法是 Quinlan 在C4.5 算法的基础上改进而来的产生决策树的一种更新的算法，它除了包括C4.5 的全部功能外，还引入许多新的技术，其中最重要的技术是提升（Boosting）技术，目的是为了进一步提高决策树对样本的识别率。同时C5.0 的算法复杂度要更低，使用更简单，适应性更强，因此具有更高的使用价值。

C5.0算法的优点
1.C5.0 模型能同时处理连续和离散的数据
2.C5.0 模型估计
模型通常不需要很长的训练时间；
3.C5.0 引入Boosting 技术以提高分类的效率和精度；
4.C5.0 模型易于理解，模型推出的规则有非常直观的解释；
5.C5.0 模型在面对数据遗漏和特征很多的问题时非常稳健。

C5.0算法的缺点
目标字段必须为分类字段。

美国地质调查局USGS)在进行土地覆盖分类项目过程中研发了支持决策树分类的软件。软件分类模块主要是针对庞大数据量的数据集进行数据挖掘，找出特征，然后建立规则集进行决策分类。在分类模块中采用C5.0 模型来完成决策树分类、形成分类文件，实现遥感影像的分类。

KNN 算法
KNN 算法是Cover 和Hart 于1968 年提出的理论上比较成熟的方法，为十大挖掘算法之一。该算法的思路非常简单直观：如果一个样本在特征空间中的k 个最相似即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

KNN算法的优点
1.KNN 算法简单、有效；
2.KNN 算法适用于样本容量比较大的类域的自动分类；
3.由于KNN 方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN 方法较其他方法更为适合。

KNN算法的缺点
1.KNN 算法计算量较大；
2.KNN 算法需要事先确定K 值；
3.KNN 算法输出的可解释不强；
4. KNN 算法对样本容量较小的类域很容易产生误分。

ANN 算法
人工神经网络（ANN）算法就是一组连续的输入/输出单元，其中每个连接都与一个权相关。在学习阶段，通过调整神经网络的权，使得能够预测样本的正确类标号来学习。

ANN算法的优点
1.能处理数值型及分类型的属性；
2.分类的准确度高，分布并行处理能力强；
3.对包含大量噪声数据的数据集有较强的鲁棒性和容错能力。

ANN算法的缺点
1.不能观察之间的学习过程；
2.学习时间过长，甚至可能达不到学习的目的；
3.对于非数值型数据需要做大量数据预处理工作；
4.输出结果难以解释，会影响到结果的可信度和可接受程度；
5.神经网络需要大量的参数，如网络拓扑结构、权值和阈值的初始值。

小结：

算法名称	收敛时间	是否过度拟合	是否过渡拟合缺失数据敏感度	训练数据量
NBC	快	存在	不敏感	无要求
LR	快	存在	敏感	无要求
SVM	一般	存在	敏感	小数据量
ID3	快	存在	不敏感	小数据集
C4.5	快	存在	不敏感	小数据集
C5.0	快	不存在	不敏感	大数据集
ANN	慢	存在	敏感	大数据集
KNN	快	存在	敏感	数据量多