Sự lựa chọn đa tiêu chuẩn

Phụ lục I.5

SỰ LỰA CHỌN ĐA TIÊU CHUẨN

I - KHOẢNG CÁCH

Cho một ánh xạ E ? = E x E → R(+), E x E = 1x, y). Thế thì với mọi (x, y), ta có các định nghĩa sau về khoảng cách Ultra và Infra :

Ví dụ

Cho hệ quy chiếu

E = la, b, c, d, e, f, g)

và các tập hợp A, B, C, E, F có các giá trị sau :

B 0.3 0,8 0,1 1

1

0,7

1 0,8 0,3 0,7

0

0,1 1 0,3

0,1 0,8 0,7 0

0 0,7 0,8 0

1

0 0,3 0,5 0,1 0,1 0,5 0,8

Tức là A(a) = 0,1, B(c) = 0, F(g) = 0,8...

Lấy khoảng cách Hamming tương đối ta thu được quan hệ mờ sau

0,25 0,34 0,44 0,28 0,34

0,31 0,32 0,42 0,40

m 0,25 0

0,61 0,14 0,54

c 0,34 0,31 0

0,64 0,27

a' 0,44 0,32 0,61 0

E 0,28 0,42 0,14 0,64 0 0,54

F 0,34 0,40 0,54 0,27 0,54 0

X, Y = A, B, C, D, E, F

Đây là một quan hệ bất đồng tính (có tính phản phản xạ và đối xứng). Cái đóng bắc cầu Min Max của nó biến quan hệ bất đồng tính thành một quan hệ bất tương đương (có tính chất phản phản xạ, đối xứng và bắc cầu Min Max) như sau :

R

F .1 0,32      0,32           0,32               0,27                   0,32                         0

II - TÔN TI

ĐỊNH NGHĨA

Cho một hệ quy chiếu E và gọi P(E) là tập hợp các tập con của E. Thế thì mọi tập con bình thường H C P(E) gọi là một tôn li trên E, nếu H thỏa mãn các điều kiện sau :

1. Với mọi A, Card A = 1, nếu A E E thì A E H,

2. E E H,

3. Với mọi B, C C H, nếu B N C # Ø, thì hoặc B C C hoặc C C B.

Ví dụ

Cho

