Luận văn Thạc sĩ Máy tính: Nghiên cứu và thử nghiệm phần mềm phân loại hành vi bò sử dụng thuật toán cây quyết định

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:60

Thêm vào BST

Báo xấu

33
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn Thạc sĩ Máy tính "Nghiên cứu và thử nghiệm phần mềm phân loại hành vi bò sử dụng thuật toán cây quyết định" trình bày các nội dung chính sau: Cơ sở lý thuyết về học máy và một số thuật toán học máy kinh điển; Quá trình thu thập dữ liệu, phương pháp đánh giá các thuật toán học máy; Xây dựng chương trình thử nghiệm cho việc quản lý dữ liệu cùng kết quả của thuật toán học máy.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Máy tính: Nghiên cứu và thử nghiệm phần mềm phân loại hành vi bò sử dụng thuật toán cây quyết định

BỘ GIÁO DỤC VIỆN HÀN LÂM VÀ ĐÀO TẠO KHOA HỌC VÀ CÔNG NGHỆ VN HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ NGUYỄN VIỆT ANH Nguyễn Việt Anh HỆ THỐNG THÔNG TIN NGHIÊN CỨU VÀ THỬ NGHIỆM PHẦN MỀM PHÂN LOẠI HÀNH VI BÒ SỬ DỤNG THUẬT TOÁN CÂY QUYẾT ĐỊNH LUẬN VĂN THẠC SĨ Hệ thống thông tin 2021 Hà Nội - 2021
BỘ GIÁO DỤC VIỆN HÀN LÂM VÀ ĐÀO TẠO KHOA HỌC VÀ CÔNG NGHỆ VN HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ Nguyễn Việt Anh NGHIÊN CỨU VÀ THỬ NGHIỆM PHẦN MỀM PHÂN LOẠI HÀNH VI BÒ SỬ DỤNG THUẬT TOÁN CÂY QUYẾT ĐỊNH Chuyên ngành: Hệ thống thông tin Mã số: ITT801 LUẬN VĂN THẠC SĨ NGÀNH MÁY TÍNH CÁN BỘ HƯỚNG DẪN KHOA HỌC TS. TRẦN ĐỨC NGHĨA Hà Nội – tháng 7 năm 2021
1 LỜI CAM ĐOAN Tôi xin cam đoan đề tài nghiên cứu trong luận văn này là công trình nghiên cứu của tôi dựa trên những tài liệu, số liệu do chính tôi tự tìm hiểu và nghiên cứu. Chính vì vậy, các kết quả nghiên cứu đảm bảo trung thực và khách quan nhất. Đồng thời, kết quả này chưa từng xuất hiện trong bất cứ một nghiên cứu nào. Các số liệu, kết quả nêu trong luận văn là trung thực nếu sai tôi hoàn chịu trách nhiệm. Tác giả luận văn Nguyễn Việt Anh
2 LỜI CẢM ƠN Để hoàn thành luận văn này, tôi xin gửi lời cảm ơn chân thành và tình cảm đặc biệt tới ngƣời thầy đồng thời cũng là đồng nghiệp cùng nơi công tác của tôi là TS. Trần Đức Nghĩa. Thầy là ngƣời đã luôn theo sát, tận tình chỉ bảo, góp ý, hƣớng dẫn và định hƣớng cho tôi trong suốt quá trình làm luận văn này tại Học Viện Khoa học và Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam. Nghiên cứu này đƣợc thực hiện trong khuôn khổ đề tài mã số KC.01.21/16-20 tài trợ bởi Bộ Khoa học và Công nghệ. Tiếp theo, tôi cũng xin gửi lời cảm ơn sâu sắc tới các thầy cô, các bạn trong Học Viện Khoa học và Công nghệ; các anh chị đồng nghiệp tại Viện Công nghệ Thông tin đã luôn sẵn sàng giúp đỡ tạo điều kiện tốt nhất cho tôi trong quá trình làm luận văn. Tôi cũng xin cảm ơn sự hỗ trợ của nhóm nghiên cứu tiềm năng Cảm nhận thông minh và ứng dụng (SSA), Trƣờng đại học Phenikaa. Mặc dù có nhiều cố gắng, song thời gian thực hiện luận văn có hạn, nên luận văn còn nhiều hạn chế. Tôi rất mong nhận đƣợc nhiều sự góp ý, chỉ bảo của các thầy, cô để hoàn thiện hơn luận văn của mình. Tôi xin chân thành cảm ơn! Hà Nội, ngày 12 tháng 7 năm 2021 Học viên Nguyễn Việt Anh
3 MỤC LỤC LỜI CAM ĐOAN ......................................................................................................... 1 LỜI CẢM ƠN ............................................................................................................... 2 MỤC LỤC ..................................................................................................................... 3 DANH MỤC HÌNH VẼ ................................................................................................ 5 DANH MỤC BẢNG BIỂU .......................................................................................... 6 DANH MỤC VIẾT TẮT .............................................................................................. 7 CHƢƠNG 1: TỔNG QUAN VỀ ĐỀ TÀI NGHIÊN CỨU...................................... 8 1.1. Yêu cầu thực tiễn ...................................................................................... 8 1.2. Mục tiêu của luận văn ............................................................................... 9 1.3. Cấu trúc của luận văn................................................................................ 9 CHƢƠNG 2: CƠ SỞ LÝ THUYẾT ......................................................................... 10 2.1. Các nghiên cứu liên quan.......................................................................... 10 2.2. Giới thiệu về học máy ............................................................................... 10 2.3. Các thuật toán phân loại phổ biến............................................................. 11 2.3.1. K-Nearest Neighbors (k-NN) ................................................................ 11 2.3.2. Support Vector Machines ...................................................................... 13 2.3.3. Decision Tree ........................................................................................ 13 2.3.4. Random Forest ...................................................................................... 16 2.3.5. Gradient Boosted Decision Tree ........................................................... 17 2.4. Ngôn ngữ lập trình Python........................................................................ 17 2.4.1. Đặc điểm chung và thế mạnh ................................................................ 17 2.4.2. Thƣ viện scikit-learn cho học máy ........................................................ 18 CHƢƠNG 3: PHƢƠNG PHÁP ĐÁNH GIÁ VÀ KẾT QUẢ.................................. 19 3.1. Quy trình đề xuất ...................................................................................... 19 3.2. Gia tốc kế 3 trục và phần cứng cảm biến.................................................. 20 3.3. Lấy mẫu dữ liệu và tiền xử lý ................................................................... 22 3.4. Kết quả đánh giá ....................................................................................... 25 3.5. Nhận xét .................................................................................................... 29
4 CHƢƠNG 4: XÂY DỰNG CHƢƠNG TRÌNH THỬ NGHIỆM QUẢN LÝ VÀ PHÂN LOẠI DỮ LIỆU HÀNH VI .............................................................................. 31 4.1. Nhu cầu và mục tiêu ................................................................................. 31 4.2. Yêu cầu kỹ thuật ....................................................................................... 31 4.3. Giải pháp và phân tích lựa chọn ............................................................... 32 4.3.1. Kiến trúc vật lý của hệ thống................................................................. 33 4.3.2. Ngôn ngữ Python và nền tảng phát triển ............................................... 34 4.3.3. Giải pháp quản trị cơ sở dữ liệu Posgresql ............................................ 34 4.3.4. Mô hình MVC xây dựng phần mềm thử nghiệm .................................. 35 4.3.5. Xử lý các tác vụ chạy nền với Celery và Redis ..................................... 36 4.3.6. Kiến trúc logic tổng thể của phần mềm thử nghiệm ............................. 38 4.4. Thiết kế chức năng hệ thống ..................................................................... 39 4.4.1. Quản trị ngƣời sử dụng .......................................................................... 39 4.4.2. Quản lý thông tin trang trại ................................................................... 41 4.4.3. Quản lý thông tin bò sữa ....................................................................... 42 4.4.4. Quản lý thông tin dữ liệu huấn luyện và mô hình ................................. 44 4.4.5. Quản lý dữ liệu suy luận và kế quả phân loại ....................................... 45 4.5. Giao diện và chức năng sử dụng cơ bản ................................................... 46 4.5.1. Quản lý ngƣời dùng ............................................................................... 46 4.5.2. Quản lý thông tin trang trại ................................................................... 47 4.5.3. Quản lý cá thể bò sữa và dữ liệu ........................................................... 48 4.5.4. Quản lý dữ liệu huấn luyện và mô hình huấn luyện.............................. 48 4.5.5. Quản lý dữ liệu suy luận và kết quả phân loại ...................................... 50 4.5.6. Thống kê kết quả ................................................................................... 52 CHƢƠNG 5: KẾT LUẬN ........................................................................................ 53 TÀI LIỆU THAM KHẢO ............................................................................................. 54
5 DANH MỤC HÌNH VẼ Hình 2-1: Mô hình thuật toán k-NN............................................................................... 12 Hình 2-2: Mô hình thuật toán SVM ............................................................................... 13 Hình 2-3: Mô hình thuật toán cây quyết định ................................................................ 14 Hình 2-4: Mô hình thuật toán Random Forest ............................................................... 16 Hình 3-1: Mô hình thuật toán học máy để phân loại hành vi ........................................ 19 Hình 4-1: Kiến trúc vật lý của hệ thống ......................................................................... 33 Hình 4-2: Mô hình MVC................................................................................................ 35 Hình 4-3: Hàng đợi tác vụ xử lý không đồng bộ ........................................................... 37 Hình 4-4: Nguyên lý hoạt động của Celery và Redis trong nền tảng Django ............... 37 Hình 4-5: Kiến trúc logic tổng thể của phần mềm thử nghiệm...................................... 38 Hình 4-6: Sơ đồ usecase của nhóm chức năng quản trị ngƣời dùng .............................. 39 Hình 4-7: Sơ đồ usecase nhóm chức năng quản lý trang trại......................................... 41 Hình 4-8: Sơ đồ usecase quản lý thông tin bò sữa ......................................................... 42 Hình 4-9: Sơ đồ usecase nhóm chức năng quản lý dữ liệu huấn luyện ......................... 44 Hình 4-10: Sơ đồ usecase nhóm chức năng quản lý dữ liệu suy luận ........................... 45 Hình 4-11: Danh sách ngƣời dùng ................................................................................. 46 Hình 4-12: Chức năng liệt kê trang trại ......................................................................... 47 Hình 4-13: Chức năng thêm, sửa, xóa trang trại ............................................................ 47 Hình 4-14: Chức năng liệt kê danh sách cá thể bò sữa .................................................. 48 Hình 4-15: Chức năng thêm, sửa, xóa cá thể bò sữa...................................................... 48 Hình 4-16: Huấn luyện mô hình cho cá thể bò sữa ........................................................ 49 Hình 4-17: Danh sách các tập dữ liệu huấn luyện ......................................................... 49 Hình 4-18: Lịch sử kết quả tác vụ huấn luyện mô hình phân loại ................................. 50 Hình 4-19: Danh sách tập dữ liệu phân loại đƣợc tải lên thủ công ................................ 50 Hình 4-20: Tải lên dữ liệu mới phục vụ phân loại hành vi ............................................ 51 Hình 4-21: Kết quả suy luận từ dữ liệu tải lên ............................................................... 51 Hình 4-22: Thống kê hành vi của một cá thể bò sữa trong 7 ngày gần nhất ................. 52
6 DANH MỤC BẢNG BIỂU ảng 3-1: Ví dụ một bản ghi sau khi chia đoạn ............................................................. 23 ảng 3-2: Số lƣợng dữ liệu thu đƣợc mỗi hành vi ......................................................... 24 ảng 3-3: Các phƣơng pháp trích chọn đặc trƣng ......................................................... 25 ảng 3-4: So sánh độ chỉ rõ chung của 4 mô hình phân loại......................................... 27 ảng 3-5: Ma trận nhầm lẫn của thuật toán G DT đối với từng hành vi cụ thể trên bộ dữ liệu J. Wang............................................................................................................... 28 ảng 3-6: Ma trận nhầm lẫn của thuật toán G DT đối với từng hành vi cụ thể trên bộ dữ liệu tự thu thập .......................................................................................................... 28 ảng 3-7: Hiệu suất tổng thể của mô hình G DT đối với các hành vi đối với bộ dữ liệu của Jun Wang ................................................................................................................. 29 ảng 3-8: Hiệu suất tổng thể của mô hình G DT đối với các hành vi đối với bộ dữ liệu của tự thu thập ................................................................................................................ 29 ảng 4-1: Mô tả các thành phần chính trong thiết kế chƣơng trình thử nghiệm ........... 38
7 DANH MỤC VIẾT TẮT GDBT Gradient Boosted Decision Tree k-NN K-Nearest Neighbors SVM Support Vector Machine RF Random Forest MVC Model – View – Controller CSDL Cơ sở dữ liệu DBMS Database Management System API Application Programming Interface
8 CHƢƠNG 1: TỔNG QUAN VỀ ĐỀ TÀI NGHIÊN CỨU 1.1. Yêu cầu thực tiễn Trong chăn nuôi ngày nay, vấn đề sức khoẻ của gia súc có liên quan trực tiếp đến sản lƣợng. Đối với đàn bò sữa, để duy trì sức khỏe và sản lƣợng sữa chất lƣợng cao và chức năng sinh sản, ngƣời chăn nuôi phải đảm bảo các điều kiện tốt nhất [1]. Một trong những biểu hiện dễ nhận thấy nhất về sức khoẻ gia súc là các biểu hiện và hành vi của chúng. Hành vi là một yếu tố quan trọng để đánh giá sức khoẻ và tình trạng sức khoẻ của bò sữa [2]. Gia súc thay đổi hành vi của chúng để đối phó với các yếu tố nhƣ chấn thƣơng, bệnh dịch hoặc những thay đổi về môi trƣờng và xã hội [3]. Việc đánh giá hành vi chủ yếu thông qua kinh nghiệm của ngƣời chăn nuôi, nhƣng khó phát hiện một cách tập trung và trực quan, đặc biệt là ở những đàn gia súc lớn do thiếu thời gian và lao động [4]. Một phƣơng pháp chính xác, nhanh chóng và chi phí thấp để theo dõi các mô hình hành vi nhƣ một biện pháp hỗ trợ trong việc đánh giá sức khỏe và phúc lợi của bò sẽ có lợi. Sử dụng cảm biến đeo trên cơ thể cung cấp một giải pháp khả thi cho vấn đề này, cho phép theo dõi hành vi đàn gia súc đo lƣờng ở quy mô lớn, tuy nhiên điều này chỉ có thể thành công nếu đầu ra cảm biến có thể đƣợc diễn giải chính xác và theo thời gian thực. Theo dõi hành vi của gia súc bằng cách sử dụng cảm biến đang trở thành một giải pháp phổ biến trong các chƣơng trình quản lý trang trại và chọn lọc di truyền [4]. Cách tiếp cận này tập trung nhiều hơn vào sức khoẻ và hiệu suất của từng cá thể hơn là cách tiếp cận dựa trên bầy đàn truyền thống. Tuy nhiên, việc thu thập và giải thích dữ liệu thu đƣợc từ các cảm biến nhằm mô tả loại hành vi của cá thể vẫn mang lại thách thức nghiêm trọng cho các nhà phát triển. ài toán này liên quan đến độ phức tạp của hành vi (tức là một số hành vi có chứa các cử chỉ tƣơng tự), đến việc trích xuất các tính năng liên quan cho phép phân biệt hành vi, việc mất mát dữ liệu đặc trƣng cho cảm biến phát không dây, việc xử lý dữ liệu để đối phó với nhiễu vốn có trong các phép đo đã thu thập [5].
9 1.2. Mục tiêu của luận văn Nghiên cứu này bắt đầu với hy vọng nâng cao độ chính xác trong việc nhận diện hành vi bằng cách đƣa vào thống kê dữ liệu cảm biến gia tốc. Luận văn này bắt đầu với việc nghiên cứu các thuộc tính dữ liệu dựa trên dữ liệu thô thu đƣợc từ cảm biến gia tốc ba trục trong các điều kiện hành vi khác nhau bằng cách tính toán biểu đồ, sau đó xác định các tính năng nào sẽ sử dụng để phân loại trạng thái của bò. Trong bƣớc phân loại, nhiều thuật toán phân loại phổ biến và cổ điển khác nhau đƣợc thử nghiệm và đánh giá tính hiệu quả, bao gồm: Decision Tree (Cây quyết định), k-Nearest Neighbors, Support Vector Machine (Máy véc tơ hỗ trợ). Do đó, tín hiệu gia tốc kế đƣợc phân loại thành một trong bảy trạng thái chuyển động: ăn, nằm, đứng, nằm, đứng lên, đi bình thƣờng, đi lại tích cực. Dựa vào đánh giá tính hiệu quả của các thuật toán trên, luận văn này sau đó đề xuất xây dựng một chƣơng trình thử nghiệm nhằm quản lý tập trung các dữ liệu thu đƣợc từ cảm biến gia tốc gắn trên mỗi đối tƣợng gia súc. Chƣơng trình cũng có khả năng phân loại tự động dữ liệu mới thu về và lƣu kết quả trên cơ sở dữ liệu, tạo điều kiện cho ngƣời quản lý theo dõi các thống kê một cách trực quan về hoạt động của các cá thể gia súc. 1.3. Cấu trúc của luận văn Luận văn đƣợc tổ chức nhƣ sau: Phần 1 giới thiệu chung về đề tài cùng các nghiên cứu liên quan trong và ngoài nƣớc. Phần 2 thảo luận về cơ sở lý thuyết về học máy và một số thuật toán học máy kinh điển. Phần 3 trình bày quá trình thu thập dữ liệu, phƣơng pháp đánh giá các thuật toán học máy ở chƣơng 2 cùng kết quả đánh giá. Phần 4 trình bày việc xây dựng chƣơng trình thử nghiệm cho việc quản lý dữ liệu cùng kết quả của thuật toán học máy. Phần 5 là kết luận.
10 CHƢƠNG 2: CƠ SỞ LÝ THUYẾT 2.1. Các nghiên cứu liên quan Vấn đề phức tạp trong việc nhận dạng hành vi của động vật đã thúc đẩy các nhóm nghiên cứu khác nhau giải quyết các bài toán thực tế bằng cảm biến đeo trên cơ thể [6, 7, 8, 9]. Cụ thể trong bài toán ứng dụng cảm biến đeo trên cơ thể, một số hệ thống hiện có đã đƣợc phát triển để phân tích hành vi bò sữa tự động [7, 8, 9]. Cảm biến gia tốc đã đƣợc sử dụng rộng rãi để theo dõi các hành vi của bò do có ƣu điểm là kích thƣớc nhỏ và trọng lƣợng nhẹ [12, 13, 14, 15]. Các phƣơng pháp này đƣợc xếp vào các loại chung là học có giám sát và không giám sát. Tuy nhiên, các hệ thống này thƣờng chỉ xác định một số mẫu hành vi và các thuật toán máy học của nó có nhƣợc điểm là tiêu thụ quá nhiều bộ nhớ, khả năng học liên tục không khả thi, độ nhạy cao với dữ liệu ngoại lai và hiệu suất tối ƣu hóa tổng thể còn hạn chế [4]. Trong [15], tác giả dựa vào dữ liệu cảm biến gia tốc để phân biệt các hành vi nhƣ: ăn, nằm, đứng nhƣng chƣa phân tách đƣợc hành vi chuyển trạng thái từ đứng sang nằm hoặc ngƣợc lại một cách rõ ràng. Nghiên cứu này cũng kết luận rằng thuật toán Support Vector Machine cho kết quả chính xác hơn nhƣng Decision Tree lại có độ nhạy tốt hơn. Trong khi đó ở [28], nhiều loại cảm biến khác nhau đƣợc sử dụng để thu nhập nhiều loại thông tin cho hệ thống giám sát, bao gồm: GPS cho dữ liệu vị trí, cảm biến tốc độ di chuyển, nhiệt kế, gia tốc kế 3 trục, cảm biến từ trƣờng ba trục. Ngoài ra, [28] xây dựng hệ thống cảm biến truyền dữ liệu qua mạng không dây để có thể thu thập thông tin về sinh hoạt của gia súc một cách gián tiếp từ xa. Trong một thực nghiệm tƣơng tự [29], cảm biến đeo cũng đƣợc sử dụng cho nghiên cứu về tính hiệu quả của việc phát hiện động dục, thời gian rụng trứng của giống bò đen Nhật Bản. Hệ thống này phát hiện các trạng thái đứng, so sánh với khả năng sẵn có của nó để phát hiện sự kiện động dục. 2.2. Giới thiệu về học máy Học máy (Machine learning) là một lĩnh vực đang phát triển mạnh của khoa học máy tính tập trung đến xây dựng và nghiên cứu các lý thuyết và kỹ thuật liên quan nhằm cho phép máy tính có thể "học" một cách tự động dựa trên các dữ liệu đầu vào để giải quyết những bài toán cụ thể.
11 Học máy và thống kê có liên quan trực tiếp với nhau, cả hai khía cạnh đều hƣớng đến việc phân tích và khai thác dữ liệu. Tuy nhiên học máy khác với thống kê ở chỗ tập trung vào nghiên cứu các giải thuật thay vì áp dụng tính toán trực tiếp lên dữ liệu. Học máy cùng các lĩnh vực có liên quan nhƣ học sâu, trí tuệ nhân tạo đang đƣợc áp dụng ngày càng rộng rãi trong mọi lĩnh vực đời sống. Học máy cung cấp một cách tiếp cận tuyệt vời để cải thiện độ chính xác của mô hình, dựa trên cấu trúc dữ liệu có thể thay đổi động, đồng thời xử lý các tập dữ liệu lớn và phức tạp có đƣợc từ một môi trƣờng cụ thể [10]. Ba kỹ thuật phổ biến nhất trong học máy là học có giám sát, học không giám sát và học bán giám sát. Học tập có giám sát xảy ra khi đối tƣợng nhận đƣợc một loạt các ví dụ đƣợc gắn nhãn là tập dữ liệu huấn luyện, sau đó đƣa ra các dự đoán về các dữ liệu khác. Vấn đề phƣơng pháp học máy này là dữ liệu cần đƣợc dán nhãn theo cách thủ công toàn bộ, để tạo ra tập dữ liệu cần thiết. Trong học tập không có giám sát, đối tƣợng nhận đƣợc một loạt các ví dụ không đƣợc gắn nhãn ở tập huấn luyện và đƣa ra dự đoán về các dữ liệu chƣa đƣợc biết. Kỹ thuật này thƣờng đƣợc sử dụng trong các bài toán phân cụm và giảm kích thƣớc. Khi ngƣời học nhận đƣợc một loạt các ví dụ có nhãn và không đƣợc gắn nhãn giới hạn nhƣ tập huấn luyện và đƣa ra dự đoán về các dữ liệu mới, quá trình này đƣợc gọi là học bán giám sát. Ƣu điểm của phƣơng pháp sau là thực tế là chỉ cần một số lƣợng hạn chế các mẫu đƣợc dán nhãn, thay vì toàn bộ tập dữ liệu đào tạo đƣợc gắn nhãn. Học bán giám sát cũng nhƣ học có giám sát đƣợc sử dụng phổ biến trong các bài toán phân loại, hồi quy và xếp hạng [11]. 2.3. Các thuật toán phân loại phổ biến Năm thuật toán phân loại kinh điển sau đây đƣợc đề xuất để đánh giá trong luận văn này: Decision Tree, K-Nearest Neighbors (k-NN), Support Vector Machine (SVM), Random Forest (RF), Gradient Boosted Decision Tree (GBDT). 2.3.1. K-Nearest Neighbors (k-NN) k-NN là thuật toán đơn giản, dễ triển khai cho các bài toán học máy có giám sát có thể sử dụng cho việc phân loại lẫn hồi quy. Lý thuyết cơ bản của k-NN dựa trên việc các hiện tƣợng hoặc đối tƣợng tƣơng tự nhau thì thƣờng xuất hiện gần nhau.
12 Để phục vụ cho việc phân loại dữ liệu, k-NN hoạt động bằng cách ghi nhờ toàn bộ tập dữ liệu huấn luyện đã đƣợc gắn nhãn và sau đó nó phân loại một thể hiện mới bằng cách thực hiện 3 bƣớc. Đầu tiên, đo khoảng cách từ dữ liệu cần phân loại đến tất cả các dữ liệu đƣợc gắn nhãn của tập huấn luyện, cách đo dữ liệu có thể là Euclidian, Manhattan, Minkowski... Sau đó, chọn k là một số nguyên bất kỳ, k có vai trò là số điểm dữ liệu đã đƣợc phân loại có khoảng cách nhỏ nhất (láng giềng gần nhất) với dữ liệu cần phân loại. Cuối cùng, kiểm tra các lớp gắn nhãn có khoảng cách ngắn nhất và tìm số lƣợng của mỗi lớp xuất hiện, lớp xuất hiện nhiều nhất đƣợc chọn làm nhãn phân loại. Ở ví dụ trong hình dƣới đây, ta cần phân loại điểm tròn màu xanh lục thuộc lớp nào: màu xanh lam hay màu đỏ. Từ hình này, ta có thể dễ dàng điểm gần chấm màu xanh lục nhất là màu đỏ, do đó nó sẽ đƣợc phân loại vào lớp màu đỏ. Tuy nhiên, có thể điểm màu đỏ gần điểm ta đang xét nhất nhƣng xung quanh nó có rất nhiều điểm màu xanh lam. Vì vậy, việc xét điểm gần nhất là chƣa đủ, thay vào đó ta xét k điểm gần nhất. Giả sử ta lấy k=3 thì sẽ có 2 điểm đỏ và 1 điểm xanh lam gần điểm ta xét, do đó điểm xanh lục vẫn đƣợc phân loại vào lớp đỏ. Nếu ta lấy k=7 thì xung quanh có 5 điểm xanh lam và 2 điểm đỏ, lúc này điểm xanh lục đƣợc phân loại vào lớp xanh lam. Có một điều là nếu ta lấy k=4 thì sẽ có 2 điểm xanh lam và 2 điểm đỏ, lúc này sẽ so sánh khoảng cách các điểm với điểm ta đang xét. Vì vậy việc chọn giá trị k thực sự quan trọng và thƣờng là số lẻ. ình 2-1: Mô hình thuật toán k-NN
13 2.3.2. Support Vector Machines Máy vector hỗ trợ (Support Vector Machines - SVM) là các mô hình học máy có giám sát cũng đƣợc sử dụng phổ biến cho phân loại gắn nhãn và phân tích hồi quy. Máy vectơ hỗ trợ là một bộ phân loại đƣợc xác định bởi một siêu phẳng tách biệt. Lý thuyết của thuật toán SVM là ánh xạ tập dữ liệu vào không gian đặc trƣng có số chiều lớn hơn số chiều ban đầu của dữ liệu nguyên thuỷ và tìm siêu phẳng tách tối ƣu trong không gian mới này. Nói cách khác, với một tập dữ liệu huấn luyện đã đƣợc gắn nhãn cho trƣớc, các thuật toán đƣa ra một siêu phẳng tối ƣu [19]. ình 2-2: Mô hình thuật toán SVM Mô hình Máy Vector Hỗ trợ là biểu diễn của các điểm dữ liệu dƣới dạng các điểm trong không gian n chiều, đƣợc ánh xạ sao cho các dữ liệu thuộc về các nhãn riêng biệt đƣợc tách bởi một khoảng cách rõ ràng càng rộng càng tốt. Ngoài việc thực hiện phân loại tuyến tính, SVM có thể thực hiện hiệu quả phân loại phi tuyến tính, ánh xạ các đầu vào vào các không gian đặc trƣng nhiều chiều hơn [19]. 2.3.3. Decision Tree Cây quyết định là một mô hình học có giám sát, có thể đƣợc áp dụng trong cả các bài toán phân loại dữ liệu và hồi quy. Cây quyết định là một sơ đồ giống nhƣ cấu trúc cây rẽ nhánh, trong đó mỗi nút bên trong biểu thị một thuộc tính, mỗi nhánh biểu diễn một quy luật và mỗi lá (nút đầu cuối) biểu thị một kết quả của quy luật trƣớc nó.
14 Cây quyết định dễ sử dụng và dễ hiểu, cung cấp một phƣơng pháp dựa trên việc mô phỏng suy nghĩ của con ngƣời. Cây quyết định cho thấy đƣợc logic từ dữ liệu và những thuộc tính có tính ảnh hƣởng của dữ liệu. Ở hình ví dụ dƣới đây, hai lớp xanh và đỏ trên không gian hai chiều, nhiệm vụ là đi tìm ranh giới giúp phân chia hai lớp này, nói đơn giản đây là một bài toán phân loại, ta cần xây dựng một bộ phân lớp để quyết định việc một điểm dữ liệu thuộc vào lớp nào. Quan sát hình ta thấy rằng ranh giới cho hai lớp trong bài toán này khá đơn giản, chúng là các đƣờng song song với các trục toạ độ. Nếu một điểm có thành phần thứ nhất nhỏ hơn ngƣỡng , ta quyết định ngay đƣợc rằng nó thuộc lớp xanh. Nếu thành phần thứ hai lớn hơn ngƣỡng , ta quyết định nó cũng thuộc vào lớp xanh. Xét tiếp, nếu thành phần thứ nhất lớn hơn ngƣỡng , ta quyết định nó thuộc vào lớp xanh. Không thỏa mãn các điều kiện trên ta xếp vào lớp đỏ. ình 2-3: Mô hình thuật toán cây quyết định Về cơ bản, cây quyết định tìm hiểu một loạt các quy tắc Nếu-Thì rõ ràng về các giá trị của thuộc tính dẫn đến quyết định dự đoán giá trị đích. Xây dựng cây quyết định trên một tập dữ liệu huấn luyện nhất định là đơn giản xây dựng một loạt các câu hỏi Nếu-Thì và thứ tự của chúng. Những câu hỏi này thƣờng đƣợc áp dụng cho từng thuộc tính hoặc sự kết hợp tuyến tính của của các thuộc tính. Phƣơng thức đầu tiên, đƣợc áp dụng cho từng thuộc tính, đƣợc sử dụng thƣờng xuyên hơn vì tính đơn giản của nó. Chúng ta cần xác định thứ tự các thuộc tính ở mỗi bƣớc. Đối với các bài toán và tập dữ
15 liệu có nhiều thuộc tính và mỗi thuộc tính có các giá trị khác nhau, việc tìm giải pháp tối ƣu thƣờng không khả thi. Thay vào đó, một phƣơng pháp đơn giản thƣờng đƣợc sử dụng ở mỗi bƣớc, thuộc tính tốt nhất sẽ đƣợc chọn dựa trên các tiêu chuẩn nhất định. Đối với mỗi thuộc tính đƣợc chọn, dữ liệu đƣợc chia thành các nút con tƣơng ứng với các giá trị của thuộc tính đó và sau đó tiếp tục áp dụng phƣơng thức này cho từng nút con. Lựa chọn này có thể không phải là tốt nhất, nhƣng trực giác cho thấy rằng phƣơng pháp này sẽ gần với tối ƣu. Ngoài ra, cách tiếp cận này làm cho vấn đề trở nên đơn giản hơn [21]. Sau mỗi câu hỏi, dữ liệu đƣợc chia thành từng nút con tƣơng ứng với câu trả lời cho câu hỏi đó. Câu hỏi ở đây là một thuộc tính, câu trả lời là giá trị của thuộc tính đó. Theo trực giác, một phân chia nhánh đƣợc coi là phân chia tốt nhất nếu dữ liệu trong mỗi nút con hoàn toàn thuộc về một lớp thì nút con này có thể đƣợc coi là một nút lá (tới đây thì không cần phải phân chia thêm). Nếu nhƣ dữ liệu trong nút con vẫn bị trộn, chia nhánh đấy đƣợc coi là chƣa thực sự tốt. Từ quan sát này, cần thiết phải có một phƣơng pháp định lƣợng để tính toán sự tối ƣu của phép chia nhánh. Hàm này sẽ cho giá trị thấp nhất nếu dữ liệu trong mỗi nút con nằm trong cùng một lớp, và cho giá trị cao nếu mỗi nút con chứa dữ liệu thuộc về nhiều lớp khác nhau [21]. Việc xây dựng trình phân loại cây quyết định không yêu cầu bất kỳ tham số cài đặt nào nào, thuật toán cây quyết định có thể xử lý dữ liệu có chiều sâu lớn. [20] Một phƣơng pháp đƣợc sử dụng rộng rãi và hiệu quả trong học máy liên quan đến việc tạo ra các mô hình đƣợc gọi là tập hợp. Một tập hợp có nhiều mô hình học tập riêng lẻ và kết hợp chúng để tạo ra một mô hình tổng hợp mạnh hơn bất kỳ mô hình học tập riêng lẻ nào. Ý tƣởng xuất phát từ việc nếu chúng ta có các mô hình học tập khác nhau, mặc dù mỗi mô hình có thể hoạt động tốt riêng lẻ, chúng sẽ có xu hƣớng mắc các loại lỗi khác nhau trên tập dữ liệu. Và thông thƣờng, điều này xảy ra bởi vì mỗi mô hình riêng lẻ có thể overfit một phần khác nhau của dữ liệu. Bằng cách kết hợp các mô hình riêng lẻ khác nhau thành một nhóm, chúng ta có thể tính trung bình các lỗi riêng lẻ của chúng để giảm nguy cơ overfit trong khi duy trì hiệu suất dự đoán mạnh mẽ [22]. Rừng ngẫu nhiên và Gradient Boosted Decision tree là những ví dụ về ý tƣởng tập hợp đƣợc áp dụng cho cây quyết định.
16 2.3.4. Random Forest Ở góc nhìn tổng quan, thuật toán Rừng ngẫu nhiên (Random forest) có thể đƣợc hiểu là một tập hợp các cây quyết định [23]. Một mô hình rừng ngẫu nhiên tạp ra rất nhiều cây quyết định đơn lẻ áp dụng lên một tập dữ liệu huấn luyện, thƣờng là hàng chục đến hàng trăm cây quyết định khác nhau. Ý tƣởng xuất phát từ việc mỗi cây quyết định đơn lẻ sẽ hoạt động tốt trên một phần dữ liệu. Sự khác biệt này đạt đƣợc bằng cách thêm vào các biến đổi ngẫu nhiên trong quá trình xây dững mỗi cây quyết định riêng. Việc biến đổi ngẫu nhiên này diễn ra theo hai cách. Đầu tiên, dữ liệu đƣợc sử dụng để xây dựng mỗi cây sẽ đƣợc lựa chọn ngẫu nhiên. Thứ hai, các thuộc tính đƣợc chọn trong mỗi phép thử chia nhánh đƣợc chọn ngẫu nhiên [22]. ình 2-4: Mô hình thuật toán Random Forest Để tạo mô hình rừng ngẫu nhiên, trƣớc hết cần xác định sẽ có bao nhiêu cây sẽ đƣợc xây dựng. Mỗi cây đƣợc xây dựng từ các mẫu dữ liệu ngẫu nhiên khác nhau đƣợc gọi là bootstrap. Mẫu bootstrap đƣợc sử dụng phổ biến trong thống kê và học máy. Việc này xuất pháp từ ý tƣởng rằng: nếu dữ liệu huấn luyện có tổng cộng N đơn vị hoặc mẫu dữ liệu, một mẫu bootstrap với kích thƣớc N đƣợc tạo ra bằng cách liên tục chọn một trong số N hàng dữ liệu ngẫu nhiên mà ở đó cho phép việc chọn lại đúng hàng dữ liệu ấy trong mỗi lần lựa chọn. Thực hiện việc lựa chọn ngẫu nhiên này N lần sẽ có kết quả mẫu bootstrap đƣợc tạo ra có N hàng giống nhƣ tập dữ liệu huấn luyện ban đầu nhƣng với khả năng một số hàng dữ liệu sẽ đƣợc lập lại [22].
17 Khi xây dựng cây quyết định cho thuật toán rừng ngẫu nhiên, quá trình đƣợc xem lá gần nhƣ nhau và đƣợc coi là cây dữ liệu chuẩn nhƣng với một khác biệt lớn. Khi chọn chia nhánh tốt nhất cho một nút, thay vì chọn chia nhánh tốt nhất trên tất cả thuộc tính có thể, một tập con ngẫu nhiên đƣợc chọn và cách chia nhánh tốt nhất đƣợc tìm thấy trong một tập con nhỏ hơn của các thuộc tính [22]. 2.3.5. Gradient Boosted Decision Tree Giống nhƣ Rừng ngẫu nhiên, Cây quyết định tăng cƣờng (Gradient Boosted Decision Tree - GBDT) sử dụng một tập hợp nhiều cây quyết định để tạo ra mô hình dự báo mạnh mẽ cho việc phân loại dữ liệu. Tuy nhiên khác với rừng ngẫu nhiên chọn xây dựng mỗi cây quyết định một cách ngẫu nhiên và song song, GBDT dựa trên ý tƣởng rằng việc xây dựng mỗi cây quyết định có thể huấn luyện đƣợc, do đó nó có thể sửa chữa sai sót trong việc xây dựng cây trƣớc đó trong một chuỗi các cây. Thông thƣờng, tập hợp cây quyết định tăng cƣờng sử dụng rất nhiều các cây nông đƣợc biết đến trong học máy nhƣ là các nhân tố học tập yếu theo một cách không ngẫu nhiên, theo đó tạo một mô hình mà dần dần sẽ chứa ít sai sót hơn khi mỗi cây đƣợc thêm vào chuỗi. Một khi mô hình đã xây dựng xong, việc dự đoán với cây quyết định tăng cƣờng sẽ nhanh và không sử dụng nhiều bộ nhớ [22]. Những tham số chủ chốt ảnh hƣởng tới sự phức tạp của mô hình cho cây quyết định tăng cƣờng là một số các cây quyết định nhỏ. 2.4. Ngôn ngữ lập trình Python 2.4.1. Đặc điểm chung và thế mạnh Python là một ngôn ngữ lập trình thông dịch, bậc cao, và đa nhiệm. Python có triết lý thiết kế nhấn mạnh khả năng dễ đọc, dễ học [17]. Mặc dù Python và Matlab có thể so sánh đƣợc trong một số lĩnh vực, nhƣng Python cung cấp một số lợi thế quan trọng khiến luận văn này chọn sử dụng:  Mã nguồn Python ngắn gọn, xúc tích và dễ hiểu hơn so với Matlab [18].  Là một ngôn ngữ lập trình mã nguồn mở và miễn phí, có bộ thƣ viện chuẩn cùng các thƣ viện do bên thứ ba phát hành đồ sộ và mạnh mẽ.  Python cho nhiều lựa chọn hơn ở các gói thƣ viện đồ họa cùng công cụ.
18  Python cung cấp nhiều quyền kiểm soát hơn đối với tổ chức mã nguồn và quản lý namespace tốt hơn. Python giúp dễ dàng duy trì nhiều phiên bản thƣ viện đƣợc chia sẻ [18].  Giống nhƣ C/C ++, Java và hầu hết các ngôn ngữ lập trình khác ngoài Matlab, Python tuân theo một số tiêu chuẩn nhất định, bao gồm lập chỉ mục dựa trên 0 và sử dụng dấu ngoặc vuông thay vì dấu ngoặc để lập chỉ mục. Đây là một lợi thế cho lập trình viên, những ngƣời phải thực hiện các thuật toán xử lý tín hiệu đã xuất bản, chuyển đổi mã từ ngôn ngữ này sang ngôn ngữ khác hoặc làm việc trên nhiều ngôn ngữ [18]. 2.4.2. Thư viện scikit-learn cho học máy Scikit-learn là thƣ viện Python đƣợc sử dụng rộng rãi nhất trong học máy. Đây là một dự án mã nguồn mở đang đƣợc phát triển và cải tiến liên tục, đồng thời hỗ trợ một loạt các thuật toán học máy quan trọng. Scikit-learn có hệ thống tài liệu trực tuyến đầy đủ và một cộng đồng ngƣời dùng rất tích cực. Trong luận văn này, 5 bộ phân loại đƣợc tích hợp trong thƣ viện scikit-learning, đó là Decision Tree, k-Nearest Neighbors, Support Vector Machines, Random Forest và Gradient Boosted Decision Tree đƣợc đánh giá để tìm ra giải pháp tối ƣu, sau đó áp dụng cho chƣơng trình thử nghiệm.