Phụ thuộc thông tin

52

TRƯỜNG ĐẠI HỌC THỦ ĐÔ HÀ NỘI

PHỤ THUỘC THÔNG TIN

Nguyễn Minh Huy ¹

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à . 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ỏ

g₃g₃

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à

¹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

53

nhữ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ất

thiế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ập

nhau.

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ước

hế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

của X là đại lượng H(X), xác định bởi công thức sau:

Entropy

P  (p(x ), p(x₂), ..., p(x_n)),

X

1

n

1

H(X ) 

p(x_i)log

,



p(x_i)

i1

với quy định

bit.

. Cơ số hàm lô-ga-rít ở đây được lấy là 2, đơn vị đo của Entropy là

0log0  0

Entropy

là số đo độ bất định, không chắc chắn (uncertainty) của X. Một đại

H(X)

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

q  1

dãy số Q  q ,q , ... ,q thỏa mãn

với mọi 0  j  n và

P  (p(x ), p(x₂), ..., p(x_n)),



_n



j

1

2

X

1

j1

n

q  1. Khi đó, ta có:



j

i1

n

1

.

H(X ) 

p(x )log



p(x )log



i

p(x_i)

q_j

i1

Chứng minh: Sử dụng bất đẳng thức

, ta có:

logx  x1

54

TRƯỜNG ĐẠI HỌC THỦ ĐÔ HÀ NỘI

q_i

log



1

.

p(x_i) p(x_i)

Suy ra:

q_i

p(x_i)log

 q  p(x )

,

i

p(x_i)

,

p(x )(logq log p(x ))  q  p(x )

i

,

p(x )log p(x )  p(x )logq q  p(x )

i

1

p(x_i)log

 p(x_i)log  q  p(x )

,

i

p(x_i)

q_i

n









1

p(x )log



p(x )log  q  p(x )

,







i

p(x_i)

q_i

i1

n

1

p(x )log



p(x )log



q  p(x )

,



 

i

p(x_i)

q_i

i1

n

Vì

q  1

,

p(x ) 1 , nên

q  p(x )  0 . Suy ra:



j



 

i

j1

i1

n

1

H(X ) 

p(x )log



p(x )log

i

. □



i

p(x_i)

q_i

i1

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

. Ta có:

P  (p(x ), p(x₂), ..., p(x_n))

X

1

0  H(X)  logn

1

log

 0

1 i  n

Chứng minh: Vì

, ta có

với mọi

. Suy ra

. Dấu

H( X ) 0

0  p(x ) 1

i

p(x_i)

“=” xảy ra khi và chỉ n 1

.

n

1

q  1

Đặt

,

i 1,2, ... ,n . Thế thì 0  q_j1 với mọi 0  j  n và

. Sử dụng Bổ đề

q_i



j

n

j1

2.1. ta có:

n

1





H(X ) 

p(x )log



p(x )log  log n

p(x )  log n



__

i



p(x_i)

q_i

i1



1

Đẳng thức xảy ra khi p(x_i) 

,

i 1,2, ... ,n . □

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à

và

. Entropy có điều kiện của Y khi X đã

P  (p(x ), p(x₂), ..., p(x_n)) P  (p(y₁), p(y₂), ..., p(y_m))

X

1

Y

biết, ký hiệu là H Y X , được định nghĩa như sau:





n

m

1

H Y X 

p(x_i)

p y / x log







_i

j

2

 

p(y_j/ x_i)

i1

j1

Entropy có điều kiện H Y X 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

P  (p(y₁), p(y₂), ..., p(y_m))

P  (p(x ), p(x₂), ..., p(x_n))

X

1

Y

lượng:

n

m

1

H(X,Y) 

p x , y log



_j

i

2



p x , y



_j



i

i1 j1

Hiển nhiên :

H(X,Y)  H(Y, X)

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à

P  (p(x ), p(x₂), ..., p(x_n))

P  (p(y₁), p(y₂), ..., p(y_m))

X

1

Y

Khi đó :

max H(X), H(Y)  H(X,Y)  H(X)  H(Y)

.





Chứng minh :

a) Bất đẳng thức bên trái

m

p(x ) 

p(x , y )

q  max p(x , y ) |1 j  m

Ta có :

. Đặt

. Khi đó với mọi j:







i

j

i

j

j1

p(x_i, y_j)  q_i p(x_i)

1

log

 log  log

Suy ra :

p(x_i)

q_i

p(x_i, y_j)

