Luận văn Thạc sĩ Công nghệ kỹ thuật điện tử viễn thông: Nghiên cứu mạng cảm biến không dây giám sát hành vi gia súc sử dụng thuật toán phân loại hiệu quả đáp ứng thời gian thực

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

Thêm vào BST

Báo xấu

44
lượt xem 11
download

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

Luận văn này đề xuất thiết bị có thể giám sát 3 hành vi bò (gồm ăn, nằm, đứng) theo thời gian thực. Hệ thống được thiết kế theo mô hình mạng cảm biến không dây, có thể mở rộng về số lượng nút mạng. Các thiết bị nhận biết hành vi được xây dựng dựa trên cảm biến gia tốc và thuật toán k-means. Sở dĩ thuật toán k-means được lựa chọn vì có thể áp dụng ngay cả trên các vi điều khiển cấu hình thấp. Mời các bạn tham khảo!

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ĩ Công nghệ kỹ thuật điện tử viễn thông: Nghiên cứu mạng cảm biến không dây giám sát hành vi gia súc sử dụng thuật toán phân loại hiệu quả đáp ứng thời gian thực

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ---------- VŨ MINH THOẠI NGHIÊN CỨU PHÁT TRIỂN MẠNG CẢM BIẾN KHÔNG DÂY GIÁM SÁT HÀNH VI GIA SÚC SỬ DỤNG THUẬT TOÁN PHÂN LOẠI HIỆU QUẢ ĐÁP ỨNG THỜI GIAN THỰC LUẬN VĂN THẠC SĨ CÔNG NGHỆ KỸ THUẬT ĐIỆN TỬ VIỄN THÔNG Hà Nội - 2020
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ---------- VŨ MINH THOẠI NGHIÊN CỨU PHÁT TRIỂN MẠNG CẢM BIẾN KHÔNG DÂY GIÁM SÁT HÀNH VI GIA SÚC SỬ DỤNG THUẬT TOÁN PHÂN LOẠI HIỆU QUẢ ĐÁP ỨNG THỜI GIAN THỰC Ngành: Công nghệ kỹ thuật Điện tử, Viễn thông Chuyên ngành: Kỹ thuật Điện tử Mã số: 8510302.01 LUẬN VĂN THẠC SĨ CÔNG NGHỆ KỸ THUẬT ĐIỆN TỬ VIỄN THÔNG NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. TRẦN ĐỨC TÂN Hà nội – 2020
LỜI CAM ĐOAN Tôi xin cam đoan luận văn tốt nghiệp: ”Nghiên cứu mạng cảm biến không dây giám sát hành vi gia súc sử dụng thuật toán phân loại hiệu quả đáp ứng thời gian thực” là công trình nghiên cứu của riêng tác giả. Các số liệu, kết quả trình bày trong luận văn là hoàn toàn trung thực, chưa từng được công bố trong các công trình nào khác. Trong luận văn có dùng một số tài liệu tham khảo như đã nêu trong phần tài liệu tham khảo. Tác giả luận văn Vũ Minh Thoại i
LỜI CẢM ƠN Để hoàn thành luận văn này, tôi xin gửi lời cảm ơn chân thành và tình cảm đặc biệt tới người Thầy của tôi PGS. TS. Trần Đức Tân. Thầy là người đã luôn theo sát, tận tình chỉ bảo, góp ý, hướng dẫn và định hướng cho tôi trong suốt quá trình làm luận văn này tại Khoa Điện tử Viễn thông, Trường đại học Công nghệ. Tôi xin cám ơn sự hỗ trợ từ đề tài “Nghiên cứu xử lý thông tin hành vi của bò dựa trên chuyển động từ cảm biến nhằm nâng cao hiệu quả chăn nuôi”, mã số ĐLTE00.02/20-21. Nghiên cứu nà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ô và các anh chị em trong Khoa đã luôn sẵn sà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. 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 25 tháng 8 năm 2020 Học viên Vũ Minh Thoại ii
TÓM TẮT Hiện nay, ngành chăn nuôi sản xuất sữa và thực phẩm đang có nhiều bước phát triển mạnh tại nước ta. Là ngành kinh tế quan trọng để phát triển kinh tế xã hội và an ninh lương thực. Để bảo đảm sự phát triển bền vững của các ngành này việc giám sát và chăm sóc sức khỏe của gia súc có vai trò rất quan trọng và nó là nhu cầu thiết yếu đối với ngành chăn nuôi. Tại Việt Nam, có một số trang trại chăn nuôi bò sữa lớn để nâng cao năng suất và chất lượng sản phẩm, họ rất quan tâm đến vấn đề sức khoẻ của bò. Vì vậy, họ có nhu cầu giám sát về thể chất và sinh lý của đàn gia súc càng thường xuyên càng tốt. Phát sinh từ bản chất của những khó khăn liên quan đến việc quản lý trang trại với các khu chăn thả lớn, các nhà chăn nuôi luôn luôn có nhu cầu "giám sát" động vật của họ một cách tự động và tiết kiệm chi phí nhất. Công nghệ mạng cảm biến không dây là một giải pháp khả thi cho vấn đề này. Trong các thông tin cần cho việc chăn sóc sức khỏe gia súc thì hành vi là một trong những cơ sở quan trọng và nhạy cảm nhất. Việc giám sát hành vi của gia súc trên thực tế thường được tiến hành theo hướng quan sát chuyển động trên cổ bò hoặc chuyển động trên chân. Dữ liệu từ các thiết bị quan sát đó có thể được lưu lại tại thiết bị để xử lý sau hoặc được truyền thông không dây về một thiết bị trung tâm để xử lý. Tuy nhiên, việc thực thi các kỹ thuật trên còn rất cơ bản chưa đáp ứng được việc giám sát thời gian thực hay quy mô chăn thả lớn, nhiều hệ thống chỉ xác định một hoặc hai hành vi hoặc trạng thái động vật tại một thời điểm hoặc nhiều hành vi nhưng độ chính xác còn thấp. Luận văn này đề xuất thiết bị có thể giám sát 3 hành vi bò (gồm ăn, nằm, đứng) theo thời gian thực. Hệ thống được thiết kế theo mô hình mạng cảm biến không dây, có thể mở rộng về số lượng nút mạng. Các thiết bị nhận biết hành vi được xây dựng dựa trên cảm biến gia tốc và thuật toán k-means. Sở dĩ thuật toán k-means được lựa chọn vì có thể áp dụng ngay cả trên các vi điều khiển cấu hình thấp. iii
MỤC LỤC MỤC LỤC ......................................................................................................................iv DANH MỤC HÌNH VẼ ..................................................................................................v DANH MỤC BẢNG BIỂU ............................................................................................vi DANH MỤC VIẾT TẮT.............................................................................................. vii DANH MỤC KÍ HIỆU ................................................................................................ viii CHƯƠNG 1. TỔNG QUAN VỀ ĐỀ TÀI NGHIÊN CỨU .........................................1 1.1. TÌNH HÌNH NGHIÊN CỨU TRONG NƯỚC VÀ QUỐC TẾ .........................1 1.1.1. Giới thiệu ............................................................................................................1 1.1.2. Tình hình nghiên cứu quốc tế .............................................................................2 1.1.3. Tình hình nghiên cứu trong nước .......................................................................3 1.2. NGHIÊN CỨU CÁC THUẬT TOÁN PHÂN LOẠI HÀNH VI GIA SÚC ............3 1.2.1 Tổng quan về các phương pháp học máy ...........................................................3 1.2.1.1. Giới thiệu về học máy .................................................................................3 1.2.1.2. Các giải thuật học máy ................................................................................4 1.2.2. Thuật toán phân cụm k-means............................................................................5 1.2.3. Thuật toán máy vector hỗ trợ (SVM) .................................................................7 1.2.4. Thuật toán cây quyết định ..................................................................................9 1.2.5. So sánh các loại thuật toán phân loại và nhận xét ............................................12 CHƯƠNG 2. NỘI DUNG ĐỀ TÀI NGHIÊN CỨU..................................................14 2.1. NGHIÊN CỨU HỆ THỐNG THIẾT BỊ GIÁM SÁT HÀNH VI GIA SÚC ........14 2.1.1. Xây dựng mạng wsn ứng dụng cho giám sát hành vi gia súc .........................14 Module Ra-02 (hình 2.3) ...........................................................................................19 Mạng không dây 2.4GHz trên dòng module nRF24 .................................................20 Module NRF24L01 ...................................................................................................23 Thiết bị gắn cảm biến ................................................................................................ 25 Thiết bị LoRa Gateway ............................................................................................. 29 2.2. PHÂN LOẠI HÀNH VI GIA SÚC ....................................................................31 2.2.1. Trạng thái hành vi gia súc ...............................................................................31 2.1.3. Xây dựng bộ tham số đánh giá phân loại gia súc .............................................33 CHƯƠNG 3. KẾT QUẢ.............................................................................................. 36 3.1. HỆ THỐNG PHẦN CỨNG ...............................................................................36 3.2. THỬ NGHIỆM HỆ THỐNG .............................................................................36 3.3. KẾT QUẢ PHÂN LOẠI HÀNH VI SỬ DỤNG K-MEANS ............................ 36 3.4. MỘT SỐ SAI SỐ TRONG QUÁ TRÌNH THU DỮ LIỆU ............................... 36 KẾT LUẬN ..................................................................................................................45 TÀI LIỆU THAM KHẢO...........................................................................................46 iv
DANH MỤC HÌNH VẼ Hình 1.1. Sơ đồ giải thuật toán k-means .........................................................................7 Hình 1.2. Thuật toán SVM ............................................................................................... 8 Hình 2.1. Mô tả vị trí của các thiết bị trên cá thể gia súc .............................................15 Hình 2.2. Mô tả về kiến trúc mạng sao (star)................................................................ 17 Hình 2.3. Module thu phát LoRa Ra-02 ........................................................................19 Hình 2.4. Sơ đồ kênh truyền trên mạng nRF 2.4GHz....................................................20 Hình 2.5. Mạng đa thiết bị truyền một thiết bị nhận .....................................................21 Hình 2.6. Cấu trúc gói tin ShockBurst ..........................................................................22 Hình 2.7. Dữ liệu gửi đi cho nhau .................................................................................22 Hình 2.8. Module nRF24L01 mini .................................................................................23 Hình 2.9. Thiết bị được gắn trên con bò thực tế ...........................................................25 Hình 2.10. Sơ đồ khối hệ thống của thiết bị gắn cảm biến ...........................................25 Hình 2.11. Sơ đồ thuật toán thiết bị gắn cảm biến ........................................................28 Hình 2.12. Sơ đồ khổi hệ thống của LoRa Gateway .....................................................29 Hình 2.13. Sơ đồ thuật toán thiết bị LoRa Gateway .....................................................30 Hình 2.14. Hướng của các trục gia tốc gắn trên cổ bò .................................................32 Hình 2.15. Các trục cảm biến gia tốc khi bò đang đứng ..............................................32 Hình 2.16. Hướng cảm biến gia tốc khi con bò đang ăn...............................................33 Hình 2.17. Hướng cảm biến gia tốc khi con bò đang nằm ............................................33 Hình 2.17. Phương pháp cửa sổ trượt ...........................................................................35 Hình 3.1. Thiết bị phần cứng gắn cổ .............................................................................36 Hình 3.2. Dữ liệu 3 tốc theo 3 trục X, Y, Z ( 1 mg = 0.001 g, 1 g =9.8 m/s2) ...............38 Hình 3.3. Khai thác đặc trưng VeDBA ..........................................................................39 Hình 3.4. Khai thác đặc trưng SCAY ............................................................................39 Hình 3.5. Khai thác quan hệ giữa SCAY (trục tung) và VeDBA (trục hoành) ..............40 Hình 3.6. Quan hệ giữa SCAY (trục tung) và VeDBA (trục hoành).............................. 41 khi sử dụng k-means với thiết lập là 3 cụm khác nhau .................................................41 Hình 3.7. Dữ liệu gia tốc của tập kiểm tra ....................................................................41 Hình 3.8. VeDBA của tập kiểm tra ................................................................................42 Hình 3.9. VeDBA của tập kiểm tra ................................................................................42 Hình 3.10. Quan hệ VeDBA – SCAY của tập kiểm tra ..................................................43 Hình 3.11. Chỉ số nhận dạng ước lượng (trên) và thực tế (dưới) .................................43 v
DANH MỤC BẢNG BIỂU Bảng 1.1. So sánh các thuật toán phân loại ...................................................................13 Bảng 2.1. Các tầng mạng của mạng không dây LoRa ..................................................16 Bảng 2.2. Các lớp thiết bị trong mạng truyền thông LoRa ...........................................18 vi
DANH MỤC VIẾT TẮT Tiếng Anh đầyđủ TiếngViệt DBA Dynamic Body Acceleration Gia tốc cơ thể động DBAx Dynamic Body Acceleration of x-axis Gia tốc cơ thể động trục x DBAy Dynamic Body Acceleration of y-axis Gia tốc cơ thể động trục y DBAz Dynamic Body Acceleration of z-axis Gia tốc cơ thể động trục z VeDBA Vector of Dynamic Body Acceleration Vector gia tốc cơ thể động SCAY Static Component of the Acceleration Thành phần gia tốc tĩnh của in the Y-axis trục y ADC Analog to Digital Converter Bộ chuyển đội tương tự sang số UART Universal asynchronous receiver / Truyền nhận nối tiếp không transmitter đồng bộ I2C Inter-Integrated Circuit Mạch chuyển đổi giao tiếp vii
DANH MỤC KÍ HIỆU Kí hiệu Đơn vị VeDBA m/s2 SCAY m/s2 DBAx m/s2 DBAy m/s2 DBAz m/s2 viii
CHƯƠNG 1. TỔNG QUAN VỀ ĐỀ TÀI NGHIÊN CỨU 1.1. TÌNH HÌNH NGHIÊN CỨU TRONG NƯỚC VÀ QUỐC TẾ 1.1.1. Giới thiệu Xã hội phát triển, nhu cầu về thực phẩm ngày càng cao, không những đòi hỏi về mặt số lượng mà còn về mặt chất lượng. Kéo theo việc chăn nuôi gia súc phát triển nông trại với quy mô chăn nuôi lớn, do vậy việc giám sát tình trạng sức khỏe, sinh sản vật nuôi sẽ trở nên rất khó khăn nếu áp dụng theo phương pháp thủ công và theo kinh nghiệm của người chăn nuôi. Hình thức giám sát phổ biến nhất hiện nay được dùng là sử dụng mã vạch được gắn trên vật nuôi và ghi chép lại thông tin của từng con theo ngày, tuần, tháng... Việc sử dụng cách này gây nhiều bất tiện cho người chăm sóc. Hướng phát triển theo hình thức hiện đại hơn đó là hệ giám sát tự động tình trạng sức khỏe và các thông số đặc thù theo mong muốn từ người chăn nuôi. Các hình thức giám sát hiện đại giúp người chăn nuôi gia súc tiết kiệm được đáng kể thời gian giám sát và nâng cao tính hiệu quả trong việc chăm sóc và phúc lợi cho vật nuôi. Sức khỏe và phúc lợi chung của gia súc thường có thể được kiểm chứng và xác định theo mô hình hành vi của bò. Hành vi vật lí của bò được báo cáo như một các phát hiện sớm các bệnh như bệnh tim và chỉ thị về đau đớn, stress nhiệt và tương tác xã hội trong một đàn. Hành vi thay đổi khi động vật ốm có thể bao gồm giảm hoạt độn thường ngày, hoạt động sinh sản, ăn uống, chăm sóc và các hành vi xã hội khác. Việc giám sát bò được tập chung theo ba hướng phổ biến nhất đó là giám sát phân loại hành vi của bò; phát hiện trấn thương; xác định thời điểm sinh sản của bò. Việt Nam là một nước có khí hậu nhiệt đới gió mùa, nơi có điều kiện phát triển chăn nuôi gia súc. Một số công ty lớn chế biến sữa đã đi đầu trong việc áp dụng công nghệ tiên tiến như TH True Milk đã áp dụng quy trình chăn nuôi bò sữa Israel, hay Vinamilk mỗi con bò được đeo một chíp điện tử để giám sát qua hệ thống Alpro hiện đại do Delaval cung cấp. Nhiều tỉnh thành trong cả nước (Hải Dương, Hà Nam, Nghệ An, Bắc Giang, Sơn La...) đã có những đề án phát triển chăn nuôi gia súc, trong đó nhấn mạnh đến chủ trương xây dụng trung tâm phát triển chăn nuôi gia súc theo hướng quy mô lớn, hiệu quả, bán công nghiệp theo hướng tập chung. Nhiều địa phương đã khuyến khích chuyển đổi trồng lúa sang trồng ngô, trồng cỏ phục vụ chăn nuôi; trong 1
đó quy hoạch hạ tầng: đường trục; hệ thống chuồng nuôi gia súc; đường điện, nước...; có thiết kế mẫu hệ thống chuồng chăn nuôi. Có thể thấy rằng việc áp dụng kĩ thuật hiện đại giúp nâng cao chất lượng sản phẩm, tăng năng suất lao động, cải tiến kĩ thuật về giống, chăm sóc, thú y... 1.1.2. Tình hình nghiên cứu quốc tế Hiện nay trên thế giới có rất nhiều kĩ thuật giúp giám sát sức khỏe, hoạt động và các vấn đề sinh sản của vật nuôi trên quy mô lớn. Những kĩ thuật này giúp chủ các trang trại công ty hay doanh nghiệp kiểm soát vật nuôi của mình, từ đó giúp nâng cao hiệu quả chăn nuôi. Tuy nhiên những kĩ thuật được áp dụng hiện tại còn khá thủ công và cần sự can thiệt sức người. Việc nghiên cứu ra các kĩ thuật và thiết bị mới vẫn luôn là một chủ đề đang được quan tâm mạnh mẽ. Như trong bài báo [4] tác giả tập chung vào vấn đề phân loại các hoạt động thường ngày của bò sử dụng hệ thống giám sát hoạt động dựa trên cảm biến gia tốc. Tuy nhiên bài báo chỉ dừng lại ở việc nhận biế các trạng thái như: ăn, nằm, đứng và chưa phân biệt được một cách rõ ràng giữa việc chuyển trạng thái từ đứng sang nằm hay ngược lại. Trong đó bài báo [5], nhóm tác giả xây dựng hệ giám sát hoạt động của bò sử dụng nhiều loại cảm biến khác nhau để thu thập thông tin như: cảm biến vị trí, cảm biến tốc độ di chuyển, cảm biến nhiệt độ, cảm biến gia tốc ba trục, cảm biến từ trường 3 trục. Bên cạnh đó họ đã xây dựng nền tảng cảm biến không dây có thể quan sát và thu thập thông tin của gia súc mà không cần can thiệt đến chúng. Dựa trên các thông tin thu được có thể phân biệt thành công được các hoạt động và ứng sử khác nhau của gia súc. Tuy nhiên hệ thống mới chỉ dừng lại ở việc thông tin lưu trữ trên thẻ nhớ chứ chưa truyền đi được. Trong nghiên cứu [6] tác giả tập chung vào hiệu quả của việc phát hiện động dục và phát hiện thời gian rụng trứng của giống bò đen Nhật Bản sử dụng hệ thống giám sát số bước chân thời gian thực và truyền thông không dây. 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. Bên cạnh việc phát triển các kĩ thuật phần cứng, các kĩ thuật phần mềm hay thuật toán cũng đang được nghiên cứu nhằm nâng cao khả năng nhận biết một cách chính xác các trạng thái của gia súc. Các thuật toán được phát triển theo hai hướng: Thuật toán học máy có giám sát và thuật toán học máy không có giám sát. Thuật toán có giám sát thường là hệt thống gồm hai tiến trình: Tiến trình đào tạo dữ liệu và tiến trình kiểm thử dữ liệu. Hệ thống 2
này sử dụng các tập dữ liệu đã biết để xây dựng nên mô hình, sau đó sử dụng mô hình này để dự đoán để dự đoán cho tập dữ liệu mới. Thuật toán học máy không có giám sát khám phá dữ liệu để tìm mô hình ẩn hoặc cụm dữ liệu đầu vào trong các lớp với tính chất thống kê tương tự. Thuật toán học máy có giám sát có thể kể đến là: máy vector hỗ trợ (SVM). Thuật toán học máy không có giám sát là: thuật toán cây quyết định, k- mean và mô hình Markov ẩn (HMM). Mỗi thuật toán đều có ưu và nhược điểm khác nhau. SVM và HMM đi kèm với chi phí tính toán lớn, làm cho việc thực hiện một thuật toán như vậy bên trong một thiết bị sinh học từ xa là không thực tế. Tuy nhiên thuật toán cây quyết định có chi phí tính toán thấp hơn nhiều và dễ dành được thực hiện trong thời gian thực. Bên cạnh đó, SVM lại có độ chính xác cao trong khi cây quyết định lại cho độ nhạy cao [4]. 1.1.3. Tình hình nghiên cứu trong nước Hiện nay, ở Việt Nam chưa có nhiều nghiên cứu về giám sát hoạt động của bò. Có một nhóm nghiên cứu về giám sát hoạt động, hỗ trợ chăm sóc sức khỏe là một số cán bộ trong Khoa Điện tử viễn thông – Trường đại học Công nghệ, nhóm đã có một số kết quả tốt theo hướng này. Trong bài báo [1] các tác giả đã đưa ra mô hình giám sát hành vi trên bò bao gồm thiết bị gắn ở chân bò để đếm số bước chân và thiết bị gắn trên cổ bò để thu dữ liệu gia tốc ở cổ. Hai thiết bị này kết nối không dây với nhau tạo thành một nút mạng để thu dữ liệu giúp giám sát hành vi của bò. Tuy nhiên đây mới là mô hình chưa triển khai thực nghiệm và chưa đưa ra thuật toán xử lý dữ liệu. Trong bài báo [3] nhóm tác giả đã tiến hành chế tạo một thiết bị thu dữ liệu gia tốc ở cổ và chân bò và lưu vào thẻ nhớ. Dữ liệu offline sau đó được dùng để phân loại một số hành vi cơ bản của bò thông qua thuật toán cây quyết định. Có thể thấy rằng thiết bị còn đơn giản, việc lấy dữ liệu từ thẻ nhớ vấn thủ công. Việc xử lý dữ liệu chỉ dùng thuật toán cây quyết định nên hiệu quả và độ chính xác chưa cao. 1.2. NGHIÊN CỨU CÁC THUẬT TOÁN PHÂN LOẠI HÀNH VI GIA SÚC 1.2.1 Tổng quan về các phương pháp học máy 1.2.1.1. Giới thiệu về học máy Học máy, có tài liệu gọi là máy học, 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ừ 3
dữ liệu để giải quyết những vấn đề cụ thể. Ví dụ như các máy có thể "học" cách phân loại thư điện tử xem có phải thư rác hay không và tự động xếp thư vào thư mục tương ứng. Học máy có liên quan lớn đến 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 khác với thống kê, 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. Học máy có hiện nay được áp dụng rộng rãi bao gồm máy truy tìm dữ liệu, chẩn đoán y khoa, phân loại hành vi của gia súcphát hiện thẻ tín dụng giả, phân tích thị trường chứng khoán, phân loại các chuỗi DNA, nhận dạng tiếng nói và chữ viết, dịch tự động, chơi trò chơi và cử động rô-bốt. 1.2.1.2. Các giải thuật học máy Xét theo phương thức học, các thuật toán học máy được chia làm 4 nhóm bao gồm “học máy có giám sát” (Supervised Learning), “Học không giám sát” (Unsupervised Learning), “Học bán giám sát” (hay học kết hợp - Semi-supervised Learning) và “Học tăng cường” (Reinforcement Learning) - Học có giám sát: Học có giám sát hay còn gọi là học có thầy là thuật toán dự đoán nhãn (label)/đầu ra (output) của một dữ liệu mới dựa trên tập dữ liệu huấn luyện mà trong đó mỗi mẫu dữ liệu đều đã được gán nhãn. Dữ liệu huấn luyện bao gồm các cặp gồm đối tượng đầu vào (thường dạng vec-tơ), và đầ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 qui), hay 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). Phương pháp này sử dụng cho các bài toán phân lớp. - Học không giám sát: hay học không thầy là thuật toán dự đoán nhãn của một dữ liệu mới dựa trên tập dữ liệu huấn luyện mà trong đó tất cả các mẫu dữ liệu đều chưa được gán nhãn hay nói cách khác là ta không biết câu trả lời chính xác cho mỗi dữ liệu đầu vào. Khi đó, mục tiêu của thuật toán unsupervised learning không phải là tìm đầu ra chính xác mà sẽ hướng tới việc tìm ra cấu trúc hoặc sự liên hệ trong dữ liệu để thực hiện một công việc nào đó, ví như gom cụm (clustering) hoặc giảm số chiều của dữ liệu (dimension reduction) để thuận tiện trong việc lưu trữ và tính toán. Các bài toán Unsupervised learning tiếp tục được chia nhỏ thành hai loại là phân cụm (Clustering) và luật kết hợp (Association Rule). 4
- Học máy bán giám sát: là một lớp của kỹ thuật học máy, sử dụng cả dữ liệu đã gán nhãn và 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 bán 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). - Học tăng cường: Máy tính đưa ra quyết định hà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 hành động của mình. Trong luận văn này, thuật toán SVM và decission-tree là học có giám sát, thuật toán k-means là học không giám sát. 1.2.2. Thuật toán phân cụm k-means K-means là một thuật toán phân cụm đơn giản thuộc loại học không giám sát (tức là dữ liệu không có nhãn) và được sử dụng để giải quyết bài toán phân cụm. Ý tưởng của thuật toán phân cụm k-means là phân chia 1 bộ dữ liệu thành các cụm khác nhau. Trong đó số lượng cụm được cho trước là k. Công việc phân cụm được xác lập dựa trên nguyên lý: Các điểm dữ liệu trong cùng 1 cụm thì phải có cùng 1 số tính chất nhất định. Tức là giữa các điểm trong cùng 1 cụm phải có sự liên quan lẫn nhau. Đối với máy tính thì các điểm trong 1 cụm đó sẽ là các điểm dữ liệu gần nhau. Thuật toán phân cụm k-means là một phương pháp được sử dụng trong phân tích tính chất cụm của dữ liệu. Do đó nó đặc biệt được sử dụng nhiều trong khai phá dữ liệu và thống kê. Nó phân vùng dữ liệu thành k cụm khác nhau. Giải thuật này giúp chúng ta xác định được dữ liệu của chúng ta nó thực sử thuộc về nhóm nào. Mục đích của phân cụm là tìm ra đặc trưng bên trong của các nhóm của dữ liệu. Các thuật toán phân cụm đều sinh ra các cụm. Tuy nhiên, không có tiêu chí nào là được xem là tốt nhất của của phân tích phân cụm, điều này phụ thuộc vào mục đích của phân cụm như: data reduction, “natural clusters”, “usefull” clusters, outlier detection. Khác với việc phân lớp đối tượng, nhãn của lớp là chưa biết. Điều này xảy ra thường xuyên với những cơ sở dữ liệu lớn, vì việc gán nhãn lớp cho số lượng đối 5
tượng dữ liệu lớn là một quá trình tốn kém. Việc phân cụm rất có ích trong đưa ra cái nhìn tổng quan trên toàn thể dữ liệu. K-means là thuật toán rất quan trọng và được sử dụng phổ biến trong kỹ thuật phân cụm. Ý tưởng chính của thuật toán k-means là tìm cách phân nhóm các đối tượng đã cho vào K cụm (K là số các cụm được xác định trước, K nguyên dương) sao cho tổng bình phương khoảng cách giữa các đối tượng đến tâm nhóm là nhỏ nhất. Thuật toán k-means thực hiện qua các bước chính sau: Bước 1: Khởi tạo K điểm dữ liệu trong bộ dữ liệu và tạm thời coi nó là tâm của các cụm dữ liệu. Mỗi cụm được đại diện bằng các tâm của cụm. Bước 2: Với mỗi điểm dữ liệu trong bộ dữ liệu, tâm cụm của nó sẽ được xác định là 1 trong K tâm cụm gần nó nhất. Bước 3: Sau khi tất cả các điểm dữ liệu đã có tâm, tính toán lại vị trí của tâm cụm để đảm bảo tâm của cụm nằm ở chính giữa cụm. Bước 4: Bước 2 và bước 3 sẽ được lặp đi lặp lại cho tới khi vị trí của tâm cụm không thay đổi hoặc tâm của tất cả các điểm dữ liệu không thay đổi. Sơ đồ dưới đây mô tả thuật toán k-means 6
Hình 1.1. Sơ đồ giải thuật toán k-means Thuật toán k-means là một thuật toán đơn giản, đệ quy (lặp đi lặp lại nhiều lần) nên chi phí tính toán sẽ lớn. 1.2.3. Thuật toán máy vector hỗ trợ (SVM) Thuật toán máy vector hỗ trợ (Support Vector Machines - SVM) được Corters và Vapnik giới thiệu vào năm 1995. SVM rất hiệu quả để giải quyết các bài toán với dữ liệu có số chiều lớn như các vector biểu diễn văn bản. Thuật toán SVM ban đầu chỉ được thiết kế để giải quyết bài toán phân lớp nhị phân tức là số lớp hạn chế là hai lớp. Hiện nay, SVM được đánh giá là bộ phân lớp chính xác nhất cho bài toán phân lớp văn bản, bởi vì đó là bộ phân lớp tốc độ rất nhanh và hiệu quả đối với bài toán phân lớp văn bản Phương pháp SVM được coi là phương pháp hiệu quả để giải quyết bài toán phân lớp với dữ liệu có số chiều lớn như các vector biểu diễn văn bản. Về mặt lý thuyết, thuật toán phân lớp nhị phân này cũng có thể sử dụng cho bài toán phân lớp đa lớp bằng cách chuyển bài toán đa lớp thành bài toán nhị phân. Tuy nhiên, đối với bài toán phân lớp văn bản sử dụng phương pháp SVM thì việc lựa chọn thuộc tính cho từng phân lớp lại là vấn đề cực kỳ quan trọng, nó quyết định đến hiệu quả của phân lớp. Bài toán phân lớp dữ liệu là quá trình phân lớp một đối tượng dữ liệu vào một hay nhiều lớp cho trước nhờ một mô hình phân lớp mà mô hình này được xây dựng dựa trên một tập hợp các đối tượng dữ liệu đã được gán nhãn từ trước gọi là tập dữ 7
liệu học (tập huấn luyện). Quá trình phân lớp còn được gọi là quá trình gán nhãn cho các đối tượng dữ liệu. Như vậy, nhiệm vụ của bài toán phân lớp dữ liệu là cần xây dựng mô hình phân lớp để khi có một dữ liệu mới vào thì mô hình phân lớp sẽ cho biết dữ liệu đó thuộc lớp nào. Quá trình phân lớp dữ liệu gồm hai bước là quá trình học và quá trình phân lớp. Máy vector hỗ trợ (SVM): Hình 1.2 dưới đây minh họa về tìm biên lớn nhất của thuật toán SVM: Hình 1.2. Thuật toán SVM Phương pháp SVM là cho trước một tập huấn luyện, được biểu diễn trong không gian vector, trong đó mỗi tài liệu là một điểm, phương pháp này tìm ra một siêu phẳng quyết định tốt nhất có thể chia các điểm trên không gian này thành hai lớp riêng biệt tương ứng là lớp + và lớp o. Một siêu phẳng là một hàm tương tự như phương trình đường thẳng y = ax + b. Thực tế, nếu ta cần phân lớp tập dữ liệu chỉ gồm 2 tính năng, siêu phẳng lúc này chính là một đường thẳng. Chất lượng của siêu phẳng này được quyết định bởi khoảng cách (gọi là biên) của điểm dữ liệu gần nhất của mỗi lớp đến mặt phẳng này. Khi đó, khoảng cách biên càng lớn thì mặt phẳng quyết định càng tốt, đồng thời việc phân loại càng chính xác. Mục đích của phương pháp SVM là tìm được khoảng cách biên lớn nhất. Thuật toán SVM được thực hiện qua các bước sau: 8
 Chuyển dữ liệu đầu vào về dạng số của SVM.  Tiền xử lý dữ liệu: Thực hiện biến đổi dữ liệu phù hợp cho quá trình tính toán, tránh các số quá lớn mô tả các thuộc tính. Nên co giãn dữ liệu để chuyển về đoạn [-1, 1] hoặc [0, 1].  Chọn hàm hạt nhân: Lựa chọn hàm hạt nhân phù hợp tương ứng cho từng bài toán cụ thể để đạt được độ chính xác cao trong quá trình phân lớp.  Thực hiện việc kiểm tra chéo để xác định các tham số cho ứng dụng. Điều này cũng quyết định đến tính chính xác của quá trình phân lớp.  Sử dụng các tham số cho việc huấn luyện với tập mẫu. Trong quá trình huấn luyện sẽ sử dụng thuật toán tối ưu hóa khoảng cách giữa các siêu phẳng trong quá trình phân lớp, xác định hàm phân lớp trong không gian đặc trưng nhờ việc ánh xạ dữ liệu vào không gian đặc trưng bằng cách mô tả hạt nhân, giải quyết cho cả hai trường hợp dữ liệu là phân tách và không phân tách tuyến tính trong không gian đặc trưng.  Kiểm thử tập dữ liệu Kiểm tra. 1.2.4. Thuật toán cây quyết định Trong lĩnh vực học máy, cây quyết định là một kiểu mô hình dự báo, nghĩa là một ánh xạ từ các quan sát về một sự vật/hiện tượng tới các kết luận về giá trị mục tiêu của sự vật/hiện tượng. Mỗi một nút trong tương ứng với một biến; đường nối giữa nó với nút con của nó thể hiện một giá trị cụ thể cho biến đó. Mỗi nút đại diện cho giá trị dự đoán của biến mục tiêu, cho trước các giá trị của các biến được biểu diễn bởi đường đi từ nút gốc tới nút đó. Kỹ thuật học máy dùng trong cây quyết định được gọi là học bằng cây quyết định, hay chỉ gọi với cái tên ngắn gọn là cây quyết định. Cây quyết định cũng nằm trong bài toán phân lớp (học có giám sát). Để xây dựng cây quyết định cũng cần phải có 2 bước là “Học” và “Phân lớp”. Học bằng cây quyết định cũng là một phương pháp thông dụng trong khai phá dữ liệu. Khi đó, cây quyết định mô tả một cấu trúc cây, trong đó, các lá đại diện cho các phân loại còn cành đại diện cho các kết hợp của các thuộc tính dẫn tới phân loại đó. Một cây quyết định có thể được học bằng cách chia tập hợp nguồn thành các tập con dựa theo một kiểm tra giá trị thuộc tính. Quá trình này được lặp lại một cách đệ qui cho mỗi tập con dẫn xuất. Quá trình đệ qui hoàn thành khi không thể tiếp tục thực hiện 9
