Granular computing the rough set model comparison

Abstract: This paper presents several combinations of grain under the rough set model, and with the single one under the rough set were compared, while the next logical operations with grain rough set model for comparison, get creative combination tablets, as well as a single logical operation under grain rough set model the relationship between the results showed that the combination of tablets and capsules constitute a logical chain structure, which is based on information granules explore knowledge acquisition and dynamic grain reasoning laid the foundation.

Keywords: Combination tablets; grain logic operations; single one; rough set; approximation

Comparison of rough set model under granular computing


ZHANG Xiao-feng, ZOU Hai-lin, JIA Shi-xiang

(School of Information Science & Engineering, Ludong University, Yantai Shandong 264025, China)


Abstract: This paper proposed the rough set model under combination granule, and compared it with that under single granular, also with rough set model under logical computing of granule, which contributed to the relationship between rough set models under combination granule, singular granules and logical computing of granules. Results show that combination granule and logical computing of granule construct a chain, which will lay a foundation for knowledge acquisition based on information granule and induction based on dynamic granule.

Keywords:: combination granule; logical computing of granule; single granular; rough set; approximation

0 Introduction

Particle size calculated from Zadeh [1] proposed in 1996, he believed that human knowledge is mainly based on three main concepts, namely size, organization and causation which granular computing is an umbrella that covers about granular computing theory, methodology, techniques and tools of research in the rough set theory, concept lattice, knowledge engineering, data mining, artificial intelligence, machine learning and other fields have potential applications in information science research has become one of the hotspots [2] titles of papers.

Rough Set [3] is defined as the relationship between a given set of upper and lower approximation constitutes an ordered pair approximation has been successfully applied to machine learning, decision analysis, process control, pattern recognition and data mining and other fields [4]. Traditional rough set theory is based on the definition of a single one, namely static grains. literature [5-7] proposed a multi-grain operation under rough set theory model, namely MGRS (multi-granulations rough set, MGRS), and discussed the relevant mathematical properties. Taking into account the literature [5-7] in the collection of mainly discussed in size P and Q P + Q, P ∩ Q collection of computing the lower and upper approximations, the paper under the multi-grain rough set model calculation carried out further discussion of them with a single granularity rough set model are compared; same time, the multi-grain operation under rough set model and combination granulation under rough set model was? comparison.

A related concepts

This chapter gives some related concepts are given for subsequent discussion is necessary.
Define a propositional logic, propositions P and Q is denoted conjunction P ∧ QP ∧ Q is true if and only if P and Q are both true; propositional disjunction of P and Q is denoted P ∨ Q, P ∨ Q is False if and only if P and Q are both false.

Definition 2 information system is a four-tuple (U, A, V, f). Them, U is a collection of objects, called the domain (universe); A is used to describe a collection of properties of the object; V is the attribute set A the range; f: U × A → V reflects on an object in the value of a property, and information systems are usually abbreviated as (U, A).

Definition 3 Given a non-empty domain U, U × U subset of EU × U represents a relation on U domain. Ordered pair (U, E) is called an approximation space [8] (approximation space).

If the relationship E reflexive, symmetric and transitive, then E is called an equivalence relation [9]. Equivalence relation E on the domain can form a partition of U, denoted by U / E. It can be proved equivalence relation and division are equivalent, ie, given an equivalence relation can be constructed domain partition; Similarly, a partition of a given domain, the domain can be constructed on an equivalence relation.

Information system (U, A), if the two bodies x, y ∈ U on the properties of the same value a ∈ A, then we say both in the attribute a is not resolved, if x, y in each of the set BA an attribute b ∈ B are indistinguishable, claimed both in the set B is indistinguishable with x in the set B indistinguishable on the set of all individuals in the collection called x equivalence classes generated on B, is denoted by [x]? B, it can be seen from the x-indiscernible grain structure of an information element of [8] (information granule).

