Tree Expressions for Information Systems  

作　　者：赵岷 韩素青 王珏 

机构地区：[1]NEC Research China, Beijing 100080, China [2]Department of Mathematics, Taiyuan Normal University, Taiyuan 030012, China [3]Institute of Automation, Chinese Academy of Sciences, Beijing 100080, China

出　　处：《Journal of Computer Science & Technology》2007年第2期297-307,共11页计算机科学技术学报（英文版）

基　　金：This work is partially supported by the National Grand Fundamental Research 973 Program of China under Grant No. 2004CB318103 and the National Nature Science Foundation of China under Grant No. 60573078.

摘　　要：The discernibility matrix is one of the most important approaches to computing positive region, reduct, core and value reduct in rough sets. The subject of this paper is to develop a parallel approach of it, called ＂tree expression＂. Its computational complexity for positive region and reduct is O（m^2 × n） instead of O（m × n^2） in discernibility-matrix-based approach, and is not over O（n^2） for other concepts in rough sets, where rn and n are the numbers of attributes and objects respectively in a given dataset （also called an ＂information system＂ in rough sets）. This approach suits information systems with n ≥ m and containing over one million objects.The discernibility matrix is one of the most important approaches to computing positive region, reduct, core and value reduct in rough sets. The subject of this paper is to develop a parallel approach of it, called ＂tree expression＂. Its computational complexity for positive region and reduct is O（m^2 × n） instead of O（m × n^2） in discernibility-matrix-based approach, and is not over O（n^2） for other concepts in rough sets, where rn and n are the numbers of attributes and objects respectively in a given dataset （also called an ＂information system＂ in rough sets）. This approach suits information systems with n ≥ m and containing over one million objects.

关 键 词：ALGORITHMS tree expression reduct theory 

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