ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

LÊ THỊ BÍCH THẢO

KHAI PHÁ LUẬT KẾT HỢP MỜ DỰA
TRÊN ĐẠI SỐ GIA TỬ

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên - 2013


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

LÊ THỊ BÍCH THẢO

KHAI PHÁ LUẬT KẾT HỢP MỜ DỰA
TRÊN ĐẠI SỐ GIA TỬ
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

NGƯỜI HƯỚNG DẪN KHOA HỌC
TS.Trần Thái Sơn

Thái Nguyên - 2012



Tác giả

Lê Thị Bích Thảo


i
MỤC LỤC
LỜI CAM ĐOAN...............................................................................................iii
LỜI CẢM ƠN.....................................................................................................iv
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT............................................ii
DANH MỤC CÁC HÌNH ẢNH..........................................................................iii
............................................................................................................................iii
PHẦN MỞ ĐẦU...................................................................................................1
Chương 1..............................................................................................................4
LÝ THUYẾT CHUNG VỀTẬP MỜ VÀLÝTHUYÊT
́ ........................................4
ĐAỊ SỐGIA TỬ..................................................................................................4
1.1. Lýthuyêt́ chung về tập mờ ....................................................................4
1.2. Lôgic mờ...................................................................................................9
1.3. Biến ngôn ngữ........................................................................................13
1.4. Một số khái niệm cơ bản về Đại số gia tử........................................15
1.4.1. Đại số gia tử ..................................................................................................................16

1.4.2. Định nghĩa đại số gia tử ................................................................................................17

Chương 2............................................................................................................31
LUẬT KẾT HỢP TRONG KHAI PHÁ DỮ LIỆU.............................................31
2.1. Bài toán kinh điển dẫn đến việc khai phá luật kết hợp...................31
2.2. Khai phá luật kết hợp mờ:....................................................................36
Chương 3............................................................................................................38

các chữ viết tắt
ĐSGT
α
β
AX, AT
AX
W

Ý nghĩa
Đại số gia tử
Tổng độ đo tính mờ của các gia tử âm
Tổng độ đó tính mờ của các gia tử dương
Đại số gia tử
Đại số gia tử tuyến tính đầy đủ
Phần tử trung hòa trong đại số gia tử


iii
DANH MỤC CÁC HÌNH ẢNH
Hình
Hình 1
Hình 2
Hình 3
Hình 4
Hình 5

Mô tả
Đồ thị biểu diễn hàm thuộc của tập mờ già (old)
Biểu diễn bộ 2
Độ đo tính mờ của biến TRUTH

các quy luật giúp cho quản lý, kiểu như "Nếu một người đã mua bánh mỳ và
bơ, khả năng người đó cũng mua giăm bông là rất cao". Luật có dạng như vậy


