Phụ thuộc thông tin

ntropy 
của X là đại lượng H(X), xác định bởi công thức sau: 
 n 1
 H( X )  p ( xi )log , 
 i 1 px()i
với quy định 0log0 0 . Cơ số hàm lô-ga-rít ở đây được lấy là 2, đơn vị đo của Entropy là 
bit. 
 Entropy HX() là số đo độ bất định, không chắc chắn (uncertainty) của X. Một đại 
lượ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ác 
suấ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ấp 
và 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ân 
phố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ố bit 
trung 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 
 n
 dãy số Q q12, q , ... , qn thỏa mãn  q j 1 với mọi 0 jn và 
 j 1
n
 q j 1. Khi đó, ta có: 
i 1
 nn11
 H() X  p ()log xii p ()log x . 
 ii 11p() xij q
 Chứng minh: Sử dụng bất đẳng thức logx x 1, ta có: 
54 TRƯỜNG ĐẠI HỌC THỦ ĐÔ HÀ NỘI 
 qq
 logii 1 . 
 p()() xii p x
 Suy ra: 
 qi
 p( xi )log q i p ( x i ) , 
 px()i
 p( xi )(log q i log p ( x i )) q i p ( x i ) , 
 p()log() xi p x i p ()log x i q i q i p () x i , 
 11
 p( xi )log p ( x i )log q i p ( x i ) , 
 p() xii q
 nn11 
 p( xi )log p ( x i )log q i p ( x i ) , 
 ii 11p() xii q
 n11 n n n
 p( xi )log  p ( x i )log  q i  p ( x i ) , 
 i 1p() xii i 1 q i 1 i 1
 n n nn
 Vì  q j 1,  px(i ) 1 , nên qii p( x ) 0 . Suy ra: 
 j 1 i 1 ii 11
 nn11
 H( X )  p ( xii )log p ( x )log . □ 
 ii 11p() xii q
 Mệnh đề 2.1. Cận dưới và cận trên của entropy 
 Cho biến ngẫu nhiên X có hàm phân bố xác suất PXn ( p ( x12 ), p ( x ), ..., p ( x )) . Ta có: 
0 H ( X ) log n 
 1
 Chứng minh: Vì 0 px (i ) 1, ta có log 0 với mọi1 in. Suy ra H( X ) 0. Dấu 
 px()i
“=” xảy ra khi và chỉ n 1 . 
 1 n
 Đặt qi , in 1,2, ... , . Thế thì 01 q j với mọi 0 jn và  q j 1. Sử dụng Bổ đề 
 n j 1
2.1. ta có: 
 n11 n n
 H( X )  p ( xi )log  p ( x i )log log n  p ( x i ) log n 
 i 1p() xii i 1 q i 1
 1
 Đẳng thức xảy ra khi px() , in 1,2, ... , . □ 
 i n
 Định nghĩa 2.2. (Entropy có điều kiện – conditional entropy) 
TẠP CHÍ KHOA HỌC SỐ 2/2016 55 
 Cho hai biến ngẫu nhiên X và Y với phân bố xác suất lần lượt là 
PXn ( p ( x12 ), p ( x ), ..., p ( x )) và PYm ( p ( y12 ), p ( y ), ..., p ( y )). Entropy có điều kiện của Y khi X đã 
biết, ký hiệu là HYX , được định nghĩa như sau: 
 nm 1
 H Y X p( xi ) p y j / x i log2 
  p(/) y x
 ij 11 ji
 Entropy có điều kiện là lượng Entropy còn lại của Y khi biết X, là số đo độ 
phụ thuộc của Y vào X. 
 Định nghĩa 2.3. (Entropy đồng thời – Joint entropy ) 
 Cho hai biến ngẫu nhiên X và Y với phân bố xác suất lần lượt là 
 và . Entropy đồng thời của X và Y là đại 
