Luận Văn Thạc Sĩ Về Học Nửa Giám Sát Dựa Trên Đồ Thị và Ứng Dụng

Luận văn thạc sĩ nghiên cứu hay học nửa giám sát dựa trên đồ thị và ứng dụng, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp hoàn thiện trong lĩnh vực y tế.

• Người hướng dẫn: PGS. Đoàn Văn Ban
• Trường học: Trường đại học công nghệ thông tin và truyền thông
• Chuyên ngành: Khoa học máy tính
• Đề tài: Học nửa giám sát dựa trên đồ thị và ứng dụng
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2015
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI MỞ ĐẦU
• 1. CHƯƠNG 1: TỔNG QUAN VỀ CÁC PHƯƠNG PHÁP HỌC MÁY
• 1.1. Giới thiệu về học máy
• 1.2. Các phương pháp học máy
• 1.2.1. Học không giám sát
• 1.2.2. Học tăng cường
• 1.2.3. Học nửa giám sát
• 1.2.4. Một số phương pháp học nửa giám sát
• 1.2.4.1. Phương pháp tự huấn luyện
• 1.2.4.2. Phương pháp đồng huấn luyện
• 1.2.4.3. Phương pháp Máy véc tơ hỗ trợ truyền dẫn
• 1.2.4.4. Phương pháp dựa trên đồ thị
• 2. CHƯƠNG 2: PHƯƠNG PHÁP HỌC NỬA GIÁM SÁT DỰA TRÊN ĐỒ THỊ
• 2.1. Các loại đồ thị phổ biến có thể sử dụng trong học nửa giám sát
• 2.1.1. Đồ thị kết nối đầy đủ
• 2.1.2. Đồ thị rời rạc
• 2.1.3. Đồ thị - láng giềng gần nhất
• 2.1.4. Đồ thị trọng số exp
• 2.2. Các phương pháp xác định khoảng cách giữa các điểm dữ liệu
• 2.2.1. Khoảng cách cục bộ, khoảng cách toàn cục và trọng số
• 2.2.2. Khoảng cách Hamming
• 2.2.3. Khoảng cách Manhattan cho các thuộc tính số học
• 2.2.4. Các hàm khoảng cách cục bộ không đồng nhất
• 2.2.5. Hàm khoảng cách tri thức chuyên gia
• 2.3. Thuật toán lan truyền nhãn trong đồ thị
• 2.3.1. Nội dung thuật toán
• 2.3.2. Sự hội tụ của thuật toán
• 2.4. Phương pháp xác định siêu tham số của đồ thị
• 2.5. Độ phức tạp của thuật toán
• 2.6. Thuật toán học nửa giám sát dựa trên đồ thị - Mincut
• 2.7. Các trường Gaussian ngẫu nhiên và các hàm điều hòa
• 2.7.1. Các trường Gaussian ngẫu nhiên
• 2.8. Kết luận chương
• 3. CHƯƠNG 3: CÀI ĐẶT VÀ THỬ NGHIỆM THUẬT TOÁN
• 3.1. Mô tả bài toán
• 3.2. Mô tả dữ liệu đầu vào
• 3.3. Trích chọn đặc trưng
• 3.4. Cài đặt và thử nghiệm
• 3.4.1. Môi trường cài đặt và thử nghiệm
• 3.4.2. Các chức năng của chương trình
• 3.4.3. Kết quả thực nghiệm và đánh giá độ phức tạp
• KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về Học Nửa Giám Sát Dựa Trên Đồ Thị

Học nửa giám sát dựa trên đồ thị là một lĩnh vực quan trọng trong học máy, kết hợp giữa dữ liệu đã gán nhãn và chưa gán nhãn. Phương pháp này giúp cải thiện độ chính xác của mô hình học máy bằng cách sử dụng cấu trúc đồ thị để khai thác thông tin từ dữ liệu chưa gán nhãn. Đồ thị cung cấp một cách tiếp cận mạnh mẽ để mô hình hóa mối quan hệ giữa các điểm dữ liệu, từ đó tối ưu hóa quá trình học.

