- Email: [email protected]

189

An algorithm for computing the transitive closure of a fuzzy similarity matrix Fu Guoyao Nanjing Gas Turbine Research Institute, Nanfing, China Received March 1991 Revised October 1991 Abstract: Up to now, many algorithms for computing the transitive closure of a fuzzy similarity matrix have been proposed. This paper presents a new algorithm, which possesses all the advantages of these previous algorithms. Moreover, its complexityis smaller.

operations of matrices, only simple ^ or v operations. So computation would be more convenient, but its complexity is higher too, it is O(n4). The present paper is another search in this field; the complexity of the algorithm here is O(~ n 3) and contains all the advantages of the above algorithms. First we introduce some definitions and notations.

Keywords: Algorithm; fuzzy classification analysis; fuzzy equivalence matrix; fuzzysimilaritymatrix; complexity.

Definition 1. A fuzzy reflexive and symmetrical matrix is called similarity matrix.

In the process of classification analysis applying fuzzy equivalence relations, the computation of the transitive closure e(R) of a similarity matrix R is always necessary. The similarity matrix is a matrix representation of fuzzy reflexive and symmetrical relations,

Definition 2. A transitive if

e(R) = R U R 2 U . . . U R "

(1)

where n is the order of the fuzzy matrix R. The amount of work done for (1) is enormous: the complexity is O(nS). In order to accelerate and simplify the computing, a lot of effort has been devoted to the discovery of new algorithms. Kandel and Yelowitz [3] and Dunn [1] are initial works. According to e ( R ) = R " [2], a square algorithm has been proposed: R---.~R2---,...---~R2k=e(R),

matrix

aii >i min(aik, ark) = aik A aik

A=(a~j)

is

called (2)

holds for any aij, aik, ajk e A. Definition 3. A transitive and similarity matrix is called equivalence matrix.

Definition 4. We say matrix B = (bo) includes matrix A = ( a i j ) and denote it by A ~ B , if aij <~bij for every (i,/). Definition 5. The equivalence matrix B is called equivalence closure of similarity matrix A if B includes A and is included by any equivalence matrix which includes matrix A.

2 k - l < n < ~ 2 k.

Its complexity is O(n 3 log n). Spreading the Warshall algorithm, [4] proposed an algorithm whose complexity is O(2n3), The algorithm proposed in [7] only needs one group of n × n working elements of a computer, while the above algorithms need 2 or 3 groups of n x n elements, but its complexity is (p + 1)n 3. In the algorithm of [6] there are no multiplicative

Obviously the transitive closure of a similarity matrix is just its equivalence closure. For simplicity 'equivalence closure' is denoted by EC, and the n-vector consisting of the i-th column of A = (a0) by ai. Suppose £2, is the set of all n × n fuzzy similarity matrices and 4 , the set of all n x n fuzzy equivalence matrices. It is easy to verify the following propositions.

Correspondence to: Dr. Fu Guoyao, Nanjing Gas Turbine Research Institute, Nanjing 210037, China.

Proposition 1. Let A e cb,. Exchanging the s-th column of A with the t-th column of A and the

