基于粗糙集方法的决策树多值偏向理论分析
2014-12-02
杭州电子科技大学学报(自然科学版) 2014年2期
(浙江工业大学信息工程学院,浙江 杭州310023)
0 引 言
决策树方法是最受欢迎的数据挖掘技术之一,主要用于分类和预测。学者提出了著名的ID3 决策树分类方法[1]。然而实验表明ID3算法在构造决策树时有多值偏向的问题,以往大多数的学者都是通过实验研究多值偏向问题[2-5]。有学者首次提出一种理论分析多值偏向问题的方法[6]。然而文献[6]在分析多值偏向问题时,理论的严密性及逻辑性不强,缺少实例验证。本文在文献[6]基础上,针对其不足,基于粗糙集理论引入属性重要度概念,从理论上分析了属性多值对信息熵的影响和属性多值对其他属性的重要性程度的影响两个问题。最后通过实验表明理论分析方法的正确性与可行性。
1 ID3算法及粗糙集理论
1.1 ID3算法
算法的主要思想[7]:已知数据样本集S,样本个数s,样本所属类别集合为C,设共有m个{c1,c2,…,cm-1,cm},把S 分为m个样本子集为S={S1,S2,…,Sm-1,Sm},样本集Si中样本的个数为si。样本集的信息熵表示为:

设样本集集合S 中某个属性为A,A 有n个不同的属性值{a1,a2,…,an-1,an}。基于A的属性值把S划分为n个样本子集:S={S1,S2,…,Sn-1,Sn},sij表示为Sj(j=1,2,…,n)中属于类ci(i=1,2,…,m)的个数,pij表示为样本子集Sj中样本属于有类ci的概率:

子集Sj的信息熵为:

根据属性A 划分后的样本集合的信息熵为:

信息增益:

选择属性对结点进行划分的标准就是选取信息增益最大的属性。
1.2 粗糙集理论及属性重要度
定义1 在信息表S中,对于属性集I⊆A,可构成对应的二元等价关系:

式中,f(x)表示对象x 在属性I 上的属性值,称为由I 构成的不可分辨关系。……
登录APP查看全文
