2017B题工商银行ATM机交易

zhangtt123

ID3算法在ATM选点预测系统中的应用

【摘要】：ATM的应用日益广泛,如何部署一个利用率高的ATM已成为一个值得探讨的问题。运用数据挖掘知识和决策树ID3算法,可以对已经部署ATM的地区进行分析,从而找出高利用率ATM地区的特征,并建立ATM选点模型,作为金融机构在何处部署高效的ATM的参考。

ID3算法   ID3算法是一种贪心算法，用来构造决策树。ID3算法起源于概念学习系统(CLS)，以信息熵的下降速度为选取测试属性的标准，即在每个节点选取还尚未被用来划分的具有最高信息增益的属性作为划分标准，然后继续这个过程，直到生成的决策树能完美分类训练样例。基本信息

中文名称ID3算法

外文名称ID3SUANFA

提出者Quinlan

大    学 悉尼大学

解    释 建立了概念学习系统(CLS)算法

背景知识

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

file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wpsED23.tmp.png使用ID3算法构造决策树

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

信息论的基本概念

定义1：若存在n个相同概率的消息，则每个消息的概率p是1/n，一个消息传递的信息量为Log2(n)

定义2：若有n个消息，其给定概率分布为P=(p1,p2…pn)，则由该分布传递的信息量称为P的熵，记为

I(p)=-(i=1ton求和)piLog2(pi)。

定义3：若一个记录集合T根据类别属性的值被分成互相独立的类C1C2..Ck，则识别T的一个元素所属哪个类所需要的信息量为Info(T)=I(p)，其中P为C1C2…Ck的概率分布，即P=(|C1|/|T|,…..|Ck|/|T|)

定义4：若我们先根据非类别属性X的值将T分成集合T1,T2…Tn，则确定T中一个元素类的信息量可通过确定Ti的加权平均值来得到，即Info(Ti)的加权平均值为：

Info(X,T)=(i=1ton求和)((|Ti|/|T|)Info(Ti))

定义5：信息增益度是两个信息量之间的差值，其中一个信息量是需确定T的一个元素的信息量，另一个信息量是在已得到的属性X的值后需确定的T一个元素的信息量，信息增益度公式为：

Gain(X, T)=Info(T)-Info(X,T)

为方便理解，在此举例说明算法过程，具体算法其实很简单：

某市高中一年级（共六个班）学生上学期期末考试成绩数据库。其中学生考试成绩属性有：学籍号、语文、数学、英语、物理、化学，如下表所示，本例子的目的是利用决策树技术研究学生物理成绩的及格与否可以由哪些属性决定:

学号语文数学英语物理化学

17671687181

27165637274

36081678780

46784716178

56476726472

67380665867

76281785279

87478476056

96268637467

107273734960

第一步：对数据进行规范化处理。

将上表中的数据规范化，用0表示成绩小于60分，1表示成绩大于或等于60分，得到下表：

学号语文数学英语物理化学

17671687181

27165637274

36081678780

46784716178

56476726472

67380 66 5867

76281785279

87478476056

96268637467

107273 73 4960

第二步：选取训练实例集。

从所有学生中进行抽样，将抽样数据作为训练集，共计有161条记录。经统计，在这161条记录的训练集中单科成绩及格人数和不及格人数如下表所示：

语文数学英语物理化学

及格8257343239

不及格79104127129122

第三步：利用信息增益度选取最能区别训练集中实例的属性。

首先计算课程物理所含有的信息量。由表4可知物理及格人数P=32，不及格人数N=129，则可得到：

Info(T)=I(32,129)=-[(32/161)Log2(32/161)+(129/161)Log2(129/161)]=0.7195

然后计算当课程物理及格和不及格时，课程语文所包含的总信息量。经统计，语文和物理有如下表所示的统计数据：

成绩搭配 人数

语文成绩=1且物理成绩=128

语文成绩=1且物理成绩=054

语文成绩=0且物理成绩=14

语文成绩=0且物理成绩=075

可得到：

Info(X,T)=)=(i=1ton求和)((|Ti|/|T|)Info(Ti))=(82/161)I(28,54)+(79/161)I(4,75)=0.6136

最后可得到语文的信息增益度为：

Gain(X,T)=Info(T)-Info(X,T)=0.7195-0.6136=0.1059

同理可得其他课程的信息增益度，结果如下表所示：

数学英语化学

Gain0.21360.0950.1701

由此可以看出所有课程当中数学是最能区别训练集中决定物理成绩与否的课程\

第四步：创建一个树结点，并创建该结点的子链，每个子链代表所选属性的一个唯一值。使用子链的值进一步细化子类。当出现以下两种情形之一时可以停止分类：1.一个结点上的数据都是属于同一类别；2.没有属性可以再对属性进行分割。

根据各个课程的信息增益度，应该选择数学作为所建决策树的根结点。由于数学的属性值只有两个：1（及格）和0（不及格），所以在数学下可以建立两个分支。经统计，数学不及格且物理不及格的人数为100，其准确率为100/104=96.2%。因此对数学不及格这个分之停止分割。又经统计，数学及格的57人中有26人物理及格，31人物理不及格，所以应对数学及格这个分支进行分割。从上表可知，应该选取化学作为分割结点进行细化。分割后经统计显示，数学和化学都及格的学生中，有26人物理及格，6人物理不及格，准确率为26/32=81.3%；数学及格但化学不及格的学生中，有22人物理不及格，3人物理及格，准确率为22/25=88%。

第五步：将其它成绩作为检验集。并用来检验所生成的决策树的准确度。

由该决策树可以得出下列规则：

(1)IF

学生的数学成绩不及格

THEN

其物理成绩通常也不及格。

准确度=(104-4)/104=96.2％

覆盖率=104/161=64.6％

(2)IF

学生的数学及格且化学成绩不及格

THEN

物理成绩不及格。

准确度=(32-6)/32=81.3％

覆盖率=32/161=20％

(3)IF

学生的数学成绩及格且化学成绩及格

THEN其物理成绩及格

准确度=(25-3)/25=88％

覆盖率=25/161=16％

我们也可这样描述：学生数学的学习程度将直接影响着其对物理的学习效果。化学的学习对物理的学习也有一定的影响。因此高中教师在进行物理教学时。应考虑学生的数学基础。数学程度较好而物理程度一般的学生应更重视化学的学习。

ID3算法计算每个属性的信息增益，并选取具有最高增益的属性作为给定集合的测试属性。对被选取的测试属性创建一个节点，并以该节点的属性标记，对该属性的每个值创建一个分支据此划分样本.

词条标签： 数学 文化 概率 算法

9 w( n0 l! h. U6 g: B3 c