覆盖的两类拟阵结构

Two Matroidal Structures of Coverings

覆盖是属性约简中一种常见的数据表示,而覆盖粗糙集恰是处理这类数据的有效工具;拟阵是线性代数与图论的推广,目前已被广泛应用于许多领域特别是贪婪算法的设计,该算法在属性约简中起着重要的作用.鉴于此,有必要将拟阵与覆盖粗糙集相结合来解决此类优化问题.首先,本文通过横贯拟阵理论,构造了覆盖的拟阵结构;其次,利用该拟阵结构实现对覆盖的等价刻划;进一步,在该拟阵结构上定义了一类近似算子,通过证明上近似算子满足拟阵的闭包公理,从而诱导出另一个拟阵结构;最后研究了这两类拟阵结构之间的关系,而当覆盖退化到划分时,二者相等.

Coverings are the common forms of data representation, and covering-based rough sets serve as an efficient technique to process this type of data in attribute reductions. Matroids generalized from linear algebra and graph are widely used in many fields, especially greedy algorithm design which plays an important role in attribute reduction. Therefore, it is necessary to combine matroids with covering-based rough sets to solve these optimization issues. This paper constructs a matroidal structure of coverings through transversal matroids, and establishes certain equivalence characterizations for coverings by using the matroid. Furthermore,we define a type of approximation operators based on the matroid. Through proving the upper approximation operator satisfies the closure axiom of matroids, we induce the other matroidal structure of coverings. Finally, we study the relationship between .these two matroidal structures. It is interesting to find that these two matroidal structures are equal when coverings degrade into partitions.