Luận văn 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 ngꢀ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 lꢀ hoꢀn toꢀ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 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 của tôi PGS. TS. Trần Đức Tân. 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 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 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ô và các anh chị
em trong Khoa đã 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.
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, ngꢀ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
vꢀ 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 ngꢀ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 đꢀn gia súc cꢀ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 nhꢀ 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 hꢀnh vi nhưng độ chính xác còn thấp.
Luận văn nꢀ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 hꢀ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
MꢁC LꢁC
MꢁC LꢁC......................................................................................................................iv
DANH MꢁC HÌNH VẼ ..................................................................................................v
DANH MꢁC BẢNG BIỂU............................................................................................vi
DANH MꢁC VIẾT TẮT.............................................................................................. vii
DANH MꢁC KÍ HIỆU................................................................................................ viii
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.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
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
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
KẾT LUẬN ..................................................................................................................45
TꢀI LIỆU THAM KHẢO...........................................................................................46
iv
DANH Mꢁ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. 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.3. Khai thác đặc trưng VeDBA..........................................................................39
Hình 3.4. Khai thác đặc trưng SCAY ............................................................................39
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
v
DANH Mꢁ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 MꢁC VIẾT TẮT
Tiếng Anh đầyđủ
TiếngViệt
DBA
Dynamic Body Acceleration
Gia tốc cơ thể động
DBAx
DBAy
DBAz
VeDBA
SCAY
Dynamic Body Acceleration of x-axis
Dynamic Body Acceleration of y-axis
Dynamic Body Acceleration of z-axis
Gia tốc cơ thể động trục x
Gia tốc cơ thể động trục y
Gia tốc cơ thể động trục z
Vector of Dynamic Body Acceleration Vector gia tốc cơ thể động
Static Component of the Acceleration
in the Y-axis
Thành phần gia tốc tĩnh của
trục y
ADC
UART
I2C
Analog to Digital Converter
Bộ chuyển đội tương tự sang
số
Universal asynchronous receiver /
transmitter
Truyền nhận nối tiếp không
đồng bộ
Inter-Integrated Circuit
Mạch chuyển đổi giao tiếp
vii
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 đó lꢀ 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 vꢀ 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 vꢀ 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 vꢀ tương tác xã hội trong một đꢀn. Hꢀ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 vꢀ các hꢀ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 đó lꢀ 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, Hꢀ 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 bꢀ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 vꢀ 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 đó bꢀ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 thꢀ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 đꢀ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
nꢀ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 vꢀ nhược điểm khác
nhau. SVM vꢀ 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ễ dꢀ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 vꢀ 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ò vꢀ lưu vꢀo thẻ nhớ. Dữ liệu offline sau đó được dùng để phân loại một số
hꢀ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ả vꢀ độ 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ư vꢀ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 vꢀ 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)
vꢀ
“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ơ), vꢀ đầ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 mꢀ 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 lꢀ 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 nꢀ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 vꢀ chưa gán nhãn để huấn luyện - điển hình là một lượng nhỏ dữ liệu có gán
nhãn cùng với lượng lớn dữ liệu chưa gán nhãn. Học 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 hꢀnh động và nhận kết quả phản
hồi từ môi trường. Sau đó máy tính tìm cách chỉnh sửa cách ra quyết định hꢀnh động
của mình.
Trong luận văn nꢀ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) vꢀ đượ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ẽ lꢀ 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 lꢀ 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 lꢀ 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 vꢀ đượ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 lꢀ tìm cách phân nhóm các đối tượng
đã cho vꢀ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 vꢀ 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 vꢀ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á lꢀ 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ì đó lꢀ 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 lꢀ 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 nꢀ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 bꢀ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 mꢀ mô hình nꢀ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 lꢀ 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 nꢀ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 hꢀ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 nꢀ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 lꢀ 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 lꢀ
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 lꢀ “Học” vꢀ “Phân lớp”.
Học bằng cây quyết định cũng lꢀ 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 cꢀ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 nꢀ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 lꢀ 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 lꢀ ư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ễ dꢀ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 nꢀ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 vꢀ không đắt. Đây lꢀ 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
Tải về để xem bản đầy đủ
57 trang
19000
Free
Bạn đang xem 20 trang mẫu của tài liệu "Luận văn 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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- luan_van_nghien_cuu_phat_trien_mang_cam_bien_khong_day_giam.pdf
