i

LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Tất cả tài
liệu tham khảo đều có nguồn gốc, xuất xứ rõ ràng.
Tôi xin cam đoan tất cả những nội dung trong luận văn đúng như nội dung
trong đề cương và yêu cầu của thầy giáo hướng dẫn. Nếu sai tôi xin hoàn toàn
chịu trách nhiệm trước Hội đồng khoa học và trước Pháp luật.

Thái Nguyên, tháng 11 năm 2014
Tác giả

Đào Thị Minh Hoàn


ii

LỜI CẢM ƠN
Lời đầu tiên cho phép tôi bày tỏ lòng biết ơn sâu sắc tới TS. Trần Thái
Sơn – Viện Công Nghệ Thông Tin – Viện Hàn Lâm Khoa Học và Công Nghệ Việt
Nam đã giúp đỡ và chỉ dẫn tận tình cho tôi về định hướng đề tài, hướng dẫn tôi
trong việc tiếp cận và khai thác các tài liệu tham khảo cũng như chỉ bảo cho tôi
trong quá trình tôi viết luận văn và hoàn thành luận văn.
Tôi xin chân thành cảm ơn Ban giám hiệu, Khoa sau đại học trường Đại
học Công Nghệ Thông Tin và Truyền Thông Thái Nguyên đã tạo mọi điều kiện
giúp tôi nghiên cứu và hoàn thành luận văn này.
Do điều kiện thời gian và phạm vi nghiên cứu có hạn, luận văn không
tránh khỏi những thiếu sót, tác giả luận văn kính mong nhận được sự chỉ dẫn và
góp ý thêm của các thầy giáo, cô giáo và các anh chị học viên để luận văn trở nên
hoàn thiện hơn.
Tác giả

2.1. Bài toán trích chọn luật mờ từ cơ sở dữ liệu ........................................... 23
2.1.1. Chuyển đổi CSDL số sang CSDL mờ: mục đích và phương pháp giải. .... 24
2.1.2. Bài toán hồi quy mờ ..................................................................................... 24

2.2. Xây dựng hệ luật mờ từ CSDL - nhóm giải pháp 2 giai doạn................ 28
2.3. Xây dựng hệ luật mờ từ CSDL – nhóm giải pháp 1 giai doạn. .............. 36
Chương 3:CHƯƠNG TRÌNH THỬ NGHIỆM ................................................. 38


iv

3.1. Đặt bài toán .............................................................................................. 38
3.2. Tìm kiếm hệ luật tối ưu dựa trên giải thuật di truyền lai ........................ 39
3.3. Chương trình ............................................................................................ 44
3.3.1. Cài đặt chương trình ..................................................................................... 44
3.3.2. Giao diện của chương trình .......................................................................... 44

KẾT LUẬN ......................................................................................................... 53
TÀI LIỆU THAM KHẢO .................................................................................. 54


v

DANH MỤC CÁC HÌNH
Hình 1.1: Đồ thị biểu diễn hàm thuộc của tập mờ già (old) ........................ 6
Hình 1.2: Mã hóa cá thể từ không gian các lời giải của bài toán ............... 18
Hình 2.1: Các bộ phận của không gian đầu vào và đầu ra thành các vùng
mờ có chức năng thành viên tương ứng. (a) rn(ri). (b) 01(12). (c) oi(y). .. 36
Hình 3.1: Sơ đồ mã hóa cá thể chọn hệ luật cho thuật toán SGA .............. 40


MF

Hàm thuộc

FB

CSDL mờ

SGA

Thuật toán di truyền lai


1