lượng: 
 nm 1
 H( X , Y )  p xij , y log2 
 ij 11 p xij, y 
 Hiển nhiên : HXYHYX(,)(,) 
 Mệnh đề 2.2. Cận dưới và cận trên của entropy đồng thời 
 Cho hai biến ngẫu nhiên X và Y có hàm phân bố xác suất lần lượt là 
 và 
 Khi đó : 
 max HXHYHXYHXHY (),() (,) () () . 
 Chứng minh : 
 a) Bất đẳng thức bên trái 
 m
 Ta có : p()(,) xi  p x i y j . Đặt qi max p ( x i , y j ) |1 j m . Khi đó với mọi j: 
 j 1
 p(,)() xi y j q i p x i 
 1 1 1
 Suy ra : log log log 
 p()(,) xi q i p x i y j
 Mà theo Bổ đề 2.1.: 
 nn11nm 1
 H( X )  p ( xii )log p ( x )log =  p( xij , y )log 
 ii 11p() xii q ij 11 qi
 nm 1
  p( xij , y )log H ( X , Y ) 
 ij 11 p(,) xij y
56 TRƯỜNG ĐẠI HỌC THỦ ĐÔ HÀ NỘI 
 Bằng cách tương tự, ta cũng có: HYHXY()(,) . Vậy: max HXHYHXY (),() (,) 
 b) Bất đẳng thức bên phải 
 nm11
 H( X ) H ( Y ) p ( x )log p ( y )log
 ijp()() x p y
 ij 11ij 
 n m11 m n
  p( xi , y j ) log   p ( x i , y j ) log 
 i 1 j 1p()() xij j 1 i 1 p y
 nm 11
 p( x , y ) log log
  ij p()() x p y
 ij 11 ij 
 nm 1
 p( x , y )log
  ij p()() x p y
 ij 11 ij 
 nm 1
  p( xij , y )log H ( X , Y ) . 
 ij 11 p(,) xij y
 Đẳng thức xảy ra khi X và Y độc lập, tức là khi p(,)()() xi y j p x i p y j . □ 
3. ĐỘ PHỤ THUỘC THÔNG TIN VÀ CÁC TÍNH CHẤT 
 Cho quan hệ r xác định trên tập thuộc tính  {}X12 , XX ,..., p . Như thường lệ, ta sẽ ký 
hiệu phép chiếu và phép chọn của đại số quan hệ lần lượt bằng  và  (kết quả của các 
phép toán này là những tập hợp). 
 Cho tập thuộc tính X . Giả sử  (r ) x ,..., x và c()() x  r với 1 in, 
 Xn 1  i X xi
 p cx()
trong đó . chỉ lực lượng của một tập hợp. Hiển nhiên, ta có: cx( ) 1 và i 1 . Do 
 i  i 1 r
đó, X xác định một biến ngẫu nhiên rời rạc có phân bố xác suất PXn ( p ( x12 ), p ( x ), ..., p ( x )) , 
 cx()
trong đó px() i với in 1, ... , . Như vậy, ta có thể nói tới các đại lượng thông tin của 
 i r
các tập thuộc tính trong  . Sử dụng kết quả của phép chọn trong r,ta có thể viết lại các 
định nghĩa như sau: 
 1) Entropy của X trên r là đại lượng HrX () xác định bởi: 
 n cx() r
 Hr( ) i log .
 X  r c() x
 j 1 i 
 Trong đó: nr  ()c()() x  r
 X i X xi
 2) Entropy có điều kiện của Y khi X đã cho là đại lượng HrYX()xác định bởi: 
TẠP CHÍ KHOA HỌC SỐ 2/2016 57 
 nc()()() x mc(,)(,) x y c x n m c x y c x
 Hr( ) ii j log i i j log i
 YX r  c()(,)(,) x c x y  r c x y
 i 1 j 1i i j i 1 j 1 i j 
 Trong đó: mr  ()c(,)() x y  r 
 Y i j X xij, Y y
 3) Entropy đồng thời của X và Y là đại lượng HrXY ()xác định bởi: 
 nm
 c(,) xij y r
 HrXY ( )  log 
 ij 11 r c(,) xij y
 Từ các khái niệm trên, ta định nghĩa Độ đo phụ thuộc thông tin như sau: 
 Định nghĩa 2.4. (Độ phụ thuộc thông tin) 
 Độ phụ thuộc thông tin (Information Dependency) của Y khi X đã cho là đại lượng 
