ID3算法改进及其在分析商品价格波动因素中的应用

蔡照鹏 ，王永皎，韩正亮

(河南城建学院 计算机与数据科学学院，河南 平顶山 467036)

ID3算法改进及其在分析商品价格波动因素中的应用

蔡照鹏 ，王永皎，韩正亮

(河南城建学院 计算机与数据科学学院，河南 平顶山 467036)

对决策树以及ID3算法进行介绍，运用决策树ID3算法对1978-2005年全国农业商品价格总指数、种植业指数、林业产品指数、畜牧业产品指数、渔业产品指数进行分析，在数据分类过程中对连续数据采用聚类分析方法进行离散化及概念泛化，最后，生成我国农业商品价格指数变化情况的决策树。结果表明，决策树分类方法适用于分析我国农业商品价格的波动状况。

决策树；ID3算法；商品价格

1 决策树方法概述

决策树方法是数据挖掘中一种重要的分类方法，它采用一种贪心算法，即自顶向下的递归方式，从根节点开始在每个节点上按照给定标准选择测试属性，然后根据相应属性的所有可能取值向下建立分枝、划分训练样本，直到一个节点上的所有样本都被划分到同一个类，这一阶段最关键的操作是在树的节点上选择最佳测试属性，该属性可以将训练样本进行最好划分。另外，测试属性的取值可以是连续的，也可以是离散的[1]。

决策树是一种逼近离散函数值的方法。本质上决策树是通过一系列规则对数据进行分类的过程[2-4]，其另一特点是在学习过程中只要训练实例能够用属性的方式表现，就可以使用该方法而并不需要很多专业背景知识。

2 决策树ID3算法

决策树方法中ID3算法是Quilan在1986年提出来的，是决策树构造中的经典算法，基本思想为：

(1)决策树中每一个非叶结点对应着一个非类别属性，树枝代表这个属性的值。一个叶节点代表从树根到叶节点之间的路径对应记录所属的类别属性值。

(2)每个非叶结点都将与属性中具有最大信息量的非类别属性相关联。

(3)采用信息增益来选择样本分类属性。

2.1 基本定义

设S是s个数据样本的集合,类标号属性具有m个不同的值，定义m个不同的类Ci，其中i[1,m]，设Si是类Ci中的样本数。

定义1：对于一个给定的样本分类需要的信息熵为：

(1)

Pi是任意样本属于Ci的概率，可用Si/S进行估算。

定义2：假如A选为测试属性，设Sij子集为Sj中属于Ci类别的样本数。利用属性A划分当前样本集合所需要的公式为：

(2)

E(A)计算结果越小，就越表示其子集划分越好。而对于一个给定子集Sj，它的信息为：

其中，Pij=Sij/|Sij|表示Sj中任一个数据样本类别的概率。

定义3：若利用A对当前节点分支进行样本集合划分所获得的信息增益为：

Gain(A)=I(S1…..Sm)-E(A)

(3)

根据属性A取值进行样本集合划分所获得的熵的减少量就是Gain(A)。Gain(A)越大说明测试属性A对结果划分分类所需信息量越小。所以应作为分类属性。

2.2 决策树ID3算法描述

输入：训练数据集samples，用离散值属性表示；候选属性的集合attribute_list。

输出：一棵决策树。

基本步骤为：

(1)创建结点N；

(2)ifsamples都在同一个类Cthen；

(3)返回N作为叶结点，用类C标记；

(4)ifattribute_list为空then；

(5)返回N作为叶结点，标记samples中最普通的类； //多数表决；

(6)选择attribute_list中具有最高信息增益的属性test_attribute； //用信息增益作为属性选择度量。

(7)标记结点N为test_attribute；

(8)foreachtest_attribute中的已知值ai//划分samples

(9)由结点N生长出一个条件为test_attribute=ai的分枝；

(10)设si为samples中test_attribute=ai的样本集合；//一个划分

