On Links between Rough Sets and Digital Topology

Abstract

Rough set theory is a powerful tool for dealing with uncertainty, granularity, and incompleteness of knowledge in information systems. In addition, digital topology deals with properties and features of two-dimensional or three-dimensional digital images that correspond to topological properties of objects. So, we try to describe the relationship between rough sets and digital topology. Firstly, we will study the classifications of topologies in rough sets. Secondly, we will use the upper approximation operator to span the digital line, which is the basic building block of the digital spaces.

Share and Cite:

Abo-Tabl, E. (2014) On Links between Rough Sets and Digital Topology. Applied Mathematics, 5, 941-948. doi: 10.4236/am.2014.56089.

1. Introduction

The theory of rough sets, proposed by Pawlak [1] [2] , is an extension of the set theory for the study of intelligent systems characterized by insufficient and incomplete information. Using the concepts of the lower and the upper approximations from the rough set theory, knowledge hidden in information systems may be unraveled and expressed in the form of decision rules [2] [3] .

The classical rough approximations are based on equivalence relations, but this requirement is not satisfied in some situations. Thus the classical rough approximations have been extended to the similarity relation based rough sets [4] [5] , the tolerance relation based rough sets [6] , the dominance relation based rough sets [7] , the arbitrary binary relation based rough sets [8] -[10] and the covering-based rough sets [11] -[13] .

An interesting and natural research topic in rough set theory is to study rough set theory via topology. Indeed, Polkowski [14] pointed: topological aspects of rough set theory were recognized early in the framework of topology of partitions. Skowron [15] and Wiweger [16] separately discussed this topic for classical rough set theory in 1988. Polkowski [17] constructed and characterized topological spaces from rough sets based on information systems. Kortelainen [18] considered relationships between modified sets, topological spaces and rough sets based on a pre-order. Skowron et al. [6] [19] generalized the classical approximation spaces to tolerance approximation spaces, and discussed the problems of attribute reduction in these spaces (also see [20] ). Lashin et al. [21] introduced the topology generated by a subbase, also defined a topological rough membership function by the subbase of the topology. In addition, connections between fuzzy rough set theory and fuzzy topology were also investigated (see [22] -[24] ).

General topology has been considered as the entrance to understanding topology science, moreover the base of general topology is the topological space, which has been considered as a representation of universal space in general, and geometric shape in special, also the mathematical analysis concepts. The general topology has become the appropriated frame for every collection connected by relations. Topology is also a mathematical tool to study information systems and rough sets [15] [21] .

General topology has applications in the theory of image processed by exhibiting algorithms, which apply current knowledge of digital topology (i.e., the study of the geometric and topological properties of digital images [25] ). The problems that might arise are, for example finding connected components, set boundaries or any other operations which are needed in image processing. The well-known digital Jordan curve theorem is proved by using topological approach [26] -[28] . The theorem is important in the theory of computer graphics.

The basic building block of the digital n-space is the digital line or the so called Khalimsky line [26] [29] -[31] . This is the set of the integers, Z, equipped with the topology K, generated by as a subbase. Thus a set U is open in K if and only if whenever is an even integer, then. Nowadays, this topology, called the Khalimsky topology, is one of the most important concepts of the digital topology. It has been studied and used by many authors, e.g., [26] -[37] .

The remainder of this paper is organized as follows. In Section 2, we present the fundamental concepts and properties of Pawlak’s rough set theory, general topology and digital topology. Section 3 presents the classifications of topologies in rough sets using the properties of the binary relations. In addition, we use the upper approximation operator to obtain the digital line, which is the basic building block of the digital spaces in Section 4 to try to describe the link between rough sets and digital topology. This paper concludes in Section 5.

2. Preliminaries

In this section, we introduce a review of some basic concepts of topological space and Pawlak approximation space.

A topological space is a pair consisting of a set U and family τ of subset of U satisfying the following conditions:

(T1) and.

(T2) τ is closed under arbitrary union.

(T3) τ is closed under finite intersection.

The pair is called a space, the elements of U are called points of the space, the subsets of U belonging to τ are called open sets in the space, and their complement are called closed sets in the space; the family τ of open subsets of U is also called a topology for U [38] .