E = {a, b, c, d, e, fl.

Thế thì

H = {a, b, c, d, e, f, {a,b), {d,el, {a,b,c), {a,b,c,d,e), E} C P(E) là một tôn ti. Tôn ti chỉ số hóa

Một tôn ti H xác định trên E gọi là được chỉ số hóa nếu có một ánh xạ p : H → R(t), tức là p(H) E R(t).

sao mà

1. Nếu A E H và Card A = 1 thì q(A) = 0,

2. Với mọi B, C C H và B > C, B # C thì q(B) > p(C).

Ví dụ

Trên tập hợp H nói trên, ta hãy thực hiện một ánh xạ, biểu diễn bằng "cây" như sau

Dễ thấy rằng tôn ti H với ánh xạ p đã trở thành một tôn ti chỉ số hóa. Có thể chứng tỏ được rằng tương ứng với một tôn ti chỉ số hóa là một khoảng cách infra, và ngược lại.

Để minh họa, ta hãy trở lại khoảng cách Ý, nhưng chỉ lấy từ A đến D cho đơn giản >

        0           0,28                0,32
0,25

Các tập hợp các điểm có khoảng cách tương đối với nhau d(X, Y) = 0 tất nhiên là {A), {B), {C) và (D).

Tập hợp các điểm có khoảng cách tương đối với nhau d(X, Y) ≤ 0,25 tất nhiên là {A,B}.

Tập hợp các điểm có khoảng cách tương đối với nhau d(X, Y) ≤ 0,28 tất nhiên là {A, B, C}.

Cuối cùng tập hợp các điểm có khoảng cách tương đối với nhau d(X, y) $ 0,32 tất nhiên là {A, B, c, D}, Và tập hợp các tập hợp

H = {{A}, {B}, {C}, {D}, {A,B}, {A,B,C}, {A,B,C,D}}

sẽ tạo thành một tôn ti được chỉ số hóa như sau

Bây giờ cho một quan hệ tương đương mờ /2, ta có thể từ đó dựng lên một tôn ti bằng cách phân tích.

Ví dụ cho quan hệ tương sau

Tiếp theo, bằng cách phân tích thông thường, ta có các quan hệ thông thường sau

v.v...

\«!D} \*{B}\»{CỊ

II - TIÊU CHUẨN

Một trong những bài toán để lập quyết định là bài toán về tiêu chuẩn. Định nghĩa về khái niệm tiêu chuẩn là khá trừu tượng.

ĐỊNH NGHĨA

Ta gọi tiêu chuẩn xác định trên một tập E là cái đã tạo nên một cấu trúc trên tập đó.

Ví dụ

Cho tập

E = [a, b, c}

Bây giờ ta hãy đưa vào E các bất đẳng thức sau

a < c < b.

Các bất đẳng thức này đã tạo trên tập E một cấu trúc thứ tự, tức là một tiêu chuẩn (tiêu chuẩn thứ tự I). ỉ

Tiêu chuẩn này được biểu diễn bằng đổ thị như sau :

Với đổ thị này, ta đã trang bị cho tập E một cấu trúc nào đó, nghĩa là biến E thành một tiêu chuẩn nào đó. Và hãy làm rõ tiêu chuẩn này. Để đạt mục đích này, trước hết ta nhận xét rằng đồ thị này mô tả một quan hệ tiền thứ tự. Và theo lệ thường, sau khi xác định được các lớp tương đương trong quan hệ tiền thứ tự đó, chúng ta sẽ thu được một quan hệ thứ tự (mờ) có thể là toàn phần hay không toàn phần.

Theo định nghĩa, quan hệ thứ tự mờ này tạo nên một tiêu chuẩn trên tập E, được mồ tả bởi đồ thị giản đơn hóa sau

HỆ TIÊU CHUẨN

Trên một tập hợp E có thể có nhiều tiêu chuẩn khác nhau, ví dụ

E = {a, b, c}

6 a > c = b c > b — à

Như chúng ta thấy, các tiêu chuẩn có thể trái ngược nhau, mâu thuẫn nhau phần nào. Và bài toán hiện ra trước mắt là phải quyết định một sự dung hòa các mâu thuẫn, hay thỏa hiệp trong một chừng mực nào đó. Nhưng sự dung hòa này, thỏa hiệp này lại phụ thuộc vào chủ quan của người xem xét vấn đề, cân nhắc tính quan trọng của từng tiêu chuẩn một.

Điều này xảy ra hằng ngày trong cuộc sống. ^

SỰ CÂN NHẮC, ĐÁNH GIÁ CHỦ QUAN

Cho một tập E, và một hệ tiêu chuẩn T|, T2,..., In trên E. Người xem xét vấn đề - theo chủ quan của mình - có thể cân nhắc và cho tiêu chuẩn thứ i một giá trị nào đó Pì...

Nếu

H pì = 1

thì sự cân nhấc Pị gọi là chuẩn hóa.

Tóm lại, nói chung trong cuộc sống hàng ngày, chúng ta luôn luôn phải quyết định giữa những bài toán đa tiêu chuẩn.

Vấn đề là phải :

- Xếp các sự kiện thành những

NHÓM TƯƠNG ĐƯƠNG

với nhau, có thể dựa vào các

KHÁI NIỆM Khoảng CÁCH

khác nhau,

- Xét

QUAN HỆ MỜ

giữa các nhóm tương đương đó, trong đó có

BÀI TOÁN QUAN HỆ THỨ TỰ MỜ, BÀI TOÁN TÔN TI,

BÀI TOÁN TIÊU CHUẨN, BÀI TOÁN CÂN NHẮC.

- Đi xa hơn thì có

BÀI TOÁN NHÂN QUẢ...

IV - TÍCH HỢP NHIỀU TẬP MỜ THÀNH MỘT TẬP MỜ

Cho n tập mờ A1, A2,..., An, trên cùng một hệ quy chiếu E = {Xi}.

Kí hiệu các hàm thuộc là Ai (x;) = uj. Hãy tìm một tập mờ A, với A(xk) = ux, sao mà A làm tối thiểu lượng

E = Eo, é (A, Ai).

trong đó P ; là trọng số của một sự cân nhắc chủ quan nào đó, còn

2 (A, A,) = EV4, - 14)3,

là khoảng cách Euclide giữa A và A;.

Bài toán quy về cách tìm cực tiểu của hàm

Như đã biết, trong trường hợp này điều kiện cần để có cực tiểu là (phương pháp bình phương tối thiểu)

Ta suy ra ngay

i ì I

Từ đó, nếu chọn một sự cân nhắc chuẩn hóa, tức là với ^pi = 1, ta được ngay i nghiệm sau

Ví dụ

Cho

E = {a, b, c, d, e},

và theo một loại kinh nghiệm chủ quan nào đó ta chọn sự cân nhắc sau : Pị = 0,3, p2 = 0,1, Py = 0,5, p^ = 0,1.

Thế thì, theo công thức trên, ta được :

ụ(à) = 0,3(0,3) + 0,1(0,2) + 0,5(0,4) 4- 0,1(0) = 0,31, Tương tự như thế, ta được :

p(a) = 0,16, p{b) = 0,55, p(c) = 0,86, p(d) = 0,30, vậy

V - TÍCH HỢP NHIỀU ĐỒ THỊ THÀNH MỘT ĐỒ THỊ

Bài toán tích hợp n đồ thị thành một đổ thị được giải nếu ta đưa ra một khái niệm gọi là "khoảng cách lưỡng phần" như sau.

Cho một tập E hữu hạn và cho A, B c E. Thế thì lượng

gọi là khoảng cách lưỡng phần giữa các tập A và B của E.

Có thể chứng minh rằng khoảng cách này thỏa mãn các điều kiện của khái niệm khoảng cách

Ví dụ 1.

Trước hết, ta chọn một ví dụ về đồ thị bình thường M, N, P, cardE = 3, hữu hạn,

Hãy tìm một đồ thị R, sao mà

9(R) = p(M)k(R,M) + p(N)k(R,N) + p(P)k(R.P)

là tối thiểu, với một sự cân nhắc chuẩn hóa p(M), p(N), p(P) nào đó.

Để tìm đồ thị R, số khả năng rất lớn. Tuy nhiên để giản đơn bài toán, ta hãy chọn giả thiết là đồ thị phải tìm thuộc loại thứ tự toàn phần. Thành thử, ta hãy xem đồ thị R phải tìm là thuộc loại này, từ đó, ta có thể chọn 6 đồ thị có thứ tự toàn phần sau :

a b

1 1

1 0 1

DÌ a b C

b c

1 1

a 0 a 1 1 1

Tiếp theo, theo phương pháp bình phương tối thiểu, ta được

Tính các k (A, M), k (A, N)... ở vế phải

Ta có

từ đó :

K(A, M) = 1 - 3/8 = 5/8, K(A, N) = 1 - 319 = 213, K(A, P) = 1,- 218 = 3/4.

Tương tự như thế, ta được

Từ đó, phép nhân ma trận trên cho các kết quả sau :

q(A) = 0,9, q(B) = 0,58, q(C) = 0,61,

q(D) = 0,58, q(E) = 0,50, q(F) = 0,44.

Như thế,

Min {q(A),..., q(F)} = 0,44,

tương ứng với F.

Trở lại với quan hệ F, ta thấy rằng tương ứng với đồ thị này là quan hệ thứ tự c & b ^ a, tương ứng với sự cân nhấc cụ thể trên về các giá trị của p.

Tất nhiên, với một sự cân nhắc khác, ta lại có một kết quả khác. Một câu hỏi tự nhiên để ra : Làm thế nào để thu được một kết quả đích thực ?

Cần có một đội ngũ chuyên gia lành nghề ! Lý thuyết tập mờ chỉ cho những phương pháp về "phần cứng", xem kết quả là một biểu thức xác định về các cân nhắc. Ví dụ 2

Bây giờ chúng ta chuyển sang trường hợp đồ thị mờ.

Cho một số đồ thị mờ

Hãy tìm một đồ thị mờ R với

sao mà

t(R) = Min.

Dùng phương pháp bình phương tối thiểu, ta được nghiệm dưới dạng sau Nếu R = p(M)M + pCN)N +... + p(Q)Q thì t(R) = Min.

