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

摘要：

目前设计基于信息熵的求核算法的主要方法是差别矩阵方法.在该种方法中,是通过搜索差别矩阵的所有差别元素得到核.由于是在所有的差别元素上搜索,故该方法比较耗时.为此,在简化决策表和简化差别矩阵的基础上,得到了核的一个新性质:当把简化决策表的对象按其条件属性值看成一个数时,其对象有序.利用这个序,只需判断简化差别矩阵的少量差别元素就可以找到核属性集.在此基础上,设计了一个高效求核算法,其时间复杂度max{O(|C|2 |U/Cl),O(|C ||U|)},其空间复杂度为O(|U|).由于新算法只判断简化差别矩阵的少量差别元素就可以找到核算属性集,故新算法的效率得到了有效地改善.

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

所属期刊栏目：31

分类号：TP18(自动化基础理论)

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

在线出版日期：2011-01-06（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：1829-1832