L0-intro-đã gộp.pdf

1 Nhập môn Học máy và Khai phá dữ liệu (IT3190) 2 Cấu trúc môn học Số tuần: 15 Lý thuyết: 11-13 tuần Sinh viên trình bày đồ án môn học: 02-03 tuần Thời gian và địa điểm Thời gian gặp sinh viên Hẹn trước qua e-mail Viện CNTT&TT, Nhà B1 3 Nội dung môn học Lecture 1: Giới thiệu về Học máy và khai phá dữ liệu Lecture 2: Thu thập và tiền xử lý dữ liệu Lecture 3: Hồi quy tuyến tính (Linear regression) Lecture 4+5: Phân cụm Lecture 6: Phân loại và Đánh giá hiệu năng Lecture 7: dựa trên láng giềng gần nhất (KNN) Lecture 8: Cây quyết định và Rừng ngẫu nhiên Lecture 9: Học dựa trên xác suất Lecture 10: Mạng nơron (Neural networks) Lecture 11: Máy vector hỗ trợ (SVM) Lecture 12: Khai phá tập mục thường xuyên và các luật kết hợp Lecture 13: Thảo luận ứng dụng học máy và khai phá dữ liệu trong thực tế 4 Mục tiêu của môn học Có kiến thức cơ bản về học máy Có hiểu biết về các phương pháp học máy, các điểm mạnh (ưu điểm) và các điểm yếu (nhược điểm) của các giải thuật học máy và khai phá dữ liệu Làm quen và sử dụng được thư viện Scikit-learn Có kinh nghiệm về thiết kế, cài đặt, và đánh giá hiệu năng của một phương pháp học máy hoặc khai phá dữ liệu Thông qua đồ án môn học 5 Đánh giá Đồ án môn học (P): Tối đa 10 điểm Mỗi đồ án được thực hiện bởi một nhóm sinh viên Chọn một phương pháp học máy được giới thiệu trong môn học để giải quyết một bài toán thực tế Cài đặt và đánh giá hiệu năng của phương pháp đó dựa trên dữ liệu thực tế Thi viết (E): Tối đa 10 điểm Điểm học phần (G) G = 0,4 x P + 0,6 x E 6 Đồ án môn học: đề tài Tự do đề xuất bài toán thực tế, (các) giải thuật học máy để giải quyết bài toán, và (các) tập dữ liệu được sử dụng Đề xuất đề tài phải được diễn giải cụ thể Mô tả bài toán thực tế sẽ được giải quyết (mục đích, yêu cầu, kịch bản ứng dụng, …) Xác định rõ giải thuật học máy dùng để giải quyết bài toán. Trình bày các thông tin về đầu vào (input) và đầu ra (output) của hệ thống học máy sẽ được cài đặt, và cách thức biểu diễn dữ liệu. Xác định rõ (các) tập dữ liệu (datasets) sẽ được sử dụng. 7 Đồ án môn học: các yêu cầu Kết quả của đồ án phải được trình bày ở cuối môn học Tất cả các thành viên phải tham gia vào việc thực hiện và trình bày đồ án Báo cáo kết quả của đồ án bao gồm: Mã nguồn (source codes): lưu trong một file nén File hướng dẫn (readme.txt) mô tả chi tiết cách thức cài đặt/biên dịch/chạy chương trình (và các gói phần mềm được sử dụng kèm theo) Tài liệu báo cáo kết quả đồ án mô học (lưu trong file.pdf): - Giới thiệu và mô tả về bài toán thực tế được giải quyết - Các chi tiết của (các) phương pháp học máy và (các) tập dữ liệu được sử dụng - Các kết quả thí nghiệm đánh giá hiệu năng của hệ thống học máy đối với (các) tập dữ liệu được sử dụng - Các chức năng chính của hệ thống (và cách sử dụng) - Cấu trúc của mã nguồn chương trình, vai trò của các lớp (classes) và các phương thức (methods) chính/quan trọng - Các vấn đề/khó khăn gặp phải trong quá trình thực hiện công việc của đồ án, và cách thức được dùng để giải quyết (vượt qua) - Các khám phá mới hoặc kết luận 8 Đồ án môn học: đánh giá Công việc đồ án được đánh giá theo các tiêu chí sau: Mức độ phức tạp / khó khăn của bài toán thực tế được giải quyết Chất lượng (sự đúng đắn và phù hợp) của phương pháp được dùng để giải quyết bài toán Đánh giá và lựa chọn kỹ lưỡng mô hình Chất lượng của bài trình bày (presentation) kết quả đồ án Chất lượng của tài liệu báo cáo kết quả đồ án Cài đặt hệ thống thử nghiệm (các chức năng, dễ sử dụng, …) Bài trình bày trong khoảng 15 phút, và phù hợp với những gì được nêu trong tài liệu báo cáo Nếu sử dụng lại / kế thừa / khai thác các mã nguồn / các gói phần mềm / các công cụ sẵn có, thì phải nêu rõ ràng và chính xác trong tài liệu báo cáo (và đề cập trong bài trình bày) 9 Tài liệu học tập Các bài giảng trên lớp (Lecture slides) Sách tham khảo: T. M. Mitchell. Machine Learning. McGraw-Hill, 1997. Trevor Hastie, Robert Tibshirani, Jerome Friedman. The Elements of Statistical Learning. Springer, 2009. Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT press, 2016. E. Alpaydin. Introduction to Machine Learning. MIT press, 2020. Jiawei Han, Micheline Kamber, Jian Pei. Data Mining: Concepts and Techniques (3rd Edition). Morgan Kaufmann, 2011. Công cụ phần mềm: Scikit-learn (http://scikit-learn.org/) WEKA (http://www.cs.waikato.ac.nz/ml/weka/) Các tập dữ liệu (datasets): UCI repository: http://archive.ics.uci.edu/ml/ 10 Thư viện hoặc ngôn ngữ Thank you for your attentions! 1 Nhập môn Học máy và Khai phá dữ liệu (IT3190) 2 Nội dung môn học Lecture 1: Giới thiệu về Học máy và khai phá dữ liệu Lecture 2: Thu thập và tiền xử lý dữ liệu Lecture 3: Hồi quy tuyến tính (Linear regression) Lecture 4+5: Phân cụm Lecture 6: Phân loại và Đánh giá hiệu năng Lecture 7: dựa trên láng giềng gần nhất (KNN) Lecture 8: Cây quyết định và Rừng ngẫu nhiên Lecture 9: Học dựa trên xác suất Lecture 10: Mạng nơron (Neural networks) Lecture 11: Máy vector hỗ trợ (SVM) Lecture 12: Khai phá tập mục thường xuyên và các luật kết hợp Lecture 13: Thảo luận ứng dụng học máy và khai phá dữ liệu trong thực tế 3 Tại sao nên biết Học Máy & Khai phá dữ liệu? “The most important general-purpose technology of our era is artificial intelligence, particularly machine learning” – Harvard Business Review https://hbr.org/cover-story/2017/07/the-business-of-artificial-intelligence Nhu cầu lớn về Data Science “Data scientist: the sexiest job of the 21st century” – Harvard Business Review. http://hbr.org/2012/10/data-scientist-the-sexiest-job-of-the-21st-century/ “The Age of Big Data” – The New York Times http://www.nytimes.com/2012/02/12/sunday-review/big-datas-impact-in-the- world.html?pagewanted=all&_r=0 4 Tại sao? Industry 4.0 https://www.pwc.com/ca/en/industries/industry-4-0.html 5 Tại sao? AI & DS & Industry 4.0 Artificial Intelligence Machine Learning Industry 4.0 Data Science 6 Vài thành công: IBM’s Watson Application IBM's Watson Supercomputer © Data Destroys Science Laboratory, Humans SOICT, in Jeopardy (2011) HUST, 2017 7 Vài thành công: Amazon’s secret “The company reported a 29% sales increase to $12.83 billion during its second fiscal quarter, up from $9.9 billion during the same time last year.” – Fortune, July 30, 2012 8 Vài thành công: GAN (2014)  Tạo Trí tưởng tượng (Imagination) Ian Goodfellow Artificial faces Goodfellow, Ian, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. "Generative adversarial nets." In NIPS, pp. 2672-2680. 2014. 9 Vài thành công: AlphaGo (2016) http://www.wired.com/2016/01/in-a-huge-breakthrough-googles-ai-beats-a-top-player-at-the-game-of-go/ 10 Học máy -- Khai phá dữ liệu Machine Learning  Data Mining (ML - Học máy) (DM - Khai phá dữ liệu) To build computer systems that can To find new and useful knowledge improve themselves by learning from datasets. from data. (Xây dựng những hệ thống mà (Tìm ra/Khai phá những tri thức có khả năng tự cải thiện bản mới và hữu dụng từ các tập dữ thân bằng cách học từ dữ liệu.) liệu lớn.) Some venues: NeurIPS, ICML, IJCAI, AAAI, ICLR, ACML, ECML  Some venues: KDD, PKDD, PAKDD, ICDM, CIKM 11 Dữ liệu Phi cấu trúc Có cấu trúc – relational (table-like) texts in websites, emails, articles, tweets 2D/3D images, videos + meta spectrograms, DNAs, … 12 Quy trình thực hiện: hướng tìm tri thức Data Analysis, Insight & Data Data vizualization hypothesis processing & testing, & Policy collection Grasping ML Decision 70-90% tổng thời gian (John Dickerson, University of Maryland) 13 Quy trình thực hiện: hướng sản phẩm Business Analytic understanding approach Data Feedback requirements Data Deployment collection Data Evaluation understanding Data Modeling preparation 14 (http://www.theta.co.nz/) Phát triển sản phẩm: kinh nghiệm từ IBM IBM Research DeepQA: Incremental Progress in Answering Precision on Application the Jeopardy Challenge: 6/2007-11/2010 IBM Watson Playing in the Winners Cloud 100% 90% v0.8 11/10 80% V0.7 04/10 70% v0.6 10/09 v0.5 05/09 60% Precision v0.4 12/08 50% v0.3 08/08 v0.2 05/08 40% v0.1 12/07 30% 20% 10% Baseline 12/06 0% 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% © Data Science % Laboratory, Answered SOICT, HUST, 2017 15 Machine Learning? Học máy (ML - Machine Learning) là một lĩnh vực nghiên cứu của Trí tuệ nhân tạo (Artificial Intelligence) Câu hỏi trung tâm của ML: [Mitchell, 2006]  How can we build computer systems that automatically improve with experience, and what are the fundamental laws that govern all learning processes? Vài quan điểm về học máy:  Build systems that automatically improve their performance [Simon, 1983].  Program computers to optimize a performance objective at some task, based on data and past experience [Alpaydin, 2020] 16 Máy học Ta nói một máy tính có khả năng học nếu nó tự cải thiện hiệu suất hoạt động P cho một công việc T cụ thể, dựa vào kinh nghiệm E của nó. Như vậy một bài toán học máy có thể biểu diễn bằng 1 bộ (T, P, E) T: một công việc (nhiệm vụ) P: tiêu chí đánh giá hiệu năng E: kinh nghiệm 17 Ví dụ thực tế (1) Lọc thư rác (email spam filtering) T: Dự đoán (để lọc) những thư điện tử nào là thư rác (spam email) P: số lượng thư điện tử gửi đến được phân loại chính xác E: Một tập các thư điện tử (emails) mẫu, mỗi thư điện tử được biểu diễn bằng một Spam? tập thuộc tính (vd: tập từ khóa) và nhãn lớp (thư thường/thư rác) tương ứng No Yes 18 Ví dụ thực tế (2) Gán nhãn ảnh ◼ T: đưa ra một vài mô tả ý nghĩa của 1 bức ảnh ◼ P: ? ◼ E: Một tập các bức ảnh, trong đó mỗi ảnh đã được gán một tập các từ mô tả ý nghĩa của chúng 19 Máy học gì?  Học một ánh xạ (hàm): x: quan sát (dữ liệu), kinh nghiệm y: phán đoán, tri thức mới, kinh nghiệm mới, …  Hồi quy (regression): nếu y là một số thực  Phân loại (classification): nếu y thuộc một tập rời rạc (tập nhãn lớp) Anh ta thích nghe + →Trẻ hay Già? 20 Máy học từ đâu?  Học từ đâu?  Từ các quan sát trong quá khứ (tập học – training data set). {{x1, x2, …, xN}; {y1, y2,…, yM}}  xi là các quan sát của x trong quá khứ  yh là nhãn (label) hoặc phản hồi (response) hoặc đầu ra (output) tương ứng với xh.  Sau khi đã học:  Thu được một mô hình, kinh nghiệm, tri thức mới (f).  Dùng nó để suy diễn (infer) hoặc phán đoán (predict) cho quan sát trong tương lai. yz = f(z) 21 Hai bài toán học cơ bản  Học có giám sát (supervised learning): cần học một hàm y = f(x) từ tập học {{x1, x2, …, xN}; {y1, y2,…, yN}} sao cho yi  f(xi).  Phân loại (phân lớp): nếu y chỉ nhận giá trị từ một tập rời rạc, chẳng hạn {cá, cây, quả, mèo}  Hồi quy: nếu y nhận giá trị số thực  Học không giám sát (unsupervised learning): cần học một hàm y = f(x) từ tập học cho trước {x1, x2, …, xN}.  Y có thể là các cụm dữ liệu.  Y có thể là các cấu trúc ẩn.  Học bán giám sát (semi-supervised learning)? 22 Supervised learning: Phân loại Multi-class classification (phân loại nhiều lớp): when the output y is one of the pre-defined labels {c1, c2, …, cL} (mỗi đầu ra chỉ thuộc 1 lớp, mỗi quan sát x chỉ có 1 nhãn)  Spam filtering: y in {spam, normal}  Financial risk estimation: y in {high, normal, no}  Discovery of network attacks: ? Multi-label classification (phân loại đa nhãn): when the output y is a subset of labels (mỗi đầu ra là một tập nhỏ các lớp; mỗi quan sát x có thể có nhiều nhãn)  Image tagging: y = {birds, nest, tree}  sentiment analysis 23 Supervised learning: Hồi quy Phán đoán chỉ số chứng khoán 24 Unsupervised learning: ví dụ (1) Gom nhóm dữ liệu vào các cụm (Clustering)  Discover the data groups/clusters Phát hiện cộng đồng  Detect communities in online social networks 25 Unsupervised learning: ví dụ (2) Trends detection  Discover the trends, demands, future needs of online users 26 Thiết kế một hệ thống học (1) Một số vấn đề quan trọng cần được xem xét kỹ Lựa chọn tập học (training examples/data):  Tập học có ảnh hưởng lớn đến hiệu quả của hệ thống học.  Liệu ta có thu thập được nhãn cho dữ liệu huấn luyện?  Các ví dụ học nên tương thích với (đại diện cho) các ví dụ sẽ được làm việc bởi hệ thống trong tương lai (future test examples) Xác định được bài toán học máy nào? Business Analytic understanding approach  Phân loại? F: X → {0,1} Data Feedback requirements  Hồi quy? F: X → R  Phân cụm? Deployment Data collection Data Evaluation understanding Data Modeling 27 preparation Thiết kế một hệ thống học (2)  Lựa chọn cách biểu diễn cho hàm mục tiêu cần học Hàm đa thức (a polynomial function) Một tập các luật (a set of rules) Một cây quyết định (a decision tree) Một mạng nơ-ron nhân tạo (an artificial neural network) …  Lựa chọn một giải thuật học máy có thể học (xấp xỉ) được hàm mục tiêu Business understanding Analytic approach Hồi quy Ridge? Data Feedback requirements Back-propagation? SGD? Deployment Data collection Data Evaluation understanding Data Modeling 28 preparation Vài vấn đề trong Học máy (1) ◼ Giải thuật học máy (Learning algorithm) Những giải thuật học máy nào có thể học (xấp xỉ) một hàm mục tiêu cần học? Với những điều kiện nào, một giải thuật học máy đã chọn sẽ hội tụ (tiệm cận) đến hàm mục tiêu cần học? Đối với một lĩnh vực cụ thể và đối với một cách biểu diễn các ví dụ (đối tượng) cụ thể, giải thuật học máy nào thực hiện tốt nhất? ◼ No-free-lunch theorem [Wolpert and Macready, 1997]: If an algorithm performs well on a certain class of problems then it necessarily pays for that with degraded performance on the set of all remaining problems. ❖ No algorithm can beat another on all domains. (không có thuật toán nào luôn hiệu quả nhất trên mọi miền ứng dụng) 29 Vài vấn đề trong Học máy (2)  Các ví dụ học (Training examples) Bao nhiêu ví dụ học là đủ? Kích thước của tập học (tập huấn luyện) ảnh hưởng thế nào đối với độ chính xác của hàm mục tiêu học được? Các ví dụ lỗi (nhiễu) và/hoặc các ví dụ thiếu giá trị thuộc tính (missing-value) ảnh hưởng thế nào đối với độ chính xác? 30 Vài vấn đề trong Học máy (3) ◼ Quá trình học (Learning process) Chiến lược tối ưu cho việc lựa chọn thứ tự sử dụng (khai thác) các ví dụ học? Các chiến lược lựa chọn này làm thay đổi mức độ phức tạp của bài toán học máy như thế nào? Các tri thức cụ thể của bài toán (ngoài các ví dụ học) có thể đóng góp thế nào đối với quá trình học? 31 Vài vấn đề trong Học máy (4)  Khả năng/giới hạn học (Learnability) Hàm mục tiêu nào mà hệ thống cần học?  Biểu diễn hàm mục tiêu: Khả năng biểu diễn (vd: hàm tuyến tính / hàm phi tuyến) vs. Độ phức tạp của giải thuật và quá trình học Các giới hạn đối với khả năng học của các giải thuật học máy? Khả năng Tổng quát hóa (generalization) của hệ thống?  Để tránh vấn đề “overfitting” (đạt độ chính xác cao trên tập học, nhưng đạt độ chính xác thấp trên tập thử nghiệm) Khả năng hệ thống tự động thay đổi (thích nghi) biểu diễn (cấu trúc) bên trong của nó?  Để cải thiện khả năng (của hệ thống đối với việc) biểu diễn và học hàm mục tiêu 32 Overfitting (quá khớp, quá khít) Hàm h được gọi là overfitting nếu tồn tại hàm g mà:  g có thể tồi hơn h đối với tập huấn luyện,  nhưng g tốt hơn h đối với dữ liệu tương lai. A learning algorithm is said to overfit relative to another one if it is more accurate in fitting known data, but less accurate in predicting unseen data. Vài nguyên nhân gây ra Overfitting:  Hàm h quá phức tạp  Lỗi (nhiễu) trong tập huấn luyện (do quá trình thu thập/xây dựng tập dữ liệu)  Số lượng các ví dụ học quá nhỏ, không đại diện cho toàn bộ tập (phân bố) của các ví dụ của bài toán học 33 Vấn đề overfitting: minh hoạ Test error Error Training error Underfitting Good model Overfitting Simple Good Too complex (Học không đến (Học vẹt?) nơi đến chốn) 34 Overfitting: ví dụ Khi tăng cỡ lớn của một Cây quyết định thì chất lượng phán đoán của nó có thể giảm dần, mặc dù độ chính xác trên tập huấn luyện tăng dần [Mitchell, 1997] 35 Overfitting: Regularization Trong số rất nhiều hàm thì hàm nào có khả năng tổng quát cao nhất khi học từ tập dữ lieu cho trước? f(x)  Tổng quát hoá là mục tiêu chính của học máy.  Tức là, khả năng phán đoán tốt với dữ liệu tương lai. Regularization: cách dùng phổ biến  Là cách hạn chế không gian chứa hàm f. x 36 (http://towardsdatascience.com/multitask-learning-teach-your-ai-more-to-make-it-better-dde116c2cd40) Tài liệu tham khảo Alpaydin E. (2020). Introduction to Machine Learning. The MIT Press. Mitchell, T. M. (1997). Machine learning. McGraw Hill. Mitchell, T. M. (2006). The discipline of machine learning. Carnegie Mellon University, School of Computer Science, Machine Learning Department. Simon H.A. (1983). Why Should Machines Learn? In R. S. Michalski, J. Carbonell, and T. M. Mitchell (Eds.): Machine learning: An artificial intelligence approach, chapter 2, pp. 25-38. Morgan Kaufmann. Wolpert, D.H., Macready, W.G. (1997), "No Free Lunch Theorems for Optimization", IEEE Transactions on Evolutionary Computation 1, 67. 37 Thank you for your attentions! 1 Nhập môn Học máy và Khai phá dữ liệu (IT3190) 2 Nội dung môn học Lecture 1: Giới thiệu về Học máy và khai phá dữ liệu Lecture 2: Thu thập và tiền xử lý dữ liệu Lecture 3: Hồi quy tuyến tính (Linear regression) Lecture 4+5: Phân cụm Lecture 6: Phân loại và Đánh giá hiệu năng Lecture 7: dựa trên láng giềng gần nhất (KNN) Lecture 8: Cây quyết định và Rừng ngẫu nhiên Lecture 9: Học dựa trên xác suất Lecture 10: Mạng nơron (Neural networks) Lecture 11: Máy vector hỗ trợ (SVM) Lecture 12: Khai phá tập mục thường xuyên và các luật kết hợp Lecture 13: Thảo luận ứng dụng trong thực tế 3 Nguồn dữ liệu 4 Khai phá dữ liệu - Dự đoán Google Flu Trends: phát hiện các đợt bùng phát trước dữ liệu CDC hai tuần 5 Khai phá dữ liệu - Khám phá Subscribers in Youtube Views in Youtube H1 (TH Hanoi) 39,298 H1 (TH Hanoi) 22,002,049 HTV Entertainment 700,866 HTV Entertainment 589,368,537 VTV Go 841,629 VTV Go 372,993,993 VTC1 Tin Tuc 696,709 VTC1 Tin Tuc 980,345,169 THVL Giai Tri 1,032,878 THVL Giai Tri 1,088,750,732 THVL 1,350,236 THVL 1,542,390,919 Kênh truyền hình hiệu quả? Videos in Youtube Attractiveness 6% THVL 13% 18% THVL Giai Tri VTC1 Tin Tuc 9% 12% VTV Go HTV Entertainment 42% H1 (TH Hanoi) 6 Khai phá dữ liệu Dữ liệu giúp mọi thứ rõ ràng hơn Searches for “Facebook” (John Canny, UC Berkeley) 7 Phát hiện tri thức và Khai phá dữ liệu The automatic extraction of non- obvious, hidden knowledge from large volumes of data (tự động trích rút những tri thức ẩn, không tường minh từ dữ liệu lớn) 8 Khái niệm dữ liệu Dữ liệu chỉ là dữ kiện thô (Long and Long, 1998) Dữ liệu… là các luồng dữ kiện thô biểu diễn các sự kiện… trước khi chúng được sắp xếp thành một dạng mà mọi người có thể hiểu và sử dụng (Laudon and Laudon, 1998) Dữ liệu bao gồm các dữ kiện (Hayes, 1992), các ký hiệu được ghi lại (McNurlin và Sprague, 1998) Dữ liệu là tín hiệu (signals) thu được do quan sát, đo đạc, thu thập... từ các đối tượng. Cụ thể, dữ liệu là giá trị (values) của các thuộc tính (features) của các đối tượng, được biểu diễn bằng dãy các bits, các con số hay ký hiệu... Data 9 Khái niệm thông tin Dữ liệu đã được đưa về một dạng có ý nghĩa và hữu ích đối với con người (Laudon and Laudon, 1998) Dữ liệu đã được thu thập và xử lý thành một dạng có ý nghĩa. Đơn giản, thông tin là ý nghĩa mà chúng ta cung cấp cho các dữ kiện tích lũy (Long and Long, 1998) Thông tin là dữ liệu có ý nghĩa (data equiped with meaning), thu Information được khi xử lý dữ liệu để lọc bỏ đi các phần dư thừa, tìm ra phần cốt lõi đặc trưng cho dữ liệu. Data 10 Khái niệm tri thức Kết quả của sự hiểu biết thông tin (Hayes, 1992) Kết quả của việc ngấm thông tin (Hayes, 1992), Thông tin thu thập về một lĩnh vực quan tâm (Senn, 1990) Thông tin có định hướng hoặc ý định, nó giúp hỗ trợ cho một quyết định hoặc một hành động (Zachman, 1987) Knowledge Tri thức là thông tin tích hợp, như Information quan hệ giữa các sự kiện, giữa các thông tin... thu được qua quá trình nhận thức, phát hiện hoặc học tập. Data 11 Dữ liệu – thông tin – tri thức Tri thức về các tri thức VD: khi nào áp dụng, áp dụng như thế nào Hiểu biết về một lĩnh Meta- vực nào đó, có thể dùng Knowledge để giải quyết các vấn đề Knowledge Kích thước nhỏ hơn, giá trị cao hơn với một Information số ý nghĩa nhất định Data Kích thước lớn, giá trị thấp, thường không rõ ý nghĩa 12 Ví dụ dữ liệu/thông tin/tri thức Dữ liệu Trời nhiệt độ là 5𝑜 𝐶 Thông tin Ngoài trời lạnh quá Tri thức Nếu trời lạnh, bạn nên mặc áo ấm khi đi ra ngoài Giá trị cảm nhận của dữ liệu tăng lên khi nó được chuyển thành kiến thức. Kiến thức giúp đưa ra các quyết định hữu ích 13 KDD: tác vụ chính Tiên đoán (predictive task): đưa ra dự đoán về những sự kiện chưa biết trong tương lai và tìm ra lý do đằng sau những sự kiện đó Tri thức nào giúp ta phân biệt được Phân loại tế bào ung thư? Hồi quy Mô tả (descriptive task): phân tích các đặc trưng của dữ liệu để thu được thông tin mới hoặc cho mục đích hữu ích nào đó Phân cụm Khai phá luật kết hợp Thói quen nghe nhạc trực tuyến ra sao? 14 Tiên đoán: Phân lớp Đoán xem một quan sát x sẽ được cho vào lớp nào “Những người đứng đầu Barcelona có vẻ hài lòng với điều này” → Tích cực hay Tiêu cực? Những người thích nghe + -> Có phải người trẻ hay không 15 Tiên đoán: Phát hiện ngoại lai Ngoại lai: ngoại lai là một đối tượng mà có khác biệt rất lớn với các đối tượng thông thường, tưởng chừng như nó được sinh ra bởi một cơ chế hoàn toàn khác Một thanh toán tín dụng bất thường Tấn công mạng Giá cổ phiếu bất thường Các điểm ngoại lai thường thú vị: Nó vi phạm các cơ chế sinh dữ liệu thông thường Khác với nhiễu Nhiệm vụ của chúng ta là phát hiện các ngoại lai này (outlier detection, anomaly detection) 16 Khai phá mô tả: Phân cụm Cụm: Nhóm dữ liệu có cùng đặc trưng nào đó Một nhóm người yêu thích nhảy Phân cụm (Clustering): tìm tất cả các cụm trong một tập dữ liệu cho trước. 17 Khai phá mô tả: Tóm tắt Tìm kiếm mô tả ngắn gọn cho tập dữ liệu VD: Tính toán trung bình và phương sai dữ liệu VD: tổng hợp tin tức Chúng ta hay viện dẫn câu chuyện thành công của học sinh Việt Nam trong các kì thi toán quốc tế để chứng minh cho năng lực học toán ở đẳng cấp thế giới của người Việt. Đấy là do cách truyền thông của ta mà thôi. Đây không chỉ là một định kiến mà còn là một sự huyễn hoặc nguy hiểm. 18 Khai phá mô tả: Mô hình phụ thuộc Tìm kiếm mô hình mà nó mô tả những phụ thuộc có ý nghĩa giữa các biến Mức cấu trúc: Biến cục bộ phụ thuộc vào nhau như thế nào Mức định lượng: độ mạnh của các phụ thuộc vào một số. 19 KDD: Kiểu dữ liệu Supervised (có giám sát, có nhãn): Mỗi quan sát x trong tập huấn luyện sẽ có một đầu ra (nhãn) Mục đích là để dự đoán kết quả đầu ra cho một quan sát mới Bát, (x = “Những người đứng đầu Barcelona Thìa, có vẻ hài lòng với điều này”, y = Positive) ramen Unsupervised (không giám sát, không nhãn): chúng ta không thể quan sát bất kỳ đầu ra y nào VD: dòng tweets -> xu hướng hiện tại? Một số tác vụ có thể có meta-data như tag, likes, links, views,… Những meta-data đó có thể giúp khám phá thêm kiến thức mới. 20 KDD: Kiểu dữ liệu Có cấu trúc Phi cấu trúc texts in websites, emails, articles, tweets 2D/3D images, videos + meta spectrograms, DNAs, … 21 KDD: Phương pháp có thể chiếm 70-90% lượng công sức và cho phí bỏ ra Sử dụng các phương (Fayyad, Piatetsky-Shapiro, & Smyth, 1996) pháp để tạo ra các tri thức hữu ích 22 The KDD: Phương KDD process pháp Data organized by function 1 Create/select target database Data warehousing Select sampling technique and sample data Supply missing Eliminate 2 values noisy data Normalize Transform Create derived Find important attributes & values values attributes value ranges 3 Select DM Select DM Extract Test Refine task (s) method (s) knowledge knowledge knowledge 4 Transform to Query & report generation different Aggregation & sequences 5 representation Advanced methods 32 23 KDD: Thách thức 24 Thách thức: phi cấu trúc Các dữ liệu phi cấu trúc phát triển và gia tăng rất nhanh Text, ảnh, tags, links, likes, … 25 Thách thức: tương tác ẩn Những mối tương tác ẩn chứa bên trong dữ liệu có thể rất lớn 26 Thách thức: số chiều quá lớn Các bài toán thực tế thường có số chiều rất lớn Xe đạp chạy: 2 chiều (một con đường) Chúng ta đang sống: 4 chiều Nhưng một hình ảnh 1024 × 1024: ~ 1 triệu chiều Bộ sưu tập văn bản: hang triệu chiều Hệ thống của người đề xuất: hang tỷ chiều (mặt hàng/sản phẩm) Lời nguyền của số chiều không gian (The curse of dimensionality) Dữ liệu dù thu thập được lớn đến đâu thì cũng là quá nhỏ so với không gian của chúng 27 Tài liệu tham khảo L. Duan, Y. Xiong. Big data analytics and business analytics. Journal of Management Analytics, vol 2 (2), pp 1-21, 2015. X. Wu, X. Zhu, G. Wu, W. Ding. Data mining with Big Data. IEEE Transactions on Knowledge and Data Engineering, vol 26 (1), pp 97-107, 2014. Vasant Dhar. Data Science and Prediction. Communication of the ACM, vol 56 (12), pp 64-73, 2013. Fayyad, Usama, Gregory Piatetsky-Shapiro, and Padhraic Smyth. "From data mining to knowledge discovery in databases." AI magazine 17, no. 3 (1996). R. Hayes. The Measurement of Information. In Vakkari, P. and Cronin, B. (editors): Conceptions of Library and Information Science, pp. 97–108. Taylor Graham, 1992. K. C. Laudon and J. P. Laudon. Management Information Systems: New Approaches to Organisation and Technology (5th edition). Prentice-Hall, 1998. L. Long and N. Long. Computers (5th edition). Prentice-Hall, 1998. B. McNurlin and R. H. Sprague. Information Systems Management in Practice (4th edition). Prentice-Hall, 1998. J. Zachman. A Framework for Information Systems Architecture. IBM Systems Journal, 26(3): 276–292, 1987. 28 Thank you for your attentions ! Nhập môn Học máy và Khai phá dữ liệu (IT3190) 2 Nội dung môn học Lecture 1: Giới thiệu về Học máy và khai phá dữ liệu Lecture 2: Thu thập và tiền xử lý dữ liệu Lecture 3: Hồi quy tuyến tính (Linear regression) Lecture 4+5: Phân cụm Lecture 6: Phân loại và Đánh giá hiệu năng Lecture 7: dựa trên láng giềng gần nhất (KNN) Lecture 8: Cây quyết định và Rừng ngẫu nhiên Lecture 9: Học dựa trên xác suất Lecture 10: Mạng nơron (Neural networks) Lecture 11: Máy vector hỗ trợ (SVM) Lecture 12: Khai phá tập mục thường xuyên và các luật kết hợp Lecture 13: Thảo luận ứng dụng trong thực tế 3 ĐẶT VẤN ĐỀ Khai phá dữ liệu là một qúa trình phân tích dữ liệu theo nhiều khía cạnh và tổng hợp nó lại để có được thông tin hữu ích hay tri thức. ĐẶT VẤN ĐỀ Các bước của quá trình phát hiện tri thức gồm 1. Thu thập, lựa chọn dữ liệu 2. Tiền xử lý dữ liệu 3. Chuyển đổi 4. Khai phá dữ liệu 5. Giải thích/Đánh giá ĐẶT VẤN ĐỀ Vì sao phải tiền xử lý dữ liệu ? Không đầy đủ (Incomplete) : thiếu một vài giá trị thuộc tính.... Nhiễu (Noisy) : xuất hiện giá trị lỗi, lỗi chủ quan người nhập dữ liệu.... Không nhất quán (Inconsistent) : sự khác biệt trong cách phân loại, phân biệt hay đơn vị của dữ liệu... ĐẶT VẤN ĐỀ Quy trình tiền xử lý dữ liệu 1. Làm sạch : Loại bỏ các giá trị sai, kiểm tra tính nhất quan của dữ liệu. 2. Tích hợp : Dữ liệu có nhiều nguồn nên cần lưu theo một cách thức thống nhất. 3. Chuyển đổi : Chuẩn hóa và tập hợp dữ liệu. 4. Giảm chiều : Mô tả dữ liệu trong kích thước nhỏ nhưng không làm mất kết quả cần kiết xuất. ĐẶT VẤN ĐỀ Quy trình tiền xử lý dữ liệu MỤC LỤC Đặt vấn đề Làm sạch dữ liệu Tích hợp Giảm chiều LÀM SẠCH DỮ LIỆU Đây là thủ tục quan trọng gồm ba bước chính 1. Điền đầy các giá trị bị mất 2. Chuốt dữ liệu để loại nhiễu 3. Kiểm tra và sửa tính không nhất quán LÀM SẠCH DỮ LIỆU Bước 1: Điền đầy các giá trị bị mất, có thể chọn một trong các phương pháp Bỏ không xét đến bộ dữ liệu bị mất giá trị Điền lại giá trị bằng tay Gán cho giá trị nhãn đặc biệt hay ngoài khoảng biểu diễn Gán giá trị trung bình cho nó. Gán giá trị trung bình của các mẫu khác thuộc cùng lớp đó. Tìm giá trị có xác suất lớn nhất điền vào chỗ bị mất (hồi quy, suy diễn Bayes, cây quyết định qui nạp) LÀM SẠCH DỮ LIỆU Bước 2: Chuốt dữ liệu loại nhiễu, có thể chọn một trong các phương pháp Hồi quy (Regression) : sẽ dành chương riêng Phân cụm (Cluster) : sẽ dành chương riêng LÀM SẠCH DỮ LIỆU Bước 3: kiểm tra và sửa tính không nhất quán trong dữ liệu. Đề phát hiện kiểm tra sự bất thường trong giá trị dữ liệu, ta tuân thủ ba luật sau Luật giá trị duy nhất (unique rule) : mỗi giá trị của một thuộc tính sẽ khác biệt với các giá trị khác thuộc cùng thuộc tính. Luật liên tục (consecutive rule) : không có giá trị bị mất giữa giá trị lớn nhất và nhỏ nhất tương ứng một thuộc tính Luật giá trị rỗng (null rule) : xác định trước các ký hiệu hay cách đánh dấu giá trị rỗng Dùng để sửa tính không nhất quán dữ liệu Công cụ chà dữ liệu (Data scrubbing tools) : dùng cho một lĩnh vực cụ thể. Công cụ kiểm toán dữ liệu (Data auditing tools) : dùng cho việc phân tích dữ liệu, xác định quan hệ, xác định các luật. MỤC LỤC Đặt vấn đề Làm sạch dữ liệu Tích hợp Giảm chiều TÍCH HỢP Ý nghĩa tích hợp và chuyển đổi dữ liệu, chuẩn hóa để tiến hành khai phá/học máy Tập hợp : các giá trị dữ liệu tạo thành bộ hay khối Tổng quát hóa (generalization) : các dữ liệu "thô" được thay bằng các khái niệm đã chuẩn hóa Chuẩn hóa (normalization) : nếu phạm vi dữ liệu lớn thì đưa nó về phạm vi chuẩn Xây dựng thuộc tính (attribute construction) : thuộc tính mới thêm vào giúp quá trinh khai phá dữ liệu MỤC LỤC Đặt vấn đề Làm sạch dữ liệu Tích hợp Giảm chiều GIẢM CHIỀU Ý nghĩa: Việc giảm kích thước của dữ liệu cần đồng thời giữ được tính phân tích dữ liệu, tăng tốc qúa trình khai phá/học máy GIẢM CHIỀU Các chiến lược giảm kích thước dữ liệu Lựa chọn tập con các thuộc tính : trong đó các thuộc tính không liên quan, dư thừa hoặc các chiều cũng có thể xóa hay loại bỏ Giảm chiều : trong đó cơ chế mã hóa được sử dụng để giảm kích cỡ tập dữ liệu Rời rạc hóa và trừu tượng khái niệm : trong đó các giá trị dữ liệu thô được thay thế bằng các khái niệm trừu tượng đã rời rạc hóa. TỔNG KẾT Vấn đề khi tiến hành thu thập dữ liệu dùng cho bài toán khai phá dữ liệu/học máy. Cần theo các bước của quy trình thu thập và tiền xử lý dữ liệu. Cần hiểu ý nghĩa trong từng bước của quy trình. Thank you for your attentions! 1 Nhập môn Học máy và Khai phá dữ liệu (IT3190) 2 Nội dung môn học Lecture 1: Giới thiệu về Học máy và khai phá dữ liệu Lecture 2: Thu thập và tiền xử lý dữ liệu Lecture 3: Hồi quy tuyến tính (Linear regression) Lecture 4+5: Phân cụm Lecture 6: Phân loại và Đánh giá hiệu năng Lecture 7: dựa trên láng giềng gần nhất (KNN) Lecture 8: Cây quyết định và Rừng ngẫu nhiên Lecture 9: Học dựa trên xác suất Lecture 10: Mạng nơron (Neural networks) Lecture 11: Máy vector hỗ trợ (SVM) Lecture 12: Khai phá tập mục thường xuyên và các luật kết hợp Lecture 13: Thảo luận ứng dụng học máy và khai phá dữ liệu trong thực tế 3 Học có giám sát Học có giám sát (Supervised learning) Tập dữ liệu học (training data) bao gồm các quan sát (examples, observations), mà mỗi quan sát được gắn kèm với một giá trị đầu ra mong muốn. Mục đích là học một hàm (vd: một phân lớp, một hàm hồi quy,...) phù hợp với tập dữ liệu hiện có và khả năng tổng quát hoá cao. Hàm học được sau đó sẽ được dùng để dự đoán cho các quan sát mới. Phân loại (classification): nếu đầu ra (output – y) thuộc tập rời rạc và hữu hạn. Hồi quy (regression): nếu đầu ra (output – y) là các số thực. 4 Hồi quy tuyến tính: Giới thiệu Bài toán hồi quy: cần học một hàm y = f(x) từ một tập học cho trước D = {(x1, y1), (x2, y2), …, (xM, yM)} trong đó yi ≈ f(xi) với mọi i. Mỗi quan sát được biểu diễn bằng một véctơ n chiều, chẳng hạn xi = (xi1, xi2, …, xin)T. Mỗi chiều biểu diễn một thuộc tính (attribute/feature) Mô hình tuyến tính: nếu giả thuyết hàm y = f(x) là hàm có dạng tuyến tính f(x) = w0 + w1x1 + … + wnxn Học một hàm hồi quy tuyến tính thì tương đương với việc học véctơ trọng số w = (w0, w1, …, wn)T 5 Hồi quy tuyến tính: Ví dụ Hàm tuyến tính f(x) nào phù hợp? 𝑓(𝑥) 0.13 -0.91 1.02 -0.17 3.17 1.61 -2.76 -3.31 1.44 0.18 5.28 3.36 -1.74 -2.46 𝑥 7.93 5.56...... Ví dụ: 𝑓(𝑥) = −1.02 + 0.83𝑥 6 Phán đoán tương lai Đối với mỗi quan sát x = (x1, x2, …, xn)T: Giá trị đầu ra mong muốn cx (Không biết trước đối với các quan sát trong tương lai) Giá trị phán đoán (bởi hệ thống) yx = w0 + w1x1 + … + wnxn Ta thường mong muốn yx xấp xỉ tốt cx Phán đoán cho quan sát tương lai z = (z1, z2, …, zn)T Cần dự đoán giá trị đầu ra, bằng cách áp dụng hàm mục tiêu đã học được f: f(z) = w0 + w1z1 + … + wnzn 7 Học hàm hồi quy Mục tiêu học: học một hàm f* sao cho khả năng phán đoán trong tương lai là tốt nhất. Tức là sai số |cz – f(z)| là nhỏ nhất cho các quan sát tương lai z. Khả năng tổng quát hóa (generalization) là tốt nhất. Vấn đề: Có vô hạn hàm tuyến tính!! 𝑓(𝑥) Làm sao để học? Quy tắc nào? Dùng một tiêu chuẩn để đánh giá. Tiêu chuẩn thường dùng là hàm lỗi (generalization error, loss function, …) 𝑥 8 Hàm đánh giá lỗi (loss function) ▪ Định nghĩa hàm lỗi E  Lỗi (error/loss) phán đoán cho quan sát x = (x1, x2, …, xn)T r(x) = [cx – f*(x)]2 = (cx – w0 – w1x1 -… - wnxn)2 Lỗi của hệ thống trên toàn bộ không gian của x: E = Ex[r(x)] = Ex[cx – f*(x)]2 Cost, risk ▪ Mục tiêu học là tìm hàm f* mà E là nhỏ nhất: Trong đó H là không gian của hàm f. ▪ Nhưng: trong quá trình học ta không thể làm việc được với bài toán này. 9 Hàm lỗi thực nghiệm Ta chỉ quan sát được một tập D = {(x1, y1), (x2, y2), …, (xM, yM)}. Cần học hàm f từ D. Lỗi thực nghiệm (empirical loss; residual sum of squares) RSS/M là một xấp xỉ của Ex[r(x)] trên tập học D 1 𝑅𝑆𝑆𝑓 − 𝑬𝑥 𝑟 𝒙 thường được gọi là lỗi tổng quát 𝑀 hoá (generalization error) của hàm f. Nhiều phương pháp học thường gắn với RSS. 10 Bình phương tối thiểu (OLS) ◼ Cho trước D, ta đi tìm hàm f mà có RSS nhỏ nhất. (1) ◼ Đây được gọi là bình phương tối thiểu (least squares). Tìm nghiệm w* bằng cách lấy đạo hàm của RSS và giải phương trình RSS’ = 0. Thu được: Trong đó A là ma trận dữ liệu cỡ Mx(n+1) mà hàng thứ i là Ai = (1, xi1, xi2, …, xin); B-1 là ma trận nghịch đảo; y = (y1, y2, …, yM)T. Chú ý: giả thuyết ATA tồn tại nghịch đảo. 11 Bình phương tối thiểu: thuật toán ◼ Input: D = {(x1, y1), (x2, y2), …, (xM, yM)} ◼ Output: w* Học w* bằng cách tính: Trong đó A là ma trận dữ liệu cỡ Mx(n+1) mà hàng thứ i là Ai = (1, xi1, xi2, …, xin); B-1 là ma trận nghịch đảo; y = (y1, y2, …, yM)T. Chú ý: giả thuyết ATA tồn tại nghịch đảo. Phán đoán cho quan sát mới x: 12 Bình phương tối thiểu: ví dụ Kết quả học bằng bình phương tối thiểu 6 x y 0.13 -1 4 f* 1.02 -0.17 3 1.61 2 -2.5 -2 1.44 0.1 0 5 3.36 -1.74 -2.46 -2 7.5 5.56 -4 -4 -2 0 2 4 6 8 f*(x) = 0.81x – 0.78 13 Bình phương tối thiểu: nhược điểm Nếu ATA không tồn tại nghịch đảo thì không học được. Nếu các thuộc tính (cột của A) có phụ thuộc lẫn nhau. Độ phức tạp tính toán lớn do phải tính ma trận nghịch đảo. →Không làm việc được nếu số chiều n lớn. Khả năng overfitting cao vì việc học hàm f chỉ quan tâm tối thiểu lỗi đối với tập học đang có. 14 Ridge regression (1) ◼ Cho trước D = {(x1, y1), (x2, y2), …, (xM, yM)}, ta đi giải bài toán: (2) Trong đó Ai = (1, xi1, xi2, …, xin) được tạo ra từ xi; λ là một hằng số phạt (λ> 0). 15 Ridge regression (2) Giải bài toán (2) tương đương với việc giải bài toán sau: 𝑀 𝑤 ∗ = arg min ෍ 𝑦𝑖 − 𝑨𝑖 𝒘 2 (3) 𝒘 𝑖=1 sao cho σ𝑛𝑗=0 𝑤𝑗2 ≤ 𝑡  t là một hằng số nào đó. 2 Đại lượng hiệu chỉnh (phạt) 𝜆 𝒘 2 Có vai trò hạn chế độ lớn của w* (hạn chế không gian hàm f). Đánh đổi chất lượng của hàm f đối với tập học D, để có khả năng phán đoán tốt hơn với quan sát tương lai. 16 Ridge regression (3) Tìm nghiệm w* bằng cách lấy đạo hàm của RSS và giải phương trình RSS’ = 0. Thu được: Trong đó A là ma trận dữ liệu cỡ Mx(n+1) mà hàng thứ i là (1, xi1, xi2, …, xin); y = (y1, y2, …, yM)T; In+1 là ma trận đơn vị cỡ n+1. So sánh với phương pháp bình phương tối thiểu: Tránh được trường hợp ma trận dữ liệu suy biến. Hồi quy Ridge luôn làm việc được. Khả năng overfitting thường ít hơn. Lỗi trên tập học có thể nhiều hơn. Chú ý: chất lượng của phương pháp phụ thuộc rất nhiều vào sự lựa chọn của tham số λ. 17 Ridge regression: thuật toán ◼ Input: D = {(x1, y1), (x2, y2), …, (xM, yM)}, hằng số λ>0 ◼ Output: w* Học w* bằng cách tính: Trong đó A là ma trận dữ liệu cỡ Mx(n+1) mà hàng thứ i là Ai = (1, xi1, xi2, …, xin); B-1 là ma trận nghịch đảo; y = (y1, y2, …, yM)T. Phán đoán cho quan sát mới x: Chú ý: để tránh vài ảnh hưởng xấu từ độ lớn của y, ta nên loại bỏ thành phần w0 trong đại lượng phạt ở công thức (2). Khi đó nghiệm w* sẽ thay đổi một chút. 18 Ridge regression: ví dụ ◼ Xét tập dữ liệu Prostate gồm 67 quan sát dùng để học, và 31 quan sát dùng để kiểm thử. Dữ liệu gồm 8 thuộc tính. Least w squares Ridge 0 2.465 2.452 lcavol 0.680 0.420 lweight 0.263 0.238 age −0.141 −0.046 lbph 0.210 0.162 svi 0.305 0.227 lcp −0.288 0.000 gleason −0.021 0.040 pgg45 0.267 0.133 Test RSS 0.521 0.492 19 Ridge regression: ảnh hưởng của λ ◼ W* = (w0, S1, S2, S3, S4, S5, S6, AGE, SEX, BMI, BP) thay đổi khi cho λ thay đổi. 20 LASSO Hồi quy Ridge sử dụng chuẩn L2 cho đại lượng hiệu chỉnh: 𝑤 ∗ = arg min σ𝑀 𝑖=1 𝑦𝑖 − 𝑨𝑖 𝒘 2 , sao cho σ𝑛𝑗=0 𝑤𝑗2 ≤ 𝑡 𝒘 Thay L2 bằng L1 thì ta sẽ thu được phương pháp LASSO: 𝑀 𝑤 ∗ = arg min ෍ 𝑦𝑖 − 𝑨𝑖 𝒘 2 𝒘 𝑖=1 sao cho σ𝑛𝑗=0 |𝑤𝑗 | ≤ 𝑡 Hoặc có thể viết lại: 𝑀 𝑤 ∗ = arg min ෍ 𝑦𝑖 − 𝑨𝑖 𝒘 2 +𝜆 𝒘 1 𝒘 𝑖=1 Hàm mục tiêu của bài toán là không trơn. Do đó việc giải nó có thể khó hơn hồi quy Ridge. 21 LASSO: đại lượng hiệu chỉnh Các kiểu hiệu chỉnh khác nhau sẽ tạo ra các miền khác nhau cho w. LASSO thường tạo ra nghiệm thưa, tức là nhiều thành phần của w có giá trị là 0. Vì thế LASSO thực hiện đồng thời việc hạn chế và lựa chọn đặc trưng Figure by Nicoguaro - Own work, CC BY 4.0, https://commons.wikimedia.org/w/index.php?curid=58258966 22 OLS, Ridge, LASSO ◼ Xét tập dữ liệu Prostate gồm 67 quan sát dùng để học, và 31 quan sát dùng để kiểm thử. Dữ liệu gồm 8 thuộc tính. Ordinary Least w Squares Ridge LASSO 0 2.465 2.452 2.468 lcavol 0.680 0.420 0.533 lweight 0.263 0.238 0.169 Một số trọng số age −0.141 −0.046 là 0 lbph 0.210 0.162 0.002 → Chúng có thể svi 0.305 0.227 0.094 không quan trọng lcp −0.288 0.000 gleason −0.021 0.040 pgg45 0.267 0.133 Test RSS 0.521 0.492 0.479 23 Thank you for your attentions! 1 Nhập môn Học máy và Khai phá dữ liệu (IT3190) 2 Nội dung môn học Lecture 1: Giới thiệu về Học máy và khai phá dữ liệu Lecture 2: Thu thập và tiền xử lý dữ liệu Lecture 3: Hồi quy tuyến tính (Linear regression) Lecture 4+5: Phân cụm Lecture 6: Phân loại và Đánh giá hiệu năng Lecture 7: dựa trên láng giềng gần nhất (KNN) Lecture 8: Cây quyết định và Rừng ngẫu nhiên Lecture 9: Học dựa trên xác suất Lecture 10: Mạng nơron (Neural networks) Lecture 11: Máy vector hỗ trợ (SVM) Lecture 12: Khai phá tập mục thường xuyên và các luật kết hợp Lecture 13: Thảo luận ứng dụng học máy và khai phá dữ liệu trong thực tế 3 1. Hai bài toán học ◼ Học có giám sát (Supervised learning) ❑ Tập dữ liệu học (training data) bao gồm các quan sát (examples, observations), mà mỗi quan sát được gắn kèm với một giá trị đầu ra mong muốn. ❑ Ta cần học một hàm (vd: một phân lớp, một hàm hồi quy,...) phù hợp với tập dữ liệu hiện có. ❑ Hàm học được sau đó sẽ được dùng để dự đoán cho các quan sát mới. ◼ Học không giám sát (Unsupervised learning) ❑ Tập học (training data) bao gồm các quan sát, mà mỗi quan sát không có thông tin về nhãn lớp hoặc giá trị đầu ra mong muốn. ❑ Mục đích là tìm ra (học) các cụm, các cấu trúc, các quan hệ tồn tại ẩn trong tập dữ liệu hiện có. 4 Ví dụ về học không giám sát (1) ◼ Phân cụm (clustering) ❑ Phát hiện các cụm dữ liệu, cụm tính chất,… ◼ Community detection ◼ Phát hiện các cộng đồng trong mạng xã hội 5 Ví dụ về học không giám sát (2) ◼ Trends detection ❑ Phát hiện xu hướng, thị yếu,… ◼ Entity-interaction analysis 6 2. Phân cụm ◼ Phân cụm (clustering) ❑ Đầu vào: một tập dữ liệu {x1, …, xM} không có nhãn (hoặc giá trị đầu ra mong muốn) ❑ Đầu ra: các cụm (nhóm) của các quan sát ◼ Một cụm (cluster) là một tập các quan sát ❑ Tương tự với nhau (theo một ý nghĩa, đánh giá nào đó) ❑ Khác biệt với các quan sát thuộc các cụm khác Sau khi phân cụm 7 Phân cụm ◼ Giải thuật phân cụm Dựa trên phân hoạch (Partition-based clustering) Dựa trên tích tụ phân cấp (Hierarchical clustering) Bản đồ tự tổ thức (Self-organizing map – SOM) Các mô hình hỗn hợp (Mixture models) … ◼ Đánh giá chất lượng phân cụm (Clustering quality) Khoảng cách/sự khác biệt giữa các cụm → Cần được cực đại hóa Khoảng cách/sự khác biệt bên trong một cụm → Cần được cực tiểu hóa 8 3. Phương pháp K-means ◼ K-means được giới thiệu đầu tiên bởi Lloyd năm 1957. ◼ Là phương pháp phân cụm phổ biến nhất trong các phương pháp dựa trên phân hoạch (partition-based clustering) ◼ Biểu diễn dữ liệu: D={x1,x2,…,xr} xi là một quan sát (một vectơ trong một không gian n chiều) ◼ Giải thuật K-means phân chia tập dữ liệu thành k cụm Mỗi cụm (cluster) có một điểm trung tâm, được gọi là centroid k (tổng số các cụm thu được) là một giá trị được cho trước (vd: được chỉ định bởi người thiết kế hệ thống phân cụm) 9 k-Means: Các bước chính Đầu vào: tập học D, số lượng cụm k, khoảng cách d(x,y) Bước 1. Chọn ngẫu nhiên k quan sát (được gọi là các hạt nhân – seeds) để sử dụng làm các điểm trung tâm ban đầu (initial centroids) của k cụm. Bước 2. Lặp liên tục hai bước sau cho đến khi gặp điều kiện hội tụ (convergence criterion): ❑ Bước 2.1. Đối với mỗi quan sát, gán nó vào cụm (trong số k cụm) mà có tâm (centroid) gần nó nhất. ❑ Bước 2.2. Đối với mỗi cụm, tính toán lại điểm trung tâm của nó dựa trên tất cả các quan sát thuộc vào cụm đó. 10 K-means(D, k) D: Tập học k: Số lượng cụm kết quả (thu được) Lựa chọn ngẫu nhiên k quan sát trong tập D để làm các điểm trung tâm ban đầu (initial centroids) while not CONVERGENCE for each xD Tính các khoảng cách từ x đến các điểm trung tâm (centroid) Gán x vào cụm có điểm trung tâm (centroid) gần x nhất end for for each cụm Tính (xác định) lại điểm trung tâm (centroid) dựa trên các quan sát hiện thời đang thuộc vào cụm này end while return {k cụm kết quả} 11 K-means: Minh họa (1) [Liu, 2006] 12 K-means: Minh họa (2) [Liu, 2006] 13 K-means: Điều kiện hội tụ Quá trình phân cụm kết thúc, nếu: Không có (hoặc có không đáng kể) việc gán lại các quan sát vào các cụm khác, hoặc Không có (hoặc có không đáng kể) thay đổi về các điểm trung tâm (centroids) của các cụm, hoặc Giảm không đáng kể về tổng lỗi phân cụm: k Error =   d ( x, m i ) 2 i =1 xCi ▪ Ci: Cụm thứ i ▪ mi: Điểm trung tâm (centroid) của cụm Ci ▪ d(x, mi): Khoảng cách (khác biệt) giữa quan sát x và điểm trung tâm mi 14 K-means: Điểm trung tâm, hàm khoảng cách ◼ Xác định điểm trung tâm: Điểm trung bình (Mean centroid) 1 mi = Ci x xCi (vectơ) mi là điểm trung tâm (centroid) của cụm Ci |Ci| kích thước của cụm Ci (tổng số quan sát trong Ci) ◼ Hàm khoảng cách: Euclidean distance d (x, m i ) = x − m i = (x1 − mi1 )2 + (x2 − mi 2 )2 +... + (xn − min )2 (vectơ) mi là điểm trung tâm (centroid) của cụm Ci d(x,mi) là khoảng cách giữa x và điểm trung tâm mi 15 K-means: hàm khoảng cách ◼ Hàm khoảng cách ❑ Mỗi hàm sẽ tương ứng với một cách nhìn về dữ liệu. ❑ Vô hạn hàm!!! ❑ Chọn hàm nào? ◼ Có thể thay bằng độ đo tương đồng (similarity measure) 16 K-means: Các ưu điểm ◼ Đơn giản: dễ cài đặt, rất dễ hiểu ◼ Rất linh động: cho phép dùng nhiều độ đo khoảng cách khác nhau → phù hợp với các loại dữ liệu khác nhau. ◼ Hiệu quả (khi dùng độ đo Euclide) Độ phức tạp tính toán tại mỗi bước ~ O(r.k) ▪ r: Tổng số các quan sát (kích thước của tập dữ liệu) ▪ k: Tổng số cụm thu được ◼ Thuật toán có độ phức tạp trung bình là đa thức. ◼ K-means là giải thuật phân cụm được dùng phổ biến nhất 17 K-means: Các nhược điểm (1) ◼ Số cụm k phải được xác định trước ◼ Thường ta không biết chính xác ! ◼ Giải thuật K-means nhạy cảm (gặp lỗi) với các quan sát ngoại lai (outliers) Các quan sát ngoại lai là các quan sát (rất) khác biệt với tất các quan sát khác Các quan sát ngoại lai có thể do lỗi trong quá trình thu thập/lưu dữ liệu Các quan sát ngoại lai có các giá trị thuộc tính (rất) khác biệt với các giá trị thuộc tính của các quan sát khác 18 K-means: ngoại lai [Liu, 2006] 19 Giải quyết vấn đề ngoại lai Giải pháp 1: Trong quá trình phân cụm, cần loại bỏ một số các quan sát quá khác biệt với (cách xa) các điểm trung tâm (centroids) so với các quan sát khác ─ Để chắc chắn (không loại nhầm), theo dõi các quan sát ngoại lai (outliers) qua một vài (thay vì chỉ 1) bước lặp phân cụm, trước khi quyết định loại bỏ Giải pháp 2: Thực hiện việc lấy ngẫu nhiên (random sampling) một tập nhỏ từ D để học K cụm ─ Do đây là tập con nhỏ của tập dữ liệu ban đầu, nên khả năng một ngoại lai (outlier) được chọn là nhỏ ─ Gán các quan sát còn lại của tập dữ liệu vào các cụm tùy theo đánh giá về khoảng cách (hoặc độ tương tự) 20 K-means: Các nhược điểm (2) ◼ Giải thuật K-means phụ thuộc vào việc chọn các điểm trung tâm ban đầu (initial centroids) 1st centroid 2nd centroid [Liu, 2006] 21 K-means: Các hạt nhân ban đầu (1) ◼ Kết hợp nhiều kết quả phân cụm với nhau → Kết quả tốt hơn! Thực hiện giải thuật K-means nhiều lần, mỗi lần bắt đầu với một tập các hạt nhân được chọn ngẫu nhiên [Liu, 2006] 22 K-means: Các hạt nhân ban đầu (2) ◼ Một cách chọn hạt nhân nên dùng: ❑ Lựa chọn ngẫu nhiên hạt nhân thứ 1 (m1) ❑ Lựa chọn hạt nhân thứ 2 (m2) càng xa càng tốt so với hạt nhân thứ 1 ❑ … ❑ Lựa chọn hạt nhân thứ i (mi) càng xa càng tốt so với hạt nhân gần nhất trong số {m1, m2, … , mi-1} ❑... ◼ Đây được gọi là phương pháp K-means++ [Arthur, D.; Vassilvitskii, 2007] 23 K-means: Các nhược điểm (3) ◼ K-means (với khoảng cách Euclid) phù hợp với các cụm hình cầu. ◼ K-means không phù hợp để phát hiện các cụm (nhóm) không có dạng hình cầu. ◼ Cải thiện?? [Liu, 2006] 24 K-means: Tổng kết ◼ Mặc dù có những nhược điểm như trên, k-means vẫn là giải thuật phổ biến nhất được dùng để giải quyết các bài toán phân cụm – do tính đơn giản và hiệu quả. Các giải thuật phân cụm khác cũng có các nhược điểm riêng. ◼ So sánh hiệu năng của các giải thuật phân cụm là một nhiệm vụ khó khăn (thách thức). Làm sao để biết được các cụm kết quả thu được là chính xác? 25 4. Online K-means ◼ K-means: ❑ Cần dùng toàn bộ dữ liệu tại mỗi bước lặp ❑ Do đó không thể làm việc khi dữ liệu quá lớn (big data) ❑ Không phù hợp với luồng dữ liệu (stream data, dữ liệu đến liên tục) ◼ Online K-means cải thiện nhược điểm của K-means, cho phép ta phân cụm dữ liệu rất lớn, hoặc phân cụm luồng dữ liệu. ❑ Được phát triển từ K-means [Bottou, 1998]. ❑ Sử dụng tư tưởng học trực tuyến (online learning) và gradient ngẫu nhiên (stochastic gradient) 26 Online K-means: ý tưởng ◼ K-means tìm K tâm cụm và gán các quan sát {x1, …, xM} vào các cụm đó bằng cách cực tiểu hoá hàm lỗi sau M Q(w) = å|| xi - w(xi ) ||22 i=1 ❑ Trong đó w(xi) là tâm gần nhất với xi. ◼ Online K-means cực tiểu hàm Q theo phương pháp leo đồi và dùng thông tin đạo hàm (gradient) của Q. ❑ Tuy nhiên tại mỗi bước lặp t ta chỉ lấy một phần thông tin gradient, ❑ Phần gradient này thu được từ các quan sát tại bước t. Ví dụ: xt - wt (xt ) 27 Online K-means: thuật toán ◼ Khởi tạo K tâm ban đầu. ◼ Cập nhật các tâm mỗi khi một điểm dữ liệu mới đến: ❑ Tại bước t, lấy một quan sát xt. ❑ Tìm tâm wt gần nhất với xt. Sau đó cập nhật lại wt như sau: wt+1 = wt + g t (xt - wt ) ◼ Chú ý: tốc độ học {g1, g 2 ,...} là dãy hệ số dương nên được chọn thoả mãn các điều kiện sau åt=1 t åt=1 t < ¥ ¥ ¥ g = ¥; g 2 28 Online K-means: tốc độ học ◼ Một cách lựa chọn tốc độ học hay dùng: -k g t = (t + t ) ◼ 𝜏, 𝜅 là các hằng số dương. ◼ 𝜅  (0.5, 1] là tốc độ lãng quên. k càng lớn thì sẽ nhớ quá khứ càng lâu; các quan sát mới càng ít đóng góp vào mô hình hơn. 29 Online K-means: tốc độ hội tụ ◼ Hàm KM Cost Q giảm khi số lần lặp tăng lên. EM Cost (so sánh các phương pháp khác nhau) 2500 -100 2400 2300 2200 2100 2000 -80 Online K-means 1900 (hình tròn đen), 1800 1700 1600 K-means 1500 -60 Q 1400 (hình vuông đen) 1300 1200 1100 Dùng một phần Q’ 1000 -40 900 để tối ưu hàm Q 800 700 (hình tròn trắng), 600 500 -20 400 Dùng hết Q’ để tối 300 ưu hàm Q 200 100 (hình vuông trắng) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 30 Tài liệu tham khảo Arthur, D., Manthey, B., & Röglin, H. (2011). Smoothed analysis of the k-means method. Journal of the ACM (JACM), 58(5), 19. Bottou, Léon. Online learning and stochastic approximations. On-line learning in neural networks 17 (1998). B. Liu. Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data. Springer, 2006. Lloyd, S., 1982. Least squares quantization in PCM. IEEE Trans. Inform. Theory 28, 129–137. Originally as an unpublished Bell laboratories Technical Note (1957). Jain, A. K. (2010). Data clustering: 50 years beyond K- means. Pattern recognition letters, 31(8), 651-666. Arthur, D.; Vassilvitskii, S. (2007). K-means++: the advantages of careful seeding. Proceedings of the 18th annual ACM-SIAM symposium on Discrete algorithms, pp. 1027–1035. 31 Thank you for your attentions! 1 Nhập môn Học máy và Khai phá dữ liệu (IT3190) 2 Nội dung môn học Lecture 1: Giới thiệu về Học máy và khai phá dữ liệu Lecture 2: Thu thập và tiền xử lý dữ liệu Lecture 3: Hồi quy tuyến tính (Linear regression) Lecture 4+5: Phân cụm Lecture 6: Phân loại và Đánh giá hiệu năng Lecture 7: dựa trên láng giềng gần nhất (KNN) Lecture 8: Cây quyết định và Rừng ngẫu nhiên Lecture 9: Học dựa trên xác suất Lecture 10: Mạng nơron (Neural networks) Lecture 11: Máy vector hỗ trợ (SVM) Lecture 12: Khai phá tập mục thường xuyên và các luật kết hợp Lecture 13: Thảo luận ứng dụng học máy và khai phá dữ liệu trong thực tế 3 Nhắc lại: Học có giám sát Học có giám sát (Supervised learning) Tập dữ liệu học (training data) bao gồm các quan sát (examples, observations), mà mỗi quan sát được gắn kèm với một giá trị đầu ra mong muốn. Mục đích là học một hàm (vd: một phân lớp, một hàm hồi quy,...) phù hợp với tập dữ liệu hiện có và khả năng tổng quát hoá cao. Hàm học được sau đó sẽ được dùng để dự đoán cho các quan sát mới. Phân loại (classification): nếu đầu ra (output – y) thuộc tập rời rạc và hữu hạn. 4 Phân loại Multi-class classification (phân loại nhiều lớp): mỗi quan sát x chỉ nhận 1 nhãn trong tập nhãn lớp {c1, c2, …, cL}  Lọc Spam: y thuộc {spam, normal}  Đánh giá nguy cơ tín dụng: y thuộc {high, normal}  Phán đoán tấn công mạng: ? Multi-label classification (phân loại đa nhãn): mỗi đầu ra là một tập nhỏ các lớp; mỗi quan sát x có thể có nhiều nhãn  Image tagging: y = {birds, nest, tree}  sentiment analysis 5 1. Đánh giá hiệu năng hệ thống học máy. Làm thế nào để thu được một đánh giá đáng tin cậy về hiệu năng của hệ thống? Chiến lược đánh giá Lựa chọn tham số tốt Làm thế nào để lựa chọn tốt các tham số cho một phương pháp học máy? Làm thế nào để so sánh hiệu quả của hai phương pháp học máy, với độ tin cậy cao? 6 1. Đánh giá hiệu năng hệ thống học máy.. Đánh giá lý thuyết (theoretical evaluation): nghiên cứu các khía cạnh lý thuyết của một hệ thống mà có thể chứng minh được. Tốc độ học, thời gian học, Bao nhiêu ví dụ học là đủ? Độ chính xác trung bình của hệ thống, Khả năng chống nhiễu,… Đánh giá thực nghiệm (experimental evaluation): quan sát hệ thống làm việc trong thực tế, sử dụng một hoặc nhiều tập dữ liệu và các tiêu chí đánh giá. Tổng hợp đánh giá từ các quan sát đó. Chúng ta sẽ nghiên cứu cách đánh giá thực nghiệm. 7 1. Đánh giá hiệu năng hệ thống học máy… Bài toán đánh giá (model assessment): cần đánh giá hiệu năng của phương pháp (model) học máy A, chỉ dựa trên bộ dữ liệu đã quan sát D. Việc đánh giá hiệu năng của hệ thống Thực hiện một cách tự động, sử dụng một tập dữ liệu. Không cần sự tham gia (can thiệp) của người dùng. Chiến lược đánh giá (evaluation strategies) → Làm sao có được một đánh giá đáng tin cậy về hiệu năng của hệ thống? Các tiêu chí đánh giá (evaluation metrics) → Làm sao để đo hiệu năng của hệ thống? 8 2. Các phương pháp đánh giá Hold-out (chia đôi) Stratified sampling (lấy mẫu phân tầng) Repeated hold-out (chi đôi nhiều lần) Cross-validation (đánh giá chéo) k-fold Leave-one-out Bootstrap sampling 9 Hold-out (Splitting) Toàn bộ tập ví dụ D được chia thành 2 tập con không giao nhau Tập huấn luyện Dtrain – để huấn luyện hệ thống Tập kiểm thử Dtest – để đánh giá hiệu năng của hệ thống đã học → D = Dtrain  Dtest, và thường là |Dtrain| >> |Dtest| Các yêu cầu: Bất kỳ ví dụ nào thuộc vào tập kiểm thử Dtest đều không được sử dụng trong quá trình huấn luyện hệ thống Bất kỳ ví dụ nào được sử dụng trong giai đoạn huấn luyện hệ thống (i.e., thuộc vào Dtrain) đều không được sử dụng trong giai đoạn đánh giá hệ thống Các ví dụ kiểm thử trong Dtest cho phép một đánh giá không thiên vị đối với hiệu năng của hệ thống Các lựa chọn thường gặp: |Dtrain|=(2/3).|D|, |Dtest|=(1/3).|D| Phù hợp khi ta có tập ví dụ D có kích thước lớn 10 Stratified sampling Đối với các tập ví dụ có kích thước nhỏ hoặc không cân xứng (unbalanced datasets), các ví dụ trong tập huấn luyện và thử nghiệm có thể không phải là đại diện Ví dụ: Có (rất) ít ví dụ đối với một số lớp Mục tiêu: Phân bố lớp (class distribution) trong tập huấn luyện và tập kiểm thử phải xấp xỉ như trong tập toàn bộ các ví dụ (D) Lấy mẫu phân tầng (Stratified sampling) Là một phương pháp để cân xứng (về phân bố lớp) Đảm bảo tỷ lệ phân bố lớp (tỷ lệ các ví dụ giữa các lớp) trong tập huấn luyện và tập kiểm thử là xấp xỉ nhau Phương pháp lấy mẫu phân tầng không áp dụng được cho bài toán hồi quy (vì giá trị đầu ra của hệ thống là một giá trị số thực, không phải là một nhãn lớp) 11 Repeated hold-out Áp dụng phương pháp đánh giá Hold-out nhiều lần, để sinh ra (sử dụng) các tập huấn luyện và thử nghiệm khác nhau Trong mỗi bước lặp, một tỷ lệ nhất định của tập D được lựa chọn ngẫu nhiên để tạo nên tập huấn luyện (có thể sử dụng kết hợp với phương pháp lấy mẫu phân tầng – stratified sampling) Các giá trị lỗi (hoặc các giá trị đối với các tiêu chí đánh giá khác) ghi nhận được trong các bước lặp này được lấy trung bình cộng (averaged) để xác định giá trị lỗi tổng thể Phương pháp này vẫn không hoàn hảo Mỗi bước lặp sử dụng một tập kiểm thử khác nhau Có một số ví dụ trùng lặp (được sử dụng lại nhiều lần) trong các tập kiểm thử này 12 Cross-validation Để tránh việc trùng lặp giữa các tập kiểm thử (một số ví dụ cùng xuất hiện trong các tập kiểm thử khác nhau) k-fold cross-validation Tập toàn bộ các ví dụ D được chia thành k tập con không giao nhau (gọi là “fold”) có kích thước xấp xỉ nhau Mỗi lần (trong số k lần) lặp, một tập con được sử dụng làm tập kiểm thử, và (k-1) tập con còn lại được dùng làm tập huấn luyện k giá trị lỗi (mỗi giá trị tương ứng với một fold) được tính trung bình cộng để thu được giá trị lỗi tổng thể Các lựa chọn thông thường của k: 10, hoặc 5 Thông thường, mỗi tập con (fold) được lấy mẫu phân tầng (xấp xỉ phân bố lớp) trước khi áp dụng quá trình đánh giá Cross-validation Phù hợp khi ta có tập ví dụ D vừa và nhỏ 13 Leave-one-out cross-validation Một trường hợp (kiểu) của phương pháp Cross-validation Số lượng các nhóm (folds) bằng kích thước của tập dữ liệu (k=|D|) Mỗi nhóm (fold) chỉ bao gồm một ví dụ Khai thác tối đa (triệt để) tập ví dụ ban đầu Không hề có bước lấy mẫu ngẫu nhiên (no random sub- sampling) Áp dụng lấy mẫu phân tầng (stratification) không phù hợp → Vì ở mỗi bước lặp, tập thử nghiệm chỉ gồm có một ví dụ Chi phí tính toán (rất) cao Phù hợp khi ta có một tập ví dụ D (rất) nhỏ 14 Bootstrap sampling. Phương pháp Cross-validation sử dụng việc lấy mẫu không lặp lại (sampling without replacement) → Đối với mỗi ví dụ, một khi đã được chọn (được sử dụng), thì không thể được chọn (sử dụng) lại cho tập huấn luyện Phương pháp Bootstrap sampling sử dụng việc lấy mẫu có lặp lại (sampling with replacement) để tạo nên tập huấn luyện Giả sử tập toàn bộ D bao gồm n ví dụ Lấy mẫu có lặp lại n lần đối với tập D, để tạo nên tập huấn luyện Dtrain gồm n ví dụ Từ tập D, lấy ra ngẫu nhiên một ví dụ x (nhưng không loại bỏ x khỏi tập D) Đưa ví dụ x vào trong tập huấn luyện: Dtrain = Dtrain  x Lặp lại 2 bước trên n lần Sử dụng tập Dtrain để huấn luyện hệ thống Sử dụng tất cả các ví dụ thuộc D nhưng không thuộc Dtrain để tạo nên tập thử nghiệm: Dtest= {zD; zDtrain} 15 Bootstrap sampling.. Trong mỗi bước lặp, một ví dụ có xác suất 1 − n1 để không được lựa chọn đưa vào tập huấn luyện Vì vậy, xác suất để một ví dụ (sau quá trình lấy mẫu lặp lại – bootstrap sampling) được đưa vào tập kiểm thử là: 𝑛 1 1− ≈ 𝑒 −1 ≈ 0.368 𝑛 Có nghĩa rằng: Tập huấn luyện (có kích thước =n) bao gồm xấp xỉ 63.2% các ví dụ trong D (Lưu ý: Một ví dụ thuộc tập D có thể xuất hiện nhiều lần trong tập Dtrain ) Tập kiểm thử (có kích thước 1) khi cần phân lớp/dự đoán, nhưng không quá nhiều. Lý do: Tránh ảnh hưởng của lỗi/nhiễu nếu chỉ dùng 1 hàng xóm. Nếu quá nhiều hàng xóm thì sẽ phá vỡ cấu trúc tiềm ẩn trong dữ liệu. 13 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ác hàm khoảng cách hình học: Có thể phù hợp với các bài toán có các thuộc tính đầu vào là kiểu số thực (𝑥𝑖𝑅) Hàm khoảng cách Hamming: Có thể phù hợp với các bài toán có các thuộc tính đầu vào là kiểu nhị phân (𝑥𝑖{0,1}) 14 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) 1/ p  n p Hàm Minkowski (𝑝-norm): d ( x, z ) =   xi − zi   i =1  n Hàm Manhattan (𝑝 = 1): d ( x, z ) =  xi − zi i =1 n Hàm Euclid (𝑝 = 2): d ( x, z ) = (  i i x − z )2 i =1 1/ p  n p Hàm Chebyshev (𝑝 = ∞): d ( x, z ) = lim   xi − zi  p →  i =1  = max xi − zi i 15 Hàm tính khoảng cách (3) ◼ Hàm khoảng cách n Hamming d ( x, z ) =  Difference( xi , zi ) i =1 Đối với các thuộc tính đầu 1, if (a  b) vào là kiểu nhị phân ({0,1}) Difference(a, b) =  0, if (a = b) Ví dụ: 𝒙 = (0,1,0,1,1) 16 Chuẩn hóa miền giá trị thuộc tính n ◼ Hàm tính khoảng cách Euclid: d ( x, z ) = (  i i x − z )2 i =1 ◼ 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) 𝒙 = (Age=20, Income=12000, Height=1.68) 𝒛 = (Age=40, Income=1300, Height=1.75) ◼ Khoản

L0-intro-đã gộp.pdf

Document Details

Tags

Related

Full Transcript

Upgrade to continue