Bài giảng Học máy - Bài 5: Học dựa trên các láng giềng gần nhất - Nguyễn Nhật Quang

Học Máy (IT 4862) ễ hậNguy n N t Quang quangnn-fit@mail.hut.edu.vn Trường Đại học Bách Khoa Hà Nội Viện Công nghệ thông tin và truyền thông Năm học 2011-2012 Nội d ô hung m n ọc: „ Giới thiệu chung „ Đánh giá hiệu năng hệ thống học máy „ Các phương pháp học dựa trên xác suất „ 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 neighbors learning) „ Các phương pháp học không giám sát „ Lọc cộng tác „ Học tăng cường 2 Học Máy – IT 4862 Học dựa trên các láng giềng gần nhất „ Một số tên gọi khác của phương pháp học dựa trên các láng giềng gần nhất (Nearest neighbors learning) • Instance-based learning • Lazy learning • Memory-based learning „ Ý tưởng của phương pháp học dựa trên các láng giềng gần nhất • Với một tập các ví dụ học ─ (Đơn giản là) lưu lại các ví dụ học ─ Chưa xây dựng một mô hình (mô tả) rõ ràng và tổng quát của hàm mục tiêu cần học • Đối với một ví dụ cần phân loại/dự đoán ─ Xét quan hệ giữa ví dụ đó với các ví dụ học để gán giá trị của 3Học Máy – IT 4862 hàm mục tiêu (một nhãn lớp, hoặc một giá trị thực) 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 trong 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 target 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 4Học Máy – IT 4862 Ví dụ bài toán phân lớp Lớp c1 Lớp c2 „ Xét 1 láng giềng gần Ví dụ cần phân lớp z nhất →Gán z vào lớp c2 „ Xét 3 láng giềng gần nhất →Gán z vào lớp c1 „ Xét 5 láng giềng gần nhất →Gán z vào lớp c1 5Học Máy – IT 4862 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ần nhất 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 ủ á í d h t NB( ) 6Học Máy – IT 4862 c a c c v ụ ọc rong z Giải thuật dự đoán 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 • Giá trị đầu ra mong muốn: yx∈R (là một số thự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 „ Giai đoạn dự đoán: Để dự đoán giá trị đầu ra cho ví dụ z • Đối 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ần nhất với z tính theo một hàm khoảng ∑= )(1 NB xz yy cách d • Dự đoán giá trị đầu ra đối với z: 7Machine Learning: Algorithms and Applications ∈ zxk Họ Máy – IT 4862 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 Đối với bài toán phân lớp có 2 lớp k thường được chọn 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, 8Học Máy – IT 4862 Hàm tính khoảng cách (1) „ Hàm tính khoảng cách d • Đóng vai trò rất quan trọng trong phương pháp học dựa trên các láng giềng gần nhất • Thường được xác định trước, và không thay đổi trong suốt quá trình học và phân loại/dự đoán „ Lựa chọn hàm khoảng cách d Cá hà kh ả á h hì h h Dà h h á bài t á ó á• c m o ng c c n ọc: n c o c c o n c c c thuộc tính đầu vào là kiểu số thực (xi∈R) • Hàm khoảng cách Hamming: Dành cho các bài toán có các ầ ể ( { })thuộc tính đ u vào là ki u nhị phân xi∈ 0,1 • Hàm tính độ tương tự Cosine: Dành cho các bài toán phân lớp văn bản (xi là giá trị trọng số TF/IDF của từ khóa thứ i) 9Học Máy – IT 4862 Hàm tính khoảng cách (2) „ Các hàm tính khoảng cách hình học (Geometry distance functions) ∑ = −= n i ii zxzxd 1 ),( n • Hàm Minkowski (p-norm): ( )∑ = −= i ii zxzxd 1 2),( pn p /1 ⎟⎞⎜⎛∑ • Hàm Manhattan (p=1): i ii zxzxd 1 ),( ⎠⎝ −= = pn pd /1 li)( ⎟⎞⎜⎛∑ • Hàm Euclid (p=2): Hàm Chebyshev (p=∞): iii zx −= max i iip zxzx 1 m, ⎠⎝ −= =∞→ • 10Học Máy – IT 4862 Hàm tính khoảng cách (3) ∑= n ii zxDifferencezxd ),(),( „ Hàm khoảng cách Hamming =i 1 ⎩⎨ ⎧ = ≠= )(,0 )(,1 ),( baif baif baDifference • Đối với các thuộc tính đầu vào là kiểu nhị phân ({0,1}) ∑n • Ví dụ: x=(0,1,0,1,1) ∑∑ === nn i ii zx zx zx zxzxd 22 1.),( „ Hàm tính độ tương tự Cosine ố ầ == i i i i 11 • Đ i với đ u vào là một vectơ các giá trị trọng số (TF/IDF) của các từ khóa 11Học Máy – IT 4862 Chuẩn hóa miền giá trị thuộc tính ( )∑ = −= n i ii zxzxd 1 2),(„ Hàm tính khoảng cách Euclid: „ Giả sử mỗi ví dụ được biểu diễn bở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(x z) = [(20-40)2 + (12000-1300)2 + (1 68-1 75)2]1/2, . . • Giá trị khoảng cách bị quyết định chủ yếu bởi giá trị khoảng cách (sự khác biệt) giữa 2 ví dụ đối với thuộ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ần phải chuẩn hóa miền giá trị (đưa về cùng một khoảng giá trị) • Khoảng giá trị [0,1] thường được sử dụng Đối ới ỗi th ộ tí h i / l(f ) 12Học Máy – IT 4862 • v m u c n : xi = xi max_va i Trọng số của các thuộc tính ( )∑ = −= n i ii zxzxd 1 2),(„ Hàm khoảng cách Euclid: • Tất cả các thuộc tính có cùng (như nhau) ảnh hưởng đối với giá trị khoảng cách „ Các thuộc tính khác nhau có thể (nên) có mức độ ảnh hưởng n khác nhau đối với giá trị khoảng cách „ Cần phải tích hợp (đưa vào) các giá trị trọng số của các thuộc tính trong hàm tính khoảng cách ( )∑ = −= i iii zxwzxd 1 2),(•wi là trọng số của thuộc tính i: „ Làm sao để xác định các giá trị trọng số của các thuộc tính? • Dựa trên các tri thức cụ thể của bài toán (vd: được chỉ định bởi các chuyên gia trong lĩnh vực của bài toán đang xét) • Bằng một quá trình tối ưu hóa các giá trị trọng số (vd: sử dụng một tập ể ố ố 13Học Máy – IT 4862 học đ học một bộ các giá trị trọng s t i ưu) Khoảng cách của các láng giềng (1) Ví d ầ „ Xét tập NB(z) – gồm k ví dụ học gần nhất với ví dụ cần phân lớp/dự đoán z ụ c n phân loại z • Mỗi ví dụ (láng giềng gần nhất) này có 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ủa nó đến z • Mức độ ảnh hưởng cao hơn cho các láng giềng gần hơn! 14Học Máy – IT 4862 Khoảng cách của các láng giềng (2) „ Gọi v là hàm xác định trọng số theo khoảng cách • Đối với một giá trị d(x,z) – khoảng cách giữa x và z tỷ lệ hị h ới ∑ ∈∈ = )( ))(,().,(maxarg)( zNBx j Cc xccIdenticalzxvzc j ⎧ •v(x,z) ng c v d(x,z) „ Đối với bài toán phân lớp: ⎩⎨ ≠ == )(,0 )(,1 ),( baif baif baIdentical ∑ )().,( xfzxv ∑ ∈ ∈= )( )( ),( )( zNBx zNBx zxv zf„ Đối với bài toán dự đoán (hồi quy): )( 1),( zxd zxv += α 2)]([ 1),( zxd zxv += α 2 2),( ),( σ zxd ezxv −= „ Lựa chọn một hàm xác định trọng số theo khoảng cách: , , 15Học Máy – IT 4862 Lazy learning vs. Eager learning „ Lazy learning. Việc đánh giá hàm mục tiêu (target function) được hoãn lại cho đến khi xét ví dụ cần phân loại/dự đoán • Đánh giá (xấp xỉ) hàm mục tiêu một cách cục bộ (locally) và riêng rẽ (diferrently) cho mỗi ví dụ cần phân loại/dự đoán (tại thời điểm phân loại/dự đoán của hệ thống) Tí h t á hiề lầ á ấ ỉ bộ ủ hà tiê• n o n n u n c c x p x cục c a m mục u • Thường mất thời gian lâu hơn để đưa ra kết luậ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ục tiêu được hoàn thành trước khi xét đến bất kỳ ví dụ cần phân loại/dự đoán • Đánh giá (xấp xỉ) hàm mục tiêu một cách tổng thể (globally) đối với toàn bộ không gian các ví dự (tại thời điểm học của hệ thống) • Tính toán một xấp xỉ duy nhất (ở mức tổng thể) của hàm mục tiêu 16Học Máy – IT 4862 • Ví dụ: Linear regression, Support vector machines, Neural networks, ... k-NN – Khi nào? „ Các ví dụ được biểu diễn trong không gian vectơ Rn „ Số lượng các thuộc tính (để biểu diễn ví dụ) là không nhiều „ Một tập học có kích thước lớn „ Các ưu điểm Chi hí thấ h á t ì h h ấ l ệ ( hỉ iệ l l i á í d h )• p p c o qu r n u n uy n c v c ưu ạ c c v ụ ọc • Hoạt động tốt với các bài toán phân loại gồm nhiều lớp → Không cần phải học n bộ phân loại cho n lớp • Phương pháp học k-NN (k >>1) có khả năng xử lý nhiễu cao → Phân loại/dự đoán được thực hiện dựa trên k láng giềng gần nhất „ Các nhược điểm • Phải lựa chọn hàm tính khoảng cách (sự khác biệt) thích hợp với bài toán • Chi phí tính toán (thời gian, bộ nhớ) cao tại thời điểm phân loại/dự đoán • Có thể cho kết quả kém/sai với các thuộc tính không liên quan 17Học Máy – IT 4862