(11)ifsi为空then；

(12)加上一个叶结点，标记为标记samples中最普通的类；//多数表决

(13)else加上一个由Generate_decision_tree(si,attribute_list-test_attribute)返回的结点。

3 决策树ID3算法改进

在ID3算法中对于每个节点在选择测试属性时需要计算E(A)，在数据量比较大时会影响决策树的生成效率。假设决策树只有两种分类即正例和反例。设样本集S中正例个数为p,反例个数为n，由式(3)可知，I(S1…Sm)为定值，所以可以以E(A)作为划分节点的比较标准[5-7]。

其中

(4)

由麦克劳林公式：

(5)

当x→0时ln(x+1)≈x

由公式(5)对公式(4)做变换可得：

(6)

E(A)为简化后的信息增益即Gain’(A),只有加、乘、除运算，在处理大量数据时可缩减运算时间，提高计算效率。

4 我国农业商品生产价格总指数挖掘分析

4.1 数据准备

分析1987-2005年农业商品价格指数变化情况，由于数据的变化过程是连续的，所以在实际中根据人们的经验以及长期的实验判断寻求最佳值确定，上升到知识层次对此类问题进行求解的模型很少。因此，需先对连续的数据进行离散处理，选用SPSS统计软件对数据进行聚类分析，实现分类分层目的，然后对数据进行分类后的概念泛化处理。具体数据见表1，运用SPSS聚类之后的结果见表2。

表1 全国农业商品生产价格总指数

年份总指数种植业指数林业产品畜牧业产品渔业产品1978103．90104．69101．00100．50102．501979122．10122．39115．00122．60118．201980107．10107．78115．80103．40101．801981105．90106．09127．00101．10100．601982102．20102．48105．90100．30101．001983104．40105．74100．20100．50103．201984104．00103．82103．30104．10109．801985108．60101．66155．50124．10151．301986106．40106．62114．90103．00110．401987112．00108．83120．30117．90122．801988123．00113．46136．70140．20134．301989115．00118．90105．20110．2099．80199097．40100．7384．5092．3098．80199198．0097．31102．4097．40104．701992103．40101．14107．30106．30108．101993113．40112．05111．10114．20122．101994139．90141．91111．80144．60122．001995119．90123．95105．10115．80112．401996104．20104．71104．40103．30103．40199795．5092．8198．90101．8091．70199892．0093．64101．1086．9093．90199987．8085．75101．4088．5092．50200096．4094．6690．0099．00100．502001103．10105．6594．15103．0798．57

注：2000年以前农业商品生产价格总指数为农业商品收购价格指数。数据来源：中华人民共和国统计局。

为方便算法运行，特对表1数据做聚类分析处理，见表2。

表2 聚类分析结果

年份总指数种植业指数林业产品指数畜牧业产品指数渔业产品指数197811111197912222198001211198101211198201111198301111198401111198511222198601212198711222198812222198902120199001000199110101199211111199312222199412222199502122199601111199700010199800100199900100200010001200111010200201010200311111200412121200501111

注：表中各个指数数字说明：总指数：0降，1升；种植业指数：0低，1中，2高； 林业产品指数：0低，1中，2高；畜牧业产品指数：0低，1中，2高；渔业产品指数：0低，1中，2高。

4.2 传统ID3算法的信息增益

(1)计算对D(总指数)中元祖分类所需的期望信息,根据式(1)得，

Info(D)=0.996

(2)计算每个属性是期望信息需求，由式(2)得Info种植业指数(D)=0.934

同理得

Info林业产品指数(D)=0.938

Info畜牧业产品指数(D)=0.850
Info渔业产品指数(D)=0.842

计算该划分的信息增益，由式(3)得

Gain(种植业指数)= Info(D)- Info种植业指数(D)= 0.996-0.934=0.062

Gain(林业产品指数)= Info(D)- Info林业产品指数(D)= 0.996-0.938=0.058

