Near set theory and its generalization

1 Introduction

Rough set theory, proposed by Pawlak (1991, 1982), can be seen as a new mathematical approach to vagueness. The rough set philosophy is founded on the assumption that with every object of the universe of discourse we associate some information (data, knowledge) Abu-Donia et al. (2007). For example, if objects are patients suffering from a certain disease, symptoms of the disease form information about patients. Objects characterized by the same information are indiscernible (similar) in view of the available information about them. The indiscernibility relation generated in this way is the mathematical basis of rough set theory. This understanding of indiscernibility is related to the idea of Gottfried Wilhelm Leibniz that objects are indiscernible if and only if all available functionals take on identical values (Leibnizs Law of Indiscernibility: The Identity of Indiscernibles) (Ariew et al., 1989). However, in the rough set approach, indiscernibility is defined relative to a given set of functionals (attributes). Any set of all indiscernible (similar) objects is called an elementary set, and forms a basic granule (atom) of knowledge about the universe. Any union of some elementary sets is referred to as a crisp (precise) set. A set which is not crisp is called rough (imprecise, vague).

Consequently, each rough set has boundary region cases, i.e., objects which cannot with certainty be classified either as members of the set or of its complement. Obviously crisp sets have no boundary region elements at all. This means that boundary region cases cannot be properly classified by employing available knowledge.

Thus, the assumption that objects can be seen only through the information available about them leads to the view that knowledge has a granular structure. Due to the granularity of knowledge, some objects of interest cannot be discerned and appear as the same (or similar). As a consequence, vague concepts, in contrast to precise concepts, cannot be characterized in terms of information about their elements.

Ultimately, there is interest in selecting the probe functions (Peters, 2007) that lead to descriptions of objects that are minimally near each other. This is an essential idea in the near set approach (Peters, 2007; Peters et al., 2007) and differs markedly from the minimum description length (MDL) proposed in 1983 by Jorma Rissanen. MDL depends on the identification of possible data models and possible probability models. By contrast, NDP deals with a set X that is the domain of a description used to identify similar objects. The term similar is used here to denote the presence of objects that have descriptions that match each other to some degree.

The near set approach leads to partitions of ensembles of sample objects with measurable information content and an approach to feature selection. The proposed feature selection method considers combinations of n probe functions taken r at a time in searching for those combinations of probe functions that lead to partitions of a set of objects that has the highest information content.

In this work, we assume that any vague concept is replaced by a pair of precise concepts, called the lower and the upper approximations of the vague concept. The lower approximation consists of all objects which surely belong to the concept and the upper approximation contains all objects which possibly belong to the concept. The difference between the upper and the lower approximation constitutes the boundary region of the vague concept. These approximations are two basic operations in rough set theory. There is a chance to be useful in the analysis of sample data. The proposed approach does not depend on the joint probability of finding a feature value for an input vectors that belong to the same class. In addition, the proposed approach to measuring the information content of families of neighborhoods differs from the rough set. The near set approach does not depend on preferential ordering of value sets of functions representing object features. The contribution of this research is the introduction of a generalization of near set approach to feature selection.

2 Preliminaries

Rough set theory expresses vagueness, not by means of membership, but employing a boundary region of a set. If the boundary region of a set is empty, it means that the set is crisp, otherwise the set is rough (inexact). Nonempty boundary region of a set means that our knowledge about the set is not sufficient to define the set precisely.

Suppose we are given a set of objects U called the universe and an indiscernibility relation $E\subseteq U\times U$ , representing our lack of knowledge about elements of U. For the sake of simplicity we assume that E is an equivalence relation and X be a subset of U, we want to characterize the set X with respect to E. To this end we will need the basic concepts of rough set theory given below (Pawlak, 1982).