Ví dụ. Cho

E = (a, b, c}

a N a b c

a 0,3 1 0,2 a

0,3 0,2 1

b 0,7 0 b

0,8

0 0,9 0,7

c 0 0,4 1 c 0

1 0,8

P a b C

Q a b c

0,6 1 a 0,3 0,6 0,5 a 0

b 0,4 0,9 0,7 b

0,5 1 0,8

c 0,5 1 0

1 0

1

M

Giả sử ta chọn p(M) = 0,2, p(N) = 0,4, p(P) = 0,1, p(Q) = 0,3. Thế thì, theo phương pháp bình phương tối thiểu trên, ta được nghiệm : Ría, a) = 0,2(0,3) + 0,4(0,3) + 0,1(0) + 0,3(0,3) = 0,27, R(a, b) = 0,2(1) + 0,4 (0,2) + 0,1(0,6) + 0,3(0,6) = 0,52,... từ đó ta được

• R a c b

Ví dụ 3

Tìm một đồ thị thông thường R tích hợp được nhiều đồ thị mờ. Cũng bát đầu như trên nhưng ở đây chúng ta dùng khoảng cách lưỡng phân

K(R, M) = 1 - le = (R M M, Øle è (R U M, Ø), K(R, N) = 1 - le = (R n N, Øle ° (R U N, Ø))... Ví dụ.

Cho hai đồ thị mờ

và sự cân nhắc

píM) = 0,7, pỉN) = 0,3.

