基于信息熵的快速求核算法  

Quick Algorithm for Computing Core Based on Information Entropy

作　　者：徐章艳[1] 杨炳儒[2] 郭燕萍[1] 宋威[2] 

机构地区：[1]广西师范大学计算机系,广西桂林541004 [2]北京科技大学信息工程学院,北京100083

出　　处：《小型微型计算机系统》2007年第2期279-282,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金重点资助项目(69835001)

摘　　要：基于信息熵的求核算法的最好时间复杂度为O(C｜｜2｜U｜log｜U｜).为降低算法的时间复杂度,本文首先给出了基于信息熵的简化差别矩阵及相应核的定义,并证明了该核与基于信息熵的属性约简的核是等价的.然后以基数排序的思想设计了一个新的求U/C的算法,其时间复杂度为O(｜C｜｜U｜).在此基础上,设计了一个新求核算法,其时间复杂度被降为max{O(｜C｜｜U/C｜2),O(｜C｜｜U｜)}.最后用一个实例说明了新求核算法的高效性.At present, the time complexity of the best algorithm for computing core based on information entropy is O（｜C｜^2 ｜U｜log ｜U ｜）. For cutting down the time complexity, the definition of simplified discernibility matrix based on information entropy and the corresponding definition of core are first provided. At the same time, it is proved that this core is the same as the core based on information entropy. Then a new algorithm based on radix sorting for computing U/C is designed, its time complexity is O（ ｜C｜ ｜U｜）. On this condition, a new algorithm for computing core is designed, and its time complexity is cut down to max {O｜C｜｜U/C｜^2） ,O（ ｜C｜｜ U｜）}. At the end, an example is used to illustrate the efficient of this new algorithm.

关 键 词：ROUGH SET 信息熵 核 简化差别矩阵 复杂度 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]