Bài giảng: Các hệ cơ sở tri thức - Trần Nguyên Hương

ệ ơ ở

Các h c s tri th c ứ KBS: Knowledge Based Systems

Tr n Nguyên H ng

ươ

ầ

1

H c s tri th c

ệ ơ ở

ứ

ề ệ ơ ở

ễ

ậ

ng 1: T ng quan v h c s tri th c ứ ổ ng 2: Bi u di n và suy lu n tri th c ứ ể ng 3: H MYCIN ệ ng 4: H h c ệ ọ ng 5: H th ng m cho các bi n liên t c ụ ệ ố

ế

ờ

 Ch ươ  Ch ươ  Ch ươ  Ch ươ  Ch ươ  …….

2

Tài li u tham kh o

ệ

ả

1. GS.TSKH. Hoàng Ki m. ế Giáo trình các h c ệ ơ ứ . NXB Đ i h c Qu c gia Thành ph ố ạ ọ

ố

2. Đ Trung Tu n.

s tri th c H Chí Minh – 2007 ệ

ấ H Chuyên gia

. NXB Giáo d c ụ

ở ồ ỗ 1999

3. Robert I Levine. Knowledge Based Systems.

Wissenschafs Verlag, 1991.

3

Ch

ng 1. T ng quan v H c s tri th c

ươ

ề ệ ơ ở

ứ

ổ

ứ

ệ

c thi

ng trình máy tính đ

1.1. Khái ni m v H c s tri th c (CSTT) ề ệ ơ ở  H CSTT là ch ươ

t ế ượ i quy t v n đ ề ế ấ

ả

ệ k đ mô hình hoá kh năng gi ả ế ể i c a chuyên gia con ng ườ ủ ự ệ

ệ

ố

ứ

ứ

ủ ế ấ

ứ

ề

 H CSTT là h th ng d a trên tri th c, cho phép mô hình hoá các tri th c c a chuyên gia, dùng tri th c này đ gi i quy t v n đ ph c ể ả ứ t p thu c cùng lĩnh v c. ự ạ

ộ

 Hai y u t

ố

ế

ọ

ệ ươ

ứ

ậ

ớ

ơ ở

ậ ứ

ộ

quan tr ng trong H CSTT là: tri ng ng v i 2 th c chuyên gia và l p lu n, t ứ kh i chính là c s tri th c và đ ng c suy ơ ố di n.ễ

4

5

6

1.2. C u trúc c a H chuyên gia ủ

ệ

ấ

Đ ng c suy di n ơ

ễ

ộ

B x lý ngôn ộ ử nhiên ng t

ữ ự

Tìm ki mế

Đi u khi n

ề

ể

Gi

i thích

ả

C s tri th c ứ

ơ ở

Vùng nh làm vi c ệ ớ

S ki n ự ệ

Ng

i ườ

Lu tậ

Ti p nh n tri th c ứ ậ

ế

7

chuyên gia

8

9

10

1.4. H h c

ệ ọ

 Trong nhi u tình hu ng, s không có s n tri th c nh : ư ẽ

ứ

ề

ẵ

ố

chuyên gia lĩnh v c.

ậ

ứ

ự

ả

ụ ể

c bi u di n t

ng minh theo lu t, s ki n

ứ ừ lĩnh v c c th ự ễ ườ ể

ượ

ự ệ

ậ

– K s tri th c c n thu nh n tri th c t ầ ỹ ư – C n bi t các lu t mô t ậ ế ầ – Bài toán không đ hay quan h .ệ

 Có 2 ti p c n cho h th ng h c ọ

ệ

ệ Bao g m vi c hình th c hoá, s a ch a các

ử

ữ

c áp d ng cho nh ng h th ng đ

ế – H c t ọ ừ lu t t ậ ườ – H c t ọ ừ ữ ệ

ụ

ự ệ ố: đ ượ ố

i d ng s liên quan đ n các k thu t nh m t ế

ệ ố ằ ậ

ữ ỹ

ệ ố ậ ký hi u: ứ ồ ng minh, s ki n và các quan h . ệ d li u s ướ ạ ọ

ạ

ồ

i di truy n, bài toán t

ề

ố

c ượ mô hình d i u ố ư các tham s . H c theo d ng s bao g m: M ng Noron nhân ố ố i u truy n th ng. Các k t o, thu t gi ỹ ố ư ả ậ ạ thu t h c theo s không t o ra CSTT t ậ ọ

ườ

ạ

ạ ề ng minh.

ố

11

12

13

14

Ch

ươ

Bi u di n và suy lu n tri th c

ứ

ể

ễ

ng 2. ậ

Tr n Nguyên H ng

ươ

ầ

15

Ch

ng 2: Bi u di n và suy lu n tri th c

ươ

ứ

ể

ễ

ậ

ự

ở ầ ứ

ứ

1.

ứ

ả

ạ

ứ

ườ

ứ

ể

ế

ậ