Definition 2.1. [39] A topology τ on the set U is called an Alexandroff topology if the intersection of arbitrarily many open sets is still open, or equivalently, the union of arbitrarily many closed sets is still closed.

Definition 2.2. [37] Let U be a nonempty set and cl: be a function. The space is called Smyth space if the following conditions hold.

1)2)3).

Definition 2.3. For the set of integer Z we have:

(1) In Z the 2-neighbors of x is(2) In Z2 the 4-neighbors of is

(3) In Z2 the 8-neighbors of is

.

Definition 2.4. Let X be a nonempty set. Then the following are defined.

1) A relation R on a set X is reflexive if and only if xRx for all x in X.

2) A relation R on a set X is symmetric if and only if xRy implies yRx.

3) A relation R on a set X is transitive if xRy, yRz, then xRz.

A relation R on a set X is called an equivalence relation if it is reflexive, symmetric and transitive.

Definition 2.5. [2] Let R be an equivalence relation on a nonempty set U. For any subset, the lower and upper approximations of A according to R are then defined as

where [x]R is called an equivalence class of.

Yao [37] extended the Pawlak’s definitions of a rough set to any binary relation R as follows:

Definition 2.6. For the pair, the set xR is defined as called the right neighborhood of an element.

Definition 2.7. Let R be any binary relation on a nonempty set U. For any subset, the lower and the upper approximations of A according to R are then defined as

Obviously, if R is an equivalence relation, and these definitions are equivalent to the original Pawlak’s definitions.

We list the properties that are of interest in the theory of rough sets, let:

L1., where AC denotes the complementation of A in U.

L2..

L3..

L4..

L5..

L6..

L7..

L8..

L9..

L10..

U1..

U2..

U3..

U4..

U5.

U6.

U7..

U8..

U9.

U10..

Properties L1 and U1 state that two approximations are dual to each other. Hence, properties with the same numbers may be regarded as dual properties. Properties L9, L10, U9 and U10 are expressed in terms of set inclusion. The standard version using set equality can be derived from L1 - L10 and U1 - U10. For example, it follows from L7 and L9 that. It should also be noted that these properties are not independent.

We can find the basic axioms for extended topological spaces in Table 1.

3. Topology Classifications Based on Rough Sets

In this section, we discuss the classification of topologies in the theory of rough sets.

Proposition 3.1. For any relation R on a nonempty set U and for every the properties L1 - L5 and U1 - U5 hold according to Definition 2.7.

Proof. See [9] .

Example 3.1. Let be a relation on a nonempty set. Then, , and. Then is not a topology on U.

Theorem 3.1. Suppose that is a rough approximation space. If satisfies the properties L1 - L5 and U1 - U5, then is a Smyth space [37] .

Proposition 3.2. For any reflexive relation R on a nonempty set U and for every the properties L1 - L7 and U1 - U7 hold according to Definition 2.7.

Proof. See [9] .

Example 3.2. Let be a reflexive relation on a nonempty set. Then and. Then is a topology on U.

Theorem 3.2. If satisfies the properties L1 - L7 and U1 - U7, then is a pre-topology or Čech closure space.

Proposition 3.3. For any reflexive and symmetric relation R on a nonempty set U and for every the properties L1 - L8 and U1 - U8 hold according to Definition 2.7.

Proof. See [9] .

Example 3.3. Let be a reflexive and symmetric relation on a nonempty set. Then and. Then is a topology on U in which each open (closed) set is also closed (open) set.

Theorem 3.3. If satisfies the properties L1 - L8 and U1 - U8, then is a pre-topology or Čech closure space in which each open (closed) set is also closed (open).

Proposition 3.4. For any reflexive and transitive relation R on a nonempty set U and for every the properties L1 - L7, L9, U1 - U8 and U9 hold according to Definition 2.7.

Proof. See [9] .

Example 3.4. Let be a reflexive and transitive relation on a nonempty set. Then and. Then is an Alexandroff topology on U.

Birkhoff [40] showed that there exists a one-to-one correspondence between the set of all reflexive and transi

Table 1. The basic axioms for extended topological spaces.     

tive binary relations and Alexandroff topologies.

