基于PCA的决策树优化算法

谢霖铨 徐浩 陈希邦

摘 要：为了改善传统ID3算法在分类属性选择上存在多值偏向性的不足，提出基于PCA的决策树优化算法。在普通基于PCA 的决策树改进算法中，存在数据经降维处理后代表性不强的问题，导致算法需经过多次数据运行后，准确率才能小幅提升。在ID3算法基础上，在分类前两次提取属性特征值，并计算了需要分类的数据量，也即对原始数据进行最重要的属性选择。在子树建立之后，再进行数据的降维合并选择。采用UCI数据库中的3个数据集对改进算法进行验证，结果表明改进算法的平均准确率达到94.6%，相比传统ID3算法与普通PCA決策树优化算法分别提升了1.6%和0.6%。因此，基于PCA的决策树算法能在一定程度上提升结果准确率，具备一定的应用价值。

关键词：决策树算法;ID3;PCA算法

DOI：10. 11907/rjdk. 182908 开放科学（资源服务）标识码（OSID）：

中图分类号：TP312文献标识码：A 文章编号：1672-7800（2019）009-0069-03

PCA-based Decision Tree Optimization Algorithm

XIE Lin-quan， XU Hao， CHEN Xi-bang， ZHAO Nan

（College of Science， Jiangxi University of Science and Technology，Ganzhou 341000， China）

Abstract： In this paper， the problem of the multi-valued bias of the traditional ID3 algorithm in classification attribute selection is improved. A PCA-based decision tree optimization algorithm is proposed. In the ordinary PCA-based decision tree improvement algorithm， there are data after dimension reduction processing. The problem of low representation is that the improved algorithm needs to pass through multiple data to bring the accuracy to increase slightly. Therefore， based on the ID3 algorithm， the feature values are extracted twice before classification， and the classification needs to be calculated. The amount of data， that is， the most important attribute selection for the original data， after the subtree is established， the data is reduced and merged and selected. In the experimental stage， the improved algorithm was verified by three data sets in the UCI database. The results showed that the average accuracy rate in the three data sets reached 94.6%， and the traditional ID3 algorithm and the ordinary PCA decision tree optimization algorithm were improved by 1.6% and 0.6%， which proves the algorithm has certain practical significance.

Key Words： decision tree algorithm; ID3; PCA algorithm

0 引言

如今，信息化潮流对世界发展产生了重要影响，随着海量数据信息的不断更新，数据库管理系统受到越来越多人的重视。面对错综复杂的数据信息，如何对其进行高效利用成为人们亟待解决的问题。在大量数据信息中，包含着人们难以从表面发现的联系，如果得不到及时利用便会很快丢失，因此迫切需要采用新的计算技术与工具挖掘数据中的含义，使数据发挥其最大价值。数据库领域的知识发现（Knowledge Discovery in Database）及数据挖掘（DM——Data Mining）技术应运而生[1]。

分类算法是数据挖掘算法中的一种重要算法[2]。在传统ID3决策树算法中，通常以样本集中最大信息增益的属性作为树的分裂节点，且按照从大到小的信息增益取值作为依次划分点，即样本集中分裂属性个数为样本集个数，与此同时对应样本集节点生长出新的叶子节点。但经过后续研究发现，Quinlan的熵函具有一定弊端，其在属性选择时存在多值倾向性问题，因此在后续提出的C4.5算法中，通过计算信息增益率，并以此为属性分裂标准，从而在一定范围内避免了属性的多值倾向性[3]。此外，文献[4]-[6]通过引入粗糙集，利用粗糙集属性依赖的特性，选择决策属性中的核属性，以避免多值倾向问题;文献[7]-[9]通过增加属性重要度，可在某些程度上克服元算法的多值倾向问题，但该算法具有一定局限性，需要使用人员具有一定专业背景，且用户主观倾向也会对实验结果造成极大影响;文献[10]通过引入概率统计上的关联函数对ID3算法进行优化，可对原算法的多值倾向性问题起到一定优化作用，但在具体计算中，其忽视了信息熵的概念，因而影响了运算准确率;文献[11]在ID3算法中引入灰色关联度概念，但在实际应用中难以确定范围，且无法很好地确定属性取值个数;文献[12]-[13]通过对朴素贝叶斯与ID3算法的优化融合，提升了原算法执行效率;文献[14]通过采用皮尔逊相关系数计算属性间的相关性，避免了多值倾向问题，提升了算法准确率，但皮尔逊相关系数所需的数据变量是定量性质的，且服从正态分布，如果不符合该要求，计算结果的可靠性则会降低;文献[15]-[17] 融合使用PCA方法与传统决策树方法，但由于数据降维之后代表性不足，导致多次运行才能小幅提升算法准确率。

