1

LỜI NÓI ĐẦU
Trong cuộc sống loài người, ngôn ngữ được hình thành một cách tự nhiên
để giải quyết nhu cầu trao đổi thông tin với nhau. Hơn thế, nó là công cụ để con
người mô tả các sự vật, hiện tượng trong thế giới thực và dựa trên đó để tư duy,
lập luận đưa ra những nhận định, phán quyết nhằm phục vụ cho cuộc sống xã
hội. Ngày nay khoa học và công nghệ đã có những phát triển vượt bậc, nhiều
máy móc thiết bị được tạo ra đã góp phần giải phóng sức lao động của con
người. Trong đó lĩnh vực công nghệ thông tin đã có những đóng góp vô cùng to
lớn cho sự phát triển kinh tế - xã hội nói chung và giúp giải phóng sức lao động
không chỉ là lao động chân tay mà còn cả lao động trí óc của con người nói
riêng. Công nghệ thông tin đã góp phần đưa khả năng tư duy, lập luận và sự
sáng tạo kiểu như bộ não người vào máy móc thiết bị để “thông minh hơn”. Để
thực hiện điều này, rất nhiều nhà khoa học đã và đang nghiên cứu cả về lý
thuyết lẫn ứng dụng, đưa ra các phương pháp, các quy trình nhằm kế thừa, mô
phỏng khả năng của con người vào các thiết bị máy móc. Trước hết, các nhà
khoa học đã phải hình thức hóa toán học các vấn đề ngôn ngữ và xử lý ngôn ngữ
mà con người vẫn làm. Người đi tiên phong trong lĩnh vực này là Lotfi A.
Zadeh, ông đã đề xuất khái niệm mờ từ những khái niệm mơ hồ, không rõ ràng.
Cho đến nay, hệ mờ phân lớp dạng luật (FRBCS) là mô hình được nhiều
tác giả quan tâm nghiên cứu và sử dụng trong khai phá dữ liệu, tìm kiếm tri thức
từ dữ liệu cho bài toán phân lớp. Thế mạnh của mô hình này là có thể cung cấp
được cho người dùng cuối những tri thức dạng luật dễ hiểu, dễ sử dụng đối với
con người như là những tri thức của họ. Với việc sử dụng tập mờ và lôgic mờ,
các nghiên cứu đều tìm kiếm phương pháp xây dựng hệ mờ phân lớp dạng luật
nhằm đạt hai mục tiêu chính: thứ nhất, hiệu quả phân lớp của hệ càng cao càng
tốt; thứ hai, tính phức tạp của hệ đồng thời càng nhỏ càng tốt.


2

(x) mà nó liên

kết mỗi phần tử x U với một số thực trong đoạn [0,1]. Giá trị hàm
diễn mức độ thuộc của x trong A.

(x) biểu

(x) là một ánh xạ từU vào [0,1] và được gọi

là hàm thuộc của tập mờ A[1].
Hay A được gọi là tập mờ khi và chỉ khi:
A = {(x,
Trong đó

(x) x U,

(x): U

[0,1]}

(1)

(x) được gọi là hàm thuộc của tập mờ A.

Giá trị hàm

(x) càng gần tới 1 thì mức độ thuộc của x trong A càng cao.

Tập mờ là sự mở rộng của khái niệm tập hợp kinh điển. Khi A là tập hợp kinh
điển thì A có thể được biểu diễn như sau

(x’) = 1.
} là đoạn đóng trên R.

(x) là hàm liên tục.

Một số dạng số mờ thường được sử dụng là số mờ dạng tam giác, hình
thang và dạng hàm Gauss.
a. Số mờ dạng tam giác được xác định bởi 3 tham số. Khi đó hàm thuộc
của sô mờ tam giác A(a, b, c) cho bởi:

( )=

0nếu
⁄
nếu
1nếu
⁄
nếu
0nếu

≤
≤ ≤
=
≤ ≤
=

1

0


1

0

a

b

z

d

c

c.Số mờ dạng hàm Gauss có hàm thuộc cho bởi:
( )=
Trong đó

(
)
( σ)

nếu|x
0nếu|x

c| ≤
c| ≥

là số dương được chọn thích hợp.


= 0 (trong đó m0 = m1 = a và mp+1 = mp =b);

3)

(x) liên tục

4)

(x) đơn điệu tăng trên [mk-1, mk] và đơn điệu giảm trên [mk,mk+1];

5) ∀

U, ∃ , sao cho