2
gọi là luật kết hợp và là hướng nghiên cứu quan trọng trong lĩnh vực khai phá
dữ liệu. Về sau, người ta thấy sẽ là rất không đầy đủ nếu chỉ xem xét các cơ
sở dữ liệu chỉ bao gồm các phần tử 0 và 1. Chẳng hạn, trong CSDL nhân sự
của một cơ quan có các mục như tuổi, thu nhập.. có giá trị trong miền số thực
rất rộng. Để trích xuất ra các luật kết hợp, một phương pháp thường được sử
dụng là chuyển số liệu trong CSDL đã cho về CSDL chỉ chứa các giá trị 0, 1
và áp dụng các kết quả đã có. Thí dụ, trong mục "tuổi", có thể chia ra các
miền "trẻ", "trung niên" và "già" với các miền giá trị tương ứng là [0,35],
[36,55], [56,80] và nếu một giá trị của CSDL ban đầu rơi vào miền giá trị nào
thì ta ghi 1 cho vị trí tương ứng trong CSDL chuyển đổi, ngược lại gán giá trị
0. Phương pháp này đơn giản về mặt thực thi nhưng có thể gây băn khoăn do
ranh giới cứng mà người ta đưa ra khi tiến hành chuyển đổi. Chẳng hạn hai
người tuổi 35 và 36 tuy rất gần nhau về mặt tuổi tác nhưng lại thuộc hai lớp
khác nhau là "trẻ" và "trung niên", dẫn tới việc đưa ra những luật kết hợp có
thể thiếu tính chính xác. Và người ta sử dụng cách tiếp cận mờ để khắc phục
điều này, theo đó, một giá trị bất kỳ của CSDL ban đầu không chuyển đổi về
giá trị 0 hoặc 1 như trên mà sẽ chuyển về một tập giá trị thực thuộc đoạn
[0,1], là độ thuộc của giá trị đã cho vào các tập mờ được xác định trước. Thí
dụ, người tuổi 35 trong ví dụ trên, ở CSDL đã chuyển đổi sẽ nhận tập giá trị
(trẻ, 0,8), (trung niên, 0,6), (già, 0,1). Phương pháp này, tuy dẫn tới việc xử lý
phức tạp hơn nhưng dễ chấp nhận hơn về mặt trực quan và hiện đang được
nhiều nhà nghiên cứu quan tâm. Mặc dù vậy, theo ý chúng tôi, phương pháp
trích xuất luật kết hợp mờ vẫn có một số điểm yếu cần khắc phục. Đó là sự
phụ thuộc chủ quan rất lớn vào việc lựa chọn các hàm thuộc cho các tập mờ
dẫn đến việc xử lý vừa phức tạp vừa có thể thiếu chính xác. Trong bài báo này

nghĩa như sau.
Định nghĩa 1. [14] Cho một tập vũ trụ U với các phần tử ký hiệu bởi x,
U={x}. Một tập mờ A trên U là tập được đặc trưng bởi một hàm µA(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 µA(x)
biểu diễn mức độ thuộc của x trong A. µA(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.
Như vậy, giá trị hàm µA(x) càng gần tới 1 thì mức độ thuộc của x trong A
càng cao. Khi A là một tập hợp kinh điển, hàm thuộc của nó, µA(x), chỉ nhận 2
giá trị 1 hoặc 0, tương ứng với x có nằm trong A hay không. Rõ ràng, tập mờ
là sự mở rộng của khái niệm tập hợp kinh điển. Các khái niệm, phép toán
trong lý thuyết tập kinh điển cũng được mở rộng cho các tập mờ.
Họ tất cả các tập mờ trên miền cơ sở U là không gian các hàm từ U vào
đoạn [0,1], tức là

F (U ,[0,1])

= {µA : U→[0,1]}, một không gian tương đối

giàu về cấu trúc tính toán mà nhiều nhà nghiên cứu đã sử dụng cho việc mô
phỏng các phương pháp suy luận của con người.
Chúng ta có thể biểu diễn tập mờ bằng các cách sau, tùy theo tập U là
hữu hạn, đếm được hay vô hạn liên tục:


5
- Trường hợp U hữu hạn, U={ui : 1≤ i ≤ n}, ta có thể viết
A = µA(u1)/u1 + µA(u2)/u2 + … + µA(un)/un = ∑1≤ i ≤n µA(ui)/ui
- Trường hợp U vô hạn đếm được, U={ui : i=1,2,… }, ta viết
A = ∑1≤ i

6
= ∫U µA(u)du, nếu U là vô hạn liên tục.
ii) Lực lượng mờ hay bản số mờ của tập mờ A, ký hiệu card(A), là
một tập mờ trên tập các số nguyên không âm N, được xác định như sau:
card(A) = ∫N µcard(A)(n)dn , trong đó, µcard(A)(n) được xác
định theo công thức sau, với |Aα| là lực lượng tập mức Aα,

µcard(A)(n) = sup{t∈[0,1] : |Aα| = n}.
Ví dụ 1. Cho tập vũ trụ chỉ tuổi tính chẵn năm U={u : 0≤ u ≤120}, A là
một tập mờ chỉ tuổi già (old) được xác định bởi hàm thuộc sau (hình 1):
u ∈ [0, 60]
0
µold (u ) = 
−
2
−
1
(1 + ( u −660 ) ) u ∈ [61,120]

Khi đó tập mức α=0.5 của A là A0.5 = {u : 66≤ u ≤120} ;
support(A) = {u : 61≤ u ≤120} ; high(A) = 1.01-1; core(A) = {120}.

Hình 1. Đồ thị biểu diễn hàm thuộc của tập mờ già (old)
Tiếp theo chúng ta định nghĩa một số phép toán cơ bản trên tập mờ, các
phép này làm cơ sở cho việc phát triển lôgíc mờ sau này.
Định nghĩa 5. [1,14] Cho hai tập mờ A và B trên tập nền U có hàm
thuộc tương ứng là µA và µB, ba phép toán cơ bản là hợp, giao của hai tập mờ
và lấy phần bù của tập mờ A là một tập mờ C, được viết là
C = A ∪ B, hoặc C = A ∩ B, hoặc C = A~ với hàm thuộc được xác


10
1.0

)
µK(u

1.0 0.9 0.8 0.6 0.4 0.2 0.0 0.0 0.0

0.0

)
Ta có kết quả của các phép toán trên hai tập mờ này với hàm thuộc thể
hiện trong bảng sau:
1
2
3
4
5
6
7
8
9
10
u∈U
µG∪K(u) 0.0 0.0 0.0 0.6 0.5 0.5 0.7 0.9 1.0 1.0
µG∩K(u) 0.0 0.0 0.0 0.1 0.3 0.2 0.0 0.0 0.0 0.0
µG~(u) 1.0 1.0 1.0 0.9 0.7 0.5 0.3 0.1 0.0 0.0
Một lớp đặc biệt các tập mờ là lớp các quan hệ mờ, chúng là các tập mờ
trên không gian tích Đề-các các miền cơ sở. Như tên gọi, quan hệ mờ mô tả

