Abstract

This paper is devoted to a nearness relation in an Efremovicproximity 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 EFrelation. This leads to a study of the nearness of objects either spatially or descriptively in the approximation of a set. The 2007 nearness approximation space model is re ned and extended in this paper, leading two new forms of nearness approximation spaces. There is a natural transition 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 bene ts of this approach for approximate reasoning over granular computations.

Keywords

• Dedicated to Zdzislaw Pawlak
• Approximation space
• EF-proximity space
• information granules
• nearness relation
• rough sets

-

rough sets [ 2–5 ]. Two forms of nearness relations are considered, namely, a spatial nearness relation defined in a traditional Efremovi˘c (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 approximation 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 approximation 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.

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) Efremovi˘c 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 separated, 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 Cc). 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 [x] ∩E̸=∅ ∪ [x] , lower approximation of E,

[x] , upper approximation of E.

Let us observe that the lower approximation and the upper approximation of E can be equivalently defined by 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) ̸= ∅. A δ

E ⇔ Φ(A) ∩ Φ(E) = ∅.

The descriptive remoteness of A and E (denoted by A δ E) is defined by

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.

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.

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 Cc 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 Cc), 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 Cc. 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

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 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 information 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 microscopy, 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 represented 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 particular 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 features (attributes) for approximation of that relation. Discovery of these relevant attributes can be achieved using the ontology approximation methodology developed 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 adaptively 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 nearness concept is considered, methods for new relevant feature extraction, e.g., domain 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 domain 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 Development (NCBiR) under grant SP/I/1/77065 in the strategic scientific and experimental 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 University of Technology.

17. Bazan, J.: Hierarchical classi ers for complex spatio-temporal concepts. In Peters, J.F., Skowron, A., Rybinski, H., eds.: Transactions on Rough Sets IX: Journal Subline. Volume 5390 of Lecture Notes in Computer Science. Springer, Heidelberg (2008) 474{750 18. Lesniewski, S.: Grundzuge 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 Mereology. 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

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 Scienti c, Singapore ( 2012 ) , in press.

10. Peters , J. , Skowron , A. , Stepaniuk , J.: Nearness of objects: Extension of approximation 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