关于属性约简和集合覆盖问题的探讨

论文探讨了粗糙集的属性约简和集合覆盖问题之间的联系。通过构造信息系统的相关矩阵将粗糙集的属性约简问题与集合覆盖问题联系起来,从而将粗糙集的属性约简问题简化为集合覆盖问题。然后用几个定理及其证明说明了这种联系是存在的。基于这种联系,推断出求最小属性约简问题算法的近似度的上下界为ln(｜U'｜)-lnln(｜U'｜)+O(1)和(1-o(1))ln(｜U'｜)。最后,利用两个范例分别演示了如何具体地构造相关矩阵以及如何将解决集合覆盖问题的思想和方法应用到解决属性约简问题中来,由此推理如果将文献5中的解决集合覆盖问题的启发式方法应用到解决最小属性约简中,属性约简的复杂度为o(r2m3+m2),并且能以78%的“概率”得到最小属性约简。

A Study of Reduction of Attributes and Set Covering Problem

This paper discusses the relationship between the reduction of attributes and set covering by constructing the relation matrix and then gives several theorems to interpret this relationship.The authors deduce the upper bound and the lower bound of approximation is ln(｜U '｜)-lnln(｜U '｜)+O(1)and(1-o(1))ln(｜U '｜)respectively.In the end they give two examples to demonstrate how to construct the relation matrix and how the ideas and methods of set covering can be applied into the problem of reduction of attributes.And at the same time we can infer that complexity and the precision of the reduction of attributes is o(r 2 m 3 +m 2 )and78percent respectively from the heuristic algorithm appearing in reference5.