李莉

摘要 近些年来，互联网迅速发展，数据量每年都以惊人的幅度提升，人们的生活、政府的管理都和电子信息设备息息相关，特别是电子商务和科学实验数据库的迅速壮大，为我们带来了海量的数据。这些海量的数据中，往往蕴藏非常多有价值的记录和信息，等待着人们去挖掘，人们希望将这些信息分离提取出来进行更高程度的分析和统计，以便为我们所取用。而目前大部分数据库系统仅仅可以实现数据的增、删、改、查，很难找到大数据之间所蕴含的规则和关系，比较缺乏挖掘数据内部价值的有效方法，较难通过数据的维度去探索和发现、预测未来的趋势。本文通过对数据挖掘技术中决策树的分类算法做出实验分析，进行比较，给出合理的分析建议。

【关键词】数据挖掘 决策树 ID3 算法

1 绪论

1.1 数据挖掘

在海量数据中提取有价值的信息和知识我们称之为数据挖掘技术。在海量数据库、云端服务器、数据仓储等存储媒介里面都存放着大量的数据信息，我们可以在这些存储媒介当中去探寻有价值的数据，深入分析和挖掘数据中的内在价值。帮助决策者找寻数据与数据之间可能存在的潜在关联结构，及时有效的发现可能被忽略和遗忘的要点。通常来说，这些数据信息对未来趋势的行为判断有着重要的作用，从而引导决策者做出正确的判断和最优的决策。因此，人们发明的决策树分类算法，来帮助人们更好的挖掘數据中有价值的信息。决策树分类算法的挖掘过程可能要多次循环往复螺旋递进，直至达到我们想要的结果。

1.2 数据挖掘分类算法的意义

目前来看，数据挖掘在实际应用中有着重要的作用和意义，数据挖掘技术可以运用于很多场合。比如：在股票金融市场中，可以对股票的历史交易信息数据进行分析和预测，并多其涨跌走势做出比较准确的判断;再比如在天气预报的过程中，对空气各类成分以及近半个月的数据进行收集、处理和分析，可以对天气预报做出比较准确的合理预测;在产品的销售系统中，己存原始数据库信息，现在假定有新的客户添加进数据库中，我们想讲广告促销信息分发给顾客。如果每一位顾客都通知，这势必成本较大，耗费较多，此时通过数据挖掘技术，找到那些比较有意向购买的顾客，向他们推送广告，可以大大节约了时间和金钱费用，促进的成交量，为商家带来更大的经济效益。数据挖掘技术其实就是一种决策支持的过程，是对数据进行深层次的数据分析方法。在平常生活中，可以将数据挖掘技术应用于方方面面，对促进社会的进步和发展有着很大的帮助。因此，对决策树分类算法的相关研究有着较高的实用价值和研究价值。

2 决策树分类算法相关知识

2.1 决策树的介绍

决策树（Decision Tree，DT）是一种常用的分类方法，适用于解决各种的分类问题。它通过将数据集进行分类、聚类和预测建模，将一个整体的大问题逐个逐个分解成每个子集小问题，再逐个一已解决子集问题，提高解决问题的效率。通常我们需要构建一个决策树来对分类过程进行建模比较。

2.2 决策树基本原理

1948年，美国数学家克劳德.艾而德伍.香农（ Claude Elwood Shannon）创建了信息论，用来解决在信息传递过程中的不确定性等问题。在信息论的基础上，决策树运用技术发展壮大。它通过数学的方法度量分析信息数据，通过自定义不同的符号情况，来描绘信息量的大小。其中包括一系列相关概念描述，以下为具体展示：

（1）自信息量。设连续发出的信号为Xl、X2…Xn为发出的信号，直到接收Xi信号，把不确定性的信号标识为I（Xi），即式（1）：

I（Xi）=-log1P（Xi）

（1）

其中P（Xi）表示信源发出Xi的概率。

（2）信息熵。再通过信息熵来度量信号源X的不确定性，即式（2）：

H（X）=∑P（Xi）Iog2p（xi）

（2）