Bài tính đặt ra là tìm một đồ thị thông thường R, mang tính thứ tự toàn phần (để được đơn giản), tích hợp được tốt nhất các đồ thị M và N. Ta chọn đồ thị R đó trong số các đồ thị A, B, C, D, E, F ở ví dụ 1 trên. Ta tính

AN N M, Ø) = (0,3)2 + 0 + 0 + 1 + (0,2)2 + 0 + (0,92 + 1 + 0 = 2,94, (A UM, Ø) = 1 + 0 + (0,8)2 + 1 + 1 + (0,4) +1+1+1 = 6,80,

tức là

k (A, M) = 1 - (2,94/6,80) = 0,56

Tiếp theo, tương tự như thế, ta tính được

é (A n N, Ø) = 2,74, é° (A UN, Ø) = 7,45,

tức là

k (A, N) = 0,63.

q(A) = p(M) k (A, M) + p(N) k(A, N) = 0,7(0,56) + 0,3(0,63) = 0,58. Tương tự như thế, ta có

Thành thử

Min {q(A), q'B), q(C), q'D), q(E), q(F)) = 0,58.

Nhưng số này lại tương ứng với đồ thị A.

Cuối cùng như thế là

R = A,

và quan hệ thứ tự tương ứng là

a > 6 ≥ c.

Ta nói rằng đồ thị A đã tích hợp tốt nhất các đồ thị mờ M và N theo sự cân nhắc trên.

Còn có một số loại bài toán khác trong phạm vi tích hợp đồ thị, chẳng hạn là bài toán tích hợp nhiều đồ thị M, N,.., P thông thường bằng một đồ thị mờ R. Công thức vẫn tương tự như trên, tức là

VI - TÍCH HỢP NHIỀU QUAN HỆ THÀNH MỘT QUAN HỆ.

PHƯƠNG PHÁP JACQUET LAGRÈGE

Cho một hệ quy chiếu E = {a, b, c, d} và 7 tiêu chuẩn sau

Kí hiệu hệ tiêu chuẩn này là

C = 1C1, Cz, Cz, C4, O5, Cụm, Cnt.

trong đó a ≥ b, và tương tự như thế cho các tập con khác. Thành thử, theo định Tiếp theo, ta định nghĩa Cab là tập con của C chỉ chứa các phần tử nào của C nghĩa đó, ta được

Từ đó các tập con

91. 02, 03. C7. C5, 96,97

có thể viết dưới dạng sau

Bây giờ, ta hãy chọn một sự cân nhắc đối với tập c và biến nó thành một tập mờ như sau

sau đó, ta định nghĩa các tập mờ Cmt} sau, dùng sự cân nhắc trên

Ị

i = 1, 2, 3, 4, 5, 6, 7.

ta được Bảng

Trong Bảng trên, ờ cột cuối lượng Smn bằng

