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.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên bùng nổ dữ liệu số, việc thu thập dữ liệu thô diễn ra với tốc độ cấp số nhân, nhưng chi phí gán nhãn thủ công cho toàn bộ tập dữ liệu thường chiếm từ 70% đến 85% tổng ngân sách và thời gian của các dự án trí tuệ nhân tạo. Trong khi các thuật toán học có giám sát truyền thống đòi hỏi 100% mẫu dữ liệu phải được dán nhãn chính xác bởi chuyên gia, nguồn dữ liệu chưa gán nhãn lại chiếm tới hơn 95% tổng dung lượng sẵn có trong thực tế. Vấn đề cốt lõi đặt ra là làm thế nào để khai thác triệt để nguồn tài nguyên dữ liệu chưa gán nhãn dồi dào với chi phí thấp nhằm nâng cao hiệu quả phân lớp. Luận văn thạc sĩ chuyên ngành Khoa học máy tính tại Đại học Thái Nguyên, hoàn thành vào tháng 4 năm 2015, tập trung giải quyết bài toán tối ưu hóa mô hình học máy thông qua đề tài "Học nửa giám sát dựa trên đồ thị và ứng dụng". Mục tiêu trọng tâm của công trình là nghiên cứu hệ thống lý thuyết về học nửa giám sát (Semi-Supervised Learning), phân tích sâu cơ chế hoạt động của các phương pháp biểu diễn đồ thị, đồng thời thiết kế và cài đặt thực nghiệm thuật toán lan truyền nhãn (Label Propagation) cùng phương pháp tự huấn luyện (Self-training). Phạm vi nghiên cứu bao gồm việc khảo sát các cấu trúc đồ thị từ không gian 2 chiều đến đa chiều, ứng dụng phân loại trên tập dữ liệu tin nhắn văn bản mẫu. Ý nghĩa thực tiễn của đề tài được thể hiện qua việc giảm thiểu tới hơn 60% chi phí gán nhãn dữ liệu ban đầu, đồng thời cải thiện độ chính xác phân lớp lên khoảng 12% đến 18% so với việc chỉ sử dụng lượng nhỏ dữ liệu gán nhãn ban đầu trên các mô hình có giám sát truyền thống.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu xây dựng trên nền tảng của lý thuyết học máy hiện đại, kết hợp chặt chẽ giữa lý thuyết học thống kê (Statistical Learning Theory) và lý thuyết quang phổ đồ thị (Spectral Graph Theory). Hệ thống khái niệm cốt lõi bao gồm: học nửa giám sát (Semi-Supervised Learning), cấu trúc đồ thị dữ liệu (Graph Construction), ma trận Laplacian đồ thị, và cơ chế hàm điều hòa kết hợp trường ngẫu nhiên Gaussian (Gaussian Random Fields - GRF). Trong mô hình học nửa giám sát dựa trên đồ thị, tập dữ liệu tổng thể gồm n phần tử được chia thành tập có nhãn L với kích thước l phần tử và tập chưa có nhãn U với kích thước u phần tử, trong đó tỷ lệ dữ liệu chưa gán nhãn luôn chiếm ưu thế vượt trội với u gấp từ 10 đến 100 lần l. Mô hình chuyển đổi toàn bộ không gian dữ liệu thành một đồ thị vô hướng G = (V, E, W), trong đó tập đỉnh V biểu diễn các điểm dữ liệu và ma trận trọng số W thể hiện mức độ tương đồng cục bộ. Lý thuyết hàm điều hòa chứng minh rằng giá trị nhãn tại mỗi đỉnh chưa biết f(i) là trung bình trọng số của các đỉnh láng giềng, cực tiểu hóa hàm năng lượng bậc 2 và đảm bảo tính mượt trên toàn bộ cấu trúc topo đồ thị.

Phương pháp nghiên cứu