Theorem 1 domain U is the set of all elements generated on the equivalence class A satisfies the following three conditions [9]:


a)? x ∈ U, there is [x]? A ≠?;

b)? x, y ∈ U, or [x]? A = [y]? A set, or [x]? A ∩ [y]? A =? established;

c) ∪ x ∈ U [x]? A = U.
This theorem shows that the set A of all equivalence classes generated on the domain constitutes a partition of the equivalence class equivalence class is called the base.

Definition 4 any subset of the domain U XU, if it can be represented as a certain equivalence classes and sets, called x is accurate (or known as definable), otherwise known as rough, if a XU concept is rough, you can use two precisely defined to approximate the set, called the lower approximation of X or upper approximation, denoted by PX and X, defined as follows:

PX = ∪ [x]? PX [x]? P

X = ∪ [x]? P ∩ X ≠? [X]? P


Wherein: [x]? P = {y | f (x, P) = f (x, P)} is a set of attributes P, x is generated equivalence classes. Clearly established the following formula:
PXXX
Definition 5 If the set X is rough, it is called an ordered pair <PX,X> rough set of the rough set approximation quality @? P (X) is defined as follows:

@? P (X) = | PX | / | X |

Two types based on granular computing rough set model

Definition 6 a given information system (U, A), P, QA. Assuming P, Q can be constructed corresponding to the domain is divided into

U / IND (P) = {[x? 1]? P, [x? 2]? P, ..., [x | U |]? P}
U / IND (Q) = {[x? 1]? Q, [x? 2]? Q, ..., [x | U |]? Q}

Constituted by the P and Q is defined as the combination of the two grains

U / IND (P ∩ Q) = {[x? 1]? P ∩ [x? 1]? Q, ..., [x | U |]? P ∩

[X | U |]? Q} (1)


U / IND (P ∪ Q) = {[x? 1]? P ∪ [x? 1]? Q, ..., [x | U |]? P ∪

[X | U |]? Q} (2)


Such as information system (U, A) in, XU and P, QA. Wherein U = {e? 1, e? 2, e? 3, e? 4, e? 5, e? 6, e? 7, e? 8}, X = {e? 1, e? 2, e? 5, e? 7, e? 8}. from the P, Q divide the domain were formed

U / IND (P) = {{e? 1, e? 7}, {e? 2, e? 3, e? 4, e? 5, e? 6}, {e? 8}}

U / IND (Q) = {{e? 1, e? 2}, {e? 3, e? 4, e? 5}, {e? 6, e? 7, e? 8}}


Therefore U / IND (P ∩ Q) = {{e? 1}, {e? 2}, {e? 3, e? 4, e? 5}, {e? 6}, {e? 7}, {e? 8}}


U / IND (P ∪ Q) = {e? 1, e? 2, e? 7}, {e? 1, e? 2, e? 3, e? 4, e? 5, e? 6}, { e? 2, e? 3, e? 4, e? 5, e? 6},? {e? 2, e? 3, e? 4, e? 5, e? 6, e? 7, e? 8 }, {e? 1, e? 6, e? 7, e? 8}, {e? 8}

Theorem 2 U / IND (P ∩ Q) to form the domain partition, and U / IND (P ∪ Q) is formed covering the domain.

Prove the equivalence relation satisfy reflexive, by P, Q construct equivalence class [x? I]? P and [x? I]? Q, there is x? I ∈ [x? I]? P and x ? i ∈ [x? i]? Q. So there? ∪ x? i ([x? i]? P ∩ [x? i]? Q) = ∪ x? i [x? i]? P ∪ [x ? i]? Q) = U established, while there? [x? i]? P ∩ [x? i]? Q ≠?, [x? i]? P ∪ [x? i]? Q ≠?, ie U / IND (P ∩ Q) and U / IND (P ∪ Q) forming a field coverage.

