分类的树形决策器：理解决策树工作方式

5.2.1.1 基本概念

分类是将指定对象映射到某个预设的目标类别上的过程。比如，根据鸟的叫声区分鸟的种类，或者通过对银行客户分类来开展银行贷款的风险评估等。分类这一种数据分析方法能够帮助数据工作人员更好地从整体上理解数据，并且具有广泛的应用领域，如反欺诈、目标营销、性能预测等。

解决分类问题的一般方法是通过训练数据集来建立分类模型，涉及机器学习、模式识别以及统计学。常见的分类方法有决策树、基于规则的分类法、朴素贝叶斯、最近邻分类器等。

一般来说，对数据进行分类需要两个基本步骤。第一个步骤是训练，在训练过程中根据已经分类好的数据来创建分类模型。创建模型的解决方案就是分类算法，它通常就是通过学习得到的一个将给定元组映射到类标签的函数y=f（X）。这里X表示给定的元组，即待分类的数据，表示为包含n个特征属性的向量X=（x₁，x₂，...，x_n）；y表示类标签，是非连续且无序的；f就是映射的函数，即分类器，目标是针对给定的一个元组X预测与它相关联的类标签y。在训练步骤中，从已经标记好类标签的数据集中随机选出多个元组构成训练集，这些元组也被称为样本、样例、数据点等。第二个步骤是测试，在这个阶段首先使用测试数据对前一步所创建的分类模型进行测试，以评估分类器的准确性，如果其准确性是可以接受的，就可以用它来对新的未知类标签数据进行分类。所谓准确性，就是指被正确映射到其类标签的元组数量占测试集总的元组数量的比例。同样，在这个步骤中，用于测试的元组数据是从已经标记好分类标签的数据集中随机选取出来的，构成测试集，测试集中的元组不能是用于构建分类模型的元组，并且应与训练集相独立。

5.2.1.2 分类算法

1.决策树归纳 决策树归纳（Decision Tree Induction）是一种简单而广泛应用的分类方法。顾名思义，决策树是树形分类器，叶子节点表示分类标签，非叶子节点表示对该节点所带的属性进行的测试，分支表示测试后的结果。分类从根节点开始，经过非叶子节点时，就对该节点所带属性进行测试，同时根据测试结果进行分支。这样，从根节点一直到叶子节点的过程决定了待分类的元组的标签。如图5-2所示，决策树分类器用于对贷款偿还能力进行分类，节点“有房产”“已婚”“收入状况”表示特征属性，根节点为“有房产”，中间节点为“已婚”和“收入状况”，叶子节点在图中以方形框表示，“可以偿还”和“无法偿还”是分类的类标签。分类从根节点开始，对每个节点进行测试，经过判别条件进入分支。每次对一个元组进行分类，直到叶节点结束，分类的整个过程在决策树上循环进行。

（1）创建决策树。原则上来讲，对于给定的属性集，可以构造的决策树的数量达到指数级，因此几乎不可能搜索找到最佳决策树。为此，学者们提出近似方法，这些算法通常使用贪心策略，在选择划分数据的属性时，采取一系列局部最优决策来构造决策树。Hunt算法是大部分决策树算法的基础，由此扩展而来的ID3（Iterative Dichotomiser3）、C4.5（a successor of ID3）、CART（Classification and Regression Tree）算法都是目前常用的创建决策树的算法。通常创建的过程采用自顶向下的分治算法，在训练的过程中，训练集逐渐被拆分成更小的子集。

创建决策树最基本的方法需要将训练集D、候选特征属性、属性测试方案作为输入参数。这里的属性测试方案指的是选择能够将数据元组分入正确类别中的分类边界的最优方案。

算法从单个节点开始，如果D中的元组都属于同一个类别，那么将该节点记为叶子节点，表示确定类别。如果D中的元组属于多个类别，那么根据属性测试方案选择属性测试条件，把元组集分为更小的子集，对应测试条件的输出创建子节点，并且依据测试结果将元组集分配到创建的子节点中，对每个子节点再进行以上操作。

图5-2 决策树示例

在属性测试选择中，根据训练数据属性种类的不同有不同的划分方法。

1）非连续属性：直接根据属性值进行划分，比如颜色={红色，黄色，白色}，这里就以三种色彩进行多路划分。

2）连续属性：以划分点为界，测试条件一般是进行比较，比如年收入这一个元组，可以以<80000元和≥80000元来划分，也可以以<10000元，10000～20000元，>20000来划分。