việc chia tách được nữa, hay khi một phân loại đơn có thể áp dụng cho từng phần tử của tập con dẫn xuất. Một bộ phân loại rừng ngẫu nhiên sử dụng một số cây quyết định để có thể cải thiện tỉ lệ phân loại. Cây quyết định cũng là một phương tiện có tính mô tả dành cho việc tính toán các xác suất có điều kiện. Ưu điểm của cây quyết định:  Dễ dàng chuyển đổi: Cây quyết định có khả năng sinh ra các quy tắc có thể chuyển đổi được sang dạng tiếng Anh, hoặc các câu lệnh SQL. Đây là ưu điểm nổi bật của kỹ thuật này. Thậm chí với những tập dữ liệu lớn khiến cho hình dáng cây quyết định lớn và phức tạp, việc đi theo bất cứ đường nào trên cây là dễ dàng theo nghĩa phổ biến và rõ ràng. Do vậy sự giải thích cho bất cứ một sự phân lớp hay dự đoán nào đều tương đối minh bạch.  Khả năng thực thi trong những lĩnh vực hướng quy tắc: Điều này có nghe có vẻ hiển nhiên, nhưng quy tắc quy nạp nói chung và cây quyết định nói riêng là lựa chọn hoàn hảo cho những lĩnh vực thực sự là các quy tắc. Rất nhiều lĩnh vực từ di truyền tới các quá trình công nghiệp thực sự chứa các quy tắc ẩn, không rõ ràng do khá phức tạp và tối nghĩa bởi những dữ liệu lỗi. Cây quyết định là một sự lựa chọn tự nhiên khi chúng ta nghi ngờ sự tồn tại của các quy tắc ẩn, không rõ ràng.  Dễ dàng tính toán trong khi phân lớp: Mặc dù như chúng ta đã biết, cây quyết định có thể chứa nhiều định dạng, nhưng trong thực tế, các thuật toán sử dụng để tạo ra cây quyết định thường tạo ra những cây với số phân nhánh thấp và các kiểm tra đơn giản tại từng node. Những kiểm tra điển hình là: so sánh số, xem xét phần tử của một tập hợp, và các phép nối đơn giản. Khi thực thi trên máy tính, những kiểm tra này chuyển thành các toán hàm logic và số nguyên là những toán hạng thực thi nhanh và không đắt. Đây là một ưu điểm quan trọng bởi trong môi trường thương mại, các mô hình dự đoán thường được sử dụng để phân lớp hàng triệu thậm chí hàng tỉ bản ghi.  Khả năng xử lý với cả thuộc tính liên tục và thuộc tính rời rạc: Cây quyết định xử lý “tốt” như nhau với thuộc tính liên tục và thuộc tính rời rạc. Tuy rằng với thuộc tính liên tục cần nhiều tài nguyên tính toán hơn. Những thuộc tính 10