{^(cp + Cnin(C2) C(C7). •• + Cmn(C7>^3’6’ 3’6 = C<CP + C(C2) s™

Bây giờ, ta hãy viết ma trận Smn

Hoán vị a, b, c, d với nhau ta sẽ thu được 24 ma trận s khác nhau, chẳng hạn là ma trận

0,38 0,69 0,36

c    0,36          0,72               0,97                      1

Hai ma trận trên là tương ứng với hai thứ tự khác nhau :

Smn tương ứng với thứ tự a > b > c > d.

S'mn tương ứng với thứ tự a > 6 > d > c.

Các phần tử ma trận nằm bên trên đường chéo chính của mỗi ma trận đó gọi là các "hệ số dính từng phần tương ứng với thứ tự đang xét", còn các phần tử nằm bên dưới gọi là các "hệ số thải từng phần" Thế thì lượng

K(a, b, c, d) = E(Smn - SJ,

tổng lấy theo các hệ số dính và hệ số thải, các hệ số thứ nhất không đổi dấu, các hệ số thứ hai đổi dấu, gọi là "hệ số dính toàn bộ" tương ứng với thứ tự đang xét của a, b, c, d.

Như thế là ta có tất cả 24 hệ số dính tương ứng với 24 thứ tự khác nhau của a, b, c, d. Nói riêng, với thứ tự a > b > c > d, theo định nghĩa, ta được

Kết quả chung được ghi thành Bảng sau

Thứ tự toàn phần tốt nhất (tất nhiên theo sự cân nhắc được lựa chọn) là tương ứng với giá trị cao nhất của K. Đó là giá trị Max K = 2,11. Thứ tự tương ứng là a > c > d > b. Đó chính là kết quả tích hợp 7 tiêu chuẩn trên. Cũng có trường hợp xuất hiện nhiều nghiệm.

VU - TÍCH HỢP NHIỀU QUAN HỆ THÀNH MỘT

QUAN HỆ. PHƯƠNG PHÁP ELECTRE

Ta chuyển sang một phương pháp tích hợp nhiều quan hệ khác, gọi là phương pháp Electre. Cũng như trước, cho n tiêu chuẩn

Cp C2J..., cn,

được xác định bởi n quan hệ tiền thứ tự (với các tính chất phản xạ và bắc cầu)

^p ^2’ •'•’ ^n'

Bây giờ chúng ta hãy giả sử có một sự cân nhác pi và từ đó xây dựng được một quan hệ mờ R với hàm thành phần dạng

R(^. y) = 'LpỊRỷx, V),

Ẹpị = 1.

Do các quan hệ 7?i có tính phản ■xạ, quan hệ R cũng có tính chất đó.

Ví dụ

Cho ba tiêu chuẩn A, B, c tương ứng với ba quan hệ tiền thứ tự M, N, p sau

1 0 0 1 1 b ỉ

Tiếp theo, ta chọn sự cân nhắc p(M) = 0,3, p(N) = 0,6, p(P) = 0,1.

Từ đó, ta dựng được quan hệ mờ sau b d a e c

Đến đây có hai thao tác khác nhau, có liên quan đến các quan hệ đã cho M, N, p và quan hệ mờ R, kết quả của sự cân nhắc chủ quan trên.

THAO TÁC 1

Thành lập mối quan hệ thứ tự cho các lớp thuộc mối quan hệ M, N, p đã cho.

- Với quan hệ M, chúng ta có ba lớp tương đương là

{a, ố}, {c, d}, {e},

trong đó xuất phát là lớp {a, b} (lớp xuất phát gọi là lớp không có tổ tiên) được xác định theo chiều mũi tên. Từ đó, ta có thể lập sơ đổ sau :

M : {e}, Np số thứ tự 1

No> số thứ tự 0

N:           {a}                                                       Np                                                         số                                                          thứ                                                            tự                                                              1

Theo các kết quả thu được, các lớp tương đương chia thành từng mức có các số thứ tự tương ứng.

Các số thứ tự theo các quan hệ khác nhau M, N, p của lớp các phần tử a, b..., cho phép định nghĩa lượng sau :

r(x, y) = Max (mức của X - mức của y),x, y = a, b, c...

M.N.P

Từ đó lập Bảng r(x, y).

Đến đây, chúng ta cho một định mức z = 0, 1, 2, 3... và định nghĩa tập D(l) = {{x, ỵ} sao mà r(x, yj ^ 11 Dự) = E X E[ D(l), chẳng hạn, theo Bảng trên, ta được

D(2) = Hc, a}, {c, e], {c, a], [d, a}, {d, e} }, f từ đó P(2) gồm tất cả các cặp có mặt trong Bảng mà không có dấu *

THAO TÁC II

Thao tác này có liên quan đến quan hệ mờ R. Cụ thể là : Ta hãy phân tích quan hệ mờ này thành nhiều quan hệ thông thường như đã nói trong định lý phân tích R(1) 1 1 c b d e A(0,9)1 a b d e

         1            0               0
                              0
                                              a                                                  1                                                    0
a                        0                                                           0
                                                                   0                                                                       0
b                                                   1                                                                1
         1
                   1                       1                          1
                                              b
                                                        1
                                                                        1
c             0                      1                         0                                             0                                                          1
         0
                   1
                                                                         0

• Các mức

k = 1, 0,9, 0,7, 0,4

gọi là ngưỡng. Ta thấy ngay rằng tại ngưỡng k = 1 thì, với ma trận thứ nhất, các cặp sau là có liên quan với nhau (thường gọi là tương thích với nhau)

Q(1) = {ía, as, {b,b}, {b, c), (b, d), (c. c), íc, di, (d, d), {d, el). Tại ngưỡng k = 0,9 ta có các cặp sau :

Q(0,9) = Q(1) U {ib aj, {b, e) ; {d, b)).

Và tại các ngưỡng khác, ta có

Dễ thấy rằng khi k càng tăng thì tập trên càng nghèo

Q(1) C Q(0,9) C Q(0,7) C Q(0,4).

Trong lúc các tập Q gọi là tập tương thích, thì các tập D gọi là tập không tương thích. Vì lí do này, để ước lượng sự tương thích giữa các cặp, ta cần lấy cái giao I(k, 1) = Q(k) n D(L) C E X E.

Tập ỉ(k, l) sẽ gồm những cặp tạo nên một quan hệ thông thường. Cái đóng bắc cầu của nó sẽ cho một quan hệ bắc cầu Max Min, nghĩa là một quan hệ tiền thứ tự thông thường, quan hệ này sẽ đóng vai trò tổng hợp các quan hệ M, N, p lại với nhau, với các đặc trưng sau :

- Trọng số cân nhắc p,

- Ngưỡng k,

- Mức l.

Ví dụ, ta chọn ngưỡng 0,7 và mức 2. Ta thu được trong trường hợp này ỉ(k, ỉ) = 1(0,7 ; 2) = Q(0,7) n 5(2) = {{a, a}, {b, a}, {b, b}, {b, c}, {b, d}, {c, c}, {c, d}, {d, c}, {d, d}, {e, a}, {e, b}, {e, c}, {e, d}, {e, e}}}. Một điều may mắn là quan hệ với /(0,7 ; 2) chính là cái dóng bắc cầu Max Min của nó. Kết quả này của bài toán tích hợp nhiều quan hệ M,' N, p chính lại là 7 ? — M. Và điều này không lấy làm ngạc nhiên lắm, do chúng ta đã chọn sự cân nhắc p(M) = 0,6 khá cao.

Chú ý

Trong ví dụ trên, khi thành lập số thứ tự các lớp của một quan hệ tiền thứ tự, chúng ta đã xuất phát từ các lớp không có tổ tiên, nghĩa là tại đó chỉ có các mũi tên xuất phát, mà không có mũi tên tới.

Tất nhiên, cũng có thể dựng thứ tự các lớp xuất phát từ tình huống ngược lại, tức là các lớp tại đó chỉ có mũi tên tới mà không có mũi tên đi. Những lớp như thế gọi là những lớp không có thừa tự.

VIII - TÍCH HỢP NHIỀU PHÂN HOẠCH THÀNH MỘT

PHÂN HOẠCH

Chúng ta hãy chuyển sang một loại bài toán khác là bài toán tích hợp nhiều phân hoạch thành một phân hoạch. Cách giải bài toán này dựa vào hai điểm sau :

- Công thức Stirling về số lượng phân hoạch,

- Khái niệm chỉ số bất đồng tính giữa hai tập con của cùng một tập.

CÔNG THỨC STIRLING

Cho một tập E gồm m phần tử, card E = ni, và E có r lớp tương đương. Thế thì số phân hoạch sím, r) đối với tập E sẽ cho bởi công thức truy toán sau (công thức Stirling) :

Từ đó có thể lập Bảng sau

Ví dụ

Cho E = la, b, c, dl, m = 4. Nếu r = 2, thì ta có các phân loại sau

Lớp (3, 1) ; [(a, b, c), (d}], lía, b, d), (c}l, [ía, c, d). {b}], [íb, c, d}, {a)], 4 phân hoạch, Lớp (2, 2) ; [la, b), íc, d)l, lía, c), íb, dil, Lía, di, Ib, cłl, 3 phân hoạch. •