1.1. Định nghĩa và Ý nghĩa của Học Nửa Giám Sát

Học nửa giám sát là phương pháp sử dụng cả dữ liệu có nhãn và không có nhãn để huấn luyện mô hình. Điều này giúp giảm thiểu chi phí gán nhãn và tận dụng tối đa dữ liệu có sẵn. Theo nghiên cứu, phương pháp này có thể cải thiện đáng kể độ chính xác của các mô hình học máy.

1.2. Lịch sử Phát triển của Học Nửa Giám Sát

Học nửa giám sát đã phát triển từ những năm 1990, với sự gia tăng nhu cầu về các phương pháp học hiệu quả trong bối cảnh dữ liệu lớn. Các nghiên cứu ban đầu đã chỉ ra rằng việc kết hợp dữ liệu có nhãn và không có nhãn có thể dẫn đến kết quả tốt hơn so với việc chỉ sử dụng một loại dữ liệu.

II. Vấn đề và Thách thức trong Học Nửa Giám Sát Dựa Trên Đồ Thị

Mặc dù học nửa giám sát có nhiều lợi ích, nhưng vẫn tồn tại một số thách thức lớn. Một trong những vấn đề chính là việc xác định cách thức tối ưu để kết hợp dữ liệu có nhãn và không có nhãn. Ngoài ra, việc xây dựng đồ thị phù hợp để mô hình hóa mối quan hệ giữa các điểm dữ liệu cũng là một thách thức không nhỏ.

2.1. Khó khăn trong Việc Gán Nhãn Dữ Liệu

Gán nhãn dữ liệu là một quá trình tốn thời gian và chi phí. Nhiều nghiên cứu đã chỉ ra rằng việc có quá ít dữ liệu gán nhãn có thể dẫn đến việc mô hình học không chính xác. Do đó, việc tìm kiếm các phương pháp tự động hóa gán nhãn là rất cần thiết.

2.2. Thách thức trong Xây dựng Đồ Thị

Xây dựng đồ thị phù hợp để mô hình hóa mối quan hệ giữa các điểm dữ liệu là một thách thức lớn. Đồ thị cần phải phản ánh chính xác cấu trúc của dữ liệu để có thể tối ưu hóa quá trình học. Việc lựa chọn loại đồ thị và cách thức kết nối giữa các điểm dữ liệu là rất quan trọng.

III. Phương Pháp Học Nửa Giám Sát Dựa Trên Đồ Thị Hiệu Quả

Có nhiều phương pháp học nửa giám sát dựa trên đồ thị, trong đó nổi bật là phương pháp tự huấn luyện và đồng huấn luyện. Những phương pháp này cho phép tận dụng tối đa thông tin từ dữ liệu chưa gán nhãn, từ đó cải thiện độ chính xác của mô hình.

3.1. Phương Pháp Tự Huấn Luyện

Phương pháp tự huấn luyện cho phép mô hình tự động gán nhãn cho dữ liệu chưa gán nhãn dựa trên các dự đoán từ dữ liệu đã gán nhãn. Nghiên cứu cho thấy phương pháp này có thể cải thiện đáng kể độ chính xác của mô hình học máy.

3.2. Phương Pháp Đồng Huấn Luyện

Phương pháp đồng huấn luyện sử dụng nhiều mô hình học khác nhau để gán nhãn cho dữ liệu chưa gán nhãn. Điều này giúp tăng cường độ chính xác và độ tin cậy của các dự đoán. Các nghiên cứu đã chỉ ra rằng phương pháp này có thể mang lại kết quả tốt hơn so với việc sử dụng một mô hình đơn lẻ.

IV. Ứng Dụng Thực Tiễn của Học Nửa Giám Sát Dựa Trên Đồ Thị

Học nửa giám sát dựa trên đồ thị đã được áp dụng rộng rãi trong nhiều lĩnh vực, từ nhận dạng hình ảnh đến phân tích ngữ nghĩa trong văn bản. Những ứng dụng này cho thấy tiềm năng lớn của phương pháp này trong việc giải quyết các bài toán thực tiễn.

