集覆盖问题的粗糙集属性约简方法

An Attribute Reduction Method Based on Rough Sets for Set Covering Problem

集覆盖问题和粗糙集属性约简问题都是当前的研究热点,两者均有广泛的应用背景。目前,集覆盖理论与粗糙集理论的交叉研究还处于起步阶段。文章的工作主要是把集覆盖问题转化成测试代价敏感粗糙集属性约简问题,使得可应用粗糙集理论来研究集覆盖问题,目的在于丰富集覆盖理论与粗糙集理论的交叉研究。首先构造集覆盖的分辨矩阵,然后在该分辨矩阵上构造集覆盖对应的测试代价敏感信息系统模型,发现求解集合覆盖问题等价于求解对应测试代价敏感信息系统的最小测试代价约简。接着给出了基于正域正向近似加速器最小集覆盖问题的粗糙集解法。最后通过实例验证了该算法的可行性和有效性。

Set covering problems and rough set attribute reduction problems are both current research hotspots,and have extensive application backgrounds.At present,the intersection of set cover theory and rough set theory is still in its infancy.The work of this paper is mainly to transform set covering problems into attribute reduction problems in test-cost-sensitive rough sets,so that the rough set theory can be applied to study set covering problems and the cross research of set covering theory and rough set theory can be enriched.Firstly,a discernibility matrix of a set covering is constructed.Based on the discernibility matrix,a test-cost-sensitive information system model corresponding to the set covering is constructed.It is found that solving a set covering problem is equivalent to solving the minimum test cost reduction in the corresponding test-cost-sensitive information system.Then,a rough set method for minimal set covering problems based on positive approximation accelerator is proposed.Finally,the feasibility and effectiveness of the algorithm are verified by an example.