HrYY () định nghĩa bởi: 
 n m n m
 c()()() xic(,)(,) xi y j c x i c x i y j c x i
 HYY ( r ) HYX ( r )   log  log 
 i 1r j 1 c()(,)(,) xi c x i y j i 1 j 1 r c x i y j
 Độ phụ thuộc thông tin có các tính chất đáng chú ý sau đây: 
 Mệnh đề 2.3. HX Y()()() r H XY r H X r . 
 Chứng minh: 
 Ta có: 
 nm
 c(,) xij y cx()i
 HrXY ()  log 
 ij 11 r c(,) xij y
 nm
 c(,) xij y
  logc ( xi ) log c ( x i , y j ) 
 ij 11 r
 nmc(,) x y 11
 ijlog log
  
 ij 11 r c(,)() xi y j c x i
 nmc(,) x y 11
 ij log logrr log log
  r c(,)() x y c x
 ij 11 i j i 
 nmc(,) x y rr
 ijlog log
  
 ij 11 r c(,)() xi y j c x i
 n mc(,)(,) x yrr n m c x y
 i jlog i j log
    
 i 1 j 1r c(,)() xi y j i 1 j 1 r c x i
58 TRƯỜNG ĐẠI HỌC THỦ ĐÔ HÀ NỘI 
 n mc(,) x y rr n cx()
 ijlog  i log 
 i 1 j 1r c(,)() xi y j i 1 r c x i
 HXY()() r H X r .□ 
 Mệnh đề 2.4. Luật phản xạ 
 Nếu YX   thì H XY 0 . 
 Chứng minh: 
 Vì YX , nên X YZ, Z  . Ứng dụng Mệnh đề 2.3. ta có: 
 HX Y() r H XY () r H X () r H X () r H X ()0 r □ 
 Mệnh đề 2.5. HXZ YZ()() r H XZ Y r . 
 Chứng minh: 
 Ứng dụng Mệnh đề 3.3. ta có: 
 HXZ YZ()()()()()()() rHrHrH XYZ XZ XZ Y rHrHrH XZ XZ XZ Y r □ 
 Bổ đề 2.6. Luật hợp phải 
 HHHX Y X Z X YZ . Đẳng thức xảy ra nếu các biến cố Yy j và Yy k là độc lập 
nhau khi đã biết Xx i . 
 Chứng minh: 
 Ta có: 
 n m n m
 c(,) xij y c()(,)() xi c x i z k c x i
 HXYXZ ( r ) H ( r )  log  log 
 i 1 j 1r c(,)(,) xi y j i 1 j 1 r c x i z k
 nmq
 c(,,) xi y j z k c()() x c x
  logii log 
 i 1 j 1 k 1 r c( xi , y j ) c ( x i ,z k )
 nmq 11
 p( xi , y j , z k ) log log 
 i 1 j 1 k 1 p()() yj x i p z k x i
 nmq 1
 p( x ) p ( y , z x )log
 i  j k i p()() y x p z x
 i 1 j 1 k 1 j i k i 
 mq
 Đặt q p()() y x p z x , ta có q 0 , q 1 . Áp dụng Bổ đề 2.1 thu được: 
 j k j i k i jk jk 11jk
