Bài giảng Hệ cơ sở tri thức (Tuần 13-15) trình bày các nội dung: Dạng luật trong CSTT, các dạng luật suy diễn, các phép toán, tiến trình suy diễn, phân giải luật suy diễn không đệ qui, các chức năng quản trị CSTT.
AMBIENT/
Chủ đề:
Nội dung Text: 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
Hai V Pham
hai@spice.ci.ritsumei.ac.jp 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.
23 November 2015 2
Rules:
Rules: R1, R2,…R3
Ri : IF THEN
parent(X
parent X,Y Y): - father(X
father X,Y
Y) | mother(X
mother X,Y
Y)
Với father,
father mother,
mother parent là các vị từ X,Y
Y
là các biến.
Mỗi vị từ p(X X,Y
Y,Z
Z) ứng với một quan hệ
P(XX,Y
Y,Z
Z) trong CSDL
23 November 2015 3
1
- 23/11/2015
Luật không đệ qui: Vị từ ở phần đầu không
xuất hiện trong phần thân của luật.
VD: sibling(X
sibling X,Y
Y):- parent(Z
parent Z,X
X) & mother(Z
mother Z,Y
Y)
Luật đệ qui: Vị từ ở phần đầu xuất hiện
trong phần thân của luật.
Ví dụ 3: ancestor(X
ancestor X,YY): - parent(X
parent X,Y
Y).
ancestor(X
ancestor X,Y
Y): - parent(X
parent X,ZZ) & ancestor(Z
ancestor Z,Y
Y)
23 November 2015 4
Phép AND(&) được xây dựng trên cơ sở
phép kết và phép chiếu của đại số quan hệ.
Với luật t(a
a,b
b,d
d,ee): r(a
a,b
b,c
c) & s(c
c,d
d,e
e), quan hệ
trong T(aa,b
b,d
d,ee) ứng với vị từ t(a a,b
b,d
d,e
e) được
tính theo cách sau:
Nếu dùng câu SQL, ta có câu lệnh tương
ứng:
SELECT r.aa, r.b
b, s.dd, s.e
e
FROM table r, table s
WHERE r.c c = s.cc.
23 November 2015 5
Phép toán OR (|) được xây dựng trên cơ sở
phép hợp sau đây:
t(a,b,c):
t(a,b,c): - r(a,b,c) | s(a,b,c)
Quan hệ T(a a,bb,c
c) trong t(a a,b
b,c
c) được tính
theo cách sau:
T(a,b,c) = R(a,b,c) ∪ S(a,b,c)
Nếu dùng SQL, ta có câu lệnh tương ứng :
SELECT * FROM table1 r
UNION SELECT * FROM table2 r INTO table t
23 November 2015 6
2
- 23/11/2015
Phép not(∼
not(∼ ) được xây dựng trên cơ sở phép
hiệu, ví dụ:
t(a,b,c):
t(a,b,c): - r(a,b,c) & (∼ s(a,b,c))
Quan hệ được suy T(a a,b
b,c
c) của vị từ t(a
a,b
b,c
c)
được tính theo cách sau:
t(a,b,c) = r(a,b,c) \ s(a,b,c)
Nếu dùng SQL, ta có thể cài đặt như sau:
SELECT a, b, e
FROM table r
WHERE a NOT IN (SELECT
SELECT a FROM s)
23 November 2015 7
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:
23 November 2015 8
Trong tiến trình suy diễn để tạo quan
hệ cho vị từ được suy grandfather(X
grandfather X,Y
Y)
chúng ta cần tạo các quan hệ cho các
vị từ father(X
father X,Z
Z) và parent(Z
parent Z,Y
Y).
23 November 2015 9
3
- 23/11/2015
Do father(X
father X,Z
Z) là quan hệ nền nên chỉ
cần thẩm định parent(Z
parent Z,Y
Y) bằng cách
so khớp và đồng nhất biến để có dạng
sau:
parent(Z,Y):
parent(Z,Y):- father(Z,Y) | mother(Z,Y)
23 November 2015 10
Với vị từ nền father(Z
father Z,Y
Y) chúng ta sử
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.
23 November 2015 11
Từ quan hệ father(F,C
father F,C),
F,C chúng ta có
các đồng nhất biến sau cho father(X
father X,Z
Z)
và father(Z
father Z,Y
Y).
FATHER(F
FATHER F C) father(X
father X Z) father(Z
father Z Y)
nam son nam son nam son
loc vinh loc vinh loc vinh
23 November 2015 12
4
- 23/11/2015
Có hai bước chính là:
Tạo cây suy diễn theo các luật.
Duyệt cây để thẩm định và tạo sinh
dữ liệu cho vị từ được suy.
Với hai luật:
r1: sibling
sibling(X
X,Y
Y):- parent(X
parent X,ZZ) & parent(Z
parent Z,YY) &
(X
XYY)
r2: parent(X
parent X,Y
Y):- father(X
father X,Y
Y) | mother(X
mother X,Y
Y)
23 November 2015 13
Vị từ được suy sibling(X
sibling X,Y
Y) với các đích
sibling(A
sibling A,B
B) sẽ được thẩm định như sau:
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.
23 November 2015 14
23 November 2015 15
5
- 23/11/2015
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:
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. 23 November 2015 16
23 November 2015 17
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):
Nganhhoc chứa các ngành học của trường.
Sinhvien(masv,manganh,holot,ten):
Sinhvien chứa hồ sơ sinh viên.
Moncoso(manganh,mamon,tenmon,sotc):
Moncoso các môn cơ sở của từng
ngành học và số tín chỉ của môn.
Chuan(manganh,mamon,dchuan):
Chuan điểm chuẩn của môn cơ sở chính
của ngành dùng để suy diễn.
Diemcoso(masv,mamon,dmon):
Diemcoso điểm kết quả môn của sinh viên.
Chuyennganh(manganh,machnganh):các
Chuyennganh chuyên ngành của từng
ngành.
Chuyende(machnganh,machde,tenchde,sotc):
Chuyende các chuyên đề của
ngành.
Diemchde(masv,machde,dchde):
Diemchde điểm kết quả chuyên đề của sinh
viên
23 November 2015 18
6
- 23/11/2015
Phần CSTT bao gồm các luật suy diễn dữ liệu sau:
Các luật
lu t suy diễn
di n 1: Sinh viên giỏi
gi i ở giai đoạn
đo n cơ sở
r1: IF diemcoso(masv,mamon,dmon)
diemcoso
AND chuan(manganh,
chuan mamon,
dmon,dchuan)
THEN
diemchinh(masv,manganh,mamon,dmon,dchuan)
diemchinh
Tạo quan hệ
diemchinh(masv,manganh,mamon,dmon,dchuan)
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 đó.
23 November 2015 19
r2:: IF dchinh(masv,manganh,
r2 dchinh mamon,
dmon,dchuan)
AND (dmon> dchuan)
THEN svgioicoso (masv,manganh)
Tạo quan hệ svgioicoso(masv,manganh)
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.
23 November 2015 20
Các luật
lu t suy diễn
di n 2: Sinh viên giỏi
gi i ở giai
đoạn
đo n chuyên ngành
r3:IF
IF chuyende(machnganh,machde,tenchde,sotchi)
chuyende
AND (sotchi>5)
THEN chdeqtrong(machnganh,
chdeqtrong machde)
Tạo quan hệ
chdeqtrong(machnganh,machde)
chdeqtrong chứa các
chuyên đề quan trọng theo nghĩa có số tín
chỉ lớn hơn 5.
23 November 2015 21
7
- 23/11/2015
r4: IF diemde(masv,machde,dchde)
AND (dchde>8
(dchde>8)
THEN svgioicde(masv, machde)
Tạo quan hệ svgioicde(masv,machde)
svgioicde
chứa các chuyên đề mà sinh viên đạt
kết quả tốt.
23 November 2015 22
r5: IFsvgioicde(masv,machde)
AND chdeqtrong(machnganh,machde)
THEN svgioichng(masv, machnganh)
Tạo quan hệ svgioichng(masv,
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á.
23 November 2015 23
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: IF svgioicoso(masv,manganh)
AND svgioichng(masv, machnganh)
THEN svtheochnganh(masv,machnganh)
Tạo quan hệ
svtheochnganh(masv,machnganh)
svtheochnganh suy luận
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 November 2015 24
8
- 23/11/2015
a) Bảng 1: EvidenceTable(RuleNo,Term)
EvidenceTable
Thuộc tính Term của bảng này chứa dạng
Postfix của phần giả thuyết của luật suy
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 ~ &
23 November 2015 25
b) Bảngng 2: RuleTable(Ruleno, Evidence,
Conclusion,Cfrule)
Chứa luật suy diễn dữ liệu. Cfrule là độ tin cây
của luật
c) Bảng
ng 3: NodeTable(NodeNo,NodeType,
NodeDescription, Cfnode)
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.
23 November 2015 26
Hệ quản
qu n trị
tr CSTT này, chúng ta có thểth
tiến
ti n hành soạn
so n thảo
th o các luật
lu t suy diễn
di n
dữ liệu
li u.
Hệ quản
qu n trị
tr CSTT bao gồm m các chức
ch c
năng thêm, xoá, sửa a luật
lu t.
23 November 2015 27
9
- 23/11/2015
a) Hàm tạo o dữ li liệu
u cho các bảng ng
EvidenceTable
b) Hàm tạo
o dữ liệu
li u cho các bảng
ng RuleTable
c) Hàm tạo o dữ liệuli u cho các bảng ng
NodeTable
23 November 2015 28
a) Hàm tạo o dữ liệu
li u cho các bảng
ng
EvidenceTable
b) Hàm tạo o dữ liệu
li u cho các bảng
ng
RuleTable
c) Hàm tạo o dữ li
liệu
u cho các bảng
ng
NodeTable
23 November 2015 29
a) Thêm luật
lu t vào CSTT
b) Hàm xử lý xóa luật
lu t khỏi
kh i CSTT
c) Hàm sửa
a luật
lu t suy diễn
di n trong CSTT
d) Hàm kiểm
ki m tra tính hợpp lệ của
a CSTT
23 November 2015 30
10
- 23/11/2015
a) Hàm tính trị
tr của
a mộtt nút
b) Hàm tính trị
tr của
a mộtt luật
lu t
c) Các hàm phân giảigi i các phép toán
AND, OR, NOT
Các hàm ANDCombine( ); ORCombine(
); NOTEvaluate( ) nhằm
nh m thức
th c hiện
hi n các
phép toán AND, OR, NOT nhằmnh m tạo o sinh
ra quan hệ ứng
ng vớii vị từ kếtt qủa
a
23 November 2015 31
Cách kếtt hợp p cơ sở tri thức
th c (CSTT) vớii
cơ sở dữ liệu
li u (CSDL)
Các dạng
ng luật
lu t có tiền
ti n đề là các vị từ
ng vớii các bảng
ứng ng trong CSDL
Cách diễn
di n dịch
ch các toán tử logic
Cách suy diễn
di n củaa hệ CSTT kếtt hợpp vớii
CSDL
Mộtt số thuật
thu t giải
gi i trong động
ng cơ suy
diễn
di n
Ví dụ áp dụngng
23 November 2015 32
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
Các bước cài đặt và cấu hình
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)
Hai V Pham
hai@spice.ci.ritsumei.ac.jp 33
11
- 23/11/2015
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
Ten_nhom_ten_tom_tat_du_an.zip
(ghi rõ mã nguồn tham khảo nếu có)
Bài tập gửi cho lớp phó / lớp trưởng
Ngày nộp: 3 tuần trước khi kết thúc học kỳ
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
hai@spice.ci.ritsumei.ac.jp 34
12
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