v2

w1
w2
u1  0.4 1 
v1  0.2 0.8


R = u2  1 0.3 và S = 
v2 0.7 0.1
u3  0.7 0.8
w1

w2

u1 0.7 1 
khi đó phép hợp thành max-min là R o S = u2  0.3 0.8  ,


u3 0.7 0.7 
w1

w2

u1  0.8 0.32 
và max-product là R o S = u2  0.21 0.8  .


u3 0.56 0.56 



ii) Tính giao hoán:

T(a,b) = T(b,a)

iii) Tính đơn điệu:

a ≤ a’ ⇒ T(a,b) ≤ T(a’,b)

iv) Tính kết hợp:

T(a,T(b,c)) = T(T(a,b),c)


10
Ngoài ra, một số tính chất khác cần đòi hỏi phải có trong nhiều ứng dụng
đối với phép t-norm bao gồm:
v) Tính liên tục:

T là hàm hai biến liên tục

vi) Tính lũy đẳng dưới:

T(a,b) < a

vii) Tính đơn điệu chặt:

a ≤ a’ và b ≤ b’ ⇒ T(a,a’)

N(N(a)) = a

Ví dụ 4: Các phép t-norm, t-conorm và phép phủ định hay được sử dụng
như:
TM(a,b) = min{a,b}
TP(a,b) = a.b
TL(a,b) = max{0,a+b-1}


11
a

T (a, b) = b
0

*

khi b = 1
khi a = 1
khi a ≠ 1& b ≠ 1

SM(a,b) = max{a,b}
SP(a,b) = a+b-a.b
SL(a,b) = min{1,a+b}
a

S ( a , b ) = b
0

*

