Ứng dụng lập luận mờ trong dự đoán kết quả sát hạch quốc gia của học viên lái xe

d Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được ai công bố trong bắt kỳ công trình nào khác.. Phạm vi nghiên cứu Đề tài được thực hiện trong phạm vi của một Luậ

BỘ GIÁO DỤC VÀ ĐÀO TẠO

DAI HOC HUE

TRUONG DAI HOC KHOA HOC

PHAN PHU BINH

UNG DUNG LAP LUAN MO TRONG

DU DOAN KET QUA SAT HACH QUOC GIA

CUA HOC VIEN LAI XE CHUYEN NGANH: KHOA HOC MAY TiNH

MA SO: 60.48.01.01

LUAN VAN THAC SI KHOA HOC DINH HUONG NGHIEN CUU

NGUOI HUONG DAN KHOA HOC PGS.TS LE MANH THANH

Thừa Thiên Huế, 2018

LỜI CAM ĐOAN

Tôi xin cam đoan:

a Những nội dung trong luận văn này là đo tôi thực hiện đưới sự hướng

dân khoa học trực tiếp của Ti hầy Lê Mạnh Thạnh

b Mọi tham khảo dùng trong luận văn này đều được trích dẫn rõ ràng và trung thực tên tác giả, tên công trình, thời gian, địa điểm công bố

c Moi sao chép không hợp lệ, vi phạm quy chế đào tạo, hay gian trả, tơi

xin chịu hồn toàn trách nhiệm

d Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được ai công bố trong bắt kỳ công trình nào khác

HỌC VIÊN

e_ Giao hoán: T(P)¡ or P;)= T(P; or Pịụ)

s_ Kết hợp: TP; or(ŒP¿ or P)) = T(Œ) or P›) or P))

e_ Nếu T(P,) <T(P;) thì TP, orP¿)<T(P›orP¿) Vmệnh đề P,

" Phép kéo theo (Implication)

Phép kéo theo mờ là một dạng luật (rule) được xác định như sau:

R=P->Q =]F "V là A" THEN "W là B"

được xây dựng từ 2 biến ngôn ngữ (V, X, Tv), (W, Y, Tự)

Ta có thé thay: R là quan hệ được xác định trên XxY giữa các giá trị của V

và các giá trị của W Gia tri cia R thể hiện độ mạnh của mối liên hệ giữa tiên để "V là A" và kết luận "W là B" Như vay, ta co thể xác định giá trị của phép kéo theo

mờ như sau:

tạ (X.Y) = Í(HAŒ), Ha(Y)) V(x,y) e(X,Y)

Với hàm /# từ [0,1] x [0,1] > [0,1]

Ham £, trừ những trường hợp đặc biệt, được chon sao cho phép kéo theo mờ

đồng nhất với phép kéo theo cổ điển Nghĩa là:

M„ Œ,Y) = fQ,1)= 1

Lưu ý: Không tồn tại một cách thức đuy nhất để mở rộng phép kéo theo của logic cổ điển Tùy thuộc vào xuất phát điểm đã chọn, ta có thể thu được những lớp kéo theo mờ các tính chất chung [1]

Trên cơ sở định nghĩa trên, người ta đã xây dựng một số hàm f cho phép kéo theo:

Phép kéo theo Boole (Boolean Implication)

br (Y) = (Vv Ha@y)

Trường hợp cho n luật có sử dụng liên két AND:

Ur (GY) — Ax (TACI-Hạ (X))V Ha(y) (& = 1, ,n)

Phép kéo theo Lukqsiewics

tạ (X.y) — LACI-HẠ (X)) + Ha(y))

Trường hợp cho n luật có sử dụng liên kết AND:

Trang

DANH MỤC CÁC BẢNG 22-222 222221122112111211121112211211221222222e i DANH MỤC CÁC HÌNH 522222 22222212212112112112112112222 re ii DANH MỤC CÁC TỪ VIẾT TẮTT -©222211221221122112211221221211211212 e6 iii MO DAU ooo coos eoscsosseseeveeseeseev tev tevtevtevabtettartattaritaseastistsresasesesetaeeasesanetases 1 Chương 1 LÝ THUYẾT TẬP MỜ 2-©2222212221222122212211221221.2 2 re 4 1.1 KHÁI NIỆM LOGIC MỜ . - 22 2222221221121112111211121112112112212 re 4 1.2.LÝ THUYÉT TẬP MỜ - 222 222222122112211211121112111221121112111222 xe 5 1.2.1 Tập vũ trụ 5-2 222221222122111211121112112112121212122 re 5 1.2.2 Tập mờ 2 22 222225121112111211121112111211121112112112221212122222 are 5 1.2.3 Các định nghĩa đặc trưng của tẬp mỜ i- cc tScnhrnrerrrrrrerre 6 1.2.4 Một số dạng hàm thuộc thường gặp -©22222222222212221222122 e6 8 1.2.5 VỊ tri cua tap mo trong m6 hinh MO eee eee eeeereneeneeteeeneenee 9

1.2.6 Bién ng6m nthe cece cece ceeseeeeseeesevteeeee tee tereeeteeseseeteteteeeteseneteeees 10 1.3 MỆNH ĐẺ MỜ VÀ LUẬT MỜ 222222122212212222222222 e6 10 1.3.1 Mệnh để mờ 222222 22122212221221121122112112112212222222 re 10 1.3.2 Luật mờ 2 22-221 222122212112112112211211222222222222 2 eeree 14 1.4 HỆ CHUYÊN GIA MỜ 2222222 222222122112112122122222222 ae 15 1.4.1 Cấu trúc hệ mờ 2-22 22212212221222121121121121121221222222 re 15 1.4.2 Cơ chế hoạt động của hệ mờ -2-©22222122122122212212211221221 2 xe 17 1:4:3 Phần tích loại hệ THỜ scecessoeotytthoatttitigtitdtiOEGGGRRHGRORHSTAGEASWq"GtQunquasa 18 1.5 KÉT LUẬN CHƯƠNG I -©222222222122212211221211221121121.2 2 e6 19 Chương 2 CÂY QUYẾT ĐỊNH MỜ - 52 222222212222 21

2.1 GIỚI THIỆU ©-2-222222122212212221121112111211211211211211212222 re 21

2.1.1 Khái niệm 22-222 2212211221122112111221121112111211112212222 re 21

2.1.6 Hệ điều khiển Quyết định mờ (Fuzzy logie Control/Decision System) 31

2.2 CÂY QUYÉT ĐỊNH MỜ 22s 122 1221221222122 21 eererrreai 32 2.2.1 Dữ liệu mẫu với biểu diễn mờ -2- 22 2222222225122512111211121112212 xe 33

2.2.2 Entropy mo và độ đo thông tin mỜ - S232 Ennrtierrerrrerre 36 2.2.3 Định nghĩa ngưỡng c3 12t nv nh HH Hà HH HH Hai grey 37 2.2.4 Thủ tục xây dựng cây quyết định mờ -2-©222222222222222122221 22x 38 2:2:5: ấp luấn với Euzzy: LỘ iecsesaseresasoriodstiiihottiiittotiotis4i8iiit4goniitagRgagrteta 40 3:2:6: Brobabilislio Euzzy TỔ puussszssnsssianviositfVESSEPRGBSHEEISHSIREISMBIRPABBismieeal 41

2.3 SO SANH CAC GIAI THUAT ID3, FID3 VA PFID3 «000 0 cece 46 2.3.1 Biểu diễn dữ liệu 22 22 222225122112111211121112111211221222122 re 46 2.3.2 Tiêu chuân kết thúc - 22 22222222251223121112111111211121112112222 re 46

2:3:3: EHITODV Scaxirpsessirtidixiitidtiyittfi3S115G1113 201356110 S53411005595 00133838631 86ã480mss9l 46 2,54Á SuW lUẬN sexsasesesaeimnenergsrnieniristientirrrosEttrrT01E15011010E6IEL00300 0108010010-558 0002 0060098 46

2.4 KẾT LUẬN -2-222221222121121122112112112122122222222 2e 47

Chương 3 ỨNG DỤNG DỰ BÁO KHẢ NĂNG SÁT HẠCH LÁI XE 48

3.1 HIỆN TRẠNG CỦA TRUNG TÂM KỸ THUẬT TỎNG HỢP - HƯỚNG NGHIỆP PHÚ YÊN 2 22222222122112211221122112122222 2e 48 3.2 TÌNH HÌNH ĐÀO TẠO -22222212221221221122222222 2e 49

