摘要       本文介绍了在数据挖掘中数据分类的几个主要分类方法，包括：贝叶斯分类、决策树分类、感知器分类，及其各自的优势与劣势。并对于分类问题中出现的高维效应，介绍了两种通用的解决办法。
关键词   数据分类  贝叶斯分类  决策树分类  感知器分类
 
 
引言
数据分类是指按照分析对象的属性、特征，建立不同的组类来描述事物。数据分类是数据挖掘的主要内容之一，主要是通过分析训练数据样本，产生关于类别的精确描述。这种类别通常由分类规则组成，可以用来对未来的数据进行分类和预测。分类技术解决问题的关键是构造分类器。
一．数据分类
数据分类一般是两个步骤的过程：
第1步：建立一个模型，描述给定的数据类集或概念集（简称训练集）。通过分析由属性描述的数据库元组来构造模型。每个元组属于一个预定义的类，由类标号属性确定。用于建立模型的元组集称为训练数据集，其中每个元组称为训练样本。由于给出了类标号属性，因此该步骤又称为有指导的学习。如果训练样本的类标号是未知的，则称为无指导的学习（聚类）。学习模型可用分类规则、决策树和数学公式的形式给出。
第2步：使用模型对数据进行分类。包括评估模型的分类准确性以及对类标号未知的元组按模型进行分类。
常用的分类规则挖掘方法
分类规则挖掘有着广泛的应用前景。对于分类规则的挖掘通常有以下几种方法，不同的方法适用于不同特点的数据：
1．贝叶斯方法
2．决策树方法
3．人工神经网络方法
4．约略集方法
5．遗传算法
分类方法的评估标准：
准确率：模型正确预测新数据类标号的能力。
速度：产生和使用模型花费的时间。
健壮性：有噪声数据或空缺值数据时模型正确分类或预测的能力。
伸缩性：对于给定的大量数据，有效地构造模型的能力。
可解释性：学习模型提供的理解和观察的层次。
影响一个分类器错误率的因素
(1) 训练集的记录数量。生成器要利用训练集进行学习，因而训练集越大，分类器也就越可靠。然而，训练集越大，生成器构造分类器的时间也就越长。错误率改善情况随训练集规模的增大而降低。
(2) 属性的数目。更多的属性数目对于生成器而言意味着要计算更多的组合，使得生成器难度增大，需要的时间也更长。有时随机的关系会将生成器引入歧途，结果可能构造出不够准确的分类器（这在技术上被称为过分拟合）。因此，如果我们通过常识可以确认某个属性与目标无关，则将它从训练集中移走。
(3) 属性中的信息。有时生成器不能从属性中获取足够的信息来正确、低错误率地预测标签（如试图根据某人眼睛的颜色来决定他的收入）。加入其他的属性（如职业、每周工作小时数和年龄），可以降低错误率。
(4) 待预测记录的分布。如果待预测记录来自不同于训练集中记录的分布，那么错误率有可能很高。比如如果你从包含家用轿车数据的训练集中构造出分类器，那么试图用它来对包含许多运动用车辆的记录进行分类可能没多大用途，因为数据属性值的分布可能是有很大差别的。
评估方法
有两种方法可以用于对分类器的错误率进行评估，它们都假定待预测记录和训练集取自同样的样本分布。
(1) 保留方法(Holdout)：记录集中的一部分（通常是2/3）作为训练集，保留剩余的部分用作测试集。生成器使用2/3 的数据来构造分类器，然后使用这个分类器来对测试集进行分类，得出的错误率就是评估错误率。
虽然这种方法速度快，但由于仅使用2/3 的数据来构造分类器，因此它没有充分利用所有的数据来进行学习。如果使用所有的数据，那么可能构造出更精确的分类器。
(2) 交叉纠错方法(Cross validation)：数据集被分成k 个没有交叉数据的子集，所有子集的大小大致相同。生成器训练和测试共k 次；每一次，生成器使用去除一个子集的剩余数据作为训练集，然后在被去除的子集上进行测试。把所有得到的错误率的平均值作为评估错误率。
交叉纠错法可以被重复多次(t)，对于一个t 次k 分的交叉纠错法，k ＊t 个分类器被构造并被评估，这意味着交叉纠错法的时间是分类器构造时间的k ＊t 倍。增加重复的次数意味着运行时间的增长和错误率评估的改善。我们可以对k 的值进行调整，将它减少到3 或5，这样可以缩短运行时间。然而，减小训练集有可能使评估产生更大的偏差。
通常Holdout 评估方法被用在最初试验性的场合，或者多于5000 条记录的数据集；交叉纠错法被用于建立最终的分类器，或者很小的数据集。
 
