Granulation of Knowledge: Similarity Based Approach in Information and Decision Systems

Glossary

Definition of the Subject

Introduction

Similarity

Information and Decision Systems

Granulation of Knowledge: General Ideas and Technique of Rough Inclusions

Calculus on Granules

Some Principal Fields of Applications

Complexity Issues

Future Directions

Bibliography

Knowledge:

The notion of knowledge can be described by positing the structure of the perceivable world as a system of states of things. These states are related among themselves by relations which in turn form a network of interdependent combinations. States and relations, as well as dependencies among them, are reflected in knowledge: things are reflected in objects or notions, relations in notions or concepts, states of things in sentences. Sentences form knowledge [6]; for instance, in Artificial Intelligence, a judiciously chosen set of sentences forms a knowledge base for a logical agent (see [52]).

Knowledge representation :

A chosen symbolic system (language) by means of which notions are encoded and reasoning is formalized.

Description logic :

A language of concepts commonly used for knowledge representation in Artificial Intelligence logical systems (see [2]). The variant which is interesting to us is constructed in the attribute‐value context in which objects are described in terms of chosen attributes (features) and their values.Primitive formulas of description logic are descriptors of the form \( { (a=v) } \) where a is an attribute and v is one of its values. Descriptors are interpreted in the universe U of objects: the meaning \( { [(a=v)] } \) of the descriptor \( { (a=v) } \) is defined as the set \( { \{u\in U \colon a(u)=v\} } \). Descriptors are extended to formulas of description logic with the help of connectives of sentential calculus: when \( { \alpha, \beta } \) are formulas then \( { \alpha\vee\beta } \), \( { \alpha\wedge\beta } \), \( { \neg\alpha } \), \( { \alpha\Rightarrow\beta } \) are formulas as well. The meaning of formulas is defined by recursion: \( { [\alpha\vee\beta]=[\alpha]\cup [\beta] } \), \( { [\alpha\wedge\beta]=[\alpha]\cap [\beta] } \), \( { [\neg\alpha]=U\setminus [\alpha] } \). The meaning of implication \( { \alpha\Rightarrow\beta } \) depends on the chosen interpretation of implication; when it is interpreted as in sentential calculus, that is, as \( { \neg\alpha\vee\beta } \), the meaning is already defined by the given formulas for \( { \vee, \neg } \).

Rough sets: knowledge as classification:

Rough set theory proposed by Pawlak [30,32], understands knowledge as classification: a set of equivalence relations, each of which is understood as a certain classification of objects into its equivalence classes. Together, these relations constitute the knowledge base \( { \mathcal{R} } \). Objects that belong in one class \( { [u]_R } \) of a relation R in the knowledge base are R‑indiscernible. Objects that belong in the intersection \( { \bigcap_{R\in {\mathcal{R}}}[u]_R } \) are \( { {\mathcal{R}} } \) ‑indiscernible: they cannot be discerned by means of the knowledge available in \( { \mathcal{R} } \).

Indiscernibility relations are formally defined for sets of relations: given \( { \mathcal{T} } \)⊆\( { \mathcal{R} } \), the \( { \mathcal{T} } \)‑indiscernibility relation \( { \operatorname{ind}({\mathcal{T}}) } \) is defined as the intersection \( { \bigcap_{R\in {\mathcal{T}}}R } \). Concepts are divided into two classes: \( { {\mathcal{T}} } \) ‑exact concepts are sets of objects which can be expressed as unions of \( { \mathcal{T} } \)‑indiscernibility classes; other concepts are \( { {\mathcal{T}} } \) ‑rough. For each concept X, there exist the greatest exact concept \( { \underline{\mathcal{T}} } \) contained in X (the \( { {\mathcal{T}} } \) ‑lower approximation to X) and the smallest exact concept \( { \underline{\mathcal{T}} } \) which contains X (the \( { {\mathcal{T}} } \) ‑upper approximation to X). Rough concepts are perceived as uncertain sets sandwiched between a lower approximation and an upper approximation.

