Luận văn Thạc sĩ Công nghệ kỹ thuật Điện tử Viễn thông: 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

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

Thêm vào BST

Báo xấu

30
lượt xem 4
download

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

Luận văn này đã thành công trong việc xây dựng 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 với độ chính xác phân loại đạt tới 89%.

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 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

ĐẠ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ố: 60520203 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 Ngành chăn nuôi, sản xuất sữa và thực phẩm là ngành kinh tế quan trọng trong phát triển kinh tế xã hội và an ninh lương thực thế giới. Để 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ố công ty sữa lớn như TH Truemilk, VINAMILK, để 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 hà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 hà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) ......................................................................6 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 ....................................................................................................... 26 Thiết bị LoRa Gateway .................................................................................................... 30 2.2. PHÂN LOẠI HÀNH VI GIA SÚC......................................................................... 32 2.2.1. Trạng thái hành vi gia súc ..................................................................................... 32 2.1.3. Xây dựng bộ tham số đánh giá phân loại gia súc................................................ 34 CHƯƠNG 3. KẾT QUẢ .................................................................................................... 37 3.1. HỆ THỐNG PHẦN CỨNG ..................................................................................... 37 3.2. THỬ NGHIỆM HỆ THỐNG ................................................................................... 37 3.3. KẾT QUẢ PHÂN LOẠI HÀNH VI SỬ DỤNG K-MEANS.............................. 37 3.4. MỘT SỐ SAI SỐ TRONG QUÁ TRÌNH THU DỮ LIỆU ................................. 37 KẾT LUẬN ........................................................................................................................... 46 TÀI LIỆU THAM KHẢO ................................................................................................. 47 iv
DANH MỤC HÌNH VẼ Hình 1.1. Sơ đồ giải thuật toán k-means...............................................................................6 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 .............................................. 26 Hình 2.11. Sơ đồ thuật toán thiết bị gắn cảm biến ........................................................... 29 Hình 2.12. Sơ đồ khổi hệ thống của LoRa Gateway ......................................................... 30 Hình 2.13. Sơ đồ thuật toán thiết bị LoRa Gateway ......................................................... 31 Hình 2.14. Hướng của các trục gia tốc gắn trên cổ bò .................................................... 33 Hình 2.15. Các trục cảm biến gia tốc khi bò đang đứng ................................................. 33 Hình 2.16. Hướng cảm biến gia tốc khi con bò đang ăn ................................................. 34 Hình 2.17. Hướng cảm biến gia tốc khi con bò đang nằm .............................................. 34 Hình 2.17. Phương pháp cửa sổ trượt ................................................................................ 36 Hình 3.1. Thiết bị phần cứng gắn cổ .................................................................................. 37 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/s 2) ............... 39 Hình 3.3. Khai thác đặc trưng VeDBA ............................................................................... 40 Hình 3.4. Khai thác đặc trưng SCAY .................................................................................. 40 Hình 3.5. Khai thác quan hệ giữa SCAY (trục tung) và VeDBA (trục hoành) .............. 41 Hình 3.6. Quan hệ giữa SCAY (trục tung) và VeDBA (trục hoành) ............................... 42 khi sử dụng k-means với thiết lập là 3 cụm khác nhau..................................................... 42 Hình 3.7. Dữ liệu gia tốc của tập kiểm tra......................................................................... 42 Hình 3.8. VeDBA của tập kiểm tra...................................................................................... 43 Hình 3.9. VeDBA của tập kiểm tra...................................................................................... 43 Hình 3.10. Quan hệ VeDBA – SCAY của tập kiểm tra ..................................................... 44 Hình 3.11. Chỉ số nhận dạng ước lượng (trên) và thực tế (dưới) ................................... 44 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 Ngày nay, nhu cầu xã hội về thực phẩm ngày càng cao, không những đòi hỏi về số lượng mà còn về 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... Cách thức này gây nhiều bất tiện cho người chăm sóc. Một trong những hệ được 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 Các nhóm giải thuật học máy: - Học có giám sát: là một kĩ thuật của ngành học máy để xây dựng một hàm từ tập dữ liệu huấn luyệ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: là phương pháp học máy nhằm tìm ra một mô hình phù hợp với các quan sát. Cho trước một mẫu chỉ gồm các đối tượng, cần tìm kiếm cấu trúc quan tâm của dữ liệu, và nhóm các đối tượng giống nhau ... Phương pháp này sử dụng cho các bài toán phân cụm, gom cụm. - 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. 4
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 Phân cụm là kỹ thuật quan trọng trong khai phá dữ liệu, nó thuộc lớp các phương pháp “Học không giám sát” trong Học Máy. Có rất nhiều định nghĩa khác nhau về kỹ thuật này, nhưng về bản chất ta có thể hiểu phân cụm là các qui trình tìm cách nhóm các đối tượng đã cho vào các cụm (clusters), sao cho các đối tượng trong cùng 1 cụm tương tự nhau và các đối tượng khác cụm thì không tương tự nhau. Mục đích của phân cụm là tìm ra bản chất bên trong 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í nào là đượ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 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ư 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: a) Chọn ngẫu nhiên K tâm cho K cụm. Mỗi cụm được đại diện bằng các tâm của cụm. b) Tính khoảng cách giữa các đối tượng đến K tâm (thường dùng khoảng cách Euclidean). c) Nhóm các đối tượng vào nhóm gần nhất. d) Xác định lại tâm mới cho các nhóm. e) Thực hiện lại bước b) cho đến khi không có sự thay đổi nhóm nào của các đối tượng. Sơ đồ dưới đây mô tả thuật toán k-means 5
Bắt đầu Số cluster K Tính tâm cụm Không thay đổi? Kết thúc Tính khoảng cách từ dữ liệu Nhóm dữ liệu dựa trên khoảng cách 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) Thực tế đặt ra nhu cầu là từ một cơ sở dữ liệu với nhiều thông tin ẩn con người có thể trích rút ra các quyết định nghiệp vụ thông minh. Phân lớp và dự đoán là hai dạng của phân tích dữ liệu nhằm trích rút ra một mô hình mô tả các lớp dữ liệu quan trọng hay dự đoán xu hướng dữ liệu tương lai. Phân lớp dự đoán giá trị của những nhãn xác định hay những giá trị rời rạc, có nghĩa là phân lớp thao tác với những đối tượng dữ liệu mà có bộ giá trị là biết trước. Trong khi đó, dự đoán lại xây dựng mô hình với các hàm dạng giá trị liên tục. Ví dụ mô hình phân lớp dự báo thời tiết có thể cho biết thời tiết ngày mai là mưa, hay nắng dựa vào những thông số về độ ẩm, sức gió, nhiệt độ, … của ngày hôm nay và các ngày trước đó. Hay nhờ các luật về xu hướng mua hàng của khách hàng trong siêu thị, các nhân viên kinh doanh có thể ra những quyết sách đúng đắn về lượng mặt hàng cũng như chủng loại bày bán… Một 6
mô hình dự đoán có thể dự đoán được tiền lương tiêu dùng của các khách hàng tiềm năng dựa trên những thông tin về thu nhập và nghề nghiệp của khách hàng. 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ữ 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:  Bước thứ nhất là quá trình học: Quá trình học nhằm xây dựng một mô hình mô tả một tập các lớp dữ liệu hay các khái niệm định trước. Đầu vào của quá trình này là một tập dữ liệu có cấu trúc được mô tả bằng các thuộc tính và được tạo ra từ tập các bộ giá trị của các thuộc tính đó. Mỗi bộ giá trị được gọi chung là một phần tử dữ liệu, có thể là các mẫu, ví dụ, đối tượng, bản ghi hay trường hợp. Trong tập dữ liệu này, mỗi phần tử dữ liệu được giả sử thuộc về một lớp định trước, lớp ở đây là giá trị của một thuộc tính được chọn làm thuộc tính gán nhãn lớp hay thuộc tính phân lớp. Đầu ra của bước này thường là các quy tắc phân lớp dưới dạng luật dạng if then, cây quyết định, công thức logic, hay mạng nơron.  Bước thứ hai là quá trình phân lớp: Phân lớp là dùng mô hình đã xây dựng ở bước trước (quá trình học) để phân lớp dữ liệu mới. Trước tiên độ chính xác mang tính chất dự đoán của mô hình phân lớp vừa tạo ra được ước lượng. Holdout là một kỹ thuật đơn giản để ước lượng độ chính xác đó. Kỹ thuật này sử dụng một tập dữ liệu kiểm tra với các mẫu đã được gán nhãn lớp. Các mẫu này được chọn ngẫu nhiên và độc lập với các mẫu trong tập dữ liệu đào tạo. Độ chính xác của mô hình trên tập dữ liệu kiểm tra đã đưa là tỉ lệ phần trăm các các mẫu trong tập dữ liệu kiểm tra được mô hình phân lớp đúng (so với thực tế). Nếu độ chính xác của mô hình được ước lượng dựa trên tập dữ liệu đào tạo thì kết quả thu 7
được là rất khả quan vì mô hình luôn có xu hướng “quá vừa” dữ liệu. Quá vừa dữ liệu là hiện tượng kết quả phân lớp trùng khít với dữ liệu thực tế vì quá trình xây dựng mô hình phân lớp từ tập dữ liệu đào tạo có thể đã kết hợp những đặc điểm riêng biệt của tập dữ liệu đó. Do vậy cần sử dụng một tập dữ liệu kiểm tra độc lập với tập dữ liệu đào tạo. Nếu độ chính xác của mô hình là chấp nhận được, thì mô hình được sử dụng để phân lớp những dữ liệu tương lai, hoặc những dữ liệu mà giá trị của thuộc tính phân lớp là chưa biết. Máy vector hỗ trợ (SVM):  Là phương pháp dựa trên nền tảng của lý thuyết thống kê nên có một nền tảng toán học chặt chẽ để đảm bảo rằng kết quả tìm được là chính xác.  Là thuật toán học giám sát được sử dụng cho phân lớp dữ liệu.  Là 1 phương pháp thử nghiệm, là 1 trong những phương pháp mạnh và chính xác nhất trong số các thuật toán nổi tiếng về phân lớp dữ liệu.  SVM là một phương pháp có tính tổng quát cao nên có thể được áp dụng cho nhiều loại bài toán nhận dạng và phân loại. 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 Ý tưởng của 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 8
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. Trong 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:  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 9
đ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 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: 10