Theorem 3.4. If satisfies the properties L1 - L7, L9, U1 - U7 and U9, then is an Alexandroff topological space.

Proposition 3.5. For any equivalence relation R on a nonempty set U and for every the properties L1 - L10 and U1 - U10 hold according to Definition 2.7.

Proof. See [9] .

Example 3.5. Let be an equivalence relation on a nonempty set. Then and. Then is a topology on U in which each open (closed) set is also closed (open) set, and socalled clo-open topology.

Theorem 3.5. If satisfies the properties L1 - L10 and U1 - U10, then is an Alexandroff topological space in which each open (closed) set is also closed (open) set, and so-called clo-open space.

We summarize these results in Table 2, which indicates the generalized topological spaces depending on the properties of rough sets.

4. Connecting Digital Topology and Rough Sets

In this section, we try to get the structure of digital topology from the concepts of the theory of rough sets (the upper approximate operator).

Definition 4.1. Let R be any relation on a set of integer Z. We define another relation R' on Z as follows:

on the other hand, we can write the relation R′ in an equivalent form as follows:

Theorem 4.1. 1) The relation R on Z is reflexive if and only if R′ is also reflexive.

2) The relation R on Z is transitive if and only if R′ is also transitive.

Proof. 1) Let R be a reflexive relation on is reflexive.

2) Assume that xR′y and yR′z, then and and yRz, hence by transitivity of R we get xRz, thus, that implies xR′z. Therefore R′ is transitive. Conversely, suppose that xRy and yRz, then and, that implies xR′y and yR′z, hence by transitivity of R′ we get xR′z, thus, so that xRz. Therefore R is transitive.

The following conditions hold on Z using the relation →1) if two points are 2-neighbors, then either x → y or y → x2) if two points are not 2-neighbors, then both x →  y and y →  x not hold.

Lemma 4.1. If such that and, then we have either or.

Proof. By condition (1) we have either or. Let. By condition (1) either or. If, then by transitivity which contradiction to condition (2). Hence.

Then by Lemma 4.1 we can draw the graph of the relation → as follows (Figure 1).

Note that, in the line → ○ ← is equivalent to the open set containing the element “○” and ← □ → is equivalent to the closed set containing the element “□”, also the digital line is an Alexandroff topology.

Now, if we consider R is a relation on Z2, then the following conditions hold:

a) If two points are 4-neighbors, then either x → y or y → x,

Table 2. Generalized topological spaces defining axioms are indicated by٭. 

b) If two points are not 8-neighbors, then both x → y and y → x not hold.

Lemma 4.2. If which are in the same horizontal or vertical gride line of Z2 such that and, then we have either or on a gride line.

Proof. By condition a) we have either or. Let. Also, by condition a) either or. If, then by transitivity which contradiction to condition b). Hence.

In the plane note that, the element “○” is equivalent to the open-open, the element “□” is equivalent to the closed-closed, and the element “●” is called the mixed point and equivalent to the open-closed or the closedopen.

We must note that, there are two topologies on Z2 which satisfy the conditions 1 and 2, one of them was described in Khalimsky et al. [26] and the other was introduced by Marcus et al. [41] .

Figure 2 describe the topology in [26] . Furthermore, if there is no mixed point, then we have the topology in [41] , which described in Figure 3.

Figure 1. Khalimsky line.                                             

Figure 2. Khalimsky topology in the plane.                          

Figure 3. Marcus topology in the plane.          

5. Conclusions

In short, topology is a branch of mathematics, whose concepts are fundamental not only to all branches of mathematics, but also in real life applications. Image plays important role in real life. In the past the process of image analysis took place via various mathematical models with an acceptable amount of error. Digital topology is a new accurate approach.

