分类算法，是从数据集中提取描述数据类的一个函数或模型（也叫分类器），并将数据集中每个样本归结到某个已知的类中。分类算法的目标是对已有数据进行分类，并预测未来数据的归类，分类算法常用语医疗诊断、图像识别模式等领域。常见分类算法包括贝叶斯（Bayes）、决策树（Decision Tree）、支持向量机（SVM）、K近邻（KNN）、逻辑回归（Logistic Regression）、神经网络、深度学习等。

朴素贝叶斯（Naive Bayes）

贝叶斯分类法是基于贝叶斯定理的一种十分简单的分类算法，核心思想是，对于待分类的对象，求该对象在各类别出现的概率，哪个概率最大，就将此对象归入哪个类别。朴素贝叶斯有一个前提，每个特征值相对于其他特征值必须独立——类条件独立性。

贝叶斯定理：

$$P(A|B)=\cfrac{P(B|A)P(A)}{P(B)}$$

• P(A|B)是在B发生的情况下，A的发生概率，即A的后验概率；
• P(A)是发生A的概率，即A的先验概率；
• P(B|A)是在A发生的情况下，B的发生概率，即B的后验概率；
• P(B)是发生B的概率，即B的先验概率。

公式

假设某样本有n项特征（Feature），分别为$F_1$、$F_2$、…、$F_n$。现有m个类别（Category），分别为$C_1$、$C_2$、…、$C_m$。贝叶斯分类器就是计算出概率最大的那个分类，也就是求下面这个算式的最大值：

$$P(C|F_1F_2…F_n)=\cfrac{P(F_1F_2…F_n|C)P(C)}{P(F_1F_2…F_n)}$$

由于 P(F1F2…Fn) 对于所有的类别都是相同的，可以省略，问题就变成了求下式的最大值：

$$P(F_1F_2…F_n|C)P(C)$$

朴素贝叶斯分类器则是更进一步，假设所有特征都彼此独立，因此

$$P(F_1F_2…F_n|C)P(C)=P(F_1|C)P(F_2|C) … P(F_n|C)P(C)$$

上式等号右边的每一项，都可以从样本资料中计算得到，由此就可以计算出每个类别对应的概率，从而找出最大概率的那个类。

案例

有一组样本数据，记录了各门诊病人的职业、症状和确诊疾病，如下：

现在来了一个打喷嚏的工人，请问他最有可能是什么疾病？

• 设疾病为Category={"感冒", "过敏", "脑震荡"}，职业和症状为Feature={"工人", "打喷嚏"}
• 首先计算此人得感冒的概率，根据贝叶斯定理，可

$$P(感冒|打喷嚏×工人)=\cfrac{P(打喷嚏×工人|感冒)×P(感冒)}{P(打喷嚏×工人)}$$

由于朴素贝叶斯中各特征值独立，即“症状”（打喷嚏）和“职业”（工人）相互独立，上面的等式变为

$$P(感冒|打喷嚏×工人)=\cfrac{P(打喷嚏|感冒)×P(工人|感冒)×P(感冒)}{P(打喷嚏×工人)}$$

等号右边的所有概率P都可以根据样本数据计算得到

$$P(感冒|打喷嚏×工人)=\cfrac{0.66×0.33×0.5}{0.5×0.33}=0.66$$

所以他得感冒的概率为66%

• 同理计算此人患过敏或脑震荡的概率，比较后就能知道他最可能的疾病

优点

• 过程简单速度快；
• 在属性独立假设成立的前提下，效果极佳，所需样本量也少。

缺点

• 属性间相互独立的假设经常不成立；
• 通过先验和数据来决定后验的概率从而决定分类，先验概率很多时候取决于假设，存在一定的错误率。

应用

• 需要不同维度之间相关性较小的样本，例如：垃圾邮件识别、微博上的褒贬情绪判断等。

决策树（Decision Tree）

决策树是一个树结构（二叉树或非二叉树），使用时从根节点开始，在每个非叶节点测试样本中相应的属性值，按照属性值进行分支输出，直至到达叶节点，每个叶节点代表一个类别，将最终到达的叶节点作为决策结果。

构造决策树的关键是分裂属性，在非叶节点按照某个属性值的不同，划分构造不同的分支，目标是让各分裂子集尽可能单纯，即让分裂后的子集中的待分类样本属于同意类别。分裂属性包含以下三种情况：

• 属性是离散值（名称型Nornimal）且不要求生成二叉决策树时，属性的每个值作为一个分支。
• 属性是离散值（名称型Nornimal），且要求生成二叉决策树时，使用属性划分的一个子集进行测试，按照“属于此子集”和“不属于此子集”分成两个分支。
• 属性是连续值（数字型Numeric）。此时确定一个值作为分裂点split_point，按照>split_point和<=split_point生成两个分支。

例如有以下对话：

女儿：多大年纪了？

母亲：26。

女儿：长的帅不帅？

母亲：挺帅的。

女儿：收入高不？

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

女儿：是公务员不？

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

女儿：那好，我去见见。

这就是典型的决策树，通过年龄、长相、收入和是否是公务员的判断，得到最终的两个类别：见和不见。

• 年龄属性是连续值，此时假设女儿选择30作为分裂点，按照<=30和>30生成两个分支；
• 长相是连续值，且要求生成二叉树，属性划分为“丑”和“不丑”子集，生成两个分支；
• 收入是离散值，包括高、中、低三个值，此处不要求生成二叉树，每个值作为一个分支。

在构造决策树的过程中，决策点的选取和决策顺序非常重要，良好的决策顺序和分支设定可以减少性能消耗，提高效率，因此需要一个量化的方法，选取决策划分点和划分顺序。常见决策树算法包括ID3和C4.5。

ID3算法

ID3算法建立在“奥卡姆剃刀”的基础上：越是小型的决策树优于大的决策树。

ID3算法的重要衡量标准为熵和信息增益。

熵（entropy）是整个系统的平均消息量，一个系统越是有序，熵就越低；反之，熵就越高，所以，熵也可以说是系统有序化程度的一个度量。反映到决策树上，熵越大，在决策树上要达到叶节点（即输出最终结果），所需要判断的属性就越多，效率就越低。

信息熵，代表随机变量的复杂度。

条件熵，代表在某一个条件下，随机变量的复杂度。

信息增益，表示得知某个属性之后，使得样本集合不确定度减少的程度。

$$信息增益=信息熵-条件熵$$

过程

• 计算信息熵

样本集合D中有$k$类样本，其中第$i$类所占比例为$P_i$，D的信息熵计算公式如下：

$$Entropy(D)=-\sum_{i=1}^k P_i\log_2 P_i$$

• 计算信息增益

$a$表示某个属性，$V(a)$表示属性a的值的数量，$D$是样本集合，$D^v$是$D$中在$a$属性上，值等于$v$的样本集合，信息增益计算公式如下：

$$Gain(D,a)=Entropy(D)-\sum_{v\in V(a)}\cfrac{|D^v|}{|D|}Entropy(D^v)$$

案例

假设样本集合D某个属性a有3个分支x、y、z，通过对样本数据的统计，发现10个样本中，有6个走向了x分支、3个走向y分支，1个走向z分支。

• 计算熵

  $$Ent(D_x)=\cfrac{6}{10}\log_2\cfrac{6}{10}$$

  $$Ent(D_y)=\cfrac{3}{10}\log_2\cfrac{3}{10}$$

  $$Ent(D_z)=\cfrac{1}{10}\log_2\cfrac{1}{10}$$

  $$Ent(D)=-P_x-P_y-P_z$$

• 计算信息增益

  $$Gain(D, a)=Ent(D)-(\cfrac{6}{10}\times Ent(D_x)+\cfrac{3}{10}\times Ent(D_y)+\cfrac{1}{10}\times Ent(D_z))$$

• 计算其他属性的信息增益，进行对比，选择信息增益最高的属性作为当前节点，假设属性$a$的信息增益最高，则$a$作为当前节点的测试属性，x、y、z作为三个分支，将集合D分为三部分$D_x$、$D_y$、$D_z$

• 针对上一步得到的各分支，重复前三步，向下递归构成决策树

• 决策树构建时，某条路径终止的条件有两种：

  • 这条路径包括了所有的属性。
  • 某个分支输出的样本集合，剩余的属性值全部相同，则终止并得到一个叶节点。

优点

• 构建决策树的速度比较快，算法实现简单，生成的规则容易理解。

缺点

• 在属性选择时，倾向于选择那些拥有多个属性值的属性作为分裂属性，例如：当一个属性为ID时，这个属性会被作为根节点，而实际上这并没有意义。

应用

• 可以训练缺少属性值的实例。

C4.5算法

C4.5算法是对ID3算发的改进，C4.5算法不使用信息增益来选取特征值，而是使用了信息增益率。

$$信息增益率=\cfrac{信息增益}{属性固有值}$$

公式如下：

$$GainRadio(D,a)=\cfrac{Gain(D,a)}{IV(a)}$$

$$IV(a)=-\sum_{v\in V(a)}\cfrac{|D^v|}{|D|}\log_2\cfrac{|D^v|}{|D|}$$

属性固有值$IV(a)$随着$a$的值域数量增大而增大，此时优先选择GainRadio较大的属性作为当前节点，然后向下递归。

优点

• 既保证了信息增益高于平均水平，又避免出现选择ID作为特征这种极端的情况。

缺点

• 在构造树的过程中，需要对数据集进行多次顺序扫描和排序，导致算法低效。