MỞ ĐẦU
Khai phá dữ liệu, rộng hơn là khai phá tri thức đã và đang thu hút sự chú ý
mạnh mẽ của các nhà nghiên cứu trên thế giới và ở Việt Nam. Do sự bùng nổ
thông tin trong mọi lĩnh vực của đời sống, đòi hỏi phải có những phương pháp
khoa học và công nghệ để khai thác có hiệu quả từ khối lượng thông tin khổng lồ
những tri thức cần thiết giúp cho con người hoạch định những chiến lược, chính
sách cho xã hội. Hồi quy (regression), một trong những hướng nghiên cứu chính
trong khai phá dữ liệu, có nhiệm vụ từ những tập dữ liệu mẫu rút ra các quy luật
để dự báo mô hình và kết quả có thể xẩy ra trong dữ liệu tương lai. Hồi quy toán
học đã phát triển từ khá lâu và cũng đạt được nhiều kết quả tốt đẹp, tuy nhiên so
với yêu cầu thực tế thì vẫn còn nhiều việc phải làm, như tăng tính chính xác của
mô hình, giảm thời gian tính toán đến mức tối thiểu, nghiên cứu các mối tương
quan nhiều biến phức tạp... Với sự phát triển mạnh mẽ của công nghệ thông tin,
gần đây nhiều hướng nghiên cứu mới giải bài toán hồi quy đã ra đời, trong đó có
hướng nghiên cứu hồi quy mờ dựa trên hệ luật mờ đặc biệt được quan tâm do

Phần mở đầu nêu mục đích yêu cầu và cách tiếp cận giải bài toán hồi quy
mờ thông qua hệ luật mờ Mandani theo cách tiếp cận lý thuyết tập mờ.
Chương 1: Tập mờ và giải thuật di truyền
Trong chương này trình bày các kiến thức cơ bản về tập mờ và giải thuật di
truyền.
Chương 2: Giải bài toán xây dựng hệ luật mờ theo cách tiếp cận của lý
thuyết tập mờ. Ứng dụng vào bài toán hồi quy mờ
Đề xuất cách xây dựng hệ luật mờ Mandani và sử dụng hệ luật mờ này giải
quyết bài toán hồi quy mờ.
Chương 3: Chương trình thử nghiệm
Trình bày chương trình thử nghiệm minh họa cho cách tiếp cận lý thuyết
tập mờ trong việc giải bài toán hồi quy mờ.


3

Chương 1
TẬP MỜ VÀ GIẢI THUẬT DI TRUYỀN
1.1. Tổng quan về tập mờ
1.1.1. Mở đầu
Lý thuyết tập mờ được đề xuất bởi L. A. Zadeh năm 1965, và có lẽ đến nay
thuật ngữ “fuzzy” trở nên rõ ràng đối với các nhà nghiên cứu và các kỹ sư. Nó đã
và đang được tiếp tục nghiên cứu rất mạnh mẽ. Bằng các phương pháp tiếp cận
khác nhau, các nhà nghiên cứu như Dubois, Prade, Mamdani, Tagaki, Sugeno,…
đã đưa ra những kết quả cả về lý thuyết và ứng dụng trong các bài toán điều
khiển mờ, khai phá dữ liệu mờ, cơ sở dữ liệu mờ, các hệ hỗ trợ và quyết định....
Hệ suy diễn mờ áp dụng cho lập luận xấp xỉ được phát triển dựa trên lý
thuyết tập mờ, với những ràng buộc nhất định, được xem như là một bộ xấp xỉ vạn
năng. Hơn nữa, thế mạnh của hệ mờ là có thể xấp xỉ các hành vi hệ thống mà ở đó
các hàm giải tích hoặc các quan hệ dạng số không tồn tại. Vì vậy, hệ mờ có tiềm

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
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 định như sau:

AB(u) = max(A(u), B(u)), uU,
AB(u) = min(A(u), B(u)), uU,
A~(u) = 1- A(u), uU.
Hay viết ở dạng thu gọn là

AB(u) = A(u)B(u)),
AB(u) = A(u) B(u)).
Ví dụ 1.2. Xét tập nền U = {1,2,3,4,5,6,8,9,10,11} là tập các giá trị trong
thang điểm 10 đánh giá kết quả học tập của học sinh. Hai tập mờ G và K tương
ứng là hai khái niệm mờ về năng lực học giỏi và học kém, với hàm thuộc được
cho dưới dạng bảng như sau:
uU

1

2

3

4

5

6

7


1.0

0.9

0.8

0.6

0.4

0.2

0.0

0.0

0.0

0.0


7
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


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

1.0

1.0

1.0

 (u1 ,..., u1 ) / (u1 ,..., u1 )

