Người ta đã nghiên cứu các hệ thống thông minh lai (hybrid intelligent system), trong đó kết hợp hai trường phái này. Các luật suy diễn của hệ chuyên gia có thể được sinh bởi mạng nơ-ron hoặc các luật dẫn xuất (production rule) từ việc học theo thống kê như trong kiến trúc ACT-R.
Các phương pháp trí tuệ nhân tạo thường được dùng trong các công trình nghiên cứu khoa học nhận thức (cognitive science), một ngành cố gắng tạo ra mô hình nhận thức của con người (việc này khác với các nghiên cứu TTNT, vì TTNT chỉ muốn tạo ra máy móc thực dụng, không phải tạo ra mô hình về hoạt động của bộ óc con người).
31 trang |
Chia sẻ: tlsuongmuoi | Lượt xem: 2322 | Lượt tải: 2
Bạn đang xem trước 20 trang tài liệu Các hệ cơ sở tri thức, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
L O G O
1
Bùi Đức Dương
Khoa Công nghệ Thông tin
Bài giảng Các hệ cơ sở tri thức
LOGO
2
1. Giới thiệu
Trong nhiều trường hợp, ta không có sẵn tri thức
Kỹ sư tri thức cần thu nhận tri thức từ các chuyên gia
Cần biết các luật mô tả lĩnh vực cụ thể
Bài toán không được biểu diễn tường minh theo luật, sự
kiện hay quan hệ.
Hai hướng tiếp cận cho hệ thống học:
Học từ ký hiệu
Học từ dữ liệu số
LOGO
3
2. Các hình thức học
Học vẹt
Học bằng cách chỉ dẫn
Học bằng quy nạp
Học bằng tương tự
Học dựa trên giải thích
Học dựa trên tình huống
Học không giám sát (Khám phá)
LOGO
4
3. Cây định danh
Xây dựng cây định danh dựa trên sự phân hoạch của
các thuộc tính
Phân hoạch:
Nút cha là thuộc tính được phân hoạch
Các nút con: Các giá trị phân biệt ứng với thuộc tính được phân
hoạch.
Là công cụ phổ biến trong một số ứng dụng
LOGO
5
3. Cây định danh
Ví dụ 1:
Bảng quan sát người đi tắm biển có/không bị rám nắng
TT Tên Màu tóc Chiều cao Cân nặng Dùng thuốc Kết quả
1 Hoa Đen TB Nhẹ Không Bị rám
2 Lan Đen Cao Vừa Có Không
3 Xuân Râm Thấp Vừa Có Không
4 Hạ Đen Thấp Vừa Không Bị rám
5 Thu Bạc TB Nặng Không Bị rám
6 Đông Râm Cao Nặng Không Không
7 Mơ Râm TB Nặng Không Không
8 Đào Đen Thấp Nhẹ Có Không
LOGO
6
3. Cây định danh (tt)
Râm Đen
Bạc
Dùng thuốc
Màu tóc
Không Có
Hoa, Hạ
ThuĐông, Xuân, Mơ
Lan, Đào
Một cây định danh tương ứng
LOGO
7
3. Cây định danh (tt)
Chuyển tri thức học từ dạng cây sang luật:
Đi từ nút gốc đến nút lá;
Lấy nút trong làm giả thiết;
Lấy nút lá làm kết luật .
Với cây định danh Ví dụ 1, ta có luật:
If (Màu tóc = Đen) and (Dùng thuốc = Không) then (Bị rám)
LOGO
8
4. Thuật toán Quinlan
Xây dựng các vector đặc trưng
VA(j) = (T(j, r1), T(j, r2),h T(j, rn))
Trong đó:
A: Thuộc tính dẫn xuất; r1, r2,h rn: Các thuộc tính mục tiêu
T(j, ri) = TAij/TAj
TAij : tổng số phần tử trong phân hoạch có thuộc tính A là j và thuộc
tính mục tiêu là ri.
TAj : tổng số phần tử trong phân hoạch có thuộc tính A là j.
Lưu ý: T(j, r1)+ T(j, r2)+h +T(j, rn) = 1
Vector đơn vị: Có 1 thành phần bằng 1; còn lại bằng 0.
Thuộc tính được chọn để phân hoạch là thuộc tính có
nhiều vector đơn vị nhất
LOGO
9
3. Cây định danh
Ví dụ 1:
Bảng quan sát người đi tắm biển có/không bị rám nắng
TT Tên Màu tóc Chiều cao Cân nặng Dùng thuốc Kết quả
1 Hoa Đen TB Nhẹ Không Bị rám
2 Lan Đen Cao Vừa Có Không
3 Xuân Râm Thấp Vừa Có Không
4 Hạ Đen Thấp Vừa Không Bị rám
5 Thu Bạc TB Nặng Không Bị rám
6 Đông Râm Cao Nặng Không Không
7 Mơ Râm TB Nặng Không Không
8 Đào Đen Thấp Nhẹ Có Không
LOGO
10
4. Thuật toán Quinlan (tt)
Ví dụ 2. Dựa trên bảng cho trong Ví dụ 1
Thuộc tính Màu tóc (3 giá trị)
Vmàu tóc(Đen) = (T(Đen/Bị rám), T(Đen/Không bị rám))
= (2/4, 2/4) = (0.5, 0.5)
Vmàu tóc(Râm) = (T(Râm/Bị rám), T(Râm/Không bị rám))
= (0/3, 3/3) = (0.0, 1.0)
Vmàu tóc(Bạc) = (T(Bạc/Bị rám), T(Bạc/Không bị rám))
= (1/1, 0/1) = (1.0, 0.0)
⇒ Số vector đơn vị: 02
LOGO
11
4. Thuật toán Quinlan (tt)
Thuộc tính Chiều cao (3 giá trị)
VChiều cao(Cao) = (0/2, 2/2) = (0.0, 1.0)
VChiều cao(TB) = (2/3, 1/3)
VChiều cao(Thấp) = (1/3, 2/3)
⇒ Số vector đơn vị: 01
Thuộc tính Cân nặng (3 giá trị)
VCân nặng(Nặng) = (1/3, 2/3)
VCân nặng(Vừa) = (1/3, 2/3)
VCân nặng(Nhẹ) = (1/2, 1/2)
⇒ Số vector đơn vị: 0
LOGO
12
4. Thuật toán Quinlan (tt)
Thuộc tính Dùng thuốc (2 giá trị)
VDùng thuốc(Có) = (0/3, 3/3) = (0.0, 1.0)
VDùng thuốc(Không) = (3/5, 2/5)
⇒ Số vector đơn vị: 01
Vậy, ta chọn thuộc tính màu tóc để phân hoạch!
Râm Đen
Bạc
Màu tóc
ThuĐông, Xuân, Mơ Hoa, Hạ, Lan, Đào
LOGO
13
4. Thuật toán Quinlan (tt)
Màu tóc TT Tên
Chiều
cao
Cân
nặng
Dùng
thuốc
Kết quả
Đen 1 Hoa TB Nhẹ Không Bị rám
Đen 2 Lan Cao Vừa Có Không
Đen 3 Hạ Thấp Vừa Không Bị rám
Đen 4 Đào Thấp Nhẹ Có Không
Thuộc tính Chiều cao (3 giá trị)
VChiều cao(Cao) = (0/1,1/1) = (0.0, 1.0)
VChiều cao(TB) = (1/1, 0/1) = (1.0, 0.0)
VChiều cao(Thấp) = (1/2, 1/2)
⇒ Số vector đơn vị: 02
LOGO
14
4. Thuật toán Quinlan (tt)
Thuộc tính Cân nặng (2 giá trị)
VCân nặng(Vừa) = (1/2, 1/2)
VCân nặng(Nhẹ) = (1/2, 1/2)
⇒ Số vector đơn vị: 0
Thuộc tính Dùng thuốc (2 giá trị)
VDùng thuốc(Có) = (0/2, 2/2) = (0.0, 1.0)
VDùng thuốc(Không) = (2/2, 0/2) = (1.0, 0.0)
⇒ Số vector đơn vị: 02
Có 2 thuộc tính cùng có 2 vector đơn vị:
Chiều cao: Tỷ lệ 2/3
Dùng thuốc: Tỷ lệ 2/2
Chọn thuộc tính Dùng thuốc để phân hoạch
LOGO
15
4. Thuật toán Quinlan (tt)
Râm Đen
Bạc
Dùng thuốc
Màu tóc
Không Có
Hoa, Hạ
ThuĐông, Xuân, Mơ
Lan, Đào
Cây định danh kết quả
LOGO
16
4. Thuật toán Quinlan (tt)
Râm Đen
Bạc
Dùng thuốc
Màu tóc
Không Có
Hoa, Hạ
ThuĐông, Xuân, Mơ
Lan, ĐàoKết quả học:
If (Màu tóc = Râm) then (Bị rám = Không)
If (Màu tóc = Bạc) then (Bị rám = Có)
If (Màu tóc = Đen) AND (Dùng thuốc = Không) then (Bị rám = Có)
If (Màu tóc = Đen) AND (Dùng thuốc = Có) then (Bị rám = Không)
LOGO
17
5. Học theo độ bất định
Độ bất định (entropy) của thuộc tính X
Thuật toán
b
bc
a
c b
bc
b t
b
n
n
n
n
n
n
XE log)( ∑∑ −=
Trong đó:
nb: số mẫu nhánh b; nt: tổng số mẫu; nbc: số mẫu trong nhánh b
của lớp c; a: Số lượng giá trị của thuộc tính mục tiêu.
Repeat
- Tính độ bất định cho mọi thuộc tính
- Chọn thuộc tính có độ bất định nhỏ nhất để phân hoạch
Until (Hết thuộc tính phân hoạch)
t
í t ị i t tí
t tí t ị t
til t t tí
LOGO
18
5. Học theo độ bất định (tt)
Ví dụ 3. Dựa trên bảng cho trong Ví dụ 1
Thuộc tính Màu tóc (3 giá trị)
Tập tóc đen: 2/4 người bị rám; 2/4 người không bị rám
Tập tóc bạc: 1/1 người bị rám; 0/1 người không bị rám
Tập tóc râm: 0/3 người bị rám; 3/3 người không bị rám
⇒ E(Màu tóc) = 4/8(-2/4log22/4-2/4log22/4)
+ 1/8(-1/1log21/1-0/1log20/1)
+3/8(-0/3log20/3-3/3log23/3)
= 0.5 + 0 + 0 =0.5.
Tương tự ta có:
E(Chiều cao)= 0.69; E(Cân nặng)=0.94; E(Dùng thuốc)=0.61.
Vậy, ta chọn Màu tóc làm thuộc tính phân hoạch
LOGO
19
5. Học theo độ bất định (tt)
Ở bước tiếp theo, ta sẽ tính được:
E(Chiều cao)=0.5;
E(Cân nặng)=1.0;
E(Dùng thuốc)=0.0;
Vậy ta chọn Dùng thuốc làm thuộc tính phân hoạch và được
cây định danh kết quả.
LOGO
20
5. Học theo độ bất định (tt)
Ví dụ 4:
LOGO
Chia bảng m mẫu thành n
bảng con theo tt quyết định
i=1; //số bảng con đã xét
R=∅; //Tập luật
Xét bảng con (i)
Chia các tt theo các tổ hợp
phân biệt j thuộc tính
21
6. Thuật giải ILA (Inductive Learning A)
j=1; //số thuộc tính kết hợp
j++Tìm tổ hợp lớn nhất
Tổ hợp lớn
nhất = ∅
TrueFalseĐánh dấu các dòng thỏa
tổ hợp lớn nhất
Các dòng đều
đã đánh dấu
Thêm luật mới vào R
i++
True
False
i>n
//Hết bảng con
False
END
True
LOGO
22
6. Thuật giải ILA (tt)
Ví dụ 5:
Bảng quan sát người đi tắm biển cho trong Ví dụ 1
TT Màu tóc Chiều cao Cân nặng Dùng thuốc Kết quả
1 Đen TB Nhẹ Không Bị rám
2 Đen Cao Vừa Có Không
3 Râm Thấp Vừa Có Không
4 Đen Thấp Vừa Không Bị rám
5 Bạc TB Nặng Không Bị rám
6 Râm Cao Nặng Không Không
7 Râm TB Nặng Không Không
8 Đen Thấp Nhẹ Có Không
LOGO
23
6. Thuật giải ILA (tt)
Bước 1: Chia thành 2 bảng con
Bảng TT Màu tóc Chiều cao Cân nặng Dùng thuốc Kết quả
1
1 Đen TB Nhẹ Không Bị rám
2 Đen Thấp Vừa Không Bị rám
3 Bạc TB Nặng Không Bị rám
Bảng TT Màu tóc Chiều cao Cân nặng Dùng thuốc Kết quả
2
1 Đen Cao Vừa Có Không
2 Râm Thấp Vừa Có Không
3 Râm Cao Nặng Không Không
4 Râm TB Nặng Không Không
5 Đen Thấp Nhẹ Có Không
LOGO
24
6. Thuật giải ILA (tt)
Xét bảng con i=1;
Bảng TT Màu tóc Chiều cao Cân nặng Dùng thuốc Kết quả
1
1 Đen TB Nhẹ Không Bị rám
2 Đen Thấp Vừa Không Bị rám
3 Bạc TB Nặng Không Bị rám
j=1 (1 thuộc tính):
Có 4 tổ hợp {Màu tóc}, {Chiều cao}, {Cân nặng} và {Dùng thuốc}
{Màu tóc} {Chiều cao} {Cân nặng} {Dùng thuốc}
Bạc (1) ∅ ∅ ∅
Tổ hợp lớn nhất: {Màu tóc}= “Bạc”
R = R ∪ {IF Màu tóc = Bạc THEN Kết quả = Bị rám}
LOGO
25
6. Thuật giải ILA (tt)
Bảng TT Màu tóc Chiều cao Cân nặng Dùng thuốc Kết quả
1
1 Đen TB Nhẹ Không Bị rám
2 Đen Thấp Vừa Không Bị rám
3 Bạc TB Nặng Không Bị rám
Tổ hợp lớn nhất: ∅;
Đánh dấu dòng có {Màu tóc}= “Bạc”
j=2 (2 thuộc tính):
{Màu tóc, Chiều cao}, {Màu tóc, Cân nặng}; {Màu tóc, Dùng thuốc}
{Chiều cao, Cân nặng}, {Chiều cao, Dùng thuốc}; {Cân nặng, Dùng thuốc}
R = R ∪ {IF Màu tóc = Bạc THEN Kết quả = Bị rám}
{Màu tóc} {Chiều cao} {Cân nặng} {Dùng thuốc}
∅ ∅ ∅ ∅
LOGO
26
6. Thuật giải ILA (tt)
{Màu tóc, Chiều cao} {Màu tóc, Cân nặng} {Màu tóc, Dùng thuốc}
Đen, TB (1) ∅ Đen, Không (2)
{Chiều cao, Cân nặng} {Chiều cao, Dùng thuốc} {Cân nặng, Dùng thuốc}
TB, Nhẹ (1) TB, Không (1) Nhẹ, Không (1)
Vừa, Không (1)
Tổ hợp lớn nhất: {Màu tóc, Dùng thuốc}= “Đen, Không”
Bảng TT Màu tóc Chiều cao Cân nặng Dùng thuốc Kết quả
1
1 Đen TB Nhẹ Không Bị rám
2 Đen Thấp Vừa Không Bị rám
3 Bạc TB Nặng Không Bị rám
Đánh dấu dòng có {Màu tóc, Dùng thuốc}= “Đen, Không”
R = R ∪ {IF Màu tóc = Đen AND Dùng thuốc =Không
THEN Kết quả = Bị rám}
LOGO
27
6. Thuật giải ILA (tt)
Xét bảng con i=2;
Bảng TT Màu tóc Chiều cao Cân nặng Dùng thuốc Kết quả
2
1 Đen Cao Vừa Có Không
2 Râm Thấp Vừa Có Không
3 Râm Cao Nặng Không Không
4 Râm TB Nặng Không Không
5 Đen Thấp Nhẹ Có Không
j=1 (1 thuộc tính):
{Màu tóc} {Chiều cao} {Cân nặng} {Dùng thuốc}
Râm (3) Cao (2) ∅ Có (3)
Tổ hợp lớn nhất: {Màu tóc}= “Râm” và {Dùng thuốc}=“Có”
Chọn tổ hợp đầu tiên: {Màu tóc}= “Râm”
LOGO
28
6. Thuật giải ILA (tt)
Bảng TT Màu tóc Chiều cao Cân nặng Dùng thuốc Kết quả
2
1 Đen Cao Vừa Có Không
2 Râm Thấp Vừa Có Không
3 Râm Cao Nặng Không Không
4 Râm TB Nặng Không Không
5 Đen Thấp Nhẹ Có Không
R = R ∪ {IF Màu tóc = Râm THEN Kết quả =Không}
Đánh dấu các dòng có : {Màu tóc}= “Râm”
{Màu tóc} {Chiều cao} {Cân nặng} {Dùng thuốc}
∅ Cao (1) ∅ Có (2)
Tổ hợp lớn nhất: {Dùng thuốc}=“Có”
LOGO
29
6. Thuật giải ILA (tt)
Bảng TT Màu tóc Chiều cao Cân nặng Dùng thuốc Kết quả
2
1 Đen Cao Vừa Có Không
2 Râm Thấp Vừa Có Không
3 Râm Cao Nặng Không Không
4 Râm TB Nặng Không Không
5 Đen Thấp Nhẹ Có Không
R = R ∪ {IF Dùng thuốc= Có THEN Kết quả =Không}
Đánh dấu các dòng có : {Dùng thuốc}= “Có”
Đánh dấu hết dòng
Đã xét hết các bảng con
Kết thúc
LOGO
30
Bài tập Chương
Tìm hiểu về:
Thuật giải di truyền
Mạng nơron nhân tạo
Hệ mờ
L O G O
31
Bùi Đức Dương
Khoa Công nghệ Thông tin
Các file đính kèm theo tài liệu này:
- Các hệ cơ sở tri thức.pdf