3.2.1 Đặc điểm về công tác đảo {ẠO St HH Hà HH ghe Hà te 50

3.2.2 Chương trình đảo {ạO St vn nh HH Hà Hào hat 51

3.2.3 Tổ chức kiểm tra -©-2-22222212212111211121112112112112112122 ae 51

3;2:4; Tình:hỉnh hoetap: seeecsssyeceneroneer eee mensme mene memaeneeemenecrnuennees 52

3.3 BAL TOAN ooo cece cecc ese eeeeseeeeeeev te tn tet trtetetetenetetteesenstecesensteeees 53 3.4 PHUONG PHAP GIAI QUYET oooceccsccescecccsecsssessesstsssessesseesessesesessessesssesseres 53 3.5 XÂY DỰNG CƠ SỞ DỮ LIỆU -22222222212221222112212212212211221 2 xee 53 3.6 HUẦN LUYỆỆN 552 222221222121122112112212212222222222 22a 57 3.7 KÉT LUẬN -22222222122212221221211211211211212212222ea 60 KÉT LUẬN 2 22 2222211221121112111211121112212212122122122212121222 re 62 TÀI LIỆU THAM KHẢO 222 22222212221221222121121121121222222 xe 63

DANH MỤC CÁC BẢNG

Trang Bang 2.1: Dữ liệu huấn luyện trong tài liệu tham khảo -2-©22¿22z+22z22z22 25

Bảng 2.2 Dữ liệu mẫu về việc tự lái xe đi làm (Car DrIving) cccccccscs: 34

Bảng 2.3 Biểu điễn mờ của tập mẫu 22- 22 22222122211221122122122122222 e6 36

DANH MỤC CÁC HÌNH

Trang Hình 1.1 Hình minh họa Supp(Ä) c2: 21121112 x2 HH Hà Hà ng 6 Hình 1.2 Hình minh họa h((À)) - 1 2 221221121121 11211511111 21111111111 8111111 trệt 7 Hình 1.3 Hình minh họa KKe€r(A)) - - c2: 211211211221 11111111211111111 111111111 81 trệt 7 Hình 1.4 Dạng hình tam giác HẠ(X) 5c 2: 221211 2 12 Hà Hà ngan 8 Hinh: 1,5 Dang‘hinh thang: ta 68) ceceonecennceeeneneeennenenemee 9 Hình 1.6 Dạng hình chuông HẠ(X) 5 2: 22221122 x2 này the 9

Hình 1.7 Cấu trúc của một hệ mờ - 5222222222222 t2 tri 15

Hình 2.1 Cây quyết định biêu diễn Độ Tuổi va Loại Xe thể hiện nguy cơ gây tai nạn 22

Hình 2.2 Mô hình các thuộc tính khi được chọn - 22 222211222 z££szzxesssss 26

Hình 2.3 Cây quyết định với thuật tốn CL§ 222222 2222212221222121122,22 e6 28 Hình 2.4 Cây quyết định với thuật toán ID3 222222 222222122212212212222 e6 29

Hình 2.5 Mô hình hệ thống Điều khiên/Quyết định mờ - 2222222222222 31

Hình 2.6 Hình biểu diễn hàm thuộc của thuộc tính 7; rdfJic¬JqI 34

MỞ ĐẦU

1 LÝ DO CHỌN ĐÈ TÀI

Nhằm duy trì và nâng cao chất lượng đào tạo, sát hạch lái xe đạt được mục

tiêu là được cấp giấy phép lái xe, khi đó đòi hỏi người học phải có ý thức trách

nhiệm công dân, có đạo đức nghề nghiệp, nắm vững các quy định của Luật Giao thông đường bộ, có kỹ năng điều khiển phương tiện tham gia giao thơng an tồn

Hiện nay tại các cơ sở đào tạo lái xe trên địa bàn tỉnh Phú Yên, xây dựng bài

sát hạch lái xe cho các học viên chủ yếu được thực hiện bằng phương pháp thủ công, việc này thường mất thời gian và độ chính xác trong quá trình tập luyện các bài thi không đảm bảo về chất lượng Chỉ ở các Thành phố lớn và các tỉnh lân cận

thì có sân tập lái và sân sát hạch có sự hỗ trợ thiết bị chấm điểm tự động

Tại các Trung tâm sát hạch lái xe có gắn thiết bị chấm điểm tự động đòi hỏi

người học luyện tập các kỹ năng các tình huống một cách chính xác Qua đó các

khóa sát hạch đào tạo lái xe bằng thiết bị chấm điểm tự động đầu tiên được tổ chức

tại Trung tâm sát hạch lái xe Hồng Bàng tỉnh Khánh Hòa có tỷ lệ trượt tới 50%

Điều này cho thấy việc học và thi sát hạch lái xe bằng thiết bị chấm điểm tự động

không dễ như nhiều người từng nghĩ

Trung Tâm Kỹ Thuật Tổng hợp - Hướng nghiệp Phú yên là đơn vị hành chính sự nghiệp có thu đưới sự quản lý của nhà nước và trực tiếp là Sở Giáo dục và Đào tạo Phú Yên Trung Tâm Kỹ thuật Tổng hợp - Hướng nghiệp Phú Yên hoạt động chủ yếu là dạy nghề phổ thông cho học sinh Trung học cơ sở và Trung học phô thông, đồng thời có chức năng đào tạo nghé lai xe 6 tô cho nhân dân trong tỉnh

Phú Yên và các tỉnh lân cận

Tỉnh Phú yên là tỉnh có vị trí địa lý nằm ở miền trung trung bộ, dân số khoảng 800 nghìn dân, có đường sắt đi qua, sân bay Đông tác và cảng Vũng rô, đó là điều kiện để tỉnh Phú yên phát triển Hiện nay, nhiều công trình, đự án lớn dang khởi công thúc đẩy nền kinh tế Phú Yên phát triển, đòi hỏi có lực lượng lao động có tay nghề và nhất là lực lượng lái xe phục vụ công tác thi công nhà máy là rất lớn

lái xe ô tô dé tự phục vụ cho gia đình ngày càng lớn, đó là yếu tố quyết định tạo sự phát triển cho Trung tâm về công tác đào tạo, sát hạch lái xe

Bên cạnh đó khi tham gia dạy thực hành lái xe, các giáo viên dùng hình thức đánh giá tính cách, năng khiếu, chuyên cần của của học viên là các câu hỏi trắc

nghiệm với hình thức trả lời [Có/ không], điều này không thê hiện hết thái độ cảm

giác của người học V7 đụ: Bạn có thích nghề lái xe không? Hoặc bạn nhắm thi sát

hạch đậu không? thì câu trả lời [có/ không] không đáp ứng được cho học viên vì phần lớn câu trả lời theo cảm giác ngôn ngũ tự nhiên là: ít thích, thích vừa vừa, khá

thích, chắc là đậu

Chính vì vậy, dựa trên những kiến thức và năng lực chuyên môn của mình,

tôi có thê nghiên cứu và phát triển trong lĩnh công tác mà cụ thể là quản lý công tác

đào tạo, sát hạch lái xe ô tô nhằm đóng góp cho thực tiến đó là dự đoán kết quả sát hạch lái xe cho học viên của mình phụ trách

Có thé thay rang, việc ứng dụng lý thuyết lập luận mờ cho kết quả chính xác trong dự đoán khả năng thành công khi tham dự kỳ sát hạch đề cấp giấy phép lái xe của học viên Do đó tôi đã thực hiện chon dé tài “Ứng dụng lập luận mờ trong dự đoán kết quả sát hạch quốc gia của học viên lái xe”, nhằm giúp cho học viên lái xe tự tin, chủ động khi tham dự sát hạch, góp phần xây dựng khả năng tham dự kỳ

sát hạch cấp giấy phép lái xe ngày càng được nâng cao về chất lượng

2 MỤC TIỂU NGHIÊN CỨU

Dưới góc độ một cuộc nghiên cứu nhỏ của một người đang quản lý về công

tác đào tạo, sát hạch lái xe cơ giới đường bộ, tôi tiến hành thực hiện đề tài này Mục

đích chủ yếu là dựa vào các yếu tố của người học như: Tuổi tác, sức khỏe, nghề nghiệp, mức độ chuyên cân, kỹ năng, tâm lý, kết quả thi thử v.v đề du đoán một học viên nào đó có thể thi qua được kỳ thi sát hạch quốc gia hay không

