基于图的覆盖决策信息系统属性约简新算法  

A New Attribute Reduction Algorithm for Covering Decision Information System Based on Graph

作　　者：张杰 张燕兰 林艺东 ZHANG Jie;ZHANG Yanlan;LIN Yidong(School of Computing,Minnan Normal University,Zhangzhou 363000,China;School of Mathematical Sciences,Xiamen University,Xiamen 361005,China)

机构地区：[1]闽南师范大学计算机学院,福建漳州363000 [2]厦门大学数学科学学院,福建厦门361005

出　　处：《海南师范大学学报（自然科学版）》2022年第1期16-24,共9页Journal of Hainan Normal University（Natural Science）

基　　金：福建省自然科学基金项目(2019J01749,2019J01748)。

摘　　要：属性约简是粗糙集理论的重要研究内容之一,主要是用于去除高维数据的冗余信息。利用图论求约简是覆盖决策信息系统属性约简的一个新方法,其将覆盖决策系统的约简等价于超图的极小顶点覆盖。本研究提出一种新的覆盖决策信息系统的属性约简算法,该算法采用三步策略:首先确定覆盖决策信息系统的辨识集,然后得到超图的关联矩阵,最后用贪心法求出超图的极小顶点覆盖。实验结果表明,新的属性约简算法能够有效地降低数据维数和时间复杂度。At present,attribute reduction is one of the important research issues for rough set theory and is mainly used to remove redundant information of high-dimensional data.It is proved that solving the attribute reduction of covering deci⁃sion information system is equivalent to finding the minimal vertex covering of a hypergraph.Our new attribute reduction al⁃gorithm was proposed with a three-step strategy.Firstly,the discernibility set of the covering decision information system was determined,then the incidence matrix of a hypergraph was specified and finally the minimal vertex cover of the hyper⁃graph with greedy method was found.Experimental results showed that the new attribute reduction algorithm can reduce the dimension of data as well as the time complexity effectively.

关 键 词：属性约简 顶点覆盖 图论 覆盖粗糙集 关联矩阵 

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