Nếu r = 3, thì ta có 6 phân hoạch sau

Lớp (2, 1, 1) : ({a, b), {c), {d)l, ({a, c), {b), {d)l. (a, d}, {b}, {c)l, ({b, c}, {a}, {d} ], ((o, d), {a}, {c}l, ({e, di, {aj, {6]].

CHỈ SỐ BẤT ĐỒNG TÍNH

Cho một tập E và tập các tập con của E là P(E). Gọi T và S là hai tập con của P(E),

S C P(E), S C P(E).

Thế thì, theo định nghĩa, chỉ số bất đồng tính q (T, S) giữa hai tập T và S là # (T, S) = 1-=2 Max CardAn B)

Rõ ràng là :

Ví dụ

Cho

với

Câu hỏi : Hai tập T và s đồng tính với nhau đến mức nào, nghĩa là hai phần hoạch T và s khác nhau đến mức nào ?

Ta tính như sau :

Card (A n F) = Card 0 = 0, Card CA u F) = Card {a, b, c} = 3, từ đó

Card (A n F) / Card (A u F) = 0.

CA ÍT G) = {a}, Card CA (An G) = 1, (A u G) = {ữ, b, d, /}, Card (A u G) = 4 => Card (A n G) / Card (A u G) = 1/4. - •

Max{[Card (A n F)/ Card (A u F)] ; [Card (A n Gì/ Card (A u G]} =

= Max {0,1/4} = 1/4.

(B n F) = {b}, Card (B n F) = 1, (B u F) = {a, b, c}, Card (A u G) = 3 Card (B n GỊ / Card (B u F) = ỉ/3.

(B n G) ={a, ờ}, Card n G) = 2, (B u G) =(ữ, b, d, f}, CardíB u G) = 4 => Card (B n G) ỉ Card (B u G) = 1/2.

Max { [Card (B n F) / Card (B u F)], [Card (B n GỴ. / Card (B u G]} = =Max {1/3,1/4} = 1/3.

(C n F) = 0, Card (C n F) = 0, (C n F) = {a, b, d, e, f}, (C u F) = 5 => Card (C n F) / Card {C u F) = 0.

(C n G) = {af}, Card(C n G) = 2, (C u G) = {a,b,d,e,f}t Card(C n G) = 5 => Card (C n G) / Car (C u G) = 2/5.

Max {[Card (C n F) / Card ÍC u F)], [Card (C n G) / Card (C u G]} = = Max {0,2/5} = 2/5.

Max {[Card (D n F) / Card co u F)]s [Card (B n G) / Card (D u G]} = 2/5. Max {[Card (B n F) / Card (E u F)], [Card (E n G) / Card (E u G]} = 1/3.

Các kết quả thu được ở trên có thể viết dưới dạng ma trận sau

Như thế ta được hàm

V'(I, S) = (1/4 + 1/2 + 2/5 + 2/5 + 1/3)/5 = 113/300, do Card T = 5. Đối với 4(S, T) ta lấy Max theo cột, ta được

V(S, T) = (1/3 + 1/2)/3 = 5/12, do Card S = 2.

Từ đó, chỉ số bất đồng tính giữa T và S là p(S, T) = 1 - (113/300 + 5/12)/2 = 1 - 119/300 = 181/300 = 0,603. Bây giờ chúng ta hãy chuyển sang một loại khác về quan hệ bất đồng, tính. Cho một tập E, và P(E) là tập các tập con của nó. Lại cho hai tập

T VÀ S, T C P(E), S C P(E), trong đó

I = 1A;), S = (Bị, i = 1,2,... n, j = 1, 2.., n2,

Ai, B ; đều là những tập mờ.

Cũng như trước, ta định nghĩa

u(T,S) = Card F T E Max (e ? (A n B, Ø)le° (A U B, Ø)).

AET BES

từ đó, chỉ số bất đồng tính định nghĩa như sau

P(T, S) = 1 - 14(T, S) + Y(S, T)H/2.

Cũng có thể dùng định nghĩa khác, thay khoảng cách Euclide bằng khoảng cách Hamming.

Ví dụ

Cho

E = {a, b, c, d, el, T = ÍM, N, P}, S = {U, V),

u a b c d e

Ta được ngay các tập mờ sau

Mn u

MU u

từ đó ta được (M n Ư, 0) = (0,3)2 + (0,4)2 + (0,8)2 = 0,89,

u u, 0) = 2,29,

e2 (M (M n ơ, 0) / e2 (M u t/, 0) = 0,89/0,29 = 0,38.

Tương tự như thế ta tính được

Ta lập Bảng sau

U V Max

V

Max     0,38          0,53

Từ đó ta được

tức là theo định nghĩa

p(T, S) = y(S, T) = 1 - 10,33 + 0,45} / 2 = 0,61.

Hệ số bất đồng tính này chứng tỏ rằng T và S là khác tính nhau.

TÍCH HỢP NHIỀU PHÂN HOẠCH THÀNH MỘT PHÂN HOẠCH

Bài toán này có ý nghĩa như sau : Chúng ta đã giới thiệu công thức Stirling về các phân hoạch của một tập E hữu hạn, đồng thời với chỉ số bất đồng 4 tính giữa hai tập mờ.

Nói cụ thể hơn, giả sử ta cho tập hữu hạn

E = {a, b, c, d).

Các phân hoạch của E là :

r = 1 : chỉ một phân hoạch, Ai = { a b c d}, r = 2 : 7 phân hoạch, Ao = {{«, b, c}, {c, đị), A3 = {{ữ, d, b}. {c}}, A4 = {{a, c, d}. {6}}, A5 = {{ờ, c, d}, {ữ}}, A() = {{ữ, 6}, {c, d}}, A7 = {{c, d}, {a, ÒH Ay = { {ố, c}, {a, d}}.

r = 3 : 6 phân hoạch

A9 = -Hư, b}, {c}, (dí}, A1() = {{a, c}, {ỏ}, {d}} An = {{n, d}, {b}, {c}} A12 = 116 c}, {a, d}}, 13 = {{ồ, d}, {a, c}} A j 4 = {{c, d}, {a}, {ố}}, r = 4 : chỉ ra một phân hoạch

A i 5 = {{a}, {ố}, {c}, W}.

Tập hợp các phân hoạch trong trường hợp này là p = {A1, A2... A15}. Tính chất các phân hoạch :

Bây giờ ta cho một ví dụ cụ thể :

- E như trên, E = {a, b, c, d},

- Tiếp theo, để được cụ thể, ta cho ba phân hoạch sau :

N = {{a, c, d}, {b}} = {G(Nj},

GẠN) = {a, c, d}, ơ 2(N) = {ố}, Card w = 2,

Q = {{a}> {ố, c, d}} = {G(Q)},

GẠQ) = {«}, G2(Q) = {ố, c, d}, Card ộ = 2,

Hãy tích hợp 3 phân hoạch đó, dưới dạng

^A) = p(M) <p(A, M) + p(N) p(A, N) + p(Q) p(A, Q), (*)

với sự cân nhác sau

p(M) = 1/8, p(N) = 3/8, p(Q) = 1/2,

với chỉ số bất đồng tính

p(K, J) = 1 - ty(K, J) + ^ụ, K)}!2,

ụ>(A, M) = (CardP) ! 2 Max {Card (J n G) / Card (J ứỡ)},

J£A GEM

ự>(M, A) = (CardM)" ! 2 Max {Card y n G) / Card (J u G)},

GEM JEA

G = la,6}, 1c1. hay là {dì, khi xét tập M.

Các công thức cho các tập N và Q cũng tương tự như với M. Với N và Q ta có tương ứng

G(N) = la, c, d) hay là 10), khi xét tập N,

