基于ID3决策树算法的非规则数据的规律

文/孙亚非 郭盛 李悦

基于ID3决策树算法的非规则数据的规律

文/孙亚非 郭盛 李悦

海量信息的处理，关键在于找出有价值或者有潜在价值的数据。这些数据为非规则数据，从这些数据中找到规律是数据处理中的重点和难点。ID3算法可以较为有效地解决这些问题，能够准确的把握数据的走势和是否能够成为热点的可能。

ID3算法 样本集 决策树

1 引言

随着社会各个领域的快速发展，各种数据量成爆炸式增长，网络数据尤为体现。这些数据的增长呈现出的特点为非规则性、突发性，研究它们的关键点就在于时间特性和数据量特性。如何在这些不规则的数据中找到某些数据的变化规律以及走势，已经成为现在数据研究中的重点和热点。本文采用ID3算法[1]建立决策树，可以较为有效的解决这些问题。

2 ID3决策树算法的基本原理

决策树又可称之为判定树。在决策树中，某一属性的一次测试由内部的某个节点代表，每个测试结果由每条边代表，某个类或类的分布由叶节点代表。在ID3决策树算法中信息熵和信息增量的计算是最主要的两个部分。

ID3决策树算法的描述[2]如下：

ID3（A：条件属性集合，d：决策属性，U：训练集）返回一棵决策树

{

if U为空，返回一个值为Failure的单结点；//为了程序的健壮性这种情况一般不会出现

if U由其值均为相同决策属性值的记录构成，返回带有该值的单结点；//此分支到此结束

if A为空，则返回一个单结点，其值为在U的记录中找到频率最高的决策属性值；//这时记录出现误分类

将A中属性之间具有最大I(d;a)的属性赋给a；

将属性a的值赋给{aj|j=1,2,...,m}；

将分别由对应于a的值aj的记录组成的U的子集赋给{uj|j=1,2,...,m}；

返回一棵树，其根标记为a，树枝标记为a1,a2,...am；

再构造树：ID3(A-{a},d,u1)，ID3(A-{a},d,u2)，...，ID3(A-{a},d,um)；//递归算法}

3 利用ID3算法建立决策树的过程

3.1 数据量定义

假设数据的训练样本集[3]为S，且对其在两个方向进行定义，一个为时间方向，一个为数据量大小方向，分别定义为ht、hd。

即数据样本的集合为

根据上述数据集，利用ID3算法，即可得出在不同时间域数据的分布以及变化情况，即满足某些趋势条件下信息熵的情况。

3.2 信息熵的获取

假设从上述数据集中取出某种具有同种属性的数据s。

在s中假设取三个相邻的数值，分别为an-1bn-1、anbn、an+1bn+1。当同时满足

条件时（约定该条件为θn），该属性数据开始出现上升趋势，即该数据有可能成为热点数据。当θn-1、θn、θn+1均出现时，该数据必然成为热点数据，且较长时间处于上升趋势。在相反条件下，当满足

图1：根据ID3算法生成的决策树

3.3 决策树的生成

根据以上条件，可生成的决策树如图1所示。

4 结束语

从以上ID3算法的应用研究[4]中，可以看出此算法在数据规律以及数据趋势的应用中效果明显，提高了数据判定的真实性。同时，此算法也显露出不足之处，如在数据建树的过程较为复杂，即时性需要提高。此种应用研究适合于网络数据的跟踪与处理，对突发热点事件有较强反馈处理能力。

[1]王永梅,胡学钢.决策树中ID3算法的研究[J].安徽大学学报(自然科学版),2011(03)：121.

[2]孙怡哲.一种改进的决策树算法研究与应用[D].辽宁：辽宁工程技术大学,2010.

[3]朱颢东.ID3算法的改进和简化[J].上海交通大学学报,2010(07)：242-243.

[4]周爱华.决策树技术在实验室评估中的应用研究[D].北京：中国石油大学,2011．

作者单位 沧州职业技术学院 河北省沧州市 061001

孙亚非（1981-），女，河北省唐山市人。硕士学位。现为沧州职业技术学院信息工程系讲师。研究方向为计算机应用技术。

●本论文为：2017年度沧州市社会科学发展研究课题。课题名称为：《基于大数据的高职院校毕业生就业情况的研究》，课题批准号为：2017213，一般课题。