3 DOI TUONG VA PHAM VI NGHIEN CỨU 3.1 Đối tượng nghiên cứu

Các đối tượng được đề tài tập trung nghiên cứu như sau: > Logic mé va cAy quyết định mờ

> Học viên học lái xe tại Trung Tâm Kỹ thuật Tổng hợp - Hướng nghiệp Phú Yên 3.2 Phạm vi nghiên cứu

Đề tài được thực hiện trong phạm vi của một Luận văn thạc sĩ ngành Khoa

học máy tính căn cứ theo chuyên môn nghiệp vụ được áp dụng tại Trung tâm Kỹ thuật Tổng hợp - Hướng nghiệp Phú Yên

4 PHƯƠNG PHÁP NGHIÊN CỨU

Lý thuyết: Tổng hợp và phân tích các tài liệu liên quan đến lập luận mờ, các kỹ thuật đã được sử dụng có kết quả để chọn lọc các phương pháp thích hợp để áp dụng vào giải quyết vấn đề đặt ra

Thực nghiệm: Thu thập các số liệu liên quan đến kết quả thi sát hạch trong mấy năm qua kết hợp với thu thập ý kiến chuyên gia để xây đựng tập lập luận và ứng dụng vào xây đựng hệ thống dự báo

5 Ý NGHĨA KHOA HOC VA THUC TIEN CUA DE TAI

Chương 1 LÝ THUYẾT TẬP MỜ

1.1 KHÁI NIỆM LOGIC MỜ

Légic mo (Fuzzy logic) được phát triển từ lý thuyết tập mờ đề thực hiện lập luận một cách xấp xỉ thay vì lập luận chính xác theo légic vị từ cỗ điển Lôgie mờ có thê được coi là mặt ứng đụng của lý thuyết tập mờ dé xử lý các giá trị trong thế giới thực cho các bài toán phức tạp.[Š]

Để minh họa, xét tình huống sau: Khi người đăng ký học lái xe được hỏi " Anh/Chị có thích điều khiển xe ô tô không?" Nếu câu trả lời là "Có" hoặc "Không"

thì xử lý đơn giản theo logic cỗ điển Tuy nhiên, phần lớn người được hỏi lại trả lời

ở một số dạng sau: "Dạ, chỉ hơi thích thôi ạ" hoặc "thích, nhưng không nhiều lắm" hoặc “hình như là thích"

Logic cổ điển có ý nghĩa rất lớn trong việc thực tiễn và là mục tiêu cơ bản cần hướng tới của mọi quá trình biểu diễn và xử lý thông tin, Tuy nhiên, để đạt được điều này là không đơn giản Trong thế giới hiện hữu xung quanh ta, các thông

tin đầu vào cần xử lý tổn tại rất nhiều các yếu tế khó có thể định lượng chính xác,

chăng hạn như:

Cô ấy rất trẻ Anh ấy khá cao

Ơng ta vơ cùng thơng mình

Tôi hơi thích học môn] oản

vv

Với những môi trường chứa đựng nhiều thông tin "mờ" và "không chính

xác" như vay, thi viéc su dung Logic cổ điển để suy luận và đưa ra tri thức là điều

bất khả thi Xuất phát từ thực tế đó, người ta để xuất ra việc sử dụng logic mờ để suy luận từ các thông tin trên với một sai số chấp nhận được Lô gic mờ cho phép độ liên thuộc có giá trị trong khoảng đóng 0 và 1, và ở hình thức ngôn ngữ, các

khái niệm không chính xác như "hơi hơi", "gần như", "khá là" và "rất" Cụ thể, nó

1.2 LY THUYET TAP MO

1.2.1 Tập vũ trụ

Ky hiéu U la tap vii tru (Universe of discourse) Khi do, U la miễn xác định

của các biến trong hệ thống (cả biến đầu vào và biến đầu ra)

Ví dụ: 1.1 Giả sử khi ta làm việc với biến "Nhiệt độ cơ thể người" thì: U= {xe RỊ 35C <x <42°C} Tuy nhiên, khi ta làm việc với biến "Tuổi đời của người" thì: U={x e N| 0<x< 150} 1.2.2 Tập mờ Định nghĩa: Cho một tập vũ trụ U Tập hợp Aˆ được xác định bởi đẳng thức: 1, (a) tt

A={ :ue U, py (uv) € [0,1]} Tap hop A” duoc goi la một tập hop mo trén tap U

Bién u lay giá trị trong U được gọi là biến cơ sở nên tập U còn được gọi là

tập tham chiếu hay miễn cơ sở Hàm , HẠ" :U -> [0,1] được gọi là hàm thuộc và giá trị Hạ (z) tại u được gọi là độ thuộc của phan từ u thuộc về tap mo A’ Ho tat ca cac tap mo trén miễn cơ sở U được ký hiệu là F(Ö),