二．贝叶斯分类
贝叶斯分类方法是一种具有最小错误率的概率分类方法，可以用数学公式的精确方法表示出来，并且可以用很多种概率理论来解决。
设（Ω,Θ,P）为概率空间，Ai∈Θ（i=1,2,…,n）为Ω的一个有穷剖分，且P(Ai)>0 (i=1,2,…,n)，则对任意B∈Θ且P(B)>0，有
 
 
P(Ai|B)=   
   
 （i=1,2,…,n）
 
上式称为贝叶斯公式。
贝叶斯定理为我们提供了一个计算假设h的后验概率的方法
 
P(h|D)=

 
分类有规则分类和非规则分类，贝叶斯分类是非规则分类，它通过训练集训练而归纳出分类器，并利用分类器对没有分类的数据进行分类。
贝叶斯分类的特点
贝叶斯分类具有如下特点：
(1) 贝叶斯分类并不把一个对象绝对地指派给某一类，而是通过计算得出属于某一类的概率，具有最大概率的类便是该对象所属的类；
(2) 一般情况下在贝叶斯分类中所有的属性都潜在地起作用，即并不是一个或几个属性决定分类，而是所有的属性都参与分类；
(3) 贝叶斯分类对象的属性可以是离散的、连续的，也可以是混合的。
贝叶斯定理给出了最小化误差的最优解决方法，可用于分类和预测。理论上，它看起来很完美，但在实际中，它并不能直接利用，它需要知道证据的确切分布概率，而实际上我们并不能确切的给出证据的分布概率。因此我们在很多分类方法中都会作出某种假设以逼近贝叶斯定理的要求。
 
三．决策树分类
决策树（ Decision Tree ）又称为判定树，是运用于分类的一种树结构。其中的每个内部结点（ internal node ）代表对某个属性的一次测试，每条边代表一个测试结果，叶结点（ leaf ）代表某个类（ class ）或者类的分布（ class
 distribution ），最上面的结点是根结点。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。
构造决策树是采用自上而下的递归构造方法。决策树构造的结果是一棵二叉或多叉树，它的输入是一组带有类别标记的训练数据。二叉树的内部结点（非叶结点）一般表示为一个逻辑判断，如形式为 (a = b) 的逻辑判断，其中 a 是属性， b 是该属性的某个属性值；树的边是逻辑判断的分支结果。多叉树（ ID3 ）的内部结点是属性，边是该属性的所有取值，有几个属性值，就有几条边。树的叶结点都是类别标记。
使用决策树进行分类分为两步：
第 1 步：利用训练集建立并精化一棵决策树，建立决策树模型。这个过程实际上是一个从数据中获取知识，进行机器学习的过程。
第 2 步：利用生成完毕的决策树对输入数据进行分类。对输入的记录，从根结点依次测试记录的属性值，直到到达某个叶结点，从而找到该记录所在的类。
问题的关键是建立一棵决策树。这个过程通常分为两个阶段：
(1) 建树（ Tree Building ）：决策树建树算法见下，可以看得出，这是一个递归的过程，最终将得到一棵树。
(2) 剪枝（ Tree Pruning ）：剪枝是目的是降低由于训练集存在噪声而产生的起伏。
决策树方法的评价。
优点
与其他分类算法相比决策树有如下优点：
(1) 速度快：计算量相对较小，且容易转化成分类规则。只要沿着树根向下一直走到叶，沿途的分裂条件就能够唯一确定一条分类的谓词。
(2) 准确性高：挖掘出的分类规则准确性高，便于理解，决策树可以清晰的显示哪些字段比较重要。
缺点
一般决策树的劣势：
(1) 缺乏伸缩性：由于进行深度优先搜索，所以算法受内存大小限制，难于处理大训练集。一个例子：在 Irvine 机器学习知识库中，最大可以允许的数据集仅仅为 700KB ， 2000 条记录。而现代的数据仓库动辄存储几个 G-Bytes 的海量数据。用以前的方法是显然不行的。
(2) 为了处理大数据集或连续量的种种改进算法（离散化、取样）不仅增加了分类算法的额外开销，而且降低了分类的准确性，对连续性的字段比较难预测，当类别太多时，错误可能就会增加的比较快，对有时间顺序的数据，需要很多预处理的工作。
但是，所用的基于分类挖掘的决策树算法没有考虑噪声问题，生成的决策树很完美，这只不过是理论上的，在实际应用过程中，大量的现实世界中的数据都不是以的意愿来定的，可能某些字段上缺值（ missing values ）；可能数据不准确含有噪声或者是错误的；可能是缺少必须的数据造成了数据的不完整。
另外决策树技术本身也存在一些不足的地方，例如当类别很多的时候，它的错误就可能出现甚至很多。而且它对连续性的字段比较难作出准确的预测。而且一般算法在分类的时候，只是根据一个属性来分类的。
在有噪声的情况下，完全拟合将导致过分拟合（ overfitting ），即对训练数据的完全拟合反而不具有很好的预测性能。剪枝是一种克服噪声的技术，同时它也能使树得到简化而变得更容易理解。另外，决策树技术也可能产生子树复制和碎片问题。
 
