Bài giảng 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
lượt xem 9
download
Bài giảng Xây dựng hệ khai mỏ dữ liệu: Phân lớp dữ liệu (cây quyết định) của Phan Hiển nêu lên khái quát về phân lớp dữ liệu; yếu tố quan trọng trong phân lớp dữ liệu; xu hướng, thang đo, cách xây dựng, thuật toán trong phân lớp dữ liệu.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng 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 PHÂN LỚP DỮ LIỆU (CÂY QUYẾT ĐỊNH) Phan Hiền
- 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 Lợi: 40 Đầu tư 100 Hại: 15 Lợi: 200 Đầu tư Mua vàng 300 Hại: 300 Lợi: 100 Đầu tư 1000 Hại: 500
- 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 Lợi: 40 0.7 Đầu tư 100 0.3 Hại: 15 Lợi: 200 0.4 Đầu tư Mua vàng 300 0.6 Hại: 300 Lợi: 100 0.8 Đầu tư 1000 0.2 Hại: 500
- 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) EV Pi *Vi i 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)
- XU HƯỚNG 1 Lợi: 40 0.7 Đầu tư EV= 23.5 100 0.3 Hại: -15 Lợi: 200 EV= 23.5 0.4 Đầu tư Mua vàng 300 EV= -100 0.6 Hại: -300 Lợi: 100 0.8 Đầu tư 1000 EV= -20 0.2 Hại: -500 Chọn EV cao, EV chính là khoảng lời lỗ kỳ vọng bình quân
- 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 En( X ) P( X i ) * Log2 P( X i ) i Đ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.
- 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. Enmax log 2 n Enmin log 2 1 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 En( X ) P( X i ) * Log2 P( X i ) i Ai En ( X | A) Ai A A * En( X / X j X ) A Ai IG( X | A) En( X ) En( X | A) 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) Giới Thu Giá Đi xe Giới Thu Giá Đi xe tính nhập xăng tính nhập xăng Nam [0,10) Cao Bus Nu [10,) Thap Cup Nam [10,) Cao Taxi Nam [0,10) Thap Bus Nu [10,) Cao Taxi Nam [0,10) Vua Cup Nu [0,10) Cao Bus Nam [10,) Vua Taxi Nu [0,10) Cao Bus Nam [0,10) Vua Cup Nu [0,10) Thap Cup Nu [10,) Vua Taxi 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
- Ví dụ - Lần 1 En(DX)=1.584 Xét 3 thuộc tính. Ký hiệu {a,b,c} là bộ số theo giá trị {Bus,Taxi,Cup} GT TN Nam: 6 Nu: 6 [0,10): 7 [10,): 5 {2,2,2} {2,2,2} {4,0,3} {0,4,1} IG(DX|GT)=0 IG(DX|TN)=0.709 GX Cao: 5 Vua: 4 Thap: 3 {3,2,0} {0,2,2} {1,0,2} IG(DX|GX)=En(DX) - [(5*En({3,2,0}) + 4*En({0,2,2}) + 3*En({1,0,2}))/12]=0.617
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Thiết kế hệ thống thông tin: Chương 1 - ThS. Lê Văn Tấn
40 p | 186 | 22
-
Bài giảng Xây dựng hệ thống Firewall: Bài 5 - Cao đẳng Nghề CNTT iSPACE
131 p | 73 | 21
-
Bài giảng Triển khai ứng dụng mạng - Bài 4: Xây dựng DNS Server
50 p | 132 | 21
-
Bài giảng Hệ thống thông tin quản trị - Chương 4: Tổng quan về tiến trình lựa chọn và phát triển hệ thống thông tin
12 p | 97 | 17
-
Bài giảng Triển khai ứng dụng mạng - Bài 5: Xây dựng Web, FPT server
63 p | 127 | 14
-
Bài giảng Thiết kế hệ thống mạng LAN - Chương 4: Quy trình thiết kế mạng LAN
55 p | 80 | 10
-
Bài giảng Hệ quản trị cơ sở dữ liệu: Chương 2 - ĐH Công nghiệp Thực phẩm
142 p | 73 | 8
-
Bài giảng môn học Nguyên lý hệ điều hành: Chương 1 – Đỗ Văn Uy
54 p | 134 | 8
-
Bài giảng Nguyên lý hệ điều hành: Chương 1 - Phạm Đăng Hải
115 p | 59 | 7
-
Bài giảng Nguyên lý hệ điều hành (handout): Chương 1 - Phạm Đăng Hải
33 p | 54 | 6
-
Bài giảng Nguyên lý Hệ điều hành - Chương 1: Các khái niệm cơ bản
54 p | 118 | 6
-
Bài giảng Xây dựng hệ: Biểu diễn và suy luận - Phan Hiền
39 p | 80 | 6
-
Bài giảng An toàn và bảo mật thông tin - Bài 5: Xây dựng hệ thống tường lửa mạng doanh nghiệp trên Microsoft Forefront Threat Management Gateway 2010
0 p | 84 | 5
-
Bài giảng Mật mã ứng dụng: Hệ mật RSA - Đại học Bách khoa Hà Nội
23 p | 15 | 5
-
Bài giảng Thiết kế hệ thống thông tin: Chương 6 - Trần Thị Kim Chi
140 p | 69 | 3
-
Bài giảng Xây dựng hệ khai mỏ dữ liệu: Mẫu thường xuyên, luật kết hợp - Phan Hiền
37 p | 66 | 3
-
Bài giảng Xây dựng hệ: Khai mỏ dữ liệu - Phan Hiền
13 p | 74 | 2
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn