International Journal of Computational Intelligence Systems

Volume 11, Issue 1, 2018, Pages 1179 - 1191

Information structures in an incomplete information system: A granular computing viewpoint

Authors
*Corresponding author: Guangji Yu
Corresponding Author
Received 10 February 2018, Accepted 18 May 2018, Available Online 4 June 2018.
DOI
10.2991/ijcis.11.1.89How to use a DOI?
Keywords
Granular computing; Incomplete information system; Information granule; Information structure; Inclusion degree; Characterization
Abstract

Granular computing is a essential mathematical tool in artificial intelligence. An incomplete information system is an important model and its basic structures are information structures. This paper investigates information structures in an incomplete information system from granular computing viewpoint, i.e., information structures are viewed as granular structures. Information structures in an incomplete information system are first described through set vectors. Then, dependence between information structures is depicted, and information distance for calculating the difference between information structures is proposed. Next, properties of information structures in an incomplete information system are given. Finally, group and lattice characterizations of information structures in an incomplete information system are obtained. These results will be helpful for establishing a framework of granular computing in information systems.

Copyright
© 2018, the Authors. Published by Atlantis Press.
Open Access
This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

1. Introduction

Granular computing, proposed by Zadeh 17, is an important tool in artificial intelligence and information processing 17,18,19,20. The study of granular computing mainly concentrates in three aspects, including information granulation, organization and causation. Zadeh thought that the information granulation involves decomposition of whole into parts, the organization involves integration of parts into whole and the causation involves association of causes with effects.

The aim of granular computing is to seek for an approximation scheme, which allows us to view a phenomenon with different levels of granularity and then can effectively solve complex problems. Information granules and granular structures are two important notions in granular computing. Information granule is a collection of objects that are drawn together by some constraints, such as indistinguishability, similarity or functionality. The process of constructing information granules is said to be information granulation. It granulates a universe of discourse into a collection of disjoint or overlapping information granules. Granular structure is the collection of information granules, in which the internal structure of each information granule is visible as a substructure. To manage the construction, interprettation and representation of information granules is an important problem in granular computing. Until now, the research on granular computing mainly has four methods, i.e., rough set 8,9,10,11, fuzzy set 16, concept lattice 15 and quotient space 22.

Rough set is a mathematical tool for disposing uncertainty of knowledge and has been successfully applied to intelligent systems, machine learning, knowledge discovery, expert systems, decision analysis, inductive reasoning, pattern recognition, signal analysis.

An information system based on rough sets was introduced by Pawlak. Most applications of rough sets, such as rule extraction, reasoning with uncertainty, uncertainty modeling, classification and feature selection are related to information systems.

In granular computing in information systems, information granular and information structures are two important concepts. An equivalence relation is a special kind of similarities among objects from a data set. In an information system, an attribute subset determines an equivalence relation. The object set of this information system is divided into some disjoint classes by this equivalence relation, and these classes are said to be equivalence classes. If two objects of the universe belong to the same equivalence class, then we may say that they cannot be distinguished under this equivalence relation. Thus, every equivalence class can be seen as an information granule consisting of indistinguishable objects 3,4,13. All these equivalence classes or information granules constitutes a vector, this vector is called an information structures in the information system induced by this attribute subset. Obviously, information structures in this information system are granular structures in the meaning of granular computing. Liang et al. 7 introduced information structures in an information system. Chen et al. 1 studied information structures in a latticevalued information system and obtained their invariant characterizations under homomorphisms based on data compression.

So far, however, information structures in an incomplete information system have not been reported. A set vector is better than a set family in displaying the image of information structures. Based on granular computing, this paper investigates information structures in an incomplete information system by using set vectors.

The remaining part of this paper is organized as follows. In Section 2 , we recall some basic concepts about set vectors, binary relations and incomplete information systems. In Section 3, we describe information structures in an incomplete information system through set vectors. In Section 4, we divide dependence between information structures into two classes and introduce information distance between information structures. In Section 5, we give properties of information structures in an incomplete information system. In Sections 6, we obtain group and lattice characterizations of information structures in an incomplete information system. Sections 7 summarizes this paper.

2. Preliminaries

In this section, we recall some basic concepts about set vectors, binary relations and incomplete information systems.

Throughout this paper, U and V denotes two non-empty finite sets called the universes, E denotes the set of parameters, 2U denotes the family of all subsets of U, |X| denotes the cardinality of X ∈ 2U. All mappings are assumed to be surjective.

Put

U={u1,u2,,un},V={v1,v2,,vm},δ=U×U,Δ={(u,u):uU},p(X)=|X||U|(X2U).

2.1. Set vectors

Recall that (A1, A2,······, An) is called a set vector on U if for any in, Ai ∈ 2U. We write A = (A1, A2,······, An).

The family of all set vectors on U is denoted by 2U.

If A1 = A2 = ··· = An = B, then A is called constant. We write A=B˜ . Especially,

U˜=(U,U,,U),˜=(,,,).

Let A = (A1, A2, ······, An), B = (B1, B2,······, Bn) ∈ 2U. Define

A=Bi,Ai=Bi;ABi,AiBi;ABi,AiBi;ABi,AiBi;AB=(A1B1,A2B2,,AnBn);

Obviously,

A=BABandBA;ABAB.

2.2. Binary relations

Recall that R is a binary relation on U whenever RU × U. If (x, y) ∈ R, then we denote it by xRy.