以上方法虽然都在一定程度上解决了ID3算法的多值倾向性问题，但仍存在一定不足，也有研究结合使用PCA算法与ID3算法，但也只是简单融合，并未进行PCA算法的多步骤计算。

本文在ID3算法基础上，在分类前两次提取属性特征值，并计算需要分类的数据量，也即对原始数据进行最重要的属性选择，在子树建立后再进行数据降维合并选择，从而得到更好的结果。

1 相关工作

1.1 决策树算法简介

決策树构建过程就是对数据不断划分的过程，每次计算都对应一个问题进行划分，与此对应的即是决策树节点。所以构造一个好的决策树，需要注重切分点划分，即准确、合理地选择决策树分裂属性。

1986年，机器学习研究者Quinlan[18]将Shannon的信息论引入决策树算法中，提出了ID3 算法。ID3算法具体计算过程如下[19-22]：设存在一个样本集E，其中包含样本训练集类数为C，而C类训练集中每项样本数为[Pi]，i=1，2，…C。如果以属性A作为测试属性，属性A的V个不同值为{[V1]，[V2]，…，[Vv]}，可以用属性A将E划分成V个子集{[E1]，[E2]，…，[Ev]}。假定[Ei]中含有第j类样本个数为[Pij]，j=1，2，…C ，则子集[Ei]的熵为[12]：

1.2 PCA算法简介

主成分分析法 （Principal Components Analysis，PCA）在1933年由霍特林首次提出[23]，PCA算法以降维为运算思路，也即在保证原数据集中信息损失较少的前提下，将多方面指标信息转化为更少的综合指标，从而提升对主要目标寻找的准确性。计算后得到的综合指标被称为主成分，任意主成分都是原数据集中变量的线性组合，且保持独立关系。通过相关计算得到的主成分在一定程度上对原问题进行了简化，提升了算法分析效率。

为了解决ID3原算法在分类属性上存在的多值倾向性问题，本文融合了PCA算法与决策树算法，在属性分类前对数据集中的数据进行主成分分析，然后进行压缩，选择更重要的特性进行分类，并在子树建立之后再次运用PCA算法进行整合。实验结果证明，该方法在一定程度上提高了算法准确率。

2 实验过程

2.1 算法流程

原算法流程如下：

设当前样本条件属性集为A，训练集为D，决策树属性为C。

1. 选择训练决定分类属性Ak;

2. 建立一个节点N;

3. 如果当前考虑的数据隶属于同一类，则此时N为决策树树叶，并在树叶上标记所属的类;

4. 如果当前所考虑的数据中没有其它属性可以分析，则此时N也是树叶，并按照少数服从多数的原则在树叶上标记所属类别;

5. 否则计算平均信息期望值，并根据属性期望值选出一个最佳属性作为节点N的测试属性。

本算法主要是基于原ID3决策树的算法，主要思想流程如下：

（1）选择数据集合A，将数据集先采用PCA算法进行压缩，选择重要特性。此时采用PCA算法压缩数据并构造决策树时，往往面临众多变量，变量之间会存在一定相关性，说明其之间存在起控制作用的共同因素。本文利用该项数据特性，对原始数据中的变量相关矩阵或协方差矩阵中的内部结构进行分析研究，并采用以下步骤构造相关系数矩阵。

步骤1：将需要处理的数据进行矩阵初始化处理，构建完整的数据矩阵[Xm*n]，m表示数据条数，n表示数据记录维数。

步骤2：对数据进行标准化处理，标准化是为了将不同量纲的数据放入同一矩阵中，使数据平均值为0，标准差为1。数据标准化公式为：

接着利用对原始变量线性组合的方式得到一些综合指标，也即主成分。对主成分的分析过程还需对矩阵结构进行分析，找到求解的特征值。

（2）决定分类属性。

（3）建立一个节点 N。

（4）如果数据都属于同一个类，N即是树叶，在树叶上标出所属的类。

（5）使用PCA算法对已选定的类进行再次压缩，选择重要特性。

（6）如果数据中没有其它属性可以考虑，则N也是树叶，按照少数服从多数的原则在树叶上标出所属类别。

（7）否则根据平均信息期望值选出一个最佳属性作为节点N的测试属性。

2.2 实验测试

为了验证本文提出的优化算法，选用来自UCI机器学习数据库中的数据进行试验。首先选取的是wine数据集，wine数据集包含178个样本个数，13个属性个数。原ID3算法以及本文优化算法运行结果对比如图1所示。

