1.    概述

决策树算法是一种归纳分类算法，它通过对训练集的学习，挖掘出有用的规则，用于对新集进行预测。决策树算法可设计成具有良好可伸缩性的算法，能够很好地与超大型数据库结合，处理相关的多种数据类型，并且，其运算结果容易被人理解，其分类模式容易转化成分类规则。因此，在过去的几十年中，决策树算法在机器学习(machine learning)和数据挖掘( data mining) 领域一直受到广泛地重视。本文将介绍决策树在交友类产品中的应用，重点将结合交友产品中用户偏好数据集阐述决策树的构造过程，并对常见的决策树构建算法进行对比。此外，本文介绍了决策树模型在交友类产品中的实际运用。

2.    决策树介绍

本文通过交友应用中一个用户交友偏好的实例，对决策树相关的一些概念进行详细的介绍。

2.1 决策树结构概述

表2.1是某一个用户Alice交友对象的属性以及该用户对于这些对象的喜好程度。属性包括“姓名”、“年龄”、“职业”、“月薪”、......、“喜好程度”，每一行是一个用户对象的样本，每一列是一个属性（字段）。这里把这个表记做数据集D。

此处需要解决的问题是，根据数据集D，建立一个用户偏好分析模型，并根据这个模型，产生一系列规则。当某个用户未来的某个时刻遇到新的一个用户时，依据这些规则，即该新用户的年龄、职业、月薪等属性，来预测对其的喜好程度，从而决定是否把这个新的用户推荐出来，以及确定推荐的优先度等等。这里的用户偏好分析模型，就可以用一棵决策树来表示。

在这个案例中，研究的重点是“喜好程度”这个属性。对于一个用户来说，当给定一个喜好程度未知的客户，要根据他/她的其他属性来估计“喜好等级”的值是“喜欢”、“一般”还是“不喜欢”，也就是说，要把对该用户的喜好程度分到喜好等级为“喜欢”、“一般”、“不喜欢”这3个类别的某一类别中去。这里把“喜好等级”这个属性称为“类标号属性”。数据集D中“信用等级”属性的全部取值就构成了类别集合：C={“喜欢”，“一般”，“不喜欢”}。

(1) 构建决策树

在决策树方法中，有两个基本的步骤。其一是构建决策树，其二是将决策树应用于新数据的预测。大多数研究都集中在如何有效地构建决策树，而应用则相对比较简单。构建决策树算法比较多，常见的算法有ID3，C4.5，CART等算法。采用其中的某种算法，输入训练数据集，就可以构造出一棵类似于图2.1所示的决策树。

一棵决策树是一棵有向无环树，它由若干个节点、分支、分裂谓词以及类别组成。

节点是一棵决策树的主体。其中，没有父亲节点的节点称为根节点，如图2.1中的顶部的“年龄”节点；没有子节点的节点称为叶子节点，如底部用方框标识的一系列节。一个节点按照某个属性分裂时，这个属性称为分裂属性，如根节点按照“年龄”被分裂，这里“年龄”就是分裂属性，同理，“职业”、“月薪”也是分裂属性。每一个分支都会被标记一个分裂谓词，这个分裂谓词就是分裂父节点的具体依据，例如在根节点分裂时，产生两个分支，对应的分裂谓词分别是“年龄<30”和“年龄>=30”。另外，每一个叶子节点都被确定一个类标号，这里是“不喜欢”、“一般”或者“喜欢”。

基于以上描述，下面给出决策树的定义：

给定一个数据集D={t₁,t₂,…,t_n}，其中t_i=(t_i1,t_i2,…t_ih)是D中的第i个样本，i=1,2,…,n，共n个样本；数据集模式包含的属性集A={A₁,A₂,…A_h}，共h个属性；t_ij是第i个样本的第j个属性。同时给定类别标号集合C={C₁,C₂,…C_m}，共m个类别。对于数据集D，决策树是指具有下列3个性质的树：

(a) 每个非叶子节点都被标记一个分裂属性A_i;

(b)  每个分支都被标记一个分裂谓词，这个分裂谓词是分裂父节点的具体规则；

(c)  每个叶子节点都被标记一个类别标号C_j∈C。

由此可以看出，构建一棵决策树，关键问题就在于，如何选择一个合适的分裂属性来进行一次分裂，以及如何制定合适的分裂谓词来产生相应的分支。各种决策树算法的主要区别也正在于此。

(2) 修剪决策树

利用决策树算法构建一个初始的树之后，为了有效地分类，还要对其进行剪枝。这是因为，由于数据表示不当、有噪音等原因，会造成生成的决策树过大或过度拟合。因此为了简化决策树，寻找一颗最优的决策树，剪枝是一个必不可少的过程。

通常，决策树越小，就越容易理解，其存储与传输的代价也就越小，但决策树过小会导致错误率较大。反之，决策树越复杂，节点越多，每个节点包含的训练样本个数越少，则支持每个节点样本数量也越少，可能导致决策树在测试集上的分类错误率越大。因此，剪枝的基本原则就是，在保证一定的决策精度的前提下，使树的叶子节点最少，叶子节点的深度最小。要在树的大小和正确率之间寻找平衡点。

常有的剪枝方法有预剪枝和后剪枝两种。

预剪枝，是指在构建决策树之前，先制定好生长停止准则（例如指定某个评估参数的阈值），在树的生长过程中，一旦某个分支满足了停止准则，则停止该分支的生长，这样就可以限制树的过度生长。采用预剪枝的算法有可能过早地停止决策树的构建过程，但由于不必生成完整的决策树，算法的效率很高，适合应用于大规模问题。