i) Tính đơn điệu giảm đối với biến thứ nhất
x ≤ z ⇒ I(x,y) ≥ I(z,y), ∀y∈[0,1]
ii) Tính đơn điệu tăng đối với biến thứ hai
y ≤ u ⇒ I(x,y) ≤ I(x,u), ∀x∈[0,1]
iii) Tính chi phối của giá trị chân lý sai
I(0,x) = 1
iv) Tính trung tính của giá trị chân lý đúng
I(1,x) = x
v) Tính đồng nhất
I(x,x) = x
vi) Tính chất hoán đổi
I(x,I(y,z)) = I(y,I(x,z))
vii) Tính chất về điều kiện giới nội
I(x,y) = 1 nếu và chỉ nếu x ≤ y
viii) Tính chất khái quát hóa của phép kéo theo kinh điển
I(x,y) = I(N(y),N(x)), trong đó N là phép phủ định
ix) I là hàm liên tục theo cả hai biến.
Rõ ràng mệnh đề điều kiện ở dạng “If X is A then Y is B” thể hiện mối
quan hệ giữa hai khái niệm mờ A và B. Vì vậy, chúng cảm sinh một quan hệ
mờ R thể hiện bởi một tập mờ trên không gian tích Đề-Các U×V được xác
định bởi hàm thuộc thông qua một phép kéo theo được chọn.
Ví dụ 5. Một số dạng phép kéo theo thường dùng
Mamdani


13
I(x,y) = min{x,y}
Dạng khái quát từ phép kéo theo kinh điển
I(x,y) = S(N(x),y), hoặc
I(x,y) = S(N(x),T(x,y)), hoặc

lớp khái niệm rộng hơn có thể mô hình qua các tập mờ, đó là biến ngôn ngữ.
Định nghĩa 13. [14] Biến ngôn ngữ là một bộ năm (X,T(X),U,R,M),
trong đó X là tên biến, T(X) là tập các giá trị ngôn ngữ của biến X, U là không
gian tham chiếu hay còn gọi là miền cơ sở của biến X, R là một quy tắc ký
pháp sinh các giá trị ngôn ngữ cho T(X), M là quy tắc gán ngữ nghĩa biểu thị
bằng tập mờ trên U cho các từ ngôn ngữ trong T(X).
Ví dụ 6 Cho X là biến ngôn ngữ có tên AGE, miền tham chiếu của X là
U=[0,120]. Tập các giá trị ngôn ngữ T(AGE)={very old, old, possible old, less
old, less young, quite young, more young,…}. Chẳng hạn với giá trị ngôn ngữ
old, quy tắc gán ngữ nghĩa M cho old bằng tập mờ cho bởi ví dụ 1
M(old) = {(u,µold(u)) : u∈[0,120]}.
Chúng ta thấy rằng một biến ngôn ngữ được cấu trúc theo hướng mà
trong đó có hai quy tắc cơ bản. Thứ nhất là quy tắc cú pháp, qui định cách
thức để sinh các giá trị ngôn ngữ. Thứ hai là quy tắc ngữ nghĩa, qui định thủ
tục tính toán ngữ nghĩa của các giá trị ngôn ngữ. Ngoài các giá trị sinh
nguyên thủy, các giá trị ngôn ngữ có thể gồm các từ liên kết như and, or, not,
… và các gia tử ngôn ngữ như very, possible, less, quite, more,….Zadeh cũng
nêu ra một vài thí dụ về cách sinh ra các hàm thuộc từ các hàm thuộc đã có
như nếu A là nhãn ngôn ngữ mờ có hàm thuộc là μ A thì veryA có hàm thuộc
là (μA)2 còn lessA có hàm thuộc là căn bặc hai của μA...
Trong thực tế có nhiều biến ngôn ngữ khác nhau về giá trị sinh nguyên
thủy, tuy nhiên cấu trúc miền giá trị của chúng tồn tại một “đẳng cấu” sai


15
khác nhau bởi giá trị sinh nguyên thủy này. Đây gọi là tính phổ quát của biến
ngôn ngữ.
Khác với giá trị nguyên thủy của các biến ngôn ngữ phụ thuộc vào ngữ
cảnh, ngữ nghĩa của các gia tử và các từ liên kết hoàn toàn độc lập với ngữ
cảnh. Đây là tính độc lập ngữ cảnh của gia tử và liên kết.