四．感知器分类
感知器是由具有可调节的键结值以及阈值的单一个类神经元所组成，它是各种类神经网络中，最简单且最早发展出来的类神经网络模型，通常被用来作为分类器使用。感知器的基本组成元件为一个具有线性组合功能的累加器，后接一个硬限制器而成，如图 4.1 所示。

        
 
 

图4.1
单层感知器是一个具有一层神经元、采用阈值激活函数的前向网络。通过对网络权值的训练，可以使感知器对一组输入矢量的响应达到元素为0或1的目标输出，从而达到对输入矢量分类的目的。
分类的判断规则是：若感知器的输出为1，则将其归类于C1类；若感知器的输出为0，则将其归类于C2类。判断规则所划分的只有两个判断区域，我们将作为分类依据的超平面定义如下：
                                  
 

感知器分类是通过训练模式的迭代和学习算法，产生线性或非线性可分的模式判别函数。它不需要对各类训练模式样本的统计性质作任何假设，所以是一种确定性的方法。比如固定增量逐次调整算法、最小平方误差算法。
要使前向神经网络模型实现某种功能，必须对它进行训练，让他学会要做的事情，并把所学到的知识记忆在网络的权值中。人工神经网络的权值的确定不是通过计算，而是通过网络自身的训练来完成的。
感知器的训练过程如下：在输入矢量X的作用下，计算网络的实际输出A与相应的目标矢量T进行比较，检查A是否等于T，然后比较误差T-A，根据学习规则进行权值和偏差的调整；重新计算网络在新权值作用下的输入，重复权值调整过程，知道网络的输出A等于目标矢量T或训练次数达到事先设置的最大值时结束训练。
感知器设计训练的步骤如下：
（1）对于所要解决的问题，确定输入矢量X，目标矢量T，并由此确定各矢量的维数以及确定网络结构大小的参数：r(表示输入矢量维数，神经元的权值向量维数)，s（表示一个输入矢量所对应的输出矢量的维数，或者表示神经元个数），p（表示输入矢量组数，）。
（2）参数初始化：赋给权值矢量W在（-1，1）的随机非0初始值；给出最大循环次数max_epcho。
（3）网络表达式：根据输入矢量X以及最新权矢量W，计算网络输出矢量A。
（4）检查输出矢量A与目标矢量T是否相同，如果是，或已达到自大循环次数，训练结束，否则转入（5）。
（5）学习：根据感知器的学习规则调整权矢量，并返回（3）。

步骤一：网络初始化
以随机的方式产生乱数，令w(0)为很小的实数，并且将学习循环n设定为1。
步骤二：计算网络输出值


凡是有该标志的文章，都是该blog博主Caoer（草儿）原创，凡是索引、收藏
、转载请注明来处和原文作者。非常感谢。

摘要本文介绍了在数据挖掘中数据分类的几个主要分类方法，包括：贝叶斯分类、决策树分类、感知器分类，及其各自的优势与劣势。并对于分类问题中出现的高维效应，介绍了两种通用的解决办法。
关键词数据分类贝叶斯分类决策树分类感知器分类


