Closed-set lattice and modular matroid induced by covering-based rough sets
详细信息 查看全文
- 作者：Lirun Su ; William Zhu
- 关键词：Closed ; set lattice ; Modular matroid ; Covering ; Rough sets ; Granular computing
- 刊名：International Journal of Machine Learning and Cybernetics
- 出版年：2017
- 出版时间：February 2017
- 年：2017
- 卷：8
- 期：1
- 页码：191-201
- 全文大小：
- 刊物类别：Engineering
- 刊物主题：Computational Intelligence; Artificial Intelligence (incl. Robotics); Control, Robotics, Mechatronics; Complex Systems; Systems Biology; Pattern Recognition;
- 出版者：Springer Berlin Heidelberg
- ISSN：1868-808X
- 卷排序：8
文摘
Covering is a common form of data representation, and covering-based rough sets, a technique of granular computing, provide an effective tool to deal with this type of data. However, many important problems of covering-based rough sets, such as covering reduction, are NP-hard so that most algorithms to solve them are greedy ones. Matroid theory, based on linear algebra and graph theory, provides well-established platforms for greedy algorithms. Lattice has been widely used in diverse fields, especially algorithm design, which plays an important role in covering reduction. Therefore, it is necessary to integrate covering-based rough sets with matroid and lattice. In this paper, we construct three types of matroids through covering-based rough sets and investigate their modularity. Moreover, we investigate some characteristics of these types of closed-set lattices induced by these three types of matroids and the relationships among these closed-set lattices. First, based on covering-based rough sets, three families of sets are constructed and proved to satisfy independent set axiom of matroids. So three types of matroids are induced by covering-based rough sets in this way. Second, some characteristics of these matroids, such as rank function, closure operator and closed set, are presented. Moreover, we investigate the characteristics of these closed-set lattices induced by these three types of matroids, such as modular pair, modular element. Finally, the relationships among these closed-set lattices induced by these three types of matroids are investigated. Especially, we prove that these three types of matroids induced by covering-based rough sets are all modular matroids.