F(U) = {uy :U=> [0.1] =[0,1]°

Có rất nhiều cach biéu dién hình thức một tập mờ Trong trường hợp U là

một tập hữu hạn, đếm được hay vô hạn liên tục, tập mờ A” có thể được biểu diễn

bằng các biểu thức hình thức như sau

“_ Trong trường hợp U hữu hạn U - {u;: 1 <i <n},ta cd thé viét:

AT= Per wy +60 ge Un

1t 1 u + 1t n

hay AT” »x SiS of, (u,)/m,

" Trong trường hợp này tập hợp mờ được gọi là tập mờ rời rạc

" Trong trường hợp U là vô hạn đếm được, U = {u¡ :1E 1,2, }, ta viết: A“= 3 ¡4<1l <œuL¿ (uj}/U¡

A= ƒ Ha (u)/u

Ví dụ: Xét tập mờ U gồm 5 người xị, xạ x; tương ứng có tuổi lần lượt là

10, 15, 50, 55, 70 và A” là tập hợp người "#é" Khi đó ta có thể xây dựng hàm thuộc như sau:

Hire (10) = 0.95, une (15) = 0.75, Une (50) = 0.35 ne (55)

= 0.30,pye (70) = 0.05

095 0.75 0.35 030 0.05

TapmoA , +, a x, 1, % Ty Xu FT Xs

Dinh nghia: Tap mo A’ co dang hinh thang xác định bởi bộ 4 giá tri (a, b, c, d), ký hiệu A’ = (a,b,c,d) và được xác định: 0 nếu x<a x- b-a Q néua<x<b Ha (u) = lnéu b<x<c d-x _ néuc<x<d

1.2.3 Các định nghĩa đặc trưng của tập mờ

Giả sử: X là tập vũ trụ, A là một tập mờ (HA/„) e [0;I]'V x eX)

1.2.3.1 Gia (Support)

Giá của A là tập hợp các phần tử của X sao cho hàm thuộc Mac >0 Ky hiéu: Supp(A)

1.2.3.2 Chiều cao của một tập mờ (Heigh)

Chiều cao của tập A là giá trị lớn nhất mà hàm thuộc kẠ(X) có thể đạt được (Vx €X)

Ky hiệu: h(A) = Max(ta(xj) (Vx €X, 1 = 1 n)

Hinh 1.2 Hinh minh hoa h(A)

1.2.3.3 Tập mờ chuẩn

Tập mờ A được gọi là tập mờ chuẩn nếu h(A)=1

Thông thường, người ta dùng các tập mờ được chuẩn hóa, nghĩa là có ít nhất mét phan tr x € X: pa(x) = 1

1.2.3.4 Tập mờ rỗng

Tập mờ A được gọi là tập mờ rong (Ký hiệu: ©), nếu h(A)= 0

A= Dnéu La(x) = 0, voi moi x EX

1.2.3.5 Hat nhân của tập mờ (Kernel)

Hạt nhân của A là tập các phần tử x;eX mà tại đó hàm thuộc kẠ(%;)= 1

Ký hiệu: Ker(A)

1.2.4 Một số dạng hàm thuộc thường gặp 1.241 Dạng hình tam giác Hàm này được xác định bởi 3 tham số {a,b,c} theo công thức: 0 x<a —_ asx <b tA(X) , — b<x <a c—b 0 c<x

Có thể biểu diễn công thức trên theo các hàm Max, Min

MA(X) = max (min ( —— ) 0)

A

0.5

0 a b c x

Hinh 1.4 Dang hinh tam giác HẠ(X) 1.2.4.2 Dang hinh thang

Có thể biểu diễn công thức kẠ(x) theo các hàm Max, Min

kA(X) = max [min == ay a 5Ì] > -a d-c 0 abc dX Hình 1.5 Dạng hình thang a(x) 1.243 Dạng hình chuông Hàm này được xác định bởi 3 tham số {a, b, c} theo công thức: HA(X)= ————y Me 1+ a 1 0.5 0 a >

Hinh 1.6 Dang hinh chuông kạ(x) 1.2.5 Vị trí của tập mờ trong mô hình mờ

Khi một mô hình được xây dựng trên cơ sở logic mờ, mỗi tập mờ thường

Biến ngôn ngữ (nguistic variables) là bién ma giá trị thường là một từ hay

một câu hơn là một số xác định [6]

Một biến ngôn ngữ được xác định bởi một bộ ba (V;X;T,), trong do: V là một biến xác định trên tập vũ trụ X

Tập hợp Ty ={ AuA› A„) là hữu hạn hay vô hạn Với A, (ï=1 n) là các tập

mờ chuẩn hỏa của X dùng đề đặc tả L Như vậy, số lượng tập mờ A, trong T, nhiều hay it sé phụ thuộc vào yêu cầu mức độ rõ ràng khi đặc ta V

1.3 MẸNH ĐÈ MỜ VÀ LUẬT MỜ 1.3.1 Mệnh đề mờ

1.3.1.1 Khái niệm

Một mệnh để mờ P là một câu chỉ ra một khái niệm nao dé không rõ ràng, được xác định nhiễu giới hạn Giá trị chân lý của P có thể là một giá trị nào đó

trong khoảng [0;1], tire la:

T: xeX -> [0:1]

Các mệnh để mờ được gán cho tập mờ Giả sử mệnh dé P duoc gan cho tap

mờ A Khi đó, giá trị chân lý của mệnh đề được ký hiệu T(P) và được tính:

TP) = HẠ(X), 0 < HẠ(X) < Ì

Đăng thức trên chỉ ra rằng bậc chân lý của mệnh đề P: x là A là tương được

mức độ thuộc của x trong tập mờ A [2]

1.3.1.2 Các loại mệnh đề mờ

"_ Mệnh đề mờ không điều kiện và không bị giới hạn

Mệnh để mờ không điều kiện và không hạn chế là mệnh đề có dang sau

P: "x la A"

Trong đó x là giá trị trên tập vũ trụ X, A là tập mô trên X biểu thị ngữ nghĩa

của giá trị ngôn ngữ như fre, rất cao, nhanh nhẹn,

Khi đó, giá trị chân lý của P, ký hiệu tụ, (x), được xác định như sau: Up (X) = Up (X) VX EX

P:"xlàA" là z

Trong đó z là phép giới hạn chân lý mờ (fuzzy truth qualifier) và nó là tập

mờ trên tap U = [0,1]

Chang han, ta lay vi du mét ménh dé dang

“Kết quả học tập của sinh viên Nam là gidi la rat ding", hay "Trình độ Tiếng Anh của anh A là giỏi là hơi đúng"

Khi đó, giá trị chân lý của p(t, (x)) được xác định như sau: bp (X) =H (Ha(x)) Vx e X

"_ Mệnh đê điều kiện không giới hạn chân lý

Mệnh đề điều kiện không giới hạn chân lý (conditional and unqualified proposition) la ménh dé cé dang sau:

P: Nếu "x là A", thì "y là B"

Trong đó x và y là các biến xác định trên tập vũ trụ tương ứng X và Y, còn A và B là các tập mờ tương ứng trén X,Y

Như chúng ta đã dé cap trong khai niém vé quan hệ mờ, P xác định một quan hệ mờ R giữa hai đại lượng x và y, R là tập mờ trên diện tích Descartes X„Y Lúc nay, P được xác định như mục

"_ \/ệnh đề điều kiện và giới hạn chân lý

Mệnh đề điều kiện có giới hạn chân lý là mệnh để có đạng sau

P: "Nếu x là A, thì y là B" là z

Với r là giá trị chân lý ngôn ngữ biểu thị bằng hàm thuộc z(t), t e [0:1]

Như vậy, P sẽ xác định một quan hệ mờ R* với hàm thuộc R*(u, v) được

định nghĩa như sau:

R* (u,v)= r(R(u,v)) 1.3.1.3 Các phép toán cơ bản

" Các phép kết nổi mệnh đề

Các phép kết nối thông thường bao gồm: Phủ định (NOT), Hội (AND),

= Phép phu dinh (NOT - Negation)

Phủ định là một trong những phép toán cơ bản: T(P) = 1-T(P) Một số tính chất thường đùng: e T (P) chỉ phụ thuộc vào T(P) s_ Nếu T(P) = 1 thì T(P) = 0 e_ Nếu T(P) = 0thì TP) = 1 s_ Nếu T(P,) <T(P›) thì T(P,) <T(P›)

"_ Phép hội (IND — Conjuction)

Phép hội là một trong những phép toán logic cơ bản Ta xác định phép hội như sau:

PAQ:xi1sA and B

TPA Q)= Min (TP), TQ)

Một số tính chất thường đùng:

e_ 7(P¡ and P;) chỉ phụ thuộc vào T(P)), T(P;)

e_ Nếu TP) = 1 thì TP, andP;) = T(P;) Yménh dé P,

e_ Giao hoán : T(P¡ and (P› andP;) = T((P;and P;) and P;)

e_ Nếu T(P¡) <T(P›) thì TP, and P;) <T(P› andP;) Vmệnh đề P;

" Phép tuyén (OR - Disjuction)

e_ Giao hoán: T(P)¡ or P;)= T(P; or Pịụ)

s_ Kết hợp: TP; or(ŒP¿ or P)) = T(Œ) or P›) or P))

e_ Nếu T(P,) <T(P;) thì TP, orP¿)<T(P›orP¿) Vmệnh đề P,

" Phép kéo theo (Implication)

Phép kéo theo mờ là một dạng luật (rule) được xác định như sau:

R=P->Q =]F "V là A" THEN "W là B"

được xây dựng từ 2 biến ngôn ngữ (V, X, Tv), (W, Y, Tự)

Ta có thé thay: R là quan hệ được xác định trên XxY giữa các giá trị của V

và các giá trị của W Gia tri cia R thể hiện độ mạnh của mối liên hệ giữa tiên để "V là A" và kết luận "W là B" Như vay, ta co thể xác định giá trị của phép kéo theo

mờ như sau:

tạ (X.Y) = Í(HAŒ), Ha(Y)) V(x,y) e(X,Y)

Với hàm /# từ [0,1] x [0,1] > [0,1]

Ham £, trừ những trường hợp đặc biệt, được chon sao cho phép kéo theo mờ

đồng nhất với phép kéo theo cổ điển Nghĩa là:

M„ Œ,Y) = fQ,1)= 1

Lưu ý: Không tồn tại một cách thức đuy nhất để mở rộng phép kéo theo của logic cổ điển Tùy thuộc vào xuất phát điểm đã chọn, ta có thể thu được những lớp kéo theo mờ các tính chất chung [1]

Trên cơ sở định nghĩa trên, người ta đã xây dựng một số hàm f cho phép kéo theo:

Phép kéo theo Boole (Boolean Implication)

br (Y) = (Vv Ha@y)

Trường hợp cho n luật có sử dụng liên két AND:

Ur (GY) — Ax (TACI-Hạ (X))V Ha(y) (& = 1, ,n)

Phép kéo theo Lukqsiewics

tạ (X.y) — LACI-HẠ (X)) + Ha(y))

Trường hợp cho n luật có sử dụng liên kết AND:

Phép kéo theo Zaseh

br OGY) = Ca (X) A Max (y))V (l -HẠ ())

Luat mé kéo theo ca Zadeh khé ap dung trong thue té va né kéo dai nhiéu năm cho đến khi Mamdani để xuất dạng đơn giản hơn và thường được sử dụng trong điều khiển mờ

Phép kéo theo Mamdani

Up (XY) = (Ha (X) A Hex (y)) = min (Ha (X), Up (y))

Trường hợp cho n luật có sử dụng lién két OR:

br (X.Y) = Vi Citak (8) A Hay (9) (È= J, 0)

Phép kéo theo Larsen

Ur (XY) = a(x) * Up (Y)

Trường hợp cho n luật có sử dụng lién két OR:

Ur (GY) = Vẹ (HẠk (X) “ Hay (V)) (È= 1 1)

1.3.2 Luật mờ

1.3.2.1 Luật đơn giản (Simple Rule)

Luật mờ (Fuzzy Rule) là cách biểu diễn một suy luận, nếu chúng ta biết được một sự kiện (tién đề, giả thiết) thì chúng ta có thể rút ra một kết luận Hình thức một

luật mờ đơn giản thông thường được biểu dién đưới dáng ngôn ngữ tự nhiên như: Nếu <tiền đề>, thì < kết quả>

Cho một luật đơn giản để xét hồ sơ đăng ký học nghề, với tiêu chí: nếu đã tốt nghiệp 12/12 thì được đăng ký bậc học là Cao đẳng, như sau:

Nếu (Trình độ là lớp 12) thì (Bậc học là Cao đẳng)

Phần "7rừnh độ là lớp 12" được gọi là phần tiền dé (hay giả thuyết), phần "Bác học là Cao Đẳng" được gọi là phần kết quả (hay kết luận)

Một luật với cấu trúc như trên được gọi là luật mờ chuẩn tắc

1.3.2.2 Luật phức hợp

Khi đó khi xây dựng cơ sở luật phục vụ cho cơ chế suy diễn, việc đầu tiên là

phải phân rã các luật phức hợp và biến đổi về một số luật cô điển đơn giản bằng cách sử dụng các tính chất và toán tử đã định nghĩa trong tập mờ

1.4 HỆ CHUYÊN GIA MỜ

1.4.1 Cấu trúc hệ mờ

Và tổng thể, mỗi mô hình nói chung đều bao gồm các đầu vao (inputs), đầu

ra (output) cling với một bộ xử lý Bộ xử lý thực chất là một ánh xạ phản ánh dự phụ thuộc của biến đầu ra hệ thống đối với các biến đầu vào Đối với mô hình mờ, các yếu tố đầu vào nhận giá trị số rõ, còn đầu ra có thể là một tập mờ hoặc một giá trị SỐ rõ Quan hệ ánh xạ của đầu ra đối với các đầu vào mô hình mờ được mô tả bằng một tập luật mờ, thay vì một hàm số tường minh Cụ thể hơn, cấu trúc cơ bản

của một hệ mờ bao gồm các thành phan chu dao: Sơ sở tri thức TNPUT Bộ tham số Cơ sở luật OUTPUT Ỷ Vv i

— Giao dién Giao ị RẺ

(Giả trị rõ) mờ hóa điện khử (Gia tri rd)

