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

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

属性约简是粗糙集理论的重要研究内容之一,主要是用于去除高维数据的冗余信息。利用图论求约简是覆盖决策信息系统属性约简的一个新方法,其将覆盖决策系统的约简等价于超图的极小顶点覆盖。本研究提出一种新的覆盖决策信息系统的属性约简算法,该算法采用三步策略:首先确定覆盖决策信息系统的辨识集,然后得到超图的关联矩阵,最后用贪心法求出超图的极小顶点覆盖。实验结果表明,新的属性约简算法能够有效地降低数据维数和时间复杂度。

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.