Information system:

A system commonly used for representing information about a given world fragment. An information system can be represented as a collection of pairs of the form \( { (U,A) } \) where U is a set of objects – representing things – and A is a set of attributes; each attribute a is modeled as a mapping \( a\colon U\rightarrow V_a \) from the set of objects into the value set V _a . For an attribute a, the equivalence relation R _a is the set \( \{(u,v)\in U\times U\colon a(u)=a(v)\} \) and the collection \( \mathcal{R}=\{R_a\colon a\in A\} \) is the knowledge base. For each set \( { B\subseteq A } \) of attributes, the B ‑indiscernibility relation \( { \operatorname{ind}(B) } \) is the set \( \{(u,v)\in U\times U\colon a(u)=a(v)\text{ for each }a\in B\} \). Each object \( { u\in U } \) can be described in two ways: first, by means of its indiscernibility class \( [u]_A=\{v\in U\colon (u,v) \in \operatorname{ind}(A)\} \); next, by means of its descriptor logic formula \( \phi^A(u)\colon \bigwedge_{a\in A}(a=a(u)) \); as \( { [\phi^A(u)]=[u]_A } \), both descriptions are equivalent and u is described up to its equivalence class.

Decision system:

A particular form of an information system, a triple \( { (U,A,d) } \) in which d is the decision , the attribute not in A, that expresses the evaluation of objects by an external oracle, an expert. Attributes in A are called conditional which expresses the fact that they are set by us as conditions describing objects in our language. The principal problem related to a decision system is to find a description of dependence between conditional knowledge given by \( { (U,A) } \) and the expert knowledge \( { (U,\{d\}) } \).

Decision rule:

A  decision rule is a formula in descriptor language that expresses a particular relation among conditional attributes in the attribute set A and the decision d, of the form: \( { \bigwedge_{a\in A}(a=v_a)\Rightarrow (d=v) } \) with the semantics defined in (Glossary: Description logic).The formula is true, or certain in case \( { [\bigwedge_{a\in A}(a=v_a)]=\bigcap_{a\in A}[(a=v_a)] \subseteq [(d=v)] } \).Otherwise, the formula is partially true, or possible. An object o which satisfies the rule \( { a(o)=v_a } \) for \( { a\in A } \) can be assigned to the class \( { [(d=v)] } \); often a partial match based on a chosen similarity measure must be performed.

Similarity :

Similarity relations are weaker forms of indiscernibility: indiscernible objects are similar but not necessarily vice versa an example attributable to Henri Poincaré [35] explains this best: assume that points \( { x,y } \) in the real line are similar whenever their distance is less than a fixed threshold δ: \( { |x-y|<\delta } \). Then certainly each x is similar to x, and if x is similar to y then y is similar to x, but from x similar to y and y similar to z it need not follow that x is similar to z: \( { |x-z| } \) can be close to \( { 2\delta } \). Relations of this kind are reflexive and symmetric: they were called tolerance relations in Zeeman [67]. Tolerance relations in the framework of rough set theory information systems were considered in Nieminen [26] and tolerance reducts and related notions in information systems were discussed in Polkowski, Skowron and Zytkow [50]. Some authors relax tolerance relations to similarity relations that need not be symmetric: for instance, rough inclusions need not be symmetric [37].

In many applications, metrics are taken as similarity measures: a metric on a set U is a function \( d\colon U\times U\rightarrow R^+ \) into non‐negative reals such that 1. \( { d(x,y)=0 } \) if and only if \( { x=y } \). 2. \( { d(x,y)=d(y,x) } \). 3. \( d(x,y)\leq d(x,z) + d(z,y) \) for each \( { x,y,z } \) in X (the triangle inequality); similarity induced by a metric d is usually of the form \( { d(x,y)<\delta } \) for a certain \( { \delta > 0 } \), Poincaré‐style.

