Bài giảng Hệ cơ sở tri thức (Tuần 13-15)

23/11/2015

Tuần 13-15 (Week 13-15) Email: haivnu@yahoo.com

(cid:1)

(cid:1) Mục đích: Kết hợp cơ sở tri thức (CSTT) với cơ sở dữ liệu (CSDL) nhằm suy diễn thông tin từ CSDL bằng các luật suy diễn trong CSTT và các dữ liệu trong CSDL. Cách suy diễn thông tin từ các luật có trong CSTT và dữ liệu trong CSDL, cách quản trị CSTT.

1 Hai V Pham hai@spice.ci.ritsumei.ac.jp

2 23 November 2015

Rules:::: RRRR1111,,,, RRRR2222,,,,…………RRRR3333 Rules Rules Rules THENTHENTHENTHEN RiRiRiRi :::: IFIFIFIF mother(XXXX,YYYY) father(XXXX,YYYY) | mother parent parent(XXXX,YYYY): - father mother mother father father parent parent parent là các vị từ XXXX,YYYY Với father mother, parent father, mother father parent parent mother mother father là các biến.

Mỗi vị từ pppp(XXXX,YYYY,ZZZZ) ứng với một quan hệ

PPPP(XXXX,YYYY,ZZZZ) trong CSDL

3 23 November 2015

1

23/11/2015

LuLuLuLuậttttkhôngkhôngkhôngkhôngđđđđệ quiquiquiqui: Vị từ ở phần đầu không xuất hiện trong phần thân của luật.

VDVDVDVD: : : : sibling mother(ZZZZ,YYYY) parent(ZZZZ,XXXX) & mother sibling(XXXX,YYYY):- parent mother mother parent parent sibling sibling LuLuLuLuậtttt đđđđệ quiquiquiqui: Vị từ ở phần đầu xuất hiện trong phần thân của luật. VíVíVíVí ddddụ 3333::::ancestor parent(XXXX,YYYY). ancestor(XXXX,YYYY): - parent parent parent ancestor ancestor ancestor(ZZZZ,YYYY) parent(XXXX,ZZZZ) & ancestor ancestor(XXXX,YYYY): - parent ancestor ancestor ancestor parent parent ancestor ancestor

(cid:1)

(cid:1)

(cid:1)

AND(&) được xây dựng trên cơ sở Phép AND(&) AND(&) AND(&) phép kết và phép chiếu của đại số quan hệ. Với luật tttt(aaaa,bbbb,dddd,eeee): rrrr(aaaa,bbbb,cccc) & ssss(cccc,dddd,eeee), quan hệ trong TTTT(aaaa,bbbb,dddd,eeee) ứng với vị từ tttt(aaaa,bbbb,dddd,eeee) được tính theo cách sau: Nếu dùng câu SQL, ta có câu lệnh tương ứng: SELECT SELECT rrrr.aaaa, rrrr.bbbb, ssss.dddd, ssss.eeee SELECT SELECT FROMFROMFROMFROM table rrrr, table ssss WHERE rrrr.cccc = ssss.cccc. WHERE WHERE WHERE

4 23 November 2015

(cid:1)

Phép toán OROROROR (|)(|)(|)(|) được xây dựng trên cơ sở phép hợp sau đây: s(a,b,c) r(a,b,c) |||| s(a,b,c) t(a,b,c):::: ---- r(a,b,c) t(a,b,c) s(a,b,c) s(a,b,c) r(a,b,c) r(a,b,c) t(a,b,c) t(a,b,c)

(cid:1)

(cid:1)

Quan hệ TTTT(aaaa,bbbb,cccc) trong tttt(aaaa,bbbb,cccc) được tính theo cách sau: R(a,b,c) ∪∪∪∪ S(a,b,c) S(a,b,c) T(a,b,c) ==== R(a,b,c) T(a,b,c) S(a,b,c) S(a,b,c) R(a,b,c) R(a,b,c) T(a,b,c) T(a,b,c) Nếu dùng SQL, ta có câu lệnh tương ứng : SELECT * FROMFROMFROMFROM table1 rrrr SELECT SELECT SELECT SELECT * FROMFROMFROMFROM table2 rrrr INTOINTOINTOINTO table tttt UNION SELECT UNION SELECT SELECT UNION UNION