G'Q ! = la) hay là lb. c. dì, khi xét tập Q.

Những điều nói trên có nghĩa là tìm một phân hoạch cụ thể W trong số 15 phân hoạch A1... Als của E sao mà chỉ số bất đồng tính (°) là bé nhất.

1. Với phân hoạch

A = A, = la, b. c. d), và M = la, bi, icl, {đì,

ta có

J(A,) = la, b, c, d), Card A, = 1,

và G(M) = {a, bì, lc), hay là Id), Card M = 3.

Ta tính riêng từng trường hợp trên. Ta có

JEACEM

= Max (Card (J n G) / Card (J U G)) = 1/2,

GEM

J= A = Ay,

từ đó

Tương tự như thế, ta được

từ đó ta được chỉ số bất đồng tính giữa M và A, p(M, A,) = 1 - (1/2) {(1/3) (1/2 + 1/4 + 1/4) + (1/1) (1/2)} = 1 - 5/12 = 7/12.

Các kết quả trên có thể viết lại dưới dạng Bảng sau

Max 1/4 3/4

Từ đó đẳng thức (*) cụ thể sẽ là

W(A,) = (1/8) (7/12) + (318) (3/8) + (4/8) (3/8) = 0,40.

d = 1 - (1/2) {(1/3) (2/3 + 1/3 + 1) +

0    0       1

Max 2/3 1/3 1

Đẳng thức (*) trong trường hợp này sẽ là WIA.) = (1/8) (1/4) + (3/8) (7/12) + (4/8) (7/12) = 13/24 = 0,54.

Tiếp tục tính như thế, cuối cùng ta được

•(N. A2)

1 - (1/2) {(1/2) (1/2 + 1/3)

Ta thấy rằng lượng W(Ai) = 0,28 là bé nhất với AI.

KẾT LUẬN

Sự tích hợp ba quan hệ đã cho M> N, Q - với sự cân nhắc p(M), p(N), p(Q) cụ thể trên và với khái niệm khoảng cách trên - thành quan hệ ÀI4 = {{c, d}, fal, 16 là tốt nhất.