The equivalence class of E determined by element x is: $[x]{\hspace{0.17em}}_E=\{x^{\prime }\in X:E(x)=E(x^{\prime })\}$ . Hence E-lower, upper approximations and boundary region of X are: $$\begin{array}{cc}\hfill & \underline{E}(X)=\bigcup \{[x]{\hspace{0.17em}}_E:X\subseteq U\text{,}[x]{\hspace{0.17em}}_E\subseteq X\}\text{;}\hfill \\ \hfill & \overline{E}(X)=\bigcup \{[x]{\hspace{0.17em}}_E:X\subseteq U\text{,}[x]{\hspace{0.17em}}_E\cap X\ne \varphi \}\text{;}\hfill \\ \hfill & {\mathit{BND}}_E(X)=\overline{E}(X)-\underline{E}(X)\text{.}\hfill \end{array}$$ It is easily seen that approximations are in fact interior and closure operations in a topology generated by the indiscernibility relation (Abd El-Monsef et al., 2010).

The rough membership function is a degree that x belongs to X in view of information about expressed by E. It defined as (Pawlak and Skowron, 1994): $${\mu }_X^E(x):U\to [0\text{,}1]\text{,}{\mu }_X^E(x)=\frac{\left|X\cap [x]{\hspace{0.17em}}_E\right|}{\left|[x]{\hspace{0.17em}}_E\right|}\text{,}$$ where $|*|$ denotes the cardinality of $*$ .

A rough set can also be characterized numerically by the accuracy measure of an approximation (Pawlak, 1991) which is defined as: $${\alpha }_E(X)=\frac{\left|\underline{E}(X)\right|}{\left|\overline{E}(X)\right|}\text{.}$$

Obviously, $0⩽{\alpha }_E(X)⩽1$ . If ${\alpha }_E(X)=1$ , X is crisp with respect to E (X is precise with respect to E), and otherwise, if ${\alpha }_E(X)<1$ , X is rough with respect to E (X is vague with respect to E).

Underlying the study of near set theory is an interest in classifying sample objects by means of probe functions associated with object features. More recently, the term feature is defined as the form, fashion or shape (of an object).

Let F denotes a set of features for objects in a set X. For any feature $a\in F$ , we associate a function $f_a$ that maps X to some set $V_{f_a}$ (range of $f_a$ ).

The value of $f_a(x)$ is a measurement associated with feature a of an object $x\in X$ . The function $f_a$ is called a probe function (Pavel, 1993).

The following concepts introduced by Peters (2007) and Peters et al. (2006).

$\mathit{GAS}=(U\text{,}F\text{,}{N}_r\text{,}{\nu }_B)$ is a generalized approximation space, where U is a universe of objects, F is a set of functions representing object features, $N_r$ is a neighborhood family function defined as $$N_r(F)=\bigcup _{A\subseteq P_r(F)}[x]{\hspace{0.17em}}_A\text{,}\mathit{where}{P}_r(F)=\{A\subseteq F:\left|A\right|=r\text{,}1⩽r⩽\left|F\right|\}\text{.}$$ And ${\nu }_{B_r}$ is an overlap function defined by $${\nu }_{B_r}:P(U)\times P(U)\to [0\text{,}1]\text{,}{\nu }_{B_r}(Y\text{,}{N}_r(B){\hspace{0.17em}}_{*}X)=\frac{\left|Y\cap N_r(B){\hspace{0.17em}}_{*}X\right|}{\left|N_r(B){\hspace{0.17em}}_{*}X\right|}\text{,}$$ where $N_r(B){\hspace{0.17em}}_{*}X\ne \varphi \text{,}Y$ is a member of the family of neighborhoods $N_r(B)$ and ${\nu }_{B_r}(Y\text{,}{N}_r(B){\hspace{0.17em}}_{*}X)$ is equal to 1, if $N_r(B){\hspace{0.17em}}_{*}X=\varphi$ .

The overlap function ${\nu }_{B_r}$ maps a pair of sets to a number in $[0\text{,}1]$ representing the degree of overlap between the sets of objects with features $B_r$ .