(x) > 0 (tất cả mọi điểm trong U đều thuộc một

lớp của phân hoạch này với độ thuộc nào đó khác 0)
1.1.4 Các phép tính trên tập mờ Zadeh
1.1.4.1 Các phép toán tập hợp:
Cho A, B là 2 tập mờ trên cùng tập nền U:
Phép giao (Intersection):
Phép giao của tập A và B là tập mờ C được định nghĩa như sau:
C = A B = {(x,

(x))| x

U,

(x) = min{


Cho U = {1, 2, 3, 4, 5} và hai tập mờ A, B như sau:
A = {(1,0), (2,1), (3,0.6), (4,0.3), (5,0.2)}
B = {(1,0), (2,0.5), (3,0.7), (4,0.2), (5,0.4)}
Khi đó : C = A

B = {(1,0), (2,1), (3,0.7), (4,0.3), (5,0.4)}

Phép bù (Complement):
Bù của hai tập mờ A được định nghĩa như sau:
AC = {(x,

(x)) x

U,

(x) = 1 -

(x)}

Lưu ý:
1/ A∪AC U
2/ A∩AC

0

3/ (AC)C = A
1.1.4.2 Phép phủ định:
Phủ định (negation) là một trong những phép toán logic cơ bản. Để suy
rộng chúng ta cần tới toán tử v(Not P) xác định giá trị chân lý của Not P đối với
mệnh đề P.


9

S(x, y) = max(x, y) ; S (x, y) = x+ y – xy ; S(x, y) = min( x+ y -1 , 0), …..
1.1.4.5 Phép kéo theo:
Phép kéo theo là một hàm số I: [0,1]2  [0,1] thoả các điều kiện sau:
1) I(0,y)=1,  y  [0,1]
2) I(x,1)=1,  x  [0,1]
3) 0  x1, x2 1  I(x1,y)  I(x2,y),  y  [0,1]
4) 0  y1, y2 1  I(x,y1)  I(x,y2),  x  [0,1]
5) I(1,0)=0
Cho:T là t-chuẩn; S là t-đối chuẩn; n là phép phủ định mạnh
Phép kéo theo thứ nhất:
Hàm IS(x,y) xác định trên [0, 1]2 bằng biểu thức IS(x,y) =S(n(x),y)
Phép kéo theo thứ hai:
Cho T là t-chuẩn, xác định IT(x,y) =Sup{z | 0  z  1 và T(x,y) 
y},x,y [0,1]
Phép kéo theo thứ ba:
Cho (T, S, n) là bộ 3 De Morgan, T là t-chuẩn, S là t-đối chuẩn, n là phép
phủ định mạnh
Phép kéo theo thứ ba: Hàm ITS(x,y) xác định trên [0, 1]2 bằng biểu thức
ITS(x,y) =S(n(x),T(x,y))
1.1.5. Biến ngôn ngữ
Biến ngôn ngữ làm một loại biến mà giá trị của nó không phải là số mà là
từ hay mệnh đề dưới dạng ngôn ngữ tự nhiên. Biến ngôn ngữ được định nghĩa
như sau:


10



ơ

ấ

(u)

Bình thường với hàm thuộc

ì

Hơi cao với hàm thuộc

(u)

Thấp với hàm thuộc

ấ
ấ

(u)

Hơi thấp với hàm thuộc

Rất cao với hàm thuộc

ơ
ấ

ườ

Lúc đó ta có thể biểu diễn luật này dưới dạng luật mờ tổng hợp
Gọi x1, x2, …, xn là các biến đầu vào và y là biến đầu ra (thường là các
biến ngôn ngữ). Aki là các tập mờ ứng với các luật Rk trên không gian nền Ui có
hàm thuộc ký hiệu là Aki(xi) hoặc Aki(xi). Bk là tập mờ trên không gian nền V có
hàm thuộc Bk(y)= Bk(y).
IF (x1 is Ak1) (x2 is Ak2)  … (xi is Aki)  …  (xn is Akn) THEN y is Bk
Ví dụ:


12