后剪枝，是指待决策树完全生长结束后，再根据一定的准则，剪去决策树中那些不具一般代表性的叶子节点或者分支。这时，可以将数据集划分为两个部分，一个是训练数据集，一个是测试数据集。训练数据集用来生成决策树，而测试数据集用来对生成的决策树进行测试，并在测试的过程中通过剪枝来对决策树进行优化。

 (3) 生成预测规则

在构建一棵决策树并进行优化之后，就可以根据这棵决策树来生成一系列规则。这些规则往往采用条件判断，即“if …then…”的形式。从根节点到叶子节点的每一条路径，都可以生成一条规则。这条路径上的分裂属性和分裂谓词形成规则的前件（if部分），叶子节点的类标号形成规则的后件（then部分）。

例如，图2.1的决策树可以形成以下5条规则：

利用以上规则，当出现未知类别的观测样本时，即可根据其年龄、职业、月薪等属性预测该样本是属于哪一个喜好等级的类别。

此外，若要决策树能够输出连续的预测值，可以将决策问题看成是一个回归问题从而建立回归树。

2.2 决策树的构建算法

本文主要介绍经典的ID3和C4.5构建算法

ID3算法是最有影响力的决策树算法之一，由Quinlan提出。然后由于ID3算法的存在某些弱点，因此被改善之后得到了C4.5算法。

2.2.1 ID3算法

任何一个决策树算法，其核心步骤都是为每一次分裂确定一个分裂属性，即究竟按照哪一个属性来把当前数据集划分为若干个子集，从而形成若干个“树枝”。

ID3算法采用“信息增益”为度量来选择分裂属性的。哪个属性在分裂中产生的信息增益最大，就选择该属性作为分裂属性。而信息增益，则借鉴了信息熵的概念。熵是数据集中的不确定性、突发性或随机性的程度的度量。当一个数据集中的记录全部都属于同一类的时候，则没有不确定性，这种情况下的熵为0。

例如在一次分裂中，数据集D被按照分裂属性“年龄”分裂为两个子集D₁和D₂，如图2.2所示。

其中，H(D)，H(D₁)，H(D₂)分别是数据集D，D₁，D₂的熵。那么，按照年龄将数据集D分裂为D₁和D₂所得到的信息增益为：

其中，P (D₁)是D中样本被划分到D₁中的概率，P (D₂)是D中样本被划分到D₂中的概率，P (D₁) * H (D₁) + P (D₂) * H (D₂)是H (D₁)和H (D₂)的加权和。显然，如果D₁和D₂中的数据越纯，H (D₁)和H (D₂)就越小，信息增益就越大。

按照这个方法，测试每一个属性的信息增益，选择增益最大的属性作为分裂属性。

设S是由s个样本组成的数据集，若S的类标号有m个不同的取值，即有m个不同的类C_i,i=1,2,…,m。记属于类别C_i的样本集为S_i，则数据集S的熵为：

其中，p_i是任意样本属于类别C_i的概率，用s_i/s来估计。

结合到每个属性上，设S的某个属性A具有v个不同的值A={a₁,a₂,…,a_v}，根据属性A将数据集划分为v个不同的子集{S₁,S₂,…,S_v}，子集S_j中所有的样本的属性值都等于a_j, j=1,2,…,v。在分裂为v个子集后，任意一个子集S_j的熵为：

其中，s_ij(i=1,2,…,m)是子集s_j中属于类别C_i的样本，p_ij=s_ij/|s_j|是S_j中的样本属于类别C_i的概率，|sj|是子集sj中的样本数量。

所以，S按照属性A划分的v个子集的熵加权和为：

当按照属性A将数据集S分裂，得到的信息增益计算如下：

决策树分类的基本原则是，数据集被分裂为若干个子集后，要使每个子集中的数据尽可能的“纯”，也就是说子集中的记录要尽可能属于同一个类别。套用熵的概念，即要使分裂后各子集的熵尽可能的小。

ID3算法是一个从上到下、分而治之的归纳过程。其核心是：在决策树各级节点上选择分裂属性时，通过计算信息增益来选择属性，以使得在每一个非叶节点进行测试时，能获得关于被测试样本最大的类别信息。其具体方法是：检测所有的属性，选择信息增益最大的属性产生决策树节点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树节点的分支，直到所有子集仅包括同一类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。

ID3算法描述如下：

ID3算法是一种典型的决策树分析算法，后来发展的许多决策树算法都是以ID3算法为基础发展而来的。

ID3算法的优点在于它构建决策树的速度比较快，它的计算时间随问题的难度只是线性地增加，适合处理大批量数据集。

同时，ID3算法的不足之处也是突出的，包括以下几点。

（1）ID3算法对训练样本的质量的依赖性很强，训练样本的质量主要是指是否存在噪声和是否存在足够的样本。

（2）ID3算法只能处理分类属性（离散属性），而不能处理连续属性（数值属性）。在处理连续属性时，一般要先将连续属性划分为多个区间，转化为分类属性。例如“年龄”，要把其数值事先转换为诸如“小于20岁”、“20~30岁”、“大于30岁”这样的区间，再根据年龄值落入了某一个区间取相应的类别值。通常，区间端点的选取包含着一定的主观因素和大量的计算。

（3）ID3算法生成的决策树是一棵多叉树，分支的数量取决于分裂属性有多少个不同的取值。这不利于处理分裂属性取值数目较多的情况。因此目前流行的决策树算法大多采用二叉树模型。

（4）ID3算法不包含对树的修剪，无法对决策树进行优化。

正因为ID3还存在着许多不足的地方，Quinlan对ID3算法进行了改进，提出了ID3的改进算法C4.5。

    

相关阅读：决策树技术在交友类产品中的应用（下篇）