So we use the theory of rough sets to generate the digital spaces, in order to narrow the gap between rough sets and digital topology.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1] Pawlak, Z. (1982) Rough Sets. International Journal of Computer and Information Science, 11, 341-356.
http://dx.doi.org/10.1007/BF01001956
[2] Pawlak, Z. (1991) Rough Sets: Theoretical Aspects of Reasoning about Data. Kluwer Academic Publishers, Boston.
http://dx.doi.org/10.1007/978-94-011-3534-4
[3] Kryszkiewicz, M. (1998) Rough Set Approach to Incomplete Information Systems. Information Sciences, 112, 39-49.
http://dx.doi.org/10.1016/S0020-0255(98)10019-1
[4] Abo-Tabl, E.A. (2013) Rough Sets and Topological Spaces Based on Similarity. International Journal of Machine Learning and Cybernetics, 4, 451-458.
http://dx.doi.org/10.1007/s13042-012-0107-7
[5] Slowinski, R. and Vanderpooten, D. (2000) A Generalized Definition of Rough Approximations Based on Similarity. IEEE Transactions on Knowledge and Data Engineering, 12, 331-336.
http://dx.doi.org/10.1109/69.842271
[6] Skowron, A. and Stepaniuk, J. (1996) Tolerance Approximation Spaces. Fundamenta Informaticae, 27, 245-253.
[7] Zhang, H., Ouyang, Y. and Wangc, Z. (2009) Note on Generalized rough Sets Based on Reflexive and Transitive Relations. Information Sciences, 179, 471-473.
http://dx.doi.org/10.1016/j.ins.2008.10.009
[8] Liu, G.L. and Zhu, W. (2008) The Algebraic Structures of Generalized Rough Set Theory. Information Sciences, 178, 4105-4113.
http://dx.doi.org/10.1016/j.ins.2008.06.021
[9] Yao Y.Y. (1998) Relational Interpretations of Neighborhood Operators and Rough Set Approximation Operators. Information Sciences, 111, 239-259.
http://dx.doi.org/10.1016/S0020-0255(98)10006-3
[10] Zhu, W. (2009) Relationship between Generalized Rough Sets Based on Binary Relation and Covering. Information Sciences, 179, 210-225.
http://dx.doi.org/10.1016/j.ins.2008.09.015
[11] Liu, G.L. and Sai, Y. (2009) A Comparison of Two Types of Rough Sets Induced by Coverings. International Journal of Approximate Reasoning, 50, 521-528.
http://dx.doi.org/10.1016/j.ijar.2008.11.001
[12] Zhu, W. (2007) Topological Approaches to Covering Rough Sets. Information Sciences, 177, 1499-1508.
http://dx.doi.org/10.1016/j.ins.2006.06.009
[13] Zhu, W. (2009) Relationship among Basic Concepts in Covering-Based Rough Sets. Information Sciences, 179, 24782486.
http://dx.doi.org/10.1016/j.ins.2009.02.013
[14] Polkowski, L. (2002) Rough Sets: Mathematical Foundations. Physica-Verlag, Heidelberg.
http://dx.doi.org/10.1007/978-3-7908-1776-8
[15] Skowron, A. (1988) On Topology in Information System. Bulletin of Polish Academic Science and Mathematics, 36, 477-480.
[16] Wiweger, A. (1988) On Topological Rough Sets. Bulletin of the Polish Academy of Sciences Mathematics, 37, 51-62.
[17] Polkowski, L. (2001) On Fractals Defined in Information Systems via Rough Set Theory. Proceedings of the RSTGC-2001. Bulletin International Rough Set Society, 5, 163-166.
[18] Kortelainen J. (1994) On Relationship between Modified Sets, Topological Spaces and Rough Sets. Fuzzy Sets and Systems, 61, 91-95.
http://dx.doi.org/10.1016/0165-0114(94)90288-7
[19] Skowron, A., Swiniarski, R. and Synak, P. (2005) Approximation Spaces and Information Granulation. Transactions on Rough Sets III: Lecture Notes in Computer Science, 3400, 175-189.
http://dx.doi.org/10.1007/11427834_8
[20] Jarvinen, J. and Kortelainen, J. (2007) A Unifying Study between Model-Like Operators, Topologies, and Fuzzy Sets. Fuzzy Sets and Systems, 158, 1217-1225.
http://dx.doi.org/10.1016/j.fss.2007.01.011
[21] Lashin, E., Kozae, A., Khadra, A.A. and Medhat, T. (2005) Rough Set Theory for Topological Spaces. International Journal of Approximate Reasoning, 40, 35-43.
http://dx.doi.org/10.1016/j.ijar.2004.11.007
[22] Li, T.J., Yeung, Y. and Zhang, W.X. (2008) Generalized Fuzzy Rough Approximation Operators Based on Fuzzy Covering. International Journal of Approximate Reasoning, 48, 836-856.
http://dx.doi.org/10.1016/j.ijar.2008.01.006
[23] Qin, K. and Pei, Z. (2005) On the Topological Properties of Fuzzy Rough Sets. Fuzzy Sets and Systems, 151, 601-613.
http://dx.doi.org/10.1016/j.fss.2004.08.017
[24] Srivastava, A.K. and Tiwari, S.P. (2003) On Relationships among Fuzzy Approximation Operators, Fuzzy Topology, and Fuzzy Automata. Fuzzy Sets and Systems, 138, 197-204.
http://dx.doi.org/10.1016/S0165-0114(02)00442-6
[25] Rosenfeld, A. (1979) Digital topology. The American Mathematical Monthly, 86, 621-630.
http://dx.doi.org/10.2307/2321290
[26] Khalimsky, E.D., Kopperman, R. and Meyer, P.R. (1990) Computer Graphics and Connected Topologies on Finite Ordered Sets. Topology and Its Applications, 36, 1-17.
[27] Kiselman, C.O. (2000) Digital Jordan Curve Theorems. Discrete Geometry for Computer Imagery (DGCI), 1953, 4656.
http://dx.doi.org/10.1007/3-540-44438-6_5
[28] Slapal, J. (2013) Topological Structuring of the Digital Plane. Discrete Mathematics and Theoretical Computer Science, 15, 165-176.
[29] Khalimsky, E.D., Kopperman, R. and Meyer, P.R. (1990) Boundaries in Digital Planes. Journal of Applied Mathematics and Stochastic Analysis, 3, 27-55.
http://dx.doi.org/10.1155/S1048953390000041
[30] Kong, T.Y., Kopperman, R. and Meyer, P.R. (1991) A Topological Approach to Digital Topology. The American Mathematical Monthly, 98, 901-917.
http://dx.doi.org/10.2307/2324147
[31] Kopperman, R., Meyer, P.R. and Wilson, R.G. (1991) A Jordan Surface Theorem for Three-Dimensional Digital Spaces. Discrete and Computational Geometry, 6, 155-161.
http://dx.doi.org/10.1007/BF02574681
[32] Bai, Y., Han, X. and Prince, J.L. (2009) Digital Topology on Adaptive Octree Grids. Journal of Mathematical Imaging and Vision, 34, 165-184.
http://dx.doi.org/10.1007/s10851-009-0140-7
[33] Eckhardt, U. and Latecki, L.J. (2003) Topologies for the Digital Spaces Z2 and Z3. Computer Vision and Image Understanding, 90, 295-312.
http://dx.doi.org/10.1016/S1077-3142(03)00062-6
[34] Melin, E. (2007) Digital Surfaces and Boundaries in Khalimsky Spaces. Journal of Mathematical Imaging and Vision, 28, 169-177.
http://dx.doi.org/10.1007/s10851-007-0006-9
[35] Slapal, J. (2003) Closure Operations for Digital Topology. Theoretical Computer Science, 305, 457-471.
http://dx.doi.org/10.1016/S0304-3975(02)00708-9
[36] Slapal, J. (2006) Digital Jordan Curves. Topology and Its Application, 153, 3255-3264.
[37] Smyth, M.B. (1995) Semi-Metrics, Closure Spaces and Digital Topology. Theoretical Computer Science, 151, 257-276.
http://dx.doi.org/10.1016/0304-3975(95)00053-Y
[38] Sierpenski, W. and Krieger, C. (1956) General Topology. University of Toronto, Toronto.
[39] Alexandroff, P. (1937) Diskrete Raume. Matematicheskii Sbornik, 2, 501-519.
[40] Birkhoff, G. (1937) Rings of Sets. Duke Mathematical Journal, 3, 383-548.
http://dx.doi.org/10.1215/S0012-7094-37-00334-X
[41] Marcus, D., Wyse, F., et al. (1970) A Special Topology for the Integers (Problem 5712). The American Mathematical Monthly, 77, 1119.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.