ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
LÊ CẢNH THƠ
PHƯƠNG PHÁP TINH CHỈNH THAM SỐ MỜ
GIA TỬ CỦA HỆ MỜ DẠNG LUẬT PHÂN LỚP
VÀ ỨNG DỤNG
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
THÁI NGUYÊN - 2015
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
LÊ CẢNH THƠ
PHƯƠNG PHÁP TINH CHỈNH THAM SỐ MỜ GIA TỬ
CỦA HỆ MỜ DẠNG LUẬT PHÂN LỚP
VÀ ỨNG DỤNG
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
HƯỚNG DẪN KHOA HỌC: TS DƯƠNG THĂNG LONG
THÁI NGUYÊN - 2015
i Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
LỜI CAM ĐOAN
Với mục đích nghiên cứu, tìm hiểu để nâng cao kiến thức và trình độ
chuyên môn để áp dụng trong các bài toán cụ thể trong tương lai nên tôi đã
làm luận văn này một cách nghiêm túc và hoàn toàn trung thực. Nội dung
luận văn do tự tôi tìm hiểu và hoàn thành.
Trong luận văn, tôi có sử dụng tài liệu tham khảo của một số tác giả trong
và ngoài nước để hoàn thành luận văn được nêu ở phần tài liệu tham khảo.
Tôi xin cam đoan và chịu trách nhiệm về nội dung, sự trung thực trong
luận văn tốt nghiệp Thạc sỹ của mình.
Thái Nguyên, tháng 4 năm 2015
ii Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Học viên
LỜI CẢM ƠN
Những kiến thức căn bản trong luận văn này là kết quả của quá trình tự
nghiên cứu trong quá trình công tác và hai năm học Thạc sỹ (2012 - 2014) tại
Trường Đại học Công nghệ thông tin và Truyền thông Thái Nguyên. Dưới sự
giảng dạy, đào tạo và dìu dắt trực tiếp của các thầy cô trong trường và Viện
Công nghệ thông tin Việt Nam.
Tôi xin bày tỏ lời cảm ơn chân thành tới các thầy cô trong Khoa Công
nghệ thông tin, Phòng Đào tạo, Phòng Công tác học sinh sinh viên, Phòng Đào
tạo 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 điều kiện thuận lợi cho tôi trong thời gian học tập tại trường.
Tôi xin bày tỏ lòng biết ơn chân thành, lời cảm ơn sâu sắc nhất đối với
thầy giáo TS Dƣơng Thăng Long đã trực tiếp hướng dẫn, định hướng cho tôi
giải quyết các vấn đề trong luận văn.
Tôi cũng xin cảm ơn đến người thân, bạn bè và các bạn đồng môn
lớp cao học khóa 11, đã ủng hộ và giúp đỡ tôi trong quá trình làm luận văn
tốt nghiệp.
Thái Nguyên, ngày 6 tháng 4 năm 2015
Học viên
iii Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Lê Cảnh Thơ
MỤC LỤC
LỜI CAM ĐOAN .............................................................................................................................. i
LỜI CẢM ƠN ................................................................................................................................... iii
MỤC LỤC ......................................................................................................................................... iv
DANH MỤC CÁC KÝ HIỆU, CHỮ CÁI VIẾT TẮT .................................................................. vi
DANH MỤC HÌNH VẼ ................................................................................................................. viii
LỜI NÓI ĐẦU .................................................................................................................................. 1
CHƢƠNG 1: CƠ SỞ VỀ HỆ MỜ DẠNG LUẬT DỰA TRÊN ĐẠI SỐ GIA TỬ ...................... 3
1.1 Khái quát về lập luận mờ .......................................................................................................... 3
1.1.1 Định nghĩa tập mờ ................................................................................................................... 3
1.1.2 Số mờ ........................................................................................................................................ 3
1.1.3 Phân hoạch mờ ........................................................................................................................ 5
1.1.4 Các phép tính trên tập mờ Zadeh ............................................................................................ 6
1.1.4.5 Phép kéo theo ........................................................................................................................ 8
1.1.5 Biến ngôn ngữ .......................................................................................................................... 9
1.1.6 Suy luận mờ ............................................................................................................................ 11
1.2 Đại số gia tử trong lập luận mờ ............................................................................................... 12
1.2.1 Đại số gia tử (ĐSGT) .............................................................................................................. 12
1.2.2 Tính chất của đại số gia tử tuyến tính ................................................................................... 13
1.2.3 Đại số 2 gia tử ......................................................................................................................... 14
1.2.4 Định lượng ngữ nghĩa trong đại số gia tử ............................................................................ 15
1.2.5 Hệ khoảng tính mờ ................................................................................................................. 19
1.3 Kết luận chƣơng 1 .................................................................................................................... 21
CHƢƠNG 2: PHƢƠNG PHÁP TINH CHỈNH THAM SỐ MỜ GIA TỬ CỦA HỆ MỜ DẠNG LUẬT PHÂN LỚP ......................................................................................................................... 22
2.1 Phƣơng pháp xây dựng hệ mờ dạng luật phân lớp ............................................................... 22
2.1.1 Bài toán phân lớp ................................................................................................................... 22
2.1.2 Mô hình hệ mờ dạng luật giải bài toán phân lớp ................................................................. 23
2.1.3 Thuật toán sinh luật mờ dựa trên hệ khoảng tính mờ ......................................................... 26
2.2 Sự ảnh hƣởng của tham số mờ gia tử đối với bài toán phân lớp ......................................... 34
2.3 Phƣơng pháp tinh chỉnh bằng trực quan kinh nghiệm của ngƣời dùng ............................. 36
2.4 Tinh chỉnh bằng phƣơng pháp tối ƣu dựa trên giải thuật di truyền ................................... 46
iv Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
2.4.1 Giải thuật di truyền ................................................................................................................ 46
2.4.2 Sơ đồ tổng thể của giải thuật di truyền - GA ......................................................................... 47
2.4.3Áp dụng GA tìm kiếm tham số tối ưu ..................................................................................... 48
2.5 Kết luận chƣơng 2 .................................................................................................................... 55
CHƢƠNG 3: XÂY DỰNG CHƢƠNG TRÌNH ........................................................................... 56
VÀ ỨNG DỤNG THỬ NGHIỆM ................................................................................................. 56
3.1. Xây dựng ứng dụng ................................................................................................................. 56
3.2 Bài toán phân lớp hạt giống lúa mì (Seeds)............................................................................ 56
3.3 Bài toán phân loại ngƣời bị thoát vị đĩa đệm Vertebral Column ........................................ 60
3.4 Kết luận chƣơng 3 .................................................................................................................... 64
KẾT LUẬN ..................................................................................................................................... 65
TÀI LIỆU THAM KHẢO ............................................................................................................. 66
v Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
DANH MỤC CÁC KÝ HIỆU, CHỮ CÁI VIẾT TẮT
Các ký hiệu:
AX Đại số gia tử tuyến tính
AX2 Đại số 2 gia tử
(h), fm(x) Độ đo tính mờ gia tử h và của hạng từ x
Giá trị định lượng theo điểm của giá trị ngôn ngữ
Hàm định lượng của giá trị ngôn ngữ A (đo độ thuộc của v) A(v)
Khoảng tính mờ của giá trị ngôn ngữ
Tập các hạng từ có độ dài đúng k Xk
Tập các hạng từ có độ dài không quá k X(k)
Hệ khoảng tính mờ mức k của các giá trị ngôn ngữ Ik
Hệ khoảng tính mờ từ mức 1 đến mức k của các giá trị ngôn ngữ I(k)
Các chữ viết tắt:
ĐSGT Đại số gia tử
ĐS2GT Đại số 2 gia tử
SGA Simulated Annealing - Genetic Algorithm
IFRG1 Initial Fuzzy Rules Generation 1
HAFRG Hedge Algebras based Fuzzy Rules Generation
vi Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
FPO-SGA Fuzzy Parameters Optimization - SGA
DANH MỤC CÁC BẢNG
Bảng 3.1: Các tham số gia tử tinh chỉnh bằng trực quan của bài toán Seeds
Bảng 3.2: Các tham số gia tử tinh chỉnh tự động của bài toán Seeds
Bảng 3.3: So sánh số lỗi và tỉ lệ phân lớp giữa các bộ tham số bài toán Seeds
Bảng 3.4:Các tham số gia tử tinh chỉnh bằng trực quan của bài toán Vertebral
Column
Bảng 3.5:Các tham số gia tử tinh chỉnh tự động của bài toán Vertebral
Column
Bảng 3.6:So sánh số lỗi và tỉ lệ phân lớp giữa các bộ tham số bài toán
vii Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Vertebral Column
DANH MỤC HÌNH VẼ
Hình 1.1: Phép giao của hai tập mờ
Hình 1.2: Phép hợp của hai tập mờ
Hình 1.3: Độ đo tính mờ của biến “NHIỆT ĐỘ”
Hình 1.4: Khoảng tính mờ của các hạng từ của biến “NHIỆT ĐỘ”
Hình 2.1: Hàm định lượng tam giác của các hạng từ
Hình 2.2: Hàm định lượng hình thang của các hạng từ
Hình 2.3: Sơ đồ các bước chính của thuật toán di truyền (GA)
Hình 3.1 Sơ đồ phân bố dữ liệu giữa các lớp của bài toán Seeds
viii Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Hình 3.2 Sơ đồ phân bố dữ liệu giữa các lớp của bài toán Vertebral Column
LỜI NÓI ĐẦU
Ngôn ngữ của con người được hình thành một cách tự nhiên trong quá
trình phát triển của loài người, trước hết nhằm mục đích giải quyết nhu cầu
trao đổi thông tin giữa con người với con người, trong đó chúng ta dùng ngôn
ngữ để giải thích các hiện tượng sự vật trong tự nhiên. Tuy nhiên trước sự vô
hạn của thế giới tự nhiên, ngôn ngữ lại có giới hạn nên khó tránh khỏi những
từ, cụm từ không chính xác hoặc mơ hồ, ví dụ như: hơi nóng, rất đẹp, hơi
thấp, rất dài… Con người với khả năng tư duy, lập luận dựa trên sự hữu hạn
của ngôn ngữ đã xây dựng, khám phá tri thức khoa học, cải tạo thế giới tự
nhiên nhằm thúc đẩy sự phát triển của loài người ngày càng tốt đẹp, hoàn
thiện hơn.
Giáo sư Lotfi A. Zadeh là người tiên phong trong lĩnh vực công nghệ
logic mờ. Từ những khái niệm mơ hồ, không rõ ràng không chắc chắn ông đã
đề xuất khái niệm mờ và tập mờ là hình thức hóa toán học được xác định bởi
các hàm thuộc. Dựa trên lý thuyết tập mờ của L.A. Zadeh các nhà khoa học
đã phát triển theo nhiều hướng khác nhau, trong đó có các phương pháp xây
dựng hệ mờ phân lớp dạng luật dựa trên ngữ nghĩa của đại số gia tử. Phương
pháp này nhằm mang đến tính trực quan, dễ hiểu của hệ luật cho người dùng,
đồng thời để đạt được hai mục tiêu là: thứ nhất hiệu quả phân lớp của hệ càng
cao càng tốt; thứ 2 là tính phức tạp của hệ càng nhỏ càng tốt. Để thực hiện
được các yêu cầu trên trong việc xây dựng hệ mờ phân lớp dạng luật dựa trên
ngữ nghĩa của đại số gia tử, còn phải tinh chỉnh tham số mờ gia tử của hệ mờ
dạng luật phân lớp sao cho phù hợp để đạt được kết quả tối ưu tức là đạt được
hai mục tiêu trên.
Vì vậy, tên đề tài được chọn là:
“Phương pháp tinh chỉnh tham số mờ gia tử của hệ mờ dạng luật
1
phân lớp và ứng dụng”
Nội dung luận văn được bố cục như sau:
Chương 1: Cơ sở về hệ mờ dạng luật dựa trên đại số gia tử
Chương 2: Phương pháp tinh chỉnh tham số mờ gia tử của hệ mờ dạng
luật phân lớp
Chương 3: Xây dựng chương trình và ứng dụng thử nghiệm
Luận văn nghiên cứu những ứng dụng của đại số gia tử vào hệ mờ dạng
luật phân lớp, đồng thời tìm hiểu những ảnh hưởng của tham số mờ gia tử để
từ đó tinh chỉnh tham số trong hệ mờ dạng luật phân lớp để đạt đươc kết quả
tối ưu cho bài toán ứng dụng. Đây là một vấn đề mới và khá phức tạp, mặt
khác do trình độ và thời gian có hạn nên luận văn không tránh khỏi những
thiếu sót. Rất mong được sự đóng góp ý kiến của các thầy, cô để luận văn
2
được hoàn thiện hơn tạo tiền đề cho các nghiên cứu tiếp theo.
CHƢƠNG 1: CƠ SỞ VỀ HỆ MỜ DẠNG LUẬT DỰA TRÊN ĐẠI SỐ
GIA TỬ
1.1 Khái quát về lập luận mờ
Lý thuyết tập mờ được L. A. Zadeh đưa ra năm 1965, từ đó lý thuyết
tập mờ, logic mờ được nhiều tác giả quan tâm nghiên cứu bằng các cách tiếp
cận khác nhau và ứng dụng vào trong các lĩnh vực như lý thuyết điều khiển,
hệ thống xã hội, trí tuệ nhân tạo…
1.1.1 Định nghĩa tập mờ
Định nghĩa 1.1[1]: Cho 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ở một hàm 𝜇𝐴(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 𝜇𝐴(x)
biểu diễn mức độ thuộc của x trong 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[1].
Hay A được gọi là tập mờ khi và chỉ khi:
(1.1) A = {(x,𝜇𝐴(x) x∈U, 𝜇𝐴(x): U→ [0,1]}
Trong đó 𝜇𝐴(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
(1.2) A = {(x,𝜇𝐴(x) x ∈ U, 𝜇𝐴(x): U→ {0,1}}
Khi đó hàm thuộc𝜇𝐴(x) chỉ nhận hai giá trị 0 và 1.
1.1.2 Số mờ
Định nghĩa 1.2[1]: Tập mờ A trên đường thẳng số thực R là một số mờ, nếu:
1/ A chuẩn hóa, tức là có điểm x’ sao cho 𝜇𝐴(x’) = 1
2/ Ứng với mỗi 𝛼 ∈ R, tập mức {x: 𝜇𝐴(x) ≥ 𝛼 } là đoạn đóng trên R
3
3/ 𝜇𝐴(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:
0 nếu𝑥 ≤ 𝑎
𝑥 − 𝑎 𝑏 − 𝑎 nếu𝑎 ≤ 𝑥 ≤ 𝑏
𝜇𝐴 𝑥 = 1 nếu𝑥 = 𝑏
𝑥 − 𝑏 𝑐 − 𝑏 nếu𝑏 ≤ 𝑥 ≤ 𝑐
1
0
z
b
c
z
0 nếu𝑥 = 𝑐
a
b.Số mờ hình thang A(a, b, c, d) được sác định bởi 4 tham số và hàm
thuộc cho bởi:
0 nếu𝑥 ≤ 𝑎
𝜇𝐴 𝑥 =
nếu𝑎 ≤ 𝑥 ≤ 𝑏 𝑥 − 𝑎 𝑏 − 𝑎 1 nếu𝑏 ≤ 𝑥 ≤ 𝑐 nếu𝑐 ≤ 𝑥 ≤ 𝑑 𝑥 − 𝑐 𝑑 − 𝑐
1
0
z
d
a
b
c
4
0 nếu𝑥 = 𝑑
c.Số mờ dạng hàm Gauss có hàm thuộc cho bởi:
(𝑥−𝑐)2 (2σ)2 nếu x − c ≤ 𝑑𝛼 0 nếu x − c ≥ 𝑑𝛼
𝜇𝐴 𝑥 = 𝑒
1
0
z
Trong đó 𝑑𝛼 là số dương được chọn thích hợp.
Khái niệm về phân hoạch mờ (fuzzy partition) cũng là một trong khái niệm
quan trọng trong việc tiếp cận giải quyết bài toán phân lớp.
1.1.3 Phân hoạch mờ
Định nghĩa 1.3[1]: Cho p điểm cố định m1 [a, b]⊂R. Khi đó tập gồm p tập mờ A1, A2,…, Ap(với 𝜇𝐴1, 𝜇𝐴2, …, 𝜇𝐴𝑝 là các hàm thuộc tương ứng) định nghĩa trên U được gọi là một phân hoạch mờ của U nếu các điều kiện sau thỏa mãn, ∀k=1,…,p: 1) 𝜇𝐴𝑘 (mk) = 1 (mk được gọi là một điểm trong nhân của Ak); 2) Nếu x∉ [mk-1, mk+1], 𝜇𝐴𝑘 = 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 5 một lớp của phân hoạch này với độ thuộc nào đó khác không). 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{𝜇𝐴(x), 𝜇𝐵(x)}} Ví dụ: Cho U = {1, 2, 3, 4, 5, 6, 7} và hai tập mờ A, B như sau: A = {(1,0), (2,0.4), (3,0.8), (4,0.3), (5,0.2), (6,0.5), (7,0.1)} B = {(1,0.2), (2,0.5), (3,0.7), (4,0.2), (5,0.4), (6,0.3), (7,0.6)} Khi đó : C = A ∩ B = {(1,0), (2,0.4), (3,0.7), (4,0.2), (5,0.2), (6,0.3), (7, 0.1)} Hình 1.1 Phép giao của hai tập mờ Phép hợp (Union): Hợp của hai tập mờ A và B là tập mờ C được định nghĩa như sau: C = A∪B = {{(x, 𝜇𝐶(x))| x ∈ U, 𝜇𝐶(x) = max{𝜇𝐴(x), 𝜇𝐵(x)}} Ví dụ: 6 Cho U = {1, 2, 3, 4, 5} và hai tập mờ A, B như sau: A = {(1,0), (2,0.4), (3,0.8), (4,0.3), (5,0.2), (6,0.5), (7,0.1)} B = {(1,0.2), (2,0.5), (3,0.7), (4,0.2), (5,0.4), (6,0.3), (7,0.6)} Khi đó: C = A ∪ B = {(1,0.2), (2,0.5), (3,0.8), (4,0.3), (5,0.4), (6,0.5),(7, 0.6)} Hình 1.2 Phép hợp của hai tập mờ 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. Định nghĩa 1.4 [4]: Hàm n: [0, 1] [0, 1] không tăng thoả mãn các điều kiện n(0) = 1, n(1) =0 gọi là hàm phủ định. 7 Hàm n là phép phủ định mạnh, nếu n giảm chặt và n(n(x)) = x với mỗi x Ví dụ: n(x) = 1- x, n(x) = 1- x2 1.1.4.3 Phép hội Phép hội (vẫn quen gọi là phép AND – conjunction) là một trong những phép toán cơ bản nhất. Nó cũng là cơ sở để định nghĩa phép giao của hai tập mờ. Định nghĩa 1.5[4]: Hàm T: [0, 1] x[0, 1] [0, 1] là một phép hội hay t – chuẩn (t- norm) nếu thoả mãn các điều kiện sau: 1) T(1, x) = x với mọi 0 x 1 2) T có tính giao hoán, tức là T(x, y) = T(y, x) với mọi 0 x, y 1 3) T không giảm theo nghĩa T(x, y) T(u,v) với mọi x u, y v 4) T có tính kết hợp : T(x, T(y, z)) = T(T(x, y), z) với mọi 0 x, y 1 Ví dụ về một số t – chuẩn T(x, y) = min(x, y) ; T ( x, y ) = x.y ; T(x,y) = max(x+y -1, 0) 1.1.4.4 Phép tuyển Giống như phép hội, phép tuyển hay toán tử logic OR thông thường cần thoả mãn các tính chất sau: Định nghĩa 1.6[1]: Hàm S : [0, 1]x[0, 1] [0, 1] gọi là phép tuyển hay là t - đối chuẩn (t – conorm) nếu thoả mãn các tiên đề sau: 1) S(0, x) = x với mọi 0 x 1 2) S có tính giao hoán: S(x, y) = S(y, x) với mọi 0 x, y 1 3) S không giảm theo nghĩa s(x, y) s(u, v) với x u, y v 4) S có tính kết hợp S(x, S(y,z)) = S(S(x, y), z) với mọi 0 x, y, z 1 Ví dụ: Một số phép tuyển: S(x, y) = max(x, y) ; S (x, y) = x+ y – xy ; S(x, y) = min( x+ y -1 , 0), ….. 8 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 Sau đây là một số dạng của phép kéo theo: 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ộ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: Định nghĩa 1.6[1] : Biến ngôn ngữ được xác định bởi một bộ 5 thành phần (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 9 R – là một số quy tắc cú pháp sinh các giá trị ngôn ngữ trong 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ụ: Cho biến ngôn ngữ: Nhiệt độ X = Nhiệt độ T(X) = {Rất lạnh, Lạnh, Hơi lạnh, Bình thường, Hơi nóng, Nóng, Rất nóng} U = [0,100] – miền đánh giá nhiệt độ R = Nếu nhiệt độ u là X thì nhiệt độ có giá trị như sau: Rất lạnh với hàm thuộc 𝜇𝑅ấ𝑡𝑙ạ𝑛 (u) Lạnh với hàm thuộc 𝜇𝐿ạ𝑛 (u) Hơi Lạnh với hàm thuộc 𝜇𝐻ơ𝑖𝑙ạ𝑛 (u) Bình thường với hàm thuộc 𝜇𝐵ì𝑛𝑡ườ𝑛𝑔 (u) Hơi nóng với hàm thuộc 𝜇𝐻ơ𝑖𝑛 ó𝑛𝑔 (u) Rất nóng với hàm thuộc 𝜇𝑅ấ𝑡𝑛 ó𝑛𝑔 (u) M(*)(u) = {u, 𝜇(∗)(u)| u∈U = [1,100], 𝜇(∗)(u): U→ [0,1] } Với (*) = Rất lạnh (hoặc Lạnh, Hơi Lạnh,Bình thường, Hơi nóng, Nóng, Rất nóng). Một số đặc trưng cơ bản của biến ngôn ngữ [1]: 1/ Tính phổ quát: các biến ngôn ngữ khác nhau về các giá trị nguyên thủy nhưng ý nghĩa về mặt cấu trúc miền giá trị của chúng vẫn được giữ. Nói cách khác, cấu trúc miền giá trị của hai biếnngôn ngữ cho trước tồn tại một “đẳng cấu” sai khác nhau bởi giá trị sinh nguyên thủy 2/ Tính độc lập ngữ cảnh của gia tử và liên từ như AND, OR…: ngữ nghĩa của các gia tử và liên từ như AND, OR,… hoàn toàn độc lập với ngữ cảnh, 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ữ 10 cảnh. Do đó, khi tìm kiếm các mô hình cho các gia tử và liên từ như AND, OR… chúng ta không phải quan tâm đến giá trị nguyên thủy của biến ngôn ngữ đang xét. Các đặc trưng này cho phép chúng ta sử dụng cùng một tập gia tử và xây dựng một cấu trúc toán học duy nhất cho miền giá trị của các biến ngôn ngữ khác nhau. 1.1.6 Suy luận mờ Suy luận mờ hay còn gọi là suy luận xấp xỉ là quá trình suy ra những kết luận dưới dạng các mệnh đề mờ trong điều kiện các quy tắc, các luật, các dữ liệu đầu vào cho trước cũng không hoàn toàn xác định rõ ràng. Mỗi luật mờ được biểu diễn bởi một biểu thức “if – then”, được phát biểu dưới dạng ngôn ngữ tự nhiên thể hiện sự phụ thuộc nhân quả giữa các biến. Ví dụ: If chuồn chuồn bay thấp then trời mưa Trong suy luận mờ, đầu ra thường phụ thuộc vào nhiều yếu tố đầu vào. 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) hoặcBk(y). Luật mờ có dạng (theo chỉ số k): IF (x1 is Ak1) (x2 is Ak2) … (xi is Aki) … (xn is Akn) THEN y is Bk Ví dụ: IF (Ngoại ngữ giỏi) (Tin học giỏi) (Chuyên môn cao) THEN (trúng tuyển việc làm rất cao) Trong đó: - x1 là Ngoại ngữ; Ak1 là giỏi; - x2 là Tin học; Ak2 là giỏi 11 - x3 là Chuyên môn; - Ak3 là cao - y là trúng tuyển việc làm - Bk là rất cao 1.2 Đại số gia tử trong lập luận mờ Lý thuyết đại số gia tử đã cố gắng đưa các tập ngôn ngữ vào một cấu trúc thích hợp để mô phỏng các quá trình suy luận của con người mà chúng ta thường thực hiện trên ngôn ngữ tự nhiên. 1.2.1 Đại số gia tử (ĐSGT) 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 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, 𝛴, 𝛷, ≤). Khi tác động gia tử h∈H vào phần tử x ∈X, thì thu được phần tử ký hiệu hx. Với mỗi x ∈X, ký hiệu H(x) là tập tất cả các hạng từ u ∈X sinh từ x bằng cách áp dụng các gia tử trong H và viết u = hn…h1x, với hn, …, h1∈H. Tập H gồm các gia tử dương H+ và gia tử âm H-. Các gia tử dương làm tăng ngữ nghĩa của một hạng từ mà nó tác động, còn gia tử âm làm giảm ngữ
nghĩa của hạng từ. Không mất tính tổng quát, ta luôn giả thiết rằng H- = {h-1<
h-2< ... < h-q} và H+ = {h1< h2< ... < hp}. Để ý rằng biểu thức hn...h1u được gọi là một biểu diễn chính tắc của 12 một hạng từ x đối với u nếu x = hn...h1u và hi...h1u ≠ hi-1...h1u với i nguyên và i ≤ n. Ta gọi độ dài của một hạng từ x là số gia tử trong biểu diễn chính tắc của nó đối với phần tử sinh cộng thêm 1, ký hiệu l(x). Ví dụ: Cho biến ngôn ngữ HOT, có G = {0, COLD, W, HOT, 1}, H- =
{Possible More HOT , Very HOT, Little HOT ,HOT,… 1.2.2 Tính chất của đại số gia tử tuyến tính a. Tính thứ tự ngữ nghĩa của các hạng từ Định lý 1.1 [1]: 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ới nhau, tức là u∉H(v) và v∉H(u), thì H(u) ≤ H(v). Ví dụ: Cho biến ngôn ngữ WEIGHT, có G ={0, THIN, W, FAT, 1}, H+ = {More < Very }; Khi đó các hạng từ được sắp xếp theo thứ tự như sau: FAT b. So sánh hai hạng từ trong miền ngôn ngữ Đị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à 13 không so sánh được với nhau. 1.2.3 Đại số 2 gia tử Đại số 2 gia tử ký hiệu là AX2 chỉ bao gồm hai gia tử, một gia tử dương và một gia tử âm, nó có những đặc trưng quan trọng trong quá trình ứng dụng. Ta sẽ khảo sát các đặc trưng của đại số 2 gia tử, để không mất tính tổng quát đặt gia tử âm H- ={L} và gia tử dương H+ = {V}, khi đó hàm dấu là: Sign(x) = Sign(hn...h1c) = (-1)NL(x)Sign(c) trong đó hn, hn-1, ..., h1 {L, V} và NL(x) là số lượng các gia tử L có trong hạng từ x. Trong [1] tác giả đã chứng minh tính đúng đắn về kích thước của các tập Xk(tập các hạng từ có độ dài đúng k), X(k)(tập tất cả các hạng từ có độ dài từ 1 đến k), Ik(tập tất cả các khoảng tính mờ độ sâu k)và I(k)(tập các khoảng tính mờ độ sâu từ 1 đến k)trong đại số hai gia tử như sau: 1/ |Xl| = 5 2/ |Xk| = 2k, với k>1 3/ X(k) = 1+ 2k+1 Một trong những đặc trưng quan trọng của đại số 2 gia tử chính là có thể xây dựng hệ phân hoạch hệ các khoảng tính mờ, hệ các khoảng tương tự một cách nhanh tróng và chính xác. Trên cơ sở đó, phương pháp sinh hệ luật mờ được xây dựng với ngữ nghĩa gồm các hạng từ có độ dài không quá k, khắc phục được nhược điểm của đại số gia tử tuyến tính thông thường là chỉ áp dụng cho tập các hạng từ có độ dài đúng bằng k. Mặt khác đại số 2 gia tử khi áp dụng các phương pháp tìm kiếm tối ưu tham số mờ gia tử có lợi thế giảm không gian tìm kiếm, vì ta chỉ định nghĩa 14 không gian tìm kiếm cho các tham số độ đo tính mờ của phần tử sinh âm fm(c-) và độ đo tính mờ của gia tử L là 𝜇 (L) (với fm(c+) = 1- fm(c-) và 𝜇(V)=1- 𝜇(L)) dẫn tới tốc độ tìm kiếm sẽ nhanh hơn và đạt hiệu quả cao trong ứng dụng. 1.2.4Đị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.7[1]:AX = (X, G, H, 𝛴, 𝛷, ≤) là một ĐSGT tuyến tính đầy đủ. Ánh xạ fm: X → [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; 2/ fm(x) = 0, với các x thỏa H(x) = {x}. Đặc biệt, fm(0) = fm(W) = 𝑓𝑚 (𝑥) 𝑓𝑚 (𝑦 ) fm(1)=0; 𝑓𝑚 (𝑥) 𝑓𝑚 (𝑦 ) = , tỷ số này không phụ thuộc vào x và 3/ ∀x,y ∈ X, h ∈ H, y, vì vậy nó được gọi là độ đo tính mờ của các gia tử và được ký hiệu bởi 𝜇(h). Trong định nghĩa trên, điều kiện (1) thể hiện tính đầy đủ của các phần tử sinh và các gia tử cho việc biểu diễn ngữ nghĩa của miền thực đối với các biến. Điều kiện (2) thể hiện tính rõ của các hạng từ và điều kiện (3) có thể thể được chấp nhận vì chúng ta đã chấp nhận giả thiết rằng các gia tử độc lập với ngữ cảnh, do vậy khi áp dụng một gia tử h lên các hạng từ thì hiệu quả tác động tương đối làm thay đổi ngữ nghĩa của các hạng từ đó là như nhau. Hình vẽ sau sẽ minh họa rõ hơn cho khái niệm độ đo tính mờ của biến 15 ngôn ngữ “NHIỆT ĐỘ” fm(HRNóng) fm(RHNóng) fm(HHLạnh) fm(RRLạnh) fm(RRNóng) fm(RHLạnh) fm(HRLạnh) fm(HH.Nóng
) fm(RLạnh) fm(RNóng) fm(HNóng) fm(HLạnh) fm(Nóng) fm(Lạnh) Hình 1.3: Độ đo tính mờ của biến “NHIỆT ĐỘ” Một số tính chất của độ đo tính mờ của các hạng từ và gia tử đã được[1] chứng minh tính đúng đắn qua mệnh đề sau: ∈𝐻 Mệnh đề 1.1: [1] Với độ đo tính mờ fm và 𝜇 đã được định nghĩa, ta có:
1/ fm(c-) + fm(c+) = 1 và = fm(x); 𝑓𝑚(𝑥) −1
𝑗 =−𝑞 𝑝
𝑗 =1 2/ = 𝛼, = 𝛽 với 𝛼, 𝛽> 0 và 𝛼 + 𝛽 = 1; 𝜇(𝑗 ) 𝜇(𝑗 ) 𝑥∈𝑋𝑘 3/ 𝑓𝑚(𝑥) = 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) = 𝜇(𝑛 )…𝜇(1)fm(𝑐𝜀) Để 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 16 phương pháp khử mờ. Đối với ĐSGT, giá trị định lượng của các hạng từ được đị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áchạng từ và gia tử. Định nghĩa 1.8 [1]:Cho AX = (X, G, H, 𝛴, 𝛷, ≤) là một ĐSGT tuyến tính đầy đủ. Ánh xạ v: X→ [0,1] được gọi là một định lượng ngữ nghĩa của AX nếu: 1/ v là ánh xạ 1-1 từ tập X vào đoạn [0,1] và đảm bảo thứ tự trên X, tức là∀x,y∈X, x 2/ v liên tục: x ∈ X, v( 𝛷 x) = infimumv(H(x)) và v( 𝛴 x) = supremumv(H(x)) Điều kiện (1) là bắt buộc tối thiểu đối với bất kỳ phương pháp định lượng nào, điều kiện (2) đảm bảo tính trù mật của H(G) trong X. Trước hết ta cần phải định nghĩa về dấu của các hạng từ. Định nghĩa 1.9[1]: Một hàm dấu Sign: X → {-1,0,1} là một ánh xạ được định nghĩa đệ quy như sau: 1/ Sign(c-) = -1, Sign(c+) = 1; 2/ Sign(hc) = -Sign(c) nếu h âm đối với c; Sign(hc) = Sign(c) nếu h dương đối với c 3/ Sign(h’hx) = -Sign(hx), nếu h’hx≠hx và h’ âm đối với h; Sign(h’hx) = Sign(hx) nếu h’hx≠hx và h’ dương đối với h. 4/ Sign(h’hx) = 0, nếu h’hx = hx Mệnh đề 1.2: Với mọi gia tử h và phần tử x∈X nếu Sign(hx) = +1 thì hx>x;nếu Sign(hx) = -1 thì hx Định nghĩa 1.10 [1]: Khoảng tính mờ của các hạng từ x∈X, ký hiệu ℑfm(x), là một đoạn con của [0,1], ℑfm(x) ∈𝐼tv([0,1]), nếu nó có độ dài bằng độ đo tính mờ, |ℑfm(x)| = fm(x), và được xác định bằng qui nạp theo độ dài 17 của x như sau: 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+)| = fm(c+) và ℑfm(c-) ≤ ℑfm(c+); (2) Giả sử x có độ dài n (l(x) = n) và khoảng tính mờ ℑfm(x) đã được định nghĩa với |ℑfm(x)| = fm(x). Khi đó tập các khoảng tính mờ {ℑfm(hjx): -q ≤ j ≤ p và j ≠ 0} ⊂ Itv([0,1]) được xây dựng sao cho nó là một phân hoạch của ℑfm(x), và thỏa mãn |ℑfm(hjx)| = fm(hjx) và có thứ tự tuyến tính tương ứng với thứ tự của tập {h-qx, h-q+1x, ..., hpx}, tức là nếu h-qx > h-q+1x > ... > hpx thì W v(VNóng) v(HLạnh) v(HNóng
) ℑ2(VNóng) ℑ2(HNóng) v(RLạnh
)
ℑ2(RLạnh) ℑ2(HLạn
h) ℑ3(VRLanh) ℑ3(RHLạnh) ℑ3(HHNóng
) ℑ3(HRLạnh) ℑ3(HRNóng
)
ℑ3(RHNóng) ℑ3(HHLạnh) ℑ3(RRNóng) ℑfm(h-qx) >fm(h-q+1x) > ... >ℑfm(hpx) và ngược lại: Hình 1.4:Khoảng tính mờ của các hạng từ của biến “NHIỆT ĐỘ” Ví dụ: Với biến NHIỆT ĐỘ gồm 2 hạng từ nóng (N) và lạnh (L), hai gia tử “hơi” và “rất” với độ đo tính mờ của 2 hạng từ được cho như sau: fm(Lạnh) = fm(L)= 0.4 fm(Nóng) =fm(N) = 1 – fm(Lạnh) = 0.6 fm(Hơi) = fm(h) = 0.7 fm(Rất) = fm(r) = 1 – fm(hơi) = 0.3 1 0 Lạnh W Nóng fm(L) fm(N) Độ đo tính mờ của biến “NHIỆT ĐỘ” với các mức phân hoạch: 18 + Với mức phân hoạch k =1: Độ đo tính mờ: fm(L) = 0.4 fm(N) = 0.6 Khoảng tính mờ của hạng từ Lạnh và Nóng: ℑ(L) = [0, 0.4) ℑ(N) = [0.4, 1) W 0 1 Nóng hN rN Lạnh hL rL fm(rL) fm(rN) fm(hN) fm(hL) + Với mức phân hoạch k = 2: Khi đó độ đo tính mờ của các hạng từ và gia tử được tính như sau : fm(rL) = fm(L) * fm(r) = 0.28 fm(hL) = fm(L) * fm(h) = 0.12 fm(hN) = fm(N) * fm(h) = 0.18 fm(rN) = fm(N) * fm(r) = 0.42 Và khoảng tính mờ của các hạng từ: ℑ(rL) = [0, 0.28) ℑ(hL) = [0.28, 0.4) ℑ(hN) = [0.4, 0.58) ℑ(rN) = [0.58, 1] 1.2.5 Hệ khoảng tính mờ Trong phần trước chúng ta đã định nghĩa Xk là tập các hạng từ có độ dài k, Ik là tập các khoảng tính mờ của các hạng từ trong Xkvà Ik = { ℑ (x): x ∈ Xk}. Ta gọi Ik là hệ phân hoạch khoảng tính mờ mức k, nếu đặt xk,0 là hạng từ 19 bé nhất trong tập Xk thì thì (xk,0) = 0. Theo định nghĩa 1.10 và định lý 1.3[1], chúng ta có ℑ(xk,0) = [(xk,0), ( 𝑥𝑘,0)] và ℑ(x) = ((x), ( 𝑥)] cho ∀𝑥 ∈ Xk, x ≠ xk,0 , trong đó khoảng tính mờ luôn đóng ở điểm mút phải. Ví dụ: Cho fm(c-) = 0.3, fm(c+) = 0.7, µ(L) = 0.4, µ(V) = 0.6, mức phân hoạch k = 2. Khi đó ta có Độ đo tính mờ gia tử của thuộc tính DT: fm(Vc-) = 0.6* 0.3 = 0.18 fm(Lc-) = 0.4* 0.3 = 0.12 fm(Lc+) = 0.4* 0.7 = 0.28 fm(Vc+) = 0.6* 0.7 = 0.42 Hệ khoảng tính mờ: 0.3 0.18 0.58 0 1 ℑ(VC+) ℑ(VC-) ℑ(LC-) ℑ(LC+) 20 ℑDT(Vc-) = [0, 0.18)
ℑDT(Lc-) = [0.18, 0.3)
ℑDT(Lc+) = [0.3, 0.58)
ℑDT(Vc+) = [0.58, 1] 1.3 Kết luận chƣơng 1 Chương này đã trình bày một số khái niệm cơ bản về lập luận mờ: khái niệm về tập mờ, số mờ, khái niệm về biến ngôn ngữ và các phép toán trên tập mờ. Bên cạnh đó chương 1 còn trình bày các khái niệm về đại số gia tử, các tính chất của ĐSGT, vấn đề định lượng ngữ nghĩa trong ĐSGT, các khái niệm về khoảng mờ của các giá trị ngôn ngữ. Trong chương tiếp theo của luận văn sẽ phân tích sự ảnh hưởng của tham số mờ gia tử đối với bài toán phân lớp và phương pháp tinh chỉnh tham 21 số mờ gia tử dựa trên giải thuật di truyền để áp dụng cho bài toán cụ thể. CHƢƠNG 2: PHƢƠNG PHÁP TINH CHỈNH THAM SỐ MỜ GIA TỬ CỦA HỆ MỜ DẠNG LUẬT PHÂN LỚP 2.1 Phƣơng pháp xây dựng hệ mờ dạng luật phân lớp 2.1.1 Bài toán phân lớp Trong các bài toán về lĩnh vực khai phá dữ liệu thì bài toán phân lớp là một trong những bài toán đặc trưng được nhiều tác giả nghiên cứu, với các phương pháp khác nhau để đạt được hiệu quả phân lớp cao nhất. Trong đó có phương pháp dựa trên hệ mờ dạng luật (fuzzy rule-base classification systems - FRBCS), ngoài việc đạt được hiệu quả phân lớp cao phương pháp này còn được nghiên cứu để đáp ứng cho người dùng một mô hình phân lớp dễ hiểu trực quan, được người dùng sử dụng như là các tri thức của mình để áp dụng trong thực tế. Bài toán phân lớp mờ có thể được phát biểu như sau: cho một tập các dữ liệu mẫu D = {(P, C)}, trong đó P = {pi = (di,1,…,di,n)| i=1,…,N} là tập dữ liệu, C = {C1,…,Cm} là tập các nhãn của các lớp, pi ∈ U là dữ liệu thứ i với U = U1 × ... × Un là tích Đề-các của các miền của n thuộc tính X1, ..., Xn tương ứng, m là số lớp và N là số mẫu dữ liệu, để ý rằng P ⊂ U. Mỗi dữ liệu pi∈ P thuộc một lớp ci∈ C tương ứng tạo thành từng cặp (pi, ci) ∈ D. Giải bài toán bằng FRBCS chính là xây dựng một hệ các luật mờ, ký hiệu S, để phân lớp đóng vai trò như một ánh xạ từ tập dữ liệu vào tập nhãn: (2.1) S: U → C Như vậy, hệ S phải đạt được các mục tiêu như hiệu 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 22 người dùng. Khi đó mục tiêu xây dựng hệ luật sao cho có dạng: (2.2) fp(S) → max, fn(S) và fa(S) → min. trong đó: - 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 và các giá trị ngôn ngữ tham gia trong mỗi điều kiện của mỗi luật ảnh hưởng đến tính phổ quát của luật, cụ thể nếu số điều kiện ít sẽ làm tăng tính phổ quát và ngược lại. Tính phổ quát sẽ làm tăng khả năng dự đoán của luật nhưng nguy cơ gây sai số lớn, khi tính cá thể giảm thì khả năng dự đoán lại tăng tính. Vì vậy, các phương pháp giải quyết bài toán đều phải thỏa hiệp giữa các mục tiêu để đạt được kết quả cuối cùng. 2.1.2 Mô hình hệ mờ dạng luật giải bài toán phân lớp Dưới dạng tổng quát của hệ mờ dạng luật có n đầu vào và đầu ra của nó là cũng là một tập mờ, khi đó chúng ta cần giải mờ để xác định nhãn phân lớp cho mẫu dữ liệu tương ứng. Để đơn giản hơn thì ta sử dụng các luật mờ có phần kết luận của mỗi luật là một giá trị hằng tương ứng với nhãn của một lớp có dạng như sau: (2.3) If x1 is Aq1 and …and xn is Aqn then Class Cq with CFq trong đó Aqj là giá trị ngôn ngữ của các biến ngôn ngữ tương ứng với các thuộc tính, Cq là nhãn phân lớp và CFq là trọng số của mỗi luật, q= 1,…, M với M là số luật, j=1…n. Thông thường CFq∈[0,1]. Luật mờ dạng (2.3) có thể được viết gọn lại như sau: (2.4) Aq⇒ Cq with CFq 23 Trong đó Aq = (Aq,1,…,Aq,n) Luật mờ (2.4) được đánh giá qua độ tin cậy c(Aq⇒Cq) kí hiệu cq và độ hỗ trợ s(Aq⇒Cq) kí hiệu sq bằng các công thức: (2.5) (2.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: (2.7) 𝜇𝐴𝑞 (pi) = 𝜇𝐴𝑞 ,1(di,1). 𝜇𝐴𝑞 ,2(di,2). … . 𝜇𝐴𝑞 ,𝑛 (di,n). Để đánh giá trọng số của luật dạng (2.4), một số tác giả đã đề xuất (2.8) (2.9) (2.10) (2.11) phương pháp đánh giá trọng số luật như sau:
CF1(Aq ⇒ Cq) = cq
CF2(Aq ⇒ Cq) = cq – cq,Ave,
CF3(Aq ⇒Cq) = cq – cq,2nd,
CF4(Aq ⇒ Cq) = cq – cq,Sum trong đó : cq,Ave là độ tin cậy trung bình của các luật có cùng điều kiện Aq nhưng kết luận khác Cq: (2.12) 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à 24 lớp khác với Cq: (2.13) cq,2nd = max{c(Aq ⇒Cq) | h = 1, …, m; Ch ≠Cq } 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: (2.14) Với hệ luật mờ S dạng (2.4) ta thường sử dụng phương pháp chọn luật có mức đốt cháy lớn nhất đối với dữ liệu để đưa vào và phân lớp tương ứng với kết luận của luật đó (SWR – single winner rule): (2.15) trong đó w là chỉ số tương ứng trọng số luật được chọn, w ∈ {1,2,3,4}, hoặc
có thể áp dụng với trọng số đồng nhất bằng 1 cho mọi luật, kí hiệu CF0 = 1. Trong không gian các siêu hộp Hs(là không gian tích Đề-các của các miền thuộc tính được chia bởi lưới phân hoạch mờ) của phương pháp sinh luật dựa trên lưới phân hoạch mờ của các miền thuộc tính, mỗi (Aq,1, …, Aq,n) ∈ Hs sẽ dùng để xây 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: (2.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 luôn dương. Trong luận văn chỉ sử dụng công thức đánh giá
trọng số luật theo CF1. 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ã hóa bằng các cá thể trong GA bởi một trong 2 phương pháp là 25 Michigan hoặc Pittsburgh mã hóa tập các luật mờ thành một cá thể. 2.1.3 Thuật toán sinh luật mờ dựa trên hệ khoảng tính mờ Dựa trên hệ khoảng tính mờ của tập X(kj), chúng ta áp dụng lưới phân hoạch để sinh hệ luật mờ. Mỗi hạng từ trong tập X(kj) = { xj,0, xj,1, ..., xj,i-1, xj,i, xj,i+1, ..., xj,1+2kj+1} được thiết kế hàm định lượng ngữ nghĩa theo dạng tam giác (xj,i)(v) sao cho giá trị hàm càng gần tâm (xj,i) thì càng cao và bằng 1 tại tâm, nó sẽ bằng 0 nếu vượt ra ngoài tâm của hai hạng từ láng giềng của xj,i trong 1 tập X(kj) (hình 2.1): (xj,i-1) (xj,i) (xj,i+1) ℑ (0) ℑ (1) ℑ (xj,i-1) ℑ (xj,i) ℑ (xj,i+1) Hình 2.1: Hàm định lượng dạng tam giác của các hạng từ Theo cách thiết kế này thì mỗi tam giác sẽ có 3 đỉnh gồm bên trên (Top – T), bên phải (Right – R) và bên trái (Left – L). Với tọa độ của điểm Top chính là vị trí của điểm tâm ((xj,i), 1), tọa độ điểm Right là tọa độ tâm của từ bên phải đó((xj,i+1), 0), tọa độ của điểm Left là tọa độ tâm của từ bên trái ((xj,i-1), 0). Khi đó hàm định lượng ngữ nghĩa theo dạng tam giác được tính như sau: 26 + Nếu di ≤ L hoặc di ≥ R thì: + Nếu di + Nếu di ≥ T thì : Trên thực tế hai giá trị 0 và 1 ở hai đầu mút là các giá trị min và max nên không có ý nghĩa trong việc phân loại, do vậy ta sẽ không xét khoảng tính mờ của hai giá trị này, khi đó hàm định lượng ngữ nghĩa của từ cạnh hai giá trị này là hình thang, bên cạnh giá trị 0 là hình thang trái và cạnh giá trị 1 là hình thang phải. Nếu di< T (với hình thang trái) hoặc di ≥ T (với hình thang 1 phải) thì: (xj,i-1) (xj,i+1) (xj,i) ℑ (0) ℑ (1) ℑ (xj,i-1) ℑ (xj,i+1) ℑ (xj,i) Hình 2.2: Hàm định lượng ngữ nghĩa dạng hình thang Thuật toán sinh luật mờ từ tập dữ liệu mẫu dựa trên phân hoạch các 27 khoảng tính mờ trong đại số gia tử (IFRG1)[1]. Thuật toán này với đầu vào là mẫu dữ liệu D,với N số dữ liệu mẫu, n thuộc tính và m lớp và hệ khoảng tính mờ với mức phân hoạch kj cho các thuộc tính. Đầu ra là tập luật mờ S. Ví dụ 2.1: Minh họa phương pháp sinh luật của thuật toán IFRG1 để sinh luật cho bài toán phân lớp với bài toán phân loại sản phẩm sau: Bài toán: “Một công ty sản xuất sản phẩm đắt tiền chất lượng cao, sản phẩm được đặc trưng bởi hai thuộc tính Curvature – CT(độ cong) và Diameter – DT(đường kính), với 5 các sản phẩm được phân thành hai loại: thông qua – T và không thông qua – F. ” + Bước 1: Xác định dữ liệu của thuộc tính - Số thuộc tính: gồm 2 thuộc tínhCT,DT - Số lớp: gồm 2 lớp T, F - Số dữ liệu: gồm 5 mẫu dữ liệu được phân bố trong sau: CT Lớp DT 0.29 T 0.66 0.25 T 0.78 0.36 T 0.57 0.26 F 0.45 0.32 F 0.35 28 + Bước 2: Xác định các tham số mờ gia tử + Thuộc tính CT: độ đo tính mờ của phần tử sinh là fmCT(Small)= 0.4fmCT(Large) = 0.6, độ đo tính mờ của gia tử là µCT(L) =0.3; µCT(V) = 0.7, mức phân hoạch kCT=1. + Thuộc tính DT: độ đo tính mờ của phần tử sinh là fmDT(Small) =0.3 ,fmDT(Large)= 0.7, độ đo tính mờ của gia tử là µDT(L)=0.4,µDT(V)=0.6, mức phân hoạch kDT = 2. + Bước 3: Tính hệ khoảng tính mờ 1 Medium 0 fmCT(Small) fmCT(Large) + Thuộc tính CT với mức phân hoạch kCT = 1 Hệ khoảng tính mờ của thuộc tính CT: ℑCT(Small) = [0, 0.4) ℑCT(Large) = [0.4, 1) Hàm định lượng ngữ nghĩa: (Small) = 0 + 0.4 * 0.7 = 0.28 1 0 0.28 0.4 0.58 ℑ(Small) ℑ(Large) 29 (Large) = 0.4 + 0.6 * 0.3 = 0.58 1 + Thuộc tính DTvới mức phân hoạchkDT= 2: Small Large Medium fmDT(VSmall) fmDT(LSmall) fmDT(LLarge) fmDT(VLarge) fmDT(Small) fmDT(Large) 0 Độ đo tính mờ gia tử của thuộc tính DT: fmDT(VSmall) = 0.6* 0.3 = 0.18 fmDT(LSmall) = 0.4* 0.3 = 0.12 fmDT(LLarge) = 0.4* 0.7 = 0.28 fmDT(VLarge) = 0.6* 0.7 = 0.42 Hệ khoảng tính mờ của thuộc tính DT: ℑDT(VSmall) = [0, 0.18) ℑDT(LSmall) = [0.18, 0.3) ℑDT(LLarge) = [0.3, 0.58) ℑDT(VLarge) = [0.58, 1] Hàm định lượng ngữ nghĩa: Giá trị tâm của các hạng từ (VSmall) = 0 + 0.6 * 0.18 = 0.108 (LSmall) = 0.18 + 0.4*0.12 = 0.228 (LLarge) = 0.3 + 0.6*0.28 = 0.468 30 (VLarge) = 0.58 + 0.4 * 0.42 = 0.748 1 0.3 0.18 0.58 1 ℑ(VLarge) ℑ(VSmall) ℑ(LSmall) ℑ(LLarge) 0 + Bước 4: Sinh luật Lưới phân hoạch mờ trên hai miền thuộc tính: Sinh tuyển vế trái: L1(If CT is Small and DT is LLarge) L2(If CT is Small and DT is VLarge) Tính độ tin cậy của tuyển các luật: + Với tuyển vế trái 1: 31 L1(If CT is Small and DT is LLarge) CT DT Lớp Mức kich hoạt dữ liệu
đối với vế trái luật Tổng mức kích
hoạt theo lớp 0.29 0.66 T 0.3038 0.25 0.78 T 0.7700 0.0000 0.36 0.57 T 0.4662 0.26 0.45 F 0.9250 1.3656 0.32 0.35 F 0.4406 Tổng 2.1356 Độ tin cậy c và độ hỗ trợ s của tuyển vế trái 1 với kết luận là lớp T: c = 0.3606 s = 0.154 Độ tin cậy c và độ hỗ trợ s của tuyển vế trái 1 với kết luật là lớp F: c = 0.6394 s = 0.2731 Kết luận:theo công thức (2.15) thì vế phải của luật 1 là lớp F + Vớituyển vế trái2: L2(If CT is Small and DT is VLarge) CT DT Lớp Mức kich hoạt dữ liệu
đối với vế trái luật Tổng mức kích
hoạt theo lớp 0.29 0.66 T 0.9667 0.25 0.78 T 2.5274 0.8929 0.36 0.57 T 0.6679 32 0.26 0.45 F 0.0000 0.0000 0.32 0.35 F 0.0000 Tổng 2.5274 Độ tin cậy c và độ hỗ trợ s của tuyển vế trái 2 với kết luận là lớp T: c = 1 s = 0.5055 Độ tin cậy c và độ hỗ trợ s của luật 2 với kết luật vế phải là lớp F: c = 0 s = 0 Kết luận theo công thức (2.15) thì vế phải của luật 2 là lớp T + Bước 5: Kết luận Vậy hệ luật được sinh ra gồm 2 luật sau: - If CT is Small and DT is LLarge then class F - If CT is Small and DT is VLarge then class T + Bước 6: Kiểm tra lại hệ luật L1 L2 Max{L1, L2} Kết quả phân lớp Đúng/Sai D1 T Đ L2 0.3038 0.9667 D2 T Đ L2 0.0000 0.8929 D3 T Đ L2 0.4662 0.6679 D4 F Đ L1 0.9250 0.0000 D5 F Đ L1 0.4406 0.0000 33 Tỉ lệ phân lớp đúng 100%. 2.2 Sự ảnh hƣởng của tham số mờ gia tử đối với bài toán phân lớp Trong ĐSGT tuyến tính AX = (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. Ví dụ: nếu ta có thuộc tính NHIET DO là “Nhiệt độ của thời tiết” thì ta có Dom(NHIET DO) = {nóng, lạnh, rất nóng, hơi nóng, rất lạnh, hơi lạnh,…}, G = {nóng, lạnh, bình thường, 0, 1}, H={rất, hơi} và ≤ một qua hệ thứ tự cảm sinh từ ngữ nghĩa của các từ trong Dom(NHIET DO), chẳng hạn ta có rất nóng>nóng, hơi nóng phần tử x ∈X, thì thu được phần tử ký hiệu hx. Với mỗi x ∈X, ký hiệu H(x) là tập tất cả các hạng từ u ∈X sinh từ x bằng cách áp dụng các gia tử trong H và viết u = hn…h1x, với hn, …, h1∈H. Chúng ta có thể thấy rằng, dựa trên tính chất ngữ nghĩa của các phần tử x có thể biểu thị trong quan hệ “≤” trên X. 1/ Dựa vào quan hệ thứ tự thì mỗi một hạng từ nguyên thủy được xác định giá trị theo các hướng khác nhau: ví dụnhanhcó xu hướng tăng(dương),
và kí hiệu là c+, ngược lại, chậm có xu hướng giảm (âm), kí hiệu là c-. Chúng
có thể được biểu diễn bởi Vc+>c+ hoặc Vc- 2/ Ngoài ra, một số gia tử còn làm tăng hoặc giảm giá trị ngữ nghĩa của các hạng từ nguyên thủy, gia tử làm tăng giá trị ngữ nghĩa được gọi là gia tử
dương và ngược lại là gia tử âm. Chẳng hạn như, 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à dương nếu g ≤ Lg). Tập H+ và H- có thể
được phân hoạch thành hai tập với các gia tử trong 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à 34 ngược lại. Đây là độ đo tính mờ phần tử sinh kí kiệu µ(V) vàµ(L). Tuy nhiên, ngoài tham số mờ gia tử, tham số về mức phân hoạch kj cũng tác động lớn đến kết quả của mô hình. Mức phân hoạch càng lớn (kj càng lớn) sẽ sinh ra càng nhiều luật và các luật có tính phân biệt càng cao làm tăng hiệu năng phân lớp, nhưng số lượng các luật sẽ rất nhiều và khả năng dự đoán thấp do tính phổ quát thấp. Có hai phương để xác định mức phân hoạch kj là: xác định bằng trực quan và xác định tự động. Tuy nhiên việc xác định kj khó thực hiện bằng trực quan của người dùng đối với bất kỳ bài toán nào. Một cách tự nhiên chúng ta cũng đưa việc xác định mức phân hoạch kj vào bài toán tìm kiếm tối ưu. Ký hiệu PAR = { fmj(c-), fmj(c+), j(hi), kj | hiH, j = 1,...,n } là tập các tham số mờ gia tử cùng với mức phân hoạch kj của bài toán phân lớp, khi đó bài toán tìm kiếm tối ưu tham số mờ gia tử được phát biểu dưới dạng sau. Các mục tiêu: fp(S*) max, fn(S*) và fa(S*) min, Các ràng buộc: i) Điều kiện cho các tham số trong ĐSGT: 0 fmj(c-) + fmj(c+) = 1, (2.18) ij(hi) = 1, cho mọi j = 1,2,...,n. (2.19) ii) Điều kiện cho mức phân hoạch: 0 Trong đó S* là hệ luật sinh bởi quá trình sinh luật từ những điều kiện ban 35 đầu, kj là ngưỡng tối đa cho mức phân hoạch tại thuộc tính Xj. Các hàm đánh
giá fp(S*), fn(S*) và fa(S*) tương ứng là tỷ lệ % số mẫu phân lớp đúng trên tập dữ liệu (hay gọi là hiệu quả phân lớp), số lượng các luật và độ dài trung bình hệ luật. 2.3Phƣơng pháp tinh chỉnh bằng trực quan kinh nghiệm của ngƣời dùng
Như đã nói ở trên, các tham số mờ: độ đo tính mờ của gia tử fm(C+),
fm(C-); độ đo tính mờ của phần tử sinh µ(L), µ(V); mức phân hoạch k ảnh hưởng rất lớn đến kết quả của bài toán.Độ đo tính mờ của gia tử và độ đo tính mờ của phần tử sinh làm thay đổi không gian hệ khoảng tính mờ, còn mức phân hoạch kảnh hưởng tới số lượng luật được sinh ra, k càng lớn số luật sinh ra càng nhiều. Với dữ liệu từ ví dụ 2.1 chúng ta thấy khi các tham số mờ fmCT(Small)=0.4;fmCT(Large) = 0.6; µCT(L)=0.3; µCT(V) = 0.7; fmDT(Small) = 0.3; fmDT(Large) = 0.7; µDT(L)=0.4, µDT(V)=0.6và mức phân hoạch với thuộc tính DT là k=2, với CT là k=1 ta sinh ra được hệ luật gồm 2 luật: - If CT is Small and DT is LLarge then T(c = 0.7613, s = 0.2658) - If CT is Small and DT is VLarge then T(c = 0.90999, s = 0,4246) Chúng ta sẽ thay đổi từng tham số mờ gia tử và mức phân hoạch để xem sét sự ảnh hưởng đến kết quả bài toán. Thay đổi độ đo tính mờ của gia tử Độ đo tính mờ của gia tử µCT(L) = 0.2; µCT(V) = 0.8; µDT(L) = 0.7; µDT(V) = 0.3 các tham số độ đo tính mờ của gia tử fmCT(Small) = 0.4; fmCT(Large) = 0.6; fmDT(Small) = 0.3; fmDT(Large) = 0.7 mức phân hoạch kCT=1 và kDT=2 Hệ khoảng tính mờ của thuộc tính CT: 36 ℑCT(Small) =[0, 0.4) ℑCT(Large) =[0.4, 1] Hàm định lượng ngữ nghĩa cho thuộc tính CT: Giá trị tâm của các hạng từ: (Small) = 0.32 1 0 0.2 0.6 0.8 0.4 ℑCT(Large) ℑCT(Small) (Large) = 0.52 Hệ khoảng tính mờ của thuộc tính DT: ℑDT(VSmall) = [0, 0.09) ℑDT(LSmall) = [0.09, 0.3) ℑDT(LLarge) = [0.3, 0.79) ℑDT(VLarge) = [0.79, 1] Hàm định lượng ngữ nghĩa của thuộc tính DT: Giá trị tâm của các hạng từ (VSmall) = 0.027 (LSmall) = 0.237 (LLarge) = 0.447 37 (VLarge) = 0.937 1 0 0.2 0.6 0.8 0.4 ℑDT(VLarge) ℑDT(VSmall) ℑDT(LSmall) ℑDT(LLarge) Lưới phân hoạch trên hai miền thuộc tính CT và DT: Khi đó hệ luật sinh ra gồm 1 luật sau: - If CT is Small and DT is LLarge then classF (c = 0.5487, s=0.3064) Tỉ lệ phân lớp đúng là 40%. 38 Thay đổi độ to tính mờ của phần tử sinh Khi độ đo tính mờ của phần tử sinh thay đổi với fmCT(Small) = 0.84, fmCT(Large) = 0.16,fmDT(Small) = 0.13, fmDT(Large) = 0.87 độ đo tính mờ của gia tử và mức phân hoạch của hai thuộc tính CT và DT không thay đổi µCT(L)=0.3; µCT(V) = 0.7; µDT(L)=0.4, µDT(V)=0.6; kDT = 2, kCT =1, thì hệ khoảng tính mờ của hai thuộc tính có sự thay đổi: Hệ khoảng tính mờ của thuộc tính CT: ℑCT(Small) =[0, 0.84) ℑCT(Large) =[0.84, 1] Hàm định lượng ngữ nghĩa của thuộc tính CT: Giá trị tâm của các hạng từ (Small) = 0.588 1 0 0.5888 0.84 0.888 ℑCT(Small) ℑCT(Large) (Large) = 0.888 Hệ khoảng tính mờ của thuộc tính DT: ℑDT(VSmall) = [0, 0.052) ℑDT(LSmall) = [0.052, 0.13) ℑDT(LLarge) = [0.13, 0.478) ℑDT(VLarge) = [0.478, 1] Hàm định lượng ngữ nghĩa của thuộc tính DT: 39 Giá trị tâm của các hạng từ (VSmall) = 0.0468 (LSmall) = 0.099 (LLarge) = 0.339 1 0 0.2 0.6 0.8 0.4 ℑCT(LSmall) ℑCT(VLarge) ℑCT(LLarge) ℑDT(VSmall) (VLarge) = 0.687 Lưới phân hoạch trên hai miền thuộc tính CT và DT: Khi đó hệ luật được sinh ra gồm 2 luật sau: - If CT is Small and DT is LLarge then classT (c = 0.7387, s = 0.5484) 40 - If CT is Small and DT is VLargethen class T(c = 1, s = 0.2241) Tỉ lệ phân lớp đúng là 80%. Thay đổi mức phân hoạch k Các giá trị giữ nguyên µCT(L) =0.3; µCT(V) = 0.7 và fmCT(Small) =0.4; fmCT(Large) = 0.6; µDT(L) =0.4; µDT(V) = 0.6 và fmDT(Small) = 0.3; fmDT(Large) = 0.7 thay đổi mức phân hoạch kCT = 2, kDT = 3. Hệ khoảng tính mờ của thuộc tính CT: ℑCT(VSmall) =[0, 0.28) ℑCT(LSmall) =[0.28, 0.4) ℑCT(LLarge) =[0.4, 0.58) ℑCT(VLarge) =[0.58, 1] Hàm định lượng ngữ nghĩa của thuộc tính CT: Giá trị tâm của các hạng từ (VSmall) = 0.196 (LSmall) = 0.316 (LLarge) = 0.526 1 0 0.2 0.6 0.8 0.4 ℑCT(VLarge) ℑCT(LSmall) ℑCT(LLarge) ℑCT(VSmall
) 41 (VLarge) = 0.706 Hệ khoảng tính mờ của thuộc tính DT: ℑDT(VVSmall) = [0, 0.108) ℑDT(VLSmall) = [0.108, 0.18) ℑDT(LVSmall) = [0.18, 0.228) ℑDT(LLSmall) = [0.228, 0.3) ℑDT(LLLarge) = [0.3, 0.468) ℑDT(LVLarge) = [0.468, 0.58) ℑDT(VLLarge) = [0.58, 0.748) ℑDT(VVLarge) = [0.748, 1] Hàm định lượng ngữ nghĩa của thuộc tính DT: Giá trị tâm của các hạng từ (VVSmall) = 0.0648 (LVSmall) = 0.137 (LLSmall) = 0.209 (VLSmall) = 0.257 (VLLarge) = 0.401 (LLLarge) = 0.513 (LVLarge) = 0.681 1 0 0.2 0.6 0.8 0.4 42 (VVLarge)=0.849 Lưới phân hoạch trên hai miền thuộc tính CT và DT: Khi đó hệ luật sinh ra gồm 5 luật sau: - If CT is VSmall and DT is VLLarge then classF (c = 1, s = 0.0525) - If CT is VSmall and DT is VVLarge thenclassT(c = 1, s = 0.0648) - If CT is LSmall and DT is VLLarge then classF(c = 1, s = 0.1867) - If CT is LSmall and DT is LLLarge then classT (c = 0.7266, s=0.1240) - If CT is LSmall and DT is LVLarge thenclassT (c = 1, s = 0.2277) Tỉ lệ phân lớp đúng là 100%. Thay đổi cả ba loại tham số Các tham số mờ được thay đổi như sau: fmCT(Small)=0.6;fmCT(Large)=0.4;µCT(L)=0.7; µCT(V) = 0.3; fmDT(Small) = 0.4; fmDT(Large) = 0.6; µDT(L)=0.6, µDT(V)=0.4và mức phân hoạch với thuộc tính DT là k=1, với CT là k=2 43 Hệ khoảng tính mờ của thuộc tính CT: ℑCT(VSmall) =[0, 0.18) ℑCT(LSmall) =[0.18, 0.6) ℑCT(LLarge) =[0.6, 0.88) ℑCT(VLarge) =[0.88, 1] Hàm định lượng ngữ nghĩa của thuộc tính CT: Giá trị tâm của các hạng từ (VSmall) = 0.054 (LSmall) = 0.474 (LLarge) = 0.684 1 0 0.2 0.6 0.8 0.4 ℑCT(LLarge
) ℑCT(LSmall
) ℑCT(VLarg
e) ℑCT(VSmall
) (VLarge) = 0.964 Hệ khoảng tính mờ của thuộc tính DT: ℑDT(Small) = [0, 0.4) ℑDT(Large) = [0.4, 1] Hàm định lượng ngữ nghĩa của thuộc tính DT: Giá trị tâm của các hạng từ 44 (Small) = 0.16 1 0 0.2 0.6 0.8 0.4 ℑDT(Large) ℑDT(Small) (Large) = 0.76 Lưới phân hoạch trên hai miền thuộc tính CT và DT: Khi đó hệ luật sinh ra gồm 2 luật sau: - If CT is LSmall and DT is Small then classF (c = 0.679, s =0.1372) - If CT is LSmall and DT is Large then classT (c = 0.766, s =0.2866) Tỉ lệ phân lớp đúng là 100%. 45 Kết luận Ta thấy rằng với sự thay đổi của các tham số mờ thì hệ luật được sinh ra cũng bị ảnh hưởng về số luật được sinh ra cũng như tỉ lệ phân lớp của bài toán. Sự thay đổi bằng trực quan, kinh nghiệm của người dùng đôi khi cũng đưa ra những kết quả không được tối ưu, do vậy sử dụng giải thuật di truyền để tìm kiếm được các tham số mờ là một giải pháp. 2.4 Tinh chỉnh bằng phƣơng pháp tối ƣu dựa trên giải thuật di truyền 2.4.1 Giải thuật di truyền Giải thuật di truyền (GA) là một kĩ thuật chung giúp giải quyết bài toán bằng cách mô phỏng sự tiến hóa của loài người hay sinh vật nói chung dựa trên thuyết tiến hóa của Darwin, trong điều kiện quy định sẵn của môi trường. Đây là một giải thuật nên hàm mục tiêu của GA không đưa ra lời giải chính xác mà đưa ra lời giải tương đối và mang tính phù hợp. Xuất phát từ số lượng lớn cá thể giới hạn được gọi là quần thể ban đầu, sau đó dựa vào một hàm nào đó để ta xác định sự thích nghi của từng cá thể trong quần thể. Vì phát sinh tự nhiên nên tính thích nghi của các cá thể trong quần thể là không xác định. Để cải thiện tính thích nghi của quần thể ta tạo ra quần thể mới, quần thể mới được tạo ra theo hai trường hợp: một là, chọn lọc các cá thể có độ thích nghi cao từ thế hệ trước đưa sang thế hệ sau. Hai là, sản sinh trên một số cá thể được chọn từ thế hệ trước bằng cách lai tạo hoặc đột biến, việc lai tạo được tạo ra từ sự kết hợp của hai cá thể thế hệ trước theo nguyên tắc nào đó để tạo ra cá thế mới cho thế hệ sau. Tuy rằng chọn lọc và lai ghép sinh ra được thế hệ sau, nhưng nhiều khi do thế hệ khởi đầu có đặc tính chưa phong phú và phù hợp nên các cá thể 46 không thể rải đều hết không gian của bài toán, nên khó tìm ra lời giải tối ưu. Thao tác đột biết sẽ giải quyết được vấn đề này, thao tác này sẽ biến đổi ngẫu nhiên một hoặc nhiều thành phần của một cá thể thế hệ trước để sinh ra một cá thể khác hoàn toàn mới ở thế hệ sau. Nhưng thao tác này xảy ra với tần xuất thấp vì có thể gây xáo trộn hoặc mất đi những cá thể có tính thích nghi cao dẫn tới việc thuật toán không còn hiệu quả. 2.4.2 Sơ đồ tổng thể của giải thuật di truyền - GA Trong hầu hết các nghiên cứu, các tác giả sử dụng GA với sơ đồ chính như Hình 2.2 dưới đây. Trong [1], các phép toán trong GA được tác giả sử dụng bao gồm phép chọn lọc cá thể bố mẹ từ quần thể hiện tại (SGA_Selection), phép lai ghép các bố mẹ thành cá thể con (SGA_Crossover), phép đột biến các cá thể con (SGA_Mutation) và phép tái tạo hay chọn và tạo ra quần thể mới từ các cá thể bố mẹ và con sau khi được đột biến (SGA_Reproduction). Để sinh một thế hệ mới từ thế hệ hiện tại, các phép toán di truyền trên được áp dụng như sau: Chọn một cặp bố mẹ từ quần thể hiện tại bằng SGA_Selection, thực hiện phép lai ghép (SGA_Crossover) theo xác suất pc để tạo hai con và thực hiện đột biến trên hai con này theo xác xuất đột biến là pm. Hai con được sinh ra sẽ cạnh tranh với cặp bố mẹ của chúng để tồn tại ở thế hệ tiếp thông qua phép toán SGA_Reproduction. Quá trình này được lặp lại cho đến khi thu được quần thể có đủ số lượng cá thể là Npop. Kích thước của quần thể (số cá thể - Npop) trong các thế hệ là như nhau và được xác định trước. Điều kiện dừng trong thuật toán này là khi đạt được số thế hệ tối đa (Gmax), tham số Gmax được xác định bởi chuyên gia, hoặc khi sự khác nhau giữa hai thế hệ liền nhau dưới ngưỡng cho trước diff. Cuối cùng, cá thể tốt nhất được chọn để đưa ra kết quả của quá trình tìm kiếm bằng 47 thuật toán SGA này. Bắt đầu Khởi tạo quần thể xuất phát và đánh giá cá thể Chọn lọc Lai ghép Đột biến Tạo quần thể mới và đánh giá cá thể No Dừng? Yes Kết thúc Hình 2.3. Sơ đồ các bước chính của thuật toán di truyền (GA). 2.4.3Áp dụng GA tìm kiếm tham số tối ưu a, Phát biểu bài toán Trong quá trình xây dựng hệ luật khi áp dụng thuật toán sinh luật
IFRG1[1], nếu chỉ sử dụng một hệ S* với M luật thì nhiều khả năng hàm đánh
giá mục tiêu fp(S*) dẫn đến tối ưu tham số mang tính địa phương, tức là nó chỉ 48 tối ưu đối với hệ đúng M luật. Một lý do khác là chúng ta khó xác định số luật M đối với một bài toán để có được bộ tham số tối ưu theo đúng nghĩa của nó (1.6). Ở đây chúng ta sẽ đánh giá mục tiêu hiệu quả phân lớp đối với một bộ Ns} có số 2,..., S* 1, S* tham số dựa trên nhiều hệ luật, giả sử với bộ tham số PAR, áp dụng thuật toán sinh luật IFRG1 để sinh hệ luật S0. Đặt Ns là số lượng các hệ luật cần dùng để
đánh giá hiệu quả đối với PAR, khi đó để lấy ra Ns hệ luật {S*
lượng các luật lần lượt là M1, M2,..., MNs, gọi Ns hệ này là Set(Ns) (ký hiệu S**). i | S* i= HAFRG(PAR, IFRG1, Mi), i = 1,...,Ns}, Set(Ns) = {S* trong đó các Mi được cho trước. Theo cách này, chúng ta đánh giá các
mục tiêu trong (2.1) dưới dạng trung bình, khi đó ký hiệu fp(S**) = tương ứng là , fn(S**) = và fa(S**) = hiệu quả phân lớp, số luật và độ dài trung bình của luật đánh giá trên Ns hệ luật Set(Ns). Bài toán tối ưu ở trên có 3 mục tiêu, để áp dụng giải thuật di truyền, theo cách thông thường chúng ta kết nhập theo trọng số các mục tiêu trong (2.1) thành một mục tiêu dưới dạng sau: wp.fp(S**) + wn.fn(S**)-1+ wa.fa(S**)-1max, (2.21) trong đó 0 fa(S**) > 0 do đó fn(S**)-1 và fa(S**)-1 luôn tồn tại. Theo điều kiện (2.3), ta giảm bớt tham số fm(c+) trong tập PAR, vì fm(c+)
= 1- fm(c-). Hơn nữa, trong ĐS2GT chỉ gồm hai gia tử {L,V}, từ điều kiện(2.4) cho phép giảm bớt tham số (V), vì (V) = 1-(L). Như vậy không gian tìm kiếm sẽ được thu hẹp rất nhiều, cụ thể PAR = { fmj(c-), j(L), kj | j =1,2,...,n }, (2.22) Ngoài ra, để các giá trị ngôn ngữ mang ngữ nghĩa và định lượng của 49 chúng thích hợp với thực tế, chúng ta sẽ đặt ràng buộc (2.2) theo khoảng giới hạn nhỏ hơn. Tuy rằng việc thu hẹp giới hạn của các tham số làm cho hiệu quả của mô hình có thể không cao, nhưng các giá trị ngôn ngữ biểu diễn trong luật mờ sẽ có tính thực tế hơn. Khi đó ràng buộc (2.2) trở thành (2.23) Laj < fmj(c-) < Lbj, Lcj<µj(L) < Ldj, j=1,2…n trong đó các hằng số thỏa mãn 0 ≤ Laj ≤ Lbj≤ 1và 0 ≤ Lcj≤ Ldj ≤ 1 được lựa chọn để phù hợp với thực tế bài toán. b, Phương pháp biểu diễn chuỗi gen trong GA Để thiết kế thuật toán tìm kiếm tối ưu cho cả hệ luật và tham số mờ gia tử, chúng ta áp dụng mã hóa kép trong chuỗi gen của mỗi cá thể. Chuỗi gen, ký hiệu là C, bao gồm các gen biểu diễn các tham số gia mờ gia tử cho bài toán gọi là CP gồm 3 đoạn. Đối với phần CP, sử dụng mã hóa số thực. Phần này bao gồm N cặp tham số mờ gia tử của N thuộc tính trong bài toán, mỗi thuộc tính có 3 tham số là
fm(c-) và(L), kj (trong ĐS2GT, ta có fm(c+) = 1-fm(c-) vàV = 1-(L)). Vậy
chuỗi gen của phần này có độ dài 3N, Cp = {fm1(c-),1(L),k1,fm2(c-),2(L),
k2,..., fmN(c-),N(L), kN}. Giới hạn giá trị của mỗi allen, CP[i], trong chuỗi gen của phần này là [min, max] (0<min<max<1) nhằm phù hợp với tính ngữ nghĩa trực quan của người dùng, nếu khoảng giới hạn này càng lớn thì mức độ dị biệt về ngữ nghĩa của các giá trị ngôn ngữ càng cao và ngược lại. Trong bài này, chúng tôi sử dụng khoảng giới hạn [0.2, 0.8]. fm1(c-) fm2(c-) … k1 k2 … kN fmN(c-) 1(L) 2(L) … N(L) Cuối cùng, chuỗi gen của mỗi cá thể trong thuật toán GA là C = CP. c, Đánh giá cá thể (evaluation) Để có được những cá thể như trên ta phải lấy được các tham số, từ đó sinh hệ luật bằng cách tính giá trị các hạng từ, khoảng tính mờ và hàm định 50 lượng ngữ nghĩa của các hạng từ, sau đó đánh giá tỉ lệ phân lớp của hệ luật. Để đánh giá cá thể trong quần thể ta phải dựa vào một mục tiêu nào đó, rất nhiều tác giả chuyển từ hàm đa mục tiêu về về dạng một mục tiêu bằng việc kết nhâ ̣p thành hàm mục tiêu như sau: fitness = wp.fp(S) + wn.fn(S)-1+ wa.fa(S)-1 (2.24) trong đó wp, wn là các tro ̣ng số kết nhập, 0 wa=1. Mỗi cá thể có chuỗi gen C = CP, phần CP sẽ xác định một bộ tham số mờ gia tử cho các thuộc tính. Bộ tham số mờ này được dùng để tính toán và định lượng ngữ nghĩa của các giá trị ngôn ngữ trong tập X và sử dụng chúng trong các luật mờ đã được sinh trong tập S0. Như vậy, chúng ta sẽ áp dụng hệ luật được chọn với định lượng ngữ nghĩa của các giá trị ngôn ngữ trong các luật để thực hiện phân lớp trên tập dữ liệu của bài toán và đánh giá các tiêu chí trong (2.4). d, Thuật toán tinh chỉnh tham số mờ gia tử Thuật toán tìm kiếm tối ưu bộ tham số dựa trên các phép toán di truyền gọi là thuật toán FPO-SGA[1] (fuzzy parameters optimization - SGA) như sau: Inputs: - Tập dữ liệu mẫu D = { (pi; ci) | i=1, ..., N }, pi = (di,1, ..., di,n) P, ciC = {C1, ..., Cm}, n là số thuộc tính, m là số lớp, N là số mẫu dữ liệu; - Giới hạn ràng buộc các tham số theo (2.8) gồm: 0 ≤ Laj Lcj - Trọng số cho các mục tiêu của hàm thích nghi (2.6): 0 wp + wn+wa= 1; 51 Outputs: - Bộ các tham số mờ gia tử và mức phân hoạch kj của các thuộc tính PAR = { fmj(c-), fmj(c+) = 1- fmj(c-), j(h), kj | h H, j = 1, ..., n }; Actions: Bước 1) Khởi tạo một quần thể xuất phát gồm Np cá thể Pop0 = { p0,1, p0,2, ..., p0,Np } để tính tham số nhiệt ban đầu T0 (ký hiệu pk,i là cá thể thứ i trong quần thể của thế hệ k,nó là mã hóa của bộ tham số PAR, Np là kích thước của quần thể tại mỗi thế hệ trong SGA); Bước2) Với mỗi p0,iPop0, thực hiện quá trình sinh hệ luật phân lớp S(p0,i) = IFRG1(p0,i). Tính độ phù hợp của mỗi cá thể Fit(S(p0,i)) dựa trên hệ luật S(p0,i) theo công thức (2.24), và tính tham số nhiệt ban đầu: Bước 3) Đặt k = 0. Lặp theo mỗi k cho đến khi k = Gmax, Popk = {pk,1, pk,2, ..., pk,Np} và thực hiện 3.a) Tính tham số nhiệt cho thế hệ k+1, Tk+1 = k.Tk, trong đó < 1 là hệ số giảm nhiệt độ (thường chọn 0.7); 3.b) Tạo quần thể mới Popk+1 cho thế hệ k+1 như sau: Lặp theo i cho đến khi |Popk+1| = Np, Chọn hai cặp cá thể bố mẹ p, qPopk sử dụng phép chọn lọc SGA_Selection(Popk, Tk+1). Sau đó thực hiện các phép lai ghép, độ biến và thay thế trên cặp bố mẹ này sử dụng các phép SGA_Crossover, SGA_Mutation, SGA_Replacement để tạo cặp cá 52 thể mới p, q và đưa vào Popk+1. Kết quả Popk+1 = {pk+1,1, pk+1,2, ..., pk+1,Np} 3.c) Với mỗi pk,iPopk+1, thực hiện quá trình sinh hệ luật phân lớp S(pk,i) = HAFRG(pk,i). Tính độ phù hợp của mỗi cá thể Fit(S(pk,i)) dựa trên hệ luật S(pk,i) theo công thức (2.6). Bước 4) Trả về kết quả bộ tham số tương ứng với cá thể có độ phù hợp cao nhất trong thế hệ cuối cùng, PARopt. End. Các tham số trong thuật toán này được sử dụng để sinh hệ luật IFRG1 và để thực hiện các phép di truyền của SGA phải được cho trước. Tham số mứ c phân hoa ̣ch kj là một giá trị nguyên 1,2,3… đươ ̣c mã hóa bở i gen là mô ̣t số thực trong [0,1]. Ví dụ 2.2: Cho mẫu dữ liệu được bao gồm 8 mẫu dữ liệu được chia làm 3 lớp với hai thuộc tính Curvature và Diameter như sau: CT 0.36
0.57
0.35
0.38
0.82
0.24
0.33
0.51 Class
0
0
0
1
1
2
2
2 DT
0.86
0.76
0.04
0.89
0.69
0.41
0.91
0.99 Thực hiện tối ưu tham số mờ bằng thuật toán FPO-SGA theo phương pháp sinh luật dựa trên khoảng tính mờ IFRG1.Chúng ta sử dụng giá trị ngôn ngữ sinh là c- = small và c+ = large, bộ tham số gia tử của hai thuộc tính được 53 mã hóa trong mỗi cá thể gồm PAR = {fmj(c-), µj(L), kj | j =1,2}, giới hạn các
tham số mờ gia tử là 0.1 ≤ fmj(c-), µj(L) ≤ 0.9 và mức phân hoạch kj∈ [1,3]. Các tham số chạy thuật toán tối ưu α = 0.7, 𝛾max = 9, kích thước quần thể tại mỗi thế hệ Np = 10, số thế hệ tiến hóa Gmax = 15. Trọng số cho các thành phần trong hàm mục tiêu (2.24) là wp = 0.9, wn = 0.01 Các tham số gia tử tối ưu bằng thuật toán FPO-SGA: Curvature
0.501
0.499
0.468
0.532
3 Diameter
0.9
0.1
0.669
0.331
1 fm(c-)
fm(c+)
µ(L)
µ(V)
kj Với số luật sinh ra là 7, độ phù hợp của mỗi cá thể fitness = 0.9143. Hệ luật bao gồm các luật sau: ifCurvature is LL.small and Diameter is smallthenClass 0 R1 c= 1, s= 0.0515 ifCurvature is VL.large and Diameter is smallthenClass 0 R2 c=1, s=0.0276 ifCurvature is VL.small and Diameter is smallthenClass 1 R3 c= 1, s= 1.329 ifCurvature is LV.large and Diameter is smallthenClass 1 R4 c=1, s=0.0291 ifCurvature is LV.small and Diameter is smallthenClass 2 R5 c= 1, s= 0.0407 ifCurvature is LL.small and Diameter is large thenClass 2 R6 c=1, s=0.0168 ifCurvature is VL.large and Diameter is largethenClass 2 R7 c=1, s=0.017 54 Kết quả phân lớp đúng là 100%. 2.5 Kết luận chƣơng 2 Các tham số mờ gia tử và mức phân hoạch k trong bài toán phân lớp có ảnh hưởng quan trọng trong quá trình xây dựng hệ luật cũng như trong hiệu quả phân lớp. Từ đó đưa ra được thuật toán tối ưu các tham số mờ gia tử này để làm tăng hiệu quả của quá trình phân lớp và tối ưu hóa hệ luật trong bài toán phân lớp. Sử dụng giải thuật di truyền là giải pháp tốt để tìm kiếm được bộ tham số tối ưu của bài toán bằng cách sử dụng các bằng các phép toán trong giải thuật như: chọn lọc, lai ghép, tái tạo, đột biến. Tiếp theo chương 3 chúng ta sẽ ứng dụng thuật toán di truyền để tìm 55 kiếm bộ tham số tối ưu cho một vài bài toán đặc trưng. CHƢƠNG 3: XÂY DỰNG CHƢƠNG TRÌNH VÀ ỨNG DỤNG THỬ NGHIỆM 3.1. Xây dựng ứng dụng Ứng dụng thử nghiệm được xây dựng bằng ngôn ngữ lập trình java với một số chức năng cơ bản như: Thay đổi tập dữ liệu, thay đổi các tham số đầu vào của bài toán trên form bằng trực quan, thay đổi tham số bài toán bằng giải thuật di truyền, sinh hệ luật mờ và kiểm tra quá trình phân lớp dữ liệu của bài toán ứng dụng. 3.2 Bài toán phân lớp hạt giống lúa mì (Seeds) Bài toán phân lớp hạt giống lúa mì được các nhà khoa học tại viện Agrophysics của Viện hàn lâm Khoa học Ba Lan tại Lublin nghiên cứu. Bài toán gồm có 7 thuộc tính là các tính chất hình học của 3 loại hạt lúa mì: Kama, Rosa và Canadian, các thuộc tính bao gồm: area(A), Perimeter(chu vi hạt - P), Compactness (Độ chặt - C), length of kernel (Chiều dài của nhân - LK), width of kernel (Chiều rộng của nhân - WK), asymmetry coefficient (hệ số không đối xứng - AC) và length of kernel groove (Chiều dài rãnh của nhân - LKG). Giá trị của các thuộc tính này đều là các giá trị thực. Tập dữ liệu gồm 210 mẫu với 3 lớp gồm Kama(0), Rosa(1) và Canadian(2). Tỷ lệ số mẫu trong mỗi lớp tương ứng là: 70/0, 70/1, 70/2. Sơ đồ phân bố các dữ liệu mẫu theo từng cặp thuộc tính trên 3 lớp được thể hiện trên hình 3.1, thuộc tính width of kernel (WK) được thể hiện trên cả hai hình 3.1c và 3.1d bởi vì thuộc tính lẻ ra cần được kết hợp để thể hiện dưới 56 dạng sơ đồ hai chiều. (3.1a) 57 (3.1b) (3.1c) (3.1d) Hình 3.1 Sơ đồ phân bố dữ liệu giữa các lớp của bài toán Seeds Chúng ta sẽ chạy thuật toán FPO-SGA tối ưu tham số mờ gia tử cho bài toán. Các tham số chạy thuật toán tối ưu gồm: kích thước quần thể Np=30
cá thể, số thế hệ tiến hóa là Gmax = 30, ràng buộc các tham số là 0.1≤ fm(c-), µ(L)≤ 0.9, k≤ 3, trọng số các hàm fitness là wp = 0.99, wn = 0.01. Với bộ tham số mờ chưa được tối ưu tức là tất cả các giá trị fmj(c-) = 0.5, µj(L) = 0.5, mức phân hoạch kj = 1, số luật sinh sinh ra gồm 21 luật, số lỗi 58 phân lớp là 21/210 mẫu dữ liệu, tỉ lệ phân lớp đúng là 90%. Với bộ tham số mờ được tinh chỉnh bằng trực quan (bảng 3.1) thì hệ luật sinh ra gồm 139 luật, số lỗi phân lớp là 5/210 mẫu dữ liệu, tỉ lệ phân lớp đúng là 97.62%. Kết quả tối ưu bộ tham số mờ cùng mức phân hoạch được thể hiện trong bảng 3.2, hệ luật sinh ra gồm 177 luật, số lỗi phân lớp là 0/210 mẫu dữ liệu, hiệu quả phân lớp đạt 100%. Bảng 3.1 Các tham số gia tử tinh chỉnh bằng trực quan của bài toán Seeds Thuộc tính µj(L) µj(V) kj A fmj(c-)
0.778 0. 127 fmj(c+)
0.222 0.873 1 P 0. 63 0. 585 0.37 0.415 3 C 0. 573 0. 598 0.427 0.402 3 LK 0. 559 0. 853 0.441 0.147 2 WK 0. 884 0. 318 0.116 0.692 3 AC 0.611 0. 437 0.389 0.563 3 LKG 0. 104 0. 637 0.896 0.363 2 Bảng 3.2 Các tham số gia tử tối ưu bằng thuật toán FBO-SGA cho bài toán Seeds Thuộc tính µj(L) µj(V) kj A fmj(c-)
0.682 0.672 fmj(c+)
0.318 0.328 3 P 0.31 0.315 0.69 0.685 3 C 0.268 0.469 0.732 0.531 3 LK 0.184 0.777 0.816 0.223 2 WK 0.13 0.505 0.87 0.495 3 AC 0.36 0.566 0.64 0.434 3 59 LKG 0.28 0.688 0.72 0.312 2 Bảng 3.3 So sánh về số lỗi và tỉ lệ phân lớp giữa các bộ tham số Phương pháp tinh chỉnh bộ tham số Số lỗi Tỉ lệ phân lớp Mặc định 21 90% Trực quan 5 97.63% Tự động 0 100% 3.3 Bài toán phân loại ngƣời bị thoát vị đĩa đệmVertebral Column Bài toán phân lớp bệnh nhân bị thoát vị đĩa đệm được xây dựng bởi tiến sỹ Henrique da Mota tại trung tâm Group of Applied Research in Orthopaedics, Lyon, Pháp. Bài toán có 6 thuộc tính gồm: Pelvic incidence (Tỉ lệ khung chậu - PI),Pelvic tilt (Độ nghiêng xương chậu - PT), Lumbar lordosis angle (Góc ưỡn cột sống thắt lưng - LA), Sacral slopes(Độ dốc xương cùng - SS), Pelvic radius(Bán kính vùng chậu - PR)vàGrade of Spondylolisthesis(GS) và gồm 3 lớp sau: Normal (NO – Bình thường), Disk Hernia (DH – thoát vị đĩa đệm), Spondylolisthesis (SL – Trượt đốt sống), với tỉ lệ số mẫu trong mỗi lớp tương ứng như sau: 100/NO, 60/DH và 150/SL. Sơ đồ phân bố dữ liệu của từng cặp thuộc tính được thể hiện trong hình 3.2. Ở các Hình 3.1a của cặp thuộc tính PI và PT, Hình 3.1b của cặp thuộc 60 tính LA và SS, Hình 3.1c của cặp thuộc tính PR và GS. (a) 61 (b) (c) Hình 3.2 Sơ đồ phân bố dữ liệu giữa các lớp của bài toánVertebral Column Chúng ta sẽ chạy thuật toán FPO-SGA tối ưu tham số mờ gia tử cho bài toán. Các tham số chạy thuật toán tối ưu gồm: kích thước quần thể Np=50 cá thể, số thế hệ tiến hóa là Gmax = 50, ràng buộc các tham số là 0.1 ≤ fm(c) ≤0.9; 0.2 ≤ µ(L)≤ 0.8; k≤ 3, trọng số các hàm fitness là wp = 0.9, wn = 0.01. Với bộ tham số mờ chưa được tối ưu tức là tất cả các giá trị fmj(c-) = 0.5, µj(L) = 0.5, mức phân hoạch kj = 1, số luật sinh sinh ra gồm 25 luật, số lỗi phân lớp là 99/310 mẫu dữ liệu, tỉ lệ phân lớp đúng là 68.1%. Với bộ tham số mờ được tinh chỉnh bằng trực quan (bảng 3.4) thì hệ luật sinh ra gồm 187 luật, số lỗi phân lớp là 24/310 mẫu dữ liệu, tỉ lệ phân lớp 62 đúng là 92.26%. Kết quả tối ưu bộ tham số mờ được tinh chỉnh tự động cùng mức phân hoạch được thể hiện trong bảng 3.5, hệ luật sinh ra gồm 139 luật, số lỗi phân lớp là 13/310 mẫu dữ liệu, hiệu quả phân lớp đạt 95.8%. Bảng 3.4 Các tham số gia tử tối ưu bằng trực quan cho bài toán Vertebral Column Thuộc tính µj(L) µj(V) kj fmj(c-)
0.271 fmj(c+)
0.729 0.283 0.717 3 PI 0.472 0.528 0.135 0.865 3 PT 0.51 0.49 0.661 0.339 3 LA 0.306 0.694 0.155 0.845 2 SS 0.774 0.226 0.338 0.662 3 PR 0.101 0.899 0.662 0.338 3 GS Bảng 3.5 Các tham số gia tử tối ưu bằng thuật toán FBO-SGA cho bài toán Vertebral Column Thuộc tính µj(L) µj(V) kj fmj(c-)
0.308 fmj(c+)
0.879 0.56 0.366 3 PI 0.418 0.686 0.527 0.639 3 PT 0.753 0.762 0.804 0.232 3 LA 0.419 0.693 0.755 0.539 2 SS 0.176 0.558 0.176 0.741 3 PR 63 0.436 0.896 0.436 0.32 3 GS Bảng 3.6 So sánh về số lỗi và tỉ lệ phân lớp giữa các bộ tham số Phương pháp tinh chỉnh bộ tham số Số lỗi Tỉ lệ phân lớp Mặc định 99 68.1% Trực quan 24 92.26% Tự động 13 95.8% 3.4 Kết luận chƣơng 3 Trong chương này của luận văn đã ứng dụng thuật toán FPO-SGA để tối ưu tham số mờ gia tử và mức phân hoạch cho 2 bài toán là Seeds và Vertebral Column. Mỗi bài toán có các đặc trưng riêng về số thuộc tính, số lượng mẫu dữ liệu, mức độ chênh lệch về số lượng mẫu, sự phân bố dữ liệu giữa các lớp. Thuật toán di truyền tìm kiếm bộ tham số mờ tối ưu còn tốn khá nhiều thời gian, mặc dù không gian các tham số cần tìm kiếm đã được giảm bớt, có 64 thể do sự phức tạp và đa dạng của các bài toán ứng dụng. KẾT LUẬN Sau quá trình nghiên cứu tìm hiểu và thực hiện đề tài, tôi có một vài kết luận sau: - Hệ mờ có tiềm năng to lớn để ứng dụng vào việc giải quyết các vấn đề của các hệ thống phức tạp như hệ sinh học, hệ xã hội, hệ kinh tế và hệ thống chính trị. Mặt khác, hệ mờ còn có thể ứng dụng trong các hệ thống ít phức tạp, ở đó không cần một giải pháp chính xác mà chỉ cần một giải pháp xấp xỉ nhưng nhanh hơn, hiệu quả hơn và giảm chi phí tính toán. - Các tham số gia tử có ảnh hưởng rất lớn đến kết quả bài toán. Độ đo tính mờ của gia tử và độ đo tính mờ của phần tử sinh, mức phân hoạch k làm thay đổi không gian hệ khoảng tính mờ, từ đó ảnh hưởng đến kết quả bài toán. - Phương pháp tinh chỉnh tham số mờ gia tử bằng trực quan kinh nghiệm của người dùng đôi khi sẽ đưa ra kết quả không tối ưu - Sử dụng giải thuật di truyền để tìm kiếm bộ tham số tối ưu sẽ cho ra 65 được kết quả tương đối tối ưu. TÀI LIỆU THAM KHẢO Tiếng Việt 1. Dương Thăng Long (2010), Phương pháp xây dựng hệ mờ dạng luật với ngữ nghĩa dựa trên đại số gia tử và ứng dụng trong bài toán phân lớp, Luận án tiến sĩ toán học, Viện Công nghệ Thông tin. 2. Dương Thăng Long, Trần Tiến Tùng, Trần Tiến Dũng (2013), A HA based Fuzzy Association Rule Extracting Method for Classification on High-Dimensional Datasets, Kỷ yếu hội nghị quốc gia lần thứ VI về nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR). 3. Nguyễn Cát Hồ, Dương Thăng Long, Trần Thái Sơn (2009), “Tiếp cận đại số gia tử cho phân lớp mờ”, Tạp chí tin học và điều khiển học, Tập 25(1), tr 53-68. 4. Nguyễn Ngọc Hoan (2008), Tiếp cận mờ và tiếp cận đại số gia tử trong điều khiển hệ quạt gió – cánh nhôm, Luận văn thạc sĩ khoa học máy tính, Trường ĐH Công nghệ thông tin và truyền thông Thái Nguyên. 5. Nguyễn Cát Hồ (2008), Cơ sở dữ liệu mờ với ngữ nghĩa đại số gia tử, Bài giảng Trường thu – hệ mờ và ứng dụng, Viện Toán học Việt Nam Tiếng Anh 6. A. Fernández, F. Herrera (2012), “Linguistic Fuzzy Rules in Data Mining: Follow-Up Mamdani Fuzzy Modeling Principle”, STUDFUZZ, vol. 221, pp 103-122. Website: 7.http://archive.ics.uci.edu/ml/datasets.html?format=&task=cla&att=&area=& numAtt =&numIns=&type=&sort=nameUp&view=table 66 8. http://doc.edu.vn/tai-lieu/thuat-giai-di-truyen-genetic-algorithm-59141/W
Rất nóng
Hơi Lạnh
Hơi nóng
Rất Lạnh
0
1
X(kj)
0
1
0
1
![Luận văn Thạc sĩ: Tổng hợp và đánh giá hoạt tính chống ung thư của hợp chất lai chứa khung tetrahydro-β-carboline và imidazo[1,5-a]pyridine](https://cdn.tailieu.vn/images/document/thumbnail/2025/20250807/kimphuong1001/135x160/50321754536913.jpg)