从图1中可以清晰看出，在原ID3算法下共存在5个不重合的点，在优化之后只存在两个不重合的点，证明优化算法的准确率高于原算法。

此外，本文还测试了另外两个数据集，分别是adult及car数据集，并与普通的PCA结合ID3算法进行比较，对比结果如表1所示。

从表1中可以发现，在所对比的数据集之下，本文算法相比原ID3算法及普通的PCA结合ID3算法，在准确率上都表现得更为出色，因此本文算法具有更好的优化效果。为了使结果更加清晰，将对比结果以图片形式进行展示，如图2所示。

3 结语

本文通过对原ID3算法进行优化，提出一种基于PCA的决策树优化算法。实验结果表明，改进算法在准确率上得到了一定提升。本文算法主要采用双重PCA压缩数据集，在一定程度上解决了原ID3算法的多值倾向问题，改善了决策树分类规则。之后还会将该算法运用到具体案例中，以对其作进一步改进，从而使其具备更好的实际应用价值。

参考文献：

[1] FAYYAD，USAMA M. Advances in knowledge discovery and data mining[M]. Cambridge：AAAl /The MIT Press，1996.

[2] ZHU S W. Decision tree mining technology and development trends [J]. Computer Engineering，2002，28（8）：77-78.

[3] 黄秀霞，孙力. C4.5算法的优化[J]. 计算机工程与设计，2016，37（5）：1265-1270，1361.

[4] 朱付保，霍晓齐，徐显景. 基于粗糙集的ID3决策树算法改进[J]. 郑州轻工业学院学报：自然科学版，2015，30（1）：50-54.

[5] 王子京，刘毓. 决策树ID3新属性选择方法[J]. 现代电子技术，2018，41（23）：9-12.

[6] 胡煜，郑娟. 基于粗糙集理论的ID3算法的改进与应用[J]. 贵阳学院学报：自然科学版，2015，10（1）：16-20.

[7] 李建，付小斌，吴媛媛. 基于优化ID3的井漏类型分类算法[J]. 计算机工程，2019，45（2）：290-295.

[8] 王永梅，胡学钢. 基于用户兴趣度和MID3决策树改进方法[J]. 计算机工程与应用，2011，47（27）：155-157.

[9] LUO H，CHEN Y，ZHANG W. An improved ID3 algorithm based on attribute importance-weighted[C]. International Workshop on Database Technology and Applications.IEEE， 2010：1-4.

[10] 韩松来，张辉，周华平. 基于关联度函数的决策树分类算法[J]. 计算机应用，2005（11）：2655-2657.

[11] 叶明全，胡学钢. 一种基于灰色关联度的决策树改进算法[J]. 计算机工程与应用，2007（32）：171-173.

[12] 黄宇达，王迤冉. 基于朴素贝叶斯与ID3算法的决策树分类[J]. 计算机工程，2012，38（14）：41-43，47.

[13] 黄春华，陈忠伟，李石君. 贝叶斯决策树方法在招生数据挖掘中的应用[J]. 计算机技术与发展，2016，26（4）：114-118.

[14] 董跃华，刘力. 基于相关系数的决策树优化算法[J]. 计算机工程与科学，2015，37（9）：1783-1793.

[15] 孟凡荣，蒋晓云，田恬，等. 基于主成分分析的决策树构造方法[J]. 小型微型计算机系统，2008（7）：1245-1249.

[16] 王江宇，陈焕新，刘江岩，等. 基于PCA-DT的多联机制冷剂充注量故障诊断[J]. 华中科技大学学报：自然科学版，2016，44（7）：1-4.

[17] LI M. Application of CART decision tree combined with PCA algorithm in intrusion detection[C]. Beijing：2017 8th IEEE International Conference on Software Engineering and Service Science，2017.

[18] QUINLAN J R. Induction of decision tree[J]. Machine Learning，1986（1）：81-106.

[19] LIU Y，XIE N. Improved ID3 algorithm[C]. International Conference on Computer Science and Information Technology，2010：465-468.

[20] 毛國君，段立娟，王实，等. 数据挖掘原理与算法[M]. 北京：清华大学出版社，2005：117-121.

[21] 谢妞妞. 决策树算法综述[J]. 软件导刊，2015，14（11）：63-65.

[22] 谢妞妞，刘於勋. 决策树属性选择标准的改进[J]. 计算机工程与应用，2010，46（34）：115-118.

[23] 何晓群. 多元统计分析[M]. 北京：中国人民大学出版社，2004.

（责任编辑：黄 健）