tailieunhanh - Một thuật toán tìm tập rút gọn trong bảng quyết định không đầy đủ

Bài báo mở rộng khái niệm rút gọn tri thức lên lớp các bảng quyết định không đầy đủ. Bằng cách cải tiến phương pháp của Jiye Liang và Zongben Xu, dựa vào Entropy thô đã thiết lập một thuật toán Heuristic để tìm rút gọn bẳng quyết định không đầy đủ. . | Tạp chí Tin học và Điều khiền học 2009 69-78 MỘT THUẬT TOÁN TÌM TẬP RÚT GỌN TRONG BÁNG QUYẾT ĐỊNH KHÔNG ĐÂY ĐỦ HOÀNG THỊ LAN GIAO Khoa CNTT Trường Đại học Khoa học- Đại học Huế Abstract. The aim of this work is to generalize the concept of knowledge reduction to class of incomplete decision tables. By innovating the method of J. Liang and z. Xu 3 which based on rough entropy we establish a heuristic algorithm for finding a reduct of incomplete decision table. The time complexity of this algorithm is o kn log n where k is the number of conditional attributes and n is the number of objects in data table. Tóm tắt. Bài báo mở rộng khái niệm rút gọn tri thức lên lớp các bảng quyết định không đầy đủ. Bang cách cải tiến phương pháp của Jiye Liang và Zongben Xu 3 dựa vào entropy thô đã thiết lập một thuật tóan Heuristic để tìm rút gọn của bảng quyết định không đầy đủ. Độ phức tạp của thuật toán này là o kn2 logn với k là số thuộc tính điều kiện và n là số đối tượng trong bảng. 1. MỞ ĐẦU Đối với các mô hình dữ liệu lớn rất dl xãy ra tình trạng dữ liệu bị thiếu bởi nhiều lý do khác nhau. Việc rút gọn tri thức sẽ gặp khó khăn trong các hệ thống thông tin không đầy đủ nói chung và đặc biệt trong bảng quyết định các luật quyết định đưa ra sẽ không đầy đủ. Thông thường dữ liệu thiếu thông tin rơi vào một trong ba trường hợp 9 không có thông tin về dữ liệu không biết một người nào đó có số điện thoại hay không không tồn tại không có chức vụ tồn tại nhưng không biết ngày sinh . Trong khuôn khổ bài báo ta chỉ nghiên cứu bảng quyết định không đầy đủ với giá trị thuộc tính bị mất do tồn tại nhưng không biết. Một thuật toán tìm tập rút gọn dựa vào khái niêm entropy thô với bảng chứa dữ liệu bị thiếu loại này cũng đã được đề xuất. 2. CÁC KHÁI NIỆM . Hệ thống thông tin không đầy đú Cho A u A là một hệ thống thông tin với u là tập hữu hạn khác rỗng các đối tượng và A là tập hữu hạn khác rỗng các thuộc tính. Với mỗi u G u và a G A ta ký hiệu u a là giá trị thuộc tính a của đối