引言
数据分类是指按照分析对象的属性、特征，建立不同的组类来描述事物。数据分类是数据挖掘的主要内容之一，主要是通过分析训练数据样本，产生关于类别的精确描述。这种类别通常由分类规则组成，可以用来对未来的数据进行分类和预测。分类技术解决问题的关键是构造分类器。
一．数据分类
数据分类一般是两个步骤的过程：
第1步：建立一个模型，描述给定的数据类集或概念集（简称训练集）。通过分析由属性描述的数据库元组来构造模型。每个元组属于一个预定义的类，由类标号属性确定。用于建立模型的元组集称为训练数据集，其中每个元组称为训练样本。由于给出了类标号属性，因此该步骤又称为有指导的学习。如果训练样本的类标号是未知的，则称为无指导的学习（聚类）。学习模型可用分类规则、决策树和数学公式的形式给出。
第2步：使用模型对数据进行分类。包括评估模型的分类准确性以及对类标号未知的元组按模型进行分类。
常用的分类规则挖掘方法
分类规则挖掘有着广泛的应用前景。对于分类规则的挖掘通常有以下几种方法，不同的方法适用于不同特点的数据：
1．贝叶斯方法
2．决策树方法
3．人工神经网络方法
4．约略集方法
5．遗传算法
分类方法的评估标准：
准确率：模型正确预测新数据类标号的能力。
速度：产生和使用模型花费的时间。
健壮性：有噪声数据或空缺值数据时模型正确分类或预测的能力。
伸缩性：对于给定的大量数据，有效地构造模型的能力。
可解释性：学习模型提供的理解和观察的层次。
影响一个分类器错误率的因素
(1)训练集的记录数量。生成器要利用训练集进行学习，因而训练集越大，分类器也就越可靠。然而，训练集越大，生成器构造分类器的时间也就越长。错误率改善情况随训练集规模的增大而降低。
(2)属性的数目。更多的属性数目对于生成器而言意味着要计算更多的组合，使得生成器难度增大，需要的时间也更长。有时随机的关系会将生成器引入歧途，结果可能构造出不够准确的分类器（这在技术上被称为过分拟合）。因此，如果我们通过常识可以确认某个属性与目标无关，则将它从训练集中移走。
(3)属性中的信息。有时生成器不能从属性中获取足够的信息来正确、低错误率地预测标签（如试图根据某人眼睛的颜色来决定他的收入）。加入其他的属性（如职业、每周工作小时数和年龄），可以降低错误率。
(4)待预测记录的分布。如果待预测记录来自不同于训练集中记录的分布，那么错误率有可能很高。比如如果你从包含家用轿车数据的训练集中构造出分类器，那么试图用它来对包含许多运动用车辆的记录进行分类可能没多大用途，因为数据属性值的分布可能是有很大差别的。
评估方法
有两种方法可以用于对分类器的错误率进行评估，它们都假定待预测记录和训练集取自同样的样本分布。
(1)保留方法(Holdout)：记录集中的一部分（通常是2/3）作为训练集，保留剩余的部分用作测试集。生成器使用2/3的数据来构造分类器，然后使用这个分类器来对测试集进行分类，得出的错误率就是评估错误率。
虽然这种方法速度快，但由于仅使用2/3的数据来构造分类器，因此它没有充分利用所有的数据来进行学习。如果使用所有的数据，那么可能构造出更精确的分类器。
(2)交叉纠错方法(Cross validation)：数据集被分成k个没有交叉数据的子集，所有子集的大小大致相同。生成器训练和测试共k次；每一次，生成器使用去除一个子集的剩余数据作为训练集，然后在被去除的子集上进行测试。把所有得到的错误率的平均值作为评估错误率。
交叉纠错法可以被重复多次(t)，对于一个t次k分的交叉纠错法，k＊t个分类器被构造并被评估，这意味着交叉纠错法的时间是分类器构造时间的k＊t倍。增加重复的次数意味着运行时间的增长和错误率评估的改善。我们可以对k的值进行调整，将它减少到3或5，这样可以缩短运行时间。然而，减小训练集有可能使评估产生更大的偏差。
通常Holdout评估方法被用在最初试验性的场合，或者多于5000条记录的数据集；交叉纠错法被用于建立最终的分类器，或者很小的数据集。

二．贝叶斯分类
贝叶斯分类方法是一种具有最小错误率的概率分类方法，可以用数学公式的精确方法表示出来，并且可以用很多种概率理论来解决。
设（Ω,Θ,P）为概率空间，Ai∈Θ（i=1,2,…,n）为Ω的一个有穷剖分，且P(Ai)>0 (i=1,2,…,n)，则对任意B∈Θ且P(B)>0，有


P(Ai|B)=

 （i=1,2,…,n）

上式称为贝叶斯公式。
贝叶斯定理为我们提供了一个计算假设h的后验概率的方法

P(h|D)=


分类有规则分类和非规则分类，贝叶斯分类是非规则分类，它通过训练集训练而归纳出分类器，并利用分类器对没有分类的数据进行分类。
贝叶斯分类的特点
贝叶斯分类具有如下特点：
(1)贝叶斯分类并不把一个对象绝对地指派给某一类，而是通过计算得出属于某一类的概率，具有最大概率的类便是该对象所属的类；
(2)一般情况下在贝叶斯分类中所有的属性都潜在地起作用，即并不是一个或几个属性决定分类，而是所有的属性都参与分类；
(3)贝叶斯分类对象的属性可以是离散的、连续的，也可以是混合的。
贝叶斯定理给出了最小化误差的最优解决方法，可用于分类和预测。理论上，它看起来很完美，但在实际中，它并不能直接利用，它需要知道证据的确切分布概率，而实际上我们并不能确切的给出证据的分布概率。因此我们在很多分类方法中都会作出某种假设以逼近贝叶斯定理的要求。

三．决策树分类
决策树（Decision Tree）又称为判定树，是运用于分类的一种树结构。其中的每个内部结点（internal node）代表对某个属性的一次测试，每条边代表一个测试结果，叶结点（leaf）代表某个类（class）或者类的分布（class
 distribution），最上面的结点是根结点。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。
