Phụ thuộc thông tin

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.
Nội dung trích xuất từ tài liệu:
Phụ thuộc thông tin52 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. Đặcbiệ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ủacá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 đã đượckhá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ộctí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 haibộ 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 trongY. 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ỏamã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ỏkhỏi quan hệ để phụ thuộc hàm thỏa mãn. Các bộ dữ liệu bị loại có thể được coi như là1 Nhận bài ngày 15.01.2016, gửi phản biện và duyệt đăng ngày 25.01.2016. Liên hệ tác giả: Nguyễn Minh Huy; Email: nguyenminhhuy86@gmail.com.TẠP CHÍ KHOA HỌC  SỐ 2/2016 53những trường hợp ngoại lệ. Tuy nhiên, một phụ thuộc hàm X → Y có lỗi thấp, không nhấtthiết có nghĩa là Y phụ thuộc mạnh vào X, thậm chí trên thực tế, X và Y có thể được độc lậpnhau.2. ĐỘ ĐO PHỤ THUỘC HÀM XẤP XỈ DỰA VÀO LÝ THUYẾT THÔNG TIN a. Một số khái niệm của lý thuyết thông tin Để có thể định nghĩa độ đo phụ thuộc hàm xấp xỉ dựa vào lý thuyết thông tin, trướchết ta cần tới một số khái niệm cơ bản của lý thuyết thông tin [10]. Định nghĩa 2.1. (Entropy của biến ngẫu nhiên) Cho biến ngẫu nhiên rời rạc X có phân bố xác suất PX  ( p( x1 ), p( x2 ), ... , p( xn )), Entropycủa X là đại lượng H(X), xác định bởi công thức sau: n  p( x ) log p( x ) , 1 H(X )  i i 1 ivới quy định 0log 0  0 . Cơ số hàm lô-ga-rít ở đây được lấy là 2, đơn vị đo của Entropy làbit. Entropy H ( X ) là số đo độ bất định, không chắc chắn (uncertainty) của X. Một đạilượng ngẫu nhiên càng nhận nhiều giá trị và có phân phối càng đều thì tính bất định của nócàng lớn, độ chắc chắn càng nhỏ. Ngược lại, một đại lượng ngẫu nhiên có phân phối xácsuất càng chênh lệch (có các xác suất rất nhỏ và rất lớn) thì tính bất định của nó càng thấpvà do đó sẽ có lượng thông tin chưa biết nhỏ hơn nhiều so với lượng thông tin của phânphối xác suất đều. Entropy cho phép lượng hóa thông tin chứa trong một đơn vị dữ liệu: Nó là số bittrung bình tối thiểu mà người gửi cần để mã hóa thông điệp thông báo cho người nhận biếtđược giá trị thật của biến ngẫu nhiên. Bổ đề 2.1. Cho biến ngẫu nhiên rời rạc X có phân bố xác suất nPX  ( p( x1 ), p( x2 ), ... , p( xn )), dãy số Q  q1 , q2 , ... , qn  thỏa mãn q j 1 j ...