=Paper=
{{Paper
|id=None
|storemode=property
|title=Nearness of Objects. Approximation Space Model Revisited
|pdfUrl=https://ceur-ws.org/Vol-928/0292.pdf
|volume=Vol-928
|dblpUrl=https://dblp.org/rec/conf/csp/PetersSS12
}}
==Nearness of Objects. Approximation Space Model Revisited==
https://ceur-ws.org/Vol-928/0292.pdf
Nearness of Objects.
Approximation Space Model Revisited
James F. Peters1 , Andrzej Skowron2 , and Jaroslaw Stepaniuk3
1
Department of Electrical and Computer Engineering,
University of Manitoba
Winnipeg, Manitoba R3T 5V6 Canada
jfpeters@ee.umanitoba.ca
2
Andrzej Skowron
Institute of Mathematics
Warsaw University
Banacha 2, 02-097 Warsaw, Poland
skowron@mimuw.edu.pl
3
Jaroslaw Stepaniuk
Department of Computer Science
Bialystok University of Technology
Wiejska 45A, 15-351 Bialystok, Poland
j.stepaniuk@pb.edu.pl
Dedicated to Zdzislaw Pawlak
Abstract. This paper is devoted to a nearness relation in an Efremovic̆-
proximity space. The basic approach is to consider the nearness of the
upper and lower approximation of a set introduced by Z. Pawlak during
the early 1980s as a foundation for rough sets. Two forms of nearness
relations are considered, namely, a spatial EF- and a descriptive EF-
relation. This leads to a study of the nearness of objects either spatially
or descriptively in the approximation of a set. The 2007 nearness approx-
imation space model is refined and extended in this paper, leading two
new forms of nearness approximation spaces. There is a natural transi-
tion from the two forms of approximation introduced in this article to
nearness of information granules. This leads to the study of methods of
inducing approximations of nearness relations for information granules
and the benefits of this approach for approximate reasoning over granular
computations.
Key words: Approximation space, EF-proximity space, information
granules, nearness relation, rough sets
1 Introduction
This paper introduces an extension of the Pawlak approximation space model
with a nearness relation in an EF-proximity space [1]. The basic approach is
to consider the nearness of the upper and lower approximations of a set, intro-
duced by Z. Pawlak during the early 1980s as cornerstones in the foundations of
rough sets [2–5]. Two forms of nearness relations are considered, namely, a spa-
tial nearness relation defined in a traditional Efremovic̆ (EF) proximity space [6]
and a relation defined on a descriptive EF-proximity space [7–9]. This leads to
a study of the nearness of objects either spatially or descriptively in the ap-
proximation of a set. The 2007 nearness approximation space model introduced
in [10, §3] is refined and extended in this paper, leading to two new forms of
nearness approximation spaces. There is a natural transition from the two forms
of approximation introduced in this article to nearness in a generalized approx-
imation space (GAS). In this article, approximation spaces are also considered
in the more general context of information granules (recently, this has led to
what is known as a rough granule calculus [11]). In keeping with the original
nearness approximation space model, Mitchell analogy-making [12] is revisited
and viewed in a more general setting in reasoning about concepts [10, §5].
2 Spatial and Descriptive Nearness
Let δ on a nonempty set X be a nearness (proximity) relation. For subsets
B, C in X, we write B δ C (meaning B is spatially near C), provided B ∩ C
is nonempty. If B is not near (far from) C (denoted by A δ C), then B ∩ C is
empty. Sets that are far from each other are called remote sets. Such nearness
(proximity) relation is also called a discrete proximity [1].
Example 1. Sample Remote Sets.
Let the nonempty set X with subsets A, B, C be represented by the picture in
Fig. 1.
Fig. 1. B δ C, A δ C and B δ X\C
In this picture, B δ C, since B ∩ C = B ̸= ∅. Also, A δ C in Fig. 1. The sets
A, C are examples of remote sets, since they are far from each other.
The relation δ ⊆ P(X) × P(X) is an Efremovic̆ proximity (also called an
EF-proximity), if and only if, for A, B, C ∈ P(X), the following axioms hold
[6, 1].
(EF.1) A δ B implies A and B are not empty.
(EF.2) A ∩ B ̸= ∅ implies A δ B.
(EF.3) A δ B implies B δ A (symmetry).
(EF.4) A δ (B ∪ C), if and only if, A δ B or A δ C.
(EF.5) Efremovic̆ axiom:
A δ B implies A δ C & B δ X\C for some C ⊆ X.
The pair (X, δ) is called an EF-proximity space. An EF-proximity is sepa-
rated, provided it satisfies (EF.6).
(EF.6) {x} δ {y} implies x = y.
Example 2. Illustration for the Efremovic̆ axiom.
Assume that (X, δ) is an EF-space, where the set X with subsets A, B are
represented by the picture in Fig. 1. A δ B (A and B are remote sets) and we
can find C so that B δ X\C, i.e., B is far from the complement of C (denoted
by C c ).
2.1 Pawlak Approximation Space
Let X be a nonempty set of objects, Φ a set of functions that represent ob-
ject features. For simplicity of reasoning, we assume that these are real valued
functions. We define an equivalence relation ∼ by
Φ
∼ = {(x, y) ∈ X × X : for all ϕ ∈ Φ, ϕ(x) = ϕ(y)} ,
Φ
where ϕ(x) ∈ ℜk for some k, where ℜ is the set of reals. Φ(x) is called the feature
value vector of x.
The relation ∼ is usually called an Φ-indiscernibility relation [3]. The pair
Φ
(X, ∼) is an approximation space, introduced by Z. Pawlak [2]. Let us assume
Φ
that x ∈ X. Then [x]Φ is an equivalence class in the partition X/∼Φ . Unions of
equivalence classes from X/∼Φ are called Φ-definable subsets of X.
The lower and upper approximations of E ⊆ X (denoted by Φ∗ E, Φ∗ E,
respectively) are defined by
∪
Φ∗ E = [x]Φ , lower approximation of E,
[x]Φ ⊆ E
∪
∗
Φ E= [x]Φ , upper approximation of E.
[x]Φ ∩E̸=∅
Let us observe that the lower approximation and the upper approximation
of E can be equivalently defined by
∪
Φ∗ E = [x]Φ ,
x∈X: Φ(x)∈ Φ(E)+
∪
Φ∗ E = [x]Φ ,
x∈X: Φ(x)∈ Φ(E)
where Φ(E) = {Φ(x) : x ∈ E}, Φ(E)+ = {v ∈ Φ(E) : ∀x(Φ(x) = v → x ∈ E)}.
The boundary region bdΦ (E) of E relative to Φ is defined by
bdΦ (E) = Φ∗ E \ Φ∗ E.
Let (X, ∼, δΦ ) denote a descriptive nearness approximation space, which is a
Φ
Pawlak approximation space endowed with the descriptive EF-proximity relation
δΦ .
2.2 Descriptive EF-Proximity Space
A descriptive EF-proximity is briefly presented in this section (see, e.g., [8, 7]).
Let X be a nonempty set, x a member of X, Φ = {ϕ1 , . . . , ϕn } a set of functions
that represent features of each x. Let Φ(x) denote a feature vector for the object
x, i.e., a vector of feature values that describe x. A feature vector provides a
description of an object. Let A, E be subsets of X. Let Φ(A), Φ(E) denote sets
of descriptions of members of A, E, respectively. Then we have Φ(x) ∈ Φ(A) iff
x ∈ Φ∗ (A) for any x ∈ X.
The expression A δΦ E reads A is descriptively near E. Similarly, A δ Φ E
denotes that A is descriptively far (remote) from E. The descriptive proximity
of A and E is defined by
A δΦ E ⇔ Φ(A) ∩ Φ(E) ̸= ∅.
The descriptive remoteness of A and E (denoted by A δ Φ E) is defined by
A δ Φ E ⇔ Φ(A) ∩ Φ(E) = ∅.
From the above definition one can obtain the following proposition:
Proposition 1. Let (X, ∼, δΦ ) be a descriptive nearness approximation space
Φ
and let A, E ⊆ X. Then, for descriptively near sets, the following statements are
equivalent.
(a) A δΦ E,
(b) ∃x ∈ X : [x]Φ ∩ A ̸= ∅ and [x]Φ ∩ E ̸= ∅,
(c) Φ∗ A ∩ Φ∗ E ̸= ∅.
This result is illustrated in Figure 2.
Fig. 2. Disjoint sets A and E are near because there exists an indiscernibility class
with nonempty intersection with both sets A, E.
Example 3. Sample Descriptively Remote Sets.
Let the nonempty set X with subsets A, B, C, E represented by the picture in
Fig. 3. Also, let Φ contain functions ϕg , ϕo , ϕy , ϕw used to measure the intensity
of the colours green (g), orange (o), yellow (y), and greylevel intensity (w) of
points x in X. In this picture, A δΦ E, since the description of A matches the
description of E. In addition, A δ Φ C and A δ Φ B in Fig. 1, since the description
of A does not match the descriptions of B and C. The sets A, B, C are examples
of pairwise descriptively remote sets, since their descriptions are far from each
other.
Fig. 3. A δΦ E, A δ C and B δ X\C
Define the descriptive intersection ∩ of subsets A and B of X by
Φ
A ∩ B = {x ∈ X : Φ(x) ∈ Φ(A) ∩ Φ(B)}.
Φ
We have A ∩ B = Φ∗ (A) ∩ Φ∗ (B). Hence, from Proposition 1, we also have
Φ
AδΦ B iff A ∩ B ̸= ∅.
Φ
Example 4. Sample Descriptive Intersection.
For the nonempty set X with subsets A, B, C, E be represented by the picture
in Fig. 3, observe that the sets A and E are spatially remote, but descriptively
near. In fact,
A ∩ E = Φ∗ A ̸= ∅ since Φ(A) = Φ(E) ̸= ∅.
Φ
By contrast, the sets B and C are spatially near. However, they are descriptively
remote, since
B ∩ C = ∅.
Φ
For any two nonempty sets A and B, descriptive union is defined by
A ∪ B = {x ∈ X : Φ(x) ∈ Φ(A) ∪ Φ(B)}.
Φ
We have A ∪ B = Φ∗ (A ∪ B).
Φ
The definition of the descriptive proximity relative to Φ can be generalized
as follows. Let us assume that Φ(x) ∈ ℜk , where ℜ is the set of reals and
r ⊆ P(ℜk ) × P(ℜk ), where P(ℜk ) is the powerset of ℜk . Then one can define a
binary relation δΦ,r by A δΦ,r E, if and only if, r(Φ(A), Φ(E)).
The binary relation δΦ,r is a descriptive Efremovic̆-proximity (EF-proximity),
provided the following axioms are satisfied for subsets A, B, C of X.
(EFΦ,r .1) A δΦ,r B implies A ̸= ∅, B ̸= ∅.
(EFΦ,r .2) A ∩ B ̸= ∅ ⇒ A δΦ,r B.
Φ
(EFΦ,r .3) A δΦ,r B ⇒ B δΦ,r A
(EFΦ,r .4) A δΦ,r (B ∪ C) ⇔ A δΦ,r B or A δΦ,r C.
(EFΦ,r .5) A δ Φ,r B ⇒ A δ Φ,r C and B δ Φ,r C c for some C ⊆ X.
The pair (X, δΦ,r ) is called a descriptive EF-proximity space. Points are
descriptively distinct if they have different descriptions. For distinct points x, y ∈
X, a descriptive EF-proximity is separated, if and only if, it satisfies
(EFΦ,r .6) {x} δΦ,r {y} ⇔ Φ(x) = Φ(y) (EF-Proximity Separation Axiom).
Example 5. EF-Proximity Based on Colour.
Let the subsets A, B, C ⊆ X be represented by the coloured circular regions
in Fig. 1. Let Φ contain probe functions representing various colours of the
picture elements in Fig. 1. The assumption made here is that a picture element
is the smallest visible part of the picture (a pixel) and each picture elements
has discernible features such as green, orange, yellow, white. The labels X\C
(complement of C, also written C c ), A, B, C identify the parts of the picture.
Axiom (EF.5) is satisfied in this depiction of the subsets of X, since the colour
of A is far from the colour B and B is descriptively far from the C c . It is easy to
verify that the remaining EF axioms are satisfied. Hence, (X, δΦ ) is an example
of a descriptive EF-proximity space.
By considering different functions Φ, one can obtain different proximities and
approximations of sets. Let us consider some illustrative examples.
Example 6. Descriptive Classes. In Fig. 4(a), the partition of the set X has
Fig. 4. Spatially remote and descriptively near sets
three equivalence classes, namely, the class containing white picture elements
represented along the border of the box , the class containing black picture
elements in the pair of boxes (sets labelled B1 , B2 ) and the class containing
grey picture elements in the pair of grey boxes . Let x ∈ B1 . Notice, for example,
that the pair of sets B1 , B2 are spatially remote sets but descriptively near sets
and they belong to the equivalence class [x]∼, i.e.,
Φ
B1 δ B2 (spatially remote sets),
B1 δΦ B2 (descriptively near sets),
[x]∼ = B1 ∪ B2 (class = descriptive union).
Φ Φ
Again, in Fig. 4(b), the partition of the set Y has three equivalence classes,
namely, the class containing white picture elements represented along the border
of the box , the class containing green picture elements in the pair of boxes
(sets labelled G1 , G2 ) and the class containing orange picture elements in the
pair of boxes . Let y ∈ G1 . Again, for example, the pair of sets G1 , G2 are
spatially remote sets but descriptively near sets and belong to the equivalence
class [y]∼ , i.e.,
Φ
G1 δ G2 (spatially remote sets),
G1 δΦ G2 (descriptively near sets),
[y]∼ = G1 ∪ G2 (class = descriptive union).
Φ Φ
Example 7. Descriptive Approximation Spaces.
Let X be a nonempty set of picture elements in Fig. 5(a), Φ a set of functions
used to extract colours from members of X, g ∈ G1 , b ∈ B1 , w a member of a
set W of white picture elements, and EX ⊆ X, EY ⊆ Y (represented by dotted
Fig. 5. Sample descriptive approximation spaces
circles in Fig. 5(a) and Fig. 5(b), respectively). The descriptive approximation
space (Φ(X), ∼Φ ) is represented in Fig. 5(a), where
[g]Φ = G1 ∪ G2 ,
Φ
[b]Φ = B1 ∪ B2 ,
Φ
Φ∗ EX = [g]Φ ∪ {[w]Φ : w ∈ W & [w]Φ ⊆ EX },
Φ∗ EX = [g]∼ ∪ [b]Φ ∪ {[w]Φ : w ∈ W & [w]Φ ∩ EX ̸= ∅}.
Φ
Since, for example, the sets B1 , B2 are partly in and partly outside EX , the set
EX is a rough set. A similar line of reasoning leads to the conclusion that EY in
Fig. 5(b) is a rough set.
3 Nearness of Information Granules
Granular Computing (GC) becomes a hot topic in many application areas where
it is necessary to search for or discover complex structural objects called infor-
mation granules used, e.g., for inducing classifiers for vague concepts (see, e.g.,
[13]). This approach may be necessary for approximate reasoning about dynamic
complex objects, e.g., for expressing that complex dynamic granule representing
a flock of birds is now near another complex granule representing a forest or that
two complex dynamic granules representing cells, recorded by using electron mi-
croscopy, are now near. In particular, this seems to be necessary for realization
of the computing with word paradigm proposed by Lotfi A. Zadeh [14, 15].
Information granules [14–16] have often complex structures and can be rep-
resented as objects of information systems or decision tables on different levels
of hierarchical modeling (see,e.g., [17]). Then attributes are defined over such
complex granules used as objects in such information systems. One can again
use the presented above approach for descriptive nearness using attribute value
vectors over the granules. However, there is also an issue of nearness in a par-
ticular context. One of the possible approaches is to consider granules in the
framework of mereology or rough-mereology (see,e.g., [18–21]), which makes it
possible to consider nearness of granules that are parts of some more complex
granules.
Note that in real-life applications, it is difficult to obtain an analytical form
for a nearness relation. Approximation of such a relation, as one of the relations
in an ontology of granules, should be learned from incomplete data. This process
usually will require interaction with domain experts for acquiring relevant fea-
tures (attributes) for approximation of that relation. Discovery of these relevant
attributes can be achieved using the ontology approximation methodology devel-
oped in a number of papers and summarized in [17]. In inducing approximations
of nearness relations from data, one can use the approximate Boolean reasoning
approach (see,e.g., [22, 23]), assuming that relevant features for approximation
have already been discovered.
Another problem with nearness relations in real-life applications is that they
lead to vague concepts. The temporary approximations of such relations can be
obtained using the rough set approach in combination with other soft computing
methods and hierarchical modeling. Note that it is necessary to change adap-
tively these approximations due to interactions with the dynamically changing
environment and other information sources.
Hence, in real-life applications, the nearness can be considered as a process
of dynamically changing information granules [13]. In different process stages,
these information granules represent the current semantical meanings of complex
vague concept of nearness. This requires to use advanced methods of learning
supported, e.g., by domain knowledge expressing the context in which the near-
ness concept is considered, methods for new relevant feature extraction, e.g., do-
main ontology approximation and adaptation strategies. This approach is quite
different from the traditional approach based on axiomatic definition of nearness
introduced, e.g., in proximity spaces. Note that this remark is also true for many
other complex vague concepts, e.g., related to risk analysis.
4 Conclusions and Future Research
In the paper, we discussed two approaches to nearness. The first approach has
the roots in the approach developed for proximity spaces. The second approach
arises from real-life projects, where nearness becomes a complex vague concept
dependent on the context. The latter approach requires advanced methods for
approximation of complex vague concepts, e.g., based on approximation of do-
main ontology.
We would like to address two research issues linking our considerations on
nearness of granules with our previous considerations on proximity relations.
The first one is related to methods of inducing approximations of nearness rela-
tions for information granules satisfying crisp constraints assumed for nearness
relations. Assuming that such approximations can be obtained, one can consider
the second issue based on characterization of benefits on approximate reasoning
over granular computations with approximations of nearness relations satisfying
such constraints.
Acknowledgements
The research by J.F. Peters has been supported by Natural Sciences & Engi-
neering Research Council of Canada grant 185986, Network of Excellence grant
SRI-BIO-05 and Manitoba NCE Fund grant. The research by A. Skowron has
been partially supported by grant the National Center for Research and Develop-
ment (NCBiR) under grant SP/I/1/77065 in the strategic scientific and experi-
mental development program: Interdisciplinary System for Interactive Scientific-
Technical Information, by the Foundation for Polish Science under the individual
research grant by the program Homing Plus, edition 3/2011, and by the Polish
National Science Centre under the grant 2011/01/D/ST6/06981. The research
by J. Stepaniuk is supported by the Rector grant S/WI/5/08 of Bialystok Uni-
versity of Technology.
References
1. Naimpally, S.: Proximity Spaces. Cambridge University Press, Cambridge,UK
(1970) x+128 pp., ISBN 978-0-521-09183-1.
2. Pawlak, Z.: Rough sets. International J. Comp. Inform. Science 11 (1982) 341–356
3. Pawlak, Z., Skowron, A.: Rudiments of rough sets. Information Sciences 177
(2007) 3–27
4. Pawlak, Z., Skowron, A.: Rough sets: Some extensions. Information Sciences 177
(2007) 28–40
5. Pawlak, Z., Skowron, A.: Rough sets and boolean reasoning. Information Sciences
177 (2007) 41–73
6. Efremovic̆, V.: The geometry of proximity I. Mat. Sb. 31 (1951) 189–200 (in
Russian) MR 14, 1106.
7. Peters, J.: Local near sets. Math. in Comp. Sci. (2012) , to appear.
8. Peters, J., Naimpally, S.: Applications of near sets. Amer. Math. Soc. Notices
59(4) (2012) 536–542
9. Naimpally, S., Peters, J.: Topology with Applications. Topological Spaces via Near
and Far. World Scientific, Singapore (2012) , in press.
10. Peters, J., Skowron, A., Stepaniuk, J.: Nearness of objects: Extension of approxi-
mation space model. Fundamenta Informaticae 79(3-4) (2007) 497–512
11. Skowron, A., Stepaniuk, J.: Approximation of functions: Toward rough granule
calculus. In Yao, J., Ramanna, S., Wang, G., Suraj, Z., eds.: Rough Sets and
Knowledge Technology, LNAI 6954. Springer (2012) 712–721
12. Mitchell, M.: Analogy-Making as Perception. MIT Press, Cambridge, MA, U.S.A.
(1993)
13. Pedrycz, W., Skowron, A., Kreinovich, V., eds.: Handbook of Granular Computing.
Wiley & Sons, New York, USA (2008)
14. Zadeh, L.A.: From computing with numbers to computing with words – from
manipulation of measurements to manipulation of perceptions. IEEE Transactions
on Circuits and Systems 45 (1999) 105–119
15. Zadeh, L.A.: A new direction in AI-toward a computational theory of perceptions.
AI Magazine 22(1) (2001) 73–84
16. Zadeh, L.A.: Fuzzy sets and information granularity. In Gupta, M., Ragade, R.,
Yager, R., eds.: Advances in Fuzzy Set Theory and Applications. North-Holland,
Amsterdam (1979) 3–18
17. Bazan, J.: Hierarchical classifiers for complex spatio-temporal concepts. In Peters,
J.F., Skowron, A., Rybiński, H., eds.: Transactions on Rough Sets IX: Journal
Subline. Volume 5390 of Lecture Notes in Computer Science. Springer, Heidelberg
(2008) 474–750
18. Leśniewski, S.: Grundzüge eines neuen systems der grundlagen der mathematik.
Fundamenta Mathematicae 14 (1929) 1–81
19. Polkowski, L., Skowron, A.: Rough mereology: A new paradigm for approximate
reasoning. International Journal of Approximate Reasoning 15(4) (1996) 333–365
20. Polkowski, L., Skowron, A.: Towards adaptive calculus of granules. In Zadeh, L.A.,
Kacprzyk, J., eds.: Computing with Words in Information/Intelligent Systems,
Heidelberg, Physica-Verlag (1999) 201–227
21. Polkowski, L.: Approximate Reasoning by Parts. An Introduction to Rough Mere-
ology. Volume 20 of Intelligent Systems Reference Library. Springer, Heidelberg
(2011)
22. Skowron, A.: Rough sets in KDD - plenary talk. In Shi, Z., Faltings, B., Musen,
M., eds.: 16-th World Computer Congress (IFIP’2000): Proceedings of Conference
on Intelligent Information Processing (IIP’2000). Publishing House of Electronic
Industry, Beijing (2000) 1–14
23. Nguyen, H.S.: Approximate boolean reasoning: Foundations and applications in
data mining. In Peters, J.F., Skowron, A., eds.: Transactions on Rough Sets V:
Journal Subline. Volume 4100 of Lecture Notes in Computer Science. Springer,
Heidelberg (2006) 344–523