构造决策树是采用自上而下的递归构造方法。决策树构造的结果是一棵二叉或多叉树，它的输入是一组带有类别标记的训练数据。二叉树的内部结点（非叶结点）一般表示为一个逻辑判断，如形式为(a = b)的逻辑判断，其中a是属性，b是该属性的某个属性值；树的边是逻辑判断的分支结果。多叉树（ID3）的内部结点是属性，边是该属性的所有取值，有几个属性值，就有几条边。树的叶结点都是类别标记。
使用决策树进行分类分为两步：
第1步：利用训练集建立并精化一棵决策树，建立决策树模型。这个过程实际上是一个从数据中获取知识，进行机器学习的过程。
第2步：利用生成完毕的决策树对输入数据进行分类。对输入的记录，从根结点依次测试记录的属性值，直到到达某个叶结点，从而找到该记录所在的类。
问题的关键是建立一棵决策树。这个过程通常分为两个阶段：
(1)建树（Tree Building）：决策树建树算法见下，可以看得出，这是一个递归的过程，最终将得到一棵树。
(2)剪枝（Tree Pruning）：剪枝是目的是降低由于训练集存在噪声而产生的起伏。
决策树方法的评价。
优点
与其他分类算法相比决策树有如下优点：
(1)速度快：计算量相对较小，且容易转化成分类规则。只要沿着树根向下一直走到叶，沿途的分裂条件就能够唯一确定一条分类的谓词。
(2)准确性高：挖掘出的分类规则准确性高，便于理解，决策树可以清晰的显示哪些字段比较重要。
缺点
一般决策树的劣势：
(1)缺乏伸缩性：由于进行深度优先搜索，所以算法受内存大小限制，难于处理大训练集。一个例子：在Irvine机器学习知识库中，最大可以允许的数据集仅仅为700KB，2000条记录。而现代的数据仓库动辄存储几个G-Bytes的海量数据。用以前的方法是显然不行的。
(2)为了处理大数据集或连续量的种种改进算法（离散化、取样）不仅增加了分类算法的额外开销，而且降低了分类的准确性，对连续性的字段比较难预测，当类别太多时，错误可能就会增加的比较快，对有时间顺序的数据，需要很多预处理的工作。
但是，所用的基于分类挖掘的决策树算法没有考虑噪声问题，生成的决策树很完美，这只不过是理论上的，在实际应用过程中，大量的现实世界中的数据都不是以的意愿来定的，可能某些字段上缺值（missing values）；可能数据不准确含有噪声或者是错误的；可能是缺少必须的数据造成了数据的不完整。
另外决策树技术本身也存在一些不足的地方，例如当类别很多的时候，它的错误就可能出现甚至很多。而且它对连续性的字段比较难作出准确的预测。而且一般算法在分类的时候，只是根据一个属性来分类的。
在有噪声的情况下，完全拟合将导致过分拟合（overfitting），即对训练数据的完全拟合反而不具有很好的预测性能。剪枝是一种克服噪声的技术，同时它也能使树得到简化而变得更容易理解。另外，决策树技术也可能产生子树复制和碎片问题。

四．感知器分类
感知器是由具有可调节的键结值以及阈值的单一个类神经元所组成，它是各种类神经网络中，最简单且最早发展出来的类神经网络模型，通常被用来作为分类器使用。感知器的基本组成元件为一个具有线性组合功能的累加器，后接一个硬限制器而成，如图4.1所示。





图4.1
单层感知器是一个具有一层神经元、采用阈值激活函数的前向网络。通过对网络权值的训练，可以使感知器对一组输入矢量的响应达到元素为0或1的目标输出，从而达到对输入矢量分类的目的。
分类的判断规则是：若感知器的输出为1，则将其归类于C1类；若感知器的输出为0，则将其归类于C2类。判断规则所划分的只有两个判断区域，我们将作为分类依据的超平面定义如下：



感知器分类是通过训练模式的迭代和学习算法，产生线性或非线性可分的模式判别函数。它不需要对各类训练模式样本的统计性质作任何假设，所以是一种确定性的方法。比如固定增量逐次调整算法、最方误差算法。
要使前向神经网络模型实现某种功能，必须对它进行训练，让他学会要做的事情，并把所学到的知识记忆在网络的权值中。人工神经网络的权值的确定不是通过计算，而是通过网络自身的训练来完成的。
感知器的训练过程如下：在输入矢量X的作用下，计算网络的实际输出A与相应的目标矢量T进行比较，检查A是否等于T，然后比较误差T-A，根据学习规则进行权值和偏差的调整；重新计算网络在新权值作用下的输入，重复权值调整过程，知道网络的输出A等于目标矢量T或训练次数达到事先设置的最大值时结束训练。
感知器设计训练的步骤如下：
（1）对于所要解决的问题，确定输入矢量X，目标矢量T，并由此确定各矢量的维数以及确定网络结构大小的参数：r(表示输入矢量维数，神经元的权值向量维数)，s（表示一个输入矢量所对应的输出矢量的维数，或者表示神经元个数），p（表示输入矢量组数，）。
（2）参数初始化：赋给权值矢量W在（-1，1）的随机非0初始值；给出最大循环次数max_epcho。
（3）网络表达式：根据输入矢量X以及最新权矢量W，计算网络输出矢量A。
（4）检查输出矢量A与目标矢量T是否相同，如果是，或已达到自大循环次数，训练结束，否则转入（5）。
（5）学习：根据感知器的学习规则调整权矢量，并返回（3）。