Quá trình nghiên cứu được triển khai thực nghiệm từ tháng 10 năm 2014 đến tháng 4 năm 2015 với dữ liệu thử nghiệm gồm 1.200 mẫu văn bản tin nhắn, được chia theo tỷ lệ 15% mẫu có nhãn và 85% mẫu chưa gán nhãn nhằm phản ánh trung thực môi trường thực tế. Phương pháp chọn mẫu phân tầng ngẫu nhiên được áp dụng để đảm bảo sự cân bằng giữa các lớp dữ liệu nhị phân. Dữ liệu văn bản sau khi thu thập được tiền xử lý qua các bước chuẩn hóa, loại bỏ từ dừng và trích chọn đặc trưng theo mô hình không gian vector với độ dài 250 chiều đặc trưng. Lý do lựa chọn thuật toán lan truyền nhãn và phương pháp cây khung nhỏ nhất (Minimum Spanning Tree - Kruskal) là khả năng tìm nghiệm giải tích trực tiếp qua phép nghịch đảo ma trận khối mà không yêu cầu xấp xỉ đạo hàm phức tạp, giúp giảm thời gian hội tụ xuống dưới 35 chu kỳ lặp và kiểm soát siêu tham số sigma theo quy tắc phân phối 3-sigma với độ chính xác đạt trên 90%.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Thực nghiệm kiểm thử trên chương trình mô phỏng đã chỉ ra 4 phát hiện quan trọng mang tính đột phá về hiệu năng thuật toán: Thứ nhất, thuật toán lan truyền nhãn (Label Propagation) đạt độ chính xác trung bình 92,4% trên tập kiểm tra khi chỉ cần sử dụng 10% dữ liệu gán nhãn ban đầu, vượt trội hơn 14,6% so với thuật toán tự huấn luyện (Self-training) vốn chỉ đạt 77,8% trong cùng điều kiện thực nghiệm. Thứ hai, việc xác định siêu tham số khoảng cách sigma bằng phương pháp cây khung nhỏ nhất (Kruskal) giúp giảm thiểu tỷ lệ lỗi gán nhãn sai từ 18,2% xuống còn 6,5%, tạo nên đường biên phân lớp rõ ràng giữa các cụm mật độ dữ liệu cao. Thứ ba, đồ thị k-láng giềng gần nhất (k-NN) với giá trị k thiết lập từ 5 đến 8 mang lại hiệu quả tính toán tối ưu, giảm hơn 45% thời gian tạo ma trận kề so với đồ thị kết nối đầy đủ, trong khi vẫn duy trì độ chính xác phân lớp ở mức trên 90%. Thứ tư, khi tăng tỷ lệ dữ liệu chưa gán nhãn từ 500 lên 1.000 mẫu, độ chính xác của mô hình đồ thị tăng tuyến tính thêm 5,3%, khẳng định giả thuyết rằng khối lượng dữ liệu chưa gán nhãn càng lớn thì mật độ phân bố quang phổ càng được làm mịn hiệu quả.

Thảo luận kết quả

Nguyên nhân cốt lõi giúp phương pháp đồ thị vượt trội hơn Self-training là khả năng bảo toàn toàn bộ cấu trúc hình học toàn cục và tận dụng tính chất truyền dẫn của ma trận xác suất chuyển trạng thái. Trong Self-training, sai số phân lớp từ các vòng lặp đầu tiên có xu hướng tích lũy và khuếch đại theo cấp số nhân, khiến mô hình bị lệch hướng nghiêm trọng. Ngược lại, thuật toán lan truyền nhãn cố định nhãn nguồn tại mỗi bước lặp, triệt tiêu hiện tượng trôi dạt dữ liệu. Kết quả này hoàn toàn tương đồng với các công bố học thuật quốc tế giai đoạn 2002-2010 về trường ngẫu nhiên Gaussian, đồng thời khắc phục triệt để điểm nghẽn chi phí tính toán của máy vector hỗ trợ truyền dẫn (TSVM) vốn gặp bài toán quy hoạch phi tuyến NP-khó. Để trực quan hóa hiệu quả nghiên cứu, dữ liệu thử nghiệm có thể được trình bày thông qua biểu đồ đường so sánh tốc độ hội tụ qua 50 vòng lặp giữa hai thuật toán và bảng tổng hợp 5 chỉ số đo lường hiệu năng gồm Accuracy, Precision, Recall, F1-score và thời gian xử lý CPU (ms). Biểu đồ phân tán 2D cũng giúp minh họa rõ nét cách các nhãn lan truyền từ tâm cụm có nhãn ra các vùng biên mật độ thấp.

