Bài giảng Nhập môn khai phá dữ liệu - Chương 5: Phân lớp - Hà Quang Thụy
BÀI GIẢNG NHẬP MÔN KHAI PHÁ DỮ LIỆU
CHƯƠNG 5. PHÂN LỚP
PGS. TS. Hà Quang Thụy
HÀ NỘI, 08-2018
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
ĐẠI HỌC QUỐC GIA HÀ NỘI
Charu C. Aggarwal. Data Classification: Algorithms. CRC Press, 2014.
1
Nội dung
Giới thiệu phân lớp
Phân lớp học giám sát
Phân lớp học bán giám sát
2
Phân lớp: Một vài bài toán ví dụ
⚫ 1. Bài toán phân lớp kết quả xét nghiệm
▪ Miền dữ liệu I = {phiếu xé t nghiệm},
▪ Biến mục tiêu “tập hợp lớp” O = {dương tinh, â m tí nh}
▪ Á nh xạ f: I → O, f chưa biết
▪ Input: Tập ví dụ mẫu IL gồm phiếu xé t nghiệm đã có nhã n
dương tì nh/â m tí nh.
▪ Output: Á nh xạ xấp xỉ tốt nhất f* để xâ y dựng chương trì nh
tự động gá n nhã n cho mọi phiếu xé t nghiệm.
⚫ 2. Bài toán phân lớp cam kết khách hàng
▪ Miền dữ liệu: Tập thô ng tin mua hàng khá ch hàng RFM
▪ Mục tiêu “tập hợp lớp” O = {Trung thành cao, Trung thành
thấp, Bì nh thường}
▪ Á nh xạ f: I → O, f chưa biết
▪ Input: Tập ví dụ mẫu IL gồm khá ch hàng với RFM và nhã n
tương ứng.
▪ Output: Á nh xạ xấp xỉ tốt nhất f* để xâ y dựng chương trì nh
tự động gá n nhã n cho mọi khá ch hàng.
3
Phân lớp: Một vài bài toán ví dụ
⚫ 3. Bài toán phân lớp quan điểm
▪ Miền dữ liệu I = {nhận xé t sản phẩm A},
▪ Mục tiêu “tập hợp lớp” O = {khen, chê}
▪ Á nh xạ f: I → O, f chưa biết
▪ Input: Tập ví dụ mẫu IL gồm đánh giá đã có nhã n khen/chê.
▪ Output: Á nh xạ xấp xỉ tốt nhất f* để xâ y dựng chương trì nh
tự động gá n nhã n cho mọi nhận xé t.
⚫ 4. Bài toán phân lớp trang web
▪ Miền dữ liệu: Tập cá c trang web miền lí nh vực quan tâ m
▪ Mục tiêu “tập hợp lớp” O = {Kinh tế, Thế giới, Thể thao, Giá o
dục, v.v.}
▪ Á nh xạ f: I → O, f chưa biết
▪ Input: Tập ví dụ mẫu IL gồm trang web có nhã n thuộc O.
▪ Output: Á nh xạ xấp xỉ tốt nhất f* để xâ y dựng chương trì nh
tự động gá n nhã n cho mọi trang web mới tải về.
4
Các mức phân tích kinh doanh
Làm gì khi nó xảy ra
một lần nữa?
Khi nào nó sẽ xảy ra?
PHÂN LỚP
Vì sao điều đó xảy ra?
KHAI PHÁ LUẬT KẾT HỢP
PHÂN CỤM
Điều gì đã xảy ra?
- Hiểu sâ u sắc thị trường và khá ch hàng,
- Hiểu vận hành nội bộ và nhâ n viên,
- Hiểu giá trị dữ liệu
5
2. Học máy giám sát bài toán tối ưu hóa
⚫ Bốn ví dụ trên đều có thể sử dụng học máy
giá m sá t
⚫ Bài toán học máy giám sát
▪ Cho miền dữ liệu I và một tập nhã n O (hữu hạn)
▪ Tồn tại một á nh xạ f: I → O, f chưa biết
Input
▪ Cho “tập ví dụ mẫu” IL: (ILIIL),
f xá c định trên IL, i IL: f(i)=o đã biết.
Output
▪ Tì m á nh xạ toàn bộ f* xấp xỉ tốt nhất f. Bộ phâ n lớp
⚫ Ví dụ và trao đổi
▪ Miền dữ liệu I = {nhận xé t sản phẩm A}, O = {khen, chê}
▪ Á nh xạ f: I → O, f chưa biết
▪ Input: Tập ví dụ mẫu IL gồm đánh giá đã có nhã n khen/chê.
▪ Output: Á nh xạ xấp xỉ tốt nhất f* để xâ y dựng chương trì nh
6
tự động gá n nhã n cho mọi nhận xé t.
Xấp xỉ tốt nhất?
⚫ Biết f chỉ ở một bộ phận (tập IL): f|IL
▪ Thá ch thức
❖ Tập G vô hạn cá c á nh xạ, gG, g: I→O
❖ Chưa biết f toàn bộ
▪ Cơ hội: Biết f|IL để chọn f* “xấp xỉ tốt nhất” f
▪ f|IL là toàn bộ “hiểu biết” về f
❖ vừa để tì m ra f*
❖ vừa để kiểm tra tí nh “tốt nhất” của f*
⚫ Xấp xỉ tốt nhất
▪ Giả thiết: IL “đại diện” cho I; “mọi đặc trưng của I” đều tì m
được từ IL.
▪ “đánh giá” cần độc lập với “xây dựng”
▪ IL: vừa tì m f* vừa đánh giá f*. Chia ngẫu nhiên IL = ITrain +
ITest. ITrain xâ y dựng f* và ITest đánh giá f*.
▪ Một số độ đo “tốt” liên quan đến tí nh “tốt nhất”
7
Bài toán phân lớp
⚫ Đầu vào
⚫ Tập dữ liệu D = {di}
⚫ Tập cá c lớp C1, C2, …, Ck mỗi dữ liệu d thuộc một lớp Ci
⚫ Tập ví dụ Dexam = D1+D2+ …+ Dk với Di={dDexam: d thuộc Ci}
⚫ Tập ví dụ Dexam đại diện cho tập D
⚫ D gồm m dữ liệu di thuộc không gian n chiều
⚫ Đầu ra
⚫ Mô hì nh phâ n lớp: á nh xạ từ D sang C
⚫ Sử dụng mô hì nh
⚫ d D \ Dexam : xá c định lớp của đối tượng d
8
Phân lớp: Quá trình hai pha
⚫ Xâ y dựng mô hì nh: Tì m mô tả cho tập lớp đã có
⚫ Cho trước tập lớp C = {C1, C2, …, Ck}
⚫ Cho á nh xạ (chưa biết) từ miền D sang tập lớp C
⚫ Có tập ví dụ Dexam=D1+D2+ …+ Dk với Di={dDexam: dCi}
D
exam được gọi là tập ví dụ mẫu.
⚫ Xâ y dựng á nh xạ (mô hì nh) phâ n lớp trên: Dạy bộ phâ n lớp.
⚫ Mô hì nh: Luật phâ n lớp, câ y quyết định, cô ng thức toá n học…
⚫ Pha 1: Dạy bộ phâ n lớp
⚫ Tá ch Dexam thành Dtrain (2/3) + Dtest (1/3). Dtrain và Dtest “tí nh đại
diện” cho miền ứng dụng
⚫ Dtrain : xâ y dựng mô hì nh phâ n lớp (xá c định tham số mô hì nh)
⚫ Dtest : đánh giá mô hì nh phâ n lớp (cá c độ đo hiệu quả)
⚫ Chọn mô hì nh có chất lượng nhất
⚫ Pha 2: Sử dụng mô hình (bộ phâ n lớp)
⚫ d D \ Dexam : xá c định lớp của d.
9
Ví dụ phân lớp: Bài toán cho vay
Tid
1
Refund
No
Marital Status Taxable Income Cheat
Single
Married
Single
75K
50K
75K
150K
40K
80K
75K
50K
50K
150K
40K
150K
80K
40K
80K
No
No
2
Yes
No
3
No
4
No
Married
Single
Yes
No
5
No
6
No
Married
Single
Yes
No
7
No
8
Yes
Yes
No
Married
Married
Married
Single
No
9
No
10
11
12
13
14
15
Yes
No
No
No
Married
Married
Single
Yes
Yes
No
No
No
No
Married
Yes
Ngân hàng cần cho vay: trả đúng hạn, hôn nhân, thu nhập
10
“Lớp” liên quan tới cheat (gian lận): hai lớp YES/NO
Phân lớp: Quá trình hai pha
11
Các loại phân lớp
– Phâ n lớp nhị phân/đa lớp
Nhị phâ n: hai lớp
(|C| = 2)
Đa lớp: số lượng lớp > 2 (|C| > 2)
– Phân lớp đơn nhãn/đa nhãn/phân cấp
Đơn nhãn: Một đối tượng chỉ thuộc duy nhất một
lớp
– Đa nhãn: Một đối tượng thuộc một hoặc nhiều lớp
– Phân cấp: Lớp này là con của lớp kia
12
3. Đánh giá mô hình phân lớp
– Phương pháp đánh giá hiệu quả
Câu hỏi: Làm thế nào để đánh giá được hiệu quả
của một mô hình? Khách quan
– Độ đo đánh giá hiệu quả
Câu hỏi: Làm thế nào để có được ước tính đáng
tin cậy? Sử dụng các độ đo. Nhiều độ đo: phổ biến
– Phương pháp so sánh mô hình
Câu hỏi: Làm thế nào để so sánh hiệu quả tương
đối giữa các mô hình có tính cạnh tranh? Cùng bộ
bộ dữ liệu mẫu, cùng cách đánh giá (bộ độ đo,
kịch bản, v.v.)
13
Đánh giá phân lớp nhị phân
– Theo dữ liệu test
– Giá trị thực: P dương / N â m; Giá trị qua phâ n lớp: T
đúng/F sai. : cò n gọi là ma trận nhầm lẫn
– Sử dụng cá c ký hiệu TP (true positives), TN (true
negatives), FP (false positives), FN (false negatives)
• TP: số ví dụ dương P mà thuật toá n phâ n đúng (T) cho dương P
• TN: số ví dụ â m N mà thuật toá n phâ n đúng (T) cho â m
• FN: số ví dụ dương P mà thuật toá n phâ n sai (F) cho â m
- FP: số ví dụ â m N mà thuật toá n phâ n sai (F) cho dương
N
N
P
- Độ hồi tưởng , độ chí nh xá c , cá c độ đo F1 và F
TP
TP
=
=
TP + FN
14
Đánh giá phân lớp nhị phân: minh họa
R là tập ví dụ kiểm thử được bộ phân lớp gán nhãn
dương, L là tập vị dụ kiểm thử thực tế có nhãn dương
15
Đánh giá phân lớp nhị phân
– Phương á n khá c đánh giá mô hì nh nhị phâ n theo
độ chí nh xá c (accuracy) và hệ số lỗi (Error rate)
– Ma trận nhầm lẫn
Lớp dự báo
Lớp = 1
f11
Lớp = 0
f10
Lớp = 1
Lớp = 0
Lớp thực sự
f01
f00
16
So sánh hai phương án
– Tập test có 9990 ví dụ lớp 0 và 10 ví dụ lớp 1. Kiểm
thử: mô hì nh dự đoán cả 9999 ví dụ là lớp 0 và 1 ví
dụ lớp 1. TP=1 FN = 9
TN=9990 FP= 0
– Theo phương á n (recall, precision) có
= 1/10=0.1; =1/1=1; f1 = 2*0.1/(0.1+1.0)= 0.18
– Theo phương á n (accurary, error rate) có
accurary=0.9991; error rate = 9/10000 = 0.0009
Được coi là rất chí nh xá c !
– f1 thể hiện việc đánh giá nhạy cảm với giá dữ
liệu
17
Đánh giá phân lớp đa lớp
- Bài toá n ban đầu: C gồm có k lớp
– Đối với mỗi lớp Ci , cho thực hiện thuật toá n với cá c dữ
liệu thuộc Dtest nhận được cá c đại lượng TPi, TFi, FPi, FNi
(như bảng dưới đây)
Giá trị thực
Lớp Ci
Không thuộc
Thuộc lớp Ci
lớp Ci
Thuộc lớp Ci
TPi
FNi
FPi
Giá trị qua bộ
phân lớp đa
lớp
Không thuộc
TNi
lớp Ci
18
Đánh giá phân lớp đa lớp
⚫ Tương tự bộ phân lớp hai lớp (nhị phân)
⚫ Độ chí nh xá c Pri của lớp Ci là tỷ lệ số ví dụ dương được thuật
toá n phâ n lớp cho giá trị đúng trên tổng số ví dụ được thuật toá n
phâ n lớp vào lớp Ci :
TP
TP + FP
i
Pri =
i
i
⚫ Độ hồi tưởng Rei của lớp Ci là tỷ lệ số ví dụ dương được thuật
toá n phâ n lớp cho giá trị đúng trên tổng số ví dụ dương thực sự
thuộc lớp Ci:
TP
i
Rei =
TP + FNi
i
19
Đánh giá phân lớp đa lớp
- Cá c giá trị i và i : độ hồi phục và độ chí nh xá c đối
với lớp Ci.
- Đánh giá theo cá c độ đo
- trung bì nh mịn (micro – average, được ưa chuộng) và
- trung bì nh thô (macro- average) M và M
K
K
1
M =
1
M =
K
c
K
c
c=1
c=1
K
K
TP
TP
c=1
c=1
=
=
c
c
K
K
(TP + FN )
c=1
(TP + FN )
c
c
c=1
c
c
20
Tải về để xem bản đầy đủ
70 trang
15500
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Nhập môn khai phá dữ liệu - Chương 5: Phân lớp - Hà Quang Thụy", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_nhap_mon_khai_pha_du_lieu_chuong_5_phan_lop_ha_qua.pdf