4.1. Ứng Dụng trong Nhận Dạng Hình Ảnh

Trong lĩnh vực nhận dạng hình ảnh, học nửa giám sát giúp cải thiện độ chính xác của các mô hình phân loại hình ảnh bằng cách sử dụng dữ liệu chưa gán nhãn từ internet. Nghiên cứu cho thấy rằng việc kết hợp dữ liệu này có thể dẫn đến kết quả tốt hơn so với việc chỉ sử dụng dữ liệu đã gán nhãn.

4.2. Ứng Dụng trong Phân Tích Ngữ Nghĩa

Học nửa giám sát cũng được áp dụng trong phân tích ngữ nghĩa, giúp cải thiện khả năng hiểu biết của máy tính về ngôn ngữ tự nhiên. Việc sử dụng đồ thị để mô hình hóa mối quan hệ giữa các từ và cụm từ đã cho thấy hiệu quả cao trong việc cải thiện độ chính xác của các mô hình phân tích ngữ nghĩa.

V. Kết Luận và Tương Lai của Học Nửa Giám Sát Dựa Trên Đồ Thị

Học nửa giám sát dựa trên đồ thị đang trở thành một lĩnh vực nghiên cứu quan trọng trong học máy. Với sự phát triển của công nghệ và dữ liệu lớn, tiềm năng ứng dụng của phương pháp này sẽ ngày càng mở rộng. Nghiên cứu trong tương lai cần tập trung vào việc cải thiện các thuật toán và ứng dụng thực tiễn của học nửa giám sát.

5.1. Xu Hướng Nghiên Cứu Tương Lai

Trong tương lai, nghiên cứu sẽ tập trung vào việc phát triển các thuật toán học nửa giám sát hiệu quả hơn, có khả năng xử lý dữ liệu lớn và phức tạp. Điều này sẽ mở ra nhiều cơ hội mới trong các lĩnh vực như y tế, tài chính và công nghệ thông tin.

5.2. Tiềm Năng Ứng Dụng Mới

Học nửa giám sát dựa trên đồ thị có tiềm năng ứng dụng trong nhiều lĩnh vực mới, bao gồm phân tích dữ liệu lớn và trí tuệ nhân tạo. Việc phát triển các ứng dụng này sẽ giúp nâng cao khả năng ra quyết định và tối ưu hóa quy trình làm việc trong nhiều ngành công nghiệp.

Trích đoạn nội dung tài liệu

LỜI MỞ ĐẦU 1. 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ự. Lĩnh vực học máy truyền thống thƣờng đƣợc chia thành bốn lĩnh vực con, bao gồm: Học có giám sát (Supervised learning), Học không giám sát (Unsupervised learning), Học nửa giám sát (Semi-Supervised learning) và Học tăng cƣờng (Reinforcement learning).

Học nửa giám sát sử dụng cả dữ liệu đã gán nhãn và chƣa gán nhãn để huấn luyện - điển hình là một lƣợng nhỏ dữ liệu có gán nhãn cùng với lƣợng lớn dữ liệu chƣa gán nhãn. Học nửa giám sát đứng giữa học không giám sát (không có bất kì dữ liệu có nhãn nào) và có giám sát (toàn bộ dữ liệu đều đƣợc gán nhãn). Để gán nhãn dữ liệu cho một bài toán học máy thƣờng đòi hỏi một phân loại bằng tay các ví dụ huấn luyện. Chi phí cho quy trình này khiến tập dữ liệu đƣợc gán nhãn hoàn toàn trở nên không khả thi, trong khi dữ liệu không.

