Bài giảng Học máy - L5: Các phương pháp học có giám sát Học dựa trên các láng giềng gần nhất (Nearest)

Nội dung text: Bài giảng Học máy - L5: Các phương pháp học có giám sát Học dựa trên các láng giềng gần nhất (Nearest)

1. Nội dung môn học: „ Giới thiệu chung „ Đánh giá hiệunăng hệ thống họcmáy „ Các phương pháp họccd dựatrênxácsua trên xác suất „ Các phương pháp họccógiámsát „ Học dựa trên các láng giềng gần nhất (Nearest neighbors learning) „ Các phương pppháp học không giám sát „ Lọccộng tác „ Học tăng cường Học Máy – IT 4862 2
2. Học dựa trên các láng giềng gần nhất „ Biểu diễn đầu vào của bài toán • Mỗi ví dụ x được biểu diễn là một vectơ n chiều trongggg không gian các vectơ X∈Rn • x = (x1,x2, ,xn), trong đó xi (∈R) là một số thực „ Có thể áp dụng được với cả 2 kiểu bài toán học • Bài toán phân lớp (classification) ─ Hàm mục tiêu có giá trị rời rạc (a discrete-valued targg)et function) ─ Đầu ra của hệ thống là một trong số các giá trị rời rạc đã xác định trước (một trong các nhãn lớp) • Bài toán dự đoán/hồi quy (prediction/regression) ─ Hàm mục tiêu có giá trị liên tục (a continuous-valued target function) ─ Đầu ra của hệ thống là một giá trị số thực ọ H c Máy – IT 4862 4
3. Giải thuật phân lớp k-NN „ Mỗi ví dụ học x được biểu diễn bởi 2 thành phần: • Mô tả của ví dụ: x=(x1,x2, ,xn), trong đó xi∈R • Nhãn lớp : c (∈C, với C là tập các nhãn lớp được xác định trước) „ Giai đoạn học • Đơn giản là lưu lại các ví dụ học trong tập học: D = {x} „ Giai đoạn phân lớp: Để phân lớp cho một ví dụ (mới) z • Với mỗi ví dụ học x∈D, tính khoảng cách giữa x và z • Xác định tập NB(z) – các láng giềng gần nhất của z →Gồm k ví d ụ học trong D gầnnhn nhấttv với z tính theo một hàm khoảng cách d • Phân z vào lớp chiếm số đông (the majority class) trong số các lớp của cááídc ví dụ học trong NB(z ) ọ H c Máy – IT 4862 6
4. Một hay nhiều láng giềng gần nhất? „ Việc phân lớp (hay dự đoán) chỉ dựa trên duy nhất một láng giềng gần nhất (là ví dụ học gần nhất với ví dụ cần phân lớp/dự đoán) thường không chính xác • Nếu ví dụ học này là một ví dụ bất thường, không điển hình (an outlier) – rất khác so với các ví dụ khác • Nếu ví dụ học này có nhãn lớp (giá trị đầu ra) sai – do lỗi trong quá trình thu thập (xây dựng) tập dữ liệu „ Thường xét k (>1) các ví dụ học (các láng giềng) gần nhất với ví dụ cần phân lớp/dự đoán „ Đốivi với bài toán phân lớppcó2l có 2 lớp, k thường đượccch chọnnlà là một số lẻ, để tránh cân bằng về tỷ lệ các ví dụ giữa 2 lớp • Ví dụ: k= 3, 5, 7, ọ H c Máy – IT 4862 8
5. Hàm tính khoảngg() cách (2) „ Các hàm tính khoảng cách hình học (Geometry distance functions) n • Hàm Minkowski (p-norm): d(x, z) = ∑ xi − zi i=1 n 2 • Hàm Manhattan ( =1): p d(x, z) = ∑(xi − zi ) i=1 n 1/ p ⎛ p ⎞ • Hàm Euclid (p=2): d(x, z) = ⎜∑ xi − zi ⎟ ⎝ i=1 ⎠ n 1/ p ⎛ p ⎞ • Hàm Chebyshev ( =∞): p d(x, z) = lim⎜ xi − zi ⎟ p→∞ ∑ ⎝ i=1 ⎠ = max xi − zi i ọ H c Máy – IT 4862 10
6. Chuẩn hóa miền giá trị thuộc tính n „ Hàm tính khoảng cách Euclid: 2 d(x, z) = ∑()xi − zi i=1 „ Giả sử mỗivídụđượcbiểudiễnbởi 3 thuộc tính: Age, Income (cho mỗi tháng), và Height (đo theo mét) • x = (Age=20, Income=12000, Height=1.68) • z = (Age=40, Income=1300, Height=1.75) „ Khoảng cách giữa x và z • d(xzx,z) =[(20= [(20-40)2 + (12000 -1300)2 +(168+ (1.68-1. 75)2]1/2 • Giá trị khoảng cách bị quyết định chủ yếubởigiátrị khoảng cách (sự khác biệt) giữa 2 ví dụđốivớithuộc tính Income → Vì: Thuộc tính Income có miền giá trị rất lớn so với các thuộc tính khác „ Cầnphảichuẩn hóa miềngiátrị (đưavề cùng mộtkhoảng giá trị) • Khoảng giá trị [0,1] thường đượcsử dụng • Đối với mỗi thuộc tính i: xi = xi/max_val(fi) ọ H c Máy – IT 4862 12
7. Khoảng cách của các láng giềng (1) „ Xét tập NB(z) –gồm k ví dụ học gần nhấtvt vớivídi ví dụ cần phân lớp/dự đoán z Ví d ụ cần • Mỗi ví dụ (láng giềng gần nhất) này có phân loại z khoảng cách khác nhau đến z • Các láng giềng này có ảnh hưởng như nhau đối với việc phân lớp/dự đoáncho z? → KHÔNG! „ Cần gán các mức độ ảnh hưởng (đóng góp) của mỗi láng giềng gần nhất tùy theo kho ảng cách củaanó nó đến z • Mức độ ảnh hưởng cao hơn cho các láng giềng gần hơn! ọ H c Máy – IT 4862 14
8. Lazy learning vs. Eager learning „ Lazy learning. Việc đánh giá hàm mục tiêu (target function) được hoãn lạichođếnkhixét ví dụ cần phân loại/dựđoán • Đánh giá (xấpxỉ) hàm mụctiêumộtcáchcụcbộ (locally) và riêng rẽ (diferrently) cho mỗivídụ cần phân loại/dựđoán (tạithời điểm phân loại/dựđoán củahệ thống) • Tính tátoánnhiều lầncácxấpxỉ cục bộ của hàmmục tiêu • Thường mấtthờigianlâuhơn để đưarakếtluận (phân lớp/dựđoán), và cần nhiều không gian nhớ hơn • Ví dụ: Nearest neighbor learner, Locally weighted regression „ Eager learning. Việc đánh giá hàm mụctiêuđược hoàn thành trướckhixét đếnbấtkỳ ví dụ cần phân loại/dựđoán • Đánh giá (xấpxỉ) hàm mụctiêumộtcáchtổng thể (globally) đốivới toàn bộ không gian các ví dự (tạithời điểm họccủahệ thống) • Tính toán mộtxấpxỉ duy nhất(ở mứctổng thể) của hàm mụctiêu • Ví dụ: Linear regression, Support vector machines, Neural networks, ọ H c Máy – IT 4862 16