IF (Ngoại ngữ giỏi)  (Tin học giỏi)  (Chuyên môn vững) THEN (Khả năng
trúng tuyển cao)
Giải bài toán lập luận xấp xỉ theo mô hình (1) là xây dựng một phương
pháp lập luận dựa trên các luật mờ để tính toán đầu ra từ các dữ liệu đầu vào
tương ứng, tức tìm kết quả B của Y khi biết giá trị A1, A2, ..., An tương ứng với
các biến X1, X2, …, Xn. Vì chúng ta đang ở trong môi trường thông tin mờ,
không chắc chắn, nên không có một phương pháp lập luận chính xác và duy
nhất. Mỗi phương pháp sẽ xuất phát từ một quan sát trực quan nào đó.
Theo phương pháp truyền thống, quy tắc modus ponens tổng quát hóa được
áp dụng cho hệ mờ dạng (1) cùng với việc sử dụng các phép toán lôgíc mờ đã
được nhiều tác giả đề cập chi tiết trong [1]. Ở đây chúng ta tóm tắt như sau:
Xét mỗi luật mờ trong (1) là một quan hệ mờ Ri trên miền tích Đề-các U=
U1U2 ... UnV với hàm thuộc được xác định bởi:

Ri = I(Tn(Ai,1, ..., Ai,n), Bi)

(3)

trong đó Ai,j, Bi là các hàm thuộc tương ứng với Ai,j, Bi, Tn là phép t-normnngôi và I là phép kéo theo. Kết nhập các luật mờ Ri (i = 1, ..., m) của hệ bằng

(1) khi chọn đầu ra Bi có hàm thuộc ở dạng đơn tử. Tuy nhiên, luật mờ dạng
Sugeno với ưu điểm có thể thể hiện các hành vi cục bộ của hệ thống được ứng
dụng và không cần giải mờ sau khi lập luận. Đây là những lý do thúc đẩy những
nghiên cứu hơn nữa về các mô hình ứng dụng hệ luật mờ, đặc biệt trường hợp
luật mờ có kết luận chỉ chứa giá trị hằng cá thể sẽ được trình bày tiếp ở những
phần sau.
1.2.Một số vấn đề cơ bản trong Đại số gia tử
1.2.1. Đại số gia tử
Để mô phỏng các quá trình suy luận của con người, lý thuyết đại số gia tử
(ĐSGT) đã cố gắng nhúng tập ngôn ngữ vào một cấu trúc đại số thích hợp và
tìm cách xem chúng như là một đại số để tiên đề hoá sao cho cấu trúc thu được
mô phòng tốt ngữ nghĩa ngôn ngữ.
Giả sử X là một biến ngôn ngữ và miền giá trị của X là Dom(X). Một đại
số gia tử AX tương ứng của X là một bộ 4 thành phần AX = (Dom(X), G, H, ≤)
trong đó G là tập các phần tử sinh, H là tập các gia tử và quan hệ “≤” là quan hệ
cảm sinh ngữ nghĩa trên X. Giả thiết trong G có chứa các phần tử hằng 0, 1, W
với ý nghĩa là phần tử bé nhất, phần tử lớn nhất và phần tử trung hòa trong X. Ta
gọi mỗi giá trị ngôn ngữ x ∈ X là một hạng từ trong ĐSGT.
Trong đại số gia tử AX = (Dom(X), C, H, ≤) nếu Dom(X) và C là tập sắp
thứ tự tuyến tính thì AX được gọi là đại số gia tử tuyến tính.Khi được thêm hai
gia tử tới hạn là và

với ngữ nghĩa là cận trên đúng và cận dưới đúng của tập


14

H(x) khi tác động lên x, thì ta được ĐSGT tuyến tính đầy đủ, ký hiệu AX = (X,
G, H, ,



Định lý 1.2: [1] Cho x = hn…h1u và y = km…k1u là hai biểu diễn chính tắc
của x và y đối với u. Khi đó tồn tại chỉ số j ≤ min{n, m} + 1 sao cho hj' = kj' với
mọi j' < j (ở đây nếu j = min {n, m} + 1 thì hoặc hjlà toán tử đơn vị I, hj = I, j = n
+ 1 ≤ m hoặc

dkj = I, j = m + 1 ≤ n) và

(1)x < y khi và chỉ khi hjxj< kjxj, trong đó xj = hj-1...h1u.
(2)x = y khi và chỉ khi m = n và hjxj = kjxj.
(3)x và y là không so sánh được với nhau khi và chỉ khi hjxjvà kjxjlà không
so sánh được với nhau.
1.2.3. Vấn đề định lượng ngữ nghĩa trong đại số gia tử
Hàm H(x) có thể được sử dụng như là một mô hình biểu thị tính mờ của x
và kích thước tập H(x) được xem như độ đo tính mờ của x, và được định nghĩa
như sau:
Định nghĩa 1.6: [1] AX = (X, G, H, ,
Ánh xạ fm: X

, ≤) là một ĐSGT tuyến tính đầy đủ.

[0,1] được gọi là một độ đo tính mờ của các hạng từ trong X nếu:

