毕业设计题目是(选用决策树算法的数据挖掘实例分析与设计)
发布网友
发布时间：2022-04-26 10:14
共1个回答
热心网友
时间：2022-05-02 22:33
贾修一 MG0533024
(南京大学 计算机科学与技术系, 江苏省南京市 210093)
A Comparision between the Genetic Algorithms and Decision Tree For Data
Mining
Abstract: This chapter introces the application with the genetic algorithms and ID3 for the data mining, choose
the better algorithm to classifier the given data sets through.the comparision between the two algorithms. And
analyzing the results of the experiment as well as reasons.
Key words: genetic algrithms; data ming; decision Tree
摘 要: 对训练数据分别采用遗传算法和决策树算法进行数据挖掘,通过比较两者实验得出的结果,来选
择更适合本数据集的算法进行分类,并分析实验结果及原因.
关键词: 遗传算法;数据挖掘;决策树算法
1. 数据的描述
数据属性有139351维,每个属性的取值为0或1,分类标识只有两类:A和I.数据的维数太高,在数
据预处理阶段最好做属性的约简,进行降维的处理.
(1)数据维数太高,易造成一定的维数灾难,使得分类挖掘时间过长.
(2)数据庞大,肯定有些噪音数据.
2.算法的设计
为了提高最后分类的精确度,特设计了两种方法进行比较,从中选出一种精确度高的方法.第一种是根
据数据的特点,每个属性只取值0和1,所以进行属性约简的时候采用遗传算法.遗传算法的优点是可以对
大规模的数据进行一定的属性约简.
2.1 遗传算法描述:
(1) 遗传算法的步骤是编码,选择,交叉,变异.通过模仿自然界中的遗传进化原理,来对数据进行
处理.而遗传算法的好坏取决于适应度函数的选择,进化的次数,和交叉变异的合理性和概率性等,所以要
想设计一个合适的遗传算法必须经过大量的实验.
(2) 就训练数据而言,对每一维属性的取值,在类标识一定的条件下,取1和取0的概率之间有个绝
对值差α1,α2,该差越大,说明该属性的重要程度越高.同时还要考虑对同一维属性,不论最终类标识是
什么,取值都相同的话,则该属性可以被认为是无效的属性,对最后的分类没有影响,所以适应度函数取对
每一维属性的α1,α2的熵,熵越大,则属性的重要程度就越低.
(3) 编码阶段,就把每一位属性做为一个长度为139351的染色体的一个基因,1表示选择该属性,0
表示不选择该属性.随机初始化8个种群,按照适应度函数的定义,从中选取4个适应度函数最小的染色体
做为父代.
(4) 将选出的父代进行交叉操作,因为是降维操作,所以交叉就是取两个染色体之间隔位进行AND(与)
操作,变异就是按照一定的概率,在139351维上随机的100位进行非操作,即:0变为1,1变为0.依次又
产生4个后代,结合原来的4个父代组成新的8个初始种群.进化50次.
然后利用贝叶斯方法进行分类.得到的是一个弱的学习器h,然后利用AdaBoost方法进行强化学习分类器.
2.2 AdaBoost算法描述:
(1) 给定训练集(x1,y1),(x2,y2),…,(xm,ym)m个.
(2) yi∈{-1,+1},实例xi∈X的正确标识.
(3) for t=1,…,T
2
{
构造{1,…,m}上的分布Dt,找出弱分类器 ht:X->{-1,+1},
同时在Dt产生很小的错误εt:
εt=PrDt[ht(xi)≠yi]
}
(4)构造 Dt,D1(i)=1/m
Dt+1(i)= Dt/Zt*exp(-αt*yi*ht(xi))//(注:yi和ht(xi)只能取值于{-1,+1})
其中Zt是归一化因子(使Dt+1为分布)
αt=1/2*㏑((1-εt)/ εt)>0
(5)输出最终分类器:Hfinal(x)=sign(∑αt*ht(x)).
第二种方法就是直接使用决策树方法(ID3算法)进行分类.求出每一维属性的的信息增益,建立一棵
决策树,利用决策树来进行分类.
2.3 决策树算法(ID3)
(1)创建节点N;
(2)if samples都在同一个类C then
{
返回N作为叶结点,以类C标识;
}
(3)if attribut_list为空 then
{
返回N作为叶结点,标记为samples中最普通的类;
}
(4) 选择attribute_list中具有最高信息增益的属性test_attribute;标记节点N为test_attribute;
(5) for each test_attribute中的已知值a
由节点N长出一个条件为test_attribute=a的分枝;
(6) 设s是samples中test_attribute=a的样本的集合;
(7) if s为空 then
加上一个树叶,标记weisamples中最普通的类;
else
加上一个由ID3(s,attribute_list-test_attribute)返回的节点;
3. 实验分析
就第一种方法:通过实验,在进化次数上选取50次,使得维数约简到1500维左右时得到的分类效果最
好,但由于种群是随机产生的,所以在未进行boosting强化时正确率在60～85%之间,不是很稳定,但是符
合弱分类器的要求,即只要正确率超过50%就行,在进行boosting后,正确率能超过80%,但可能是数据进
行约简的不好或进行迭代的次数选取不太合适,正确率却没有ID3的高.就本数据集而言,由于最终标识只
有2个,所以比较适合使用遗传算法和Adaboost进行训练.正确率不高主要问题应该在:
(1)遗传算法的适应度函数没有选好,不同的编码方式对应不同的适应度函数取法,就本例而言,二进
制编码方式应该是可以的,就是在对适应度函数取的时候没有一个合适的数据表示,只好利用了熵的概念,
但在实际意义上感觉效果并不是很好.属性约简后正确率不高,这应该是最主要的原因.
(2)交叉变异的方式或许有问题,但是不是主要问题,只要适应度函数选好,也就是选择操作正确的话,
这两步操作对最终结果应该影响不大.
(3)进化次数的改进,通过实验,考虑最后的正确率和运行时间,发现在进化50次和约简到1500维时
贾修一:应用遗传算法和决策树算法在数据挖掘中的比较3
效果最好.但随着适应度函数的不同,进化次数也不同.从理论上说,进化次数越多,效果也应该越好,最
终达到一个最优解,但同时要避免得到局部最优解,就需要对传统的遗传算法进行改进,避免早熟问题.在
此就不讨论.
(4)利用贝叶斯分类得到的弱学习器,在格式上并不和Adaboost完全适应,所以在应用的时候效果不
是很好,这也取决于迭代的次数和训练样集的选取.
就决策树方法,对这么*的属性在某种意义上说并不合适,但就对本实验给定的训练样例集而言,通
过建树,只要6个结点就可以,而且正确率超过90%,所以,根据不同的数据集采用不同的方法得到的正确
率是不一样的.所以在某种程度上说,奥卡姆剃刀原理是正确的.
由于时间有限,没有对第一种方法进行一定的改进和进行其他方法的实验,故最终采用ID3算法进行分
类,采用前100个数据进行训练,后10个进行测试,错误的只有1个.采用前80个数据进行训练,后30
个进行测试的时候只有2个分类错误.正确率自测还是可以的.
4. 总结和感谢
通过本次实验,最大的收获就是采用了两种不同的方法进行了实验比较,虽然自己原先设计的算法没有
得到期望中的效果,并最终采用了其他的算法,但是通过实验,我对遗传算法和AdaBoost强化弱学习器方法
等有了更深的了解,也明白对不同的数据,是没有一种万能通用的解法的.以后会继续改进自己的算法,争
取取得好的效果.最后感谢老师能提供这次实验的数据.