Rough inclusion:

A ternary relation μ on a set \( U\times U\times [0,1] \) which satisfies conditions: 1. \( \mu(x, x,1) \). 2. \( \mu(x,y,1) \) is a binary partial order relation on the set X. 3. \( \mu(x, y,1) \) implies that for each object z in U: if \( \mu(z, x,r) \) then \( \mu(z, y,r) \). 4. \( \mu(x, y,r) \) and \( { s<r } \) imply that \( \mu(x, y,s) \). The formula \( \mu(x, y,r) \) is read as “the object x is a part in object y to a degree at least r”. The partial containment idea encompasses the idea of an exact part, that is, mereological theory of concepts Leśniewski [15].Similarity induced by a rough inclusion can be introduced as an asymmetric relation: \( \mu(x, y,r) \), or a symmetric one: \( \mu(x,y,r) \wedge\mu(y,x,r) \).

Granulation of knowledge:

The concept of granulation was proposed by Zadeh [67]. In fuzzy calculus, granules are naturally induced as the inverse images of fuzzy membership functions and fuzzy computing is a fortiori computing with granules. A similar case happens with rough sets, as primitive objects in this paradigm are indiscernibility classes that are elementary granules, whereas their unions are granules of knowledge; reasoning in rough sets means, by definition, reasoning with granules. Each similarity relation induces granules understood as its classes; in comparison to indiscernibility relations, granules induced by similarity relations are more intricate due to lack of transitivity: relations among granules are more difficult to ascertain. In defining granules, attention is focused on the property that singles out objects belonging in the granule; usually, this property is a relation to an object chosen as the granule center: this means that distinct objects in the granule need not be in the relation. This feature distinguishes granules from clusters: aggregates in which any two objects have the defining property, for example, distance less than the chosen threshold.Also, relations between pairs of distinct granules are difficult to ascertain, contrary to the case of (for example) clusters, in which case the distance between distinct clusters is kept above a fixed threshold.

Classification of objects:

Classification entails assigning to each element in a set of objects (test sample) a class (a decision) to which the given element should belong; it is accomplished on the basis of knowledge induced from the given collection of examples (the training sample). To perform this task, objects are usually mapped onto vectors in a multi‐dimensional real vector space (feature space). Paradigms invented to perform classification are many, from heuristics based on cognitive networks such as neural networks, through probabilistic tools such as Bayesian networks to tools based on distance such as k-nn methods and prototype methods (see [7,12]).

Fusion of knowledge:

A combination of knowledge coming from few distinct sources. For example, in a mobile robot, fusion of knowledge by means of a Kalman filter (see [52]), consists in producing an output – a robot's predicted position at the current moment – on the basis of inputs: a robot's position estimated as the last moment preceding the current moment, the current controls, and sensor readings in the current position.

Reasoning:

Processes of reasoning include an effort by means of which sentences are created; various forms of reasoning depend on the chosen system of notions, symbolic representation of notions, forms of manipulating symbols (see [6]).

Mereology:

Mereology, see Leśniewski [15], is a theory of concepts based on the notion of a part instead – as with naive set theory – on the notion of an element. The relation of being a part is irreflexive and transitive. A secondary notion of an ingredient means either being a part or being the whole object and it sets a partial order on objects. By means of the notion of an ingredient the notion of a class operator is introduced in Leśniewski [15] which converts ontological notions, that is, collections of objects into an individual object; it is used by us in granule formation.

Authors and Affiliations

1. Polish‐Japanese Institute of Information Technology, Warsaw, Poland

   Lech Polkowski

Editors and Affiliations

1. RAMTECH LIMITED, 122 Escalle Lane, Larkspur, CA, 94939, USA

   Robert A. Meyers Ph. D. (Editor-in-Chief) (Editor-in-Chief)

Reprints and permissions

© 2012 Springer-Verlag

Policies and ethics