Further consideration, if x? J ∈ [x? I]? P ∩ [x? I]? Q, if x? J ≠ x? I, there are x? J ∈ [x? I]? P, x? J ∈ [x? i]? Q. Since [x? i]? P and [x? i]? Q are equivalence classes, according to Theorem 1 x? i ∈ [x? j]? P, x? i ∈ [x? j]? Q established that x? i ∈ [x? i]? P ∩ [x? i]? Q holds.

If x? J? [X? I]? P ∩ [x? I]? Q, you may have the following three cases: a) x? J? [X? I]? P, x? J? [X? i]? Q; b) x? j? [x? i]? P, x? j ∈ [x? i]? Q; c) x? j ∈ [x? i]? P, x? j? [ x? i]? Q. Accordingly, based on the nature of equivalence classes can be obtained: a) x? i? [x? j]? P, x? i? [x? j]? Q; b) x? i ? [x? j]? P, x? i ∈ [x? j]? Q; c) x? i ∈ [x? j]? P, x? j? [x? i]? Q, so that x ? i? [x? j]? P ∩ [x? j]? Q.

Can be obtained through the above two cases, or [x? I]? P ∩ [x? I]? Q = [x? J]? P ∩ [x? J]? Q established, or ([x? I]? P ∩ [x? i]? Q) ∩ ([x? j]? P ∩ [x? j]? Q) =? established, so U / IND (P ∩ Q) form a partition of the domain.

QED.

Definition 7 Given information system (U, A), P, QA, XU, define composite grains under rough set as follows:

P ∩ QX = ∪ ([x]?? P ∩ [x]?? Q) X

([X]? P ∩ [x]? Q)

P ∩ QX = ∪ ([x]?? P ∩ [x]?? Q) ∩ X ≠?

([X]? P ∩ [x]? Q)

P ∪ QX = ∪ ([x]?? P ∩ [x]?? Q) X

([X]? P ∪ [x]? Q)

P ∪ QX = ∪ ([x]?? P ∩ [x]?? Q) ∩ X ≠?

([X]? P ∪ [x]? Q)


Literature [10] has defined the logical operators under grain rough set model, such as the definition 8.

Definition 8 Given information system (U, A), P and Q are two information systems information granules, tablets logic operation is under rough set model is defined as

P ∧ QX = ∪ {x | ([x]? PX) ∧ ([x]? QX)}

P ∧ QX = ∪ {x | ([x]? P ∩ X ≠?) ∧ ([x]? Q ∩ X ≠?)}

P ∨ QX = ∪ {x | ([x]? PX) ∨ ([x]? QX)}

P ∨ QX = ∪ {x | ([x]? P ∩ X ≠?) ∨ ([x]? Q ∩ X ≠?)}


Combination tablets will be discussed below under the single grain under rough set and rough set model as well as the relationship between the combination of grains and grain rough set under the next logical relationships between rough set.

3 single-and multi-grain computing a rough set of relations under

The author has proved the following theorem.

Theorem 3 given information system (U, A), P, QA, XU, there

P ∧ QX = PX ∩ QX

P ∧ QX = X ∩ X

P ∨ QX = PX ∪ QX

P ∨ QX = X ∪ X


In this paper, the use of a combination of tablets, capsules and logical operations with the rough set model for further comparison, we can get the following theorem.

Theorem 4 Given information system (U, A), P, QA, XU there

PX ∩ QX? P ∩ QX

P ∩ QXX ∩ X

Proof

a)? x ∈ PX ∩ QX, by definition there is [x]? PX and [x]? PX established, it is [x]? P ∩ [x]? QX, ie x ∈? P ∩ QX established. therefore PX ∩? QX? P ∩ QX.
b)? x ∈? P ∩ QX, there are ([x]? P ∩ [x]? Q) ∩ X ≠?. because [x]? P ∩ [x]? Q [x]? P, [x] ? P ∩ [x]? Q [x]? Q, there is [x]? P ∩ X ≠? And [x]? Q ∩ X ≠?, so there is x ∈ X ∩ X, ie P ∩ QXX ∩ X.

