Bài giảng Các hệ cơ sở tri thức

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