0165-0114/92[$05.00 © 1992--Elsevier Science Publishers B.V. All rights reserved

190

Fu Guoyao / Computing the transitive closure o f a f u z z y similarity matrix

s-th row with the t-th row, the resulting matrix is still equivalent.

The truth of the case j g : s can be proved similarly as above, and is omitted.

Proposition 2. Suppose A e g2n and B is the equivalence closure o f A. Exchanging the s-th column of A with the t-th column o f A and the s-th row with the t-th row, the matrix A ' is obtained. Similarly, from B, B' is obtained. Then B' is the EC o f A'.

Proposition 5. f f A = (aq) ~ q~n, then for any column o f A , as = (als, a2~. . . . , a m ) T, there must exist x ~ [0, 1] and k 4=s, such that au=aikAX

(l<~i<-n,i=/:s).

Proof. Let aks = max~,s a~ and set x = a~. We have a~>taikAaks and a ~ / > a ~ . By using Proposition 3 we know it is impossible that

Proposition 3. I f A = (aij) ~ ~n, then for any aij, aik, ajk either they are equal or two o f them are equal and the third is larger.

ai~ > aik. S o

Proof. See [5].

a~ = aik A aks = aik ^ x.

Proposition 4. Assume that

Hence the result.

A = (air) ~ ~ . Changing the element ai~ o f the s-th column and asi o f the s-th row into t

t

asi =

t

a~ = air A X,

ass = 1,

l < ~ i , j < - n , i : / : s , x ¢ [ O , 1].

(3)

¢

¢

Propositions 4 and 5 show that if A = (aij) e q~n and B ~ qbn such that the left-upper submatrix of B is A, then the (n + 1)-th column of matrix B must be On+l = (a 6 AX, a2r A X , . . . ,

ant AX, 1)"

but keeping the rest, aii = aq, then A ' = (a~j) ~ ~n.

where 1 ~

Proof. According to the definition of a[r it is obvious that A ' e gn. Hence to verify that the elements of A ' meet the case (2) is sufficient. t Let ] = s in (3). Consider each element apq of A'. We will prove it considering three special cases. Case 1: p, q :/: s. If k 4= s then

Proposition 6. Let A,+I e f2n+l and its left-upper n-order submatrix is An. Bn is the equivalence closure o f An, and its i-th column is

t

t

b i = ( b l i , b2i . . . .

, bni) T.

I f there exist x* ~ [0, 1] and j, such that bn+l = (blj A X*, bzj A X* . . . . .

bnr A X*) T

t

apq >i apk A aqk

is the closure o f

follows from the equivalence of A: aeq >i apk ^ aqk and the definition of a[r. If k = s then

(al,n+l,

a 2 , n + l , • . . , an,n+l),

then

t

apq = apq ~ aps A aqs t

t

>I (am A X) ^ (aqs A X) = ank ^ aqk. Case 2: One of p, q is s, for example q = s, ' = aps. ' If k 4 : s , then i.e. apq

bn+i

is the equivalence closure o f An +1.

t

aps = aps A x ~ (apk A ask) A X = af,k ^ (ask ^ x) = apk ^ ask. t

t

Proof. Assume that Cn+ 1 is the equivalence closure of An+l and Cn is the left-upper n-order submatrix of Cn+l. By the definition of closure and Proposition 4,

If k = s, then t

' >~ aps ~ aps A r = aps ^

t

t

1 = aps ^ ass a~ = apk A aks. t

t

r

Case 3: p = q = s. In this case, and formula (2) holds clearly.

t

apq =

t

ass = 1

B.+1 _DCn+l __~A.+l, B.~_C.D_A..

191

Fu Guoyao / Computing the transitive closure of a fuzzy similarity matrix

However, B. is the equivalence closure of A . , so

B.=_C.,

a13 = x2. Now let us compute the EC of A3=

("' ?) aT

Hence

B.-C..

where a 3 = (al3, a23)T. Since the last column of B 2 includes a3, s e t

The rest is trivial by applying Propositions 4 and 5.

b3 = b(22) A X; = (X~' A X2, 1 A X~)T ----(X2,* X~')v. It is easy to prove that the EC of A3 is

Proposition 6 shows that after B . = (bl,. • •, b.), the EC of A., has been obtained we choose by Propositions 5 and 6. If a z 3 - X 2 , then b3 = b~z) ^ x~ may be (x~, x~) T. No matter which is b3, the last column of B3, b(33I = ( b T, 1)T, must

X* = ak,n+ 1 = max ai,n+ 1 l<-i~n

and look for the closure of a.+l in

include any column

(bq ^ x* . . . . .

X 1 :

b.j ^ x*, 1),

*

max al]

( a l p azj, a3i) ( j > 3), b e c a u s e

and

* = max a o.

X 2

2<<-j<~n

i = 1,2 3~j~n

where bj = (blj . . . . .

bnj)

6 (bj ] bj D (al,.+,, • • • , a.,.+0} then we will get B.+I, the EC of A.+~. To consider

{bj I b, ~

(al,n+ 1. .

. . .

a.,.+l)}

is not necessary because

(bii ^ x* . . . . .

b,q A X*, 1)

Step 3. Looking for the maximal element x~ in the last n - k columns of the first k rows of An, exc_hange column containing x~, with the (k + 1)-th column and the corresponding row with the (k + 1)-th row. Suppose x~ is just in (k + 1)-th column. Now look for Bk+l, the EC of (Bk ak+l~ A k + l = a~+l 1 /' ak+l = ( a l k + l , • • • , akk+l) T.

obtained from these bi can not include a. +1. According to the above propositions we introduce the following algorithm for computing B., the EC of A . = (aq) E .(-2n.

By induction we see that the last column of Bk, b~k) ~ ak+l. Set bk+l = b(k~) h X~,, then

Step 1. Suppose that To consider the other column b}k)= ch(k) h(k) , (~'lj , t"2j

a12 = max a 0 = x~'; 2~j<-n

otherwise we exchange columns and corresponding order rows so that the maximal element of the first row is al2. Clearly, B2, the EC of me=

(1 a12

a12] 1 /

=

(1 x~'

x~'] 1/

,

is just A 2. Step 2. Looking for the maximal element x~ in the last n - 2 columns of the first two rows of A., exchange the column which contains the maximum x~ with the third column and the corresponding row with the third row. Suppose

• • • ,

b~k))T (j < k)

of Bk is unnecessary, because it is impossible that

b (k) ^ x~, D b} k) ^ x~, = ak+l. This can be proved as follows: If i < j, notice j < k. By the generation of Bk it can be obtained that b}f ) = x * AX*+1 ^ ' ' "

