Bài giảng Trí tuệ nhân tạo - Chương 4: Máy học

ẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH Xét một ví dụ: Cần xây dựng các quy luật để kết luận một người như thế nào khi đi tắm biển thì bị cháy nắng. Ta gọi tính chất cháy nắng hay không cháy nắng là thuộc tính quan tâm (thuộc tính mục tiêu). Trong trường hợp này, tập R gồm có hai phần tử {"cháy nắng", "bình thường"}. tập P là tất cả những người được liệt kê trong bảng (8 người) Hiện tượng cháy nắng dựa trên 4 thuộc tính sau: chiều cao (cao, trung bình, thấp), màu tóc (vàng, nâu, đỏ) cân nặng (nhẹ, TB, nặng), dùng kem (có, không). Ta gọi các thuộc tính này là thuộc tính dẫn xuất. 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH Ý tưởng Phân hoạch tập P thành các tập Pi sao cho tất cả các phần tử trong các tập Pi đều có chung thuộc tính mục tiêu. P = P1  P2  ...  Pn và (i,j) ij: thì (Pi  Pj =  ) và  i, k,l: pk Pi và pl Pj thì f(pk) = f(pl) 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH Các phân hoạch Pi được đặc trưng bởi thuộc tính đích ri (ri  R), Ứng với mỗi phân hoạch Pi ta xây dựng luật Li: GTi  ri trong đó các GTi là mệnh đề được hình thành bằng cách kết hợp các thuộc tính dẫn xuất. 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH Có hai cách phân hoạch hiển nhiên: Cách đầu tiên là cho mỗi người vào một phân hoạch riêng (P1 = {Sarah}, P2 = {Dana}, … tổng cộng sẽ có 8 phân hoạch cho 8 người). Cách thứ hai là phân hoạch thành hai tập, một tập gồm tất cả những người cháy nắng và tập còn lại gồm tất cả những người không cháy nắng. 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH Phương pháp khác. quan sát thuộc tính– màu tóc. có 3 phân hoạch: Pvàng = { Sarah, Dana, Annie, Kartie } Pnâu = { Alex, Peter, John } Pđỏ = { Emmile } 4.2.1. Đâm chồi 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH Dùng sơ đồ cây để mô tả phân hoạch: 4.2.1. Đâm chồi 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH Nhận xét: Tập Pnâu chứa toàn người không cháy nắng, Tập Pđỏ chứa toàn người cháy nắng, Tập Pvàng chứa lẫn lộn người cháy năng và không cháy nắng. Tiếp tục phân hoạch tập Pvàng thành 3 tập con: PVàng, Thấp = {Annie, Kartie}, PVàng, T.Bình= {Sarah} và PVàng,Cao= { Dana } 4.2.1. Đâm chồi 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH 4.2.1. Đâm chồi 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH Quá trình này cứ thế tiếp tục cho đến khi tất cả các nút lá của cây không còn lẫn lộn giữa cháy nắng và không cháy nắng. quá trình này được gọi là quá trình "đâm chồi". Cây mà chúng ta đang xây dựng được gọi là cây định danh. Nếu ban đầu ta không chọn thuộc tính màu tóc để phân hoạch mà chọn thuộc tính khác như chiều cao chẳng hạn để phân hoạch thì sao? Cuối cùng thì cách phân hoạch nào sẽ tốt hơn? 4.2.1. Đâm chồi 4.2.1 4.2.2 4.2.3 4.2.4 Đâm chồi Phương án chọn thuộc tính phân hoạch Phát sinh tập luật Tối ưu tập luật 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH "Đứng trước một ngã rẽ, ta cần phải đi vào hướng nào?". Hai phương pháp đánh giá dưới đây sẽ giúp ta chọn được thuộc tính phân hoạch tại mỗi bước xây dựng cây định danh. 4.2.2. Phương án chọn thuộc tính phân hoạch 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH a.Quinlan Quinlan quyết định thuộc tính phân hoạch bằng cách xây dựng các vector đặc trưng cho mỗi giá trị của từng thuộc tính dẫn xuất và thuộc tính mục tiêu. cụ thể như sau: Với mỗi thuộc tính dẫn xuất A còn có thể sử dụng để phân hoạch, tính: VA(j) = ( T(j , r1), T(j , r2) , …, T(j , rn)) 4.2.2. Phương án chọn thuộc tính phân hoạch 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH T(j, ri) = (tổng số phần tử trong phân hoạch có giá trị thuộc tính dẫn xuất A là j và có giá trị thuộc tính mục tiêu là ri) / (tổng số phần tử trong phân hoạch có giá trị thuộc tính dẫn xuất A là j) Trong đó r1, r2, … , rn là các giá trị của thuộc tính mục tiêu 4.2.2. Phương án chọn thuộc tính phân hoạch 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH một thuộc tính A có thể nhận một trong 5 giá trị khác nhau thì nó sẽ có 5 vector đặc trưng. Một vector V(Aj) được gọi là vector đơn vị nếu nó chỉ có duy nhất một thành phần có giá trị 1 và những thành phần khác có giá trị 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. 4.2.2. Phương án chọn thuộc tính phân hoạch 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH Thuộc tính màu tóc có 3 giá trị khác nhau (vàng, đỏ, nâu) nên sẽ có 3 vector đặc trưng tương ứng là: VTóc(vàng) = (T(vàng, cháy nắng), T(vàng, không cháy nắng)) Số người tóc vàng là: 4 Số người tóc vàng và cháy nắng là: 2 Số người tóc vàng và không cháy nắng là: 2 Do đó: VTóc(vàng) = (2/4 , 2/4) = (0.5, 0.5) Tương tự VTóc(nâu) = (0/3, 3/3) = (0,1) (vector đơn vị) Số người tóc nâu là: 3 Số người tóc nâu và cháy nắng là: 0 Số người tóc nâu và không cháy nắng là: 3 VTóc(đỏ) = (1/1, 0/1) = (1,0) (vector đơn vị) Tổng số vector đơn vị của thuộc tính tóc vàng là 2 4.2.2. Phương án chọn thuộc tính phân hoạch 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH Các thuộc tính khác được tính tương tự, kết quả như sau: VC.Cao(Cao) = (0/2,2/2) = (0,1) VC.Cao(T.B) = (2/3,1/3) VC.Cao(Thấp) = (1/3,2/3)  VC.Nặng (Nhẹ) = (1/2,1/2) VC.Nặng (T.B) = (1/3,2/3) VC.Nặng (Nặng) = (1/3,2/3)  VKem (Có) = (3/3,0/3) = (1,0) VKem (Không) = (3/5,2/5) thuộc tính màu tóc có số vector đơn vị nhiều nhất nên được chọn để phân hoạch. 4.2.2. Phương án chọn thuộc tính phân hoạch 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH tiếp tục phân hoạch tập Pvàng. tính vector đặc trưng đối với các thuộc tính còn lại (chiều cao, cân nặng, dùng kem). tập dữ liệu còn lại là: 4.2.2. Phương án chọn thuộc tính phân hoạch 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH 4.2.2. Phương án chọn thuộc tính phân hoạch 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH VC.Cao(Cao) = (0/1,1/1) = (0,1) VC.Cao(T.B) = (1/1,0/1) = (1,0) VC.Cao(Thấp) = (1/2,1/2)  VC.Nặng (Nhẹ) = (1/2,1/2) VC.Nặng (T.B) = (1/2,1/2) VC.Nặng (Nặng) = (0,0)  VKem (Có) = (0/2,2/2) = (0,1) VKem (Không) = (2/2,0/2) = (1,0) 4.2.2. Phương án chọn thuộc tính phân hoạch 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH 2 thuộc tính dùng kem và chiều cao đều có 2 vector đơn vị. Tuy nhiên, số phân hoạch của thuộc tính dùng kem là ít hơn nên chọn phân hoạch theo thuộc tính dùng kem. Cây định danh cuối cùng như sau: 4.2.2. Phương án chọn thuộc tính phân hoạch 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH 4.2.2. Phương án chọn thuộc tính phân hoạch 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH b.Độ đo hỗn loạn ứng với mỗi thuộc tính dẫn xuất ta cần tính độ đo hỗn loạn và lựa chọn thuộc tính nào có độ đo hỗn loại thấp nhất. Công thức tính như sau: 4.2.2. Phương án chọn thuộc tính phân hoạch TA = trong đó: bt : tổng số phần tử có trong phân hoạch bj : tổng số phần tử có thuộc tính dẫn xuất A có giá trị j. bri: tổng số phần tử có thuộc tính dẫn xuất A có giá trị j và thuộc tính mục tiêu có giá trị i. 4.2.1 4.2.2 4.2.3 4.2.4 Đâm chồi Phương án chọn thuộc tính phân hoạch Phát sinh tập luật Tối ưu tập luật 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH Nguyên tắc phát sinh tập luật: Ứng với mỗi nút lá, đi từ đỉnh cho đến nút lá đó và phát sinh ra luật tương ứng. Cụ thể là từ cây định danh kết quả ở trên ta có các luật sau (xét các nút lá từ trái sang phải) (Màu tóc vàng) và (có dùng kem)  không cháy nắng (Màu tóc vàng) và (không dùng kem)  cháy nắng (Màu tóc nâu)  không cháy nắng (Màu tóc đỏ)  cháy nắng 4.2.3. Phát sinh tập luật 4.2.1 4.2.2 4.2.3 4.2.4 Đâm chồi Phương án chọn thuộc tính phân hoạch Phát sinh tập luật Tối ưu tập luật 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH a.Loại bỏ mệnh đề thừa phương pháp loại bỏ mệnh đề thừa dựa vào dữ liệu. Với ví dụ và tập luật đã có ở phần trước, hãy quan sát luật sau: (Màu tóc vàng) và (có dùng kem)  không cháy nắng 4.2.4. Tối ưu tập luật 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH lập bảng Contigency, thống kê những người có dùng kem tương ứng với tóc màu vàng và bị cháy nắng hay không. Trong dữ liệu đã cho, có 3 người không dùng kem. 4.2.4. Tối ưu tập luật 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH Theo bảng thống kê: thuộc tính tóc vàng không kết luận cháy nắng hay không (cả 3 người dùng kem đều không cháy nắng) nên loại bỏ thuộc tính tóc vàng ra khỏi tập luật. Sau khi loại bỏ mệnh đề thừa, tập mệnh đề trong ví dụ trên sẽ còn:   (có dùng kem)  không cháy nắng (Màu tóc vàng) và (không dùng kem)  cháy nắng (Màu tóc nâu)  không cháy nắng (Màu tóc đỏ)  cháy nắng 4.2.4. Tối ưu tập luật 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH giả sử luật của chúng ta có n mệnh đề: A1 và A2 và … và An  R Để kiểm tra xem có thể loại bỏ mệnh đề Ai hay không, hãy lập ra một tập hợp P bao gồm các phần tử thỏa tất cả mệnh đề A1 , A2 , … Ai, Ai+1, …, An (lưu ý: không cần xét là có thỏa Ai hay không, chỉ cần thỏa các mệnh đề còn lại là được) 4.2.4. Tối ưu tập luật 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH Sau đó, bạn hãy lập bảng Contigency như sau: 4.2.4. Tối ưu tập luật Trong đó: E là số phần tử trong P thỏa cả Ai và R. F là số phần tử trong P thỏa Ai và không thỏa R G là số phần tử trong P không thỏa Ai và thỏa R H là số phần tử trong P không thỏa Ai và không thỏa R Nếu tổng F+H = 0 thì có thể loại bỏ mệnh đề Ai ra khỏi luật. 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH b.Xây dựng mệnh đề mặc định một vấn đề đặt ra là: khi gặp phải một trường hợp mà tất cả các luật đều không thỏa thì phải làm như thế nào? Một cách hành động là đặt ra một luật mặc định đại loại như: Nếu không có luật nào thỏa  cháy nắng (1) Hoặc Nếu không có luật nào thỏa  không cháy nắng. (2) 4.2.4. Tối ưu tập luật 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH Giả sử ta chọn luật mặc định là (2) thì tập luật của chúng ta sẽ trở thành: (Màu tóc vàng) và (không dùng kem)  cháy nắng (Màu tóc đỏ)  cháy nắng Nếu không có luật nào thỏa  không cháy nắng. (2) 4.2.4. Tối ưu tập luật 4.2 HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH Một số quy tắc khi chọn luật mặc định: (1) Chọn luật mặc định sao cho nó có thể thay thế cho nhiều luật nhất. (2) Chọn luật mặc định có kết luận phổ biến nhất. (3) Chọn luật mặc định sao cho tổng số mệnh đề của các luật mà nó thay thế là nhiều nhất. 4.2.4. Tối ưu tập luật Tổng kết chương 4 Bài tập