Mà theo Bổ đề 2.1.:

n

m

1

=

q_i

1

H(X ) 

p(x )log



p(x )log

p(x , y )log

i j





i

p(x_i)

q_i

i1

i1 j1

n

m

1



p(x , y )log

 H(X ,Y)



i

j

p(x_i, y_j)

i1 j1

56

TRƯỜNG ĐẠI HỌC THỦ ĐÔ HÀ NỘI

Bằng cách tương tự, ta cũng có:

b) Bất đẳng thức bên phải

. Vậy: max H(X), H(Y)  H(X,Y)

H(Y)  H(X,Y)





n

m

1

H(X )  H(Y) 

p(x )log



p(y )log



i

j

p(x_i)

p(y_j)

i1

j1

n

m

n







1







p(x , y ) log



p(x , y ) log

i j



 

__

i

j



p(x_i)

p(y_j)

i1

j1

j1 i1







n

m





1





p(x , y ) log

 log









i

j



p(x_i)

p(y_j)

i1 j1



n

m

1

p(x , y )log



i

j

p(x_i) p(y_j)

i1 j1

n

m

1

p(x , y )log

 H(X ,Y) .



i

j

p(x_i, y_j)

i1 j1

Đẳng thức xảy ra khi X và Y độc lập, tức là khi p(x , y_j)  p(x_i)p(y_j) . □

i

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 {X₁, X₂,..., X_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

phép toán này là những tập hợp).



và  (kết quả của các

X  

 (r)  x ,..., x

Cho tập thuộc tính

. Giả sử

và

c(x_i)  _{X  x}(r)

với 1 i  n

c(x_i)

,



_n

X

1

i

p

1

trong đó chỉ lực lượng của một tập hợp. Hiển nhiên, ta có:

.

và

. Do

c(x_i) 1

_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

,

P  (p(x ), p(x₂), ..., p(x_n))

X

1

c(x_i)

p(x_i) 

trong đó

với i 1, ... ,n . Như vậy, ta có thể nói tới các đại lượng thông tin của

. Sử dụng kết quả của phép chọn trong r,ta có thể viết lại các

r

các tập thuộc tính trong

định nghĩa như sau:



1) Entropy của X trên r là đại lượng

xác định bởi:

H_X(r)

n

r

c(x_i)

H (r) 

log

.



X

r

c(x_i)

j1

c(x_i)  

(r)

Trong đó: n  _X(r)

X  x_i

H_Y(r)

2) Entropy có điều kiện của Y khi X đã cho là đại lượng

xác định bởi:

X

TẠP CHÍ KHOA HỌC  SỐ 2/2016

57

n

m

n

m

c(x_i, y_j)

c(x_i)

c(x_i, y_j)

c(x_i)

^{c(x )}



i

H_Y(r) 

log



log



X

r

c(x_i, y_j)

r

c(x_i, y_j)

i1

j1

i1 j1

Trong đó: m  _Y(r)

c(x_i, y_j)  _{X x , Y y}(r)

i

j

3) Entropy đồng thời của X và Y là đại lượng H_XY(r) xác định bởi:

n

m

c(x_i, y_j)

r

H (r) 

log



XY

r

c(x_i, y_j)

i1 j1

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

định nghĩa bởi:

H_YY(r)

n

m

n

m

c(x_i, y_j)

c(x_i)

c(x_i, y_j)

c(x_i)

^{c(x )}



i

H_{Y Y}(r)  H (r)

log



log



Y

X

r

c(x_i, y_j)

r

c(x_i, y_j)

i1

j1

i1 j1

Độ phụ thuộc thông tin có các tính chất đáng chú ý sau đây:

Mệnh đề 2.3. H_{X Y}(r)  H_XY(r) H_X(r)

.

Chứng minh:

Ta có:

n

m

c(x_i, y_j)

c(x_i)

H_{X Y}(r) 

log



r

c(x_i, y_j)

i1 j1

n

m

c(x_i, y_j)



logc(x ) logc(x , y )







i

j

r

i1 j1

n

m





c(x_i, y_j)

1

log

 log











r

c(x_i, y_j)

c(x_i)

i1 j1

n

m





c(x_i, y_j)

1

 log r  log r  log











r

c(x_i, y_j)

c(x_i)

i1 j1

n

m





c(x_i, y_j)

r

 log











r

c(x_i, y_j)

c(x_i)

i1 j1

n

m

n

m

c(x_i, y_j)



c(x_i, y_j) 

r

log