Vv `

————————>l|_ Cøsở truy điễn

(Giá trị mờ) (Giá trị mờ)

Hình 1.7 Cấu trúc của một hệ mờ

- Cơ sở ludt (rule base) nơi chứa đựng tập các luật mờ IF- THEN, thực chất

là một tập các phát biêu hay quy tắc mà con người có thể hiểu được, mô tả hành vi

của hệ thống, chẳng hạn:

Hai luật trên mô tả quan hệ điển hình giữa Trình độ học sinh và Bậc học

tương ứng khi đăng ký học

Một cách hình thức, với mô hình mờ n đầu vào - một đầu ra, mỗi luật mờ có thể được mô tả như sau:

rj: IF (x, is A; ) AND AND (x, 1s A, ) THEN (y is B’) (cj)

Trong đó, 4; (với k= 1, n) và B lần lượt là các giá trị ngôn ngữ được định

nghĩa trên các biến đầu vào và đầu ra mô hình Phần giả thiết của luật được hình thành từ sự giao nhau (Intersection) (thực hiện bởi p hép hội mờ - fuzzy AND) giữa

các phát biểu dạng ngôn ngữ, xự, 1s 44j, k= I, n, gọi là các tiền để thành phân

Phần kết luận của luật được ánh xạ từ phần giả thiết thông qua phép kéo theo mờ ŒF Q (THEN Q) ) Tương ứng với mỗi luật, ta có độ tin cậy c¡ c[0.0; 1.0] Độ tin cậy của luật phản ánh tính đúng đắn của luật, cụ =0 chứng tỏ luật không tham gia vào việc xác định đầu ra của mô hình Mỗi cơ sở luật là sự kết hợp (bằng phép tuyên mờ- fuzzy OR) của tất cả các luật mờ

Các luật có thể được hình thành từ tri thức của chuyên gia con người hoặc rút ra từ các mẫu thực nghiệm Cơ sở luật là thành phần quan trọng nhất trong bất kỳ mô hình mờ nào

-Bộ tham số: quy định hình dạng hàm thuộc của giá trị ngôn ngữ được dùng

để biểu diễn mờ và các luật mờ Giá trị các tham số có thể được đánh giá bằng

kinh nghiệm của các chuyên gia con người hay là kết quả của quá trình khai phá tri

thức từ thực nghiệm Thông thường, cơ sở luật và bộ tham số được gọi chung là cơ

so tri thức

- Cơ chế suy điễn: Có nhiệm vụ thực hiện thủ tục suy diễn mờ dựa trên cơ sở tri thức và các giá trị đầu vào để đưa ra một giá trị dự đoán ở đầu ra

- Giao điện mờ hóa: Thực hiện chuyển đổi các đầu vào rõ thành mức độ

trực thuộc các giá trị ngôn ngữ

- Giao điện khử mờ: Có thể có hoặc không, thực hiện chuyên đổi kết quả

1.4.2 Cơ chế hoạt động của hệ mờ

1421 Mờ hóa

Các giá trị rõ đầu vào của hệ được dùng làm đối số cho các hàm thuộc ứng

với các giá trị ngôn ngữ tương ứng xuất hiện trong phần giả thiết mỗi luật mờ IF- THEN Sau bước này, ta đã xác định được giá trị chân lý của tiền đề nằm trong phan gia thiết của mỗi luật

142.2 Suy diễn

Giá trị chân lý của phần giả thiết mỗi luật được áp dụng lên phần kết luận

của luật đó thông qua phéo Kéo theo mờ Theo đó, với mỗi luật, mô hình thu được

ở phần kết luận một tập con mờ Phép Kéo theo mờ thông thường dựa trên hai toán tử là Min hoặc Product Khi suy diễn theo toán tử Min, tập mờ kết quả suy diễn

được hình thành từ hàm thuộc của giá trị ngôn ngữ phan kết luận bị cắt bởi một

đường ngang mà độ cao tương ứng với mức chân lý phần giả thiết Trong khi đó,

với toán tử Product, tập mờ kết quả suy diễn có hàm thuộc dựa trên hàm thuộc đầu

ra của kết luận được co giãn theo một tỉ lệ ứng với mức chân lý của phần giả thiết

1.4.2.3 Kết nhập

Tất cả các tập con mờ ứng với đầu ra của mỗi luật được kết hợp với nhau

(thông qua phép Hợp mờ) tạo thành một tập con mờ duy nhất biểu diễn biến mờ đầu ra cơ chế suy diễn Quá trình tính toán kết nhập thông thường dựa trên hai toán tử là

Max hoặc Sum Với Max, tập mờ tổng hợp đầu ra có giá trị hàm thuộc tại mỗi điểm

trên tập nền bằng giá trị hàm thuộc lớn nhất của tất cả các tập con mờ tương ứng ở

đầu ra mỗi luật tại điểm đó Trong khi đó, với Sum, tap mo tổng hợp đầu ra có giá trị hàm thuộc tại mỗi điểm trên tập nên bằng tổng giá trị hàm thuộc của tất cả các

tập con mờ tương ứng ở đầu ra mỗi luật tại điểm đó 142.4 Khử mờ

Công đoạn này là tùy chọn và được sử đụng khi cần cần chuyên đổi giá trị biến ngôn ngữ đầu ra thành một giá trị số rõ (điều này thường gặp với các mô hình

hệ thống điều khiến) Có rất nhiều kỹ thuật khử mờ nhưng phô biến được sử dụng là

đại, giá trị rõ được chọn là giá trị mà tại đó tập con mờ đạt giá trị chân lý cực đại

Nói chung, các phương pháp khử mờ này đòi hỏi nhiều chỉ phí tính tốn và khơng có cách nào để phân tích chúng một cách chính xác ngoại trừ việc thông qua các nghiên cứu thực nghiệm

1.4.3 Phân tích loại hệ mờ

Dựa trên cơ chế suy diễn mờ và các dạng luật mờ được sử dụng, phần lớn các hệ mờ có thể được xếp vào một trong ba loại mô hình sau:

1.43.1 Mô hình mờ Mamidanmi

Mô hình mờ Mamdani (còn gọi la m6 hinh ng6n ngit (linguistic models))

được để xuất với mục tiêu ban đầu là điều khiển tổ hợp nổi hơi và động cơ hơi

nước thông qua một tập luật dạng ngôn ngữ thu được từ những thao tác viên con người có kinh nghiệm Đây là dạng mô hình điển hình nhất, với bộ luật bao gồm

các luật mà phan tién dé va phan kết luận đều là các tập mờ Minh họa mô hình Mamdani hai luật điển hình với một đầu ra, chịu tác động của hai đầu vào rõ Xo va

vọ với phép hợp thành Product- Max

Rõ ràng, khả năng diễn đạt luật bằng ngôn ngữ tự nhiên đối với mô hình Mamdani rất đễ dàng và tường minh Tuy nhiên, kết quả của mô hình Mamdani lại

là tập mờ tổ hợp tử mỗi luật được sử dụng, do đó, khi muốn chiết xuất một giá trị rõ ở đầu ra mô hình, ta cần chọn một cơ chế khử mở phù hợp Điều nay it nhiéu anh

hưởng tới chi phí tính tốn

1.43.2 Mơ hình mờ Takagi- Sugeno

Mô hình mờ Takagi- Sugeno (hay còn có tên là mô hình mờ TSK) được đề xuất bởi Tkagi, Sugeno và Kang trong một nỗ lực nhằm phát triển cách tiếp cận mang tính hệ thống đối với quá trình sinh luật mờ từ tập dữ liệu vào - ra cho trước Mô hình mờ Takagi- Sugeno được cấu thành từ một tập các luật mờ mà phần kết

luận của mỗi luật này là một hàm (không mờ) ánh xạ từ các tham số đầu vào của mô hình tối tham số đầu ra mô hình Cụ thể, một luật mờ điển hình trong mô hình

Takagi- Sugeno có dạng:

Trong đó, A và B là các tập mờ trong phần tiền dé, trong khi Z= f(x,y) la một hàm rõ trong phần kết luận Thông thường f(x.y) là có dạng đa chức của hai biến x vày, tuy nhiên nó có thể là một hàm bất kỳ miễn là có thê mô tả đầu ra của hệ thống một cách thích hợp trong vùng không gian xác định bởi kết luận của luật

Ta thấy thủ tục suy diện mờ của mô hình mờ Takagi- Sugeno Trong trường hợp này công đoạn hợp thành và khử mờ trong quy trình suy diễn của mô hình tổng quát được thay thế bởi khâu tính toán giá trị trung bình có trọng số, do vậy tránh được chi phí thời gian cho khâu khử mờ

1.4.3.3 M6 hinh mo Tsukamoto

Trong m6 hinh mo Tsukamoto, phan kết luận của mỗi luật mờ ¡f- then được biểu diễn bằng một tập mờ với một hàm thuộc đơn điệu Giá trị đầu ra tổng thể là

trung bình có trọng số của đầu ra rõ của mỗi luật

Theo đó, đầu ra của mỗi luật được xác định là một giá trị rõ được suy ra tử

triển vọng của luật Đầu ra tổng hợp thu được từ giá trị trung bình có trọng số của

đầu ra của mỗi luật Hình sau minh họa toàn bộ thủ tục suy diễn của hệ hai đầu vào hai luật

1.5 KẾT LUẬN CHƯƠNG 1

Lý thuyết tập mờ áp dụng trên các lớp hay các nhóm dữ liệu mà trong đó ranh giới giữa chúng không phân định rõ ràng Bất kỳ phương pháp luận hay lý

thuyết nào thực hiện trên các khái niệm rõ như lý thuyết tập hợp kinh điển, số học và quy hoạch toán học, đều có thể được "làm mờ" bằng việc khái quát hóa từ khái niệm của một tập rõ thành một tập mờ

Lợi ích của việc mở rộng lý thuyết và các phương pháp giải tích rõ thành các kỹ thuật mờ là khả năng giải quyết các bài toán trong thế giới thực, nơi luôn tồn tại các yếu tổ tác động có bản chất không chính xác và có nhiễu, hệ quả của quá trình đo đạc và xử lý trong thực tế

Xét cho cùng, tập mờ là một công cụ toán học cho phép chuyền đổi từ giá trị

định lượng sang giá trị định tính Nói rộng ra, lý thuyết tập mờ là công cụ toán học

tập mờ rất phù hợp với việc mô phỏng hoạt động tư duy của con người Xét về khả năng xử lý các thông tin xấp xi để đưa ra quyết định

Như vậy, có thể nói, sự ra đời của lý thuyết tập mờ đã mở ra một nhánh quan

trọng trong việc biểu diễn tri thức và ý nghĩ của con người Đây chính là công cụ

Chương 2 CÂY QUYÉT ĐỊNH MỜ

2.1 GIỚI THIỆU

2.1.1 Khái niệm

(tiéng Anh: decision tree) là một đỗ thị của các quyết định và các hậu quả có thê của nó (bao gồm rủi ro và hao phí tài nguyên) Cây quyết định được sử dụng để xây

dựng một kế hoạch nhằm đạt được mục tiêu mong muốn Các cây quyết định được

dùng đề hỗ tro quá trình ra quyết định Cây quyết định là một dạng đặc biệt của cấu trúc cây

2.1.2 Giới thiệu chung

Trong lĩnh vực học máy, cây quyết định là một kiểu mô hình dự báo (predictive model), nghia la một ánh xạ từ các quan sát về một sự vật/hiện tượng tới các kết luận về giá trị mục tiêu của sự vật/hiện tượng Mỗi một nút trong (internal

node) tương ứng với một biến; đường nối giữa nó với nút con của nó thể hiện một

gia tri cu thể cho biến đó Mỗi nút lá đại diện cho giá trị dự đoán của biến mục tiêu,

Cây quyết định là một đồ thị phát triển có cấu trúc dạng cây được mô tả: Age NÓ 27.5 Age > 27.5 Car type Risk = High Car type €{family, truck} Car type € ⁄ \ Risk = High Risk= Low Hình 2.1 Cây quyết định biêu diễn Độ Tuổi và Loại Xe thể hiện nguy cơ gây tai nạn Trong đó:

* Root: la node trên cùng của cây

* Tnternal node: biểu diễn một kiểm tra trên một thuộc tính đơn (4)

* Nhánh: biểu dién két qua ctia kiém tra tai Internal node (—») * Node la: biéu dién su phân phối lớp ( O)

Học bằng cây quyết định cũng là một phương pháp thông dụng trong khai

phá dữ liệu Khi đó, cây quyết định mô tả một cấu trúc cây, trong đó, các lá đại diện cho các phân loại còn cành đại diện cho các kết hợp của các thuộc tính dẫn tới phân

loại đó Một cây quyết định có thể được học bằng cách chia tập hợp nguồn thành

các tập con dựa theo một kiểm tra giá trị thuộc tính Quá trình này được lặp lại một

cách đệ qui cho mỗi tập con dẫn xuất Quá trình đệ qui hoàn thành khi không thể

tiếp tục thực hiện việc chia tách được nữa, hay khi một phân loại đơn có thể áp

Cây quyết định cũng là một phương tiện có tính mô tả dành cho việc tính

toán các xác suất có điều kiện

Cây quyết định có thê được mô tả như là sự kết hợp của các kỹ thuật toán

học và tính toán nhằm hỗ trợ việc mô tả, phân loại và tổng quát hóa một tập dữ liệu cho trước

Dữ liệu được cho dưới dạng các bản ghi có dạng: (x, y) = (x1, x2, x3 , xk, y)

Bién phu thudc (dependant variable) y là biến mà chúng ta cần tìm hiểu, phân loại hay tổng quát hóa x1, x2, x3 là các biến sẽ giúp ta thực hiện công việc đó 2.1.3 Các kiểu cây quyết định

Cây quyết định còn có hai tên khác:

Cây hồi quy (Regression tree) ước lượng các hàm giá có giá trị là số thực

thay vì được sử dụng cho các nhiệm vụ phân loại (ví dụ: ước tính giá một ngôi nhà hoặc khoảng thời gian một bệnh nhân nằm viện)

Cây phân loại (Classification tree), nếu y là một biến phân loại như: giới tính (nam hay nữ), kết quả của một trận đấu (thắng hay thua)

Kết luận là cây quyết định giúp ta biến một biểu diễn dữ liệu phức tạp thành một câu trúc đơn giản hơn rất nhiễu

2.1.4 Ưu nhược điểm của cây quyết định Ưu điểm:

— Sinh ra các quy luật dễ hiểu: Chuyển đổi được sang tiếng anh hoặc SQL

— Thực thi trong lĩnh vực hướng theo quy luật — Dé dang tính toán trong khi phân lớp

— Xử lý thuộc tính liên tục va rời rạc

Nhược điểm: - Dễ xảy ra lỗi khi có quá nhiều lớp: vì chỉ thao tác với các lớp có giá trị dạng nhị phân - Chi phi tinh toán qua dat để huấn luyện: đo phải đi qua nhiều node để đến node 14 cuối cùng 2.1.5 Một số thuật toán 21.51 Giới thiệu

Có rất nhiều thuật toán khác nhau để xây dựng cây quyết định: CLS, ID3,

C4 5, SPRINT, Trong để tài chỉ nghiên cứu một số thuật tốn phơ biến

Ở đây, các thuật toán áp dụng cho bài toán “ Có Chơi Tennis” có tập huấn luyện

Bài Toán: David là quản lý của một sân đánh tennis nổi tiếng Anh ta dang có rắc rối chuyện các thành viên đến hay không đến Có ngày ai cũng muốn chơi tennis nhưng số nhân viên của sân lại không đủ phục vụ Có hôm, không hiểu vì lý do gi ma chang ai đến chơi và sân lại thừa nhân viên

Mục tiêu của David là tối ưu hóa số nhân viên phục vụ mỗi ngày bằng cách dựa theo thông tin dự báo thời tiết để đoán xem khi nào người ta sẽ đến choi tennis

Để thực hiện điều đó, anh cần hiểu được tại sao khách hàng quyết định chơi và tìm

hiểu xem có cách giải thích nào cho việc đó hay không Vậy là trong hai tuần, anh ta thu thập thông tin về:

Quang cảnh (Outlook), Nhiệt độ(Temp), Độ Âm (Humidity), Gió(Wind)

Và tất nhiên là số người đến chơi tennis vào hôm đó David thu được một bộ đữ liệu

Bảng 2.1: Dữ liệu huấn luyện trong tài liệu tham khảo [ 1]

DI Sunny Hot Hight Weak No

D2 Sunny Hot Hight Strong No

D3 Overcast Hot Hight Weak Yes

D4 Rain Mild Hight Weak Yes

D5 Rain Cool Normal Weak Yes

D6 Rain Cool Normal Strong No

D7 Overcast Cool Normal Strong Yes

D8 Sunny Mild Hight Weak No

D9 Sunny Cool Normal Weak Yes

D10 Rain Mild Normal Weak Yes

DỊ Sunny Mild Normal Strong Yes

D12 Overcast Mild Hight Strong Yes

D13 Overcast Hot Normal Weak Yes

D14 Rain Mild Hight Strong No

Cách đọc bảng 2.1 như sau: vào ngày DI lúc này trời đang nắng, có nhiệt độ cao, độ Âm cao và gió mạnh thì sẽ không có khách chơi tennis Các ngày từ D2 tới

V M6 hinh cac thuéc tinh duoc chon trong bang 2.1 trong hình 2.1:

Sunn Rainy High Normal Oveiicast Yes Yes

Yes Ves Yes Yes

a Ves vies Yes Yes

No Yes Yes No Yes No ` No No Yes No Yes No No Yes No No NTA D[1,2,8,9,11] D[3,7,12,13] DỊ45,6,10,14] D[1,2,3,4,8,12,14] D[5,6,7,9,10,11,13] a) Thuộc tính Outlook b) Thuộc tính Humidity Tafa Coot Me \ tong 5 Ye Yes Yes

