PaperlayerView exact revision on arXiv

Source-linked AI summary

Covering rough sets based on neighborhoods: An approach without using neighborhoods

Ping Zhu

arXiv:0911.5394v2cs.AI

TL;DR

Equivalence relations are too restrictive for many rough-set applications, and topological neighborhoods have also been applied to covering rough sets. This paper gives an equivalent neighborhood-free definition of the neighborhood-based upper approximation and studies operations on coverings and homomorphisms. It examines which lower and upper approximation properties these operations and homomorphisms preserve.

  • Problem

    Equivalence relations are too restrictive for many applications, motivating covering-based rough sets and further study of their neighborhood-based formulations.

    Source: §1 · p. 1

  • Method

    The paper characterizes the neighborhood-based upper approximation without neighborhoods and introduces covering operations and homomorphisms between covering approximation spaces.

    Source: §1 · p. 2

  • Results

    The upper approximation based on neighborhoods has an equivalent definition without neighborhoods, and the paper verifies preservation properties of lower and upper approximations under operations and homomorphisms.

    Source: §2.2 · p. 3, §5 · p. 11

  • Takeaways & Limitations

    The subcovering characterization provides a non-neighborhood route to the upper approximation, while neighborhoods can still characterize local properties of elements.

    Source: §2.2 · p. 3

    The work focuses on neighborhood-based covering rough sets; extending its operations and homomorphisms to other types remains open.

    Source: §5 · p. 11

Abstract

from arXiv · show

Rough set theory, a mathematical tool to deal with inexact or uncertain knowledge in information systems, has originally described the indiscernibility of elements by equivalence relations. Covering rough sets are a natural extension of classical rough sets by relaxing the partitions arising from equivalence relations to coverings. Recently, some topological concepts such as neighborhood have been applied to covering rough sets. In this paper, we further investigate the covering rough sets based on neighborhoods by approximation operations. We show that the upper approximation based on neighborhoods can be defined equivalently without using neighborhoods. To analyze the coverings themselves, we introduce unary and composition operations on coverings. A notion of homomorphismis provided to relate two covering approximation spaces. We also examine the properties of approximations preserved by the operations and homomorphisms, respectively.

1. Introduction

Classical rough sets use equivalence relations to model indiscernibility, but coverings relax that restriction. This paper examines neighborhood-based covering rough sets, including an equivalent neighborhood-free upper approximation and preservation properties under covering operations and homomorphisms.

1. Introduction

  • Rough sets address uncertainty and incomplete information, but equivalence-based indiscernibility is too restrictive for many applications, motivating coverings.Source: §1 · p. 1
  • Because coverings are fundamental in topology, researchers have explored topological views of covering rough sets, including neighborhood-based upper approximations.Source: §1 · pp. 1–2
  • The neighborhood-based upper approximation has an equivalent definition without neighborhoods.The paper also notes that neighborhoods can still characterize local properties of elements.Source: §1 · p. 2
  • The paper introduces unary and composition operations on coverings and homomorphisms between covering approximation spaces, examining which approximation properties they preserve.Source: §1 · p. 2

2. Covering rough sets based on neighborhoods

The section extends partition-based rough sets to coverings and defines approximations using neighborhoods. It then gives a neighborhood-free characterization of the upper approximation and relates approximation behavior to the structure of coverings.

2.1. Approximations by neighborhoods

  • For a covering that is a partition, the neighborhood-based lower and upper approximations coincide with Pawlak’s approximations.A covering is a family of nonempty subsets whose union is the universe; a neighborhood is the intersection of covering elements containing an element.Source: §2.1 · pp. 2–3

2.2. An equivalent characterization of the upper approximation

  • The upper approximation of X equals the intersection of all subcoverings of X, providing a definition that does not use neighborhoods.The paper describes neighborhood computation as bottom-up and subcovering computation as top-down; neither is generally established as easier, though each may suit different sizes of X.Source: §2.2 · pp. 3, 5

2.3. Relationships between the lower and upper approximations

  • Two coverings yield the same lower and upper approximations for every X if and only if their reducts are identical.A reduct removes reducible covering elements; the paper also states that adding all definable sets to a covering leaves its approximations unchanged.Source: §2.3 · pp. 5–6

3. Operations on coverings

The section introduces unary and composition operations on coverings to facilitate their computation. It examines which lower and upper approximations these operations preserve.

3. Operations on coverings

  • Unary and composition operations modify or combine coverings to facilitate computation.The section also examines preservation of lower and upper approximations under these operations.Source: §3 · p. 6

3.1. Unary operations

  • The reduct operation is idempotent and preserves both approximations; int and the neighborhood operator preserve upper approximations.The upper approximations are preserved under int because neighborhoods remain unchanged, and the neighborhood operator is also stated to preserve them.Source: §3.1 · pp. 6–8
  • The int operation retains non-intersectional elementary sets, but it may fail to preserve lower approximations.The section gives an example where the lower approximation under the original covering strictly contains the one under int(C).Source: §3.1 · pp. 6–7

3.2. Composition operations

  • The union operation collects the sets in two coverings, while their intersection is formed from neighborhoods under their union; C1 ∧ C2 = nei(C1 ∨ C2).The section introduces these compositions to construct a new covering from two coverings and examine approximation relationships.Source: §3.2 · pp. 8–9

4. Homomorphisms between covering approximation spaces

The section defines homomorphisms between covering approximation spaces and examines how lower and upper approximations behave under them. Homomorphisms preserve lower approximations by inclusion, while isomorphisms preserve both approximations exactly.

  • Homomorphisms provide a way to relate different coverings associated with different agents or moments in time.Source: §4 · p. 9
  • A homomorphism maps each member of one covering to a member of the other, equivalently mapping definable sets to definable sets.Source: §4 · p. 9
  • Identity maps between coverings show that homomorphism direction can be asymmetric: C maps to nei(C), but not generally in reverse, and int(C) maps to C, but not generally in reverse.Source: §4 · p. 9
  • A homomorphism guarantees f(X−) ⊆ f(X)−, but no general inclusion relates f(X+) and f(X)+.A counterexample gives incomparable images of the upper approximations.Source: §4 · p. 10
  • For an isomorphism f, f(X−) = f(X)− and f(X+) = f(X)+ for every X ⊆ U.Source: §4 · p. 10
  • Under an isomorphism, the neighborhood of each element maps exactly to the neighborhood of its image.Source: §4 · p. 10

5. Conclusion

The paper establishes a neighborhood-free equivalent definition of the neighborhood-based upper approximation and studies how covering operations and homomorphisms preserve approximations. Its scope is mainly neighborhood-based covering rough sets, leaving other types and additional topological maps for future study.

  • The upper approximation based on neighborhoods has an equivalent definition that does not use neighborhoods.Source: §5 · p. 11
  • The unary operators int and nei can simplify upper-approximation computation through preprocessing, while ∨ and ∧ help estimate approximations in some cases.Source: §5 · p. 11
  • Homomorphisms, especially isomorphisms, make approximations comparable across covering approximation spaces by preserving lower and upper approximations under the stated operators and mappings.Source: §5 · p. 11
  • The work focuses mainly on neighborhood-based covering rough sets; operations for other types and continuous maps or homeomorphisms remain to be examined.Source: §5 · p. 11
Loading 0911.5394v2…