Trong đó (u1,…,un) là hàm thuộc của tập mờ R. Dấu  biểu diễn hình thức
của hàm thuộc, có thể một trong ba trường hợp là hữu hạn hoặc đếm được hoặc
liên tục.
Quan hệ mờ cũng có các phép tính cơ bản như trên tập mờ vì bản thân nó
cũng là tập mờ. Ngoài ra, quan hệ mờ có những phép tính đặc thù riêng mà trên
tập mờ không có, đó là phép hợp thành dưới đây.
Định nghĩa 1.7. Cho R là một quan hệ mờ trên UV và S là quan hệ mờ
trên VW. Khi đó, phép hợp thành của hai quan hệ này là một quan hệ trên UW,
được ký hiệu là RS và được định nghĩa như sau:
RS = vV [R(u,v)S(v,w)]/(u,w)
trong đó  là một phép tính 2-ngôi trong [0,1] có tính giao hoán, kết hợp và
phân phối đối với phép max . Nếu  là phép min , thì ta có phép hợp thành
max-min, nếu  là phép nhân số học thì ta có phép hợp thành max-product.


8
Ví dụ 1.3. Cho U = {u1, u2, u3}, V = {v1, v2} và W = {w1, w2}, với quan hệ
mờ R trên UV và S trên VW được cho hàm thuộc dưới dạng ma trận
v1

v2

w1
w2
u1  0.4 1 
v
0.2
0.8

đề phức tạp cố hữu, một cách tự nhiên là tìm cách sử dụng các biến ngôn ngữ, đó
là các biến mà giá trị của chúng không phải là số mà là các từ hoặc các câu
trong ngôn ngữ tự nhiên hoặc nhân tạo. Động lực cho việc sử dụng các từ, các
câu hơn các số là ở chỗ đặc trưng ngôn ngữ của các từ và các câu thường ít xác
định cụ thể hơn của các số”, và ông đã đưa ra một 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 1.8. 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á


9
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ụ 1.4. 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.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,….
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 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ữ


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

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’) < T(b,b’)

Định nghĩa 1.10. Một hàm 2-biến S : [0,1][0,1]  [0,1] được gọi là phép
t-conorm nếu nó thỏa các tính chất sau với a,a’,b,c [0,1]:
i) Tính giới nội:

S(a,0) = a

ii) Tính giao hoán:

S(a,b) = S(b,a)

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

a a’S(a,b)  S(a’,b)

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

S(a,S(b,c)) = S(S(a,b),c)

Như vậy, chỉ có hai tính chất điều kiện biên và giới nội làm nên sự khác


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

*

khi b  0
khi a  0
khi a  0 & b  0

N(a) = 1-a.
Định nghĩa 1.12. Ba phép tính t-normT, t-conorm S và phép phủ định N
được gọi là một hệ đối ngẫu (T,S,N) nếu chúng thỏa điều kiện sau:
N(S(a,b)) = T(N(a),N(b)), a,b[0,1].
Việc áp dụng các phép t-norm, t-conorm và phép phủ định cho việc tính
toán các toán tử hội, tuyển và phủ định trong lôgic mờ làm tăng tính mềm dẻo
trong ứng dụng. Thực vậy, khi hai mệnh đề “X is A” và “X is B” có giá trị chân lý
được biểu thị bởi hai hàm thuộc tương ứng A và B trên không gian tham chiếu
U và V thì mệnh đề mờ “X is A and B” có hàm thuộc biểu thị giá trị chân lý là

AB = T(A,B), với T là một t-norm nào đó. Tương tự, mệnh đề “X is A or B” có
hàm thuộc là AB = S(A,B) và mệnh đề “X is not A” có hàm thuộc là ~A =
N(A), ở đây S là một t-conorm và N là một phép phủ định được chọn nào đó.
Các mệnh đề mờ cùng với giá trị chân lý của chúng là những đối tượng
nghiên cứu chính của lôgíc mờ. Trong đó, một dạng mệnh đề mờ thường biểu

Ví dụ 1.6. 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
I(x,y) = S(T(N(x),N(y)),y), với T, S và N là các phép tnorm, t-conorm và phép phủ định.
 Reichenbach
I(x,y) = 1-x+x.y
 Lukasiewicz
