intTypePromotion=1

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

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PDF | Số trang:26

0
43
lượt xem
6
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) - Phan Hiển

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:
Lưu

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

  1. 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
  2. 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.
  3. 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 đó
  4. 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
  5. 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 đó
  6. 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
  7. 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)
  8. 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
  9. 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.
  10. 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
  11. 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.
  12. 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.
  13. 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.
  14. 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
  15. 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.
  16. 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
  17. 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.
  18. 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.
  19. 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
  20. 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
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2