基于正区域的快速求核算法

• 作者: 崔巍 徐章艳 李凡
• 来源期刊: 华中科技大学学报（自然科学版）
• 学科: 工学
• 关键词: 粗糙集 决策表 简化决策表 属性约简 复杂度 核
• 年，卷（期）: 2007,（12）
• 页码范围: 20-23
• 页数: 4页
• 分类号: TP18
• 字数: 3587字
• 语种: 中文
• DOI: 10.3321/j.issn:1671-4512.2007.12.006

摘要

基于正区域求核算法的最好时间复杂度为O(|C|2|U|log|U|),为降低该求核算法的时间复杂度,给出了基于正区域的简化决策表定义和相应核的定义.证明了该简化决策表的核与原决策表的核等价.由于求正区域的简化决策表首先要求划分U/C,而求划分U/C的最好算法的时间复杂度为O(|C||U|log|U|),因此以基数排序的思想设计了一个新的求划分U/C的算法,其时间复杂度为O(|C||U|).最后以快速缩小搜索空间为目的设计了一个新的求正区域POSC(D)的算法.在此基础上,利用核的性质设计了一个新的求核算法,其时间复杂度为max(O(|C||U|,O(|C|2|U/C|)).并用实例说明了算法的实用性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐章艳	广西师范大学计算机系	120	1992	21.0	40.0
2	李凡	华中科技大学计算机科学与技术学院	98	1647	20.0	37.0
3	崔巍	北京科技大学经济管理学院	11	93	8.0	9.0