3）非连续属性且要求生成二叉树（即仅有两个分支）：将节点的测试条件写为“是否属于”的判别形式，比如颜色是否属于红色或黄色，由此产生是与否的结果，构成两个分支。

（2）度量属性选择方法。所谓最优的属性选择方法，指的是根据这种方法进行划分所产生的元组集的子集是纯度最高的，也就是说落在子集中的元组都属于同一个类别。通常采用的衡量的方法为信息增益，包含信息增益率和Gini指数。

1）信息增益。对于给定的节点t，根据该节点经过属性测试之后得到的子节点中类的分布来度量纯度，采用信息熵的方法，设p（i|t）表示节点t中属于类i的记录所占的比例，那么该节点的信息熵为：

这里的c表示类的个数。

假设用于分类的属性有v个值产生分支，这样经过测试，元组集D就被划分成为v个子集。D_j表示经过第j个属性测试条件划分得到的子集，表示第j个划分所占的比重。信息增益是经过划分之后父节点和子节点信息熵的差值，换句话说就是以该属性来进行测试划分能够得到多少增加的信息。选择信息增益大的属性作为测试条件，由于父节点的信息熵是确定值，故通常选择最小化子节点信息熵的加权平均值的属性。

2）信息增益率。信息增益的方法在产生大量结果的属性测试时并没有太大意义，同时落在每个划分的元组数目太少也无法产生可靠的分析结果。C4.5采用信息增益率的方法进行评估，它用划分信息（对信息增益进行规整。信息增益率表示为。如果某个属性能够产生大量划分，那么它的划分信息将是一个很大的值，从而大大降低了它的信息增益率。3）Gini指数。CART采用的是Gini指数，。Gini指数所衡量的是数据划分或者训练元组的不纯度。在确定用属性变量进行数据划分时，根据每个划分子集所占的比重可以计算在该属性上的Gini指数的加权平均值。Gini指标越小，则认为该属性越可取。

2.贝叶斯分类器 本节所介绍的贝叶斯分类器是基于贝叶斯定理的统计分类器，在大数据上也具有很高的准确率和效率。

（1）贝叶斯定理。贝叶斯定理是一种把类的先验知识和从数据中收集的新证据相结合的统计原理。假设有相互独立的两个随机变量X和Y，它们的联合概率P（X，Y）指的是X取值x以及Y取值y的概率，而条件概率P（Y|X）表示在X取值x的情况下Y取值y的概率。根据概率论的知识，联合概率和条件概率之间的关系为P（X，Y）=P（Y|X）P（X）=P（X|Y）P（Y）。将这个公式稍微做一下变形就得到了著名的贝叶斯定理，见式（5-9）。

在分类问题中，将X看作具有多个属性的数据元组，将Y看作类变量。在数据元组与类之间的关系不确定时，认为它们都是随机变量。P（Y|X）的含义可理解为在已知元组X的属性描述的情况下它属于类别C的概率。在这里，P（Y|X）是在X确定的情况下的后验概率，而P（X）是X的先验概率。

（2）朴素贝叶斯分类器。朴素贝叶斯分类器是贝叶斯定理的应用。给定训练集D，训练集中的元组X表示为有n个属性的向量X=（x₁，x₂，…，x_n），其中各个属性都是相互独立的。假设有m个类标签C₁，C₂，…，C_m，我们认为X属于某个类别C_i，当且仅当确定X的属性描述的情况下该类别的后验概率最大，即P（C_i|X）>P（C_j|X）。根据贝叶斯定理得到式（5-10）。

在这里，P（X）的值对于任意的类标签来说都是相同的，而且一般情况下不同类别的P（C_i）也是相同的，所以决定X所属类别的关键在于P（X|C_i）。由于元组有n个属性，所以可以将P（X|C_i）扩写为P（X|C_i）=∏ⁿ_kP（x_k|C_i），分别计算类别C_i下的元组X中属性x_k的后验概率。根据属性类别的不同，考虑以下两种情况：

1）分类属性：直接根据类别C_i中属性值为x_k的比例来估计条件概率。

2）连续属性：容易想到的方案是离散化连续属性，以离散区间来表示连续属性值，但这种方法并不可靠。第二种方案是假设连续变量服从某种分布，一般假设均值为μ，标准差为σ的高斯分布，即，也就是说P（X|C_i）=g（x_k，μc_i，σ_Ci），以统计均值和标准差来估计μ和σ。