log







_



r

c(x_i, y_j)

r

c(x_i)

i1 j1

i1

j1





58

TRƯỜNG ĐẠI HỌC THỦ ĐÔ HÀ NỘI

n

m

n

c(x_i, y_j)

r

c(x_i)



log



log





r

c(x_i, y_j)

r

c(x_i)

i1 j1

i1

.□

 H_XY(r) H_X(r)

Mệnh đề 2.4. Luật phản xạ

Nếu Y  X   thì H_{X Y} 0

.

Chứng minh:

Vì Y  X , nên X  YZ, Z   . Ứng dụng Mệnh đề 2.3. ta có:

H_{X Y}(r)  H_XY(r) H_X(r)  H_X(r) H_X(r)  0

□

Mệnh đề 2.5.

Chứng minh:

.

H_XZYZ(r)  H_XZY(r)

Ứng dụng Mệnh đề 3.3. ta có:

□

H_XZYZ(r)  H_XYZ(r)H_XZ(r)  H_XZY(r) H_XZ(r)H_XZ(r)  H_XZY(r)

Bổ đề 2.6. Luật hợp phải

H_{X Y} H_{X Z} H_{X YZ}. Đẳng thức xảy ra nếu các biến cố Y  y_jvà

là độc lập

Y  y_k

nhau khi đã biết

.

X  x

i

Chứng minh:

Ta có:

n

m

n

m

c(x_i, y_j)

c(x_i)

c(x_i, z_k)

c(x_i)

H_{X Y}(r)  H_{X Z}(r) 

log



log



r

c(x_i, y_j)

r

c(x_i, z_k)

i1 j1

q

n

m







c(x_i, y_j, z_k)

c(x_i)



log

 log





r

c(x_i, y_j)

c(x ,z )

i1 j1 k1









i

k

q

n

m









c(x_i, y_j, z_k)

c(x_i)



r

c(x_i, y_j)

c(x ,z )

i1 j1 k1









i

k

q

n

m







1



p(x , y , z ) log

 log





i

j

k

p(y_jx_i)

p(z_kx )

i

i1 j1 k1









q

n

m

1

p(x )

p(y , z x_i)log

j k





i

p(y_jx_i)p(z_kx_i)

i1

j1 k1

m

q

q_{j k} p(y_jx_i)p(z_kx )

q_{j k} 0

,

Đặt

, ta có

. Áp dụng Bổ đề 2.1 thu được:

q_jk1

i

_j1_k1

TẠP CHÍ KHOA HỌC  SỐ 2/2016

59

q

m

n

m

1

p(y , z x_i)log



p(x )

p(y , z x_i)log

.







j

k

i

j

k

p(y_j, z_kx_i)

p(y_jx_i)p(z_kx_i)

j1 k1

i1

j1 k1

Vậy:

q

n

m

1

.

 H_{X YZ}(r)

H_{X Y}(r)  H_{X Z}(r)  p(x )

p(y , z x )log





i

j

k

i

p(y_j, z_kx_i)

i1

j1 k1

Trường hợp Y  y_jvà

là độc lập nhau khi đã biết

thì:

X  x

Y  y_k

i

q

n

m



p

p_{j k | i}log1 p_{j | i}p_{k | i}

H_{X Y}(r) H_{X Z}(r)

 

i

i1

j1 k 1

q

n

m

p

p_{j k |i}log1 p_{j k | i}

=

 

i

i1

j1 k 1

 H_{X YZ}(r) . □

Mệnh đề 2.7. Quy tắc xích