$N_r(B)$ -lower, upper approximations and boundary region of a set X with respect to r features from the probe functions B are defined as: $$\begin{array}{cc}\hfill & N_r(B){\hspace{0.17em}}_{*}X=\bigcup _{x:[x]{\hspace{0.17em}}_{B_r}\subseteq X}[x]{\hspace{0.17em}}_{B_r}\text{;}\hfill \\ \hfill & N_r(B){\hspace{0.17em}}^{*}X=\bigcup _{x:[x]{\hspace{0.17em}}_{B_r}\cap X\ne \varphi }[x]{\hspace{0.17em}}_{B_r}\text{;}\hfill \\ \hfill & {\mathit{BND}}_{N_r(B)}X=N_r(B){\hspace{0.17em}}^{*}X-N_r(B){\hspace{0.17em}}_{*}X\text{.}\hfill \end{array}$$ Peters introduces the following concepts:

Objects x and $x^{\prime }$ are minimally near each other if $\exists f\in B$ such that $f(x^{\prime })=f(x)$ . A set X is near to $X^{\prime }$ if $\exists x\in X$ , $x^{\prime }\in X^{\prime }$ such that x and $x^{\prime }$ are near objects. A set X is termed a near set relative to a chosen family of neighborhoods $N_r(B)$ if $|{\mathit{BND}}_{N_r(B)}X|⩾0$ .

3 Generalized near set theory

In the following, we use a general relation to deduce a new approach to near set theory, consequently we obtain a new general near lower (upper) approximation for any near set. Also we introduce a modification of some concepts.