5 23 November 2015

6 23 November 2015

2

23/11/2015

(cid:1)

(cid:1)

(cid:1)

Phép not(not(not(not(∼∼∼∼ )))) được xây dựng trên cơ sở phép hiệu, ví dụ: r(a,b,c) &&&& ((((∼∼∼∼ s(a,b,c)) t(a,b,c) s(a,b,c)) t(a,b,c):::: ---- r(a,b,c) s(a,b,c)) s(a,b,c)) r(a,b,c) r(a,b,c) t(a,b,c) t(a,b,c) Quan hệ được suy TTTT(aaaa,bbbb,cccc) của vị từ tttt(aaaa,bbbb,cccc) được tính theo cách sau: t(a,b,c) s(a,b,c) r(a,b,c) \\\\ s(a,b,c) t(a,b,c) ==== r(a,b,c) s(a,b,c) s(a,b,c) r(a,b,c) r(a,b,c) t(a,b,c) t(a,b,c) Nếu dùng SQL, ta có thể cài đặt như sau: SELECT aaaa, bbbb, eeee SELECT SELECT SELECT FROMFROMFROMFROM table rrrr SELECT aaaa FROMFROMFROMFROM ssss) WHERE aaaa NOTNOTNOTNOT ININININ (SELECT WHERE SELECT SELECT WHERE WHERE

(cid:1)

7 23 November 2015

Có thể mô tả các luật suy diễn bằng đồ thị suy diễn. Ví dụ với hai luật trên ta có thể tạo đồ thị dạng cây suy diễn ở hình sau:

(cid:1)

8 23 November 2015

Trong tiến trình suy diễn để tạo quan hệ cho vị từ được suy grandfather grandfather(XXXX,YYYY) grandfather grandfather chúng ta cần tạo các quan hệ cho các vị từ father parent(ZZZZ,YYYY). father(XXXX,ZZZZ) và parent parent parent father father

9 23 November 2015

3

23/11/2015

father(XXXX,ZZZZ) là quan hệ nền nên chỉ (cid:1) Do father father father cần thẩm định parent parent(ZZZZ,YYYY) bằng cách parent parent so khớp và đồng nhất biến để có dạng sau: mother(Z,Y) father(Z,Y) |||| mother(Z,Y) parent(Z,Y)::::---- father(Z,Y) parent(Z,Y) mother(Z,Y) mother(Z,Y) father(Z,Y) father(Z,Y) parent(Z,Y) parent(Z,Y)

(cid:1)

10 23 November 2015

father(ZZZZ,YYYY) chúng ta sử Với vị từ nền father father father dụng so khớp và đồng nhất biến theo thứ tự xuất hiện của đối trong vị từ và thứ tự xuất hiện trường trong quan hệ nền.

(cid:1)

11 23 November 2015

Từ quan hệ father father(F,CF,CF,CF,C), chúng ta có father father các đồng nhất biến sau cho father father(XXXX,ZZZZ) father father father(ZZZZ,YYYY). và father father father

FATHER(FFFF CCCC) FATHER FATHER FATHER

father(XXXX ZZZZ) father father father

father(ZZZZ father father father

YYYY)

nam son

nam son

nam son

loc vinh

loc vinh

loc

vinh

12 23 November 2015

4

23/11/2015

Có hai bước chính là: (cid:1)

Tạo cây suy diễn theo các luật. (cid:1) Duyệt cây để thẩm định và tạo sinh

(cid:1)

dữ liệu cho vị từ được suy. Với hai luật: parent(ZZZZ,YYYY) & parent(XXXX,ZZZZ) & parent sibling(XXXX,YYYY):- parent rrrr1: sibling sibling parent parent parent parent sibling (XXXX<>YYYY)

mother(XXXX,YYYY) father(XXXX,YYYY) | mother parent(XXXX,YYYY):- father rrrr2: parent mother mother father father parent parent

(cid:1)

(cid:1)

(cid:1)

sibling(XXXX,YYYY) với các đích Vị từ được suy sibling sibling sibling sibling(AAAA,BBBB) sẽ được thẩm định như sau: sibling sibling sibling Tìm luật so khớp được với đích và thực hiện đồng nhất biến. Tạo cây con có gốc chính là đích của bài toán. Xử lý đệ qui với các đích con là các lá của cây con vừa mới tạo được. Nếu vị từ trong lá là vị từ nền thì không thể mở rộng được cây con.

13 23 November 2015

14 23 November 2015

15 23 November 2015

5

23/11/2015

(cid:1)

Sau khi đã tạo xong cây suy diễn, chúng ta bước sang suy diễn bằng cách duyệt cây để tạo sinh dữ liệu cho các vị từ được suy. Ý tưởng của thuật toán như sau:

(cid:2)

(cid:2)

(cid:2)

Tìm luật có phần đầu so khớp được với đích. Tạo dữ liệu cho các vị từ trong phần thân của luật. Thực hiện các phép toán logic của cơ sở dữ liệu suy diễn để tạo dữ liệu cho vị từ được suy.

16 23 November 2015

Xét một CSDL theo dõi kết quả học tập của sinh viên với các quan hệ nền sau. Nganhhoc(manganh,tennganh): chứa các ngành học của trường. Nganhhoc Nganhhoc Nganhhoc Sinhvien(masv,manganh,holot,ten): chứa hồ sơ sinh viên. Sinhvien Sinhvien Sinhvien Moncoso(manganh,mamon,tenmon,sotc): các môn cơ sở của từng Moncoso Moncoso Moncoso ngành học và số tín chỉ của môn. Chuan(manganh,mamon,dchuan): điểm chuẩn của môn cơ sở chính Chuan Chuan Chuan của ngành dùng để suy diễn. Diemcoso(masv,mamon,dmon): điểm kết quả môn của sinh viên. Diemcoso Diemcoso Diemcoso Chuyennganh(manganh,machnganh):các chuyên ngành của từng Chuyennganh Chuyennganh Chuyennganh ngành. Chuyende(machnganh,machde,tenchde,sotc): các chuyên đề của Chuyende Chuyende Chuyende ngành. Diemchde(masv,machde,dchde): điểm kết quả chuyên đề của sinh Diemchde Diemchde Diemchde viên

17 23 November 2015

18 23 November 2015

6

23/11/2015

mamon,

Phần CSTT bao gồm các luật suy diễn dữ liệu sau: CácCácCácCác lulululuậtttt suysuysuysuy didididiễnnnn 1111:::: SinhSinhSinhSinh viênviênviênviên gigigigiỏiiii ở giaigiaigiaigiai đođođođoạnnnn cơcơcơcơ ssssở diemcoso(masv,mamon,dmon) rrrr1111:::: IFIFIFIF diemcoso diemcoso diemcoso chuan(manganh, chuan ANDANDANDAND chuan chuan

dmon,dchuan)

THENTHENTHENTHEN

diemchinh diemchinh(masv,manganh,mamon,dmon,dchuan) diemchinh diemchinh Tạo quan hệ diemchinh(masv,manganh,mamon,dmon,dchuan) diemchinh diemchinh diemchinh chứa điểm môn quan trọng của ngành ở giai đọan của sinh viên và điểm chuẩn để suy diễn của môn đó.

19 23 November 2015

r2r2r2r2: : : : IFIFIFIF dchinh dchinh(masv,manganh, mamon, dchinh dchinh dmon,dchuan)

ANDANDANDAND (dmon> dchuan) svgioicoso (masv,manganh) THENTHENTHENTHEN svgioicoso svgioicoso svgioicoso

Tạo quan hệ svgioicoso svgioicoso(masv,manganh) svgioicoso svgioicoso chứa các sinh viên được đánh giá là giỏi ở giai đoạn cơ sơ theo quan điểm nếu điểm môn quan trọng của sinh viên lớn hơn điểm chuẩn.

(cid:1)

n 2: Sinh viên giỏi i i i ở giai giai giai giai t suy diễn 2: Sinh viên gi Các luật suy di Các lu t suy di n 2: Sinh viên gi n 2: Sinh viên gi t suy di Các lu Các lu đođođođoạn chuyên ngành n chuyên ngành n chuyên ngành n chuyên ngành r3r3r3r3:IFIFIFIF chuyende chuyende(machnganh,machde,tenchde,sotchi) chuyende chuyende

ANDANDANDAND (sotchi>5) chdeqtrong(machnganh, machde) THENTHENTHENTHEN chdeqtrong chdeqtrong chdeqtrong

(cid:1)

Tạo quan hệ chdeqtrong(machnganh,machde) chứa các chdeqtrong chdeqtrong chdeqtrong chuyên đề quan trọng theo nghĩa có số tín chỉ lớn hơn 5.

20 23 November 2015

21 23 November 2015

7

23/11/2015

diemde(masv,machde,dchde) rrrr4444:::: IFIFIFIF diemde(masv,machde,dchde) diemde(masv,machde,dchde) diemde(masv,machde,dchde)

(cid:1)

ANDANDANDAND (dchde> (dchde>8888)))) (dchde> (dchde> machde) svgioicde(masv, machde) THENTHENTHENTHEN svgioicde(masv, machde) machde) svgioicde(masv, svgioicde(masv, Tạo quan hệ svgioicde svgioicde(masv,machde) svgioicde svgioicde chứa các chuyên đề mà sinh viên đạt kết quả tốt.

22 23 November 2015

IFsvgioicde(masv,machde) rrrr5555:::: IFsvgioicde(masv,machde) IFsvgioicde(masv,machde) IFsvgioicde(masv,machde)

(cid:1)

ANDANDANDAND chdeqtrong(machnganh,machde) chdeqtrong(machnganh,machde) chdeqtrong(machnganh,machde) chdeqtrong(machnganh,machde) svgioichng(masv, machnganh) THENTHENTHENTHEN svgioichng(masv, machnganh) machnganh) machnganh) svgioichng(masv, svgioichng(masv, Tạo quan hệ svgioichng svgioichng(masv, svgioichng svgioichng machnganh) chứa các sinh viên được đánh giá là giỏi chuyên ngành được xác định bởi machnganh. Ở đây có thể dùng độ đo niềm tin vào để đánh giá.

(cid:1)

(cid:1)

Các luật suy diễn 3: Sinh viên sẽ làm sẽ làm nghiên cứu sinh theo chuyên ngành nào sau khi tốt nghiệp r6:r6:r6:r6: IF svgioicoso(masv,manganh) IF svgioicoso(masv,manganh) IF svgioicoso(masv,manganh) IF svgioicoso(masv,manganh) AND svgioichng(masv, machnganh) AND svgioichng(masv, machnganh) AND svgioichng(masv, machnganh) AND svgioichng(masv, machnganh) THEN svtheochnganh(masv,machnganh) THEN svtheochnganh(masv,machnganh) THEN svtheochnganh(masv,machnganh) THEN svtheochnganh(masv,machnganh) Tạo quan hệ svtheochnganh(masv,machnganh) suy luận svtheochnganh svtheochnganh svtheochnganh về chuyên ngành sinh viên sẽ làm nghiên cứu sinh. Luật này có độ đo chính xác của luật.

23 23 November 2015

24 23 November 2015

8

23/11/2015

a) Bảng 1: EvidenceTable EvidenceTable(RuleNo,Term) EvidenceTable EvidenceTable Thuộc tính TermTermTermTerm của bảng này chứa dạng Postfix của phần giả thuyết của luật suy Postfix Postfix Postfix diễn dữ liệu. Với dạng lưu trữ của luật

r1: IF ( NOT a) AND ( NOT b ) THEN sẽ là a ~ b ~ &

25 23 November 2015

Evidence, Evidence, Evidence, Evidence,

BBBBảngngngng 2222:::: RuleTable(Ruleno, RuleTable(Ruleno, RuleTable(Ruleno, RuleTable(Ruleno,

b)b)b)b) Conclusion,Cfrule) Conclusion,Cfrule) Conclusion,Cfrule) Conclusion,Cfrule) Chứa luật suy diễn dữ liệu. Cfrule là độ tin cây của luật c)c)c)c) BBBBảngngngng 3333:::: NodeTable(NodeNo,NodeType, NodeTable(NodeNo,NodeType, NodeTable(NodeNo,NodeType, NodeTable(NodeNo,NodeType, NodeDescription, Cfnode) NodeDescription, Cfnode) Cfnode) Cfnode) NodeDescription, NodeDescription, Chứa thông tin của các node trên đồ thị suy diễn. Thuộc tính Nodetype có ba gía trị là 1 nếu là node lá, 2 nếu là nối mục tiêu trung gian và 3 nếu là mục tiêu cuối.