I(x,y) = min{1, 1-x+y}.
Một cách tiếp cận khác, phép kéo theo được định nghĩa thông qua phép tnorm bằng công thức sau:
I(x,y) = sup{ u[0,1] : T(x,u)  y}.
Định lý sau đây cho chúng ta xem xét liệu phép kéo theo như thế nào sẽ
thỏa mãn tất cả các tính chất trong định nghĩa 1.13.
Định lý 1.1. Một hàm 2-biến I : [0,1]2 [0,1] thỏa các tính chất từ i) đến
ix) trong định nghĩa 1.13 nếu và chỉ nếu có tồn tại một hàm liên tục đơn điệu tăng
thực sự f : [0,1]  [0,+) sao cho f(0) = 0 và
I(x,y) = f-1(f(1)-f(x)+f(y)), với x,y  [0,1], và
N(x) = f-1(f(1)-f(x)), với x [0,1].
Tuy nhiên, bản chất ngữ nghĩa của phép kéo theo mờ trong lập luận của con
người rất phức tạp, khó có một hệ tiên đề chung cho mọi tình huống. Vì vậy, các
tính chất ở định nghĩa 1.13 không bắt buộc mọi phép kéo theo mờ đều phải thỏa
mãn. Hơn nữa, cũng không có quyền đặt ra các yêu cầu về một tính chất nào đó
khác mà một phép kéo theo cần phải có. Chỉ có ứng dụng thực tiễn là tiêu chuẩn
cuối cùng chứng minh tính phù hợp của một định nghĩa phép kéo theo mờ.
1.1.5. Lập luận xấp xỉ


Trong đó X1, X2,…, Xnvà Y là các biến ngôn ngữ, N là số biến vào và M là
số luật mờ, Ai,j (i=1,…,M và j=1,…,N) là các tập mờ trên không gian nền U1,
U2,…,Un và V tương ứng. Tìm được tập mờ B’ có nghĩa là chúng ta đã lập luận từ
sự kiện X1 is A1’ AND … AND XN is AN’ dựa trên các tiền đề dạng luật If X1 is
Ai,1 AND… AND XN is Ai,N then Y is Bi (i=1,…,M).
Vì rằng chúng ta đang ở trong môi trường thông tin mờ, không chắc chắn,
nên sẽ 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 đó.


15
Áp dụng quy tắc modus ponens tổng quát hóa, chúng ta xét mỗi luật mờ
như là một quan hệ mờ Ri trên không gian tích Đề-các U1…UnV có dạng:
Ai,1… Ai,n Bi,
trong đó,  là phép hợp của các tập mờ và  là phép kéo theo mờ. Áp dụng một
toán tử t-norm Tex mở rộng cho phép hội  và một phép kéo theo I nào đó, ta có
hàm thuộc của quan hệ mờ trên là

 Ri  I (Tex (  Ai ,1 ,...,  Ai ,N ),  Bi )

(1.1)

Mô hình mờ ở đây được coi là tuyển của các luật, do vậy áp dụng phép hội
để kết nhập các quan hệ mờ Ri ở trên bằng toán tử t-conorm Sex mở rộng như sau:
R = R1… RN,
với  là phép hợp của các tập mờ, hay hàm thuộc của nó là
 R  Sex (  R ,...,  R ) .

(1.2)

mờ B’ như sau:

 B ' (v)  sup

( u1 ,...,u1 )U



N
j 1





 A (u j )  o   iM1 I ( Nj 1 A (u j ),  B (v)) 
'
j

 

i, j

i

(1.4)

với U = U1…UN ,  là ký hiệu của phép t-norm Texmở rộng N ngôi và  là ký
hiệu phép t-conorm Sex mở rộng N ngôi. Phép  là min, hoặc product, hoặc một
phép tính 2-ngôi trong [0,1] có tính giao hoán, kết hợp và phân phối đối với phép

Định lý này cho thấy mọi hàm thực liên tục trên một tập compact có thể
được xấp xỉ với độ chính xác tùy ý bởi một hệ mờ F. Tuy nhiên, nó mới chỉ ra có
tồn tại một hệ mờ như vậy nhưng không cho biết rõ tham số của hệ. Bắt buộc
chúng ta phải xây dựng một chiến lược tìm kiếm và thiết lập các yếu tố này.
Chẳng hạn sử dụng cơ chế học của mạng nơron, hoặc tối ưu theo giải thuật di
truyền để thực hiện điều này.


