用序关系求信息熵核的高效算法  

Efficient Algorithm for Computing the Core Based on Information Entropy with Order Relation

作　　者：徐章艳[1,2] 杨波[1] 舒文豪[1] 杨炳儒[2] 

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

出　　处：《小型微型计算机系统》2010年第9期1829-1832,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60963008;60463003)资助;广西教育厅科研基金项目(200807MS015)资助;广西师大博士启动基金

摘　　要：目前设计基于信息熵的求核算法的主要方法是差别矩阵方法.在该种方法中,是通过搜索差别矩阵的所有差别元素得到核.由于是在所有的差别元素上搜索,故该方法比较耗时.为此,在简化决策表和简化差别矩阵的基础上,得到了核的一个新性质:当把简化决策表的对象按其条件属性值看成一个数时,其对象有序.利用这个序,只需判断简化差别矩阵的少量差别元素就可以找到核属性集.在此基础上,设计了一个高效求核算法,其时间复杂度m ax{O(|C|2|U/C|),O(|C‖U|)},其空间复杂度为O(|U|).由于新算法只判断简化差别矩阵的少量差别元素就可以找到核算属性集,故新算法的效率得到了有效地改善.At present,the main method of designing algorithm for computing the core based on information entropy is discernibility matrix.In this method,the core is found by discovering all discernibility elements of discenibility matrix.So this method is very time consuming.For improving the efficient of computing the core based on information entropy,a new property of the core based on the simplified decision table and simplified discernibility matrix is found.The new property is that the objects with condition attribute value of simplified decision table are order when they are looked as numbers.The core based on information entropy can be found to use the order only by searching a small quantity of discernibility elements of the simplified discernibility matrix.On this condition,an efficient computing core is designed.The time complexity and space complexity are max{O（｜C‖U｜）,O（｜C｜2｜U/C｜）} and O（｜U｜）,respectively.Since the core can be found by searching a small quantity of discerniblity elements of discernibility matrix in the new algorithm,the efficiency of the new algorithm is improved.Finally,an example is used to illustrate the effectivity of the proposed algorithm.The experimental results show our algorithm is not only efficient,but also is suitable for dealing with large decision table.

关 键 词：粗糙集 简化决策表 信息熵 核 算法复杂度 

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