Phân lớp dữ liệu (cây quyết định) xây dựng hệ khai mỏ dữ liệu

PHÂN LỚP DỮ LIỆU (CÂY QUYẾT ĐỊNH) Phan Hiền XÂY DỰNG HỆ KHAI MỎ DỮ LIỆU KHÁI QUÁT  Cây quyết định là một phương pháp phân lớp dựa vào nguyên lý học có giám sát.  Yếu tố quan trọng ◦ Dữ liệu huấn luyện nên cây quyết định Dữ liệu phải là mẩu có độ chính xác cao. ◦ Thang đo trong việc phân lớp Thang đo phải phù hợp và thể hiện được tinh thần phân lớp dựa vào độ thường xuyên. XU HƯỚNG 1 Xét vấn đề sau: Một nhà đầu tư quyết định mua 3 dòng sản phẩm Xe, Vàng, Cổ phiếu. Nhà đầu tư nhận thấy (mọi chuyện tốt đẹp) nếu bỏ 100 mua Xe thì lời thu được là 40, nếu có lỗ thì thiệt hại là 15. Nếu bỏ 300 mua Vàng, nếu lời thu được là 200, nếu lỗ thì thiệt hại là 300. Nếu bỏ 1000 mua cổ phiếu, lời có thể là 100, nhưng thiệt hại có thể là 500. Ta có thể xác định một tổ chức các kế hoạch cho việc lựa chọn một quyết định đầu tư nào đó XU HƯỚNG 1 Đầu tư 100 Đầu tư 300 Đầu tư 1000 Lợi: 40 Lợi: 200 Lợi: 100 Hại: 15 Hại: 300 Hại: 500 Mua vàng XU HƯỚNG 1 Vấn đề được xét thêm yếu tố thường thấy Một nhà đầu tư quyết định mua 3 dòng sản phẩm Xe, Vàng, Cổ phiếu. Nhà đầu tư nhận thấy (mọi chuyện tốt đẹp) nếu bỏ 100 mua Xe thì lời thu được là 40, nếu có lỗ thì thiệt hại là 15. Nếu bỏ 300 mua Vàng, nếu lời thu được là 200, nếu lỗ thì thiệt hại là 300. Nếu bỏ 1000 mua cổ phiếu, lời có thể là 100, nhưng thiệt hại có thể là 500. Đối với mua xe, khả năng thành công là 0.7 Đối với mua vàng, khả năng thành công là 0.4 Đối với mua cổ phiếu, khả năng thành công là 0.8 Ta có thể xác định một tổ chức các kế hoạch cho việc lựa chọn một quyết định đầu tư nào đó XU HƯỚNG 1 Đầu tư 100 Đầu tư 300 Đầu tư 1000 Lợi: 40 Lợi: 200 Lợi: 100 Hại: 15 Hại: 300 Hại: 500 Mua vàng 0.7 0.3 0.4 0.6 0.8 0.2 XU HƯỚNG 1 Vấn đề đặt ra là lựa chọn phương án nào. Có 2 giải pháp - Dùng hệ số kỳ vọng (Expected value) Pi là khả năng của nhánh i, Vi là giá trị đạt của nhánh i. - Dùng hệ số hữu dụng (Utility) Dựa vào hàm mũ để xác định tính chất độ hữu dụng giảm dần khi được cung cấp quá nhiều. - Dùng hệ số liều lỉnh (Risk)  i ii VPEV * XU HƯỚNG 1 Đầu tư 100 Đầu tư 300 Đầu tư 1000 Lợi: 40 Lợi: 200 Lợi: 100 Hại: -15 Hại: -300 Hại: -500 Mua vàng 0.7 0.3 0.4 0.6 0.8 0.2 EV= 23.5 Chọn EV cao, EV chính là khoảng lời lỗ kỳ vọng bình quân EV= -100 EV= -20 EV= 23.5 XU HƯỚNG 1 Bài toán có thể được mở rộng cho nhiều phần hơn, cây quyết định có nhiều cấp độ hơn. XU HƯỚNG 2  Xây dựng cây quyết định là quá trình phân lớp.  Xây dựng cây quyết định dựa trên tập các giá trị huấn luyện.  Vấn đề quan tâm ◦ Thang đo để quyết định tách lớp ◦ Tập dữ liệu THANG ĐO  Vấn đề chính trong việc xây dựng cây quyết định là ta tách nhóm dựa vào mức độ lặp lại thường xuyên của các thuộc tính trong dữ liệu mẫu.  Xét ví dụ: Đổ hột xí ngầu, nếu hột xí ngầu cân bằng, khả năng có được các mặt là 1/6. Nếu hột xí ngầu không cân bằng, khả năng có các mặt là khác nhau. Ta nói trong trường hợp cân bằng thì lần tung sau, bạn rất khó đoán là ra mặt nào. Nếu không cân bằng thì lần sau, bạn rất dễ đoán là ra mặt nào. THANG ĐO  Xây dựng một độ đo để nếu khả năng tất cả các trường hợp ngang nhau thì độ đo là lớn nhất, sự chênh lệch khả năng của các trường hợp tạo nên độ đo thấp.  Với độ đo thấp, khả năng ta đoán được lần sau, và đó là khả năng sinh luật. ENTROPY Đo mức độ không đáng tin của việc đoán sự xuất hiện trường hợp nào (Xi) của biến cố X.  i ii XPLogXPXEn )(*)()( 2 THANG ĐO  Nếu Entropy thấp  mức độ không đáng tin thấp  mức độ tin vào việc đoán được sự xuất hiện các trường hợp là cao. (thể hiện luôn việc phán đoán (sinh luật) là dựa vào độ thường xuyên của các biến cố cao)  Chọn Entropy thấp. nEn 2max log 1log2min En En đạt max khi P(Xi) = 1/n với mọi i=1..n En đạt min khi tồn tại P(Xi) = 1 và mọi P(Xj) = 0 với j khác i. THANG ĐO  Ví dụ cho thuộc tính Xe, có tập các giá trị {Dream, Click, Atitla} và có tập các thề hiện như sau T1={D} T2={C} T3={D} T4={D} T5={C} T6={C} T7={D} T8={D} T9={D} T10={A} T11={D} T12={A}  Xét độ đo En(Xe) En(Xe) = [(7/12)*log2(12/7)] + [(3/12)*log2(12/3)] + [(2/12)*log2(12/2)] = 1.3844 THANG ĐO  IG (Information Gain) thông tin có ích.  IG thể hiện sự thay đổi của mức độ không đáng tin của biến cố X từ lúc chưa có sự xuất hiện của biến có A đến khi có sự xuất hiện của biến cố A.  IG(X|A) = En(X) – En(X|A)  Nếu IG cao  Sự xuất hiện A làm cho En(X) giảm nhiều  mức độ đáng tin xuất hiện các trạng thái Xi là cao  Ta chọn A để tách nhóm theo độ thường xuyên cho đích là X. THANG ĐO )/(*)|(     AA AA j i i i XXXEn A A AXEn )|()()|( AXEnXEnAXIG   i ii XPLogXPXEn )(*)()( 2 Ta lựa chọn IG cao XÂY DỰNG CÂY QUYẾT ĐỊNH  Chọn thuộc tính đích (tức mọi nhánh – mọi luật đều nhắm đến kết quả của thuộc tính này). -----------------------------  Chọn một thuộc tính (dựa vào IG cao nhất)  Với các giá trị của thuộc tính đã chọn, ta tách ra nhiều nhánh.  Mỗi nhánh lại hình thành tập dữ liệu huấn luyện mới (trừ đi thuộc tính đã chọn). Tiếp tục làm cho đến hết. THUẬT TOÁN B1: Chọn thuộc tính đích X B2: Tính IG cho tất cả các thuộc tính còn lại – IG(X,Ai) B3: Chọn thuộc tính Ai có IG(X, Ai) cao nhất B4: Với mọi giá trị của thuộc tính Ai , tách ra thành nhiều nhánh B5: ứng với từng nhánh ta có tập dữ liệu huấn luyện mới TAi (bỏ đi thuộc tính Ai). Ta làm lại B2 với từng Aj trong TAi mà Aj khác X. B6: Với một nhánh nào đó mà dữ liệu là đồng nhất giá trị X. Ta chấm dứt. Ví dụ Cho tập dữ liệu huấn luyện như sau (GT,TN,GX,DX) Ta chọn thuộc tính Đi Xe là thuộc tính đích En(đi xe) = En({Bus,Taxi,Cup}) = En({4,4,4}) = 1.584 Giới tính Thu nhập Giá xăng Đi xe Nam [0,10) Cao Bus Nam [10,) Cao Taxi Nu [10,) Cao Taxi Nu [0,10) Cao Bus Nu [0,10) Cao Bus Nu [0,10) Thap Cup Giới tính Thu nhập Giá xăng Đi xe Nu [10,) Thap Cup Nam [0,10) Thap Bus Nam [0,10) Vua Cup Nam [10,) Vua Taxi Nam [0,10) Vua Cup Nu [10,) Vua Taxi Ví dụ - Lần 1 Xét 3 thuộc tính. Ký hiệu {a,b,c} là bộ số theo giá trị {Bus,Taxi,Cup} GT Nam: 6 Nu: 6 {2,2,2} {2,2,2} TN [0,10): 7 [10,): 5 {4,0,3} {0,4,1} GX Cao: 5 Thap: 3 {3,2,0} {1,0,2} Vua: 4 {0,2,2} En(DX)=1.584 IG(DX|GT)=0 IG(DX|TN)=0.709 IG(DX|GX)=En(DX) - [(5*En({3,2,0}) + 4*En({0,2,2}) + 3*En({1,0,2}))/12]=0.617 Ví dụ - Lần 1 Xét thuộc tính TN, ta có 2 nhánh, ta làm với từng nhánh TN [0,10): 7 [10,): 5 {4,0,3} {0,4,1} Giới tính Thu nhập Giá xăng Đi xe Nam [0,10) Cao Bus Nu [0,10) Cao Bus Nu [0,10) Cao Bus Nu [0,10) Thap Cup Nam [0,10) Thap Bus Nam [0,10) Vua Cup Nam [0,10) Vua Cup Giới tính Thu nhập Giá xăng Đi xe Nam [10,) Cao Taxi Nu [10,) Cao Taxi Nu [10,) Thap Cup Nam [10,) Vua Taxi Nu [10,) Vua Taxi Ví dụ - Lần 2 Xét 2 thuộc tính GT và GX với TN = [10,) Chọn thuộc tính GX, và các nhánh tách từ GX đều có sự đồng nhất về đích.  Chấm dứt nhánh này. GT Nam: 2 Nu: 3 {0,2,0} {0,2,1} GX Cao: 2 Thap: 1 {0,2,0} {0,0,1} Vua: 2 {0,2,0} En(DX)=En({0,4,1})=0.721 IG(DX|GT)=0.17 IG(DX|GX)= 0.721 Ví dụ - Lần 3 Xét 2 thuộc tính GT và GX với TN = [0,10) Chọn thuộc tính GX, và các nhánh tách từ GX có sự đồng nhất về đích ở nhánh Cao và Vua, nhánh thap không đồng nhất.  Chọn xét tiếp ở Nhánh GX thấp. GT Nam: 4 Nu: 3 {2,0,2} {2,0,1} GX Cao: 3 Thap: 2 {3,0,0} {1,0,1} Vua: 2 {0,0,2} En(DX)=En({0,4,3})=0.985 IG(DX|GT)=0.02 IG(DX|GX)= 0.699 Ví dụ - Lần 3 Xét thuộc tính TN, ta có 1 nhánh Lần 4 Ta có 1 thuộc tính còn lại  Chắc chắn chọn GT và ta có các nhánh của GT đều có sự đồng nhất về thuộc tính đích. Chấm dứt. GX Thap: 2 {1,0,1} Giới tính Thu nhập Giá xăng Đi xe Nu [0,10) Thap Cup Nam [0,10) Thap Bus GT Nam: 1 Nu: 1 {1,0,0} {0,0,1} Kết quả TN [0,10): 7 [10,): 5 GX Thap: 1 Cao,Vua: 4 GX Cao: 3 Thap: 2 Vua: 2 Taxi Cup Bus Cup GT Nam: 1 Nu: 1 Bus Cup Xuất luật  Nếu thu nhập trong khoảng [0,10) và giá xăng cao thì lựa chọn là xe Bus.  .  Nếu thu nhập trong khoảng [0,10) và giá xăng thấp và là nữ thì lựa chọn là xe cup.