2.1. M đ u  Tri th c, lĩnh v c và bi u di n tri th c. ế ể c chia thành 5 lo i 2.2. Các lo i tri th c: đ ạ ượ ứ ạ i quy t m t v n đ . Lo i tri cách gi ủ ụ : mô t Tri th c th t c ề ộ ấ ế ả i pháp đ th c hi n m t công vi c nào đó. th c này đ a ra gi ệ ộ ệ ể ự ả ư ng là các lu t, chi n Các d ng tri th c th t c tiêu bi u th ủ ụ l c, l ch trình và th t c. ượ

ủ ụ

ạ ị

2.

: cho bi

ộ

ế

ứ

ấ

ạ

ứ

ề ượ ể

ơ

ứ

ặ

ạ

ị

ả ầ

ẳ ộ

ằ

ị

ng hay m t khái ni m nào đó.

c th y nh th Tri th c khai báo t m t v n đ đ ế ư ấ nào. Lo i tri th c này bao g m các phát bi u đ n gi n, d i ướ ả ồ d ng các kh ng đ nh logic đúng ho c sai. Tri th khai báo cũng đ y đ có th là m t danh sách các kh ng đ nh nh m mô t ủ ể h n v đ i t ề ố ượ

ẳ ệ

ộ

ơ

16

2.2.Các lo i tri th c (ti p)

ứ

ế

ạ

3. Siêu tri th cứ : mô t

ả

tri th c v tri th c. Lo i tri th c này giúp l a ạ

ứ

ứ

ứ

ự

ề

i quy t

ch n tri th c thích h p nh t trong s các tri th c khi gi ấ

ứ

ứ

ợ

ọ

ố

ả

ế

m t v n đ . Các chuyên gia s d ng tri th c này đ đi u ch nh ử ụ

ộ ấ

ể ề

ứ

ề

ỉ

hi u qu gi

i quy t v n đ b ng cách h

ả ả

ệ

ế ấ

ề ằ

ướ

ng các l p lu n v ề ậ

ậ

mi n tri th c có kh năng h n c . ả

ứ

ề

ả

ơ

4. Tri th c heuristic

: Mô t

các “m o” đ d n d t ti n trình l p

ứ

ả

ắ ế

ể ẫ

ẹ

ậ

lu n. Tri th c heuristic là tri th c không b o đ m hoàm toán ứ

ứ

ả

ả

ậ

100% chính xác v k t qu gi

i quy t v n đ . Các chuyên gia

ề ế

ả ả

ế ấ

ề

th

ng dùng các tri th c kho h c nh s ki n, lu t,… sau đó

ườ

ư ự ệ

ứ

ậ

ọ

chuy n chúng thành các tri th c heuristic đ thu n ti n h n ứ

ể

ể

ệ

ậ

ơ

trong vi c gi

ệ

ả

i quy t m t s bài toán. ộ ố

ế

17

2.2.Các lo i tri th c (ti p)

ứ

ế

ạ

ả

ấ

ứ

5. Tri th c có c u trúc: mô t

ả

ứ ứ

ấ ệ ố

ổ

ủ

ồ

ố ượ

ả

ệ ữ

ứ ấ

tri th c theo c u trúc. Lo i ạ mô hình t ng quan h th ng theo tri th c này mô t quan đi m c a chuyên gia, bao g m khái niêm, khái ể ng; di n t ni m con, và các đ i t ch c năng và ễ ệ m i liên h gi a các tri th c d a theo c u trúc xác ự ứ ố đ nh. ị

18

Ỹ

Ể

Ễ

2.3. CÁC K THU T BI U DI N TRI Ậ TH CỨ

ng - Thu c tính – Giá tr ị

ộ

ố ượ

ạ

2.3.1. B ba: Đ i t ộ 2.3.2. Các lu t d n ậ ẫ 2.3.3. M ng ng nghĩa ữ 2.3.4. Frames 2.3.5. Logic

19

ng-Thu c tính–Giá

ố ượ

ộ

2.3.1. B ba Đ i t ộ trị

 M t s ki n có th đ

ể

ể ượ

ộ ự ệ

ị

ố ượ

ủ

ộ

ộ ả

ị ủ ệ ộ

ụ ị ự ệ

ượ

ể

ả

ố ượ

ộ

ọ

ị

c dùng đ xác nh n giá tr c a m t ộ ậ thu c tính xác đ nh c a m t vài đ i t ng. Ví d , m nh đ ề “qu bóng màu đ ” xác nh n “đ ” là giá tr thu c tính ỏ ậ ỏ “màu” c a đ i t c ng “qu bóng”. Ki u s ki n này đ ố ượ ủ ng-Thu c tính–Giá tr (O-A-V – Object – g i là b ba Đ i t ộ Attribute - Value)

Màu

Chó

Nâu

Đ i t

ng Thu c tính Giá tr

ố ượ

ộ

ị

20

21

22

23

24

25

2.3.3. M ng ng nghĩa

ữ

ạ

 Là m t ph

ộ

ươ

ứ

ng và cung

ể ễ

ng pháp bi u di n tri th c dùng đ ồ ễ th trong đó nút bi u di n đ i t ố ượ bi u di n quan h gi a các đ i t

ng.

ể ệ ữ

ố ượ

ị ể

ễ

Cánh

CÓ

LÀ

Sẻ

Chim

DI CHUY NỂ

Bay

Hình 2.3. “S là Chim” th hi n trên m ng ng nghĩa ể ệ

ữ

