Bài giảng Trí tuệ nhân tạo - Chương 5: Hệ học - Bùi Đức Dương

ọ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