基于幂树的决策表最小属性约简

• 作者: 吴克寿 孙金华 陈玉明
• 来源期刊: 南京大学学报：自然科学版
• 学科: 工学
• 关键词: 粗糙集 决策表 最小约简 幂树 属性约简
• 年，卷（期）: 2012,（2）
• 页码范围: 164-171
• 分类号: TP311.131
• 语种: 中文

摘要

粗糙集理论是一种新的处理不精确、不完全与不一致数据的数学理论工具，决策表属性约简是粗糙集理论研究的核心内容之一．针对决策表最小属性约简穷举算法时间复杂度较高问题，从改变决策表属性约简问题的知识表示入手，在决策表中引入树的表示方式，定义幂树表示约简问题空间，给出了旋转和回溯两种剪枝搜索方法．进一步针对决策表提出了基于幂树的最小属性约简完备性算法，该算法在幂树空间中进行穷举搜索，同时采用了旋转和回溯剪枝策略，提高了完备性算法的搜索效率，分析了算法的时间与空间复杂度，指出了完备性最小属性约简算法复杂度的指数级别特点．理论分析和实例表明该方法是有效可行的．

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吴克寿	厦门理工学院计算机科学与技术系	33	188	8.0	11.0
2	陈玉明	厦门理工学院计算机科学与技术系	27	163	8.0	11.0
3	孙金华	厦门理工学院计算机科学与技术系	18	55	5.0	6.0