步骤一：网络初始化
以随机的方式产生乱数，令w(0)为很小的实数，并且将学习循环n设定为1。
步骤二：计算网络输出值


凡是有该标志的文章，都是该blog博主Caoer（草儿）原创，凡是索引、收藏
、转载请注明来处和原文作者。非常感谢。

0 引言
数据分类 是指按照分析对象的属性、特征，建立不同的组类来描述事物。数据分类 是数据挖掘的主要内容之一，主要是通过分析训练数据样本，产生关于类别的精确描述。这种类别通常由分类 规则组成，可以用来对未来的数据进行分类 和预测。分类 技术解决问题的关键是构造分类 器 。 一．数据分类 数据分类 一般是两个步骤的过程： 第1步：建立一个模型，描述给定的数据类集或概念集（简称训练集）。通过分析由属性描述的数据库元组来构造模型。每个元组属于一个预定义的类，由类标号属性确定。用于建立模型的元组集称为训练数据集，其中每个元组称为训练样本。由于给出了类标号属性，因此该步骤又称为有指导的学习。如果训练样本的类标号是未知的，则称为无指导的学习（聚类）。学习模型可用分类 规则、决策 树 和数学公式的形式给出。 第2步：使用模型对数据进行分类 。包括评估模型的分类 准确性以及对类标号未知的元组按模型进行分类 。 常用的分类 规则挖掘方法 分类 规则挖掘有着广泛的应用前景。对于分类 规则的挖掘通常有以下几种方法，不同的方法适用于不同特点的数据： 1．贝叶斯方法 2．决策树方法 3．人工神经网络方法 4．约略集方法 5．遗传算法分类 方法的评估标准： 准确率：模型正确预测新数据类标号的能力。速度：产生和使用模型花费的时间。健壮性：有噪声数据或空缺值数据时模型正确分类 或预测的能力。伸缩性：对于给定的大量数据，有效地构造模型的能力。可解释性：学习模型提供的理解和观察的层次。 影响一个分类 器 错误率的因素 (1) 训练集的记录数量。生成器 要利用训练集进行学习，因而训练集越大，分类 器 也就越可靠。然而，训练集越大，生成器 构造分类 器 的时间也就越长。错误率改善情况随训练集规模的增大而降低。 (2) 属性的数目。更多的属性数目对于生成器 而言意味着要计算更多的组合，使得生成器 难度增大，需要的时间也更长。有时随机的关系会将生成器 引入歧途，结果可能构造出不够准确的分类 器 （这在技术上被称为过分拟合）。因此，如果我们通过常识可以确认某个属性与目标无关，则将它从训练集中移走。 (3) 属性中的信息。有时生成器 不能从属性中获取足够的信息来正确、低错误率地预测标签（如试图根据某人眼睛的颜色来决定他的收入）。加入其他的属性（如职业、每周工作小时数和年龄），可以降低错误率。 (4) 待预测记录的分布。如果待预测记录来自不同于训练集中记录的分布，那么错误率有可能很高。比如如果你从包含家用轿车数据的训练集中构造出分类 器 ，那么试图用它来对包含许多运动用车辆的记录进行分类 可能没多大用途，因为数据属性值的分布可能是有很大差别的。 评估方法 有两种方法可以用于对分类 器 的错误率进行评估，它们都假定待预测记录和训练集取自同样的样本分布。 (1) 保留方法(Holdout)：记录集中的一部分（通常是2/3）作为训练集，保留剩余的部分用作测试集。生成器 使用2/3 的数据来构造分类 器 ，然后使用这个分类 器 来对测试集进行分类 ，得出的错误率就是评估错误率。虽然这种方法速度快，但由于仅使用2/3 的数据来构造分类 器 ，因此它没有充分利用所有的数据来进行学习。如果使用所有的数据，那么可能构造出更精确的分类 器 。 (2) 交叉纠错方法(Cross validation)：数据集被分成k 个没有交叉数据的子集，所有子集的大小大致相同。生成器 训练和测试共k 次；每一次，生成器 使用去除一个子集的剩余数据作为训练集，然后在被去除的子集上进行测试。把所有得到的错误率的平均值作为评估错误率。交叉纠错法可以被重复多次(t)，对于一个t 次k 分的交叉纠错法，k ＊t 个分类 器 被构造并被评估，这意味着交叉纠错法的时间是分类 器 构造时间的k ＊t 倍。增加重复的次数意味着运行时间的增长和错误率评估的改善。我们可以对k 的值进行调整，将它减少到3 或5，这样可以缩短运行时间。然而，减小训练集有可能使评估产生更大的偏差。通常Holdout 评估方法被用在最初试验性的场合，或者多于5000 条记录的数据集；交叉纠错法被用于建立最终的分类 器 ，或者很小的数据集。 二．贝叶斯分类 贝叶斯分类 方法是一种具有最小错误率的概率分类 方法，可以用数学公式的精确方法表示出来，并且可以用很多种概率理论来解决。 设（Ω,Θ,P）为概率空间，Ai∈Θ（i=1,2,...,n）为Ω的一个有穷剖分，且P(Ai)>0 (i=1,2,...,n)，则对任意B∈Θ且P(B)>0，有 P(Ai|B)= （i=1,2,...,n） 上式称为贝叶斯公式。贝叶斯定理为我们提供了一个计算假设h的后验概率的方法 P(h|D)= 分类 有规则分类 和非规则分类 ，贝叶斯分类 是非规则分类 ，它通过训练集训练而归纳出分类 器 ，并利用分类 器 对没有分类 的数据进行分类 。 贝叶斯分类 的特点贝叶斯分类 具有如下特点： (1) 贝叶斯分类 并不把一个对象绝对地指派给某一类，而是通过计算得出属于某一类的概率，具有最大概率的类便是该对象所属的类； (2) 一般情况下在贝叶斯分类 中所有的属性都潜在地起作用，即并不是一个或几个属性决定分类 ，而是所有的属性都参与分类 ； (3) 贝叶斯分类 对象的属性可以是离散的、连续的，也可以是混合的。 贝叶斯定理给出了最小化误差的最优解决方法，可用于分类 和预测。理论上，它看起来很完美，但在实际中，它并不能直接利用，它需要知道证据的确切分布概率，而实际上我们并不能确切的给出证据的分布概率。因此我们在很多分类 方法中都会作出某种假设以逼近贝叶斯定理的要求。 三．决策 树 分类 决策 树 （Decision Tree）又称为判定树 ，是运用于分类 的一种树 结构。其中的每个内部结点（internal node）代表对某个属性的一次测试，每条边代表一个测试结果，叶结点（leaf）代表某个类（class）或者类的分布（class distribution），最上面的结点是根结点。决策 树 分为分类 树 和回归树 两种，分类 树 对离散变量做决策 树 ，回归树 对连续变量做决策 树 。 构造决策 树 是采用自上而下的递归构造方法。决策 树 构造的结果是一棵二叉或多叉树 ，它的输入是一组带有类别标记的训练数据。二叉树 的内部结点（非叶结点）一般表示为一个逻辑判断，如形式为(a = b)的逻辑判断，其中a 是属性，b是该属性的某个属性值；树 的边是逻辑判断的分支结果。多叉树 （ID3）的内部结点是属性，边是该属性的所有取值，有几个属性值，就有几条边。树 的叶结点都是类别标记。 使用决策 树 进行分类 分为两步： 第1步：利用训练集建立并精化一棵决策 树 ，建立决策 树 模型。这个过程实际上是一个从数据中获取知识，进行机器学习的过程。 第2步：利用生成完毕的决策 树 对输入数据进行分类 。对输入的记录，从根结点依次测试记录的属性值，直到到达某个叶结点，从而找到该记录所在的类。 问题的关键是建立一棵决策 树 。这个过程通常分为两个阶段： (1) 建树（Tree Building）：决策 树 建树算法见下，可以看得出，这是一个递归的过程，最终将得到一棵树 。 (2) 剪枝（Tree Pruning）：剪枝是目的是降低由于训练集存在噪声而产生的起伏。 决策 树 方法的评价。 优点 与其他分类 算法相比决策 树 有如下优点： (1) 速度快：计算量相对较小，且容易转化成分类 规则。只要沿着树 根向下一直走到叶，沿途的分裂条件就能够唯一确定一条分类 的谓词。 (2) 准确性高：挖掘出的分类 规则准确性高，便于理解，决策 树 可以清晰的显示哪些字段比较重要。 缺点 一般决策 树 的劣势： (1) 缺乏伸缩性：由于进行深度优先搜索，所以算法受内存大小限制，难于处理大训练集。一个例子：在Irvine机器学习知识库中，最大可以允许的数据集仅仅为 700KB，2000条记录。而现代的数据仓库动辄存储几个G-Bytes的海量数据。用以前的方法是显然不行的。 (2) 为了处理大数据集或连续量的种种改进算法（离散化、取样）不仅增加了分类 算法的额外开销，而且降低了分类 的准确性，对连续性的字段比较难预测，当类别太多时，错误可能就会增加的比较快，对有时间顺序的数据，需要很多预处理的工作。 但是，所用的基于分类 挖掘的决策 树 算法没有考虑噪声问题，生成的决策 树 很完美，这只不过是理论上的，在实际应用过程中，大量的现实世界中的数据都不是以的意愿来定的，可能某些字段上缺值（missing values）；可能数据不准确含有噪声或者是错误的；可能是缺少必须的数据造成了数据的不完整。 另外决策 树 技术本身也存在一些不足的地方，例如当类别很多的时候，它的错误就可能出现甚至很多。而且它对连续性的字段比较难作出准确的预测。而且一般算法在分类 的时候，只是根据一个属性来分类 的。 在有噪声的情况下，完全拟合将导致过分拟合（overfitting），即对训练数据的完全拟合反而不具有很好的预测性能。剪枝是一种克服噪声的技术，同时它也能使树 得到简化而变得更容易理解。另外，决策 树 技术也可能产生子树 复制和碎片问题。