AXT-1

> ~(k) t. ik

^x*+,

^ • • • ^xj_,

^x7

^.-.

If i = j , obviously 1 = b~k) > ~t.(k) ik •

^ x

_l.

Fu Guoyao / Computingthe transitive closure of a fuzzy similarity matrix

192

If i >j, let x~ = am,k+1. According to the note after Proposition 6 there must hold

b~)>am,k+l =x~ for the considered b}k). (Otherwise b ~ / < am,k+1, b} k) ~b ak+l and according to the note b}~) need not be considered.) When i ~

b}]" = b}i*' >- vhgk' i m = b~) > and hence

When i > m, because x7 is the m a x i m u m of the last n - l columns of the first l rows of A, then Xm,* Xm+l,* • • •, X*-I are all greater than am.k+~ = x~, and thus Xm+l*

^

" " " ^X?-l>X~¢.

In sum we have b~k) A XT, ~ >-,,ikh(k) A X~ for the considered b} k), i.e. b~') ^ xT, =_ b} ~) ^ xk.

We can yet see that b(k+O i,k+,=X* A X T + l A ' ' ' A X T , > a i j

(]>k+l)

t,(k+i) of the last column ~,k+l for element ,,i.k+l Bk+~. This is due to the fact that max

a~j and

h(k+l) uk+l,k+~

=

of

1,

i=1,2 ..... l

I

so that the last column h(k+~) ~'k+l of Bk+~ includes any column (alj, azj . . . . .

ak+Lj)

(j > k + 1).

Step 4. Proceed with step 3 until k = n - 1, then exchange columns and rows which have been exchanged in the above process to their original place, and the result, the EC of A , , is obtained. In practice the exchanging can be omitted. The following example will make this clearer.

( 03)1

Example. Find the EC of similar matrix 1

A=

0.1 0.8 0.5 0.3

0.1 1 0.1 0.2 0.4

0.8 0.1 1 0.3 0.1

1 0.8 0.5 0.1 0.3

0.8 1 0.1 0.3 0.1

0.1 0.1 1 0.2 0.4

0.5 0.3 0.2 1 0.6

0.3) 0.1 04 . ~]6

0.5 0.2 0.4 0.3 0.1 1 0.6 0.6

Solution: According to the above algorithm we

0.8 1 0.3 0.1 0.1

0.5 0.3 1 0.2 0.6

0.1 0.1 0.2 1 0.4

0.3) 0.1 06 , ~]4

and exchanging the 5-th column (row) with the 4-th column (row) gives

1 0.8 0.5 0.3 0.1

Hence the result.

x~ =

1 0.8 0.1 0.5 0.3

Then exchanging the 4-th column (row) with the 3-rd column (row) yields

b~~) ^ xT, = xT, 1> b~) ^ x L

bqC)=b(ik)=h(k) Ax* q

look for the maximal elements and exchange columns and rows. By exchanging the 3-rd column (row) with the 2-nd column (row), we get

0.8 1 0.3 0.1 0.1

0.5 0.3 1 0.6 0.2

0.3 0.1 0.6 1 0.4

0.1) 0.1 0.2 = A . 0.4 1

Then compute the EC step by step: 1 0.8 0.5 0.3 0.1

0.8 0.5 1 0.3 0.3 1 0.1 0.6 0.1 0.2

0.3 0.1 0.6 1 0.4

0.1~

1 0.8 0.5 0.3 0.1

0.8 1 0.5 0.1 0.1

0.5 0.5 1 0.6 0.2

0.3 0.1 0.6 1 0.4

0.1 0.1 0.2 0.4 1

1 0.8 ---, 0.5 0.5 0.1

0.8 1 0.5 0.5 0.1

0.5 0.5 1 0.6 0.2

0.5 0.5 0.6 1 0.4

0.1 0.1 0.2 0.4 1

1 0.8 0.5 10.5 0.4

0.8 1 0.5 0.5 0.4

0.5 0.5 1 0.6 0.4

0.5 0.5 0.6 1 0.4

0.4 / 0.4 04 ~14

l l

0.1

0.2 0.4 1