17
1.2. Giải thuật di truyền
1.2.1. Những khái niệm cơ bản về giải thuật di truyền
Thế giới mà chúng ta thấy ngày hôm nay, trong đó có rất nhiều loài khác
nhau, với sự thích nghi cao theo môi trường sống và sự cân bằng sinh thái, là sản
phẩm của 3 tỷ năm tiến hóa, một quá trình dựa trên sự sinh sản hữu tính và vô
tính, chọn lọc tự nhiên, đột biến,… Nếu nhìn vào bên trong chúng ta thấy sự
phức tạp và khả năng thích nghi của các loài có được bằng việc cải tiến và kết
hợp các gen qua một quá trình rất dài. Giải thuật di truyền (genetic algorithm –
GA), được đề xuất bởi J. H. Holland (1967), là sự mô phỏng quá trình tiến hóa.
Tuy nhiên, ở một góc độ khác, giải thuật di truyền chính là phương pháp tối ưu
theo xác suất dựa trên nguyên lý tiến hóa. Đến nay đã được nhiều tác giả nghiên
cứu phát triển và ứng dụng, kết hợp với nhiều mô hình khác.
Xét ở góc độ GA là một phương pháp tối ưu, khi đó, một bài toán tối ưu
được phát biểu tổng quát như sau:
Tìm một x0∈X sao cho f đạt max tại x0, trong đó f : X → R là một hàm thực
bất kỳ, tức là : f(x0) = maxx∈X f(x)
Thực tế, một số trường hợp việc tối ưu toàn cục là rất khó và đôi khi là
không thể theo cách giải quyết toán học thông thường. Vì vậy, tùy theo bài toán
mà chúng ta quan tâm đến giá trị của x sao cho hàm mục tiêu f càng cao càng tốt.
Không gian tìm kiếm X được xem như môi trường (hay còn gọi là quần thể) bao
gồm các cá thể (individuals) cạnh tranh với nhau, trong đó hàm f ánh xạ mỗi cá

chưa thỏa mãn sang bước tiếp theo, ngược lại dừng
thuật toán.
Bước 3: Chọn lọn (selection) các cá thể trong Bt làm bố mẹ
(parent) để lai ghép.
Bước 4: Thực hiện lai ghép (crossover) các cá thể bố mẹ tạo
thành các cá thể con (offspring).
Bước 5: Đột biến (mutation) trên các cá thể con.
Bước 6: Tái tạo (reproduction) từ các cá thể con và bố mẹ tạo ra
quần thể mới.
Bước 7: Tăng chỉ số thế hệ t lên 1 và lặp lại bước 2.

Theo thuật toán, mỗi lần tiến hóa là việc chuyển từ một thế hệ này sang một
thế hệ khác, với hy vọng tốt hơn dựa trên hàm đánh giá f. Quá trình này bao gồm
4 phép cơ bản (gọi là toán tử gen) sau:


19
Chọn lọc: Kỹ thuật chọn lọc các cá thể trong quần thể hiện tại làm bố mẹ để
lai ghép tạo ra các cá thể con, dựa trên hàm đánh giá độ phù hợp f.
Lai ghép: Phương pháp trộn thông tin gen của hai cá thể bố mẹ, với mã hóa
được chọn phù hợp, hai cá thể bố mẹ tốt sẽ sinh ra hai cá thể con tốt.
Đột biến: Trong tiến hóa tự nhiên, các gen bị thay đổi một cách ngẫu nhiên
làm cho biến dạng, dưới tác động của bức xạ gama chẳng hạn. Trong GA, phép
đột biến được tự nhiên hóa theo cách biến dạng ngẫu nhiên chuỗi gen với một
xác suất cho trước. Tác dụng tích cực của đột biến là đảm bảo được tính đa dạng
của của gen và tránh khỏi tối ưu địa phương.
Tái tạo: Tạo ra một thế hệ mới gồm những cá thể tốt hơn từ các cá thể bố
mẹ và con sau khi đã đột biến.
Nằm trong lớp các bài toán tối ưu, giải thuật di truyền có những khác biệt
cơ bản, so với các phương pháp truyền thống như phương pháp Niu-tơn hoặc