基于决策树的手写数字识别问题

基于决策树的手写数字的识别问题

摘要：手写数字的识别是模式识别领域的一个重要课题。本文总结了一些文献中决策树在手写数字识别问题上的处理方法，并试着对已有的手写数字数据实现普通的决策树识别技术。实现表明，决策树在这一问题上的效果还是不错的。 关键词：手写数字 决策树 随机森林

Abstract: The handwritten digital recognition is an important problem in the field of pattern recognition. This paper summarizes some methods to classify handwritten digits by decision tree according to some literature, and try to deal with the existing digit data through decis-ion tree. Implementation show that the decision tree results has good accuracy rate. Keywords: handwritten digit , decision tree, random forest

1 引言

手写数字的识别是文字识别中的一个经典且重要的研究课题，也往往是模式识别或机器学习课程的实验数据。而且手写数字识别在实际应用中非常广泛，例如信封上邮政编码的识别，支票上金额的识别等都与人们的生活息息相关。相比于汉字识别，手写数字的分类规模少，因此研究更加深入，更加成熟。且随着计算机技术的发展，关于手写数字的识别方法也比较繁多。

然而，另一方面，由于手写数字因人而异，变体繁多，因此分类起来也有一定的难度。目前对各类字体的数字识别特别是脱机手写数字识别仍然处于发展阶段，而且识别效果仍然不够理想。在众多发展起来的方法中，本文挑选出基于决策树的分类思想来完成手写数字0-9的识别。用到的软件工具则是matlab。

近年来，人们对决策树处理手写数字的改进主要体现在两个方面。第一个是在特征选择或者特征提取上做些改进，比如参考文献中的姜文理，王卫等在《基于决策树的快速在线手写数字识别技术》中就是将手写数字的笔画走势作为决策树将要处理的特征。第二个是对决策树本身算法的改进，比如谭旭等就提出了一种层次分解决策树的方法来进行识别，并取得了较好的效果。

2 传统的决策树算法简介

2.1 决策树的优点

为什么我会选择决策树来对手写数字进行识别。主要是因为决策树有很多其它算法难以具有的优点。比如说，决策树易于理解和实现，人们通过解释后有能力去理解决策树所表达的意义。不仅如此，决策树对数据的准备往往是简单或者是不必要的，而其它技术往往要求先把数据一般化，比如去掉多余的或者空白的属性。而且，决策树还能够同时处理数据型和常规型的属性，其它技术却往往要求数据属性单一。最重要的是决策树是一个白盒子模型，如果给定一个观察的模型，那么根据所产生的决策树很容易推断出相应的逻辑表达式。因此，决策树能够在相对短的时间内对大型数据作出可行且效果良好的结果。所以笔者想尝试决策树对笔者目前已有的手写数字数据的识别效果如何。

2.2 传统的ID3算法描述

决策树是对数据进行分类，以此达到预测的目的。该方法先根据训练集数据形成一个决策树，如果该树不能对所有对象给出正确的分类，那么选择一些例外加入到训练集数据中，重复该过程一直到形成正确的决策集。决策树代表着决策集的树形结构。

决策树由决策结点、分支和叶子组成。决策树中最上面的结点为根结点，每个分支是一个新的决策结点，或者是树的叶子。每个决策结点代表一个问题或决策，通常对应于待分类对象的属性。每一个叶子结点代表一种可能的分类结果。沿决策树从上到下遍历的过程中，在每个结点都会遇到一个测试，对每个结点上问题的不同的测试输出导致不同的分支，最后会到达一个叶子结点，这个过程就是利用决策树进行分类的过程，利用若干个变量来判断所属的类别。

下图即是根据上表构造的一个决策树。

具体构造过程如下：称表中的U为对象，C为分类属性，D为决策属性。

首先，选择一个分类属性对所有对象进行分类，这里选择的是A4属性。这样根据A4属性上的取值可以将所有对象分为两类对象集（A4=1和A4=2）。然后，分别判断这两类对象集中的对象是否都取相同的决策属性值。经过比对，发现A4=1这个对象集中所有对象的决策属性值都为Class=3，则停止；同时发现A4=2这个对象集中的所有对象没有取相同的决策属性值，因此需要用别的分类属性继续分类，直到所有对象集中的对象都取相同的决策属性值为止。本例中，先后采用A4、A3、A2和A1进行分类就得到如图所示的一个决策树了。 如果选择分类属性的顺序不同，构造出的决策树也就可能不同。一般，决策树构造算法的区别就在于如何选择分类属性的顺序。因此可以说不可能构造出一个最优的决策树，因为这是个N-P难题。现在文献中经常提及的经典算法有ID3、C4.5等，这些算法在多数数据集中表现不错，但也没法保证在所有数据上最优。

3 ID3算法和随机森林对手写数字的实验

本文的实验采用的是ID3算法来构建决策树。具体的方案是首先构建一棵决策树，用它对手写数字0-9进行识别，然后再采用随机森林的方法来进行分类。因此本文中有三个实验，分别是一次性决策树识别，有5棵决策树构成的随机森林的识别，有8棵决策树构成的随机森林的识别。实验中的数据预处理以及所有调用的函数都写到了一个脚本文件Decsision tree中，方便运行和修改。

实验的目的是把这三个实验结果作一下对比，试图得出些有助于学习的结论。 实验的结果如下：

只采用决策树进行分类，总错误率为error=11.58% 采用5棵决策树的随机森林，总错误率为error=10.29%

采用8棵决策树的随机森林，总错误率为error=7.91%

4 实验结果与分析

从实验结果来看，只使用决策树的分类效果并不理想。这是因为决策树本身是一个弱分类器。而如果把众多决策树放在一起，采取投票的方法来分类，效果有明显提高。这也就是随机森林的基本思想。从实验结果还可以看出，随着随机森林中决策树个数的增加，效果越来越好。但是需要说明的是，这种错误率的降低并不是无止境的，也就是说随着决策树的增加，错误率最终会稳定在一个水平上。这是因为对于随机森林而言，森林中每棵树的分类性能越好，则效果越好，但是如果所有树的相关度很高，则效果就会下降。所以随机森林中并不是树越多越好。

参考文献

[1] 张勇.聚类与PCA融合的特征提取方法研究 [J].计算机工程与应用

[2] 谭旭，孔孟荣.基于层级分解决策树的手写数字识别[J].微电子学与计算机 [3] 姜文理，王卫.基于决策树的快速在线手写数字识别技术[J].计算机科学