Trong tình huống đó, học nửa giám sát có giá trị thực tiễn lớn lao. Chính vì vậy, học nửa giám sát là sự kết hợp một số lƣợng lớn các dữ liệu chƣa đƣợc gán nhãn cùng với các dữ liệu đã đƣợc gán nhãn để xây dựng các bộ phân lớp tốt hơn. Một số phƣơng pháp điển hình trong lĩnh vực này đƣợc kể đến nhƣ: Phƣơng pháp EM với mô hình sinh hỗn hợp (EM with generative mixture models), phƣơng pháp Tự huấn luyện (Self-training), phƣơng pháp Đồng huấn luyện (Co-training), phƣơng pháp máy véc tơ hỗ trợ (Transductive support vector machines) và phƣơng pháp Dựa trên đồ thị (Graph-based). Trong đó phƣơng pháp học nửa giám sát dựa trên đồ thị (Graph-based) đang là hƣớng nghiên cứu mở và đem lại hiệu quả lớn.

Với những lý do trên, tác giả đã chọn đề tài “ Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] ” làm đề tài nghiên cứu luận văn tốt nghiệp thạc sĩ chuyên ngành Khoa học máy tính. Nghiên cứu tổng quan về học nửa giám sát và một số phƣơng pháp học nửa giám sát. Nghiên cứu phƣơng pháp học nửa giám sát dựa trên đồ thị Cài đặt thử nghiệm thuật toán lan truyền nhãn trên đồ thị và thuật toán tự huấn luyện. Đối tượng nghiên cứu: Học nửa giám sát.

Phạm vi nghiên cứu: - Nghiên cứu tổng quan về học có giám sát, học không giám sát và học nửa giám sát. - Các phƣơng pháp học nửa giám sát phổ biến. - Phƣơng pháp học nửa giám sát dựa trên đồ thị (Graph-based) và một số thuật toán. - Cài đặt thử nghiệm thuật toán lan truyền nhãn trong phƣơng pháp học nửa giám sát dựa trên đồ thị và thuật toán tự huấn luyện.

Các luận điểm chính mà luận văn đã thể hiện đƣợc: Nghiên cứu tổng quan và đánh giá các phƣơng pháp học nửa giám sát, tập trung vào phƣơng pháp học nửa giám sát dựa trên đồ thị. Tập trung tìm hiểu một số thuật toán trong lĩnh vực học nửa giám sát nhƣ: Phƣơng pháp EM với mô hình sinh hỗn hợp, phƣơng pháp Tự huấn luyện, phƣơng pháp Đồng huấn luyện và phƣơng pháp máy véc tơ hỗ trợ. Đồng thời tập trung nghiên cứu chi tiết phƣơng pháp dựa trên đồ thị. Cài đặt phần mềm thử nghiệm mô phỏng thuật toán lan truyền nhãn và thuật toán tự huấn luyện, đánh giá độ phức tạp của hai thuật toán này.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] - Đọc tài liệu, phân tích, tổng hợp. - Thống kê, phân tích dữ liệu. - Thực nghiệm và đánh giá kết quả. - Kết hợp nghiên cứu lý thuyết, tìm hiểu tình hình ứng dụng, đánh giá khả năng ứng dụng và đề xuất giải pháp.

Nội dung luận văn gồm 03 chƣơng: Chƣơng 1: Tổng quan về các phƣơng pháp học máy Chƣơng này trình bày tổng quan về các phƣơng pháp học máy gồm phƣơng pháp Học có giám sát (Supervised learning), Học không giám sát (Unsupervised learning), Học nửa giám sát (Semi-Supervised learning). Chƣơng 2: Phƣơng pháp học nửa giám sát dựa trên đồ thị Tập trung tìm hiểu một số thuật toán trong lĩnh vực học nửa giám sát nhƣ: Phƣơng pháp EM với mô hình sinh hỗn hợp, phƣơng pháp Tự huấn luyện, phƣơng pháp Đồng huấn luyện và phƣơng pháp máy véc tơ hỗ trợ. Đồng thời tập trung nghiên cứu chi tiết phƣơng pháp dựa trên đồ thị. Chƣơng 3: Cài đặt và thử nghiệm thuật toán Cài đặt thử nghiệm thuật toán tự huấn luyện và lan truyền nhãn dựa trên đồ thị.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] CHƢƠNG 1: TỔNG QUAN VỀ CÁC PHƢƠNG PHÁP HỌC MÁY 1. Giới thiệu về học máy Học máy (Machine Learning) là một ngành khoa học nghiên cứu các thuật toán cho phép máy tính có thể học đƣợc các khái niệm (concept)[7]. 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. Các ngành khoa học liên quan đến lĩnh vực học máy điển hình là: 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.

