Biểu diễn phụ thuộc hàm xấp xỉ theo phân hoạch, ma trận phân biệt được và luật kết hợp

BIỂU DIỄN PHỤ THUỘC HÀM XAP XỈ THEO PHÂN HOẠCH, MA TRẬN
PHÂN BIỆT DƯỢC VÀ LUẬT KET HỢP
TRẦN DUY ANH
Trường Cao Dẳng Sư Phạm Thừa Thiên Huế; duyanh208@gmail.com
Tóm tắt. Các phụ thuộc hàm xấp xỉ và luật kết hợp là những tri thức thực sự có ý nghĩa trong khai phá dữ liệu. Trong bài báo này, đầu tiên, chúng tôi nhắc lại một số khái niệm cơ bản của lý thuyết tập thô, các độ đo lỗi gi, g2, g3 của phụ thuộc hàm. Sau đó, chúng tôi đề xuất độ đo lỗi g4 dựa trên phân hoạch và kỳ vọng trong lý thuyết xác suất. Phần tiếp theo chúng tôi xây dựng ma trận phân biệt theo một cách khác và biểu diễn các độ đo lỗi gi, g2, độ phụ thuộc 7 và ý nghĩa thuộc tính ơ theo ma trận phân biệt được. Cuối cùng, chúng tôi đưa ra mối liên hệ giữa phụ thuộc hàm xấp xỉ và luật kết hợp thông qua độ đo lỗi g4 và độ tin cậy Confidence.
Từ khóa. Phụ thuộc hàm xấp xỉ, luật kết hợp
Abstract. Approximate Functional Dependencies (AFD) and Association Rules are really meaningful knowledge in data mining. In this article, we first recall some basic concepts of rough set theory, error measures gi, g2 and g3 for functional dependencies. Then, based on the method of partitions and expectation in probability theory, we propose an error measure g4 to construct the discernibility matrix in a different way, defined error measures gi, g2, dependency degree 7 and significance of Attributes ơ from the discernibility matrix. Finally, a relationship between AFD and Association Rules via error measure g4 and confidence is presented.
Key words. Approximate Functional Dependencies, association rules.
MỞ ĐẦU
Phụ thuộc hàm xấp xỉ (Approximate Functional Dependencies) là tri thức biểu diễn sự phụ thuộc một phần giữa các thuộc tính. Nó là một mở rộng của phụ thuộc hàm, phụ thuộc hàm xấp xỉ cho phép có một số lượng lỗi nhất định của các bộ dữ liệu đối vói phụ thuộc hàm. Để nghiên cứu về loại phụ thuộc này Kivinen, Mannila [5] đã đưa ra các độ đo lỗi gi, g2, g3 đối vói phụ thuộc hàm. Sau đó đã có nhiều tác giả nghiên cứu các thuật toán để phát hiện các phụ thuộc hàm xấp xỉ như Huhtala, Karkkainen, Porkka, Toivonnen [4], Stéphane Lopes, Jean-Marc Petit, Lotfi Lakhal [6], Daniel Sánchez, José María Serano, Ignacio Blanco, Maria José Martin-Bautista, María Amparo Vila [7], ... Phụ thuộc hàm xấp xỉ đã có nhiều ứng dụng trong phân tích dữ liệu và đánh giá thông tin như rút gọn các thuộc tính dư thừa[11], tìm kiếm xấp xỉ [3],... Ngoài ra, những tri thức tiềm ẩn trong cơ sở dữ liệu chẳng hạn như: “Khách hàng khi mua sữa và bánh mì thường mua thêm bơ”, “Những du khách đến du lịch ở Huế khi mua tôm chua và kẹo mè xững thường mua thêm bánh lọc”... Những tri thức này chính là luật kết hợp (Association Rules). Luật kết hợp được đưa ra bởi nhà nghiên cứu Agrawal và SriKant vào năm 1994 [1] và đã có nhiều thuật toán để phát hiện luật kết hợp như thuật toán Apriori [1], Eclat [8], FP-Growth [12].
Trong bài báo này, đầu tiên, chúng tôi tìm hiểu các độ đo lỗi gi, g2, g3 của Kivinen, Mannila [5]. Sau đó, chúng tôi đề xuất một độ đo lỗi g4 đối vói phụ thuộc hàm và tìm mối liên hệ giữa phụ thuộc hàm xấp xỉ và luật kết hợp thông qua g4. Tiếp theo, chúng tôi xây dựng ma trận phân biệt được theo một cách khác, từ đó biểu diễn các độ đo lỗi gi, g2, độ phụ thuộc 7 và ý nghĩa thuộc tính ơ thông qua ma trận phân biệt này.
MỘT SỐ KHÁI NIÊM Cơ BẢN CỦA LÝ THUYET tập thô
Định nghĩa 2.1. [1, 9] (Quan hệ không phân biệt được) Cho r(R). Khi đó, vói bất kỳ X c R, tồn tại một quan hệ không phân biệt được Ộ(X) trên r được định nghĩa như sau:
8t, u 2 r, (t, u) 2 Ộ(X) , t[X] = u[X].
Định nghĩa 2.2. [1, 9] (Lớp tương đương và phân hoạch) Quan hệ Ộ(X) sẽ phân hoạch r thành các lóp tương đương. Lóp tương đương của bộ t 2 r ứng vói tập X c R, ký hiệu [t]x, được định nghĩa như sau:
[t]x = {u 2 r|t[A] = u[A] 8 A 2 X}, [t]x = ;.
Khi đó, ưx = f[t]x|t 2 r} là một phân hoạch của r ứng vói X. Lực lượng của K, ký hiệu |%|, là số lóp tương đương của K.
Cho U 2 Kx. Khi đó, ta quan niệm rằng, U thỏa phụ thuộc hàm X ! Y, ký hiệu là U| = X ! Y nếu vói mọi t, u 2 U sao cho t[X] = u[X], thì t[Y] = u[Y].
Bổ đề 2.1. [4] X ! Y đúng khi và chỉ khi |%x| = \ưXY| •
Định nghĩa 2.3. [4] (Phân hoạch thu gọn) Phân hoạch thu gọn của K, ký hiệu là 7T nếu 7T = {U 2 k||U| > 1}. Để giảm độ phức tạp tính toán khi làm việc vói các phân hoạch, ta dùng các phân hoạch thu gọn thay cho các phân hoạch.
Định nghĩa 2.4. [1] (Không gian dương) Không gian dương của tập thuộc tính X ứng vói tập thuộc tính Y được định nghĩa như sau:
POS(X, Y) = U{U 2 Kx| 9V 2 Ky : U c V}
Định nghĩa 2.5. [1] (Độ phụ thuộc) Tập thuộc tính Y phụ thuộc vào tập thuộc tính X vói mức độ 7(X, Y) 2 [0,1], ký hiệu là X —>7(x>y) Y, trong đó 7(X, Y) được xác định như sau:
7(X,Y)= PO7(?-’ )
r
Định nghĩa 2.6. [9](Bảng quyết định) Bảng quyết định S = (r, R) là bảng dữ liệu vói các cột tương ứng vói tập các thuộc tính R và các hàng là tập các đối tượng (bộ) r. Tập thuộc tính R được phân thành tập thuộc tính điều kiện C và tập thuộc tính quyết định D, R = C U D, C \ D = ;.
Định nghĩa 2.7. [9] (Ý nghĩa của thuộc tính) Ý nghĩa của các thuộc tính đo độ quan trọng của các thuộc tính trong bảng dữ liệu, nghĩa là ta xem xét độ phụ thuộc 7(C, D) thay đổinhư thế nào khi ta loại bỏ một thuộc tính Ai khỏi tập thuộc tính điều kiện C .Từ đó, ý nghĩa của thuộc tính Ai được định nghĩa như sau:
	„M.)- 1 (C;D) - 7(C -{Ai) ,D)	7(C -{Ai) ,D)