26 23 November 2015

chúng tatatata cócócócó ththththể (cid:1) HHHHệ ququququảnnnn trtrtrtrị CSTTCSTTCSTTCSTT này,này,này,này, chúng chúng chúng titititiếnnnn hànhhànhhànhhành sosososoạnnnn ththththảoooo cáccáccáccác lulululuậtttt suysuysuysuy didididiễnnnn ddddữ lilililiệuuuu....

(cid:1) HHHHệ ququququảnnnn trtrtrtrị CSTTCSTTCSTTCSTT baobaobaobao ggggồmmmm cáccáccáccác chchchchứcccc

thêm, xoá,xoá,xoá,xoá, ssssửaaaa lulululuậtttt.... năngnăngnăngnăng thêm, thêm, thêm,

27 23 November 2015

9

23/11/2015

a)a)a)a) HàmHàmHàmHàm ttttạoooo ddddữ lilililiệuuuu chochochocho cáccáccáccác bbbbảngngngng EvidenceTable EvidenceTable EvidenceTable EvidenceTable b)b)b)b) HàmHàmHàmHàm ttttạoooo ddddữ lilililiệuuuu chochochocho cáccáccáccác bbbbảngngngng RuleTable RuleTable RuleTable RuleTable c)c)c)c) HàmHàmHàmHàm ttttạoooo ddddữ lilililiệuuuu chochochocho cáccáccáccác bbbbảngngngng NodeTable NodeTable NodeTable NodeTable