Yes Yes Yes Yes Yes

No Yes Yes Yes Yes

No Yes No Yes Yes No Yes No PHI ãI No D[5,6,7,9] Yes No Yes No D[4,8,10,11,12] No Na D[2,6,7,11,12,14] DỊ[1,3,4,5,8,9,10,13]

c) Thuéc tinh Temp đ) Thuộc tính Wind

Hình 2.2 là sơ đỗ tóm tắt bốn thuộc tính được chọn nằm trong bang 2.1 Bén thuộc tính đó là điều kiện cần thiết cho việc khách có muốn chơi tennis hay không

Cách đọc sơ đồ đó như sau:

Trong thuộc tính outlook còn bao gồm 3 thuộc tính nữa la: Sunny, Overcast và Rain.Có nghĩa là khi trời bên ngoài năng thì xây ra 2 trường hợp khách chơi tennis và 3 trường hợp không chơi Và khi trời mát mẻ thì đều đồng ý đi chơi tennis Còn trời mưa thì có 3 trường hợp không chơi

Trong thuộc tính Humidity còn bao gồm 2 thuộc tính nữa là: High và Normal Có nghĩa là khi độ âm cao 3 trường hợp khách chơi tennis và 5 trường hợp không chơi Và nếu độ âm bình thường thì có 6 trường hợp khách chơi và 1 trường hợp khách không chơi

Trong thuộc tính Temp còn bao gồm 3 thuộc tính nữa là: Hot, Mild và Cool Có nghĩa là khi nhiệt độ nóng thì có 2 trường hợp khach choi tennis và 2 trường hợp không chơi Nếu nhiệt độ trung bình thì 4 trường hợp chơi và 2 trường hợp không chơi Còn nhiệt độ mát thì cỏ 3 trường hợp chơi va | không chơi

Trong thuộc tính Wind còn bao gồm 2 thuộc tính nữa là Weak và Strong Có nghĩa là khi gió yếu thì có 6 trường hợp chơi và 2 trường hợp không chơi Còn nếu gió mạnh thì 3 trường hợp chơi và 3 trường hợp không chơi

2.1.5.2 Thuật toán CLS

CLS là thuật toán được Hovland và Hint giới thiệu trong Concept Learning System vào những năm 50 của thế ki 20

}> Thuật toán CLS gồm các bước:

1) Tao | node T, node này gồm tất cả các mẫu của tập huấn luyện

2) Nếu tất cả các mẫu có thuộc tính quyết định mang giá trị “Yes” (hay thuộc cùng một lớp) thì cho nút T là “Yes” và dừng lại Và ngược

lại

3) Trường hợp các mẫu của tập huấn luyện thuộc cà 2 lớp “Yes” và

“No” thì chọn một thuộc tính X khác và tiếp tục lặp cho các node con

của X và quay lại bước 2

Outlook Sunny Rain Qvercas Wind Wind — Strong,wea Yes 1 Stron Wea Temp Ho Milld ‘Cool Yes N N N Yes

Hình 2.3 Cây quyết định với thuật toán CLS

Do vậy cùng với một tập mẫu đữ liệu huấn luyện nếu áp dụng thuật toán CLS với thứ tự chọn thuộc tính triển khai cây khác nhau, sẽ cho ra các cây có hỉnh dạng khác nhau Việc lựa chọn thuộc tính sẽ ảnh hưởng tới độ rộng, độ sâu, độ phức tạp của cây Vì vậy một câu hỏi đặt ra là thứ tự thuộc tính nào được chọn để

triển khai cây sẽ là tốt nhất Vấn để này sẽ được giải quyết trong thuật toán ID3 dưới đây

2.1.5.3 Thuật toán ID3

Cây Quyết Định theo thuật toán ID3: Outlook | Sunn Rain vercas Ỷ [D1,D2,D8,D9,D11] [D3,D7,D12,D13] [D4,D5,D6,D10,D14] Ssunnyl2+,3-] Soverl4+.0-] Siain[3+,2-] Humidity ˆ ==— Wind Normg~ Nett Ye Weak Neem Yes No Yes No

Hình 2.4 Cây quyết định với thuật toán ID3