Lĩnh vực học máy truyền thống thƣờng đƣợc chia thành bốn lĩnh vực con: Học có giám sát: Máy tính đƣợc xem một số mẫu gồm đầu vào và đầu ra tƣơng ứng trƣớc. Sau khi học xong các mẫu này, máy tính quan sát một đầu vào mới và cho ra kết quả. Học không giám sát: Máy tính chỉ đƣợc xem các mẫu không có đầu ra, sau đó máy tính phải tự tìm cách phân loại các mẫu này và các mẫu mới. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] Học nửa giám sát: Một dạng lai giữa hai nhóm giải thuật trên.

Học tăng cƣờng: Máy tính đƣa ra quyết định hành động và nhận kết quả phản hồi từ môi trƣờng. Sau đó máy tính tìm cách chỉnh sửa cách ra quyết định hành động của mình. 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. Trong đó phải kể đến các ứng dụng quan trọng nhất của nó trong khai phá dữ liệu. Khai phá dữ liệu (Data mining) là quá trình khám phá các tri thức mới và các tri thức có ích ở dạng tiềm năng trong nguồn dữ liệu đã có. Khai phá dữ liệu là một bƣớc của quá trình khai phá tri thức, bao gồm: Xác định vấn đề và không gian dữ liệu để giải quyết vấn đề.

Chuẩn bị dữ liệu, bao gồm các quá trình làm sạch dữ liệu, tích hợp dữ liệu, chọn dữ liệu, biến đổi dữ liệu. Khai phá dữ liệu: xác định nhiệm vụ khai phá dữ liệu và lựa chọn kĩ thuật khai phá dữ liệu. Kết quả cho ta một nguồn tri thức thô. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] Đánh giá: dựa trên một số tiêu chí tiến hành kiểm tra và lọc nguồn tri thức thu đƣợc.

Quá trình khai phá tri thức không chỉ là một quá trình tuần tự từ bƣớc đầu tiên đến bƣớc cuối cùng mà là một quá trình lặp và có quay trở lại các bƣớc đã qua. Về cơ bản, khai phá dữ liệu có thể ứng dụng cho bất kỳ kho thông tin nào bao gồm: Các cơ sở dữ liệu quan hệ, kho dữ liệu, các cơ sở dữ liệu giao tác, các hệ thống cơ sở dữ liệu tiên tiến, các tệp,. Phân lớp dữ liệu Phân lớp dữ liệu là kĩ thuật dựa trên tập dữ liệu huấn luyện và những giá trị trong một thuộc tính phân lớp (hay còn gọi là nhãn của lớp), sử dụng nó trong việc phân lớp dữ liệu mới. Phân lớp cũng là tiên đoán loại lớp của nhãn.

Bên cạnh kĩ thuật phân lớp còn có một hình thức tƣơng tự gọi là kĩ thuật tiên đoán, kĩ thuật tiên đoán khác với phân lớp ở chỗ phân lớp chỉ liên quan đến tiên đoán loại lớp của nhãn còn kĩ thuật tiên đoán mô hình những hàm đánh giá liên tục[6]. Kĩ thuật phân lớp đƣợc tiến hành bao gồm 2 bƣớc: Xây dựng mô hình và sử dụng mô hình. Xây dựng mô hình: là mô tả một tập những lớp đƣợc định nghĩa trƣớc, trong đó mỗi bộ hoặc mẫu đƣợc gán thuộc về một lớp đƣợc định nghĩa trƣớc nhƣ là đƣợc xát định bởi thuộc tính nhãn lớp, tập hợp của những bộ đƣợc sử dụng trong việc sử dụng mô hình đƣợc gọi là tập huấn luyện. Mô hình đƣợc biểu diễn là những luật phân lớp, cây quyết định và những công thức toán học .