2.2.2　决策树算法

决策树也是一种常见的机器学习方法，该方法先划分数据再进行对比，以尽快结束判断的过程。仍然以上述的电影数据为例：首先计算以不同方式划分的数据，得到不同的信息增益；再以熵（Entropy）为单位进行对比。在信息论中，熵是每个研究对象中包含的信息平均量，是衡量信息量的指标之一。

按某类镜头个数是否大于或等于50来划分数据所获得的信息如表2.2所示。

表2.2　按某类镜头是否大于或等于50来划分数据所获得的信息

决策树算法的步骤如下：

（1）计算全体数据集的熵。全体数据集的熵计算公式为：

式中，Sigma表示对括号内的内容求和。

在本例中，一共有4类电影，每类出现的概率分别是2/6、1/6、2/6和1/6，全体数据集的熵为：

（2）指定分类方式，划分数据集。按照打斗镜头个数≥50、接吻镜头≥50和爆破镜头个数≥50的界限，划分数据集。以打斗镜头为例，其中正例（打斗镜头个数≥50的电影）共计2个、负例（打斗镜头个数＜50的电影）共计4个，得到打斗镜头的熵为：

按照同样的方法，可得到接吻镜头的熵和爆破镜头的熵分别为1.919和1.216。

（3）计算信息增益。用3种方式划分数据集得到的熵减去总熵，差值越大越好。可知用打斗镜头个数≥50的熵为1.919-1=0.919，接吻镜头个数≥50的熵也是0.919），都好于爆破镜头个数≥50的熵。

（4）构建决策树。分别根据打斗镜头个数、接吻镜头个数和爆破镜头个数对6部老电影进行3次划分，得到的决策树如图2.3所示。

图2.3　决策树

（5）裁剪决策树。如果决策树上的节点只能增加少许信息，则可以与其他节点合并或者删除该节点。例如，在图2.3中，爆破镜头个数≥50的节点并未被触发过，因此可以删除该节点。

（6）测试效果。构建好决策树后，用新电影的信息测试决策树：新电影的打斗镜头个数为8，继续判断一次，接吻镜头个数为92，直接判断为爱情片，正确率为100%。

决策树算法旨在以最快的速度、正确地结束判断过程。与K近邻算法的不同之处在于，决策树算法的已知特征都是以0和1的形式存在的，也就是说，对于三种镜头，需要按照其个数大于或等于50，以及小于50来进行划分，个数大于或等于50就是1，个数小于50就是0。决策树算法的缺点是难以准确预测连续性的字段，需要对数据进行很多预处理。