Thuật toán [D3 được giới thiệu bởi Quinlan đã chứng tỏ là một phương pháp có hiệu quả và phổ biến để tìm những cây quyết định diễn tả thông tin được chứa

đựng hoàn toàn trong những tập dữ liệu giá trị rời rạc Tuy nhiên, vẫn còn có một số

khó khăn hay gặp phải trong áp đụng phương pháp này với những vấn để của thế

giới thực Ví dụ, cây quyết định được sinh là tương đương với một tập điều kiện lôgic có thứ tự mà mỗi điều kiện đúng với mọi phần tử của tập dữ liệu Nói cách

khác, nếu chúng ta sinh ra những luật phân lớp liên kết từ một tập các lớp với những giá trị của một số tập thuộc tính thì phân lớp đúng được bảo đảm cho mỗi phân tử trong tập huấn luyện Một hệ quả tự nhiên của tính chất này là ID3 cổ điển không thích hợp cho những cơ sở dữ liệu chứa đựng nhiễu đáng kê, từ đó các luật sinh ra sẽ khớp với nhiễu và điều này có thể đẫn tới một tỷ lệ lỗi cao khi phân lớp các trường hợp chưa thấy (unseen case) Hơn nữa, thường trong thực tế bài toán phân lớp những thuộc tính có giá trị liên tục cần phải phân vùng không gian liên quan nếu ID3 được ứng dụng Đây thực chất là cách tiếp cận được chấp nhận trong

Việc sử dụng phân vùng cứng trong trường hợp này là không hợp lý vì khi có những thay đổi nhỏ trong những giá trị của thuộc tính có thế dẫn đến những thay đổi bất ngờ và không thích hợp với lớp được gán Rõ ràng như vậy sẽ giảm bớt những khả năng khái quát hóa của hệ thống Một hạn chế hơn nữa là không có khả năng để sử dụng hay phân loại những điểm đữ liệu với một số những giá trị thuộc tính không xác định mặc dù trong thuật toán C4.5 vấn để này được giải quyết từng phần bằng việc khám phá mọi nhánh có thê có của cây phù hợp với điểm này và sau đó kết hợp vào kết quả

Cuối cùng là yêu cầu về tập các giá trị phân lớp là hữu hạn và loại trừ lẫn nhau có nghĩa ID3 cổ điển và C4.5 không thể được ứng dụng vào những vấn đề chung hơn như xấp xỉ chức năng hay sinh ra những luật đề tổng hợp thông tin được lưu trong những cơ sở dữ liệu lớn

Việc sử dụng tập mờ đề phân vùng các không gian có thê có những lợi thế quan trọng hơn là qua những cách tiếp cận truyền thống và khi được kết hợp với những phương pháp cây quyết định quy nạp cô điển có thể giúp giải quyết các khó khăn ở trên Cụ thê, những luật quyết định mờ có khuynh hướng linh hoạt và ít nhạy cảm hơn hơn đối với những thay đổi nhỏ của những giá trị thuộc tính gần những ranh giới phân vùng Cũng những luật như vậy sẽ có khuynh hướng có những khả năng khái quát hóa lớn hơn so với những bản sao cứng của chúng

Khái niệm phân vùng mờ cho phép ta để hợp nhất cả phân lớp chồng nhau (overlap) va phân lớp thuộc tính bên trong mô hình quy nạp của chúng ta một cách chặt chẽ Điều này có thể có những thuận lợi dưới dạng sự phức tạp của cây khi bằng chứng thực nghiệm đưa ra là nó ít hạn chế khái niệm phân vùng, cho phép

những lớp thuộc tính ít hơn sẽ được sử dụng Ngoài ra, nhiều bài toán có thể được

thé hiện tốt nhất sử dụng những khái niệm tự nhiên nhất tương ứng với những lớp chồng nhau (overlap) và từ đây phân vùng mờ này có thể tạo điều kiện thuận lợi

cho việc sinh ra những luật dễ hiểu hơn với con người Tất nhiên, có cách khác mà

ngữ tự nhiên Điều này đặc biệt hữu ích trong trường hợp những biến liên tục khi có thể giúp đưa những nhãn ngôn ngữ cho những tập mờ như vậy, chẳng hạn, cao, trung bình và thấp Một lợi thế hơn nữa trong phân vùng mờ là cho phép cây quyết định sẽ được sử dụng trong phối hợp với một phương pháp giải mờ cho hàm xấp xi 2.1.6 Hệ điều khiển Quyết định mờ (Euzzy logic Control/Decision System)

xs Bộ u(x) Đông cơ HỘ) _ [ Bộ khử Mò LÝ x

Mờ hóa suy điền

Cơ sở luật

mờ

Hình 2.5 Mô hình hệ thống Điều khiển/Quyết định mờ

Trong hệ thống trên, với các giá trị đầu vào X, hệ mờ sẽ cho kết quả đầu ra y

Nếu y là một hành động điều khiển cho một thiết bị, thì hệ thống trên là hệ điều

khiển mờ Còn không, đó là hệ quyết định mờ

Bộ mờ hóa (Fuzzifter) chuyển các dữ liệu được đo lường rõ thành các giá trị

ngôn ngữ thích hợp Cơ sở luật mờ (Fuzzy rule base) giữ những tri thức vận hành tiến trình của các chuyên gia trong lĩnh vực đó Động cơ suy diễn Inference Engine) là cốt lỗi của hệ thống Nó có khả năng mô phỏng việc ra quyết định của con người

bằng cách lập luận xấp xi, để từ đó, đạt được chiến lược điều khiển mong muốn Bộ

khử mờ (Defuzzifier) sẽ sinh ra các quyết định hoặc các điều khiển “rõ” từ kết quả mờ cung cấp bởi động cơ suy diễn

1 Mờ hóa: Tính toán các giá trị mờ từ các giá trị chính xác ở đầu vào

2 Cơ sở luật mờ: Một luật mờ là một biểu thức ¡f- then duoc phát biểu ở dạng ngôn ngữ tự nhiên thể hiện sự phụ thuộc nhân quả giữa các biến Luật mờ có dang: Rj: IF x la Ai, AND y la Bi THEN z = Ci (i=l, 2, ., n), với x, y, Z là các bién ngôn ngữ

mô tả trạng thái của hệ thống và A, B, C là các giá trị ngôn ngữ tương ứng Một

cách viết khác của luật mờ: Rị: IF x là Ai, , AND y là BI THEN z = f(x, ., y), với

Vi dụ: 1f nhiệt độ là lạnh và giá dau 1a ré then sưởi âm nhiều Trong do, nhiét độ, “giá dầu” và sưởi ấm là các biến còn lạnh “rẻ nhiều” là các giá trị hay chính là các tập mờ

3 Suy điễn mờ: Áp dụng tất cả các luật mờ có thể áp dụng để tính ra giá trị mờ cho

kết luận, sau đó kết hợp các kết quả đầu ra

4 Khử mờ: Xác định giá trị chính xác từ kết quả mờ có được ở bước 2 Có nhiều kỹ thuật Khử mờ có thế áp đụng được, phương pháp thông đụng nhất là phương pháp trọng tâm (centriod method)

2.2 CÂY QUYÊT ĐỊNH MỜ

Điểm không thuận lợi của cây quyết định là tính ko ổn định của nó Cây

quyết định được thừa nhận như một cách phân lớp dé thay đổi bậc nhất về khía cạnh phụ thuộc vào dữ liệu huấn luyện, cấu trúc của cây quyết định có thể khác hoàn

toàn nếu có thay đổi nào đó trong tập đữ liệu Dé khắc phục vấn đề này, một số nhà nghiên cứu đã đưa ra Cây quyết định Mờ bằng cách sử đụng lý thuyết tập mờ để

diễn tả mức độ quan hệ của các giá trị của thuộc tính, điều này có thể phân biệt chính xác sự phù hợp của các quan hệ phụ thuộc giữa các ví dụ huấn luyện khác nhau và mọi giá trị của thuộc tính

Ban đầu, Fuzzy ID3 chỉ là mở rộng của thuật toán ID3 bằng cách áp dụng tập mờ Nó sinh ra một cây quyết định Mờ sử dụng các tập mờ định nghĩa bởi một người dùng cho tất cả các thuộc tính và dùng entropy mờ tối thiêu đề lựa chọn các thuộc tính mở rộng [ 10]

Tuy nhiên, kết quả của thuật toán Fuzzy ID3 này khá hạn chế về độ chính xác trong việc học Đề giải quyết van dé này, hai tham số then chốt là tham số điều khiển mờ 0, và ngưỡng quyết định lá 0, được đưa ra Bên cạnh entropy mờ tối

thiểu, nhiều tiêu chuẩn khác nhau được đưa ra để chọn ra các thuộc tính mở rộng

như là sự nhập nhằng phân loại tối thiểu, mức độ quan trọng của sự đóng góp của

thuộc tính vào việc phân loại