Restoring the original sequence of columns and

Fu Guoyao / Computing the transitive closure of a fuzzy similarity matrix

and fix that too, getting

rows we get 1 0.4 0.8 0.5 0.5

0.4 1 0.4 0.4 0.4

193

0.8 0.4 1 0.5 0.5

0.5 0.4 0.5 1 0.6

0.5) 0.4 0.5 0.6

1 0.1

1

which is just B, the E C of A. Obviously the exchanging can be omitted provided that we fix the elements of B~ obtained just now. For example, when i = 1 choose a13 = x ~ = 0.8. Now

0.8

0.5

0.8

0.1 1 0.1

0.1 1

0.2 0.5

0.5} 0.4 0.5

0.5

0.2

0.5

1

0.6

0.5

0.4

0.5

0.6

1

Finally choose x~ = max(a,2, a32, a42, a52) = max(0.1, 0.1, 0.2, 0.4) = 0.4. Using b (4) = (0.5, 0.5, 0.6, 1) T

?t

obtained just now, replace

Fixing a11, al3, a31, a33, we obtain

)

1

0.1

0.8

0.5

0.3 /

0.1

1

0.1

0.2

0.4

0.8

0.1

1

0.5 0.3

0.2 0.4

0.3 0.1

0.3 1 0.6

0.1 0.6 1

We look for the maximal element in remaining three columns of the two rows that contain fixtures. Obviously, x~ = a14 = 0.5. Regard the column which contains 0.5 and consists of elements of the present two rows as a3 = (a14 , a34) T. Replace a3 with (0.8, 1) T ^ x~ = (0.5, 0.5) and fix that too, obtaining 1 0.1 0.8 0.5 0.3) 0.1 1 0.1 0.2 0.4 0.8 0.1 1 0.5 0.1 • 0.5 0.2 0.5 1 0.6 0.3 0.4 0.1 0.6 1 Looking for the maximal element x~ in the remaining two columns of the three rows which contain fixtures again, this time x3 =a45 =0.6. Regard the column containing 0.6 as a4 = (a,5, a35, a45) T. Using b~3) = (0.5, 0.5, 1) v

a5 = (al2, a32, a42, a52)

with

(lO40O0/1

b5 = b~44)^ x2 = (0.4, 0.4, 0.4, 0.4) T

Thus B, the EC of A, is obtained as

n =

0.4 0.8 0.5 0.5

b4 = b(33) A x~' = (0.5, 0.5, 0.6) T

0.4 1 0.5 0.5

0.4 0.5 1 0.6

0.4 0.5 0.6

In this algorithm the calculation consists of two sections for any Bi: looking for the maximum and computing bi. The operators adopted in any section are all strictly v or strictly ^ , not mixed operators. Moreover, the operative object of v or ^ is a regular block of elements of the matrix, so that using this algorithm would be easier, especially in manual computation. Finally, we explain the complexity of the algorithm simply. In calculations looking for the maximum, the frequency of v needed amounts to ((n - 1) - 1) + (2(n - 2) - 1) +... :

in3

--

+ ( ( n - 1)(n - (n - 1 ) ) - 1) i n - - (n - 1).

In calculations of bi the frequency of ^ needed amounts to 1 + 2+...

obtained just now, replace a4 with

1 0.4 0.4 0.4

+ (n-2)

= l(n - 1)(n-2).

Therefore the complexity of this algorithm is ln3

194

Fu Guoyao / Computing the transitive closure of a fuzzy similarity matrix

References [1] J.C. Dunn, A graph-theoretic analysis of pattern classification via Tamura's fuzzy relation, 1EEE Trans. Systems Man Cybernet. 4 (1974) 310-313. [2] J.C. Dunn, Some recent investigations of a new fuzzy partitioning algorithm and its application to pattern classification problems, J. Cybernet. 4 (1974) 1-15. [3] A. Kandel and L. Yelowitz, Fuzzy chains, IEEE Trans. Systems Man Cybernet. 4 (1974) 472-475.

[4] Lou Shibo and Tong Zengxiang, An algorithm for finding the transitive closure of a fuzzy matrix, J. Shanghai Inst. Railway Technology 2(1) (1981) 37-45. [5] H.B. Potoczny, On similarity relations in fuzzy relational databases, Fuzzy Sets and Systems 12(3) (1984) 231-235. [6] Xiao Xian, An algorithm for calculating fuzzy transitive closure, Fuzzy Mathematics 5(4) (1985) 71-73. [7] Zhao Zhen, An improved algorithm for fuzzy classificatory analysis, J. Lanzhou Univ. 19(3) (1983) 160-163.