其中X为信号源，i为任意可能的符号数。

（3）条件熵。设信号源X和Y不是相互独立的，则用条件熵H（X/Y）来度量整体的不确定性。设X对应的信号源为Xi，Y对应的信号源为Yj，则有： H（X/Y）=-∑∑P（XiYi）10g2P（Xi/Yj）（3）

（4）平均互信息量。信号源X和Y之间的相互关系：

I（X，Y）=H（X）-H（X/Y）

（4）

依据信息论，设S为整个样本数据整体集合，其中包含n类训练数据集，每类有Si个实例，则把它们分类所需要的信息量I用如下公式（5）表示为：

I（S1，S2，……，Sn）=一∑Pil0g2（Pi）（5）

由此，我们可以得到数据样本为S的包含N类的数据集，为了使下一步的工作尽可能尽量的减小，要求每一次都选择信息增益最大的属性作为决策树的节点，并对属性进行划分建立分枝，依据此思想划分数据样本集。

3 决策树ID3算法分析

3.1 决策树模型的建立

以下我们通过一个具体示例来演示经典ID3算法的整个构建过程。我们采用来自AllElectronics顾客数据库数据元组训练集。

利用ID3算法对对数据集合进行决策树模型的建立，对顾客进行分类，整个计算过程如下：

1计算给定样本集的信息熵，我们使用以下公式进行计算：

2.计算每个属性的信息增益

（1）需要确定属性age的每个样本值yes和no的分布。

*如果age=“<=30”，则p1=2（有2个yes），n1=3（有3个no），

由公式计算可知：

*如果age=“31……40”，则p2=4（有4个yes），n2=0（O个no），由公式计算知：I（p2，n2）=O：

*如果age=“>40”，则p3=3（有3个yes），n3=2（2个no），由公式计算可知：I（p3，n3） =0.971;

（2）对于属性1ncome，需要知道mcome的每个样本值Yes和no的分布。

*如果mcome=“high”，则p1=2（此时类别为yes的个数），n1=2（此时类别为no的个数），由公式计算可知：

*如果mcome-“medium”，则p2=4（有4个yes），n2=2（有2个no），由公式计算可知：I（p2，n2） =0.148;

*如果income=“low”，则p3=3（有3个yes），n3=1（有1个no），由公式计算可知：I（p3，n3） =0.279;

（3）生成决策树的根和分枝。如图1所示，我们可以从图中看出当age为31-40时，节点所对应的类别均为yes值，所以此时该节点的I（P2，n2）节点的信息熵为0，而<=30的属性和>40的属性都还有两个类别，所以要對它们进一步划分。

（4）依照上文所述的算法原理过程，对整体训练数据集进行递归分解，按照数据信息不同属性分为不同类别，最终建成决策树的分类模型，得到决策树的理想化模型。

4 总结

在这个信息化的时代，处理大量混乱而又复杂的数据的一个很好的方法是分类，在分类技术的发展过程中，几个流行的技术分别是神经网络、遗传算法、贝叶斯分类、决策树等。决策树算法理论清晰，效果直观，更易被读者所理解，能够较好的显示出数据之间的关联和内在联系，具有不错的分类预测能力。因此，对决策树算法的研究有着重要的研究价值和实际意义。

参考文献

[1]毛国君，段立娟，王实，石云.数据挖掘原理与算法[M]，北京：清华大学出版社，2005.

[2] Jiawei Han，Micheline Kamber著，范明，孟小峰等译.数据挖掘概念与技术[M].北京：机械工业出版社，2001.

[3]闪四清，陈茵，程雁等译，美MehmedKantardzic著，数据挖掘——概念、模型、方法和算法[M].北京：清华大学出版社，2003.

[4]张维东等.利用决策树进行数据挖掘中的信息熵计算[J].计算机工程，2001（03）：66-68.

[5]王大玲等.基于概念层次树的数据挖掘算法的研究与实现[J].计算机科学，2001，2（02）： 63-66.

[6]唐华松等.数据挖掘中决策树算法的探讨[J].计算机应用研究，2001（08）： 36-40.