TẠP CHÍ KHOA HỌC SỐ 2/2016 59 
 mqq11 n m
 p(, yj z k x i )log  p () x i  p (, y j z k x i )log . 
 j 1 k 1p()() yj x i p z k x i i 1 j 1 k 1 p(,) yj z k x i
 Vậy: 
 nmq 1
 HrHrpxXY () XZ ()  () i  pyzx (, jki )log Hr XYZ () . 
 i 1 j 1 k 1 p(,) yj z k x i
 Trường hợp Yy j và Yy k là độc lập nhau khi đã biết Xx i thì: 
 nmq
 HXYXZ ()() r H r pi  p j k| ilog1 p j | i p k | i 
 i 1 j 1 k 1
 nmq
 = pi  p j k|| ilog1 p j k i 
 i 1 j 1 k 1
 HrX YZ (). □ 
 Mệnh đề 2.7. Quy tắc xích 
 HXYZ () r H XY () r H XYZ ()max( r H XY (), r H XYZ () r 
 Chứng minh: 
 Sử dụng Mệnh đề 2.3. ta có: 
 HX YZ()()() rHrHrH XYZ X XY Z rHrHr XY X = HXY Z r H X Y r . □ 
 Mệnh đề 2.8. HHXY Z X Z 
 Chứng minh: 
 Sử dụng Mệnh đề 2.7. ta có: 
 HXY Z()()() r H X YZ r H X Y r 
 HXYXZXY ()()() r H r H r (Mệnh đề 2.6.) 
 HrXZ (). □ 
 Mệnh đề 2.9. Luật hợp trái 
 min HX Z ( r ), H Y Z ( r ) H XY Z ( r ) 
 Chứng minh: 
 Theo Mệnh đề 2.8. ta có: HX Z()() r H XY Z r , 
 HY Z()() r H XY Z r . 
 Vậy: min HX Z ( r ), H Y Z ( r ) H XY Z ( r ) . □ 
60 TRƯỜNG ĐẠI HỌC THỦ ĐÔ HÀ NỘI 
 Mệnh đề 2.10. Luật tăng trưởng 
 HXZ YZ()() r H X Y r 
 Chứng minh: 
 Theo Bổ đề 2.5. và 2.8. ta có: 
 HXZ YZ()()() r H XZ Y r H X Y r . □ 
 Mệnh đề 2.11. Luật bắc cầu 
 HXYYZXZ ()()() r H r H r 
 Chứng minh: 
 HXY ()()()() r H YZ r H XZY r H XYXZ r (Mệnh đề 2.10.) 
 HXY()()()() r H X r H XYZ r H XY r (Mệnh đề 2.3.) 
 HXYZ()() r H X r 
 H()() r H r (Mệnh đề 2.2.) 
 XZ X 
 HXZ()() r H r (Mệnh đề 2.3.) □ 
 Mệnh đề 2.12. Luật hợp toàn phần 
 HX Y()()() r H W Z r H XW YZ r 
 Chứng minh: 
 HXYWZ ()() r H r 
 HXW YW()() r H WY ZY r (Mệnh đề 2.10.) 
 HrXW YZ ()(Mệnh đề 2.11.) 
 Mệnh đề 2.13. Luật phân rã 
 Nếu ZY thì HXYXZ ()() r H r 
 Chứng minh: 
 HrYZ ( ) 0(Mệnh đề 2.4.) 
 HXYYZXZ ()()() r H r H r (Mệnh đề 2.11.) 
 HXYXZ ()() r H r . □ 
 Mệnh đề 2.14. Luật giả bắc cầu 
 HX Y()()() r H WY Z r H XW Z r 
 Chứng minh: 
TẠP CHÍ KHOA HỌC SỐ 2/2016 61 
 HX Y()() r H WY Z r 
 HXWYWWYZ ()() r H r (Mệnh đề 2.10.) 
 HrXWZ ()(Mệnh đề 2.11.) □ 
 Định nghĩa 2.5. (Độ phụ thuộc thông tin chuẩn hóa) 
 Độ phụ thuộc thông tin chuẩn hóa của Y khi X đã cho là đại lượng IAXY () r định 
nghĩa bởi: 
 HXYXYX ()()() r H r H r
 IAXY () r 
 log22 rr log 
 Từ các Mệnh đề 2.1. và 2.3. suy ra: 0 IAXY ( r ) 1. 
4. MỐI LIÊN HỆ GIỮA PHỤ THUỘC THÔNG TIN VÀ PHỤ THUỘC HÀM 
 A . Mối liên hệ 
 Các phụ thuộc hàm đã được nghiên cứu kĩ trong nhiều tài liệu. Cho hai tập thuộc tính 
XY, , ta nói Y phụ thuộc hàm vào X, viết XY , nếu mỗi giá trị X cho ta một giá trị 
duy nhất của Y. Có thể thấy phụ thuộc thông tin nghiên cứu trên đây là một mở rộng của 
phụ thuộc hàm. 
 Mệnh đề 3.1. Cho hai tập thuộc tính . thỏa mãn khi và chỉ khi 
HrXY ( ) 0 . 
 Chứng minh: 
 : Nếu thì với mỗi giá trị xi dom() X chỉ có tương ứng một giá trị duy nhất 
yj dom(Y) sao cho p( xij , y ) 0 . Suy ra, c(,)() xi y j c x i . Do đó, 
 n mc(,)(,) x ycx() n m c x y
 Hr( ) i j logi i j log1 0 .
 YX r c(,) x y  r
 i 1 j 1ij i 1 j 1 
  : Nếu thì H()() r H r . Suy ra: Hr( ) 0 với mọi x . Hơn nữa 
 XYX Yxi i
px(i ) 0 với mọi i. Vậy chỉ có duy nhất một giá trị ứng với , tức là . □ 
 B. Các tiên đề Armstrong 
 Các tiên đề Armstrong là rất quan trọng đối với lý thuyết phụ thuộc hàm vì chúng 
cung cấp cơ sở cho hệ thống suy diễn phụ thuộc. Thông thường các tiên đề Armstrong bao 
gồm 3 quy luật chính sau đây: 
 1. Luật phản xạ: Nếu YX thì 
 2. Luật tăng trưởng: Nếu thì XZ YZ 
62 TRƯỜNG ĐẠI HỌC THỦ ĐÔ HÀ NỘI 
 3. Luật bắc cầu: Nếu XY và YZ thì XZ . 
 Mệnh đề 3.2. Các tiên đề Armstrong suy ra trực tiếp từ các bất đẳng thức phụ thuộc 
thông tin. 
 Chứng minh: 
 Luật tăng trưởng: Nếu thì theo Mệnh đề 3.1. phải có HrXY ( ) 0. Theo mệnh đề 
2.10. HXZ YZ()() r H X Y r . 
 Suy ra: HrXZ YZ ( ) 0 (vì HrXZ YZ ( ) 0 ). Mà từ Mệnh đề 3.1. suy ra: XZ YZ . 
 Tương tự, luật phản xạ và luật bắc cầu suy được ra từ các Mệnh đề 5.4. và 5.11. □ 
5. KẾT LUẬN 
 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 XY hàm 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 XY . 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ừ đây, chúng tôi sẽ nghiên cứu thuật toán 
khai phá các phụ thuộc thông tin với ngưỡng phụ thuộc cho trước. 
 TÀI LIỆU THAM KHẢO 
1. Mampaey, M. (2010), “Mining non-redundant information-theoretic dependencies between 
 itemsets”, Technical report, University of Antwerp. 
2. Agrawal, R., Imielinski, T., Swami, A. (1993), “Mining association rules between sets of 
 items in large databases”, ACM SIGMODRecord 22 (2), pp.207-216. 
3. Han, J., Pei, J., Yin, Y. (2000), “Mining frequent patterns without candidate generation”, ACM 
 SIGMOD Record 29 (2), pp.1-12. 
4. Zaki, M., Parthasarathy, S., Ogihara, M., Li, W., et al. (1997), “New algorithms for fast 
 discovery of association rules”, Proceedings of KDD. 
5. Srikant, R., Agrawal, R. (1996), “Mining quantitative association rules in large relational 
 tables”, ACM SIGMOD Record 25 (2), pp.1-12. 
TẠP CHÍ KHOA HỌC SỐ 2/2016 63 
6. Kivinen, J., Mannila, H. (1995), “Approximate inference of functional dependencies from 
 relations”, Theoretical Computer Science 149 (1), pp.129-149. 
7. Huhtala, Y., Karkkainen, J., Porkka, P., Toivonen, H. (1999), “TANE: An efficient algorithm 
 for discovering functional and approximate dependencies”, The Computer Journal 42 (2), 
 pp.100-111. 
8. Dalkilic, M.M., Robertson, E.L. (2000), “Information dependencies”, In: Proceedings of ACM 
 PODS, pp.245-253. 
9. Heikinheimo, H., Hinkkanen, E., Mannila, H., Mielikäinen, T., Seppänen, J.K. (2007), 
 “Finding low-entropy sets and trees from binary data”, In: Proceedings of KDD, pp.350-359. 
10. Shannon, C.E. (1948), “A mathematical theory of communication”, Bell System Technical 
 Journal 27, pp.379-423. 
 INFORMATION DEPENDENCIES 
 Abstract: In this paper we present an information-theoretic approach to mining 
 dependencies between sets of attributes in a given relation instance. We describe the 
 dependence of a rule based on conditional entropy of consequent given antecedent, and 
 using the entropy of a rule to describe its complexity. This allows us to discover rules 
 with a high statistical dependence, and a low complexity. The problem of redundancy in 
 this context is also investigated, and we present two techniques to prune redundant rules. 
 An efficient and scalable algorithm is proposed, which exploits the inclusion-exclusion 
 principle for fast entropy computation. This algorithm is empirically evaluated through 
 experiments on synthetic and real-world data. 
 Keywords: Information dependencies, function dependencies, information theory, data 
 mining.