Tài liệu Phương pháp học nửa giám sát và ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG ———————————— TRẦN ANH TUẤN PHƯƠNG PHÁP HỌC NỬA GIÁM SÁT VÀ ỨNG DỤNG Chuyên nghành: Khoa học máy tính Mã số : 60.48.01 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Người hướng dẫn khoa học: PGS.TS ĐOÀN VĂN BAN Thái nguyên – Năm 2014 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ -i- MỤC LỤC MỤC LỤC .............................................................................................................. i DANH MỤC CÁC TỪ VIẾT TẮT ..................................................................... iv DANH MỤC CÁC HÌNH ..................................................................................... v MỞ ĐẦU ............................................................................................................... 1 CHƢƠNG 1: PHƢƠNG PHÁP HỌC MÁY ....................................................... 4 1.1. Khái niệm học máy .................................................................................... 4 1.2. Một số khái niệm cơ bản trong học máy .................................................... 6 1.2.1. Không gian biểu diễn của dữ liệu ....................................................... 6 1.2.2. Bản chất của dữ liệu ............................................................................ 6 1.2.3. Tiền xử lý dữ liệu ................................................................................ 6 1.2.4. Quá trình rời rạc hóa dữ liệu ............................................................... 7 1.2.5. Tập mẫu ............................................................................................... 7 1.2.6. Quá trình tìm kiếm trong không gian giả thuyết ................................. 7 1.3. Học có giám sát .......................................................................................... 8 1.3.1. Khái niệm ............................................................................................ 8 1.3.2. Cách giải một bài toán học có giám sát .............................................. 9 1.3.3. Cực tiểu hóa rủi ro kinh nghiệm ....................................................... 10 1.4. Học không có giám sát ............................................................................. 11 1.4.1. Khái niệm .......................................................................................... 11 1.4.2. Phân cụm dữ liệu ............................................................................... 12 1.5. Học tăng cƣờng ........................................................................................ 14 1.6. Học nửa giám sát ...................................................................................... 16 1.6.1. Khái niệm .......................................................................................... 16 - ii - 1.6.2. Bài toán học nửa giám sát ................................................................. 19 1.7. Tổng kết chƣơng 1 ................................................................................... 21 CHƢƠNG 2: MỘT SỐ THUẬT TOÁN HỌC NỬA GIÁM SÁT VÀ BÀI TOÁN PHÂN CỤM DỮ LIỆU........................................................................... 22 2.1. Một số thuật toán học nửa giám sát ......................................................... 22 2.1.1. Mô hình sinh và thuật toán kỳ vọng cực đại ..................................... 22 2.1.1.1. Giới thiệu mô hình sinh.............................................................. 22 2.1.1.2. Mô hình sinh trong học nửa giám sát......................................... 22 2.1.1.3. Thuật toán kỳ vọng cực đại ........................................................ 24 2.1.2. Thuật toán tự huấn luyện................................................................... 25 2.1.2.1 Giới thiệu thuật toán tự huấn luyện............................................. 25 2.1.2.2. Nội dung thuật toán .................................................................... 26 2.1.3. Thuật toán đồng huấn luyện .............................................................. 27 2.1.3.1. Giới thiệu thuật toán đồng huấn luyện ....................................... 27 2.1.3.2. Nội dung thuật toán .................................................................... 28 2.1.4. Thuật toán máy véc tơ hỗ trợ (S3VM) .............................................. 29 2.4.1.1. Thuật toán SVM ......................................................................... 29 2.1.4.2. Giới thiệu thuật toán S3VM ....................................................... 34 2.1.4.3. Nội dung thuật toán S3VM ........................................................ 34 2.2. Phân cụm dữ liệu ...................................................................................... 36 2.2.1. Khái quát quá trình phân cụm dữ liệu ............................................... 36 2.2.2. Bài toán phân cụm dữ liệu ................................................................ 36 2.2.3. Các yêu cầu của phân cụm dữ liệu .................................................... 39 2.2.4. Các kỹ thuật phân cụm ...................................................................... 41 - iii - 2.2.5. Một số thuật toán phân cụm dữ liệu nửa giám sát ............................ 46 2.2.5.1. Thuật toán COP-Kmeans ........................................................... 46 2.2.5.2. Phân cụm nửa giám sát trên tập dữ liệu đƣợc gán nhãn ............ 47 2.2.5.3. Thuật toán K-Means phân cấp ................................................... 49 2.3. Tổng kết chƣơng 2 ................................................................................... 50 CHƢƠNG 3: ỨNG DỤNG HỌC NỬA GIÁM SÁT VÀO BÀI TOÁN PHÂN CỤM VĂN BẢN ................................................................................................. 51 3.1. Phân tích bài toán ..................................................................................... 51 3.2 Hƣớng giải quyết của bài toán .................................................................. 53 3.3. Giải pháp, công nghệ sử dụng .................................................................. 57 3.4. Cài đặt chƣơng trình thử nghiệm ............................................................. 58 3.4.1. Nội dung chƣơng trình ...................................................................... 58 3.4.2. Kết quả thực nghiệm ......................................................................... 63 3.4.3. Thực hiện phân cụm thử nghiệm ...................................................... 64 3.5. Kết luận chƣơng 3 .................................................................................... 67 KẾT LUẬN ......................................................................................................... 68 TÀI LIỆU THAM KHẢO ................................................................................... 70 - iv - DANH MỤC CÁC TỪ VIẾT TẮT SVM Support Vector Machine S3VM Semi – superviesd Suport vector machines EM Expectation-Maximization MaxEnt Maximum Entropy TSVM Transductive Support Vector Machine RSS Residual Sum of Squares -v- DANH MỤC CÁC HÌNH Hình 1.1: Mô hình học có giám sát ....................................................................... 8 Hình 1.2: Minh họa phân cụm dữ liệu. ............................................................... 13 Hình 1.3: Sơ đồ quá trình thực hiện của học nửa giám sát ................................. 17 Hình 1.4: Mô hình học nửa giám sát .................................................................. 19 Hình 1.5: Dữ liệu chƣa gán nhãn sử dụng trong quá trình học nửa giám sát ..... 20 Hình 1.6: Mô hình hóa các tập dữ liệu trong học nửa giám sát. ......................... 21 Hình 2.1 Dữ liệu có nhãn .................................................................................... 23 Hình 2.2 Dữ liệu có nhãn và chƣa có nhãn ......................................................... 23 Hình 2.3. Quá trình tự huấn luyện....................................................................... 26 Hình 2.4 Phân lớp SVM .................................................................................... 29 Hình 2.5: Phân cụm các vector truy vấn ............................................................. 37 Hình 2.6: Hình thành cụm cha ............................................................................ 38 Hình 2.7: Các chiến lƣợc phân cụm phân cấp ................................................... 42 Hình 2.8: Thuật toán K-Means phân cấp ............................................................ 50 Hình 3.1. Thuật toán phân cụm văn bản ............................................................. 57 Hình 3.2: Giao diện chính chƣơng trình ............................................................. 63 Hình 3.3: Thử nghiệm nhập văn bản để phân cụm ............................................. 65 Hình 3.4: Thử nghiệm chèn văn bản vào danh sách chờ phân cụm ................... 66 Hình 3.5: Kết quả phân cụm thử nghiệm ............................................................ 66 -1- MỞ ĐẦU 1. Đặt vấn đề Hoạt động học tập là hoạt động chuyên hƣớng vào sự tái tạo lại tri thức ở ngƣời học. Sự tái tạo ở đây hiểu theo nghĩa là phát hiện lại. Sự thuận lợi cho ngƣời học ở đây đó là con đƣờng đi mà để phát hiện lại đã đƣợc các nhà khoa học tìm hiểu trƣớc, giờ ngƣời học chỉ việc tái tạo lại. Và để tái tạo lại, ngƣời học không có cách gì khác đó là phải huy động nội lực của bản thân (động cơ, ý chí, …), càng phát huy cao bao nhiêu thì việc tái tạo lại càng diễn ra tốt bấy nhiêu. Do đó hoạt động học làm thay đổi chính ngƣời học. Ai học thì ngƣời đó phát triển, không ai học thay thế đƣợc, ngƣời học cần phải có trách nhiệm với chính bản thân mình, vì mình trong quá trình học. Mặc dù hoạt động học có thể cũng có thể làm thay đổi khách thể. Nhƣng nhƣ thế không phải là mục đích tự thân của hoạt động học mà chính là phƣơng tiện để đạt đƣợc mục đích làm thay đổi chính chủ thể của hoạt động. Hoạt động học là hoạt động tiếp thu những tri thức lý luận, khoa học. Nghĩa là việc học không chỉ dừng lại ở việc nắm bắt những khái niệm đời thƣờng mà học phải tiến đến những tri thức khoa học, những tri thức có tính chọn lựa cao, đã đƣợc khái quát hoá, hệ thống hoá. Hoạt động học tập không chỉ hƣớng vào việc tiếp thu những tri thức, kĩ năng, kĩ xảo mà còn hƣớng vào việc tiếp thu cả những tri thức của chính bản thân hoạt động học. Hoạt động học muốn đạt kết quả cao, ngƣời học phải biết cách học, phƣơng pháp học, nghĩa là phải có những tri thức về chính bản thân hoạt động học. Vậy, việc làm thế nào để máy tính có khả năng học tập, tƣ duy và có khả năng học tập giống con ngƣời là một lĩnh vực nghiên cứu rất đƣợc chú ý trong thời đại hiện nay. Dựa trên khuynh hƣớng đó và sự hƣớng dẫn của PGS, TS -2Đoàn Văn Ban, tôi mạnh dạn nhận đề tài: ”PHƢƠNG PHÁP HỌC NỬA GIÁM SÁT VÀ ỨNG DỤNG” để tìm hiểu và ứng dụng vào thực tế. 2. Đối tƣợng và phạm vi nghiên cứu Đối tƣợng nghiên cứu: - Đề tài nghiên cứu về những vấn đề chung trong học máy, một số thuật toán trong khai phá dữ liệu và ứng dụng thuật toán học nửa giám sát trong phân cụm văn bản. Phạm vi nghiên cứu: - Khai phá dữ liệu, các giải thuật phân cụm - Học máy và m ột số thuật toán học nửa giám sát và ứng dụng trong thực tế 3. Hƣớng nghiên cứu của đề tài - Nghiên cứu lý thuyết cơ bản về học máy, học không giám sát, học có giám sát, học nửa giám sát. - Nghiên cứu một số thuật toán học nửa giám sát, phân cụm dữ liệu. - Từ kết quả thu đƣợc đề tài cài đặt ứng dụng trong bài toán phân cụm văn bản. 4. Những nội dung chính Luận văn đƣợc trình bày trong 3 chƣơng, có phần mở đầu, phần kết luận, phần mục lục, phần tài liệu tham khảo. Luận văn đƣợc chia làm ba chƣơng với nội dung cơ bản nhƣ sau: Chƣơng 1: Trình bày về khái niệm học máy, học có giám sát, học không giám sát, học tăng cƣờng và học nửa giám sát. Chƣơng 2: Trình bày về một số thuật toán học nửa giám sát và bài toán phân cụm dữ liệu. Chƣơng 3: Trình bày về bài toán phân cụm dữ liệu văn bản, cách biểu diễn và xử lý dữ liệu văn bản và tiến hành cài đặt thử nghiệm thuật toán. -35. Phƣơng pháp nghiên cứu - Nghiên cứu tổng hợp các tài liệu, về phƣơng pháp học máy: Học giám sát, học không giám sát, học nửa giám sát. - Nghiên cứu các giải thuật học nửa giám sát. Ý nghĩa khoa học: Đề tài nghiên cứu về những vấn đề chung trong học máy, một số thuật toán trong khai phá dữ liệu và ứng dụng thuật toán học nửa giám sát để phân cụm văn bản. -4- CHƢƠNG 1: PHƢƠNG PHÁP HỌC MÁY 1.1. Khái niệm học máy Học máy (machine learning) là một ngành khoa học nghiên cứu các kĩ thuật, các phƣơng pháp cho phép các máy tính có khả năng "học" giống nhƣ con ngƣời. Hay nói một cách khác cụ thể hơn, học máy là một phƣơng pháp để tạo ra các chƣơng trình máy tính bằng việc phân tích các tập dữ liệu, qua đó máy tính có khả năng tích lũy đƣợc tri thức thông qua việc học đƣợc các khái niệm để có thể ra quyết định trong các trƣờng hợp tƣơng tự [11]. Qua đó ta thấy học máy có liên quan rất mật thiết với thống kê, vì cả hai lĩnh vực đều nghiên cứu việc phân tích dữ liệu, nhƣng học máy khác với thống kê ở chỗ, học máy tập trung vào sự phức tạp của các giải thuật trong việc thực thi tính toán. Nhiều bài toán suy luận đƣợc xếp vào loại bài toán NP-khó, vì thế một phần của học máy là nghiên cứu sự phát triển các giải thuật suy luận xấp xỉ mà có thể xử lí đƣợc. Phân loại: Có hai loại phƣơng pháp học máy chính: - Phƣơng pháp quy nạp: Máy học/phân biệt các khái niệm dựa trên dữ liệu đã thu thập đƣợc trƣớc đó. Phƣơng pháp này cho phép tận dụng đƣợc nguồn dữ liệu rất nhiều và sẵn có. - Phƣơng pháp suy diễn: Máy học/phân biệt các khái niệm dựa vào các luật. Phƣơng pháp này cho phép tận dụng đƣợc các kiến thức chuyên ngành để hỗ trợ máy tính. Hiện nay, các thuật toán đều cố gắng tận dụng đƣợc ƣu điểm của hai phƣơng pháp này. -5- Các ngành khoa học liên quan: - Lý thuyết thống kê: các kết quả trong xác suất thống kê là tiền đề cho rất nhiều phƣơng pháp học máy. Đặc biệt, lý thuyết thống kê cho phép ƣớc lƣợng sai số của các phƣơng pháp học máy. - Các phƣơng pháp tính: các thuật toán học máy thƣờng sử dụng các tính toán số thực/số nguyên trên dữ liệu rất lớn. Trong đó, các bài toán nhƣ: tối ƣu có/không ràng buộc, giải phƣơng trình tuyến tính v.v… đƣợc sử dụng rất phổ biến. - Khoa học máy tính: là cơ sở để thiết kế các thuật toán, đồng thời đánh giá thời gian chạy, bộ nhớ của các thuật toán học máy. Ứng dụng: Học máy có ứng dụng rộng khắp trong các ngành khoa học/sản xuất, đặc biệt những ngành cần phân tích khối lƣợng dữ liệu khổng lồ. Một số ứng dụng thƣờng thấy:  Xử lý ngôn ngữ tự nhiên (Natural Language Processing): xử lý văn bản, giao tiếp ngƣời – máy.  Nhận dạng (Pattern Recognition): nhận dạng tiếng nói, chữ viết tay, vân tay, thị giác máy (Computer Vision).  Tìm kiếm (Search Engine).  Chẩn đoán trong y tế: phân tích ảnh X-quang, các hệ chuyên gia chẩn đoán tự động.  Tin sinh học: phân loại chuỗi gene, quá trình hình thành gene/protein.  Vật lý: phân tích ảnh thiên văn, tác động giữa các hạt.  Phát hiện gian lận tài chính (financial fraud): gian lận thẻ tỉn dụng.  Phân tích thị trƣờng chứng khoán (stock market analysis).  Chơi trò chơi: tự động chơi cờ, hành động của các nhân vật ảo.  Rôbốt: là tổng hợp của rất nhiều ngành khoa học, trong đó học máy tạo nên hệ thần kinh/bộ não của ngƣời máy. -61.2. Một số khái niệm cơ bản trong học máy 1.2.1. Không gian biểu diễn của dữ liệu Không gian biểu diễn là một tập hợp:  Ký hiệu là X, mỗi phần tử thuộc X có thể đƣợc gọi là các dữ liệu, các thể hiện, các đối tƣợng hay các ví dụ.  Mỗi phần tử S  X đƣợc biểu diễn bởi một tập gồm n thuộc tính S = (s1, s2, …, sn). Một đối tƣợng S cũng có thể đƣợc biểu diễn kết hợp với lớp liên thuộc của nó hay nói cách khác có thể đƣợc biểu diễn dƣới dạng nhãn: z = (s, c). 1.2.2. Bản chất của dữ liệu Bản chất của các dữ liệu có thể là các giá trị số trong tập số thực, các giá trị rời rạc, các giá trị nhị phân, dãy các phần tử trong một bảng chữ cái (alphabet), ... Không gian biểu diễn của dữ liệu có thể biểu diễn dƣới dạng thuần nhất (cùng kiểu) hoặc dƣới dạng trộn (không cùng kiểu). 1.2.3. Tiền xử lý dữ liệu Là quá trình xử lý dữ liệu đầu vào nhằm mục đích làm giảm số chiều của dữ liệu đầu vào, giảm số chiều của vấn đề, xử lý nhiễu, ... Ta thực hiện nhƣ sau:  Loại bỏ các thuộc tính không phù hợp hoặc ít phù hợp với quá trình học.  Sử dụng các phép biến đổi tuyến tính hoặc không tuyến tính trên các thuộc tính ban đầu, nhằm giảm số chiều của không gian đầu vào.  Dùng các chuyên gia hoặc sử dụng trực quan để phát hiện các bất thƣờng, các lỗi mô tả thuộc tính hoặc nhãn, nhằm xử lý nhiễu. -7- 1.2.4. Quá trình rời rạc hóa dữ liệu Có những thuật toán học không xử lý đƣợc các dữ liệu mang tính liên tục. Do vậy cần phải biến đổi các dữ liệu mang tính liên tục thành các giá trị rời rạc. Có thể sử dụng các phƣơng pháp sau:  Phƣơng pháp phân đoạn.  Phƣơng pháp đo lƣờng entropy.  Nếu dữ liệu tuân theo một luật phân phối nào đó, ví dụ phân phố Gauss, phân phố đều, … Thì ta có thể rời rạc thành các khoảng phân phối tƣơng ứng. 1.2.5. Tập mẫu Tập mẫu là tập hữu hạn các ví dụ. Có ba kiểu tập mẫu:  Tập mẫu học hay tập học.  Tập mẫu hợp thức hoá hay tập hợp thức.  Tập mẫu thử hay tập thử. 1.2.6. Quá trình tìm kiếm trong không gian giả thuyết Trong một không gian giả thiết X thì học trở thành bài toán tìm kiếm giả thiết tốt nhất trong X.Nếu ta đánh giá mỗi giả thiết bởi một hàm "mục tiêu" thì ta xét học nhƣ một bài toán tối ƣu hoá. Nghĩa là bài toán tìm phần tử của X làm tối ƣu hàm mục tiêu. Trong học máy ngƣời ta thƣờng dùng tối ƣu không ràng buộc hoặc tối ƣu có ràng buộc. Các phƣơng pháp tối ƣu hoá thƣờng dùng trong học máy nhƣ Gradient, nhân tử Lagrange, …[9]. -8- 1.3. Học có giám sát 1.3.1. Khái niệm Học có giám sát là một kỹ thuật của ngành học máy nhằm mục đích xây dựng một hàm f từ dữ tập dữ liệu huấn luyện. Dữ liệu huấn luyện bao gồm các cặp đối tƣợng đầu vào và đầu ra mong muốn. Đầu ra của hàm f có thể là một giá trị liên tục hoặc có thể là dự đoán một nhãn phân lớp cho một đối tƣợng đầu vào. Hình 1.1: Mô hình học có giám sát Nhiệm vụ của chƣơng trình học có giám sát là dự đoán giá trị của hàm f cho một đối tƣợng đầu vào hợp lệ bất kì, sau khi đã xét một số mẫu dữ liệu huấn luyện (nghĩa là các cặp đầu vào và đầu ra tƣơng ứng). Để đạt đƣợc điều này, chƣơng trình học phải tổng quát hóa từ các dữ liệu sẵn có để dự đoán đƣợc những tình huống chƣa gặp phải theo một cách hợp lý. Phƣơng pháp học có giám sát có thể đƣợc mô tả tóm tắt nhƣ sau: hệ thống học sẽ quan sát một tập dữ liệu huấn luyện đã đƣợc gán nhãn, bao gồm các cặp (đặc tính, nhãn), đƣợc biểu diễn bởi {(x1, y1), (x2, y2), ..., (xn, yn)}. Mục đích nhằm dự đoán nhãn y cho bất kỳ đầu vào mới với đặc tính x. Một nhiệm vụ của học có giám sát đƣợc gọi là hồi quy khi y∈ℝ và phân lớp khi y có một tập các giá trị rời rạc. Dữ liệu đƣợc gán nhãn: Là dữ liệu bao gồm các cặp gồm đối tƣợng đầu vào và đầu ra mong muốn. Đầu ra của một hàm có thể là một giá trị liên tục gọi là hồi quy, hoặc có thể là dự đoán một nhãn phân loại cho một đối tƣợng đầu vào gọi là phân loại. -9Chƣơng trình học có giám sát có nhiệm vụ là từ một đối tƣợng đầu vào hợp lệ bất kỳ thì chƣơng trình phải dự đoán đƣợc giá trị của hàm, sau khi đã xem xét một số các cặp đầu vào và đầu ra tƣơng ứng. Chƣơng trình học phải có khả năng tổng quát hóa từ các dữ liệu sẵn có để dự đoán đƣợc những tình huống chƣa gặp phải một cách hợp lý. Mô hình phổ biến nhất của học có giám sát là mô hình toàn cục là mô hình ánh xạ đối tƣợng đầu vào đến đối tƣợng đầu ra mong muốn. Tuy nhiên, trong một số trƣờng hợp, việc ánh xạ đƣợc thực hiện dƣới dạng một tập các mô hình cục bộ. 1.3.2. Cách giải một bài toán học có giám sát Để giải một bài toán học có giám sát ta thực hiện theo các bƣớc sau: Bước 1: Xác định loại của các ví dụ huấn luyện. Đầu tiên ta nên xác định xem loại dữ liệu nào sẽ đƣợc sử dụng làm dữ liệu huấn luyện. Chúng có thể là dữ liệu liên tục hay dữ liệu rời rạc, hoặc một dạng đặt biệt nào đó.Ví dụ: Ta có thể chọn dữ liệu một kí tự viết tay đơn lẻ, toàn bộ một từ viết tay, hay toàn bộ một dòng chữ viết tay, ... Bước 2: Thu thập tập dữ liệu huấn luyện. Khi thu thập tập dữ liệu huấn luyện cần phải đảm bảo đƣợc sự đặc trƣng cho thực tế sử dụng của hàm chức năng. Do đó tập các dữ liệu đầu vào và đầu ra tƣơng ứng phải đƣợc thu thập từ các chuyên gia hoặc từ việc đo dạc tính toán. Bước 3: Xác định việc biễu diễn các đặc trƣng đầu vào cho hàm mục tiêu cần tìm. Độ chính xác của mục tiêu phụ thuộc rất lớn vào các đối tƣợng đầu vào đƣợc biểu diễn nhƣ thế nào. Đa số các đối tƣợng đầu vào đƣợc chuyển đổi thành một véc tơ đặc trƣng chứa các đặc trƣng cơ bản của đối tƣợng đó. Chú ý số - 10 lƣợng các đặc trƣng không đƣợc lớn quá, để tránh sự bùng nổ tổ hợp tuy nhiên nó phải đủ lớn để đảm bảo dự đoán chính xác đầu ra. Bước 4: Xác định cấu trúc của hàm mục tiêu cần tìm và giải thuật học tƣơng ứng. Ví dụ: Ta có thể dụng mạng nơ-ron nhân tạo, cây quyết định, ... Bước 5: Hoàn thiện thiết kế. Tiến hành chạy giải thuật học với tập dữ liệu huấn luyện thu thập đƣợc. Ta có thể điều chỉnh các tham số của giải thuật học bằng cách tối ƣu hóa hiệu năng trên một tập con của tập huấn luyện, hay thông qua kiểm chứng chéo. Sau đó ta tiến hành đo đạc hiệu năng của giải thuật trên một tập dữ liệu kiểm tra độc lập với tập huấn luyện. Các thuật toán sử dụng trong học có giám sát nhƣ: Cây quyết định (Decision Trees), Máy véc tơ hỗ trợ (Support Vector Machine (SVM)), k-láng giềng gần nhất (k-Nearest Neighbor), Cực đại Entropy (Maximum Entropy (MaxEnt)), Naive Bayes,.... 1.3.3. Cực tiểu hóa rủi ro kinh nghiệm Mô hình toàn cục của việc học có giám sát có mục tiêu nhằm tìm ra một hàm g, khi cho sẵn một tập hợp các điểm có dạng (x, g(x)). Giả thiết rằng ta đã biết đặc điểm của hàm g đối với một tập điểm, và tập điểm này đƣợc lấy mẫu độc lập và có cùng phân bố theo một xác suất phân bố p chƣa biết từ một tập lớn hơn hoặc có thể vô hạn. Ta cũng giả thiết tồn tại một hàm tổn thất theo tác vụ L có dạng: L: Y × Y → R+. Trong đó miền xác định của Y trùng với miền xác định của g và L ánh xạ tới các số thực không âm. Giá trị L(z, y) là giá trị tổn thất sinh ra khi đoán giá trị của g tại một điểm z cho trƣớc khi mà giá trị thực của nó là y. - 11 Ta định nghĩa hàm rủi ro f: Là giá trị kỳ vọng của hàm tổn thất, có công thức là: R( f )   L( f ( xi ), g ( xi )) p( xi ) nếu xác suất phân bố p là rời rạc. Trong trƣờng hợp xác suất phân bố liên tục cần một tích phân xác định và một hàm mật độ xác suất. Mục tiêu là tìm một hàm f* sao cho rủi ro R(f*) là cực tiểu trong số một lớp con cố định các hàm. Thông thƣờng, ta chỉ có thể xác định gần đúng với rủi ro thực sự vì thƣờng ta chỉ biết đƣợc đặc điểm của hàm g cho một tập hữu hạn điểm (x1, y1), ..., (xn, yn). Ví dụ: Với rủi ro kinh nghiệm (empirical risk) ta có công thức: 1 n R n ( f )   L( f ( xi ), yi ) n i1 ~ Đối với rủi ro kinh nghiện ta có nguyên tắc cực tiểu hóa rủi ro kinh nghiệm bằng cách chọn hàm f* để rủi ro kinh nghiệm là nhỏ nhất. 1.4. Học không có giám sát 1.4.1. Khái niệm Học không có giám sát là một phƣơng pháp học máy mà dữ liệu huấn luyện là dữ liệu hoàn toàn chƣa đƣợc gán nhãn, nhằm tìm ra một mô hình phù hợp với các quan sát [1]. Học không có giám sát khác với học có giám sát ở chỗ, là đầu ra đúng tƣơng ứng cho mỗi đầu vào là chƣa biết trƣớc. Trong học không có giám sát, một tập dữ liệu đầu vào thƣờng đƣợc thu thập một cách ngẫu nhiên, và sau đó một mô hình mật độ kết hợp sẽ đƣợc xây dựng cho tập dữ liệu đó. - 12 Ta có thể kết hợp học không có giám sát với suy diễn Bayes để tạo ra xác suất có điều kiện cho bất kỳ biến ngẫu nhiên nào khi biết trƣớc các biến khác. Hay nói cách khác khi đó ta đã chuyển từ việc học không có giám sát sang học có giám sát. Mọi giải thuật nén dữ liệu, về cơ bản hoặc là dựa vào một phân bố xác suất trên một tập đầu vào một cách tƣờng minh hay không tƣờng minh. Do đó trong công nghệ nén dữ liệu học không có giám sát đƣợc ứng dụng một cách rất hữu dụng. * Mô hình toán học - Cho X = (x1, x2, …, xn) là tập hợp gồm n mẫu. - Ta giả thiết rằng mẫu đƣợc tạo ra một cách độc lập và giống nhau từ một phân phối chung trên X. - Mục tiêu là tìm ra một cấu trúc thông minh trên tập dữ liệu X. 1.4.2. Phân cụm dữ liệu Một ứng dụng của học không giám sát là phân cụm dữ liệu (data clustering). Phân cụm đƣợc xem nhƣ vấn đề quan trọng nhất trong học không giám sát, vì nhƣ các vấn đề khác của phân cụm dữ liệu, nó có liên quan tới việc tìm kiếm một cấu trúc trong một tập các dữ liệu không có nhãn. Một định nghĩa rộng hơn về phân cụm: “ phân cụm là quá trình tổ chức các đối tƣợng dữ liệu vào trong các nhóm trong đó các đối tƣợng giống nhau theo một cách nào đó”. Do đó, một cụm là một tập hợp các đối tƣợng mà giữa chúng có sự giống nhau và khác với các đối tƣợng thuộc về các cụm khác. - 13 - Hình 1.2: Minh họa phân cụm dữ liệu. Trong ví dụ trên, chúng ta có thẻ dễ dàng xác định đƣợc 4 cụm mà trong đó dữ liệu đƣợc phân chia. Tiêu chí giống nhau ở đây là “khoảng cách”, hai hay nhiều đối tƣợng thuộc về một cụm nếu chúng gần nhau hơn dựa theo khoảng cách đƣa ra. Điều này gọi là phân cụm dựa trên khoảng cách. Một dạng khác của phân cụm là Phân cụm khái niệm, hai hay nhiều đối tƣợng thuộc về một cụm nếu ta định nghĩa một khái niệm phổ biến cho tất cả các đối tƣợng. Tóm lại, các đối tƣợng đƣợc nhóm lại theo điều kiện mô tả chúng. Mục đích của phân cụm dữ liệu Mục đích của việc phân cụm dữ liệu là để xác định các nhóm trong một tập các dữ liệu không có nhãn. Nhƣng làm thế nào để quyết định đƣợc điều gì tạo nên việc phân cụm tốt. Có thể nói rằng, không có một tiêu chuẩn tuyệt đối nào là tốt nhất, do đó ngƣời sử dụng phải đƣa ra các tiêu chuẩn này để các dữ liệu sau khi đƣợc phân cụm sẽ phù hợp với yêu cầu của ngƣời sử dụng. Các ứng dụng của Phân cụm dữ liệu Các thuật toán phân cụm dữ liệu có thể áp dụng trong nhiều lĩnh vực, ví dụ nhƣ:  Tiếp thị: việc tìm ra các nhóm khách hàng có hành vi giống nhau sẽ đƣa ra một CSDL lớn chứa thông tin khách hàng và thông tin mua sắm của họ.  Sinh học: phân loại động vật và thực vật dựa trên các đặc trƣng của chúng  Thƣ viện: đặt sách - 14  Phân lớp văn bản, phân cụm dữ liệu weblog để xác định các nhóm ngƣời truy cập tƣơng tự nhau. Các yêu cầu với thuật toán phân cụm: Các yêu cầu chính mà một thuật toán phân cụm cần đáp ứng là:  Khả năng mở rộng  Đối xử với các loại thuộc tính khác nhau của đối tƣợng dữ liệu  Phát hiện ra các cụm với hình dạng có thể là bất kỳ.  Tối thiểu hóa yêu cầu cho miền tri thức để xác định các tham số đầu vào.  Khả năng xử lý các dữ liệu tạp và sự chênh lệch,... Các thuật toán đƣợc sử dụng phổ biến nhất hiện nay:K-means, Fuzzy Cmeans, Phân cụm có thứ bậc, Hỗn hợp Gaussian. 1.5. Học tăng cƣờng Học tăng cƣờng là một lĩnh vực con của ngành học máy, nghiên cứu cách thức để một Agent nên chọn thực hiện các hành động nào trong một “môi trƣờng” để cực đại hóa số “phần thƣởng” nào đó. “Môi trƣờng” trong học tăng cƣờng đƣợc biểu diễn dƣới dạng một quá trình trạng thái quyết định hữu hạn Markov (Markov decision process – MDP). Cụ thể hơn, trong học tăng cƣờng, các Agent tƣơng tác với môi trƣờng của nó bằng cách đƣa ra các hành động a1, a2, ... Những hành động này ảnh hƣởng tới trạng thái của môi trƣờng do đó kết quả nhận đƣợc trong Agent lần lƣợt là số phần thƣởng hoặc hình phạt r1, r2,... Mục đích của Agent là học một hành động trong một cách nào đó để cực đại hóa thuộc tính phần thƣởng nó nhận đƣợc (hay cực tiểu hóa rủi ro) trên vòng đời của nó. Khác với học có giám sát, học tăng cƣờng không có các cặp dữ liệu vào hay kết quả đúng, các hành động gần tối ƣu cũng không đƣợc đánh giá đúng sai một cách tƣờng minh.