决策树分类算法
1、概述
决策树（decision tree）——是一种被广泛使用的分类算法。
相比贝叶斯算法，决策树的优势在于构造过程不需要任何领域知识或参数设置
在实际应用中，对于探测式的知识发现，决策树更加适用。
2、算法思想
通俗来说，决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：
  女儿：多大年纪了？

  母亲：26。

  女儿：长的帅不帅？

  母亲：挺帅的。

  女儿：收入高不？

  母亲：不算很高，中等情况。

  女儿：是公务员不？

  母亲：是，在税务局上班呢。

  女儿：那好，我去见见。

这个女孩的决策过程就是典型的分类树决策。
实质：通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见
假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，那么这个可以用下图表示女孩的决策逻辑



上图完整表达了这个女孩决定是否见一个约会对象的策略，其中：
◊绿色节点表示判断条件
◊橙色节点表示决策结果
◊箭头表示在一个判断条件在不同情况下的决策路径
图中红色箭头表示了上面例子中女孩的决策过程。
这幅图基本可以算是一颗决策树，说它“基本可以算”是因为图中的判定条件没有量化，如收入高中低等等，还不能算是严格意义上的决策树，如果将所有条件量化，则就变成真正的决策树了。
决策树分类算法的关键就是根据“先验数据”构造一棵最佳的决策树，用以预测未知数据的类别
决策树：是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。
3、决策树构造
假如有以下判断苹果好坏的数据样本：


