Ứng dụng Dempster - Shafer xây dựng mô hình suy luận

Bài viết trình bày kết quả nghiên cứu, ứng dụng lý thuyết Dempster Shafer (D-S) xây dựng mô hình tự suy luận, kết quả thực nghiệm với bộ dữ liệu Iris cho thấy mô hình có khả năng ra quyết định với độ chính xác cao, góp phần bổ sung cho lý thuyết đã đề xuất.
Nội dung trích xuất từ tài liệu:
Ứng dụng Dempster - Shafer xây dựng mô hình suy luận Kỹ thuật điều khiển & Điện tử ỨNG DỤNG DEMPSTER - SHAFER XÂY DỰNG MÔ HÌNH SUY LUẬN Bùi Công Thành1*, Vũ Tuấn Anh1 , Hoàng Trung Kiên 2 Tóm tắt: Bộ não của con người xử lý, phân tích dữ liệu thu thập từ các giác quan để nhận biết sự vật hiện tượng xung quanh. Theo cách đó, lĩnh vực nghiên cứu kỹ thuật kết hợp thông tin từ nhiều nguồn (Multiple Sensor Data Fusion) đã được đẩy mạnh nghiên cứu để nâng cao độ chính xác trong suy diễn, ra quyết định. Bài báo trình bày kết quả nghiên cứu, ứng dụng lý thuyết Dempster Shafer (D-S) xây dựng mô hình tự suy luận, kết quả thực nghiệm với bộ dữ liệu Iris cho thấy mô hình có khả năng ra quyết định với độ chính xác cao, góp phần bổ sung cho lý thuyết đã đề xuất. Keywords: Dempster-Shafer, D-S, Theory of Evidence, Multiple Sensor Data Fusion. 1. GIỚI THIỆU CHUNG Tổng hợp dữ liệu từ nhiều nguồn (THDLNN) là một kỹ thuật cho phép kết hợp các thông tin từ nhiều nguồn nhằm mục đích cải tiến hiệu suất của hệ thống [5]. Theo Siaterlis and Maglaris [2004], THDLNN là các bước xử lý dữ liệu thu thập từ nhiều nguồn thông tin thành một nguồn với mức độ thông tin tổng quát hơn, có nghĩa hơn. Theo Bass [1], THDLNN là một hướng nghiên cứu về các kỹ thuật để xử lý thông tin từ nhiều nguồn khác nhau, loại thông tin khác nhau để giúp suy diễn một sự kiện, nhận định rõ hơn một tình huống. Rất nhiều phương pháp THDLNN đã được nghiên cứu nhằm mục đích nâng cao độ chính xác trong ra quyết định, ứng dụng trong nhiều lĩnh vực như chỉ huy chiến trường; an ninh mạng; chuẩn đoán y học, sinh học; giám sát môi trường; đo lường, tự động hóa,… Một trong số các hướng nghiên cứu THDLNN là việc ứng dụng lý thuyết D-S, hiện đang được rất nhiều nhà nghiên cứu quan tâm [3]. Lý thuyết D-S được giới thiệu từ 1968 bởi tác giả Arthur Dempster và phát triển bởi Glenn Shafer. Lý thuyết D-S đưa ra một nền tảng mở trong ứng dụng để tạo ra mô hình ra quyết định dựa trên các suy luận không chắc chắn thu thập được. Theo Shafer [2], lập luận của lý thuyết D-S dựa trên hai ý tưởng chính: Mức độ của “niềm tin” cho mỗi giả thuyết trong tập tất cả các giả thuyết được đưa ra cho một vấn đề và hàm kết hợp (Dempster’s Rule), là phương pháp xác định “độ tin” khi kết hợp nhiều niềm tin hay giả thuyết với nhau. Lý thuyết D-S đề xuất phương án khả thi trong tính toán đưa ra kết luận dựa vào các lập luận không chắc chắn. Thuật toán chạy không cần thông tin về tri thức ban đầu của hệ thống do vậy đặc biệt phù hợp cho ứng dụng để nhận dạng, phát hiện bất thường. 2. LÝ THUYẾT DEMPSTER SHAFER 2.1. Định nghĩa Tập F, hoặc FoD (Frame of Discernment) là tập hợp tất cả các trạng thái có thể của một hệ thống nào đó, ta có tập hàm mũ là tập chứa tất cả các tập con của F [2] . Tập đôi khi còn được gọi là tập giả thuyết hoặc tập dẫn chứng. Ví dụ: F = { a, b, c}. Tập hàm mũ là tập chứa tất cả các tập con của F. Ta được: = { , a, b, c, ab, ac, bc, abc } Tùy theo đặc trưng của từng hệ thống cụ thể mà tập F có thể rất khác nhau. Chẳng hạn như trong hệ thống phân lớp dữ liệu, tập F chính là tập các nhãn lớp khác nhau. Hoặc trong các hệ thống phát hiện xâm nhập mạng, tập F chỉ đơn giản là trạng thái mạng bình thường hoặc mạng bị tấn công. 90 B. C. Thành, V. T. Anh, H. T. Kiên, “Ứng dụng Dempster – Shafer … mô hình suy luận.” Nghiên cứu khoa học công nghệ Lý thuyết D-S sử dụng một hàm để gán một mức độ “niềm tin” vào mỗi phần tử của tập hàm mũ. Hàm đó được gọi là Hàm niềm tin cơ bản (Basic Belief Assignment – BBA), có thể gọi tắt là hàm niềm tin: m: → [0,1] Với mỗi nguồn thông tin cung cấp các phần tử (giả thuyết) của tập , ta sẽ có hàm niềm tin tương ứng là , i = 1,…n. Hàm niềm tin của D-S có hai tính chất: - Khối niềm tin của tập rỗng là bằng 0 m( ) = 0 - Khối niềm tin của tất cả các tập con còn lại cộng vào với nhau có tổng bằng 1. =1 Khối niềm tin của một tập con A nào đó, m(A), chỉ liên quan tới bản thân tập A nhưng không liên quan đến bất kỳ tập con nào nằm trong A. Do vậy, có thể tìm được giới hạn trên và giới hạn dưới cho một khoảng xác suất nào đó của tập con A. D-S đưa ra hai khái niệm độ tin (belief) và độ hợp lý (plausibility) để tính các giới hạn đó: Bel(A) = Pl(A) = Một hàm BBA có thể được coi như là việc xác định một tập các xác suất P cho các phần tử (giả thuyết) của tập sao cho: Bel(A) ≤ P(A) ≤ Pl(A) Ngoài ra, mối liên hệ giữa hàm m, Bel và Pl còn được thể hiện qua công thức: Pl(A)=1-bel( ) m(A)= với |A -B |làsố phần tử khác nhau giữa tập A và B[5]. Vì vậy, chỉ cần xác định được một trọng ba tham số m, Bel và Pl là có thể suy ra hai tham số còn lại. 2.2. Luật kết hợp – Dempster’s Rule Luật kết hợp là phương pháp xác định độ tin tổng hợp khi kết hợp các dẫn chứng khác nhau. Phương trình kết hợp[2], độ tin của hai dẫn chứng được thể hiện như sau: ( )=0 (A) = (  ) (A) = (1) K= Trong đó: là thành phần tử số của hàm kết hợp K được gọi là thước đo mức độ xung đột giữa hai giả thuyết 1 - K là thành phần mẫu số của hàm kết hợp 3. MÔ HÌNH THDLNN ỨNG DỤNG D-S 3.1. Mô hình tổng quát Xét một hệ thống có n nguồn thông tin cùng không gian xác định , m là số chiều của không gian đó. Với mỗi nguồn, có thể không có đầy đủ m tính chất, giá trị của các tính chất này thể hiện đặc trưng của nguồn thông ti ...