朴素贝叶斯分类器与其他分类器相比错误率最低，但实际上由于它条件相互独立的假设过于苛刻，往往无法达到这样高的准确率。另外，朴素贝叶斯分类器能够为其他并没有应用贝叶斯定理的分类器（如神经网络等）提供理论评估。

贝叶斯分类示例见表5-1。

表5-1 贝叶斯分类示例

由表5-1可知，数据元组有两个属性“房产”和“婚姻状况”，分别表示为x₁，x₂；类别为“拖欠贷款”和“未拖欠贷款”，分别表示为C₁和C₂。如果某客户有房产且未婚，那么以朴素贝叶斯分类器来估计其是否会拖欠贷款。

P（C₁=“拖欠贷款”|x₁=“有房产”，x₂=“未婚”）

比较两者的概率，可预测该有房产且未婚的客户不会拖欠贷款。

（3）贝叶斯信念网络。贝叶斯信念网络是贝叶斯定理的另一种应用。它不像朴素贝叶斯分类器那样要求属性之间都相互独立，而是允许某些指定属性条件独立，并且使用图形模型来表示变量之间的关系。贝叶斯网络由两个部分定义，即表示变量之间依赖关系的有向无环图和关联各节点与直接父节点的概率表，如图5-3所示。

图5-3所示的有向无环图中，若节点没有父节点（如A点），则其关联的概率表中只有先验概率P（A）；若其有一个父节点（如D点），则其关联的概率表中有条件概率P（D|C）；若其有多个父节点（如C点），则关联的概率表中有条件概率P（C|A，B）。贝叶斯信念网络中的节点可以表示类标签属性，作为输出节点，同时给出类别的概率。

(www.zuozong.com)

图5-3 贝叶斯信念网络示例

根据贝叶斯信念网络的结构，其创建过程需要两个步骤，即创建网络结构和估计每一个节点的概率表中的概率。其算法为：

设T=（X₁，X₂，…，X_d）表示变量的全序

forj=1 to d do

令X_T（j）表示T中第j个次序最高的变量

令π（X_T（j））={X_T（1），XT（2），…，XT（j-1）}表示排在XT（j）前面的变量的集合

从π（X_T（j））中去掉对X_j没有影响的变量（使用先验知识）

在π（X_T（j））和X_T（j）中剩余的变量之间画弧

endfor

3.基于规则的分类器 基于规则的分类器是以一组IF…THEN…规则来进行分类的学习模型，如IF“有房产=是”AND“已婚=否”THEN“拖欠贷款=否”。“IF”一侧（左侧）称为规则前件，各个属性判定条件以AND逻辑来连接，“THEN”一侧（右侧）称为规则后件，包含类别的预测。每个分类规则见式（5-11）。

R_i：（条件_i）→y_i （5-11）

如果在规则前件中的条件与元组中的属性相匹配，就称为覆盖。当条件覆盖给定的元组时，称r被激发。根据覆盖率和准确率来衡量规则R的质量。给定元组X，n_covers表示被R覆盖的元组的数目，n_correct表示根据规则R进行正确分类的元组的数目，而|D|表示的是数据集中元组的数目。覆盖率和准确率的定义见式（5-12）和（5-13）。

利用基于规则的分类器进行分类需要解决两个基本问题：一个问题是如果超过一个规则被激发，并且它们所预测的类别相互冲突该如何解决；另一个问题是，如果没有任何一条规则能够覆盖元组X，应该怎么解决。

对于第一个问题，需要冲突解决方案来对发生冲突的规则进行优先级排序，进而决定选择哪一条规则来进行类别预测。大小排序方案：优先级取决于被触发规则的大小，倾向于选择条件中含有最多属性测试的规则。规则排序方案：该排序方案又分为两类，即基于规则的排序和基于类别的排序。基于规则的排序方案是根据规则质量的某种度量对规则进行排序，比如准确性、专家置信度等，选择排序列表上具有最高优先级的规则进行分类。但是，这种方案中排序越靠后的规则越难解释。基于类别的排序方案中属于同一个类别的规则在规则集中一起出现，并根据它们所属的类别信息一起进行排序，排序的依据可以是类别出现的频率等，而属于同一个类别的规则之间并没有顺序关系，这些是因为它们对于预测类别并不存在冲突。

对于第二个问题，一般创建默认规则来覆盖没有被覆盖的元组，将它们归为默认类别。默认规则的规则前件为空，在没有任何现存规则能够覆盖元组时被触发。

基于规则的分类器中提取规则的创建有两种方法：直接从数据中提取规则和从其他分类模型中提取规则。