Gain(畜牧业产品指数)= Info(D)- Info畜牧业产品指数(D)=0.996-0.850=0.146

Gain(渔业产品指数)= Info(D)- Info渔业产品指数(D)= 0.996-0.842=0.154

由于渔业产品指数在属性中具有最高信息增益，它被选作测试属性。决策树创建过程为：创建一个节点，用渔业产品指数标记，并对每个属性值引出一个分枝，对各个分枝进行如上所述递归运算，决策树如图1所示。

图 1 最终决策树

4.3 改进ID3算法后的信息增益

使用改进的决策树ID3算法，由式(6)可得计算结果如下：

Gain’(D)种植业指数=6.37
Gain’(D)林业产品指数=6.41
Gain’(D)畜牧业产品指数=5.6
Gain’(D)渔业产品指数=5.58

Gain’(D)渔业产品指数最小即应把渔业产品指数作为测试属性创建决策树，然后对各个分枝进行递归运算，构造决策树与图1相同。图2为决策树ID3算法改进前后处理相同数据所需的耗时对比图。

图2 耗时对比图

5 结论

(1)从决策树中可以看出：渔业产品指数对总指数变化影响最大，其次是种植业指数和林业产品指数，在对决策树准确率验证的前提下可以以此制定、调整和检查各项经济政策，对农业商品价格指数的变化进行调节。

(2)从规则中提取相关的知识可以对新的数据进行预测。在连续数据离散化过程中，聚类分析并行概念泛化使数据更加客观反映实际情况。

(3)ID3算法在属性选择标准的改进上，虽然计算E(A)时采用了近似计算，由于在计算熵中考虑了属性的取值个数，所以对分类的准确率影响不大，改进的算法在分类效率上有很大的提高。

(4)ID3算法是决策树方法中的经典算法之一，在实际工作中，需要根据数据类型的特点以及数据集的大小选取合适的算法。

[1] 田苗苗.数据挖掘之决策树方法概述[J].长春大学学报.2004，14(6)：48-51.

[2] 唐华松，姚耀文.数据挖掘中决策树算法的探讨[J].计算机应用研究，2001，18(18)：18-19.

[3] 张琳,陈燕,李桃迎,等.决策树分类算法研究[J].计算机工程，2011，37(13)：66-67.

[4] 杨学兵，张俊.决策树算法及其核心技术[J].计算机研究与发展，2007,17(1)：43-45.

[5] 王胜.基于决策树ID3算法研究与实现[J].齐齐哈尔大学学报，2012(3)：64-68.

[6] 黄爱辉，陈湘涛.决策树ID3算法的改进[J].计算机工程与科学，2009，31(6)：109-11.

[7] 高懿洋.基于决策树的我国农业数据挖掘分析[J].测绘科学技术学报，2008，25(5)：352-354.

Improved ID3 algorithm and its application in commodity price fluctuations analysis

CAI Zhao-peng, WANG Yong-jiao, HAN Zheng-liang

(DepartmentofComputerandDataScience,HenanUniversityofUrbanConstruction,Pingdingshan467036,China)

Firstly, a brief introduction of the decision tree and ID3 algorithm is made, then decision tree ID3 algorithm was used to analyze the 1978-2005 national agricultural commodity price index, index of planting and forestry products index, animal husbandry and fishery products product index index. In the data classification process, continuous data is made discretization and generalization of the concept by using the above data cluster analysis method,and finally using decision tree classification method to generate decision tree for the change of Chinese agricultural commodity price index. The results show that the decision tree classification method is applicable to the analysis of the fluctuation of agricultural commodity prices in China.

decision tree; ID3 algorithm; price of agricultural commodity products

2016-06-22

河南省高等学校重点科研项目(15A520048)

蔡照鹏(1980—)，男，河南濮阳人，硕士，讲师。

1674-7046(2016)06-0086-07

10.14140/j.cnki.hncjxb.2016.06.016

TP393

A