Let R be a binary relation on U. Then R is called

  1. (1)

    reflexive, if xRx for any xU.

  2. (2)

    symmetric, if xRy implies yRx for any x, yU.

  3. (3)

    transitive, if xRy and yRz imply xRz for any x, y, zU.

Let R be a binary relation on U. Then R is called an equivalence relation on U, if R is reflexive, symmetric and transitive. R is called a similarity relation on U, if R is reflexive and transitive. R is called a tolerance relation on U, if R is reflexive and symmetric.

2.3. Incomplete information systems

Definition 2.1 (8)

Let U be a set of objects and A a set of attributes. Suppose that U and A are finite sets. Then the pair (U, A) is called an information system, if each attribute aA determines an information function a : UVa, where Va is the information function values set of the attribute a.

If PA, then (U, P) is called a subsystem of (U, A).

Definition 2.2 (8)

Let (U, A) be an information system. Then the pair (U, A) is called an incomplete information system, if there are the object xU and the attribute aA such that a(x) is missing or unknown.

If PA, then (U, P) is called a subsystem of (U, A).

If (U, A) is an incomplete information system and PA, then a binary relation sim(P) on U can be defined as

(u,v)sim(P)aA,a(u)=a(v)ora(u)=*ora(v)=*,

where * is a missing value.

Clearly, sim(P) is a tolerance relation on U and sim(P)=aPsim({a}) .

In particular, if sim(P) = δ, then sim(P) is called a universal relation; if sim(P) = ∆, then sim(P) is called an identity relation.

In this paper, we stipulate that sim(∅) = δ.

3. Concepts and operators of information structures in an incomplete information system

In this section, we give concepts and operators o of information structures and study their properties.

3.1. Information granules and information structures

Let (U, A) be an incomplete information system, for each uU, denote

Ssim(P)(u)={vU;(u,v)sim(P)}.

Then, Ssim(P)(u) is called the tolerance class of x under the tolerance relation sim(P). We briefly denote Ssim(P)(u) by SP(u). If two objects v1, v2 of U belong to the same tolerance class, then we may say that v1, v2 cannot be distinguished under the tolerance relation sim(P)3,4,13.

The universe U may be divided into some classes by the tolerance relation sim(P), which is said to be a quotient set. This quotient set is denoted by U/sim(P), i.e.,

U/sim(P)={SP(u):uU}.

We briefly denote U/sim(P) by U/P. An tolerance relation is a special kind of similarities among objects from a data set.

It is known that an unknown target concept can be characterized approximately by existing knowledge structures in a knowledge base, which is one of the strengths of rough set theory. Qian et al.13 have studied knowledge structures in a knowledge base by means of set families. Li et al.5,6 studied knowledge structures in a knowledge base and discussed relationships between knowledge bases. Their results have been shown to be very helpful for knowledge discovery from knowledge bases and significant for establishing a framework of granular computing in a knowledge base (see 14).

An information structure is the collection of information granules. How do we construct information structures? It should be noted that every tolerance class consists of indistinguishable objects under some tolerance relation. Then every tolerance class can be viewed as an information granule. In this way, information structures are constructed.

Considering that a set vector is better than a set family in displaying the image of structures, information structures in an incomplete information system may be described by means of set vectors.

Definition 3.1

Let (U, A) be an incomplete information system. Then for PA,

K(P)=(SP(u1),SP(u2),,SP(un))
is called the information structure of the subsystem (U, P).

If sim(P) is an identity relation, then K(P) = ({u1}, {u2},······, {un}).

Example 3.2

K(∅) = Ũ

Definition 3.3

Let (U, A) be an incomplete information system. Then

K(U,A)={K(P):P2A}
is called the information structure base of (U, A).

4. Relationships between information structures in an incomplete information system

4.1. The dependency between information structures

Definition 4.1

Let (U, A) be an incomplete information system. Given that K(P), K(Q) are the information structures of P, QA, respectively. Then K(P) and K(Q) are called to be the same, if for each i, SP(ui) = SQ(ui). We still write K(P) = K(Q).

The following definition depicts the dependency between information structures in an incomplete information system from three aspects.

Definition 4.2