QED.

Links to free download http://eng.hi138.com
The theorem shows two particle P, Q combination produces a quotient space U / IND (P ∩ Q) than the combination of size P ∧ Q finer structure of knowledge, and thus on the approximation of the set X is more accurate.

Theorem 5 given information system (U, A), P, QA, XU, there

P ∪ QX = PX ∩ QX

P ∪ QX = X ∪ X

Proof

a)? x ∈? P ∪ QX, there is [x]? P ∪ [x]? QX established because of [x]? P [x]?? P ∪ [x]? Q, [x? Q] [x ]? P ∪ [x]? Q, there is [x]? PX and [x]? QX established that
x ∈ PX and x ∈ QX. therefore x ∈ PX ∩ QX, namely
P ∪ QXPX ∩ QX established.
? X ∈ PX ∩ QX, by definition there is x ∈ PX and x ∈ QX, therefore [x]? PX and [x]? QX established because of [x]? PX and [x]? QX established with [x ]? P ∪ [x]? QX established so there is x ∈? P ∪ QX, namely PX ∩ QX? P ∪ QX.

Taking these two things get? P ∪ QX = PX ∩ QX.

b)? x ∈? P ∪ QX, there are ([x]? P ∪ [x]? Q) ∩ X ≠?, therefore [x]? P ∩ X ≠? or


[X]? Q ∩ X ≠?, Ie x ∈ X or x ∈ X

Establishment, x ∈ X ∪ X. Thus available? P ∪ QXX ∪ X holds.
? X ∈ X ∪ X, there is x ∈ X or x ∈ X established that [x]? P ∩ X ≠?, Or [x]? Q ∩ X ≠?. Because [x]? P [x]? P ∪ [x]? Q, [x]? Q [x]? P ∪ [x]? Q, can be obtained ([x]? P ∪ [x]? Q) ∩ X ≠? established. therefore x ∈? P ∪ QX, namely X ∪ X? P ∪ QX.

Based on the above two points can be obtained P ∪ QX = X ∪ X.
QED.
The theorem states that under the combined particle P ∪ Q rough set model by a single one under the rough set model constructed.

Four different grain operation under rough set model relationship

Since in combination tablets, capsules and other different logic operations can be formalized under grain operations corresponding rough sets, then the question arises: under different grain computing What is the relationship between the rough set?

Theorem 6 Given information system (U, A), P, QA, XU, there

P ∪ QX? P ∩ QX

P ∩ QX? P ∪ QX

@ P ∪ Q ≤ @ P ∩ Q

Proof
a)? x ∈? P ∪ QX, there is [x]? P ∪ [x]? QX, so you can get [x]? PX and [x]? QX. thus can be inferred [x]? P ∩ [ x]? QX, ie x ∈? P ∩ QX. therefore P ∪ QX? P ∩ QX.
b)? x ∈? P ∩ QX, by definition there ([x]? P ∩ [x]? Q) ∩ X ≠?; Also, because [x]? P ∩ [x]? Q [x]? P ∪ [x]? Q, there is ([x]? P ∪ [x]? Q) ∩ X ≠?, available? x ∈? P ∪ QX, so there? P ∩ QX? P ∪ QX.

c) As the


P ∪ QX? P ∩ QX,


There |? P ∪ QX | ≤ |? P ∩ QX |; due

P ∩ QX? P ∪ QX, there |? P ∩ QX | ≤ |? P ∪ QX |. Accordingly,? @ P ∪ Q ≤ @ P ∩ Q.

QED.

Theorem 7 given information system (U, A), P, QA, XU, there

P ∧ QX? P ∩ QX

P ∩ QX? P ∧ QX

@ P ∧ Q ≤ @ P ∩ Q

