Bài viết trình bày phương pháp xây dựng độ đo phụ thuộc thông tin trong một quan hệ như là một độ đo phụ thuộc hàm xấp xỉ. Với hai tập thuộc tính X và Y, độ đo này sẽ gán cho chúng một số thực phản ánh mức độ phụ thuộc của Y vào X. | 52 TRƯỜNG ĐẠI HỌC THỦ ĐÔ HÀ NỘI PHỤ THUỘC THÔNG TIN Nguyễn Minh Huy 1 Trường Đại học Thủ đô Hà Nội Tóm tắt Trong báo cáo này chúng tôi trình bày phương pháp xây dựng độ đo phụ thuộc thông tin trong một quan hệ như là một độ đo phụ thuộc hàm xấp xỉ. Với hai tập thuộc tính X và Y độ đo này sẽ gán cho chúng một số thực phản ánh mức độ phụ thuộc của Y vào X. Độ đo được xây dựng dựa trên các độ đo entropy trong lý thuyết thông tin của Shannon và được chuẩn hóa để nó có giá trị nằm giữa 0 và 1. Giá trị độ đo bằng 0 khi và chỉ khi tồn tại phụ thuộc hàm X Y trong quan hệ. Và như thế giá trị của nó càng nhỏ thì sự phụ thuộc của Y vào X trong quan hệ càng gần phụ thuộc hàm X Y . Các tính chất của độ đo phụ thuộc thông tin cũng đã được nghiên cứu. Các tính chất này cho thấy có thể xem phụ thuộc thông tin là sự mở rộng của khái niệm phụ thuộc hàm. Từ khóa Phụ thuộc thông tin phụ thuộc hàm lý thuyết thông tin khai phá dữ liệu. 1. GIỚI THIỆU Phát hiện các quy luật từ dữ liệu là một nhiệm vụ phổ biến trong khai thác dữ liệu. Đặc biệt khai thác luật kết hợp trong các cơ sở dữ liệu giao tác thu hút sự quan tâm rất lớn của các nhà nghiên cứu 2 4 . Mục tiêu của khai thác luật kết hợp là tìm ra các quy luật có độ tin cậy cao về sự xuất hiện cùng nhau thường xuyên giữa các tập mục. Vấn đề này đã được khái quát hóa cho trường hợp các cơ sở dữ liệu quan hệ trong đó thường có cả các thuộc tính hạng mục lẫn thuộc tính số 5 . Trong tình huống này các nhà nghiên cứu dành sự chú ý đặc biệt đến việc phát hiện các phụ thuộc hàm và phụ thuộc hàm xấp xỉ 6 7 . Một phụ thuộc hàm X Y giữa hai bộ thuộc tính được cho là thỏa mãn trong một quan hệ nếu hai bộ có cùng giá trị về các thuộc tính thuộc X thì cũng có cùng giá trị về các thuộc tính trong Y. Trong thực hành người ta thường mong muốn phát hiện các quy luật gần như thỏa mãn. Để đo mức độ mắc lỗi của các phụ hàm người ta sử dụng một số độ đo trong đó quen thuộc nhất là g3 . g3 là số lượng tương đối tối thiểu của các bộ dữ liệu cần phải loại bỏ