ẻ

ạ

26

2.3.3. M ng ng nghĩa (ti p)

ữ

ế

ạ

Không khí

Cánh

CÓ

THỞ

Chim

Con v tậ

Chip

Sẻ

LÀ

LÀ

LÀ

DI CHUY NỂ

Cánh c tụ

Bay

DI CHUY NỂ

ĐI

27

Hình 2.4. Phát tri n m ng ng nghĩa

ữ

ể

ạ

2.3.4. Frame

ể ể ệ

ứ

ạ

ng nào đó

Frame là c u trúc d li u đ th hi n tri th c đa d ng ấ v khái ni m hay đ i t ệ ề

ữ ệ ố ượ

Hình 2.6. C u trúc Frame ấ

28

2.3.4. Frame (ti p)ế

Chim

Chim sẻ

V tị

Chim c nhả

S nhà

S đ ng ẻ ồ

ẻ

V t cị ỏ

V tẹ

Y ngể

quan h ph c t p h n

Hình 2.7. Nhi u m c c a Frame mô t ứ

ủ

ề

ả

ứ ạ

ệ

ơ

29

30

31

2.4.2. Các ho t đ ng c a H th ng Suy di n ti n

ạ ộ

ệ ố

ủ

ễ

ế

THÊM THÔNG TIN VÀO B NH LÀM VI C

Ộ Ớ

Ệ

XÉT LU T TI P THEO

Ậ

Ế

XÉT LU T Đ U TIÊN

Ậ

Ầ

Đúng

GI

CÒN LU T KHÁC Ậ

Ả Ế V I B NH

THI T KH P Ớ Ớ Ộ Ớ

Sai

Đúng

Sai

D NG CÔNG VI C

Ừ

Ệ

THÊM LU T VÀO B Ộ Ậ NH LÀM VI C

Ớ

Ệ

32

33

34

35

36

37

38

Ch

ươ

ng 3. H MYCIN ệ

Tr n Nguyên H ng

ươ

ầ

39

40

41

42

43

44

45

46

47

48

Hình 3.1. M ng suy di n ạ

ễ

C5

0.8

C4

C1

0.9

0.8

C3

C2

e1

0.9

0.5

0.7

0.6

e4

e2

e5

e3

49

50

51

52

Ch

ng 4. H H C

ươ

Ệ Ọ

Tr n Nguyên H ng

ươ

ầ

53

4.1. M đ u

ở ầ

 Các ch

ả

ng tr ươ ậ

ậ ườ

ề ể ễ ng h p này gi ợ ễ ể

ể

c đã th o lu n v bi u di n ướ và suy lu n tri th c. Trong tr ả ứ đ nh đã có s n tri th c và có th bi u di n ứ ẵ ị t ườ

ứ

 Tuy v y, trong nhi u tình hu ng s không có

ẽ

ố

ng minh tri th c. ề

ả

ậ s n tri th c: ứ ẵ – C n bi t các lu t mô t ậ ế ầ – Bài toán không đ

c bi u di n t

ng minh d

lĩnh v c c th ụ ể ự ườ ễ

ể

i ướ

ượ d ng các lu t s ki n ậ ự ệ

ạ

– ..

54

Conclusion Skin Colour Size Flesh

safe Hairy brown large Hard

4.1. M đ u

ở ầ

safe hairy green large Hard

i l c

 M t ng ộ

ườ ạ

dangerous smooth red large Soft

ầ

safe hairy green large Soft

safe hairy red small Hard

safe smooth red small Hard

ể ố ả ả ạ

safe smooth brown small Hard

c

dangerous hairy green small Soft

dangerous smooth green small Hard

trên hoang đ o. ả Đ s ng, c n ph i th xem lo i ạ ử c qu nào ăn đ ượ lo i nào đ c. ộ Sau nhi u l n ề ầ th , s l p đ ử ẽ ậ ượ b ng th ng kê ố ả sau

safe hairy red large Hard

safe smooth brown large Soft

dangerous smooth green small soft

Identifying what's good to eat?

safe hairy red small soft

dangerous smooth red large hard

safe smooth red small hard

dangerous hairy green small hard

4.2. Các hình th c h c

ứ ọ

ỉ ẫ

ng 7)

