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ủ đề:
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
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