直接从数据中提取规则常采用顺序覆盖算法，从包含多个类的数据集中顺序学习得到规则，即每次提取一个规则。

顺序覆盖算法以训练集和所有可能取值的属性值作为输入，对于每一种类别用Lean-One-Rule函数提取覆盖当前训练集的最优规则，从训练集中删除被该规则覆盖的元组，并将该规则添加到规则列表中，重复以上步骤直到达到终止条件。

在这个算法中，使用Lean-One-Rule函数的目标在于提取一个分类规则，通过贪心的增长规则，先产生初始规则r，并不断对其进行求精，直到满足条件为止，然后对该规则进行修剪。

规则增长方式分为从一般到特殊和从特殊到一般。从一般到特殊是指从空的初始规则开始，逐渐向其中加入新的合取项，直到满足终止条件为止。从特殊到一般是指随机选择一个训练元组作为初始值，逐渐删除合取项，直到满足终止条件为止。这两种规则增长方式都需要有一种评估策略来决定合取项的去留。

FOIL信息增益考虑规则支持度计数的评估度量，即该规则所覆盖的训练元组数目的度量。这里将覆盖训练的类别下元组称为正例，而其他类别的称为反例。假设规则r覆盖pos个正例，neg个反例，在扩展规则之后覆盖pos′个正例和neg′个反例，则FOIL信息增益定义见式（5-14）。

使用似然比统计方法来进行评估，它比较被规则覆盖的类别的元组的观测频率以及进行随机预测的期望频率。假设有m个类别，那么似然比的定义见式（5-15）。

式（5-15）中f_i是被规则所覆盖的训练元组中的每个类别i的观测频率，e_i是假设规则在随机预测的情况下每个类别i的期望频率，而且似然比必须服从自由度为k-1的χ²分布。

从其决策树中生成规则集时，在决策树非常庞大的情况下，IF……THEN的规则更易于理解。从决策树的根节点一直到叶子节点的路径就可以生成一条规则，叶子节点是规则后件，其他节点是用AND连接的规则前件。

4.最近邻分类器 前面所介绍的分类方法都是积极学习方法，就是说给定训练集，主动生成模型而不需要添加新的分类测试元组。本节所介绍的最近邻分类器是一种消极学习方法，当给定训练集时，消极学习方法仅将它们存储起来，只有当测试元组和某个训练元组匹配的时候才进行分类。尽管这种学习方法时间和空间消耗都很大，并且不能为分类提供解释，但是它支持增量式的学习并且能够在复杂空间数据基础上建模。

最近邻分类器把每个样例看作d维空间上的一个数据点，d表示属性个数。给定一个数据点，计算该点与其他数据点的邻近度。最常见的计算距离的方法为距离矩阵，比如欧几里得距离。假设有两个数据点X₁=（x₁₁，x₁₂，…，x_1n）和X₂=（x₂₁，x₂₂，…，x_2n），其欧几里得距离见式（5-16）。

但是如果属性并不是数值，而是色彩之类的名词，那么就用差异性进行衡量，比如同时为蓝色，则差异性为0，反之为1。不同类别的属性可以制定不同的方法进行评估。

图5-4所示的是k为5时的最近邻分类器，与圆圈中心点距离最近的5个点（菱形所示）被分入同一个类别。

图5-4 k为5时的最近邻分类器

怎样选择最近邻的数目k来创建最优的分类器，需要通过实验来确定。需要经过测试比较不同k值下的分类器的错误率，一般来说训练集越大，k值越大。

5.人工神经网络 人工神经网络也是较为常用的分类方法。神经网络通过概率的方法模仿人脑中神经元细胞之间的通信过程，实现对人类决策过程的模拟。通常，人脑中的神经元细胞众多，每个神经元细胞都与大约100个其他神经元细胞有联系。通过对神经网络的模拟，可以完成简单的分类任务。

自联想存储器是一种简单的神经网络模型。在自联想存储器中，将已知的一组长度一致的布尔值向量P_i作为输入向量，其权值W_i为P_i的转置，得到权值矩阵W存储的一组模式，即

W=P₁×W₁+…+P_n×W_n

对待识别的P进行较为简单的分类操作，可以使用一个对称的硬极限函数：a=hardlims（W_p）。当W_p大于或等于0时，该函数返回1，否则返回-1。这样便实现了对输入向量P的二元分类。

除上述方法以外，常见的分类方法还有支持向量机（Support Vector Machine，SVM）、遗传算法等。