H_{X YZ}(r)  H_{X Y}(r) H_{XY Z}(r)  max(H_{X Y}(r),H_{XY Z}(r)

Chứng minh:

Sử dụng Mệnh đề 2.3. ta có:

H_{X YZ}(r)  H_XYZ(r)  H_X(r)  H_{XY Z}r  H r  H

  _XY 

r

=

H_{XY Z}r  H

 

r

. □

_X 

_{X Y} 

Mệnh đề 2.8. H_XYZ H_{X Z}

Chứng minh:

Sử dụng Mệnh đề 2.7. ta có:

H_XYZ(r)  H_{X YZ}(r) H_{X Y}(r)

 H_{X Y}(r) H_{X Z}(r) H_{X Y}(r) (Mệnh đề 2.6.)

. □

 H_{X Z}(r)

Mệnh đề 2.9. Luật hợp trái

min H_{X Z}(r), H_{Y  Z}(r)  H_{XY  Z}(r)





Chứng minh:

Theo Mệnh đề 2.8. ta có: H_{X Z}(r)  H_XYZ(r)

H_YZ(r)  H_XYZ(r)

min H_{X Z}(r), H_{Y  Z}(r)  H

,

.

(r)

Vậy:

. □





XY  Z

60

TRƯỜNG ĐẠI HỌC THỦ ĐÔ HÀ NỘI

Mệnh đề 2.10. Luật tăng trưởng

H_XZYZ(r)  H_{X Y}(r)

Chứng minh:

Theo Bổ đề 2.5. và 2.8. ta có:

H_XZYZ(r)  H_XZY(r)  H_{X Y}(r) . □

Mệnh đề 2.11. Luật bắc cầu

H_{X Y}(r) H_YZ(r)  H_{X Z}(r)

Chứng minh:

H_{X Y}(r) H_YZ(r)  H_{X ZY}(r) H_XYXZ(r) (Mệnh đề 2.10.)

(Mệnh đề 2.3.)

 H_XY(r)H_X(r) H_XYZ(r)H_XY(r)

 H_XYZ(r)H_X(r)

(Mệnh đề 2.2.)

 H_XZ(r) H_X(r)

 H_X(r) H_Z(r)

(Mệnh đề 2.3.) □

Mệnh đề 2.12. Luật hợp toàn phần

H_{X Y}(r) H_WZ(r)  H_XWYZ(r)

Chứng minh:

H_XY(r) H_WZ(r)

(Mệnh đề 2.10.)

 H_XWYW(r) H_WYZY(r)

(Mệnh đề 2.11.)

 H_XWYZ(r)

Mệnh đề 2.13. Luật phân rã

Nếu Z  Y thì H_{X Y}(r)  H_{X Z}(r)

Chứng minh:

(Mệnh đề 2.4.)

H_YZ(r)  0

H_{X Y}(r) H_YZ(r)  H_{X Z}(r) (Mệnh đề 2.11.)

H_{X Y}(r)  H_{X Z}(r). □

Mệnh đề 2.14. Luật giả bắc cầu

H_{X Y}(r) H_WYZ(r)  H_XWZ(r)

Chứng minh:

TẠP CHÍ KHOA HỌC  SỐ 2/2016

61

H_{X Y}(r) H_WYZ(r)

 H_XWYW(r) H_WYZ(r) (Mệnh đề 2.10.)

 H_{X W Z}(r) (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 IA_{X Y}(r) định

nghĩa bởi:

H_{X Y}(r) H_{X Y}(r)  H_X(r)

IA_{X  Y}(r) 



log₂

r

log₂r





 

Từ các Mệnh đề 2.1. và 2.3. suy ra: 0  IA_{X Y}(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

X,Y   , ta nói Y phụ thuộc hàm vào X, viết X  Y , 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.

X,Y   X  Y

thỏa mãn khi và chỉ khi

Mệnh đề 3.1. Cho hai tập thuộc tính

.

H_{X Y}(r)  0

.

Chứng minh:



: Nếu X  Y thì với mỗi giá trị

chỉ có tương ứng một giá trị duy nhất

x dom(X)

i

y_jdom(Y) sao cho p(x_i, y_j)  0 . Suy ra, c(x_i, y_j)  c(x_i). Do đó,

n

m

n

m

c(x_i, y_j)

c(x_i)

H_Y(r) 

log



log1 0.



X

r

c(x_i, y_j)

r

i1 j1



: Nếu H_{X Y}(r)  0 thì H_{X Y}(r)  H_X(r) . Suy ra: H_Y(r)  0 với mọi . Hơn nữa

x_i

với mọi i. Vậy chỉ có duy nhất một giá trị y_jdom(Y) ứng với , tức là X  Y . □

p(x )  0

x_i

i

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:

Y  X

1. Luật phản xạ: Nếu

thì

X  Y

2. Luật tăng trưởng: Nếu X  Y thì XZ  YZ

62

TRƯỜNG ĐẠI HỌC THỦ ĐÔ HÀ NỘI

3. Luật bắc cầu: Nếu X  Y và Y  Z thì X  Z .

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 X  Y thì theo Mệnh đề 3.1. phải có

. Theo mệnh đề

H_{X Y}(r)  0

2.10. H_XZYZ(r)  H_{X Y}(r)

Suy ra: H_XZYZ(r)  0 (vì H_XZYZ(r)  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 X  Y 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 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ừ đâ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.