Proof
a)? x ∈? P ∧ QX, there is [x]? PX and [x]? QX established, it can be obtained ([x]? P ∩ [x]? Q) X holds. therefore P ∨ QX? P ∩ QX.

b) P ∩ QX = ∪ {x | ([x]? P ∩ [x]? Q) ∩ X ≠?},? P ∧ QX =? ∪ {x | ([x]? P ∩ X ≠?) ∧ ([x]? Q ∩ X ≠?)}.
? X ∈? P ∩ QX, there are ([x]? P ∩ [x]? Q) ∩ X ≠?. Because [x]? P ∩ [x]? Q [x]? P

And [x]? P ∩ [x]? Q [x]? Q, can be obtained [x]? P ∩ X ≠? With?

[X]? Q ∩ X ≠?, There is x ∈? P ∧ QX. Therefore P ∩ QX? P ∧ QX.

c) As the

P ∨ QX? P ∩ QX, with |? P ∨ QX | ≤ |? P ∩ QX |; Meanwhile, P ∩ QX? P ∧ QX, there
|? P ∩ QX | ≤ |? P ∧ QX |. Accordingly @ P ∧ Q ≤ @ P ∩ Q holds.

QED.

Theorem 8 given information system (U, A), P, QA, XU, there


P ∨ QX? P ∩ QX

P ∩ QX? P ∨ QX

@ P ∨ Q ≤ @ P ∩ Q

Proof

a)? x ∈? P ∨ QX, there is [x]? PX or [x]? QX established due? [x]? P ∩ [x]? Q [x]? P and [x]? P ∩ [ x]? Q [x]? Q, there is [x]? P ∩ [x]? QX holds, then there is x ∈? P ∩ QX established. therefore P ∨ QX? P ∩ QX.
b)? x ∈? P ∩ QX, there are ([x]? P ∩ [x]? Q) ∩ X ≠?. because [x]? P ∩ [x]? Q [x]? P and [x] ? P ∩ [x]? Q [x]? Q. There [x]? P ∩ X ≠?, and [x]? Q ∩ X ≠? true, then there is x ∈? P ∨ QX. therefore P ∩ QX ? P ∨ QX.
c) Since P ∨ QX? P ∩ QX, there |? P ∨ QX | ≤ |? P ∩ QX |; Since P ∩ QX? P ∨ QX, there |? P ∩ QX | ≤ |? P ∨ QX |. So @ P ∨ Q ≤ @ P ∩ Q.

QED.

Theorem 9 given information system (U, A), P, QA, XU, there

P ∧ QX =? P ∪ QX

P ∧ QX? P ∪ QX


@ P ∪ Q ≤ @ P ∧ Q

Proof

a)? x ∈? P ∪ QX, by definition, can be obtained ([x]? P ∪ [x]? Q) X established


According to the relationship between the sets can be obtained

[X]? PX and [x]? QX established so there is x ∈ P ∧ QX established that

P ∪ QX? P ∧ QX.

? X ∈? P ∧ QX, there are ([x]? PX and [x]? QX established, therefore ([x]? P ∪ [x]? Q) X, ie x ∈? P ∪ QX, so P ∧ QX? P ∪ QX.
Combination of these two situations P ∧ QX =? P ∪ QX.

b)? x ∈? P ∧ QX, there is [x]? P ∩ X ≠?, and

[X]? Q ∩ X ≠? Established because of [x]? P [x]? P ∪ [x]? Q, there must be

([X]? P ∪ [x]? P) ∩ X ≠?, That is x ∈? P ∪ QX. Therefore P ∧ QX? P ∪ QX established.
c) Since P ∧ QX =? P ∪ QX, there |? P ∧ QX | = |? P ∪ QX |; Since P ∧ QX? P ∪ QX, there |? P ∧ QX | ≤ |? P ∪ QX | So can get @ P ∪ Q ≤ @ P ∧ Q.

QED.

Theorem 10 given information system (U, A), P, QA, XU, there