Let (U, A) be an incomplete information system. Given that K(P), K(Q) are the information structures of P, QA, respectively.

  1. (1)

    K(Q) is called to depend on K(P), if K(P) ≼ K(Q); moreover, K(P) ≺ K(Q), if K(P) ≼ K(Q) and K(P) ≠ K(Q).

  2. (2)

    K(Q) is called to depend partially on K(P), if( K(P) ⊑ K(Q); moreover, K(P) ⊏ K(Q), if K(P) ⊑ K(Q) and K(P) ≠ K(Q).

  3. (3)

    K(Q) is called to be independent of K(P), if K(P) ⋈ K(Q).

Obviously,

K(P)=K(Q)K(P)K(Q)andK(Q)K(P);K(P)K(Q)K(P)K(Q).

Example 4.3

Table 1 depicts an incomplete information system about several cars where U = {u1, u2, u3, u4, u5, u6} is the set of cars and A = {Price, Mileage, Size, Max-speed} = {a1, a2, a3, a4} is the set of attributes.

Price Mileage Size Max-speed
u1 high low full low
u2 low * full low
u3 * * compact low
u4 high * full high
u5 * * full high
u6 low high full *
Table 1

An incomplete information system about cars

Pick

P1 = {a1}, P2 = {a2}, P3 = {a3}, P4 = {a4}, P5 = {a1, a2}, P6 = {a1, a3}, P7 = {a1, a4 }, P8 = {a2, a3}, P9 = {a2, a4}, P10 = {a3, a4}, P11 = {a1, a2, a3}, P12 = {a1, a2, a4}, P13 = {a1, a3, a4}, P14 = {a2, a3, a4}.

It should be noted that

  • sim{a1} = Δ∪ {(u1, u4), (u4, u1), (u2, u6), (u6, u2)},

  • sim{a2} = Δ,

  • sim{a3} = Δ∪{(u1, u2), (u2, u1), (u1, u4), (u4, u1), (u1, u5), (u5, u1), (u1, u6), (u6, u1), (u2, u4), (u4, u2), (u2, u5), (u5, u2), (u2, u6), (u6, u2), (u4, u5), (u5, u4), (u4, u6), (u6, u4), (u5, u6), (u6, u5)},

  • sim{a4} = Δ∪{(u1, u2), (u2, u1), (u1, u3), (u3, u1), (u2, u3), (u3, u2), (u4, u5), (u5, u4)}. Then

  • sim(∅) = δ,

  • sim(P1) = sim(P6) = sim{a1},

  • sim(P2) = sim(P5) = sim(P7) = sim(P8) = sim(P9) = sim(P11) = sim(P12) = sim(P13) = sim(P14) = sim(A) = sim{a2},

  • sim(P3) = sim{a3},

  • sim(P4) = sim{a4},

  • sim(P10) = Δ∪{(u1, u2), (u2, u1), (u4, u5), (u5, u4)}.

Obviously,

  • K(∅) = (U, U, U, U, U, U) = Ũ.

  • K(P1) = K(P6) = ({u1, u4}, {u2, u6}, {u3}, {u4, u1}, {u5}, {u6, u2}),

  • K(P2) = K(P5) = K(P7) = K(P8) = K(P9) = K(P11) = K(P12) = K(P13) = K(P14) = K(A) = ({u1}, {u2}, {u3}, {u4}, {u5}, {u6}),

  • K(P3) = ({u1, u2, u4, u5, u6}, {u1, u2, u4, u5, u6}, {u3}, {u1, u2, u4, u5, u6}, {u1, u2, u4, u5, u6}, {u1, u2, u4, u5, u6}),

  • K(P4) = ({u1, u2, u3}, {u1, u2, u3}, {u1, u2, u3}, {u4, u5}, {u4, u5}, {u6}),

  • K(P10) = ({u1, u2}, {u1, u2}, {u3}, {u4, u5}, {u4, u5}, {u6}).

  • Then

    1. (1)

      K(U, A) = {K(∅), K(P1), K(P3), K(P4), K(P10), K(A)}.

    2. (2)

      K(A) ≺ K(P1) ≺ K(P3) ≺ K(∅), K(A) ≺ K(P10) ≺ K(P4) ≺ K(∅); K(P10) ≺ K(P3); K(P3) ⊏ K(P1) ⊏ K(A), K(P3) ⊏ K(A); K(P4) ⊏ K(P10) ⊏ K(A), K(P4) ⊏ K(A); K(P1) ⊏ K(P10), K(P10) ⊏ K(P1); K(P3) ⊏ K(P4), K(P4) ⊏ K(P3); K(P1) ⊏ K(P4), K(P4) ⊏ K(P1).

4.2. Information distance between information structures

For A, BU, denote

AB=ABAB.

Then AB is called the symmetric difference A and B.

Obviously, |AB| = |AB| − |AB|.

In rough set theory, information entropy and information granulation are two main approaches to measuring the uncertainty of information structures in an information system. If the information granulation (or information entropy) of an information structure is equal to that of the other information structure in the same information system, we say that these two information structures have the same uncertainty. However, it does not mean that these two information structures are equivalent each other. Thus, information entropy and information granulation cannot characterize the difference between any two information structures in an information system.

To differentiate two information structures in the same incomplete information system, the concept of information distance is defined as follows.

Definition 4.4

Let (U, A) be an incomplete information system. Given that K(P), K(Q) are the information structures of P, QA, respectively. Information distance between K(P) and K(Q) is defined as

ρ(K(P),K(Q))=1n2i=1n|SP(ui)SQ(ui)|.

Lemma 4.5

Let A, BU. Then

A=B|AB|=0.

Proof.

“⇒”. This is obvious.

“⇐”. Suppose |AB| = 0. Then |ABAB| = 0.

It follows that ABAB = ∅. So ABAB.

Since ABAB, we have AB= AB.

Thus A = B.

Lemma 4.6

Let A, B, CU. Then

|AB|+|BC||AC|.

Proof.

Denote

  • A1 = A −(AB + ACABC),

  • A2 = ABABC,

  • A3 = B − (AB + BCABC),

  • A4 = ACABC,

  • A5 = ABC,

  • A6 = BCABC,

  • A7 = C − (AC + BCABC).

Then

  • |AB| = |A1| + |A4| + |A3| + |A6|,

  • |BC| = |A2| + |A3| + |A4| + |A7|,

  • |AC| = |A1| + |A2| + |A6| + |A7|.

So |AB| + |BC| − |AC|= 2(|A3| + |A4 |) > 0.

Thus |AB| + |BC| ⩾ |AC|.

Lemma 4.7

Let A, B, C ∈ 2U. If ABC or CBA, then

|AB|+|BC|=|AC|.

Proof.

Suppose ABC. Then

  • |AB| = |AB| − |AB| = |B| − |A|,

  • |BC| = |BC| − |BC| = |C| − |B|,

  • |AC| = |AC| − |AC| = |C| − |A|.

Thus

|AB|+|BC|=|AC|.
Suppose CBA. Similarly, we can prove that
|AB|+|BC|=|AC|.

Theorem 4.8

Let (U, A) be an incomplete information system. Then (K(U, A), ρ) is a distance space.

Proof.

Suppose P, Q, LA.

Obviously,

  • ρ(K(P), K(Q)) 0,

  • ρ(K(P), K(Q)) = ρ(K(Q), K(P)).

By Lemma 4.5
  • ρ(K(P), K(Q)) = 0 ⇔ ∀ i, |SP(ui) ⊕ SQ(ui) |= 0 ⇔ ∀ i, SP(ui) = SQ(ui) ⇔ K(P) = K(Q).

By Lemma 4.6,
|SP(ui)SQ(ui)|+|SQ(ui)SL(ui)||SP(ui)SL(ui)|.

Then ρ(K(P), K(Q)) + ρ(K(Q), K(L))

=1n2i=1n|SP(ui)SQ(ui)|+1n2i=1n|SQ(ui)SL(ui)|=1n2i=1n(|SP(ui)SQ(ui)|+|SQ(ui)SL(ui)|)1n2i=1n|SP(ui)SL(ui)|=ρ(K(P),K(L))

Thus (K(U, A), ρ) is a distance space.

The following theorem illustrates the fact that information entropy in information system can be expressed by information distance between two information structures.

Theorem 4.9

Let (U, A) be an incomplete information system. Then for PA, ρ(K(P), K(∅)) is the information entropy of P.

Proof.

By Definition 11 in7, the information entropy of P is defined as:

E(P)=i=1n1n(1SP(ui)n).

But ρ(K(P),K())=1n2i=1n|SP(ui)U|

=1n2i=1n(|SP(ui)U||SP(ui)U|)=1n2i=1n(n|SP(ui)|).

Thus

ρ(K(P),K())=E(P).

Proposition 4.10

Let (U, A) be an incomplete information system. Then for P, QA,

  1. (1)

    0ρ(K(P),K(Q))11n;

  2. (2)

    If K(P) ≼ K(Q) and sim(P*)(P* ⊆ A) is an identity relation on U, then

    ρ(K(P),K(P*))ρ(K(Q),K(P*));

  3. (3)

    If K(P) ≼ K(Q), then

    ρ(K(P),K())ρ(K(Q),K()).

Proof.

  1. (1)

    Obviously, 1 ⩽ |SP(ui) ∪ SQ(ui) | ⩽ n and 1 ⩽ |SP(ui) ∩ SQ(ui)| ⩽ n (i = 1, 2,···, n). Then

    0|SP(ui)SQ(ui)|n1(i=1,2,,n).
    Thus
    0ρ(K(P),K(Q))1n2i=1n(n1)=n2nn2=11n.

  2. (2)

    Since K(P) ≼ K(Q), ∀ i, we have SP(ui) ⊆ SQ(ui). Then, ∀ i, |SP(ui) |⩽| SQ(ui)|. Thus

    ρ(K(P),K(P*))=1n2i=1n|SP(ui){ui}|=1n2i=1n(|SP(ui){ui}||SP(ui){ui}|)=1n2i=1n(|SP(ui)|1)1n2i=1n(|SQ(ui)|1)=ρ(K(Q),K(P*)).

(2) It should be noted that K(P) ≼ K(Q). Then, ∀ i, |SP(ui)| ⩽ |SQ(ui)|. Thus

ρ(K(P),K())=1n2i=1n|SP(ui)U|=1n2i=1n(|SP(ui)U||SP(ui)U|)=1n2i=1n(n|SP(ui)|)1n2i=1n(n|SQ(ui)|)=ρ(K(Q),K()).

Proposition 4.11

Let (U, A) be an incomplete information system. If sim(P*)(P* ⊆ A) is an identity relation on U, then for PA,

ρ(K(P),K(P*))+ρ(K(P),K())=11n.

Proof.

We can obtain that

ρ(K(P),K(P*))+ρ(K(P),K())=1n2i=1n|SP(ui){ui}|+1n2i=1n|SP(ui)U|=1n2i=1n(|SP(ui)|1)+1n2i=1n(n|SP(ui)|)=1n2i=1n(n1)=11n.

Proposition 4.12

Let (U, A) be an incomplete information system. Given P, Q, LA. If K(P) ≼ K(Q) ≼ K(L) or K(L) ≼ K(Q) ≼ K(P), then

ρ(K(P),K(Q))+ρ(K(Q),K(L))=ρ(K(P),K(L)).

Proof.

Since K(P) ≼ K(Q) ≼ K(L) or K(L) ≼ K(Q) ≼ K(P), we have

SP(ui)SQ(ui)SL(ui)orSL(ui)SQ(ui)SP(ui)(i=1,2,,n).

By Lemma 4.7,

|SP(ui)SQ(ui)|+|SQ(ui)SL(ui)|=|SP(ui)SL(ui)|(i=1,2,,n).
ρ(K(P),K(Q))+ρ(K(Q),K(L))=1n2i=1n|SP(ui)SQ(ui)|+1n2i=1n|SQ(ui)SL(ui)|=1n2i=1n(|SP(ui)SQ(ui)|+|SQ(ui)SL(ui)|)=1n2i=1n|SP(ui)SL(ui)|=ρ(K(P),K(L)).

Example 4.13

(Continued from Example 4.3) By Definition 4.4, one can obtain that

ρ(K(P1),K())=1016,ρ(K(P2),K())=816,ρ(K(P3),K())=816,ρ(K(P5),K())=1216,ρ(K(P1),K(P2))=216,ρ(K(P1),K(P3))=616,ρ(K(P1),K(P5))=216,ρ(K(P2),K(P3))=816,ρ(K(P2),K(P5))=416,ρ(K(P3),K(P5))=416.

This example illustrates the following facts:

  1. (1)

    It should be noted that K(P1) = K(P4), K(P5) = K(P6) = K(A). Then

    E(P1)=E(P4)=ρ(K(P1),K())=1016,E(P2)=ρ(K(P2),K())=816,E(P3)=ρ(K(P3),K())=816,E(P5)=E(P6)=E(A)=ρ(K(P5),K())=1216.

  2. (2)

    We have K(P1) ≺ K(P2) and ind(P5) = Δ. It is clear that

    ρ(K(P1),K(P5))=216416=ρ(K(P2),K(P5)),ρ(K(P1),K())=1016816=ρ(K(P2),K()).

  3. (3)

    We have ind(P5) = Δ. It is clear that for PA,

    ρ(K(P),K(P5))+ρ(K(P),K())=114=11n.

  4. (4)

    We have K(P5) ≺ K(P1) ≺ K(P2) ≺ K(∅). It is clear that

    ρ(K(P5),K(P1))+ρ(K(P1),K(P2))=416=ρ(K(P5),K(P2)),ρ(K(P1),K(P2))+ρ(K(P2),K())=1016=ρ(K(P1),K()).

5. Properties of information structures in incomplete information systems

Theorem 5.1

Let (U, A) be an incomplete information system. Then for P, QA, the following are equivalent:

  1. (1)

    K(P) = K(Q);

  2. (2)

    U/P = U/Q;

  3. (3)

    sim(P) = sim(Q);

  4. (4)

    ρ(K(P), K(Q)) = 0

Proof.

(1) ⇔ (2) ⇔ (3) are obvious.

(1) ⇔ (4) holds by Theorem 3.9.

Definition 5.2 (21)

Let 𝒜 = {X1, X2, ······, Xk} and ℬ = {Y1, Y2, ······, Yl} be two partitions on U.

  1. (1)

    H(𝒜)=i=1kp(Xi)p(UXi)
    is called the information amount of 𝒜, where p(Xi)=|Xi||U| means the probability that the element of U belongs to Xi.

  2. (2)

    H(/𝒜)=i=1kj=1lp(XiYj)p(XiYj)
    is called the condition information amount of ℬ with respect to 𝒜.

The following theorem quantitatively depict the dependence of information structures by the condition information amount.

Theorem 5.3

Let (U, A) be an incomplete information system. Then for P, QA, the following are equivalent:

  1. (1)

    K(P) ≼ K(Q);

  2. (2)

    U/P refines U/Q, i.e., for each XU/P, there exists YU/Q such that XY;

  3. (3)

    sim(P) ⊆ sim(Q);

  4. (4)

    H((U/Q)/(U/P)) = 0.

Proof.

(1) ⇔ (2) ⇔ (3) are obvious.

(3) ⇒ (4). Denote

U/P={X1,X2,,Xk},U/Q={Y1,Y2,,Yl}.

i, since U/P refines U/Q, we have XiYji for some jil. Then XiYji = ∅.

jji, YjYji = ∅. Then XiYj = ∅.

Thus ∀ i, j, Xi −Yj = ∅ or XiYj = ∅. This implies

p(XiYj)p(XiYj)=0.

Hence H((U/Q)/(U/P)) = 0.

(4) ⇒ (2). Since H((U/Q)/(U/P)) = 0, we have ∀ i, j, Xi − Yj = ∅ or XiYj = ∅. So ∀ i, j, XiYj or XiYj = ∅.

i, Xi=j=1l(XiYj) . Since Xi ≠ ∅, we have XiYji ≠ ∅ for some jil. Then XiYji.

Thus U/P refines U/Q.

Proposition 5.4

Let (U, A) be an incomplete information system. Given P, QA. If PQ, then K(Q) ≼ K(P).

Proof.

Since PQ, we have sim(Q) ⊆ sim(P). By Theorem 5.3, K(Q) ≼ K(P).

Proposition 5.5

Let (U, A) be an incomplete information system. Given PA. Then K(A) ≼ K(P) ≼ K(∅).

Proof.

This holds by Proposition 5.4.

Let (U, A) be an incomplete information system. For PA, denote

σ(U/P)={uXSP(u):X2U}.

Theorem 5.6

Let (U, A) be an incomplete information system and P, QA. Denote

U/Q={D1,D2,,Dr}.

Then the following are equivalent:

  1. (1)

    K(P) ≼ K(Q);

  2. (2)

    for each j, Dj ∈ σ(U/P);

  3. (3)

    for each j, P(Dj) = Dj;

  4. (4)

    j=1rP_(Dj)=U ;

Proof.

(1) ⇒ (2). ∀ uDj, we have Dj = SQ(u). Since K(P) ≼ K(Q), SP(u) ⊆ SQ(u). Then {u} ⊆ SP(u) ⊆ Dj. So

Dj=uDj{u}uDjSP(u)Dj.

Thus Dj=uDjSP(u)σ(U/P).

(2) ⇒ (3). Since Djσ(U/R), Dj=uXSP(u) for some X ∈ 2U.

Thus P_(Dj)=P_(uXSP(u))=uXSP(u)=Dj .

(3) ⇒ (4). This is obvious.

(4) ⇒ (1). ∀ i ⩽ n, ∀ vSP(ui). Since j=1rP_(Dj)=U , uiP(Dj) for some jr. Then SP(ui) ⊆ Dj. Denote Dj = SQ(u*). uiDj implies SQ(ui) = SQ(u*). Then vSQ(ui). So SP(ui) ⊆ SQ(ui). This shows K(P) ≼ K(Q).

Definition 5.7 (21)

Let (U, A) be an incomplete information system. Given that K(U, A) is the information structure base of (U, A). Then a mapping D : K(U, A) × K(U, A) → [0, 1] is called the inclusion degree on K(U, A), if

  1. (1)

    0 ⩽ D(K(Q)/K(P)) ⩽ 1;

  2. (2)

    K(P) ≼ K(Q) implies D(K(Q)/K(P)) = 1;

  3. (3)

    K(P) ⊑ K(Q) ⊑ K(L) implies D(K(P)/K(L)) ⩽ D(K(P)/K(Q)).

Definition 5.8

Let (U, A) be an incomplete information system. For any P, Q ⊂ A, define

D(K(Q)/K(P))=l=1n|SQ(ul)|i=1n|SQ(ui)|χSQ(ul)(SP(ul)),
where
χSQ(ul)(SP(ul))={1,ifSP(ul)SQ(ul),0,ifSP(ul)SQ(ul).

Proposition 5.9

D in Definition 5.8 is the inclusion degree under Definition 5.7.

Proof.

This is obvious.

Example 5.10

(Continued from Example 4.3) We have

K(U,A)={K(),K(P1),K(P3),K(P4),K(P10),K(A)}.

Pick P=P1, Q=P4.

K(P)=(SP(u1),SP(u2),SP(u3),SP(u4),SP(u5),SP(u6))=({u1,u4},{u2,u6},{u3},{u1,u4},{u5},{u6,u2}),K(Q)=(SQ(u1),SQ(u2),SQ(u3),SQ(u4),SQ(u5),SQ(u6))=({u1,u2,u3},{u1,u2,u3},{u1,u2,u3},{u4,u5},{u4,u5},{u6}).

It is easy to verify that

D(K(P)/K(P))=D(K(Q)/K(Q))=1.

We have

D(K(Q)/K(P))=514,D(K(P)/K(Q))=210.

This example illustrates that

D(K(Q)/K(P))+D(K(P)/K(Q))1.

The following theorem show that the dependency between information structures in an incomplete information system can be quantitatively described by the inclusion degree.

Theorem 5.11

Let (U, A) be an incomplete information system. Given P, QA. Then

  1. (1)

    K(P) ≼ K(Q) ⇔ D(K(Q)/K(P)) = 1.

  2. (2)

    K(P) ⋈ K(Q) ⇔ D(K(Q)/K(P)) = 0.

  3. (3)

    K(P) ⊑ K(Q) ⇔ 0 < D(K(Q)/K(P)) ⩽ 1.

Proof.

(1) “⇒” is obvious.

“⇐”. Put

|SQ(ul)|=ql,l=1n|SQ(ul)|=q.

Then q=l=1nql . Since D(K(Q)/K(P)) = 1, we have

l=1nqlχSQ(ul)(SP(ul))=q=l=1nql.

Then

l=1nql(1χSQ(ul)(SP(ul)))=0.

Thus ∀ l,

1χSQ(ul)(SP(ul))=0.

It follows that ∀ l, SP(ul) ⊆ SQ(ul).

Hence K(P) ≼ K(Q).

(2) “⇒”. Since K(P) ⋈ K(Q), we have ∀ l, SP(ul) ⊈ SQ(ul). Then ∀ l,

χSQ(ul)(SP(ul))=0.

Thus D(K(Q)/K(P)) = 0.

“⇐”. Since D(K(Q)/K(P)) = 0, we obtain that ∀l,

χSQ(ul)(SP(ul))=0.

Then ∀l, SP(ul) ⊈ SQ(ul). Thus K(P) ⋈ K(Q).

(3) This holds by (2).

6. Characterizations of information structures in incomplete information systems

In this section, group, and lattice characterizations of information structures in incomplete information systems are given.

6.1. Group characterizations of information structures

Definition 6.1

Let S be a non-empty set and “·” a binary operation on S.

  1. (1)

    (S,·) is called a semigroup, if for any a, bS, a · bS and for any a, b, cS, (a ·b) ·c = a ·(b ·c).

  2. (2)

    (S, ·) is called an exchangeable semigroup, if it is a semigroup and for any a, bS, a ·b = b ·a.

  3. (3)

    eS is called the identity element of S, if for any aS, e ·a = a ·e = a.

  4. (4)

    (S, ·) is called a group, if it is a semigroup and every element has an inverse element.

Theorem 6.2

(K(U, A), ⊙) is a exchangeable semi-group with the identity element K(∅).

Proof.

Suppose P, Q, LA. Then

K(P)K(Q)=(Ssim(P)(u1)Ssim(Q)(u1),Ssim(P)(u2)Ssim(Q)(u2),,Ssim(P)(un)Ssim(Q)(un))=(Ssim(P)sim(Q)(u1),Ssim(P)sim(Q)(u2),,Ssim(P)sim(Q)(un))=(Ssim(PQ)(u1),Ssim(PQ)(u2),,Ssim(PQ)(un))=K(PQ).

Similarly, K(Q) ⊙ K(P) = K(QP).

Thus

K(P)K(Q)=K(Q)K(P).

Since (K(P) ⊙ K(Q)) ⊙ K(L) = K(PQ) ⊙ K(B) = K(PQL), K(P) ⊙ (K(Q) ⊙ K(L) = K(P) ⊙ K(QL) = K(PQL), we have

(K(P)K(Q))K(L)=K(P)(K(Q)K(L)).

Hence (K(U), ⊙) is a exchangeable semigroup.

Obviously, K(∅) is the identity element.

Example 6.3

(K(U, A), ⊙) is not a group.

Consider Example 4.3. By Theorem 6.2, (K(U, A), ⊙) is a exchangeable semigroup with the identity element K(∅).

It should be noted thatPA,

K(P)K(A)=K(PA)=K(A)K().

Then K(A) has no inverse elements.

Thus (K(U, A), ⊙) is not a group.

6.2. Lattice characterizations of information structures

Theorem 6.4

Let (U, A) be an incomplete information system. Then

  1. (1)

    L = (K(U, A), ≼) is a lattice with 1L = K(∅) and 0L = K(A);

  2. (2)

    If P1, P2A and 𝒜 (P1, P2) = {P | PA, sim(P1) ∪ sim(P2) ⊆ sim(P)}, then

    K(P1)K(P2)=K(P1)K(P2)=K(P1P2),K(P1)K(P2)=P𝒜(P1,P2)K(P)=K(𝒜(P1,P2)).

Proof.

Obviously, ∀ PA, K(P) ≼ K(P).

Suppose that K(P) ≼ K(Q), K(Q) ≼ K(P). By Theorem 5.3, sim(P) ⊆ sim(Q), sim(Q) ⊆ sim(P). Then sim(P) = sim(Q). Thus K(P) = K(Q).

Suppose that K(P) ≼ K(Q), K(Q) ≼ K(L). By Theorem 5.3, sim(P) ⊆ sim(Q), sim(Q) ⊆ sim(L). Then sim(P) ⊆ sim(L)).

By Theorem 5.3, K(P) ≼ K(L).

Hence (K(U, A), ≼) is a partial order set.

By the proof of Theorem 5.1, we have

K(P1)K(P2)=K(P1P2),P𝒜(P1,P2)K(P)=K(𝒜(P1,P2)).

Since P1, P2P1P2, by Proposition 5.4, we have K(P1P2) ≼ K(P1) and K(P1P2) ≼ K(P2). Then K(P1P2) is the lower bound of {K(P1), K(P2)}.

Suppose K(P) is the lower bound of {K(P1), K(P2)} with PA. Then K(P) ≼ K(P1), K(P) ≼ K(P2). By Theorem 5.3, we have sim(P) ⊆ sim(P1) and sim(P) ⊆ sim(P2). Then sim(P) ⊆ sim(P1) ∩ sim(P2) = sim(P1P2). By Theorem 5.3, K(P) ≼ K(P1P2).

Thus

K(P1)K(P2)=K(P1P2).

P𝒜 (P1, P2), since sim(P1) ∪ sim(P2) ⊆ sim(P), we have

sim(P1),sim(P2)sim(P).

Then

sim(P1),sim(P2)P𝒜(P1,P2)sim(P)=sim(P𝒜(P1,P2)P)=sim(𝒜(P1,P2)).

By Theorem 5.3, K(P1), K(P2) ≼ K(∪𝒜 (P1, P2)). Then K(∪𝒜 (P1, P2)) is the upper bound of {K(P1), K(P2)}.

Suppose K(S) is the upper bound of {K(P1), K(P2)} with SA. Then K(P1) ≼ K(S), K(P2) ≼ K(S).

By Theorem 5.3, sim(P1) ⊆ sim(S) and sim(P2) ⊆ sim(S).

Then S𝒜 (P1, P2). So S ⊆ ∪𝒜 (P1, P2).

By Proposition 5.4, K(∪𝒜 (P1, P2)) ≼ K(S).

Thus K(P1) ∨ K(P2) = K(∪𝒜 (P1, P2)).

Hence L is a lattice.

Obviously, 1L = K(∅), 0L = K(A).

Corollary 6.5

(K(U, A), ∧) is a exchangeable semigroup with the identity element K(∅).

Example 6.6

L = (K(U, A), ≼) is not a distributive lattice.

Consider Example 4.3.

By Theorem 6.4, L = (K(U, A), ≼) is a lattice with 1L = K(∅) and 0L = K(A).

We have

  • 𝒜(P2, P1P4) = 𝒜 (P2, P2) = {PA : sim(P2) ∪ sim(P2) ⊆ sim(P)} = {PA : sim(P2) ⊆ sim(P)} = 2A,

  • 𝒜 (P2, P1) = {PA : sim(P2) ∪ sim(P1) ⊆ sim(P)} = {PA : sim(P1) ⊆ sim(P)} = {∅, P1, P3, P6},

  • 𝒜 (P2, P4) = {PA : sim(P2) ∪ sim(P4) ⊆ sim(P)} = {PA : sim(P4) ⊆ sim(P)} = {∅, P4}.

Then

𝒜(P2,P1P4)={a1,a2,a3,a4},(𝒜(P2,P1))(𝒜(P2,P4))={a1,a3,a4}.

By Theorem 5.1,

K(𝒜(P2,P1P4))K((𝒜(P2,P1))(𝒜(P2,P4))).

By Theorem 6.4,

K(P2)(K(P1)K(P4))=K(P2)K(P1P4)=K((𝒜(P2,P1P4))),
(K(P2)K(P1))(K(P2)K(P4))=K((𝒜(P2,P1))K((𝒜(P2,P4)))=K((𝒜(P2,P1))(𝒜(P2,P4))).

Thus

K(P2)(K(P1)K(P4))(K(P2)K(P1))(K(P2)K(P4)).

Therefore, (K(U, A), ≼) is not a distributive lattice.

Example 6.7

(K(U, A), ⊑) is not a partial order set.

Consider Example 4.3. We have K(P1) ⊑ K(P2), K(P2) ⊑ K(P1). But K(P1) ≠ K(P2). This implies thatis not anti-symmetric.

Therefore, L = (K(U, A), ≼) is not a distributive lattice.

Example 6.8

(K(U, A), ⊑) is not a partial order set.

Consider Example 4.3. We have K(P) ⊑ K(Q), K(Q) ⊑ K(P). But K(P) ≠ K(Q). This implies thatis not anti-symmetric.

Hence (K(U, A), ⊑) is not a partial order set.

7. Conclusions

In this paper, information structures in an incomplete information system have been considered as a special case of set vectors. Based on this consideration, relationships between information structures have been discussed from two aspects of dependence and separability. Properties of information structures are given. Group and lattice characterizations of information structures have been obtained. These results will be significant for establishing a framework of granular computing in a information system. This vectorbased framework can be used to represent different dimension of information in an incomplete information system and may have potential applications to knowledge discovery in incomplete information systems. In the future, we will consider the fuzzification of the proposed results and give some applications such as dealing with knowledge discovery in incomplete information systems.

Acknowledgements

The authors would like to thank the editors and the anonymous reviewers for their valuable comments and suggestions which have helped immensely in improving the quality of the paper. This work is supported by National Natural Science Foundation of China (11461005), Natural Science Foundation of Guangxi (2016GXNSFAA380045, 2016GXNS-FAA380282), Key Laboratory of Optimization Control and Engineering Calculation in Department of Guangxi Education, and Special Funds of Guangxi Distinguished Experts Construction Engineering.

References

1.N Chen and B Qin, “Invariant characterizations of information structures in a latticevalued information system under homomorphisms based on data compression”, Journal of Intelligent & Fuzzy Systems, Vol. 33, 2017, pp. 3987-3998.
2.TW Hungerford, “Algebra”, Sprnger-Verlag Press, New York, 1974.
3.TY Lin, “Granular computing on binary relations I: data mining and neighborhood systems”, A Skowron and L Polkowski (editors), Rough Sets In Knowledge Discovery, Physica-Verlag, 1998, pp. 107-121.
4.TY Lin, “Granular computing on binary relations I-I: rough set representations and belief functions”, A Skowron and L Polkowski (editors), Rough Sets In Knowledge Discovery, Physica-Verlag, 1998, pp. 121-140.
6.Z Li, Q Li, R Zhang, and N Xie, “Knowledge structures in a knowledge base”, Expert Systems, Vol. 33, 2016, pp. 581-591.
8.Z Pawlak, “Rough sets: Theoretical sspects of reasoning about data”, Kluwer Academic Publishers, Dordrecht, 1991.
15.WZ Wu, Y Leung, and JS Mi, “Granular computing and knowledge reduction in formal contexts”, IEEE Transactions on Knowledge and Data Engineering, Vol. 21, 2009, pp. 1461-1474.
17.LA Zadeh, “Fuzzy logic equals computing with words”, IEEE Transactions on Fuzzy Systems, Vol. 4, 1996, pp. 103-111.
21.W Zhang and G Qiu, “Uncertain decision making based on rough sets”, Tsinghua University Publishers, Beijing, 2005.
22.L Zhang and B Zhang, “Theory and application of problem solving-theory and application of granular computing in quotient spaces, Tsinghua University Publishers, Beijing, 2007.
Journal
International Journal of Computational Intelligence Systems
Volume-Issue
11 - 1
Pages
1179 - 1191
Publication Date
2018/06/04
ISSN (Online)
1875-6883
ISSN (Print)
1875-6891
DOI
10.2991/ijcis.11.1.89How to use a DOI?
Copyright
© 2018, the Authors. Published by Atlantis Press.
Open Access
This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

Cite this article

TY  - JOUR
AU  - Guangji Yu
PY  - 2018
DA  - 2018/06/04
TI  - Information structures in an incomplete information system: A granular computing viewpoint
JO  - International Journal of Computational Intelligence Systems
SP  - 1179
EP  - 1191
VL  - 11
IS  - 1
SN  - 1875-6883
UR  - https://doi.org/10.2991/ijcis.11.1.89
DO  - 10.2991/ijcis.11.1.89
ID  - Yu2018
ER  -