Nội dung

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- ĐỖ THỊ LƯƠNG NGHIÊN CỨU MỘT SỐ THUẬT TOÁN HỌC MÁY ĐỂ PHÂN LỚP DỮ LIỆU VÀ THỬ NGHIỆM Chuyên ngành: Hệ Thống thông tin Mã số: 8.48.01.04 TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI - NĂM 2019 Luận văn được hoàn thành tại: HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Người hướng dẫn khoa học: Tiến sỹ Vũ Văn Thỏa Phản biện 1: ………………………………………….. Phản biện 2: ………………………………………….. Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công nghệ Bưu chính Viễn thông Vào lúc: ....... giờ ....... ngày ..... tháng ....... năm ......... Có thể tìm hiểu luận văn tại: - Thư viện của Học viện Công nghệ Bưu chính Viễn thông 1 MỞ ĐẦU Trong thời gian gần đây, sự phát triển mạnh mẽ của công nghệ thông tin và các dịch vụ liên quan đã làm số lượng thông tin được trao đổi trên mạng Internet tăng một cách đáng kể. Số lượng thông tin được lưu trữ trong các kho dữ liệu cũng tăng với một tốc độ chóng mặt. Đồng thời, tốc độ thay đổi thông tin là cực kỳ nhanh chóng. Theo thống kê của Broder et al (2003), cứ sau 9 tháng hoặc 12 tháng lượng thông tin được lưu trữ, tìm kiếm và quản lý lại tăng gấp đôi. Hiện nay, loài người đang bước vào kỷ nguyên IoT (Internet of Things – Internet kết nối vạn vật). Thông qua internet, người dùng có nhiều cơ hội để tiếp xúc với nguồn thông tin vô cùng lớn. Tuy nhiên, cùng với nguồn thông tin vô tận đó, người dùng cũng đang phải đối mặt với sự quá tải thông tin. Đôi khi, để tìm được các thông tin cần thiết, người dùng phải chi phí một lượng thời gian khá lớn. Với số lượng thông tin đồ sộ như vậy, một yêu cầu cấp thiết đặt ra là làm sao tổ chức, tìm kiếm và khai thác thông tin (dữ liệu) một cách hiệu quả nhất. Một trong các giải pháp được nghiên cứu để giải quyết vấn đề trên là xây dựng các mô hình tính toán dựa trên các phương pháp học máy nhằm phân loại, khai thác thông tin một cách tự động và trích xuất các tri thức hữu ích. Trong đó, bài toán phân lớp (Classification) dữ liệu có ý nghĩa hết sức quan trọng. Phân lớp dữ liệu là việc xếp các dữ liệu vào những lớp đã biết trước. Ví dụ: Phân lớp sinh viên theo kết quả học tập, phân lớp các loài thực vật, … Bài toán phân lớp dữ liệu thường được giải quyết bằng cách sử dụng một số kỹ thuật học máy như: Thuật 2 toán Bayes (Naive Bayes), Cây quyết định (Decision Tree), Máy vector hỗ trợ (Support Vector Machine), Mạng Nơ-ron nhân tạo (Artificial Neural Network), … Xuất phát từ những lý do trên, học viên chọn thực hiện đề tài luận văn tốt nghiệp chương trình đào tạo thạc sĩ có tên “Nghiên cứu một số thuật toán học máy để phân lớp dữ liệu và thử nghiệm”. Mục tiêu của luận văn là nghiên cứu các kỹ thuật học máy để giải quyết bài toán phân lớp dữ liệu nói chung và thử nghiệm đánh giá hiệu năng của chúng trên bộ dữ liệu KDD cup 99. Nội dung của luận văn được trình bày trong ba chương nội dung chính như sau: Chương 1: Tổng quan về phân lớp dữ liệu và học máy. Nội dung chính của chương 1 là khảo sát tổng quan về bài toán phân lớp dữ liệu, học máy và các vấn đề liên quan. Chương 2: Nghiên cứu một số thuật toán học máy Nội dung chính của chương 2 là nghiên cứu chi tiết một số kỹ thuật học máy để giải quyết bài toán phân lớp dữ liệu và một số vấn đề liên quan. Chương 3: THỬ NGHIỆM VÀ ĐÁNH GIÁ Nội dung chính của chương 3 là thực hiện thử nghiệm và đánh giá các mô hình phân lớp dữ liệu dựa trên các phương pháp học máy đã nghiên cứu trong chương 2 cho bộ dữ liệu KDD cup 99. 3 CHƯƠNG 1. TỔNG QUAN VỀ PHÂN LỚP DỮ LIỆU VÀ HỌC MÁY 1.1. Giới thiệu bài toán phân lớp dữ liệu và các vấn đề liên quan 1.1.1. Khái niệm về phân lớp dữ liệu và bài toán phân lớp dữ liệu Phân lớp (classification) dữ liệu là một tiến trình xử lý nhằm xếp các mẫu dữ liệu hay các đối tượng vào một trong các lớp đã được định nghĩa trước. Các mẫu dữ liệu hay các đối tượng được xếp vào các lớp dựa trên giá trị của các thuộc tính (attributes) của mẫu dữ liệu hay đối tượng. Quá trình phân lớp dữ liệu kết thúc khi tất cả các dữ liệu đã được xếp vào các lớp tương ứng. Khi đó, mỗi lớp dữ liệu được đặc trưng bởi tập các thuộc tính của các đối tượng chứa trong lớp đó. Bài toán phân lớp dữ liệu có thể được mô tả như hình 1.1 dưới đây. Hình 1.1. Bài toán phân lớp dữ liệu Quy trình giải quyết bài toán phân lớp dữ liệu (1) Giai đoạn huấn luyện Quá trình thực hiện giai đoạn học được mô tả trong hình 1.2. Mô hình phân lớp với các lớp Hình 1.2. Giai đoạn xây dựng mô hình phân lớp dữ liệu Dữ liệu HL đã biết TRAINING 4 (2) Giai đoạn kiểm chứng Quá trình thực hiện giai đoạn phân lớp thử nghiệm được mô tả trong hình 1.3. Dữ liệu KC Mô hình Dữ liệu chưa được phân lớp được Hình 1.3. Quá trình kiểm tra đánh giá mô hình phân lớp dữ liệu phân 1.1.2.phân Các lớp độ đo đánh giáhọc mô được hình phân lớp dữ liệulớp (1) Độ đo Precision (Mức chính xác) - Định nghĩa: Precision = TP / (TP + FP). - Ý nghĩa: Giá trị Precision càng cao thể hiện khả năng càng cao để một kết quả phân lớp dữ liệu được đưa ra bởi bộ phân lớp là chính xác. (2) Độ đo Recall (Độ bao phủ, độ nhạy hoặc độ triệu hồi) - Định nghĩa: Recall = TP / (TP + FN). - Ý nghĩa: Giá trị Recall càng cao thể hiện khả năng kết quả đúng trong số các kết quả đưa ra của bộ phân lớp càng cao. (3) Độ đo Accuracy (Độ chính xác) - Định nghĩa: Accuracy = (TP + TN) / (TP + TN + FP + FN) * 100%. - Ý nghĩa: Accuracy phản ánh độ chính xác chung của bộ phân lớp dữ liệu.. (4) Độ đo F-Measure - Định nghĩa: F-Measure = 2.(Precision.Recall) / (Precision + Recall). - Ý nghĩa: F-Measure là độ đo nhằm đánh giá độ chính xác thông qua quá trình kiểm chứng dựa trên sự xem xét đến hai độ đo là Precision và Recall. Giá trị FMeasure càng cao phản ánh độ chính xác càng cao của bộ 5 phân lớp dữ liệu. Có thể coi độ đo F-Measure là trung bình điều hoà của hai độ đo Precision và Recall. (5) Độ đo Specitivity (Độ đặc hiệu) - Định nghĩa: Specitivity = TN/(TN+FP). - Ý nghĩa: Độ đo Specitivity đánh giá khả năng một dữ liệu là phần tử âm được bộ phân lớp cho ra kết quả chính xác. 1.1.3. Các phương pháp đánh giá mô hình phân lớp dữ liệu Phương pháp Hold-out Phương pháp k-fold cross validation 1.1.4. Các ứng dụng của bài toán phân lớp dữ liệu 1.2. Tổng quan về học máy 1.2.1. Khái niệm về học máy và phân loại các kỹ thuật học máy a. Khái niệm về học máy Học máy là một lĩnh vực của trí tuệ nhân tạo liên quan đến việc nghiên cứu và xây dựng các kĩ thuật cho phép các hệ thống "học" tự động từ dữ liệu để giải quyết những vấn đề cụ thể . b. Phân loại các kỹ thuật học máy Học có giám sát Học không giám sát Học bán giám sát 1.2.2. Ứng dụng học máy xây dựng mô hình phân lớp dữ liệu 1.3. Giới thiệu chung về học sâu 1.3.1. Khái niệm về học sâu Học sâu là một chi của ngành học máy dựa trên một tập hợp các thuật toán để cố gắng mô hình dữ liệu trừu tượng hoá ở mức cao bằng cách sử dụng nhiều lớp xử 6 lý với cấu trúc phức tạp, hoặc bằng cách khác bao gồm nhiều biến đổi phi tuyến. Các quá trình học sâu có thể mô tả như trong hình 1.4 Hình 1.4. Các quá trình học sâu 1.3.2. Hướng tiếp cận học sâu Hướng tiếp cận học sâu đầu tiên thường được kể đến là các mạng nơ-ron sâu. Dưới đây, luận văn liệt kê một số dạng mạng nơ-ron sâu tham khảo trên mạng Internet. Mạng nơ-ron tích chập Mạng nơ-ron lặp Mạng nơ-ron chuyển đổi Học tăng cường 1.4. Kết luận chương 1 Trong chương 1 của luận văn đã giới thiệu bài toán phân lớp dữ liệu và khảo sát quy trình phân lớp dữ liệu cũng như các độ đo đánh giá các mô hình phân lớp dữ liệu và các ứng dụng khác nhau của phân lớp dữ liệu. Trong chương này luận văn cũng trình bày tổng quan về các học máy và giới thiệu về học sâu. Trong chương tiếp theo luận văn sẽ nghiên cứu ba thuật toán học máy để xây dựng mô hình phân lớp là cây quyết định, Bayes và máy vectơ hỗ trợ. 7 CHƯƠNG 2. NGHIÊN CỨU MỘT SỐ THUẬT TOÁN HỌC MÁY 2.1. Khảo sát thuật toán cây quyết định và các vấn đề liên quan 2.1.1. Giới thiệu phương pháp Cây quyết định là một cấu trúc ra quyết định có dạng cây. Cây quyết định nhận đầu vào là một bộ giá trị các thuộc tính mô tả một đối tượng hay một tình huống và trả về một giá trị rời rạc. Mỗi bộ thuộc tính đầu vào được gọi là một mẫu hay một ví dụ, đầu ra gọi là lớp hay nhãn phân lớp. Khi đó, với tập thuộc tính đầu vào được cho dưới dạng véc tơ x, nhãn phân lớp đầu ra được ký hiệu là y thì cây quyết định có thể xem như một hàm f(x) = y. Cây quyết định được biểu diễn dưới dạng một cấu trúc cây như trong Hình 2.1 dưới đây. Hình 2.1. Mô hình cây quyết định 2.1.2. Xây dựng cây quyết định dựa trên Entropy 2.1.3. Đánh giá phương pháp Mô hình phân lớp dữ liệu sử dụng cây quyết định có các ưu điểm sau đây. 8 - Cây quyết định tự giải thích và khi được gắn kết lại, chúng có thể dễ dàng tự sinh ra. - Cây quyết định có thể xử lý được nhiều kiểu các thuộc tính đầu vào. Cây quyết định được xem như là một phương pháp phi tham số. Bên cạnh đó, cây quyết định cũng có những nhược điểm 2.2. Khảo sát thuật toán Bayes và các vấn đề liên quan 2.2.1. Giới thiệu phương pháp Ý tưởng cơ bản của cách tiếp cận phân lớp dữ liệu Bayes là sử dụng công thức Bayes về xác suất có điều kiện để lựa chọn kết quả phân lớp là sự kiện có xác suất lớn nhất. Công thức Bayes: (2.2) Trong đó: - H (Hypothesis) là giả thuyết và E (Evidence) là chứng cứ hỗ trợ cho giả thuyết H. - P(E|H): xác suất E xảy ra khi H xảy ra (xác suất có điều kiện, khả năng của E khi H đúng) thường gọi là xác suất tiên nghiệm. - P(H|E): xác suất hậu nghiệm của H nếu biết E. 2.2.2. Thuật toán Naïve Bayes Thuật toán phân lớp Naive Bayes (Naive Bayes Classification - NBC) thường được gọi ngắn gọn là thuật toán là Naive Bayes [19]. Thuật toán Naive Bayes dựa trên định lý Bayes (2.2) để đưa ra các phán đoán cũng như phân loại dữ liệu dựa trên các dữ liệu được quan sát và thống kê.