If the length of the neighborhood of the feature s (resp a and r) equals to 0.2 (resp 0.9 and 0.5), then $$\begin{array}{cc}\hfill & N_1(B)=\{\xi (s_{0.2})\text{,}\xi (a_{0.9})\text{,}\xi (r_{0.5})\}\text{,}\text{where}\hfill \\ \hfill & \xi (s_{0.2})=\{\{x_1\text{,}{x}_2\}\text{,}\{x_1\text{,}{x}_2\text{,}{x}_3\}\text{,}\{x_2\text{,}{x}_3\text{,}{x}_4\}\text{,}\{x_3\text{,}{x}_4\}\}\text{;}\hfill \\ \hfill & \xi (a_{0.9})=\{\{x_1\text{,}{x}_4\}\text{,}\{x_2\text{,}{x}_3\}\text{,}\{x_2\text{,}{x}_3\text{,}{x}_4\}\text{,}\{x_1\text{,}{x}_3\text{,}{x}_4\}\}\text{;}\hfill \\ \hfill & \xi (r_{0.5})=\{\{x_1\text{,}{x}_3\text{,}{x}_4\}\text{,}\{x_2\}\}.\text{Hence,}\hfill \\ \hfill & {\tau }_{s_{0.2}}=\{\{x_2\}\text{,}\{x_3\}\text{,}\{x_1\text{,}{x}_2\}\text{,}\{x_2\text{,}{x}_3\}\text{,}\{x_3\text{,}{x}_4\}\text{,}\hfill \\ \hfill & \{x_1\text{,}{x}_2\text{,}{x}_3\}\text{,}\{x_2\text{,}{x}_3\text{,}{x}_4\}\text{,}X\text{,}\varphi \}\text{;}\hfill \\ \hfill & {\tau }_{a_{0.9}}=\{\{x_3\}\text{,}\{x_4\}\text{,}\{x_3\text{,}{x}_4\}\text{,}\{x_2\text{,}{x}_3\}\text{,}\{x_1\text{,}{x}_4\}\text{,}\hfill \\ \hfill & \{x_2\text{,}{x}_3\text{,}{x}_4\}\text{,}\{x_1\text{,}{x}_3\text{,}{x}_4\}\text{,}X\text{,}\varphi \}\text{;}\hfill \\ \hfill & {\tau }_{r_{0.5}}=\{\{x_2\}\text{,}\{x_1\text{,}{x}_3\text{,}{x}_4\}\text{,}X\text{,}\varphi \}.\text{Also,}\text{we}\text{get}:\hfill \\ \hfill & N_2(B)=\{\xi (s_{0.2}\text{,}{a}_{0.9})\text{,}\xi (s_{0.2}\text{,}{r}_{0.5})\text{,}\xi (a_{0.9}\text{,}{r}_{0.5})\}\text{,}\text{where}\hfill \\ \hfill & \xi (s_{0.2}\text{,}{a}_{0.9})=\{\{x_1\}\text{,}\{x_2\text{,}{x}_3\}\text{,}\{x_2\text{,}{x}_3\text{,}{x}_4\}\text{,}\{x_3\text{,}{x}_4\}\}\text{;}\hfill \\ \hfill & \xi (s_{0.2}\text{,}{r}_{0.5})=\{\{x_1\}\text{,}\{x_2\}\text{,}\{x_3\text{,}{x}_4\}\}\text{;}\hfill \\ \hfill & \xi (a_{0.9}\text{,}{r}_{0.5})=\{\{x_1\text{,}{x}_4\}\text{,}\{x_2\}\text{,}\{x_3\text{,}{x}_4\}\text{,}\{x_1\text{,}{x}_3\text{,}{x}_4\}\}.\text{Hence,}\hfill \\ \hfill & {\tau }_{s_{0.2}{a}_{0.9}}=\{\{x_1\}\text{,}\{x_3\}\text{,}\{x_2\text{,}{x}_3\}\text{,}\{x_3\text{,}{x}_4\}\text{,}\{x_1\text{,}{x}_3\}\text{,}\hfill \\ \hfill & \{x_2\text{,}{x}_3\text{,}{x}_4\}\text{,}\{x_1\text{,}{x}_2\text{,}{x}_3\}\text{,}\{x_1\text{,}{x}_3\text{,}{x}_4\}\text{,}X\text{,}\varphi \}\text{;}\hfill \\ \hfill & {\tau }_{s_{0.2}{r}_{0.5}}=\{\{x_1\}\text{,}\{x_2\}\text{,}\{x_3\text{,}{x}_4\}\text{,}\{x_1\text{,}{x}_2\}\text{,}\{x_1\text{,}{x}_3\text{,}{x}_4\}\text{,}\{x_2\text{,}{x}_3\text{,}{x}_4\}\text{,}X\text{,}\varphi \}\text{;}\hfill \\ \hfill & {\tau }_{a_{0.9}{r}_{0.5}}=\{\{x_2\}\text{,}\{x_4\}\text{,}\{x_1\text{,}{x}_4\}\text{,}\{x_3\text{,}{x}_4\}\text{,}\{x_2\text{,}{x}_4\}\text{,}\hfill \\ \hfill & \{x_1\text{,}{x}_3\text{,}{x}_4\}\text{,}\{x_1\text{,}{x}_2\text{,}{x}_4\}\text{,}\{x_2\text{,}{x}_3\text{,}{x}_4\}\text{,}X\text{,}\varphi \}\text{.}\hfill \end{array}$$ Also, we find that $${\tau }_{s_{0.2}{r}_{0.5}}\equiv {\tau }_{s_{0.2}{r}_{0.5}{a}_{0.9}}\text{.}$$ Consequently the reduct of these features is the features $\{s\text{,}r\}$ , so the feature $\{a\}$ can be canceled.

Now the following example deduces a comparison between the classical and new general near approaches by using the accuracy measures.

Note that, ${\alpha }_2^{\prime }={\alpha }_3^{\prime }$ for any subset of X, as ${\tau }_{s_{0.2}{r}_{0.5}}$ $\equiv$ ${\tau }_{a_{0.9}{s}_{0.2}{r}_{0.5}}$ .

4 Conclusion

This research is as a start point of many works, which aims to improve the lower and upper approximations of near sets introduced by J.F. Peters. This has led to a refinement of the generalized approximation space model to include families of neighborhoods. These works will be useful to a decision making in many fields of our life.