Đề xuất và khuyến nghị

Để ứng dụng hiệu quả các mô hình học nửa giám sát dựa trên đồ thị vào giải quyết các bài toán công nghệ thực tiễn, luận văn đưa ra 4 nhóm khuyến nghị mang tính chiến lược:

1. Chuẩn hóa quy trình tiền xử lý và trích chọn đặc trưng: Các kỹ sư học máy và chuyên gia dữ liệu tại doanh nghiệp cần thực hiện chuẩn hóa khoảng cách đa chiều và áp dụng kỹ thuật giảm chiều dữ liệu (như PCA hoặc t-SNE) trong quý 1 nhằm giảm hơn 30% nhiễu đặc trưng và tăng tốc độ dựng đồ thị lên 25%.
2. Tự động hóa việc tối ưu siêu tham số cấu trúc đồ thị: Nhóm nghiên cứu và phát triển phần mềm cần triển khai thuật toán cây khung nhỏ nhất Kruskal kết hợp kỹ thuật đánh giá chéo phân tầng trong vòng 3 đến 6 tháng tới, hướng đến mục tiêu kiểm soát tự động tham số sigma để nâng độ chính xác phân lớp lên mức tối thiểu 95%.
3. Tích hợp giải pháp mở rộng quy mô tính toán song song: Các kiến trúc sư hệ thống cần áp dụng các thư viện tính toán ma trận thưa và xử lý đồ thị phân tán trên nền tảng GPU/Spark trong giai đoạn 6 đến 12 tháng, nhằm tối ưu hóa độ phức tạp thuật toán từ bậc 3 xuống tiệm cận tuyến tính, cho phép xử lý tập dữ liệu lớn trên 100.000 mẫu chỉ trong dưới 10 giây.
4. Xây dựng nền tảng gán nhãn bán tự động cho doanh nghiệp: Ban giám đốc công nghệ và các đơn vị viễn thông cần đầu tư phát triển hệ thống lọc tin nhắn rác và phân loại văn bản tự động trong vòng 9 tháng, đặt mục tiêu cắt giảm từ 50% đến 70% ngân sách nhân sự kiểm duyệt thủ công nhưng vẫn duy trì độ tin cậy hệ thống trên 98%.

Đối tượng nên tham khảo luận văn

Tài liệu luận văn là nguồn tham khảo chuyên sâu và thiết thực dành cho 4 nhóm đối tượng trọng tâm sau:

1. Học viên cao học và nghiên cứu sinh ngành Khoa học máy tính: Nắm bắt toàn diện khung toán học của lý thuyết học máy thống kê, tiếp cận các công thức chứng minh sự hội tụ của hàm điều hòa và thuật toán phân lớp trên đồ thị để phát triển đề tài nghiên cứu mới với hơn 10 hướng mở rộng tiềm năng.
2. Kỹ sư trí tuệ nhân tạo và xử lý dữ liệu lớn (Data Scientists): Vận dụng trực tiếp thuật toán lan truyền nhãn vào các bài toán phân loại văn bản, phát hiện gian lận thẻ tín dụng hoặc phân cụm hành vi khách hàng khi chỉ có dưới 5% dữ liệu được gán nhãn chuẩn.
3. Giảng viên và nhà nghiên cứu công nghệ thông tin: Sử dụng cấu trúc nội dung 3 chương chi tiết làm giáo trình tham khảo, tài liệu giảng dạy chuyên đề cao học về khai phá dữ liệu và các kỹ thuật bán giám sát hiện đại.
4. Nhà quản trị công nghệ và kỹ sư phát triển sản phẩm viễn thông: Xây dựng các module lọc spam tin nhắn, phân loại khiếu nại khách hàng tự động với độ chính xác đạt trên 92%, giúp doanh nghiệp tiết kiệm hàng trăm triệu đồng chi phí vận hành mỗi năm.

Câu hỏi thường gặp

1. Học nửa giám sát khác biệt như thế nào so với học có giám sát truyền thống? Học có giám sát đòi hỏi 100% dữ liệu huấn luyện phải được gán nhãn, gây tốn kém chi phí và thời gian. Ngược lại, học nửa giám sát kết hợp một lượng nhỏ dữ liệu có nhãn (khoảng 5% đến 10%) với lượng lớn dữ liệu chưa gán nhãn (90% đến 95%), giúp xây dựng ranh giới phân lớp chính xác hơn và tiết kiệm đáng kể chi phí thu thập mẫu.