cấu trúc đại số AT = (T, G, H, ≤), trong đó:
- T: Là tập cơ sở của AT.
- G: Là tập các từ nguyên thủy (tập các phần tử sinh: true, false).
- H: Là tập các toán tử một ngôi, gọi là các gia tử (các trạng từ nhấn).
- ≤: Là biểu thị quan hệ thứ tự trên các từ (các khái niệm mờ), nó được
“cảm sinh” từ ngữ nghĩa tự nhiên. Ví dụ: dựa trên ngữ nghĩa, các quan hệ thứ
tự sau là đúng: false≤ true, more true ≤ very true, very false ≤ more false,
possible true ≤ true, false ≤ possible false, …
Ta luôn giả thiết rằng các gia tử trong H là các toán tử thứ tự, nghĩa là
(∀h ∈ H, h: T → T), (∀x ∈ T) {hx ≤ x hoặc hx ≥ x}. Hai gia tử h, k ∈ H
được gọi là ngược nhau nếu (∀x ∈ T) {hx ≤ x khi và chỉ khi kx ≥ x} và
chúng được gọi là tương thích nhau nếu (∀x ∈ T) {hx ≤ x khi và chỉ khi kx ≤
x}.
Ta ký hiệu h ≥ k nếu h, k tương thích nhau và (∀x ∈ T) {hx ≤ kx ≤ x
hoặc hx ≥ kx ≥ x}.
Ngoài ra, tập H còn có thể được phân hoạch thành hai tập H+ và H- với
các gia tử trong tập H+ hay H- là tương thích nhau, mỗi phần tử trong H+
cũng ngược với bất kỳ phần tử nào trong H- và ngược lại.


17
Giả sử trong tập H+ có phần tử V (ngầm định là very – rất) và trong tập
H- có phần tử L (ngầm định là less – ít) là phần tử lớn nhất thì phần tử sinh g
∈ G là dương nếu g ≤ Vg và là âm nếu g ≥ Vg (hoặc g ∈ G là âm nếu g ≥ Lg
và là âm nếu g ≤ Lg).
Một gia tử h dương (hoặc âm) đối với một gia tử k nếu (∀x ∈ T) {hkx ≤
kx ≤ x hoặc hkx ≥ kx ≥ x} (hoặc (∀x ∈ T) { kx ≤ hkx ≤ x hoặc kx ≥ hkx ≥ x}).
T được sinh ra từ G bởi các gia tử trong H. Như vậy mỗi phần tử của T
sẽ có dạng biểu diễn là x = hnhn-1h…h1u, u ∈ G.
Tập tất cả các phần tử được sinh ra từ phần tử x có dạng biểu diễn là H(x).

dương và một cái là âm).
Đặc biệt phần đối nghịch của w được định nghĩa chính là w. Phần tử
đối nghịch của x được ký hiệu là –x với chỉ số nếu cần thiết. Nhìn chung
một phần tử có thể có nhiều phần tử đối nghịch.
Nếu mỗi phần tử của T chỉ có duy nhất một phần tử đối nghịch thì
AT được gọi là đại số gia tử đối xứng.
1.4.2.1. Một số tính chất của đại số gia tử
Định lý sau cho thấy tính thứ tự ngữ nghĩa của các hạng từ trong ĐSGT.
Định lý 2. Cho tập H- và H+ là các tập sắp thứ tự tuyến tính của ĐSGT
AX = (X, G, H, ≤). Khi đó ta có các khẳng định sau:
(1) Với mỗi u ∈ X thì H(u) là tập sắp thứ tự tuyến tính.
(2) Nếu X được sinh từ G bởi các gia tử và G là tập sắp thứ tự tuyến tính
thì X cũng là tập sắp thứ tự tuyến tính. Hơn nữa nếu u < v, và u, v là độc lập
với nhau, tức là u ∉ H(v) và v ∉ H(u), thì H(u) ≤ H(v).
Định lý tiếp theo xem xét sự so sánh của hai hạng từ trong miền ngôn
ngữ của biến X.