样本中有2个属性，A0表示是否红苹果。A1表示是否大苹果。假如要根据这个数据样本构建一棵自动判断苹果好坏的决策树。
由于本例中的数据只有2个属性，因此，我们可以穷举所有可能构造出来的决策树，就2棵，如下图所示：


显然左边先使用A0（红色）做划分依据的决策树要优于右边用A1（大小）做划分依据的决策树。
当然这是直觉的认知。而直觉显然不适合转化成程序的实现，所以需要有一种定量的考察来评价这两棵树的性能好坏。
决策树的评价所用的定量考察方法为计算每种划分情况的信息熵增益：
如果经过某个选定的属性进行数据划分后的信息熵下降最多，则这个划分属性是最优选择
属性划分选择（即构造决策树）的依据：
简单来说，熵就是“无序，混乱”的程度。
通过计算来理解：
1、原始样本数据的熵：
样例总数：4
好苹果：2
坏苹果：2
熵： -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1
信息熵为1表示当前处于最混乱，最无序的状态。
2、两颗决策树的划分结果熵增益计算
树1先选A0作划分，各子节点信息熵计算如下：
0，1叶子节点有2个正例，0个负例。信息熵为：e1 = -(2/2 * log(2/2) + 0/2 * log(0/2)) = 0。
2，3叶子节点有0个正例，2个负例。信息熵为：e2 = -(0/2 * log(0/2) + 2/2 * log(2/2)) = 0。
因此选择A0划分后的信息熵为每个子节点的信息熵所占比重的加权和：E = e12/4 + e22/4 = 0。
选择A0做划分的信息熵增益G（S, A0）=S - E = 1 - 0 = 1.
事实上，决策树叶子节点表示已经都属于相同类别，因此信息熵一定为0。
树2先选A1作划分，各子节点信息熵计算如下：
0，2子节点有1个正例，1个负例。信息熵为：e1 = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1。
1，3子节点有1个正例，1个负例。信息熵为：e2 = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1。
因此选择A1划分后的信息熵为每个子节点的信息熵所占比重的加权和：E = e12/4 + e22/4 = 1。也就是说分了跟没分一样！
选择A1做划分的信息熵增益G（S, A1）=S - E = 1 - 1 = 0.
因此，每次划分之前，我们只需要计算出信息熵增益最大的那种划分即可。
先做A0划分时的信息熵增益为1>先做A1划分时的信息熵增益，所以先做A0划分是最优选择！！！
4、算法指导思想
经过决策属性的划分后，数据的无序度越来越低，也就是信息熵越来越小
5、算法实现
梳理出数据中的属性
比较按照某特定属性划分后的数据的信息熵增益，选择信息熵增益最大的那个属性作为第一划分依据，然后继续选择第二属性，以此类推