2012 IEEE International Conference on Granular Computing

Knowledge Approximations and Representations in

Binary Granular Computing

Zehua Chen Tsau young Lin Gang Xie

Department ofAutomation, Department of Computer Department ofAutomation,
Taiyuan Univ. of Technology, Science, San Jose State Univer­ Taiyuan Univ. of Technology,
Taiyuan, Shanxi, China sity, San Jose, CA, USA Taiyuan, Shanxi, China
email : chenzehua@tyut. edu.cn email : tylin@cs. s;su. edu email : xiegang@tyut. edu. cn

ledge. Some examples are given to illustrate all the

Abstract-The primary goal of this paper is to develop definitions mentioned above.
knowledge approximations and representations on binary
relation from the view of granular computing (GrC). In II. BINARY GRANULAR COMPUTING
rough sets (RS), approximations can be defined by two
equivalent views, topology and elementary knowledge. A. Binary Relation and Binary Neighborhood System
The latter view does not behave well mathematically, so
in GrC, topology has often been adopted. Unfortunately, Definition}: binary relation and equivalent relation
such approximations, called closure and interior, can not
be interpreted elementary knowledge. In this paper, we
Let B<;;; VxU be a binary relation, XE V is B-related
show that they can be interpreted by central knowledge. to y E U if ( X,Y)E B , denoted by xBy. If V= U, then
and based on which knowledge representation is devel­ say B is a binary relation over U.
oped. Many examples are used to illustrate the idea. B is an equivalent relation marked as E if B satisfies:
(1) Reflectivity: VXE U, ( X,X)E B;
Keywords-approximation; rough set; binary granular
computing (2) Symmetric: VX,YE U,if(x,Y)E B, then( y,x)E B;
(3) Transitivity:
I. INTRODUCTION VX,y,zE U,if(X,Y)E B, ( y,Z)E B, then ( X,Z)E B
Approximation is a most important concept in X is E-related to y if (x,y) E E, denoted by xEy.
Rough Set (RS) theory. Prof. Pawlak defined it in two Definition2: binary neighborhood system and partition
equivalent ways[l1, from view of elementary set and
from topological space. Most RS concepts were based Let B be a binary relation over U, for each object
on the set definition. pE u, U={l,2, oo. p, oo. n}, 1:::; P:::; n, we associate a
There are many studies focus on generalized RS and binary subset NB(p) <;;; U
Granular Computing [2.3.41. NB(p)={UE UI(p,U)E B} (1)
Lin suggested Granular Computing (GrC) to follow
NB (P) is consist of elements u that related to p by B,
Zadeh's Granular Mathematicsrs1. In 1989, He firstly
Ns(P) is called the right neighborhood of p, corres­
studies database from view of neighborhood system [21. pondingly, left neighborhood can be defined, in this
Now he has established 9 GrC mathematical models[71. paper, we just mentioned right neighborhood system,
In this paper we mainly study the knowledge approxi­ for simplicity, just call it neighborhood in short.
mation and representation theories of binary/3rd GrC
The set {Ns(P)[P E U} for all the points p E U is de­
model_ the binary relation based Grc. Firstly, binary
fined as the binary neighborhood system (BNS)[61.
relation and binary neighborhood system[21 were intro­
Let E be an equivalent relation over U, for each ob­
duced. Then, center set and central knowledge are de­
ject pE U , we associate a subset NE(p) <;;; U , where
fined. The third, binary knowledge representation sys­
tem (B-KRS) was built. Different from knowledge NE(P) =[P]E={uE U I(p,U)E E} is consist of elements u
representation system in RS, the information in B-KRS that related to p by E , fp]E represents the equivalent
is lost compared with original binary knowledge base. class of p. Binary neighborhood system {fp]E[P E U}
However, once the B-KRS is built, knowledge reduc­ form a partition over U, marked as 1[E'
tion and association rule discovery for binary know­
ledge base can be done. At last, approximations in bi­ B. Quotient Set and Quotient Structure
nary granular computing were defined by closure and
Definition 3 to 9 can be traced back to [2,6,7,8,9].
interior, which can be interpreted as approximation of
Definition 7 is defined in this paper to express upper
central knowledge instead of the elementary know-
and lower approximation of binary relation from view
of center set and topology.

978-1-4673-2311-6/12/$31.00 ©2012 IEEE

Definition 3: derived partition and center set point qp E Q , and then Q become knowledge Set Qk.
For a given binary relation B, let U,PE U, an /oP:U --t C also map the elements of U into C.
equivalent relation EB is defmed by:
Quite different from knowledge representation in
(U,p)E EB ¢:::} NB(u)=NB(p) (2)
RS, binary knowledge representation system has lost
It is easy to prove that EB is an equivalent relation some information in binary knowledge base. How to
derived by B. Correspondingly, the partition ?rE gener- continue knowledge discovery on binary knowledge
B
ated by EB is defined as derived partition[7], shown as representation system should attract more attention.
equation 3:
D. Approximations in Binary Granular Computing
(3)
Where Definition 6: approximations by topology
[ plEB ={u 1 NB(p)= NB(u),U,pE U} (4) Let X be an arbitrary subset over U, p an arbitrary
C(p)=[ plBE (5) point in U. If NB (P) is none empty and NB (P)s;;;X, then
In equation 5, C(P)is defined as Center Set. p is an interior of X.
When we give center set a meaningful name, the From topological space, X. and X· are defined as
center set will turn into central knowledge. (8)
X.={pE UINB(p)1'¢,NB(p)s;;;X}
In RS, equivalent relation E is a special case of bi­
· (9)
nary relation B, and ?rE become?rE• x ={pE U 1 NB(p) * ¢,NB(p) n X * ¢}
B
[7 ] The topological definition here is different from that
Definition4: Quotient Set and Quotient Structure .
In Binary Granular Computing, Quotient Set Q is in RS, and it also has no knowledge explanation. In
generated by equivalent relation EB. this section, we redefine it by Center Set, just as shown
In quotient set, equivalent class [ plE is turned into a in definition 7, it will provide artificial intelligent in­
B terpretation for topological defmition.
point qp.
Intuitively, [ plE is white box, and qp, the black box. Definition 7: approximations by Center Sets
B
There exists a natural project P: U --t Q or pH q , Center Set can be used to define upper and lower
p
approximation with artificial intelligent explanation.
where pE U, qpE Q.
x. =U{C(p) 1 pE U,NB(p) * ¢,NB(p) S;;; X} (10)
Derived partition ?rE is composed of [ plE or C (P)
B B X· = U{C(p) 1 pE u, VNB(p) * ¢,::iyE NB(p) n X * ¢} (11)
(white boxes, subset), and the quotient set Q, by qp
(black box, points). We express white box with {*}, Proof (1):
and black box, [{*}]. So, q =[[ PlE l, P(P)= qp ; (La) If xE C (P), then NB(P)=NB(x) eX, from definition
p B
q" =[[u lEJ P(u)= q ll' 5, we have xE X" so U C(P)s;;;X'o
Let q",q E Q, a binary relation B Q over Q will in­
(1. b) If qE X" for any none empty subset NB(q) s;;;X,
p qE C(q),C (q) S;;; U{C(p) 1 pE U , NB(p) e X}
duce quotient structure, it is defined by binary relation
so q E U {C(P)I p E u, NB(P) S;;; X} and thus
over V:
X .s;;;UC(p).
(6)
Proof (2):
where, iE [uh ' kE [ ph , quotient structure is de­
'
(2. a) VPE X', pE C(p), so x s;;; UC(p).
fined by equation 7.
(2.b) Let qE C(p) , then NB(P)=NB(q), from definition 5,
NB(qp ) = NB([[P hB]) = {fluhB 11 ([[p lEB l,[[u hB]) E B} (7)
qE X· , for q is an arbitrary set in C(P),
= {P(u) I(p, U) E B} = {P(u) IUE NB(p)}
so C(p) S;;; x' , and thus UC(p) S;;; x' .
C. Binary Knowledge Representation System (B-KRS) Attention Please: 1. The points with empty neigh­
borhoods were not included in upper and lower ap­
Definition 5: Binary Knowledge Base and B-KRS
proximation of any subset X. 2. The topological ap­
Let B-K=(U,B) be a binary knowledge base, U is
proximation in binary relation has different meaning
universe, B is a family of binary relation.
compared with that in RS.
Let B-KRS=(U,B,Q,f,c), where U is the universe, B
From definition 6 and 7, it's easy to get definition8.
a family of binary relation, Q the quotient set./is nam­
ing function or information function, and C, the set of
concept. In this paper, / is originally act on
Definition 8: Center Set definition for RS can also be observed from Fig1 that all the vertical
coordination of these "crosses" in each column form
If B is equivalent relation E, we have: the binary neighborhood of the corresponding point in
the horizontal axis. For example, for point 1 in hori­
X.={xIC(x)=[ xl£ <:;;; X} =U{ [ xh I[ xl£ <:;;; X} ( 12) zontal axis, its binary neighborhood includes all the
X' ={xlC(X)=[X]Enx;t:¢} vertical coordination of the "crosses" in this column,
( 13 ) such as 1,2 and 3 , we circle and mark it by Ns(1). All
=U{[x]EI[x]EEPEB and [x]Enx;t:¢}
circles in Fig1 form the binary neighborhood system.
Definition 8 is as same as Prof. Pawlak's two defini­ Binary relation B realizes the mapping from a point
tions in RS, it is obviously that approximation in RS is to a binary neighborhood and from universe to a binary
a special case for that of Binary Grc. Two definitions UU
neighborhood system. B:p � Ns(P); U � 2 .
of approximations in RS can be united by Center Set.
Fig 1 directly describe we can use binary neighbor­
III. EXAMPLES FOR BINARY GRC hood system to study binary relation.
In this section, 5 examples will be given to illustrate E. Quotient Set and Quotient Structure
all the basic definitions in binary GrC, especially for
center set-based approximation definitions. Eg2: Let U={1,2,3,4,5},B<:;;;UxU,
B={(1,l), (1,2), (1,3), (2,1), (2,2), (2,3), (3,3), (3,4),
A. Binary Relation and Binary Neighborhood System
(3,5), (4,3), (4,4), (4,5), (5,3), (5,4), (5,5)}
Please fmd its quotient set and quotient structure.
Egl: Let U={l,2,3,4,5},B<:;;;UxU :
(1) Find quotient set.
B={(1,l), (1,2), (1,3), (2,1), (2,2), (2,3), (3,3), (3,4),
From Eg1, it can be seen:
(3,5), (4,3), (4,4), (4,5), (5,3), (5,4), (5,5)}
Ns(1)= Ns(2)={1,2,3}; Ns(3)= Ns(4)= Ns(5)={3,4,5}
Please find neighborhood system generated by B.
According to defmition 3, the derived partition is:
lC£B ={{l,2},{3,4,5}}, and the Center Set:

C(1)=C(2)={1,2}; C(3)=C(4)=C(5)={3,4,5}
Let[ {1,2}]= q" [{3,4,5}]}=q2 ,then quotient set
Q={q" q2}
For a natural mapping P: U --t Q
P (1)= P (2)= q" P (3)= P (4)= P (5)= q2
(2) Find the quotient structure.
From definition 4
3 4 5U
NB Q(q)={P(U)IUE NB(p) U,PE U} , qE Q ={ qb q2}.
Fig 1 BNS for a given binary relation
q=a, p={1,2} Ns(1)=Ns(2)={l,2,3}
From definition 2:
u =l, IE Ns(l) P(1)= q, ;
NB(p)={uE UI(p,U)E B}
u =2, 2E Ns(l) P(2)= q,;
Whenp=l, NB(I)={uE UI(I,u)E B}
u =3, 3E Ns(l) P(3)= q2;
According to B={(l,l), (1,2), (1,3), (2,1), (2,2),
u =4, 4e Ns(1) P(4)= q2
(2,3), (3,3), (3,4), (3,5), (4,3), (4,4), (4,5), (5,3), (5,4),
(5,5)} u =5, 5e Ns(l) P(5)= q2
(I,U)E B, when u=l, u=2, and u=3 So, NB Q(ql)={ql,qJ.
So we have: For the same reason: NB Q(q2)={qJ, So, the quo­
Ns(1)={1,2,3};
For the same reason: tient structure is {( q" q,),( q" q2),( q2, q2)}'
Ns(2)={1,2,3};
C. Binary Knowledge Representation System
Ns(3)={3,4,5};
Ns(4)={3,4,5}; Naming a meaningful name c for each point qp in Q,
Ns(5)={3,4,5}. this step is realized by map: j(q)=c. f is naming func­
And thus, neighborhood system is as follows: tion and C={c}, the set of concept. In this paper f is
NBS={ Ns(1), Ns(2), Ns(3), Ns(4), Ns(5)} originally defmed on the point in quotient set, howev­
Fig 1 can be got directly from binary relation B, and er,fo P: U --t C can also map the elements of U into C.
the "crosses" in the lattice point represent B over U. It
 Eg3: Let U={ 1,2,3,4,5}, B c:;;; Ux U , D. Approximations in Binary Granular Computing
B={(1,I), (1,2), (1,3), (2,1), (2,2), (2,3), (3,3), Just as mentioned above, Prof. Pawlak defined two
(3,4), (3,5), (4,3), (4,4), (4,5), (5,3), (5,4), (5,5)} equivalent knowledge approximations. In binary gra­
Please build binary knowledge representation sys­ nular computing, the approximation definitions from
tem. view of set theory can't get satisfied result especially
Attention please: under binary relation, each ele­ ror partial order relation[81, here an example will be
ments in V may be included in different neighborhood, given to illustrate this idea.
for example, "3" in the universe belongs to Ns(1), Eg4: Given a binary relation "less than «)" on real
Ns(2), Ns(3), Ns(4), Ns(5) at the same time. This is line (-00,+00) .
quite different from that under equivalent relation in
RS. However, each element just belongs to one center Please find the upper and lower approximations for
X=(100. 5, 199.85)
set.
According to Eg2, we have: By equation 1.
NB(p)={UE U l(p,U)E B}
P (1)= P (2)= q"
P (3)= P (4)= P (5)= q2 In this example B is "<", the neighborhood of an ar­
Let f(q,)=a; j(q2)=b bitrary point p in V is as follows.
NAp)={UE UI(p,U)E "<" }
By naming function:
Usually, such as, in Calulus calls, we re-write the
f pel) = f P(2) = a;
0 0

equations above as follows:

f oP (3) = f oP (4) = f oP (5) = b NAp)={UE Ulp<u} = ( p,oo ) (14)
Then quotient set Q={q" q2} turns to knowledge set Now, for X=(100. 5, 199.85), the low approximation
Qk={a, b} . is: Recall from definition 6
This will result Table I. It has abundant information. X.={pE UINB(p)"# ¢,NB(p) c:;;; X}
In Table I, Es is equivalent relation generated by B on From equation (14), N« p) is a half line, it can not
V. It generates derived partition: be subset of finite interval, so X.=¢ .
lCEB ={{l,2},{3,4,5}}. Next, we shall find the upper approximation. To be
B-KRS=(U,B,Q.f,c) can't totally reflect B-K=(U,B) specific, Let p = 51.
NA5l)=(5 1,+00)
because B and B Q are not one to one correspondence.
(51,+00) n (100.5,199.85) "# ¢
Table I has the same form with Knowledge represen­
·
tation system in RS, however, the two tables are totally SO 51E X
different. The concept in the B-KRS has quotient struc­ Now, let us examine the general case. Let p be arbi­
trary point p E (-00, +00) .
ture
Now, let us ask what kind of p will satisfy the condi­
NBQ(a)={a,b} ; NBQ(b)={b}
tion:
In RST, a, b totally has no relation. ( p,oo )nx;t: q),
TALBE I B-KRS Obviously all the points that are less than 199.85
will have non-empty intersection with X.
· ·
V Es Observe that 199.85 is not in the X , The X is
open right half line.
·
1 a X = (-00,199.85)
This kind of approximation is not interesting. Be­
2 a cause for any interval of the following form
( p,199.85) for all p < 199.85, will have the
- ex:

3 b
same upper approximation and lower approximation:
·
4 b X = (-00,199.85)
X.=¢
5 b This point based/topological approximations, called
closure and interior.
Observe that equivalence classes in RS are called
elementary sets. Hence generalized equivalence classes
in Generalized RS, such as neighborhoods in this paper,
are often also called elementary sets. The knowledge
ACKNOWLEDGEMENT
represented by such elementary sets have been called
elementary knowledge. This work was partially supported by National Natu­
We have called the knowledge represented by de­ ral Science Foundation of China (60975032), Natural
rived partition the central knowledge; note that the Science Foundation for Young Scientists of Shanxi
equivalence class in the derived partition has been Province (2010021016-1).
called center set.
Observe that such point based approximations have REFERENCES:

no interpretations in elementary knowledge, but has

[1] Z. Pawlak. Rough Sets, Theoretical Aspects of Reason­
interpretations in central knowledge. ing about Data. Kluwer Academic Publishers, Dor­
EgS: Three examples for binary approximation. drecht, 1991
(1) Let K=(U,B), U= {1,2,3,4,5 },
[2] T.Y.Lin. "Neighborhood Systems and Approximation
B: Ns(l)={l,2,3}; Ns (2)={1,2,3}; Ns (3)={3,4};
in Database and Knowledge Base Systems". Proceed­
Ns (4)={3,4,5}; Ns (5)={2,3,4,5}, ings of the Fourth International Symposium on Metho­
Please find upper and lower approximation for dologies of Intelligent Systems, Poster Session, Octo­
X={2,3,4} ber 12-15, 1989, pp75-86
According to definition 7:
[3] Lin T Y. Liau C J. Granular Computing and Rough
only N B (3) {3, 4 };.o f/J, N s (3) � X { 2, 3, 4 } and C (3)=3,
= =
Sets. The Data Mining and Knowledge Discovery
so X. (3)={3} Handbook. 2005: 535-561
Ns ( p) ;.of/J and Ns ( p) n X ;.of/J l � p � 5 W.Zhu, "Generalized rough sets based on relations".
[4]
So X' (3)={1,2,3,4,5} Information Sciences,2007,177(22), pp4997-5011
(2) Let K=( U,B), U={l,2,3,4,5,6}, [ 5] L.A. Zadeh. "Some reflections on soft computing, gra­
B: Ns(l)={1,2}; Ns(2)={1,2,3}; Ns(3)=9; nular computing and their roles in the conception, de­
Ns (4)={2,3,4}; Ns (5)={2,3,4,5}; Ns (6)=9 ' sign and utilization of information/intelligent systems",
Soft Computing, 1998(2): 23-25.
Please fmd upper and lower approximation for
X={2,3,4} [6] T.Y.Lin. "Granular Computing on Binary Relations I:
According to definition 7, we have: Data Mining and Neighborhood Systems","Granular
X. {4}; X
·
=
{I, 2, 4, 5}
=
Computing on Binary Relations II: Rough Set Repre­
Attention please: NB (3) Ns (6) 9 "3"and "6" are
= = sentations and Belief Functions," In Rough Sets In
not included inX. and X'. Knowledge Discovery, A. Skowron and L. Polkowski
(3) Let K =( U,B), U={1,2,3,4,5}, (eds), Physica -Verlag, 1998, pp 107-140.
B: Ns(l)={1,2}; Ns(2)={1,2}; Ns(3)={3,4};Ns
[ 7] T.Y.Lin. "Granular Computing: Practices, Theories,
(4)={5}; Ns (5)={2,3,4}. and Future Directions". Encyclopedia of Complexity
Please fmd upper and lower approximation for and Systems Science. 2009: 4339-4355
X={2,3,4}
· [ 8] T.Y.Lin, R.Barot, S.Tsumoto."Some Remarks on the
Obviously X. {3,5} ; X {1,2,3,5}
= =
Concept of Approximations from the View of Know­
Attention Please: "4" belongs toX, however it was ledge Engineering". The International Journal of Cog­
' nitive Informatics and Natural Intelligence 2010,4(2),
not included inX. andX , because Ns (4) n X =9. This
pp I- II
is a little different with commonsense.

IV. CONCLUSION

Center Set is the key concept in this paper, based on

which, the approximations for binary granular compu­
ting is studied in detail from view of knowledge engi­
neering. Binary representation system is also built to
express binary knowledge base. Once the Binary
knowledge representation system is built, knowledge
dependency and knowledge reduction can be done, and
it can be connected with gragh theory. This will help
for the study for social network computing. Further
study is still going on.