28 23 November 2015

a)a)a)a) HàmHàmHàmHàm ttttạoooo ddddữ lilililiệuuuu chochochocho cáccáccáccác bbbbảngngngng EvidenceTable EvidenceTable EvidenceTable EvidenceTable b)b)b)b) HàmHàmHàmHàm ttttạoooo ddddữ lilililiệuuuu chochochocho cáccáccáccác bbbbảngngngng RuleTable RuleTable RuleTable RuleTable c)c)c)c) HàmHàmHàmHàm ttttạoooo ddddữ lilililiệuuuu chochochocho cáccáccáccác bbbbảngngngng NodeTable NodeTable NodeTable NodeTable

29 23 November 2015

a)a)a)a) ThêmThêmThêmThêm lulululuậtttt vàovàovàovào CSTTCSTTCSTTCSTT b)b)b)b) HàmHàmHàmHàm xxxxử lýlýlýlý xóaxóaxóaxóa lulululuậtttt khkhkhkhỏiiii CSTTCSTTCSTTCSTT c)c)c)c) HàmHàmHàmHàm ssssửaaaa lulululuậtttt suysuysuysuy didididiễnnnn trong trong CSTTCSTTCSTTCSTT trong trong d)d)d)d) HàmHàmHàmHàm kikikikiểmmmm tratratratra tínhtínhtínhtính hhhhợpppp llllệ ccccủaaaa CSTTCSTTCSTTCSTT

