论文研究-一种基于知识粒度的启发式属性约简算法.pdf

所需积分/C币:8 2019-09-08 01:39:35 426KB .PDF

属性约简是粗糙集理论进行知识获取的核心问题之一。根据属性相似度与知识粒度的一致性,通过条件属性与决策属性以及条件属性之间的相似度度量,提出了一种基于知识粒度的启发式属性约简算法。根据条件属性与决策属性的相似度对条件属性进行降序排列,根据条件属性之间的相似度度量选择重要的属性,从而得到约简集合。理论分析与实验结果表明,该算法具有较高的运行效率和较好的约简效果。
马福民,张腾飞:一种基于知识粒度的启发式属性约简算法 2012,48(36) 33 性集中的属性不能被删除,并还原此属性。 表2样本信息表 根据上述性质,可以得到一个基于知识粒度的 b C D 启发式属性约简算法 输入:决策表S=<U,C∪D,V,/>,其中C,D分 别是条件属性和决策属性集。 40 输出:决策表中的一个相对约简。 0110 12012 步骤1计算各个条件属性与决策属性的相似度 6 第2步:进行降序排序,排序结果为b、c、a。 步骤2并根据相似度的值大小将条件属性进行 第3步:计算b与c、a间的属性相似度,So 降序排列C={c1,c2,…,Cn},n是条件属性的个数。 0.7378,S=0.5976,与s(D,b)比较,sm>sD,b),又 步骤3定义约简集C,赋初值C=C,冗余属因为sD,a)<D,b),所以将条件属性a放入集合 性集C=0,检验属性集C1=0,对集合C中的每个C中,将剩下的属性放入集合C1中,计算S(D,C)= 属性c1,令Cm=C-C1,执行如下操作: 04743,S(D,C)=0.4743,S(D,C)=S(D,C),那么 步骤31计算c1与集合Cm中条件属性c的相似就将集合C中的属性a删除,得到最后的约简(,c) 度s(,c),然后与xc,D)比较,如果s(e,c)≥s(c,D) 为进一步验证本文算法的优越性,选择与基于 则将属性c,赋给C,将集合Cn-c赋给C1。 分辨矩阵属性频率的算汏(记为A算法)、正域的属 步骤32计算sC1,D是否等于s(C,D若相等,性约简算法(记为B算法和文献6]基丁属性相似 则删除c,将集合C1赋给C,否则将保留c,C保度的属性约简算法(记为C算法)进行比较。选择6 持不变。 个UCI数据库表,根据属性从少到多排列,分类数是 步骤33若C中的条件属性没有完成遍历,则决策属性值的分类情况如表3所示 中直接转步骤3,若完成遍历则令=+1,Cn2=CR-c 表3UCI数据库的基本特征 若Cn=⑦,转步骤4,否则,转步骤3.1。 数据库属性数实例数分类数 Splice 3190 3 步骤4结束,输出相对约简集合C Uscensus 90 9338 32算法复杂性分析 Musk2 169 6598 目前很多的属性约简都要先求核属性,而本算 Arrhythmia 280 452 16 Isolet 618 1560 法是不需要求核的。假设一个决策表中条件属性的 Mult-Fcature 650 2000 个数是n,对象是m个。本文算法的时间复杂度:计 算属性的相似度,时间复杂度与n成正比,删除冗余 表4、表5记录了这5种算法在分类精度保持不 属性时最好的情况是将剩余属性都删除,最坏的情变的前提下,对上面每个数据库运行时间和结果 况是所有属性都没被删除,那么这部分的时间复杂 选择的属性条数,从表中可以看出,本文算法在处理 是n2,所以总的时间复杂是m+mn2。以下是本文高维数据时比别的算法效率要高,并且得到更为精 算法与一些常见算法在时间复杂度的比较。 简的属性约简结果。 表4算法的运行时间对比 表1各算法的时间复杂度比较结果 数据库文算法A算法B算法C算法 算法名称 时间复杂度 1580 23431905 1389 基于分辨矩阵属性频率 Uscensus90 4098 760l 19675005 基于正域属性约简 n m Musk2 基于属性相似度的属性约简n(mn2+m) 790018066890310096 arrhythmia 1509 223320028907 本文算法 刀1n+mn Isolet 14980 170257798639086 33算法实例应用 Mult- Fcatures18034163711125192678435 为了验证本文算法的可行性,选择如表2的样本 从算法的运算结果可以看出,在处理小数据集 信息表,a、b、c为条件属性,D为决策属性。 时,运行时间区别不大,当处理高维数据库时,本文 第1步:由属性相似度公式(2)计算可以得到算法的计算速度明显优于其他算法,说明本文算法 s(D,a)=0.527,(D.b)=0.6,s(D,c)=0.5976 (下转38页)

...展开详情
试读 3P 论文研究-一种基于知识粒度的启发式属性约简算法.pdf
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-一种基于知识粒度的启发式属性约简算法.pdf 8积分/C币 立即下载
    1/3
    论文研究-一种基于知识粒度的启发式属性约简算法.pdf第1页

    试读已结束,剩余2页未读...

    8积分/C币 立即下载 >