登录 注册 | 服务热线:400 886 1266 | ENGLISH | 
 
|
技术方法

决策树算法的比较分析

发布时间:2014-10-22 16:04:03  点击数:5429

一.前言

  所谓决策树,就是在对数据进行决策分类时利用树的结构将数据记录进行分类,其中树的一个叶结点就代表符合某个条件的属性集,根据属性的不同取值建立决策树的各个分支;随后递归的构造每个子节点的子树。由于决策树结构简单便于人们认识理解以及决策树不需要额外的数据训练,因此决策树是数据挖掘中常用的一种分类方法,而现在最常用的是基于信息熵的算法。

二.各种算法比较

  1)ID3算法(Iterative Dicho to mizer 3)

  Quinlan的ID3算法是国际上公认的最早有影响的决策树算法。ID3算法是基于信息熵的决策树算法,它是根据属性集的取值分类。

  ID3算法原理:

  设E = {V1,V2,…,Vm}是m 维有穷向量空间,其中Vi 是有穷离散符号集, E 中的元素e =〈E1,E2,…,En〉称为实例.其中Ei∈Fi ,i=1,2,…,n. 设Pe和Ne是E 的2 个实例集,分别叫正例集和反例集.

  假设向量空间E 中的正例集Pe 和反例集Ne的大小分别为p,n, ID3基于如下两种假设:

  a.在响亮空间E上的一颗正确决策树对任意实例的分类概率同正反实例的概率。

  b.一棵决策树对一实例做出正确判断所需的信息量为:

  I(p,n) = -(p/p+n)log(p/(p+n))*log(p/(p+n))-

  (n/(p+n))log(p/(p+n))*log(p/(p+n))

  如果以某属性A作为决策树的根,则A具有m个值{V1,V2,...,Vm},它将E分成m个子集{E1,E2,…,Em},假设Et中含有Pt个正例和Nt个反例,那么子集Et所需的期望信息是H(Pt,Nt),以属性A为根所需的期望熵是:

  E(A) = ∑((Pt+Nt)/(P+N))I(Pt,Nt)

  以A为根的信息熵增益是:

  Gain(A) = I(P,N) – E(A)

  ID3选择使Gain(A)具有最大的属性A*作为根节点,对A*的不同取值对应的 E的V个子集Et递归调用上述生成过程生成子节点。

  ID3的优缺点:

  ID3采用自顶向下不回溯的策略搜索全部的属性空间,它建立决策树的算法简单,深度小,分类速度快。但是ID3对于大的属性集则执行效率下降快,准确性降低,并且学习能力低下。

  2)C4.5算法

  C4.5算法是ID3算法的改进,它采用了一种归纳学习的机制,

  IBM的IntelligentMiner采用的算法是一种称为Gini算法,Gini由以下公式计算求得:

  如果集合T分成两部分 N1 and N2 。那么这个分割的Gini就是:


  决策树算法的比较分析


  提供最小Ginisplit 就被选择作为分割的标准(对于每个属性都要遍历所有可以的分割方法).


  3)SLIQ算法(Supervised Learning In Quest)

  由于ID3和C4.5算法只能对于小的数据集有效,以及分类的准确性值得商榷,对于此有人提出一些改进的算法SLIQ。

  SLIQ算法的采用将属性分片,将其中的类常驻内存,随后由一关键字进行索引,每个数据集通过每个属性列表一个入口的连接来加以表示,类别列表的大小由训练样本数决定。

  当记录集达到无法全部放入内存时需要与外存进行交互而产生较大的I/O,此时算法的效率下降。

  4)SPRINT算法(Scalable Parallelizable Induction of Decision Trees)

  此算法利用了一个不同的属性列表数据结构。该数据结构保存类别与连接关键字ID信息,当一个结点进行分解时,相应属性列表也被分解到各个子结点中;而当一个结点进行分解时,列表的纪录顺序也被保留,因此分解后的列表无需再排序。此算法的设计思想使得它能够易于实现并行计算,从而具有较好的扩展性。

  但是SPRINT算法也有认为存在的缺点:为每个结点都保存属性表,这个表的大小有可能是数据库中原始数据大小的好几倍。维护每个结点属性表的hash表的开销很大(该表的大小与该结点所具有的纪录成正比)。

  5)RainForest算法

  RainForest算法框架关注于提高决策树算法的伸缩性,该框架可运用于大多数决策树算法(例如Sprint和SLIQ) ,使算法获得的结果与将全部的数据放置于内存所得到的结果一致,也就是说该算法能根据内存的大小自适应的调整决策书算法的具体过程。他保持一个AVC集合(属性、值、类别),并描述每个类别的分布。

  决策树的RainForest算法建立过程:

  建立节点的AVC-Group(通过读取整个原始数据库或者某个分支的数据库表或文件);

  选择分裂属性和分裂标准:取决于使用RainForest算法框架的具体算法,通过逐一检查AVC-set来选择;

  将数据分解到各个子节点:必须读取整个数据集(数据库或文件),将各条数据分解到各个子节点中,此时如果有足够的内存,将建立一个或多个子节点的AVC-group;


 
分享到:
查看更多行业成功案例及解决方案