2.1.3 典型分类算法
简单来说，分类就是根据对象的特征或属性，将其划分到已有类别的过程。常用的分类算法包括：决策树分类算法，朴素的贝叶斯分类算法、基于支持向量机（SVM）的分类器，神经网络法，K最近邻法（K⁃Nearest Neighbor，KNN），模糊分类法等。下面主要介绍决策树分类算法和贝叶斯分类算法。
1）决策树分类算法
决策树是一种依托于策略抉择建立起来的，用于对实例进行分类的树形结构。决策树由节点（node）和有向边（directed edge）组成。节点的类型有两种：内部节点和叶子节点。其中，内部节点表示一个特征或属性的测试条件（用于分开具有不同特性的记录），叶子节点表示一个分类。
一旦构造了一个决策树模型，以它为基础来进行分类将是非常容易的。具体做法是，从根节点开始，对实例的某一特征进行测试，根据测试结构将实例分配到其子节点（也就是选择适当的分支）。沿着该分支可能到达叶子节点或者到达另一个内部节点时，那么就使用新的测试条件递归执行下去，直到抵达一个叶子节点。当到达叶子节点时，人们便得到了最终的分类结果。
决策树是一种以树形数据结构来展示决策规则和分类结果的模型，作为一种归纳学习算法，其重点是将看似无序、杂乱的已知实例，通过某种技术手段将它们转化成可以预测未知实例的树状模型，每一条从根节点（对最终分类结果贡献最大的属性）到叶子节点（最终分类结果）的路径都代表一条决策的规则。决策树算法的优势在于，它不仅简单易于理解，而且高效实用，构建一次就可以多次使用，或者只对树模型进行简单的维护就可以保持其分类的准确性。
决策树算法采用自上而下递归构建树的技术，该算法的产生源于CLS（Concept Learning System，概念学习系统），图2⁃3展示一个CLS系统的简易模型。该模型是决策树发展的理论基础，该模型定义了一个学习系统的基本结构。
图2⁃3 CLS简易模型
通俗来说，决策树分类的思想类似于找对象。现在，想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：
女儿：多大年纪了？
母亲：26岁。
女儿：长得帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员吗？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。
这个女孩的决策过程就是典型的分类树决策。其实质就是通过年龄、长相、收入和是否是公务员将男人分为两个类别：见和不见。
假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，那么这个可以用图2⁃4表示女孩的决策逻辑。
图2⁃4 见面决策树
决策树分类算法的关键就是根据“先验数据”构造一棵最佳的决策树，用以预测未知数据的类别。根据不同的建树思想，决策树分类算法会延伸出一系列新的分类算法。
国际权威的学术组织IEEE International Conference on Data Mining（ICDM）曾在21世纪初期，将两种决策树算法（C4.5算法和CART算法）列入数据挖掘领域十大经典算法之中。可见决策树算法优良的结构特性和算法效率，得到了很多专家学者的一致认可。
当今社会，信息化的程度日益提高，人们被各种数据所包围。数据挖掘作为一种新兴的学术领域，它的发展极大地促进了人们对海量数据中所蕴含的知识的认识程度。数据挖掘最根本的目的就是，通过各种有效的技术手段，在已知的数据中探寻有价值的信息。决策树分类算法，作为一种简单高效、容易理解的启发式算法，有着广泛的应用领域。近年来随着模糊理论与决策树的融合，使得该算法更为智能，更符合人的思维方式，极大地扩展了其应用范围。(https://www.daowen.com)
2）贝叶斯分类算法
贝叶斯分类算法是一类分类算法的总称，它利用概率统计知识进行分类，这类算法均以贝叶斯定理为基础，故统称为贝叶斯分类。这些算法主要利用贝叶斯定理，来预测一个未知类别的样本属于哪个类别的可能性，选择其中可能性最大的一个类别作为该样本的最终类别。由于贝叶斯定理的成立，本身需要一个很强的条件独立性假设前提，而此假设在实际情况中经常是不成立的，因而其分类准确性就会下降。为此就出现了许多降低独立性假设的贝叶斯分类算法，如TAN（Tree Augmented Bayes Network）算法，它是在贝叶斯网络结构的基础上通过增加属性对之间的关联来实现的。而朴素贝叶斯分类是贝叶斯分类中最简单，也是常见的一种分类方法。下面重点介绍朴素贝叶斯分类算法。
（1）贝叶斯定理
贝叶斯统计方式与统计学中的频率概念是不同的，统计学是从频率的角度出发，即假定数据遵循某种分布，人们的目标是确定该分布的几个参数，在某个固定的环境下做模型。而贝叶斯定理则是根据实际的推理方式来建模，用得到的数据，来更新模型对某事件即将发生的可能性的预测结果。在贝叶斯统计学中，人们使用数据来描述模型，而不是使用模型来描述数据。
贝叶斯定理旨在计算P（A|B）的值，也就是在已知B发生的条件下，A发生的概率是多少。大多数情况下，B是被观察事件，比如“昨天下雨了”，A为预测结果“今天会下雨”。对数据挖掘来说，B通常是观察样本个体，A为被预测个体所属类别。所以，说简单一点，贝叶斯就是计算：B是A类别的概率。
贝叶斯公式：
（2⁃1）
例如，想计算含有单词“drugs”的邮件为垃圾邮件的概率。
在这里，A为“这是封垃圾邮件”。先来计算P（A），它也被称为先验概率，计算方法是，统计训练中的垃圾邮件的比例，如果数据集每100封邮件有30封垃圾邮件，P（A）为30/100=0.3。
B表示“该封邮件含有单词‘drugs’”。类似地，可通过计算数据集中含有单词“drugs”的邮件数P（B）。如果每100封邮件有10封包含有“drugs”，那么P（B）就为10/100=0.1。
P（B|A）指的是垃圾邮件中含有单词“drugs”的概率，计算起来也很容易，如果30封邮件中有6封含有“drugs”，那么P（B|A）的概率为6/30=0.2。
现在，就可以根据贝叶斯定理计算出P（A|B），得到含有“drugs”的邮件为垃圾邮件的概率。把上面的每一项代入前面的贝叶斯公式，得到结果为0.6。这表明如果邮件中含有“drugs”这个词，那么该邮件为垃圾邮件的概率为60%。
（2）朴素贝叶斯
通过上面的例子可以知道它能计算个体从属于给定类别的概率。因此，它能用来分类。
用C表示某种类别，用D代表数据集中的一篇文档，来计算贝叶斯公式所要用到的各种统计量，对于不好计算的，做出朴素假设，简化计算。
P（C）为某一类别的概率，可以从训练集中计算得到。
P（D）为某一文档的概率，它涉及很多特征，计算很难。但是，可以这样理解，当在计算文档属于某一类别时，对于所有类别来说，每一篇文档都是独立重复事件，P（D）相同，因此根本不用计算它。稍后看怎样处理它。
P（D|C）为文档D属于C类的概率，由于D包含很多特征，计算起来很难，这时朴素贝叶斯就派上用场了，朴素地假定各个特征是互相独立的，分别计算每个特征（D1、D2、D3等）在给定类别的概率，再求它们的积。
（2⁃2）
式（2⁃2）右侧对于二值特征相对比较容易计算。直接在数据集中进行统计，就能得到所有特征的概率值。
相反，如果不做朴素的假设，就要计算每个类别不同特征之间的相关性。这些计算很难完成，如果没有大量的数据或足够的语言分析模型是不可能完成的。
到这里，算法就很明确了。对于每个类别，都要计算P（C|D），忽略P（D）项。概率较高的那个类别即为分类结果。
朴素贝叶斯分类是基于各类别相互独立这一假设来进行分类计算的，也就是要求若给定一个数据样本类别，其样本属性的取值应是相互独立的。这一假设简化了分类计算的复杂性，若这一假设成立，则与其他分类方法相比，朴素贝叶斯分类法是最准确的，具有最小的错误率。
对于朴素贝叶斯还需要说明的一点是：若某种属性值在训练集中没有与某个类同时出现过，则直接基于概率估计公式得出来概率为0，再通过各个属性概率连乘式计算出的概率也为0，这就导致没有办法进行分类了，所以，为了避免属性携带的信息被训练集未出现的属性值“抹去”，在估计概率值时通常要进行“平滑”，常用“拉普拉斯修正”。拉普拉斯修正避免了样本不充分而导致概率估计为0的问题，并且在训练集样本变大的时候，修正过程所引入的先验影响也会逐渐变得可忽略，使得估计值越来越接近实际概率值。