P ∪ QX? P ∨ QX

P ∨ QX? P ∪ QX

@ P ∨ Q ≤ @ P ∪ Q

Proof

a)? x ∈? P ∪ QX, there is [x]? P ∪ [x]? QX established;

Since [x]? P [x]? P ∪ [x]? Q, can be obtained [x]? PX, ie x ∈? P ∨ QX.
Therefore P ∪ QX? P ∨ QX.

b)? x ∈? P ∨ QX, there is [x]? P ∩ X ≠? or

[X]? Q ∩ X ≠? Established due to [x]? P [x]? P ∪ [x]? Q,


[X]? Q [x]? P ∪ [x]? Q, the above two cases can be derived in any one of the

([X]? P ∪ [x]? Q)

∩ X ≠?. Therefore P ∨ QX? P ∪ QX.

c) Since P ∪ QX? P ∨ QX, there |? P ∪ QX | ≤ |? P ∨ QX |; Since P ∨ QX? P ∪ QX, there

|? P ∨ QX | |? P ∪ QX |. Therefore available @ P ∨ Q ≤ @ P ∪ Q.

QED.
The above theorem can be obtained through the combination of the rough set model grain grain logic operation with the relationship between the rough set model, and found that the knowledge of the relevant grain roughness has the following relationship:

@ P ∨ Q ≤ @ P ∪ Q

≤ @ P ∧ Q ≤ @ P ∩ Q

Based on this, from another angle, the thickness of the formal definition given knowledge.
Definition 9 Given information system (U, A), P, Q are two information granules constructed quotient space, called P? Q, if for any collection XU, both @? Q ≤ @? P holds.

In fact, if P? Q, by providing the knowledge set P tablets than the knowledge provided by the Q finer. Based on the above related theorems, we can get the following conclusions.

Theorem 11 <{P ∨ Q, P ∪ Q, P ∧ Q, P ∩ Q},?> Is a chain.
Proved slightly.

5 Conclusion

This article discusses the single grain computing and multi-grain operation between rough sets and different multi-grain operation between rough sets these two issues, for further study of the structure and the dynamics tablets tablets based on dynamic knowledge acquisition laid a good foundation.

References:

[1] ZADEH L A.Fuzzy logic = computing with words [J]. IEEE Trans on Fuzzy System, 1996,4 (1) :103-111.

[2] LIANG Ji-ye, QIAN Yu Hua. Information system information granules and entropy theory [J]. Science in China Series E, 2008,38 (12) :2048-2065.

[3] PAWLAK Z.Rough sets [J]. International Journal of Computer and Information Sciences, 1982,11 (5) :341-356.

[4] Zhang Wenxiu, Wu Chi, LIANG Ji-ye, and so on. Rough set theory and method [M]. Beijing: Science Press, 2001.

[5] QIAN Yu-hua, LIANG Ji-ye.Rough set method based on multi-granulations [C] / / Proc of the 5th IEEE Conference on Cognitive Informa-? Tics.New York: IEEE Press ,2006:297-304 .

[6] QIAN Yu-hua, LIANG Ji-ye, DANG Chang-yin.MGRS in incomplete information systems [C] / / Proc of IEEE International Conference on Granular Computing.New York: IEEE Press ,2007:163-168.

[7] QIAN Yu-hua, LIANG Ji-ye, YAO Yi-yu, et al.MGRS: a multi-granulation rough set [J]. Information Sciences, 2009,180 (6) :949-970.

[8] YAO Yi-yu.Stratified rough sets and granular computing [C] / / Proc of the 18th International Conference of the North American Fuzzy Information Processing Society.New York: IEEE Press ,1999:800-804.

[9] Fu Yan, Gu Xiaofeng, Liu Qi, and, etc. Discrete Mathematics [M]. Beijing: Higher Education Press, 2008 Links to free download http://eng.hi138.com

Theoretical Computer Papers