(1)fm là đầy đủ, tức là fm(c-) + fm(c+) = 1 và ∑

∈

(

) = fm(u), ∀u∈X;


Hình vẽ sau sẽ minh họa rõ hơn cho khái niệm độ đo tính mờ của biến
ngôn ngữ HOT
Hot
Poss Hot

Little Hot

VeryHot

More Hot

W

1
fm(MLHot)

fm(LLHot)

fm(PVHot)

fm(VVHot)

fm(LVHot)
fm(VLHot)

fm(MHot)

fm(PLHot)



với , > 0 và

+

= 1;

( )= 1, trong đó Xk là tập các hạng từ có độ dài đúng k;

(4)fm(hx) = ( ).fm(x). và x∈X, fm( x) = fm( x) = 0;
(5)Cho fm(c-), fm(c+) và = ( ) với ∀h∈H,khi đó với x = hn…h1 ,

∈{-

,+}, dễ dàng tính được độ do tính mờ của x như sau:
fm(x) = (

)… ( )fm( )

Để thuận tiện cho việc tính toán và xử lý trong nhiều ứng dụng chúng ta
cần xác định giá trị định lượng của các hạng từ này. Việc định lượng hóa các
khái niệm mờ theo phương pháp tiếp cận của tập mờ được thực hiện qua các
phương pháp khử mờ. Đối với ĐSGT, giá trị định lượng của các hạng từ được


17

