摘要
基于正区域求核算法的最好时间复杂度为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|)).并用实例说明了算法的实用性.
At present,the time complexity of the best algorithm for computing core based on positive region is O(|C|2|U|log|U|).For reducing the computational complexity,simplified decision table for positive region and corresponding core were introduced at first.At the same time,it was proved that this core was equal to the core of the old decision table.Since it was first to compute the partition U/C before computing the simplified decision table for positive region.However the time complexity of the best algorithm ...
出处
《华中科技大学学报(自然科学版)》
EI
CAS
CSCD
北大核心
2007年第12期20-23,共4页
Journal of Huazhong University of Science and Technology(Natural Science Edition)
基金
国家自然科学基金资助项目(60663001)
关键词
粗糙集
决策表
简化决策表
属性约简
复杂度
核
rough set
decision table
simplified decision table
attribute reduction
complexity
core