2. Tại sao phương pháp lan truyền nhãn dựa trên đồ thị lại vượt trội hơn phương pháp tự huấn luyện? Phương pháp tự huấn luyện (Self-training) dễ tích lũy sai số khi các nhãn dự đoán sai ban đầu tiếp tục được dùng để huấn luyện vòng lặp tiếp theo. Trong khi đó, thuật toán lan truyền nhãn tận dụng toàn bộ cấu trúc topo đồ thị và ma trận xác suất chuyển trạng thái, giúp giảm tỷ lệ lỗi phân lớp từ khoảng 18% xuống dưới 7% trong thực nghiệm.

3. Độ phức tạp tính toán của thuật toán lan truyền nhãn trên đồ thị là bao nhiêu? Độ phức tạp tính toán của quá trình lặp và nghịch đảo ma trận trong thuật toán đạt khoảng O(m nhân n mũ 3), trong đó n là tổng số đỉnh đồ thị và m là số nhãn. Quá trình tính toán ma trận trọng số kề W và ma trận chuyển tiếp P ban đầu có độ phức tạp là O(n bình phương), đảm bảo thời gian xử lý nhanh cho các tập dữ liệu dưới 2.000 điểm.

4. Làm thế nào để lựa chọn siêu tham số khoảng cách sigma tối ưu khi xây dựng đồ thị? Luận văn ứng dụng thuật toán Kruskal xây dựng cây khung nhỏ nhất (MST) trên toàn bộ không gian dữ liệu. Bằng cách tìm cạnh ngắn nhất kết nối hai đỉnh thuộc hai lớp khác nhau với độ dài d0 và thiết lập giá trị sigma bằng d0 chia 3 theo quy tắc 3-sigma, trọng số cạnh giữa các cụm khác lớp sẽ tiệm cận về 0, tối ưu hóa việc phân tách nhãn.

5. Thuật toán phân lớp đồ thị có thể ứng dụng trong các bài toán thực tế nào? Mô hình có tính ứng dụng cao trong phân loại tin nhắn rác viễn thông, nhận dạng chữ viết tay, phân tích hình ảnh y tế (như ảnh X-quang), phân tầng protein trong tin sinh học và phát hiện giao dịch gian lận tài chính. Trong thực nghiệm phân loại tin nhắn với 1.200 mẫu, mô hình đạt độ chính xác thực tế vượt mốc 92%.

Kết luận

Nghiên cứu về học nửa giám sát dựa trên đồ thị đã khẳng định tiềm năng vượt bậc trong việc giải quyết bài toán khan hiếm dữ liệu có nhãn của kỷ nguyên số:

• Hệ thống hóa hoàn chỉnh cơ sở lý thuyết và mô hình toán học của 4 phương pháp học nửa giám sát điển hình gồm Self-training, Co-training, TSVM và Graph-based.
• Làm rõ nguyên lý lan truyền nhãn thông qua ma trận xác suất chuyển tiếp và nghiệm giải tích điều hòa trên trường ngẫu nhiên Gaussian.
• Đề xuất quy trình tối ưu siêu tham số đồ thị hiệu quả dựa trên thuật toán cây khung nhỏ nhất Kruskal với độ chính xác đạt trên 92%.
• Triển khai thành công phần mềm thử nghiệm mô phỏng phân loại tin nhắn văn bản, chứng minh thuật toán đồ thị giảm hơn 45% thời gian xử lý so với đồ thị toàn thể.
• Đóng góp giải pháp khoa học giúp giảm từ 60% đến 80% chi phí gán nhãn thủ công trong các dự án khai phá dữ liệu thực tiễn. Trong lộ trình 12 tháng tới, các nhóm nghiên cứu nên tiếp tục mở rộng mô hình sang đồ thị động nhiều chiều và triển khai tính toán song song trên nền tảng đám mây. Hãy chủ động tải toàn văn luận văn và ứng dụng ngay các thuật toán đồ thị để tối ưu hóa quy trình phân tích dữ liệu cho tổ chức của bạn.

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 .