' (A) =	D :	= 1	1(aD) 
Định nghĩa 2.8. [9] (Ma trận phân biệt được) Cho r = {t1,t2,...; tng. Ma trận phân biệt được của S = (r, R), ký hiệu M(S) = (mij)|r|x|r| là ma trận đối xứng mà mỗi phần tử của nó là một tập hợp các thuộc tính, được xác định như sau:
m.. = / {Ai 2 c\ti(Ai') = tj(Ai)g ti(D) = tj(D)	. j =Y~
m = t	;	ti(D) = tj(D) vói ~1’n'
CÁC ĐỘ ĐO LỖI CỦA PHỤ THUỘC HÀM
Để xác định một phụ thuộc hàm xấp xỉ, Kivinen và Mannila [5] đã đưa ra một số độ đo để tính toán lỗi của một phụ thuộc hàm như sau:
Định nghĩa 3.1. [5] (Độ đo lỗi gì) Cho quan hệ r(R). Khi đó, độ đo lỗi g1 của một phụ thuộc hàm X ! Y trẽn r được xác định như sau:
\r\2
gỵ_(X ! Yr)= \{(ti;tj)\ti’tj 2 r; ti[X] = tjÍX]’ ti[Y] = tjÍY]g\
Định nghĩa 3.2. [5] (Độ đo lỗi g2) Cho quan hệ r(R). Khi đó, độ đo lỗi g2 của một phụ thuộc hàm X ! Y trẽn r được xác định như sau:
\r\
g2 (X ! Yr)= \{ ti	\ ti	2	r’	9tj	2 r :	ti	[X ] = t [X ]	’ ti	[Y ]	= t	[Y ]	' \
Định nghĩa 3.3. [5](Độ đo lỗi g3) Cho quan hệ r(R). Khi đó, độ đo lỗi g3 của một phụ thuộc hàm X ! Y trẽn r được xác định như sau:
\r\
x _ max {\s\|s c r, s| = X ! Y} g3(X ! Y; r) = 1	v 11 c,ị	
BIỂU DIỄN PHỤ THUỘC HÀM XAP XỈ THEO PHÂN HOẠCH
Độ phụ thuộc 1 rất thuận tiện trong việc xem xét hệ tiẽn đề Armstrong và một số phép toán đại số quan hệ đối vói phụ thuộc hàm xấp xỉ trong [1]. Tuy nhiẽn các thuật toán [4, 10] dùng độ đo lỗi g3 để phát hiện phụ thuộc hàm xấp xỉ. Trong các thuật toán này độ đo lỗi g3 được tính theo các phân hoạch dựa vào Bổ đề 2.1 như sau:
Định nghĩa 4.1. [4] (Độ đo lỗi g3 theo phân hoạch) Cho quan hệ r(R). Khi đó, độ đo lỗi của một phụ thuộc hàm X ! Y được xác định như sau:
\r\ — P max{ \V\\ V 2 ưxY ;V c Ug
jrj
Sa(X ! Y,r) =	U&X
Tính chất 4.1. [10](Mối liên hệ giữa g3 và 7) Cho độ phụ thuộc
7(X;y) = |POS 1.
|r|
và độ đo lỗi g3(X ! Y, r> của phụ thuộc hàm X ! Y. Khi đó, ta có:
P max { | V | | V 2 ~\Y ; V c U }
g3(X ! Y; r> = 1 - 7(X; Y> -	—	
jrj
Định nghĩa 4.2. [10](Độ đo lỗi g3 theo phân hoạch thu gọn) Độ đo lỗi g3(X ! Y; r> từ các phân hoạch thu gọn được xác định như sau:
P (|U|- max {|V||V 2 XXY;V c U}> + P {(|U| L3V 2 ttxy;V c U> - 1} g3(X ! Y;r> =	|r	
Bây giờ chúng tôi đưa ra một số tính chất và nhận xét để xây dựng độ đo lỗi g4 của phụ thuộc hàm X —> Y.
Tính chất 4.2. Cho một quan hệ r(R> và X; Y c R. Khi đó, X ! Y là một phụ thuộc hàm khi và chỉ khi P |U|2 = P |V|2
U2~x	V2~xY
Chùng minh. Giả sử phân hoạch YX gồm các lóp tương đương Ui;i = 1;...; |%X| và phân hoạch "XY gồm các lóp tương đương Vj; j = 1;...; | TXU|. Gọi E(%X> là kỳ vọng của tổng số bộ ứng vói các lóp tương đương Ui; i = 1;...; |%X|. Gọi E(^XY> là kỳ vọng của tổng số bộ ứng vói các lóp tương đương Vj; j = 1;...; | TXU|.
Khi đó
l^x I
E(%X> ^2 | Ui |.P (Ui>; vói P(Ui>: khả năng phân bố các bộ của r vào Ui
i=1
= Pl Ui | .Ẹ| = Ẳ X I U 12;
y | | rl	| r |„irv||;
l“xr 1
E('KXY>	^2 | Vj| .P (Vj>; vói P(Vj>: khả năng phân bố các bộ của r vào Vj
j=1
V 2.
V 2^XY
= X11 V. | .Ịj = -1 j= ' |. | r |	| r |
Ta có E(^X > = E(^xy > khi và phân bố các bộ vào các V 2 'KXY.
P | U | 2 = P | V |2 ■
U 2^x	V 2^XY
chỉ khi có sự phân bố các bộ vào các U 2 ^X giống sự Do vậy X ! Y là một phụ thuộc hàm khi và chỉ khi
P IVI2
Nhận xét 4.1. Ta có thể đặt Ổ(X; Y> = ' pVY|U|2 . Khi đó, 0 tăng
U E^x
thì khả năng xảy ra lỗi của phụ thuộc hàm càng ít.
Ví dụ 4.1. Cho quan hệ r(R) sau:
Bảng 1. Một quan hệ trẽn tập thuộc tính R = {A1,..., A4}
A1
A2
A3
A4
0
1
0
0
1
0
1
1
0
1
1
2
2
1
0
0
0
1
0
1
1
0
2
2
Khi đó, ta có: Ổ(A1, A2) = 1, Ổ(A1, A3) = 4/7, Ổ(A1, A4) = 3/7.
Từ Tính chất 4.2 và Nhận xét 4.1, ta có Định nghĩa 4.3 như sau:
Định nghĩa 4.3. (Độ đo lỗi g4 theo phân hoạch) Cho quan hệ r(R). Khi đó, độ đo lỗi g4(X ! Y, r) từ các phân hoạch được tính như sau:
P |VI2
g4(X ! Y,r) = 1 - Ỗ(X,Y) = 1 - V P |U |2 ■
U 2~X
Với Bảng 1, ta có g4(A1 ! A2, r) = 0, g4(A1 ! A3, r) = 3/7, g4(A1 ! A4, r) = 4/7.
Nhận xét 4.2. Từ Tính chất 4.2, Nhận xét 4.1 và Định nghĩa 4.3, ta thấy rằng g4(X ! Y, r) có quan hệ mật thiết với sự phân bố của các bộ dữ liệu vào các V 2 "XY ùng với các U 2 TĨX . Tuy nhiẽn g2 (X ! Y, r) và g3 (X ! Y, r) không biểu diễn được cho sự phân bố này.
Ví dụ 4.2. Cho quan hệ r(R) sau:
Bảng 2. Một quan hệ trẽn tập thuộc tính {Hoten, Trieuchung, Benh}
Hoten
Trieuchung
Benh
P1
2
4
P2
1
1
P3
1
2
P4
2
2
P5
1
4
P6
2
3
P7
1
1
P8
2
2
P9
2
2
P10
1
3
P11
2
1
Vói quan hệ ở Bảng 2, ta có g2(Trieuchung ! Benh, r) = 0, g3(Trieuchung ! Benh, r) = i6i. Nếu chúng ta thay đổi sự phân bố của các bộ dữ liệu, chẳng hạn ở người có Hoten là Pq, ta thay thế giá trị 3 thành giá trị 1 ứng vói thuộc tính Benh thì g2(Trieuchung ! Benh,r) và g3(Trieuchung ! Benh, r) vẫn không thay đổi.
Nhận xét 4.3. Bây giờ, ta thu hẹp tập dữ liệu của quan hệ r ứng vói phép chọn, khi đó g4(X ! Y, ơX=Xi (r)) vói Xi 2 dom(X) đo được mức độ tập trung của các bộ dữ liệu trong ơX=Xi (r) vào các lóp tương đương V 2 ^XY.
VP |V|2
Thật vậy, ta có g4(X ! Y,ƠX=XÌ(r)) = 1 - .	—T2. Do đó g4(X ! Y,ơX=Xi(r)) càng
Iơv = xi(r)|
v P |V|2
nhỏ khi chỉ khi 	XY 2 càng lón. Hay g4(X ! Y, ƠX =Xi(r)) càng nhỏ khi chỉ khi mức độ tập
jơX=Xi (r)|
trung các bộ ơX=Xi (r) vào một hay một số lóp tương đương V 2 'KXY là càng lón.
Vói quan hệ ở Bảng 2, ta có: g4(Trieuchung ! Benh,ơTrieuchung=i(r)) = 25, g4(Trieuchung ! Benh, ơTrieuchung=2(r)) = 2. Nếu ở người có Hoten là Pq, ta thay đổi giá trị 3 thành giá trị 1 ứng vói thuộc tính Benh thì g4(Trieuchung ! Benh, ơTrieuchung=2(r)) = .
Như vậy nếu g4(Trieuchung ! Benh, ơTrieuchung=Xi (r)) càng nhỏ ứng vói triệu chứng Xi thì mức độ phân bố tập trung bệnh nhân trong ơTrieuchung=Xi (r) vào một hoặc một số bệnh nào đó càng lón và ngược lại. Điều này góp một phần trong việc dự đoán được bệnh của bệnh nhân thông qua các triệu chứng.
Nhận xét 4.4. Ta thấy rằng g4(X ! Y,r) > gi(X ! Y, r), nghĩa là g4(X ! Y, r) nghiêm ngặt hơn gi(X ! Y,r). Tuy nhiên gi(X ! Y, r) là không tốt cho việc đo lỗi của X ! Y và mức độ tập trung của các bộ dữ liệu trong r vào các lóp tương đương V 2 'KXY. Thật vậy, ta có
E V2
g4(X ! Y,r) = - VPjư|2
U 2~x
E j|2 - E |VỊ2)
U 2~\-
|r|2
E |U|2
U
■ gi(X ! Y,r)
Suy ra g4(X ! Y,r) > gi(X ! Y,r).
Bây giờ ta xét một quan hệ ở Ví dụ 4.3 dưói đây.
Ví dụ 4.3. Cho quan hệ r(R) sau:
Bảng 3. Một quan hệ trên tập thuộc tính {A, B, Cg
A
0
2
1
1
0
1
3
3
2
3
0
2
2
3
2
B
1
5
1
2
3
4
3
4
3
2
2
2
1
1
4
C
1
3
2
2
2
1
2
1
2
1
1
3
1
1
3
n.( A B r A — 44 ~ 0 756 A \ B r 1— 11 ~ 0 733 n, (A \ B r) — 44 ~ 0 196 g4(A ! I ) — 59 —	<00, g3(A ! B; ' ) — 15 — 0 •7 33, g1(A !	' ) — 225 — °-196-
Ta thấy rằng độ đo lỗi g1(A ! B,r) là quá nhỏ so với g4(A ! B;r), trong khi đó lỗi của phụ thuộc hàm A ! B là tương đối lớn và mức độ phân bố tập trung các bộ dữ liệu vào các lớp tương đương V 2 kab ứng với U 2 KA là nhỏ.
Tính chất 4.3. (Độ đo g4 trên phân hoạch thu gọn) Cho quan hệ r(R). Khi đó, độ đo lỗi g4(X ! Y) từ các phân hoạch thu gọn được xác định như sau:
P |UI2 - P |VI2 - P |UI + E |VI
(X —ỳ. Yr) — U2^X	VXy	U	U&CXY
g	rp IU I2 + |r| - P |U I	'
U C-ÍTX	U &~.v
Chùng minh. Ta có |r| — ^2 |U|: là số lớp tương đương một phần tử bị loại khỏi '~x để có U 2ttx
Tĩ X. Suy ra
X IU I2 — X IU I2 + |r| - X IU I
U &TX	U 2ttx	U 2ttx
Tương tự ta có P |V|2 — P |V|2 + |r| — E |V|: Do đó:
V C^XY	V Cttxy	V Cttxy
E I V 12 + I r I - E I V I
/ -rr ÍT’ \	-1	V2^XY	V2^XY
g4(	! ,r)— -	£ I U I 2 + I r| - E |U I
U Cttx	U Cttx
E ' E |V|2- E |U|+ E |V|
ae#x	V e#XY	U X	U e#XY
E	|U |2+|r| — E |U |
Ue#x	Ue#x
Ví du 4.4. Với Bảng 1, ta có:
T^A-1 — {{t1; t2; t3g; {t4;t5}}; KA1A3 — {{t1,t2g}
3 Độ đo lỗi g4(A1 ! A3, r) được tính từ các phân hoạch thu gọn và g4(A1 ! A3, r) — 4ị•
BIỂU DIỄN PHỤ THUỘC HÀM XAP XỈ THEO MA TRẬN
PHÂN BIỆT ĐUỢC
Trong phần này chúng tôi xây dựng ma trận phân biệt được M(S) theo 1 cách khác và đề xuất cách biểu diễn độ đo lỗi g1, g2, độ phụ thuộc 7 và ý nghĩa thuộc tính ơ thông qua M(S).
Định nghĩa 5.1. (Ma trận phân biệt được) Cho r — t4,t2, • • •, tn. Ma trận phân biệt được của S — (r, R), ký hiệu M(S) — (mịj)|r|x|r| là ma trận đối xứng mà mỗi phần tử của nó là một tập hợp các thuộc tính, được xác định như sau:
<	fAk 2 c| ti(Ak1 — tj(Ak)g
mij — <	;
:	| 9Ak 2 c : ti(Ak1 — tj(Ak1}
ti(D)— tj (D)
ti(D) — tj(D)	với i,j — 1, I rI •
ti(D) — tj(D),^ 2C
Định nghĩa 5.2. Cho ma trận phân biệt được M(S) = (mij)|r|x|r|. Khi đó số lần X xuất hiện trong M(S) ký hiệu là SL(X) và được định nghĩa như sau:
SL (X) = I n mj |(X n mj) = 0, X c C; Vi; j = 1; |r| o I
Nếu X = 0 thì SL(0) = In mij Imij = 0 ;Vi; j = 1; |r| o I •
Tính chất 5.1. Cho ma trân phân biệt được M(S) = (mij)|r|x|r|. Khi đó, X ! D với X c C là một phụ thuộc hàm khi và chỉ khi SL(X) = |r|2 — SL(0).
Chùng minh. Ta có với mỗi mj = 0 thì ti[D] = tj[D]. Do đó SL(0) là số cặp bộ (ti;tj), i; j = 1, |r| không vi phạm phụ thuộc hàm X ! D.
Mặt khác, với mỗi mj sao cho (X n mj) = 0;X c C thì ti[X n mj] = tj [X n mj] và ti[D] = tj[D] suy ra ti[X] = tj[X] và ti[D] = tj[D]. Do đó SL(X) là số cặp bộ (ti;tj), i; j = 1, |r| không vi phạm phụ thuộc hàm X ! D.
Vậy Sl(X) + sL(0) = |r|2 với X c C ,9ti, tj 2 r : ti[D] = tj[D] và ti[X] = tj[X] , X ! D là một phụ thuộc hàm. ■
Tính chất 5.2. Độ đo lỗi gi của một phụ thuộc hàm X ! D, với X c C trẽn r được xác định như sau:
gi(X ! D;r) = 1 - SL(0>+ 2SL
|r|2
Chùng minh. Theo Tính chất 5.1, ta có SL(X) + SL(0) là số cặp bộ (ti;tj); i; j = 1; |r| không vi phạm phụ thuộc hàm X —> D Do đó: g (X —> D, r) = |r|2-SL(;)-SL(X) = 1 _ SL(0)+SL(X)
vi pnỉun pnn bnưuc HÍUH A 7 J-J. do tió: gi 7 J-J; r ) —	I |2	— T	i p
■
Hệ quả 5.1. Độ đo lỗi gi của một phụ thuộc hàm X ! D, với X c C trên r được xác định như sau:
In mij | ((X n mij ) = 0) A (mj = 0) ; i; j = 1; |r| OI
gi(X ! D	|	u
Chùng minh. - Ta có ((X n fflj-) = 0) A (m-ij = 0)	2 X : ti[A] = tj[A] và ti[D] =
tj[D] , ti[X] = tj[X] và ti[D] = tj[D] , cặp (ti;tj) vi phạm phụ thuộc X ! D.
- Trường hợp mij	= suy ra ((X n mij)	= 0)	A (m j	=	0)	(vì	2	X)	, cặp	(ti; tj) vi phạm
phụ thuộc X 7 D
Vậy I { m j | ((X n m j) = 0) A (mij = 0) ; i; j = 1; |r| n I = số cặp (ti; tj) vi phạm phụ thuộc X ! D. Do đó: gi(X ! D; r) = |f ' |((X'g|. ■
Tính chất 5.3. Độ đo lỗi g2 của một phụ thuộc hàm X ! D, với X c C trẽn r được xác định như sau:
H
y hangi(X) g2(X ! D;r) = 1 -	1	
Trong đó: hangi(X) = n 1 (X n mt Vmij=0;j =1; |r| ■
g hangi(X) ị 0	9j : (m= 0) A ((X n mij) = 0)
Chùng minh. Ta có:
g2(X ! D r)= \{ ti\ti 2 r’ 9tj 2 r : ti[X] = tj [X] ; ti[D] = tj [D] } \.
Gọi q là số bộ vi phạm phụ thuộc hàm X ! D trên r. Khi đó:
q = |{ ti \tị 2 r, 9tj 2 r : ti [X] = tj [X] ; ti [D] = tj [D] } I
Ta có vói mỗi bộ ti 2 r:
Xét trường hợp, nếu (X \ mj) = 0 Vmij = 0; j = 1; |rI
Ta có (X \ mj) = 0 Vmij = 0; j = 1; |rI ,/9tj 2 r : ti[X] = tj[X] và ti[D] = tj[D] (vì nếu 9tj : ti[X] = tj[X] và ti[D] = tj[D] thì (X \ mij) = 0. Điều này mâu thuẫn vói giả thiết) , ti là bộ thỏa phụ thuộc X ! D , hangi(X) = 1.
Xét trường hợp, nếu : (mij = 0) A ((X \ mij) = 0):
Ta có : (mij = 0) A ((X \ mij) = 0) , ti[X] = tj[X] và ti[D] = tj[D] , ti là bộ vi phạm phụ thuộc X ! D , hangi(X) = 0.
Xét trường hợp mịj =
Ta có mij = suy ra (mij = 0) A ((X \ mij) = 0) , ti là bộ vi phạm phụ thuộc X ! D , hangi(X) = 0. Do đó ]C hangi(X) = số bộ thỏa phụ thuộc hàm X ! D nên q = \r\ — i=1
|r|
|r|	P hangi(X)
hangi(X). Suy ra g2(X ! D; r) = 1 - i=1 |r|	. ■
i=1
Nhận xét 5.1.
Độ phụ thuộc 7(X; D) được tính thông qua công thức 7(X; D) = 1 — g2(X ! D; r) [7], vói
M	W
hangi(X)	Ỵ, hangi(X)
X c C và g2(X ! D; r) = 1 — ——Pĩ	 (Tính chất 5.3) như sau: 7(X; D) = i=1—Pĩ	
Y nghĩa thuộc tính được tính dựa trên ma trận phân biệt được thông qua công thức:
lrl
Y hangi(X)
■ ■(Ai) = 1 - 7(ơf Ĩ’D) [9], vói 7(X; D) =	 và X c C.
LUẬT KẾT HỢP
Định nghĩa 6.1. [2] (CSDL giao dịch) Cho I (items) = {i1; i2;...; im} là tập mục, một CSDL giao dịch, được ký hiệu là TD gồm các giao dịch T 2 TD, vói mỗi giao dịch (Transaction) T được định nghĩa là tập con của tập mục I(T c I) và có một định danh duy nhất hTID;Ì1;Ì2; ...;ik }.
Định nghĩa 6.2. [2] (Luật kết hợp) Cho cơ sở dữ liệu TD gồm các giao dịch T ứng vói tập mục I = {i1;i2;...; im}. Khi đó, một luật kết hợp giữa IX và IY có dạng là IX ) IY, vói IX, IY c I và IX \ IY = 0.
Định nghĩa 6.3. [2] (Độ hỗ trợ của một tập mục) Cho tập mục IX c I, độ hỗ trợ của tập mục IX được ký hiệu là Support(IX; TD) và được định nghĩa như sau: Support(IX; TD) = fT2T\Td\~Tgl hay Support(IX; TD) là tỷ lệ phần trăm giữa các giao dịch chứa IX trên tổng các giao dịch có trong cơ sở dữ liệu TD.
Định nghĩa 6.4. [2] (Độ hỗ trợ của luật kết hợp) Độ hỗ trợ của luật kết hợp IX ) IY, (ký hiệu là Support(IX ) IY, TD)) bằng tỷ lệ phần trăm giữa các giao dịch chứa IX u IY trẽn tổng số các giao dịch trong cơ sở dữ liệu TD:
Support(IX ) IY, TD) = Support(IX u IY, TD) =	—.
Định nghĩa 6.5. [2] (Độ tin cậy của luật kết hợp) Độ tin cậy của luật kết hợp Ix ) IY, (ký hiệu là Confidence(IX ) IY, TD)) bằng tỷ lệ phần trăm giữa các giao dịch chứa Ix u IY trẽn số giao dịch có chứa IX:
r,,	- Support(IX u Iy, TD)
)IY,TD) =	sUppOrf(/X, TD)
MỐI QUAN HỆ GIỮA PHỤ THUỘC HÀM XAP XỈ
VÀ LUẬT KẾT HỢP
Một số ký hiệu [7]
r(R): một quan hệ trẽn lược đồ R, vói R = {A1, A2, ..., Am}
Miền trị của X c R, ký hiệu là dom(X) = {xi, X2, ...,Xk}
Miền trị của Y c R, ký hiệu là dom(Y) = {yi, y2, ...,yi}
n = \r\ và nXi = \{t 2 r\t [X] = Xi}\, nyj = \{ t 2 r\t [Y] = yj} I,
nxiVj = 1 { t 2 r\t [X] = Xi và t [Y] = y^Ị I
Cho R = {Ai, A2, ..., Am}. Khi đó, vói Ak 2 R thì ÌAk là một mục (item) trong luật kết hợp.
Cho X c R. Khi đó, tập mục của X ký hiệu là Ix = {ÌAk \Ak 2 X}
Định nghĩa mới của phụ thuộc hàm xấp xỉ
Định nghĩa 7.1. [7] Cho quan hệ r(R) vói R = {A1, A2, ..., Am} . Một cơ sở dữ liệu giao dịch TD được định nghĩa như sau: mỗi cặp (t, s) 2 r X r sao cho t, s 2 r là một giao dịch ts 2 TD và được xác định như sau: ÌAk 2 ts , t [Ak] = s [Ak]. Khi đó: ts.ÌAk =
1 nếu ÌAk 2 ts
0 nếu ÌAk 2 ts
Ví dụ 7.1. Cho quan hệ sau:
Bảng 4. Một quan hệ r
Masv
Quequan
Truong
Ketqua
1
Hue
QH
Dau
2
Hue
NH
Dau
3
Hue
QH
Rot
Ta có thể biểu diễn Bảng 4 thành cơ sở dữ liệu giao dịch TD như trong Bảng 5.
Bảng 5. Một cơ sở dữ liệu giao dịch TD của r
ts
^Masv
iQuequan
^Truong
iKetqua
(1,1)
1
1
1
1
(1,2)
0
1
0
1
(1,3)
0
1
1
0
(2,1)
0
1
0
1
(2,2)
1
1
1
1
(2,3)
0
1
0
0
(3,1)
0
1
1
0
(3,2)
0
1
0
0
(3,3)
1
1
1
1
Định nghĩa 7.2. [7] Cho X, Y c R sao cho X \ Y = 0. Khi đó một phụ thuộc hàm xấp xỉ X ! Y trẽn quan hệ r là một luật kết hợp Ix ) IY trẽn cơ sở giao dịch TD. Và ta có độ hỗ trợ và độ tin cậy như sau: Support (X ! Y, r) = Support(IX ) IY, TD)
Confidence (X ! Y,r) = Confidence(IX ) IY, TD)
Theo cách biểu diễn này thì độ hỗ trợ của tập thuộc tính X là Support(X, r) = Support(Ix, TD).
Tính chất 7.1. [7] X, Y c R, X ! Y là một phụ thuộc hàm khi và chỉ khi Confidence(Ix ) IY, TD) = 1.
Định nghĩa 7.3. [7] Cho R = {A1, A2, ...,Am}, X, Y c R. Khi đó, độ hỗ trợ của X và k	kỉ
X Y tương ưng là Support(X, ỉ) = n2 / z nXi và Suppo't(X ! Y,r ) = n- / 2_^ nXiyj. i=1	i=1 j=1
Ví dụ 7.2. Trong Bảng 4, ta có: Support (Truong, r) = 5/9; Support ({Truong, Ketqua} , r) = 3/9.
Khi đó, ta có một số luật kết hợp trong TD tương ùng với các phụ thuộc hàm xấp xỉ trong r như sau:
Bảng 6. Một số luật kết hợp tương ùng với phụ thuộc hàm xấp xỉ
Luật kết hợp
Độ hỗ trợ
Độ tin cậy
Phụ thuộc hàm xấp xỉ
{iQuequa,n,y	{iTruong }
5/9
5/9
{ Quequan } ! {Truong}
{tQuequanì iTruong } ) {iKetqua }
1/3
3/5
{Quequan, Truong} ! {Ketqua}
7.3. Độ hỗ trỢ, độ tin cậy của phụ thuộc hàm xấp xỉ
Gọi ARSịX!Y] = {ARij|9t 2 r : t [X] = xi và t [Y] = yj}	8i = 1, k;8j = 1, l, trong đó
ARij là một luật kết hợp có dạng (X = Xi) ) (Y = yj), với Sij, Cij tương ùng là độ hỗ trợ, độ tin cậy của ARij .
Tính chất 7.2. [7] Độ hỗ trợ của phụ thuộc hàm xấp xỉ X — Y được tính theo công thức như sau:
Support(X — Y;r) = n X	= X
ARij 2ARS[X!Y ]	ARij 2ARS[X!Y ]
Tính chất 7.3. [7] Độ tin cậy của một phụ thuộc hàm xấp xỉ được tính theo công thức
sau:
1
Confidence(X — Y; r)
S2
Ví dụ 7.3. Đối với Bảng 4, ta có:
ARij 2ARS
y,
[X!Y] ARpq2ARS[X!Y]
1
Cj
1
Confidence({Quequan, Truong} — {Ketqua} ,r)
)Confidence({Quequan, Truong} — {Ketqua} ,r)
5
3
3
5
7.4. Biểu diễn độ phụ thuộc, độ đo lỗi thông qua luật kết hợp
Tính chất
\POS(X,Y )\
\r\	.
7.4. [7] Cho phụ thuộc hàm xấp xỉ X ':' —; ) Y, trong đó độ phụ thuộc 7(X; Y) = Khi đó 7(X, Y) = PAR.2ARS[X!Y]\Cij = 1 Sij■
Tính chất diễn như sau:
7.5. [7] Độ đo lỗi g1 của phụ thuộc hàm X — Y ở Định nghĩa 3.1 được biểu
g1(X — Y,r) = Support (IX ;TD) — Support (IX ) IY;TD)
Tính chất 7.6.
diễn như sau:
[7] Độ đo lỗi g2 của phụ thuộc hàm X — Y ở Định nghĩa 3.2 được biểu
g2(X — y,t}	1	X ARij 2ARSlX!Y]\Cij = 1 Sij
Tính chất 7.7.
[7] Cho phụ thuộc hàm xấp xỉ X — Y với
g3(X — Y,r) =
|r| — 52 ma^ |Vl V 2 "\Y; V C U U 2p;	I
|r|
K
Khi đó g3(X — Y; r) = 1 — 52 max{Sij\ARij 2 ARS[X!Y]}:
i=1	j=Ỹ
Tính chất 7.8. Cho g4(X — Y; r) là độ đo lỗi của phụ thuộc hàm X — Y, Confidence(IX ) IY; TD) là độ tin cậy của luật kết hợp IX ) IY. Khi đó g4(X — Y; r) = 1 — Confidence(IX ) Iy ; TD).
Chùng minh. Ta có
P |VI2	P P l{t 2 r|(t|X] = Xi) A (t[Y] = yĩ)}|2
„ fv ,	_1	V2AXY	i=1 j=l
g4(X ! Y; r)=1	P |U|2 = 1	k
■ 1 1	P |{t 2 r|t[X]= Xi}|2
i=1
k I
P P n-ÌXiVi	„	,,r	_
i=i j=i	y	Support(Ix ) Iy, TD)
*	Support(IX ,TD)
E nẵi
i=i
=1 — Confidence(IX ) IY,TD).
Vậy g4(X ! Y, r) = 1 — Confidence(IX ) IY,TD) ■
Ví dụ 7.4. Đối với Bảng 1 ta có g4(A1 ! A3, r) = 3/7 và Confidence(IA1 ) Ia3;TD) = 4/7. Do đó, g4(A1 ! A3,r) = 1 — Confidence(IA1 ) Ia3,TD).
g4(X ! Y,r) = 1 -
Tính chất 7.9. Mối liên hệ giữa g4(X ! Y,r) và ARSịx!Y] Ear pq2 ARS X Y Spq
(Sij
XARij 2ARS[X!Y] I Cij I
Chùng minh. Ta có g4(X ! Y, r) = 1 —
! YY	ARjeA^[x
Confidence(IX ) IY,TD). Mà
Sỉ,	1
	S2 ■ (Tính chất 7.3)
2^ Spq Cij ^Y] ARpq2ARS[X-!Y]
/S2.\
/ S2j PARpq 2ARS[X!Y] --- 2ARS[X!yẠ Cj Do đó, g4(X ! Y,r) = 1 - PARpq2ARS[X!Yì	. ■
P _	_ _	I Vj I
^ARij 2ARS[X—Y] I Cij I
	1	n P . „ _ . „ „	Sij I _ 1 suy ra gAX ! Y) =	''A Ij
1
Ví dụ 7.5. Đối với Bảng 1 ta có g4(A1 ! A3, r) = 3/7 (theo Định nghĩa 4.3) và
1	pq	[X!Yl E = 1 - 8/14 = 3/7.
P _	 ( Sij I
XARij 2ARS[X!Y] I Cij I
KẾT LUẬN
Trong bài báo này chúng tôi đã nghiên cứu phụ thuộc hàm xấp xỉ dựa vào phân hoạch, ma trận phân biệt được và luật kết hợp và đã đạt được một số kết quả sau:
Đề xuất độ đo lỗi g4 đối vói phụ thuộc hàm và phân tích những thuận lợi của nó so vói các độ đo lỗi gi, g2, g3. Độ đo g4 không những đo được lỗi của phụ thuộc hàm mà còn đo được mức độ tập trung hay không tập trung của các bộ dữ liệu. Sau đó xây dựng g4 trên phân hoạch thu gọn và biểu diễn mối quan hệ giữa nó vói độ tin cậy của luật kết hợp. Từ đó chúng ta có thể sử dụng các thuật toán phát hiện luật kết hợp để phát hiện các phụ thuộc hàm xấp xỉ và ngược lại.
Đưa ra một định nghĩa mói về ma trận phân biệt được. Từ đó xem xét phụ thuộc hàm, biểu diễn độ đo lỗi gi, độ đo lỗi g2, độ phụ thuộc và ý nghĩa thuộc tính thông qua ma trận phân biệt được. Điều này làm cì sở để nghiên cứu tiếp tục thuật toán rút gọn các thuộc tính dư thừa thông qua các độ đo lỗi này.
TÀI LIÊU THAM KHẢO
L. B. Cristofor, A Rough Set Based Generalization of Functional Denpendencies, Department of Math and Computer Science, UMass/Boston, 2000.
Rakesh Agrawal and Ramakrishnan Srikant, Fast algorithms for mining association rules in large databases, In Jorge B. Bocca, Matthias Jarke, and Carlo Zaniolo, editors, Proceedings of the 20th International Conference on Very Large Data Bases, VLDB, Santiago, Chile (1994) 487-499.
Ullas Nambiar, Subbarao Kamhampati, Mining Approximate Functional Dependencies and Concept Similarities to Answer Imprecise Queries, Department of Computer Science, Arizona State University, USA, 2004.
Y. Huhtala, J Karkkainen, P. Porkka, H. Toivonnen, Tane: An Efficient Algorithm for Discovery Functional and Approxiamate Dependencies, The Computer Journal, 42 (3) (1999) 100-111.
J. Kivinen, H. Mannila, Approximate Inference of Functional Dependencies from Relations, Theoretical Computer Science, 149 (1) (1995) 129-149.
Stéphane Lopes, Jean-Marc Petit, Lotfi Lakhal, Functional and approximate dependency mining: database and FCA points of view, J. Exp. Theor. Artif Intell., 14(2-3) (2002) 93-114.
Daniel Sánchez, José María Serano, Ignacio Blanco, Maria José Martin-Bautista, María Am- paro Vila, Using association rules to mine for strong approximate dependencies, Data mining knowledge discovery, Springer Science (2008) 313-348.
Mohammed J. Zaki, Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3) (2000) 372-390.
Jan Komorowski, Lech Polkowski, Andrzej Skowron, Rough Set: A Tutorial, Institute of Mathematics, Warsaw University, 2000.
Trần Duy Anh, Phát hiện các phụ thuộc hàm xấp xỉ theo cách tiếp cận tập thô, Tạp chí tin học và điều khiển học, 23(3) (2007) 284-295
Keyun Hu, Yuchang Lu, Chunyi Shi, Feature ranking in rough set, Department of Computer science, Tsinghua University Beijing 100084, P.R.China, 2003.
Jiawei Han, Jian Pei, Yiwen Yin, and Runying Mao, Mining frequent patterns without candidate generation, Data Mining and Knowledge Discovery 8 (2004) 53-87.
Ngày nhận bài 21 - 3 - 2013 Nhận lại sau sửa ngày 8 - 9 - 2013