30 23 November 2015

10

23/11/2015

a)a)a)a) HàmHàmHàmHàm tínhtínhtínhtính trtrtrtrị ccccủaaaa mmmmộtttt nútnútnútnút b)b)b)b) HàmHàmHàmHàm tínhtínhtínhtính trtrtrtrị ccccủaaaa mmmmộtttt lulululuậtttt c)c)c)c) CácCácCácCác hàmhàmhàmhàm phânphânphânphân gigigigiảiiii cáccáccáccác phépphépphépphép toántoántoántoán AND, AND, OR,OR,OR,OR, NOTNOTNOTNOT AND, AND, CácCácCácCác hàmhàmhàmhàm ANDCombine( ORCombine( ANDCombine( ))));;;; ORCombine( ORCombine( ORCombine( ANDCombine( ANDCombine( NOTEvaluate( )))) nhnhnhnhằmmmm ththththứcccc hihihihiệnnnn cáccáccáccác ))));;;; NOTEvaluate( NOTEvaluate( NOTEvaluate( AND, OR,OR,OR,OR, NOTNOTNOTNOT nhnhnhnhằmmmm ttttạoooo sinhsinhsinhsinh phépphépphépphép toántoántoántoán AND, AND, AND, rararara quanquanquanquan hhhhệ ứngngngng vvvvớiiii vvvvị ttttừ kkkkếtttt qqqqủaaaa

(cid:1)

(cid:1)

(cid:1)

(cid:1)

31 23 November 2015

CáchCáchCáchCách kkkkếtttt hhhhợpppp cơcơcơcơ ssssở tritritritri ththththứcccc (CSTT) (CSTT) vvvvớiiii (CSTT) (CSTT) cơcơcơcơ ssssở ddddữ lilililiệuuuu (CSDL) (CSDL) (CSDL) (CSDL) CácCácCácCác ddddạngngngng lulululuậtttt cócócócó titititiềnnnn đđđđề làlàlàlà cáccáccáccác vvvvị ttttừ ứngngngng vvvvớiiii cáccáccáccác bbbbảngngngng trong trong CSDLCSDLCSDLCSDL trong trong CáchCáchCáchCách didididiễnnnn ddddịchchchch cáccáccáccác toántoántoántoán ttttử logic logic logic logic CáchCáchCáchCách suysuysuysuy didididiễnnnn ccccủaaaa hhhhệ CSTTCSTTCSTTCSTT kkkkếtttt hhhhợpppp vvvvớiiii CSDLCSDLCSDLCSDL

trong đđđđộngngngng cơcơcơcơ suysuysuysuy (cid:1) MMMMộtttt ssssố thuthuthuthuậtttt gigigigiảiiii trong trong trong

(cid:1)

didididiễnnnn VíVíVíVí ddddụ ápápápáp ddddụngngngng

(cid:1) Cấu trúc báo cáo bao gồm các phần như sau:

◦ 1. Mục đích ◦ 2. Phạm vi ◦ 3. Các sự kiện, ngữ cảnh và cách biểu diễn tri thức ◦ 4. aộng cơ suy diễn, các luật và diễn giải của luật ◦ 5. Sơ đồ kiến trúc hệ CSTT / hệ chuyên gia ◦ 6. Thiết kế giao diện, giao diện tổng thể và đặc tả chi tiết ◦ 7. Cài đặt chương trình và lựa chọn công cụ lập trình

(cid:1) Các bước cài đặt và cấu hình (cid:1) Hướng dẫn sử dụng chương trình

◦ 8. Kiểm tra và đánh giá ◦ 9. Viết báo cáo tổng kết ◦ 10. Bảo vệ BTL- dự án môn học (7 phút trình bày / mỗi

nhóm)

(cid:1)

32 23 November 2015

33 Hai V Pham hai@spice.ci.ritsumei.ac.jp

11

23/11/2015

(cid:1) Tất cả file mã nguồn, file chương trình và file

báo cáo nén .zip ghi theo định dạng

(cid:1) Ten_nhom_ten_tom_tat_du_an.zip (cid:1) (ghi rõ mã nguồn tham khảo nếu có) (cid:1) Bài tập gửi cho lớp phó / lớp trưởng (cid:1) Ngày nộp: 3 tuần trước khi kết thúc học kỳ (cid:1) Bản báo cáo nộp trực tiếp tại lớp khi nhóm

báo cáo

Hai V Pham 34 hai@spice.ci.ritsumei.ac.jp

12