định nghĩa dựa trên cấu trúc thứ tự ngữ nghĩa của miền giá trị của các biến ngôn
ngữ, cụ thể là độ đo tính mờ của các hạng từ và gia tử.
Định nghĩa 1.7:[1] Cho AX = (X, G, H, ,

fm(x)|

fm(x)

fm(x),

∈ tv([0,1]), nếu nó có độ dài bằng độ đo tính

= fm(x), và được xác định bằng qui nạp theo độ dài của x như sau:


18

(1) Với độ dài của x bằng 1 (l(x)=1), tức là x∈ {c-, c+}, khi đó |
fm(c-), |

fm(c

+

)| = fm(c+) và

fm(c )

≤

fm(x)|

fm(x)


fm(h-qx)

>fm(h-

và ngược lại:
v(Hot)
v(PHot)

v(LHot)

2(PHot)

2(LHot)

3(VLHot)

3(PLHot)

3(LPHot)

v(VHot)

v(MHot)

2(VHot)

2(MHot)

3(MPHot)



(h2x′) ≤ ... ≤

(h-qx′) ≤

(h-q+1x′) ≤ ... ≤

(h-1x′) ≤

(hpx′), và nếu Sign(hpx′) = -1, thì ta có

(hpx′) ≤

(hp-1x′) ≤ ... ≤ (h1x′) ≤ (h-1x′) ≤ (h-2x′) ≤ ... ≤ (h-qx′);
(2) Tập Ik = { (x): x ∈ Xk} là một tựa phân hoạch của đoạn [0,1];
(3) Cho một số m, tập { (y): y = km... k1x, ∀km,... , k1∈ H} là một tựa
phân hoạch của khoảng tính mờ (x);
(4) Tập Ik = { (x): x ∈ Xk} “mịn” hơn tập Ik-1 = { (x): x ∈ Xk-1}, tức là


19

bất kỳ một khoảng tính mờ trong Ik chắc chắn được chứa bên trong một khoảng
của Ik-1;
(5) Với x < y và l(x) = l(y), thì (x) ≤ (y) và (x) ≠ (y).
Theo Định nghĩa 1.7 và 1.8, có một mối liên hệ giữa ánh xạ định lượng
ngữnghĩa và khoảng tính mờ của của hạng từ trong một ĐSGT, được thể hiện bằng
địnhlý sau :
Định lý 1.3: [1] Cho A X = (X, G, H, ∑, Φ, ≤) là một ĐSGT tuyến tính đầy
đủ và hàm υ được định nghĩa trong Định nghĩa 1.7. Khi đó υ là một ánh xạ định

S: U

C

(1.1)

Như vậy, hệ S phải đạt được các mục tiêu như hiệu quả quả phân lớp cao,
tức là sai số phân lớp cho các dữ liệu ít nhất có thể, số lượng các luật nhỏ cũng
như số điều kiện tham gia trong vế trái mỗi luật ít. Mục tiêu về hiệu quả phân
lớp nhằm đáp ứng tính đúng đắn của của hệ đối với tập dữ liệu mẫu được cho
của bài toán, các luật mờ trong S phải đơn giản và dễ hiểu đối với người dùng.
Khi đó mục tiêu xây dựng hệ luật sao cho:
fp(S) → max, fn(S) và fa(S) → min.
trong đó:

-

(1.2)

fp(S) – hàm đánh giá hiệu quả phân lớp

- fn(S) – là số luật
- fa(S) – là độ dài (số điều kiện tham gia)
Tuy nhiên, ta thấy rằng ba mục tiêu xây dựng hệ luật trên không thể đạt
được đồng thời. Khi số luật giảm thì lượng tri thức về bài toán giảm khi đó nguy
cơ phân lớp sai tăng, khi có quá nhiều luật lại gây nhiễu loạn thông tin trong quá
trình phân lớp. Số điều kiện của mỗi luật ảnh hưởng đến tính phổ quát của luật,


21



22

Ví dụ: Cho bài toán phân lớp với tập mẫu có thuộc tính x1, x2 và hai lớp
{C1, C2} biểu thị bằng chấm tròn và vuông (hình..):

Hình 1.3: Lưới phân hoạch mờ trên miền của hai thuộc tính
Lưới phân hoạch này chia không gian tích Đề-các của các miền của thuộc
tính tạo thành không gian các siêu hộp, ký hiệu Hs, các luật mờ sẽ được hình
thành từ các tổ hợp của các giá trị ngôn ngữ trong không gian phân hoạch tương
ứng với mỗi siêu hộp mà tại đó có hỗ trợ bởi các mẫu dữ liệu.
Trực quan từ ví dụ trong hình 1.3, các hệ luật có thể được chọn như sau:
- Hệ S1 gồm 7 luật mờ sau:
If x1 is Small and x2 is Small then Class C1,
If x1 is Small and x2 is Large then Class C1,
If x1 is Large and x2 is Medium then Class C1,
If x1 is Large and x2 is Small then Class C2,
If x1 is Medium and x2 is Small then Class C2,
If x1 is Medium and x2 is Medium then Class C2,
If x1 is Medium and x2 is Large then Class C2.
- Hệ S2 gồm 4 luật mờ sau:


23

If x1 is Small then Class C1,
If x1 is Large and x2 is Medium then Class C1,
If x1 is Medium then Class C2,
If x1 is Large and x2 is Small then Class C2.



s(A q  Cq )  sq 

 Aq (pi )

pi ClassCq

N

(1.6)

Để tính mức đốt cháy của mẫu dữ liệu pi đối với điều kiện Aq của luật mờ,
ta áp dụng t-norm dạng tích:
(pi) =

,

(di,1).

,

(di,2). … .

,

(di,n).

(1.7)


luận khác Cq:

cq , Ave

m
1

 c(Aq  Ch )
m  1 h 1

(1.12)

Ch Cq

cq,2nd là độ tin cậy lớn nhất của các luật có cùng điều kiện Aq nhưng kết
luận là lớp khác với Cq:
cq,2nd = max{c(Aq ⇒Cq) | h = 1, …, m; Ch ≠Cq }

(1.13)

cq,Sum là tổng các độ tin cậy của các luật có cùng điều kiện Aq nhưng kết
luận là lớp khác với Cq:
m

cq ,Sum 

 c(A

q


dựng một luật mờ bằng cách đặt điều kiện của luật tương ứng với siêu hộp đó
Aq= (Aq,1, …, Aq,n), phần kết luận được chọn là nhãn phân lớp sao cho luật đạt
độ tin cậy lớn nhất:
Cq  arg Ch max{c(A h  Ch )| s(A h  C h )  0, h  1,..., m}

(1.16)

Phương pháp sinh luật này sẽ đảm bảo các công thức đánh giá trọng số
của luật theo CF1, CF3 luôn dương.
Ký hiệu S0 là tập tất cả các luật mờ được sinh ra từ không gian Hs, kích
thước tập S0 có khả năng rất lớn, có thể |S0| = |Hs|. Do vậy, mỗi luật trong S0 sẽ
được đánh giá tiêu chuẩn lựa chọn (hay tiêu chuẩn sẵn sàng), kí hiệu là SR:
SR1(Aq

Cq) = cq’

(1.17)

SR2(Aq

Cq) = sq,

(1.18)

SR3(Aq ⇒Cq) = cq.sq

(1.19)

Một phương pháp khác được sử dụng là thiết kết các thuật toán tìm kiếm
hệ luật tối ưu dựa trên giải thuật di truyền (GA). Trong đó các luật mờ được mã