(ch

Xem giáo trình ươ

ươ

1. H c v t ẹ ọ 2. H c b ng cách ch d n ằ ọ 3. H c b ng quy n p ạ ằ ọ ng t 4. H c b ng t ự ằ ọ 5. H c d a trên gi i thích ả ự ọ 6. H c d a trên tình hu ng ọ ố ự 7. H c không giám sát ọ

56

57

4.3. Bài toán

- Cho b ng nhi u c t, m i c t là m t d u hi u

ộ ấ

ỗ ộ

ệ

ộ

ả

ỉ

ậ ả

ợ

ề (thu c tính..), ộ ộ ộ ỗ ng

ườ

-> Cây quy t đ nh bi u di n tri th c t ễ các nút = l a ch n, r thành nhi u nhánh, tùy theo

- M t c t là k t lu n ch 2 kh năng “có” | “không”. ả ế - M i dòng c a b ng là m t tr ượ ừ c t ộ ườ ủ i chuyên gia, t ừ ể ẽ giá tr c a m t d u hi u ( thu c tính ..).

ọ ộ ấ

ệ

ng h p (có đ kinh nghi m quá kh ..). ứ ệ b ng này ứ ừ ả ề ộ ư ngơ án quy t đ nh: có | không. ế ị

ế ị ự ị ủ - Nút lá là m t phộ

58

Conclusion Skin Colour Size Flesh

Ví dụ

safe Hairy brown large Hard

safe hairy green large Hard

i l c

 M t ng ộ

ườ ạ

dangerous smooth red large Soft

ầ

safe hairy green large Soft

safe hairy red small Hard

safe smooth red small Hard

ể ố ả ả ạ

safe smooth brown small Hard

c

dangerous hairy green small Soft

dangerous smooth green small Hard

trên hoang đ o. ả Đ s ng, c n ph i th xem lo i ạ ử c qu nào ăn đ ượ lo i nào đ c. ộ Sau nhi u l n ề ầ th , s l p đ ử ẽ ậ ượ b ng th ng kê ố ả sau

safe hairy red large Hard

safe smooth brown large Soft

dangerous smooth green small soft

Identifying what's good to eat?

safe hairy red small soft

dangerous smooth red large hard

safe smooth red small hard

dangerous hairy green small hard

ụ ọ

ộ

ậ ạ

ộ

Ví dụ M i dòng trong b ng là m t ví d h c. ả ỗ B ng là t p ví d h c ụ ọ ậ ả M i dòng có th coi là m t lu t d ng ể ỗ

IF skin = hairy and colour = brown and size = large and flesh = hard THEN conclusion = safe

Ví dụ  Có th t o ra m t cây quy t đ nh đ thay th t p

ế ị

ế ậ

ể

ộ

ể ạ h p các lu t

ậ

 M t nút l a ch n c a cây quy t đ nh có d ng t ng

ợ ộ

ế ị

ủ

ự

ạ

ọ

ổ

ư

ị

ộ

ị

quát nh sau IF thu c tính = giá tr 1 then ộ else if thu c tính = giá tr 2 then else if ... ........... else if thu c tính = giá tr N then

ị

 Trên cây quy t đ nh, m

ng đi t

t đ ộ ườ

ừ ố

g c đ n nút lá ế

ộ ế ị ớ m tộ lu t. ậ

s ng v i ẽ ứ

4.4. T o cây quy t đ nh -

Thu t toán CLS

ế ị

ạ

ậ

ề

ấ ử ụ

ệ ố

ọ

ệ

 Do Hunt đ xu t s d ng trong h th ng h c khái ni m CLS – concept learning system, 1966.

 Là Thu t toán h c quy n p l n đ u tiên

ạ ầ

ầ

ậ

ọ

62

4.4. T o cây quy t đ nh -

Thu t toán CLS

ế ị

ạ

ậ

ỗ

: cây r ng. B xung thêm d n các nút cho t

c đúng t

ấ

ụ ọ 1- N u các ví d trong C đ u ụ

ề “đúng” thì t o nút lá “có” và ạ

ạ

ề “sai” thì t o nút lá “không”

Xu t phát ấ ầ ổ đ n khi cây quy t đ nh phân lo i đ ạ ượ ế ị ế c các ví d trong t p h c C. ả ậ ế k t thúc ế N u các ví d trong C đ u ụ ạ : i và k t thúc. Trái l 2- Ch n m t thu c tính A có các giá tr V ộ

ộ

ị

ạ

1,V2 ..Vm. T o nút

quy t đ nh m nhánh.

3- Chia t p ví d h c thành m t p con C

ậ

1,C2 .. Cm tùy theo

ọ

4- Quay l

ế ế ọ ế ị ậ ị ủ i t

ụ ọ giá tr c a thu c tính đã ch n ộ b ạ ừ ướ

c 1.

63

4.4. T o cây quy t đ nh -

Thu t toán CLS

ế ị

ạ

ậ

 Trong thu t toán CLS, vi c ch n thu c tính A

ệ

ậ

ọ

ộ

c 2 là ng u nhiên. ẫ

Quinland s c i ti n đ tăng hi u

ẽ ả ế

ệ đ phân

ộ

ọ

ộ

ể qu b ng cách ch n thu c tính có bi

b ở ướ  Thu t toán ậ ả ằ t cao nh t ệ

ấ .

64

Conclusion Skin Colour Size Flesh

safe Hairy brown large Hard

Minh ho ạ CLS

safe hairy green large Hard

dangerous smooth red large Soft

safe hairy green large Soft

safe hairy red small Hard

safe smooth red small Hard

safe smooth brown small Hard

dangerous hairy green small Soft

dangerous smooth green small Hard

safe hairy red large Hard

safe smooth brown large Soft

dangerous smooth green small soft

safe hairy red small soft

dangerous smooth red large hard

safe smooth red small hard

dangerous hairy green small hard

Minh ho ạ CLS

Skin=“Hairy”

Conclusion Skin Colour Size Flesh

safe Hairy brown Hard large

safe hairy green Hard large

safe hairy green large Soft

safe hairy red small Hard

dangerous hairy green small Soft

safe hairy red large Hard

safe hairy red small soft

hairy dangerous green small hard

Skin=“Smooth”

Minh ho ạ CLS

Conclusion Skin Colour Size Flesh

dangerous smooth red large Soft

safe smooth red small Hard

safe smooth brown small Hard

dangerous smooth green small Hard

safe smooth brown large Soft

dangerous smooth green small soft

dangerous smooth red large hard

safe smooth red small hard

Minh ho CLS

ạ

Skin=“Hairy” and Size = “large”

Conclusion Skin Colour Size Flesh

safe Hairy brown large Hard

safe hairy green large Hard

safe hairy green large Soft

R1: If Skin=“Hairy” and Size = “large” Then Safe

68

safe hairy red large Hard

Minh ho CLS

ạ

Skin=“Hairy” and Size = “Small”

Conclusion Skin Colour Size Flesh

safe hairy red small Hard

dangerous hairy green small Soft

safe hairy red small soft

R2: If Skin=“Hairy” and Size = “Small” and Colour=“Green” then Dangerous R3: If Skin=“Hairy” and Size = “Small” and Colour=“Red” then Safe

69

dangerous hairy green small hard

Skin=“Smooth” and Size = “Small”

Conclusion Skin Colour Size Flesh

smooth red small Hard safe

smooth brown small Hard safe

dangerous smooth green small Hard

70

R4: If Skin=“Smooth” and Size = “Small” and Colour=“Green” then Dangerous R5: If Skin=“Smooth” and Size = “Small” and Colour=“Red” then Safe R6: If Skin=“Smooth” and Size = “Small” and Colour=“Brown” then Safe

smooth red small hard safe

Skin=“Smooth” and Size = “Large”

Conclusion Skin Colour Size Flesh

dangerous smooth red large Soft

safe smooth brown large Soft

R7: If Skin=“Smooth” and Size = “Large” and Colour=“Red” then Dangerous R8: If Skin=“Smooth” and Size = “Small” and Colour=“Brown” then Safe

71

large dangerous smooth red hard

ế ị

Cây quy t đ nh Skin

Hairy

Smooth

Size

Size

Small

Large

Large

Small

Color

Green

Color

Safe

Color

Brown

Dangerous

Green

Red

Red

Red

Safe

Brown

Safe

Dangerous

Dangerous

Safe

Safe

4.5. Entropy và m c đ phân ứ t c a m t thu c tính

bi

ệ ủ

ộ ộ

ộ

t c a m t thu c tính

ế

ệ ủ

ộ

 Th nào là đ phân bi ộ  Lí thuy t thông tin cho phép l

? ộ ng hóa thông ượ

ế

 M t cách t ng quát, gi ổ

tin. ộ ậ

ộ

s k t lu n C có th ể ậ ả ử ế nh n m t trong n giá tr c1, c2, .. cn. Trong ví ị d trên, C nh n 2 giá tr “ăn đ ị ậ

c”, “đ c”. ộ

ượ

ụ

73

phân bi

4.5. Entropy và m c đ ộ ứ (ti p)ế t c a m t thu c tính ộ

ệ ủ

ộ

 Gi

s thu c tính A có th nh n m giá tr a1, ể

ậ

ị

ả ử

 Kí hi u xác su t đi u ki n P(C= ci | A = aj)

ề

ệ

ấ

ộ a2, … am. ệ ọ

hay g n h n P(ci | aj). ơ

 Ví d P(C= safe | Skin = hairy) = 6/8 = ¾,

ụ

ớ

(8 dòng v i Skin=hairy, (trong đó 6 dòng k t lu n C = safe. ậ

ế

74

4.5. Entropy và m c đ ộ

phân bi

t c a m t thu c tính

ệ ủ

ộ

ộ

ứ (ti p)ế

Entropy(C) = - ∑ P(C = ci) log2 P(C = ci)

i=1, 2. ,,, n

75

4.5. Entropy và m c đ ộ

phân bi

t c a m t thu c tính

ệ ủ

ộ

ộ

ứ (ti p)ế

 Entropy c a thông tin A= a

ủ

ố ớ ế

ậ

Bi u th c

ng tin mà A = a

i cho

ượ

j đ i v i k t lu n C ạ

j mang l

ứ - log2 P(ci | aj) là l ể i. k t lu n C = c ậ ế

T ng theo i = 1 … n là entropy c a thông tin A= a

ổ

j đ i v i ố ớ

k t lu n C: ậ ế

ủ Entropy(aj) = - ∑ P(ci | aj ) log2 P(ci | aj)

Entropy c a thu c tính A đ i v i C đ

c đ nh nghĩa là t ng

ố ớ

ủ

ộ

ượ

ổ

ị

Entropy (A) = - ∑ P(A = aj) * Entropy(aj) = - ∑ P(A =aj) ∑ P(ci | aj ) log2 P(ci | aj)

76

4.5. Entropy và m c đ ộ

phân bi

t c a m t thu c tính

ệ ủ

ộ

ộ

ứ (ti p)ế

 Entropy là m t s bi n thiên trong đo n [0,1].

ạ

ứ

ẫ

ờ

ậ

ộ ố ế Entropy là đ đo m c nghi ng , m c ng u nhiên ứ ộ c a k t lu n. ế ủ – Nó càng cao thì nghi ng v k t lu n C càng

ờ ề ế

ậ

l n. ớ

– Entropy càng th p thì a

ề

j càng mang nhi u thông

ậ

ề ế

t c các ví d thu c cùng ụ

ộ

ấ tin v k t lu n C. – Entropy = 0 nghĩa là t ộ ế

ấ ả ậ

ớ

1 l p, có cùng m t k t lu n.

77

– Entropy = 1 nghĩa là hoàn toàn ng u nhiên

ẫ

4.5. Entropy và m c đ ộ

phân bi

t c a m t thu c tính

ệ ủ

ộ

ộ

ứ (ti p)ế

Size trong ví d trên. T b ng d ụ

ừ ả

ữ

Ví dụ Xét thu c tính ộ li u ta có ệ – P(safe | large ) = 5/7 – P(dangerous | large ) = 2/7 – P(large ) = 7/16 – P(safe | small ) = 5/9 – P(dangerous | small ) = 4/9 – P(small ) = 9/16

78

4.5. Entropy và m c đ ộ

phân bi

t c a m t thu c tính

ệ ủ

ộ

ộ

ứ (ti p)ế

 Nh v y entropy c a thu c tính

Size đ i v i k t

ủ

ố ớ ế

ộ lu n “safe | dangerous” là

ư ậ ậ

7/16* {5/7 *log2 5/7 + 2/7 * log2 2/7} +

9/16* {5/9 *log2 5/9 + 4/9* log2 4/9} = 0.9350955

79

4.5. Entropy và m c đ ộ

phân bi

t c a m t thu c tính

ệ ủ

ộ

ộ

ứ (ti p)ế

ượ

i ạ

 Đ nh nghĩa l ị ố ớ ậ

ở

ấ

ng tin mà thu c tính A mang l ộ đ i v i t p ví d ụ Gain(C, A) = Entropy(C) – Entropy (A) đây: Thu c tính có entropy th p nh t chính là có đ ộ ộ t cao nh t (cho k t lu n C). phân bi

ấ ậ

ế

ệ

ấ

80

4.6. Thu t gi

i Quinlan

ậ

ả

 Là thu t toán h c theo quy n p dùng lu t, đa

ạ

ậ

ọ

ậ m c tiêu

ụ

 Do Quinlan đ a ra năm 1979. C i ti n thu t

ả ế

ư

ậ

toán CLS.

 Còn g i là thu t toán ID3 (ID là vi ậ

ọ

t c a t t ế ắ ủ ‘iterative dichotomiser = chia đôi nhi u l n) ề ầ

 Ý t

ng:

ưở

– 1- CLS làm vi c v i toàn b t p thí d h c có s n

ộ ậ

ụ ọ

ẵ ng thí d h c, dùng m t

ớ ố ượ

ụ ọ

ộ

ệ ả

đ u. ID3 gi m s l ấ

ọ

t ừ ầ t p con xu t phát. ậ – 2- m i b ộ ở ỗ ướ t cao nh t đ phân nhánh. bi ệ

c ID3 ch n thu c tính có m c phân ấ ể

ứ

81

4.6. Thu t gi

i Quinlan

ậ

ả

c c a thu t toán ID3 ậ

 Các b ướ ủ ọ

W c a t p ủ ậ

ẫ ụ ọ

ộ ậ ử

ọ

2. Áp d ng thu t toán CLS t o cây (hay lu t)

1. Ch n ng u nhiên m t t p con các ví d h c, g i là c a s ổ ạ ậ

ậ

quy t đ nh cho W

i (tr W) trên

ụ ế ị ệ

ụ

ừ

3. Duy t toàn b các ví d còn l ạ ộ cây đ phát hi n các ngo i l ạ ệ ệ

ể

ạ ệ ạ

, thêm vào W và i, k t thúc cho k t ế

ế

4. N u có ví d là ngo i l ụ ế c 2. Trái l l p l b i t ặ ạ ừ ướ c qu là cây nh n đ ậ ả

ượ

82

4.6. Thu t gi

i Quinlan

ậ

ả

c 2

t b ế ướ

t c các thu c tính

(đ i v i k t lu n

ủ ấ ả

ộ

ố ớ ế

ậ

Chi ti 1. Tính entropy c a t c n quy t đ nh); ầ

ế ị ộ

ọ

ấ

tùy theo giá tr c a

2. Ch n thu c tính (ví d A) có entropy th p nh t ấ ụ 3. Chia t p ví d thành các t p con ụ

ị ủ

ậ

ậ

thu c tính A. A nh n cùng m t giá tr trên m i t p con.

ậ

ộ

ộ

ỗ ậ :

ị ị ủ

ự

b

ừ

4. Xây d ng cây phân nhánh theo giá tr c a A if A=a1 then ... (subtree1) if A=a2 then ... (subtree2) ...etc... i t 5. L p l ặ ạ ừ ướ 6. M i l n l p xét đ ỗ ầ ặ ế

ầ

ặ

83

ụ

ế

ọ

. c 1 v i m i cây con ỗ ớ Quá trình d ng khi c 1 thu c tính. ượ ộ đã xét h t các thu c tính, ho c không c n phân nhánh ộ n aữ (vì m i ví d trong m t cây con đã có cùng k t ộ lu n. ậ

i Quinlan

Minh ho Thu t gi ạ

ậ

ả

ụ

ư

ả

ồ

ướ

i. C t ộ

– T p C g m 14 ví d nh trong b ng d ậ k t lu n là có ch i bóng hay không. ơ ế

ậ

– Các thu c tính: outlook, temperature, humidity,

ộ

ị

t đ )= {hot, mild, cool }

wind speed. – Các giá tr có th : ể t) = { sunny, overcast – u ám , rain }  Outlook (th i ti ờ ế  temperature (nhi ệ ộ  Humidity (đ m) = { high, normal } ộ ẩ  Wind (gió) = {weak, strong }

84

Day

Outlook

Temperature

Humidity Wind

Play ball

D1

Sunny

Hot

High

Weak

No

D2

Sunny

Hot

High

Strong

No

D3

Overcast

Hot

High

Weak

Yes

D4

Rain

Mild

High

Weak

Yes

D5

Rain

Cool

Normal

Weak

Yes

D6

Rain

Cool

Normal

Strong

No

D7

Overcast

Cool

Normal

Strong

Yes

D8

Sunny

Mild

High

Weak

No

D9

Sunny

Cool

Normal

Weak

Yes

D10

Rain

Mild

Normal

Weak

Yes

D11

Sunny

Mild

Normal

Strong

Yes

D12

Overcast

Mild

High

Strong

Yes

D13

Overcast

Hot

Normal

Weak

Yes

D14

Rain

Mild

High

Strong

No

i Quinlan

Minh ho Thu t gi ạ

ậ

ả

t c các thu c tính

ố ộ

 Xác đ nh thu c tính làm nút g c cây. ộ ị  Tính Gain c a t ủ ấ ả  Ví d Gain(C, Wind) = ?

ụ

Gain(C,Wind) = Entropy(C)-(8/14)*Entropy(weak)

- (6/14)*Entropy(strong) Entropy(weak) = - (6/8)*log2(6/8) - (2/8)*log2(2/8) = 0.811 Entropy(Strong) = - (3/6)*log2(3/6) - (3/6)*log2(3/6) = 1.00 V y: ậ

Gain(C,Wind) = 0.940 - (8/14)*0.811 - (6/14)*1.00

= 0.048

86

i Quinlan

Minh ho Thu t gi ạ

ậ

ả

K t qu :

ả

ấ

c dùng làm nút g c.

đ

ế Gain(C, Outlook) = 0.246 Gain(C, Temperature) = 0.029 Gain(C, Humidity) = 0.151 Gain(C, Wind) = 0.048 Thu c tính Outlook có Gain cao nh t. Do đó, nó ố

ộ ượ

87

i Quinlan

Minh ho Thu t gi ạ

ậ

ả

sunny,

Outlook có 3 giá tr , c n phân 3 nhánh ị ầ

overcast, rain.

88

i Quinlan

Minh ho Thu t gi ạ

ậ

ả

ế ụ

ỉ

ộ

 Ti p t c phân nhánh. Xét nút Sunny. Ch còn các thu c tính Humidity, Temperature, Wind. ng h p ợ

ườ

 Csunny = {D1, D2, D8, D9, D11} = 5 tr

v i outlook = sunny ớ – Gain(Csunny, Humidity) = 0.970 – Gain(Csunny, Temperature) = 0.570 – Gain(Csunny, Wind) = 0.019

89

i Quinlan

Minh ho Thu t gi ạ

ậ

ả

ộ

ấ

 Thu c tính Humidity có Gain cao nh t. L y nó ấ i làm nút phân nhánh ti p theo. Quá trình l p l ặ ạ ế

90

i Quinlan

Minh ho Thu t gi ạ

ậ

ả

Cây quy t đ nh th hi n các lu t, là tri th c rút ra t

ừ

ậ

ứ

ể ệ

ả

1.

2.

3.

4.

5.

91

ế ị b ng trên. IF outlook = sunny AND humidity = high THEN playball = no IF outlook = rain AND humidity = high THEN playball = no IF outlook = rain AND wind = strong THEN playball = yes IF outlook = overcast THEN playball = yes IF outlook = rain AND wind = weak THEN playball = yes

u đi m c a gi

i thu t Quinlan

Ư

ủ

ể

ả

ậ

ổ

ơ

ọ

1. Dùng c a s hay ph ử ụ ầ

áp l c các ngo i ư ng ph ạ . Gi m s ví d c n x lí, t p trung vào các ậ ử

ố

l ả ệ tụ ố ví d t

2. Ch n ọ thu c tính có đ phân bi

ệ

ấ

ộ

ở ộ c, là m t heuristic cho phép tăng hi u

t cao nh t ệ

m i b qu c a h th ng.

ỗ ướ ả ủ

ộ ệ ố

92

c đi m c a gi

i thu t

ủ

ể

ả

ậ

Nh ượ Quinlan

1. Thu t toán không bi

ậ

ế

ộ

t phát hi n thu c ệ ế

ế

ụ ế

ậ ả ộ

ề

ử

ẫ

ầ

ng quan gi a vi c “ăn qu vào ngày th ứ

ữ

ả

c” /

ượ

ầ

ậ

tính không liên quan đ n k t lu n. - Ví d n u trong b ng trên có c c t ch a ứ ả thông tin v “ăn qu vào ngày th m y ả ứ ấ trong tu n” thì thu t toán v n x lí m i ố ậ t ươ ệ m y trong tu n” và k t lu n “ăn đ ấ “đ c” m t cách gi ộ ộ

ế t o. ả ạ

93

c đi m c a gi

i thu t

ủ

ể

ả

ậ

Nh ượ Quinlan

Outcom e X Y

ộ

ậ ộ

ỗ ầ ộ

ớ ặ

ẫ

2. Thu t toán ch xét m i l n m t ỉ thu c tính. N u có 2 thu c tính ế có entropy trùng kh p nhau thì nó v n xét riêng m c dù đúng ra nên xem xét chúng cùng v i ớ nhau.

ệ

ả

Thu t toán ID3 s không th phát ể ẽ ậ hi n ra lu t đ n gi n là : ậ ơ if X = Y then outcome = yes else outcome = no

yes 3 3 no 2 1 yes 4 4 no 2 4 no 1 3 yes 1 1 yes 2 2 no 2 3

94

c đi m c a gi

i thu t

ủ

ể

ả

ậ

Nh ượ Quinlan

m t t p ví d v i nhi u

3. Khi quy n p rút ra lu t t ạ

ậ ừ ộ ậ

ụ ớ ứ

ế

ớ

ững

ả ả

ạ

ớ

ề kh năng k t lu n khác nhau (n l n ch không ph i là 2) thì thu t toán quá nh y c m v i nh thay đ i t m th ổ ầ

ả ng trong t p ví d . ụ ậ

ậ ậ ườ

ử

ậ

ắ

ắ

ụ.

ự

4. Thu t toán không x lí các lu t không ch c ch n, ắ ắ cũng ch nh m t thí d ng t ỉ c các thí d mâu thu n nhau

ậ ữ ệ 5. Nhi u thí d t ề 6. Không x lí đ

d li u không ch c ch n. ụ ươ ượ

ư ộ ẫ

ử

ụ

95

Conclusion Skin Colour Size Flesh

Bài t p 1ậ

safe Hairy brown large Hard

i l c

 M t ng ộ

ườ ạ

safe hairy green large Hard

dangerous smooth red large Soft

ầ

safe hairy green large Soft

safe hairy red small Hard

ể ố ả ả ạ

safe smooth red small Hard

safe smooth brown small Hard

c

dangerous hairy green small Soft

trên hoang đ o. ả Đ s ng, c n ph i th xem lo i ạ ử c qu nào ăn đ ượ lo i nào đ c. ộ Sau nhi u l n ề ầ th , s l p đ ử ẽ ậ ượ b ng th ng kê ố ả sau

dangerous smooth green small Hard

safe hairy red large Hard

safe smooth brown large Soft

dangerous smooth green small soft

safe hairy red small soft

Xây d ng các ự t p lu t dùng ậ ậ thu t toán ậ Quinlan

dangerous smooth red large hard

safe smooth red small hard

dangerous hairy green small hard

ậ

ậ ể

Bài t p 2. Xây d ng t p lu t đ suy di n ra ễ ậ Conclusion s d ng thu t toán Quinlan

ự ử ụ

ậ

Bài t p 2. K t qu

ế

ậ

ả

ậ

ễ

ậ

ậ

Bài t p 3. Xây d ng t p lu t suy di n ra ự Profit s d ng thu t toán Quinlan

ử ụ

ậ

K t quế

ả

100

ả

i ILA 4.7. Thu t gi ậ (Inductive Learning Algorithm)

101

4.7. Thu t gi

i ILA

ậ

ả

102

4.7. Thu t gi

i ILA

ậ

ả

103

4.7. Thu t gi

i ILA

ậ

ả

104

105

106

107

108

109

110

111

ế

ậ

ậ

Bài t p: ậ Xây d ng t p lu t cho k t lu n ậ s d ng thu t toán ILA ậ

ự ử ụ

(B ng 7.1. trang 129 giáo trình)

ả

112

STT

Màu tóc

Dùng

Chi u cao ề

Cân n ngặ

K t quế

ả

Tên ng

iườ

thu cố

Hoa

Đen

Không

1

Nhẹ

B rámị

T m ầ th

cướ

2

Lan

Đen

Cao

Có

Không

V a ph i ả

ừ

3

Xuân

Râm

Có

Không

Th pấ

V a ph i ả

ừ

4

Đen

Không

Hạ

Th pấ

V a ph i ả

ừ

B rámị

5

Thu

Không

B cạ

N ngặ

B rámị

T m ầ th

cướ

6

Đông

Râm

Cao

Không

Không

N ngặ

7

Râm

Không

Không

Mơ

N ngặ

T m ầ th

cướ

8

Đào

Đen

Có

Không

Th pấ

Nhẹ

ươ

ng 5. H TH NG M Ch Ờ Ệ Ố CHO CÁC BI N LIÊN T C Ế

Ụ

Tr n Nguyên H ng

ươ

ầ

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142