一种基于决策表约简的集覆盖问题的近似解法

• 作者: 谭安辉 赵仕梅 陶玉枝
• 来源期刊: 南京大学学报（自然科学版）
• 学科: 工学
• 关键词: 决策表 粗糙集 属性约简 集覆盖 辨识矩阵 条件熵
• 年，卷（期）: 2018,（4）
• 页码范围: 821-828
• 页数: 8页
• 分类号: TP18
• 字数: 5289字
• 语种: 中文
• DOI: 10.13232/j.cnki.jnju.2018.04.018

摘要

集覆盖问题和决策信息表的约简问题分别是优化领域和信息处理领域重要的研究课题,但目前的研究大都针对这两个问题分别独立展开.通过分析集覆盖问题的解结构和决策信息表的布尔约简结构,将两者联系起来探讨.首先,给出一个集覆盖问题的布尔矩阵表示,并通过添加决策属性,对集覆盖中的集合进行分类,进一步诱导出一个以该布尔矩阵为条件属性值的决策信息表.其次,分析了决策表和集覆盖的辨识集之间的关系,证明了集覆盖问题的一个局部最优解恰好是该决策表的一个属性约简,即,求解集覆盖问题可等价地转化为求解决策表的属性约简问题.然后,利用决策表中的条件熵来度量集覆盖中一个集合在集族中的相对重要度,并构造了基于条件熵的集覆盖问题的近似算法.最后,运用实例验证了该算法的有效性和可行性,并将新算法与几个传统集覆盖算法进行了对比.实验结果表明,新算法在求得满意解上具有一定决策表;粗糙集;属性约简;集覆盖;辨识矩阵;条件熵的优势.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	谭安辉	浙江海洋大学数理与信息学院	8	29	3.0	5.0
5	陶玉枝	浙江海洋大学数理与信息学院	1	2	1.0	1.0
9	赵仕梅	浙江海洋大学数理与信息学院	1	2	1.0	1.0