1
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN MINH HUY
PHỤ THUỘC HÀM XẤP XỈ VÀ ỨNG DỤNG
TRONG KHAI PHÁ DỮ LIỆU LUẬN VĂN THẠC SĨ
1.3 Phụ thuộc hàm xấp xỉ 14
1.3.1 Phụ thuộc hàm xấp xỉ loại 1 14
1.3.2 Phụ thuộc hàm xấp xỉ loại 2 16
1.3.3 Bao đóng xấp xỉ 20
1.3.4 Khoá xấp xỉ 21
Chương 2 - Xây dựng cây quyết định 24
3
2.1 Đặt vấn đề 24
2.2 Bảng quyết định 24
2.2.1 Hệ thống thông tin 24
2.2.2 Bảng quyết định 27
2.3 Cây quyết định 30
2.4 Ảnh hưởng của phụ thuộc hàm, phụ thuộc hàm xấp xỉ khi xây dựng
cây quyết định 36
Chương 3 - Thử nghiệm và đánh giá 37
3.1 Thuật toán TANE 37
3.1.1 Mô tả thuật toán 37
3.1.2 Độ phức tạp 38
3.2 Thuật toán AFDMCEC 38
3.2.1 Phân tích thử nghiệm 39
3.2.2 Những so sánh về độ phức tạp thời gian 40
KẾT LUẬN 41
TÀI LIỆU THAM KHẢO 42
PHỤ LỤC 43
a) Giao diện chương trình
b) Thủ tục tính phụ thuộc hàm xấp xỉ
c) Thủ tục phân hoạch
5 DANH MỤC CÁC BẢNG BIỂU
Bảng 1.1 Quy trình phát hiện tri thức
Bảng 1.2 Bảng cơ sở dữ liệu quan hệ
Bảng 1.3 Cây khai phá các AFDs(ví dụ với 5 thuộc tính)
Bảng 1.4 Bảng cơ sở dữ liệu quan hệ số
Bảng 1.5 Bảng cơ sở dữ liệu kiểm toán(ví dụ trong 5 tháng)
Bảng 2.1 Bảng dữ liệu các đồ chơi
Bảng 2.2 Bảng các triệu chứng của bệnh nhân
Bảng 2.3 Bảng quyết định về cúm
Bảng 2.4 Bảng rút gọn thứ nhất của bảng quyết định về cúm
Bảng 2.5 Bảng rút gọn thứ hai của bảng quyết định về cúm
Bảng 2.6 Bảng chọn ứng cử viên vào ngạch giảng dạy
Bảng 2.7 Bảng dữ liệu điều tra khách hàng mua ôtô
Bảng 2.8 Cây quyết định tại bước 1 trên thuộc tính phụ cấp
Bảng 2.9 Cây quyết định tại bước 2
phụ thuộc hàm xấp xỉ đang được quan tâm nghiên cứu, một trong hững thuật toán
đó là TANE - một thuật toán tương đối hiệu quả trong khai phá phụ thuộc hàm xấp
xỉ. 7
CHƯƠNG 1:
PHỤ THUỘC HÀM VÀ PHỤ THUỘC HÀM XẤP XỈ
1.1 Khai phá dữ liệu
1.1.1 Phát hiện tri thức và khai phá dữ liệu
Phát hiện tri thức trong các cơ sở dữ liệu là một qui trình nhận biết các mẫu
hoặc các mô hình trong dữ liệu với các tính năng: hợp thức, mới, khả ích, và có thể
hiểu được. Còn khai thác dữ liệu là một bước trong qui trình phát hiện tri thức gồm
có các thuật toán khai thác dữ liệu chuyên dùng dưới một số qui định về hiệu quả
tính toán chấp nhận được để tìm ra các mẫu hoặc các mô hình trong dữ liệu. Nói
một cách khác, mục đích của phát hiện tri thức và khai phá dữ liệu chính là tìm ra
các mẫu và/hoặc các mô hình đang tồn tại trong các cơ sở dữ liệu nhưng vẫn còn bị
che khuất bởi hàng núi dữ liệu.
Qui trình phát hiện tri thức
Qui trình phát hiện tri thức được mô tả tóm tắt :
Bảng 1.1 Quy trình phát hiện tri thức
- Bước thứ nhất là tìm hiểu lĩnh vực ứng dụng và hình thành bài toán, bước
Trong mỗi CSDL luôn tồn tại nhiều mối liên hệ giữa các thuộc tính, giữa các
bộ; sự liên hệ này có thể xảy ra trong cùng một quan hệ hoặc trong các quan hệ của
một lược đồ CSDL. Các mối liên hệ này là những điều kiện bất biến mà tất cả các
bộ của những quan hệ có liên quan trong CSDL đều phải thoả mãn ở mọi thời
điểm. Những điều kiện bất biến đó được gọi là rằng buộc toàn vẹn.
Phụ thuộc hàm là 1 công cụ dùng để biểu diễn 1 cách hình thức 1 số rằng
buộc toàn vẹn.
9
Các phụ thuộc hàm là các tương quan giữa các thuộc tính của một quan hệ:
Một phụ thuộc hàm chỉ ra rằng giá trị của một thuộc tính được xác định duy nhất
bởi một số các thuộc tính khác. Vấn đề phát hiện các phụ thuộc hàm từ các quan hệ
đã nhận được các mối quan tâm đáng kể. Việc phân tích CSDL tự động, đương
nhiên, rất thú vị cho các mục tiêu khai phá tri thức và khai phá dữ liệu , và các phụ
thuộc hàm có nhiều ứng dụng trong các lĩnh vực quản lý CSDL, tối ưu hóa truy
vấn…
Một cách hình thức, một phụ thuộc hàm trên một lược đồ quan hệ R là một
biểu diễn XA với X R và A
R.Phụ thuộc này đúng trong một quan hệ r trên
R cho trước nếu với mọi cặp hàng t,u
R, ta có nếu t[B] = u[B] mọi B
X thì
t[A] = u[A] (ta cũng nói rằng t và u thoả trên X và A).
Ví dụ :
Mã Sinh viên Họ và tên Số chứng minh Năm sinh
Quê quán
n
) là tập các thuộc tính: giả
sử X, Y, Z U, hệ tiên đề Armstrong bao gồm:
* Tính phản xạ: Nếu Y X thì X -> Y
* Tính tăng trưởng: Nếu Z U, X->Y thì ZX -> ZY. Trong đó ZX=Z
U
* Tính bắc cầu: Nếu X -> Y và Y -> Zthì X -> Z.
Ví dụ:
Cho AB -> C, C -> A, chứng minh BC -> ABC
(1) C -> A (theo giả thiết)
(2) BC -> AB (áp dụng luật tăng trưởng tăng (1) lên B)
(3) AB -> C (theo giả thiết)
(4) AB -> ABC (tăng (3)AB)
(5) BC -> ABC (bắc cầu (1), (2)).
Bổ đề 1:
Hệ tiên đề Armstrong là đầy đủ, có nghĩa là nếu F là tập phụ thuộc hàm đúng
trên quan hệ r và f : X -> Y là một phụ thuộc hàm được suy dẫn từ F nhờ hệ tiên đề
Armstrong thì f đúng trên r
Bổ đề 2:
Tính hợp : nếu X -> Y và X -> Z thì X -> YZ .
Tính tựa bắc cầu : Nếu X -> Y và WY -> Z thì XW -> Z.
Tính tách: Nếu X -> Y và Z Y thì X -> Z.
Bao đóng của F được kí hiệu là F
+
, là tập tất cả các phụ thuộc hàm được suy
diễn logic nhờ tiên đề Armstrong, 3 bổ đề trên từ F, nếu F = F
+
thì F là họ đầy đủ
của các phụ thuộc hàm. Bao đóng của tập thuộc tính (X
+
, X
1
, X
2
, , X
i
BC0: Đặt X
0
= X
BC1: Nếu tồn tại phụ thuộc hàm f: Y->Z F sao cho Y X
0
, Z
U thì X
1
=X
0
Z
BC2: Tương tư.
Until X
i
= X
i
+1.
Kết luận X
+
= X
i
.
Ví dụ:
= {{1, 2}, {3, 4, 5}, {6, 7, 8}}.
Các lớp tương đương đối với các thuộc tính kết hợp (B, C), ví dụ:
∏
{B, C}
r = {{1}, {2}, {3, 4}, {5}, {6}, {7}, {8}}.
Tuple ID A B C D E
1 1 A $ Flower 2
2 1 A Tulip 2
3 2 A $ Daffodil 0
4 2 A $ Flower 0
5 2 B Lily 0
6 3 B $ Orchid 1
7 3 C Flower 1
8 3 C # Rose 1
Bảng 1.2 : Bảng cơ sở dữ liệu quan hệ
FD X → Y được suy ra khi và chỉ khi Π (x) lọc Π (Y).
Trong ví dụ : thuộc tính A có các bộ sau đây của lớp tương đương: ((T1, T2),
(T3, T4, T5), (T6, T7, T8)), và thuộc tính E có các tập sau của lớp tương đương:
((T1, T2), (T3, T4, T5), (T6, T7, T8)). Các lớp tương đương trong thuộc tính E
được lọc bởi các lớp tương đương trong thuộc tính A, chúng ta có thể khám phá ra
rằng A → E .
1.2.4 Định nghĩa phủ cực tiểu (tối thiểu)
13
Cho tập thuộc tính U và tập phụ thuộc hàm F. Nguời ta nói F là tối thiểu khi và
chỉ khi:
Vế phải của mỗi phụ thuộc hàm trong F chỉ có một thuộc tính độc nhất.
BC3: Loại bỏ những phụ thuộc hàm dư thừa:
Giả sử hai phụ thuộc hàm có vế phải giống nhau: f1 = X -> A và f2 = Y -> A,
lúc đó nếu có A X
+
F
\ {f1} thì loại f1 ra khỏi F:
1.2.5 Khoá của quan hệ
a) Khoá của tập thực thể
Là một hoặc một tập các thuộc tính xác định duy nhất một thực thể trong một
tập thực thể.
b) Khoá của quan hệ
Tập các thuộc tính X của một quan hệ R là một khoá nếu. Không tồn tại 2 bộ
khác nhau nhưng tất cả các phần tử của X đều giống nhau, và không có tập con
thực sự nào của X có tính chất này.
Định nghĩa: Cho lược đồ quan hệ R(A
1
, A
2
, ,A
n
) và tập phụ thuộc hàm F, X
A
1
, A
2
, ,A
n
. Ta nói X là một khoá của R khi và chỉ khi X -> A
1
F = { A → C, AB → DC}, khoá là {AB}. Khi đó thuộc tính A, B gọi là thuộc
tính khoá, còn thuộc tính D, C gọi là thuộc tính không khóa.
15
- Thuật toán tìm tất cả các khoá của một lược đồ quan hệ
Bước 1: Tạo tập thuộc tính nguồn TN, tập thuộc tính trung gian TG
Bước 2: if TG = ∅ then lược đồ quan hệ chỉ có một khoá K
K = TN
Kết thúc
Ngược lại
Qua bước 3
Bước 3: Tìm tất cả các tập con Xi của tập trung gian TG
Bước 4; Tìm các siêu khoá Si băng cách :
X
i
if ( TNX
i
)
+
= Q
+
then
Si = TNX
i
Bước 5: Tìm kháo bằng cách loại bỏ các siêu khoá không tối tiểu
S
i
, S
1 1 A $ Flower 2
2 1 A Tulip 2
3 2 A $ Daffodil 0
4 2 A $ Flower 0
5 2 B Lily 0
6 3 B $ Orchid 1
7 1 C Flower 1
8 3 C # Rose 1
Bảng 1.2 : Bảng cơ sở dữ liệu quan hệ
Trong bảng cơ sở dữ liệu bên trên. Kiểm tra phụ thuộc hàm AB không
được suy diễn. Chúng ta tìm thấy các lớp tương đương:
∏
{A}
= {{1, 2,7}, {3, 4, 5}, {6, 8}}.
∏
{B}
= {{1}, {2, 3, 4,}, {5, 6}, {7,8}}.
A không lọc được B ở các lớp khác nhau. Suy ra AB không đúng.
Tuy nhiên A B có thể đúng ở trong ví dụ, với độ đo là g3. Nếu chúng ta
loại bỏ 1 vài bản ghi từ các mối quan hệ, bằng phương pháp loại trừ nhau cho việc
tính toán g3.
∏
{A}
= {{1, 2}, {3, 4, 5}, {6, 7, 8}}.
∏
{B}
= {{1}, {2, 3, 4,}, {5, 6}, {7,8}}.
Chúng ta tìm được ∏
{A} {B}
= {{1}, {2}, {3,4}, {5}, {6}, {7.8}}. Lớp tương
Bảng 1.3 : Cây khai phá tất cả các AFD.
1.3.2 Phụ thuộc hàm xấp xỉ loại 2
Cho r là một quan hệ trên tập thuộc tính R= {A
1
, A
2
,A
n
} trong đó các thuộc
tính A
1
, A
2
, A
n
có thể là thuộc tính định danh(categorical), rời rạc hoặc liên
tục(trường số). Đối với những thuộc tính định danh, ta tiến hành thực hiện ánh xạ
tất cả các giá trị có thể tới một tập các số nguyên dương liên kề.
Định nghĩa: (khoảng cách giữa 2 bộ giá trị trên tập thuộc tính)
Với 2 bộ t
2
(A
i
)|), A
i
X):
18
Hàm max(x, y) là hàm chọn ra số lớn nhất trong 2 số x và y;
Trường hợp max(|t
1
(A
i
)|- |t
2
(A
i
)|)= 0, tức t
1
(A
i
) = t
2
(A
i
) = 0 thì ta qui ước:
|t
1
(A
i
(X)) >=0 với t
1
, t
2
, X tuỳ ý ;
A2. p(t
1
(X), t
2
(X)) = 0 t
1
(X) = t
2
(X)
p(t
1
(X),t
2
(X)) p(t
1
(X),t
3
(X)) + p(t
3
(X),t
2
(X))
Và ngoài ra cũng dễ chứng minh các tính chất:
Nếu X Y thì p(t
1
2
(X)) thì ta cũng có
p(t
1
(Y), t
2
(Y))
Ví dụ:
A B C D E
2.5 18 160 25 12
2.51 18 160.5 15 13
3.6 20 320 30 16
3.65 20 323 45 28
4.25 25 641 60 19
Bảng 1.4 : Bảng dữ liệu quan hệ số
Ta thấy giữa bộ A, B có mối tương quan với cột C với = 0.05 ta kiểm tra
điều kiện phụ thuộc hàm xấp xỉ
19
với cặp hàng 1,2
ta có p(t
1
(AB), t
2
(AB)) = max (|t
1
(A) - t
2
(A)|/max(|t
1
2
Y
cũng đúng trên r
- Tính chất 3 : Tính phản xạ
Nếu Y X khi đó X >
Y là phụ thuộc hàm xấp xỉ loại 2 với mức tuỳ ý (0
<1)
- Tính chất 4 : Tính bắc cầu
Nếu X >
Y và Y >
Z thì X >
Z
- Tính chất 5 : Tính gia tăng
Với mọi X, Y, Z R và mức nào đó, nếu X >
Y thì XZ >
YZ.
1.3.2.1 Xây dựng thuật toán kiểm tra phụ thuộc hàm xấp xỉ loại 2
Giả sử cho r = {t
1
, t
2
, ,t
n
} là một quan hệ trên tập thuộc tính R và X, Y R,
Giả sử cho r = {t
1
, t
2
, ,t
n
} là một quan hệ trên tập thuộc tính R và X, Y R
với một số cho trước ( 0 <1); E
r
là một hệ xấp xỉ mức thoả phụ thuộc hàm
xấp xỉ loại 2 mức :X >
Y khi và chỉ khi :
E()i,j E
r
: ( X E()i,j Y E()i,j )
1.3.2.2 Ứng dụng trong thực tế hoạt động kiểm toán
Hoạt động kiểm toán của kiểm toán nhà nước gắn liền với việc phát hiện ra
những hiện tượng bất thường hoặc ngoại lai trong tập dữ liệu thông tin của doanh
nghiệp hoặc đơn vị được kiểm toán. Trên cơ sở các hiện tượng bất thường nay,
kiểm toán viên sẽ tiến hành các biện pháp nghiệp vụ để xem xét liệu có sự gian lận
hoặc sai sót hay không và tiến hành xử lý.
Ví dụ :
THANG TONG_CP CHI_NVL TIENLUONG VAT
1 1,450,267,320 580,271,928 507,823,562 41,019,035
2 1,465,890,000 586,521,000 513,291,500 41,456,470
3 1,500,540,000 600,381,000 525,419,000 42,426,670
4 1,510,567,000 604,391,800 528,928,450 42,707,426
5 1,515,680,000 680,437,000 530,718,000 48,030,590
Bảng 1.5: Bảng cơ sở dữ liệu kiểm toán
} được gọi là bao đóng xấp xỉ của A trên s. Có
thể thấy rằng A B F
+
nếu và chỉ nếu B A
+
.
1.3.3.1 Thuật toán tìm bao đóng xấp xỉ
Thuật toán 1:
Vào: s
z
= <R, F
z
>, ở đây R={ a1, , an} tập hữu hạn các thuộc tính, F
z
tập các
phụ thuộc hàm xấp xỉ, A R.
Ra: A
z
+
bao đóng của A đối với F
z
Thuật toán thực hiện như sau:
Tính các tập thuộc tính A
0
, A
1
, theo qui tắc:
z
. 22Ví dụ:
Cho bảng quan hệ sau:
A B C D E
2.5 18 160 19 18
2.51 18 160.5 21 20
3.6 20 320 22 20
3.65 20 323 20 18
Ta xây dựng được một sơ đồ quan hệ <R,F
> với tập thuộc tính là R=
<A,B,C,D,E> và tập phụ thuộc xấp xỉ F
={AB >0.05 C, AB >0.05 E, E >0.05
D} với mức xấp xỉ của = 0.05.
Áp dụng thuật toán tính bao đóng xấp xỉ trên ta dễ dàng thu được bao đóng
xấp xỉ của AB = {ABCDE}
1.3.4 Khoá xấp xỉ
Giả sử s
= < R, F> là một sơ đồ quan hệ xấp xỉ. Khi đó A là một khoá xấp
xỉ của s
là một khoá xấp xỉ của s
Thuật toán thực hiện như sau:
Tính liên tiếp các tập thuộc tính K
0
, K
1
,K
n
như sau:
K
0
= R = { a
1
, , a
n
}
23
K
i
= K
i-1
, nếu K
i-1
- {a
i
} R F+, và K
i-1
> với tập thuộc tính là R= {A, B, C, D, E} và tập
phụ thuộc xâp xỉ F
={AB >0.05 C, AB >0.05 E, E >0.05 D} với mức xấp xỉ
của = 0.05.
Áp dụng thuật toán trên ta có:
Bước 1: Đặt K
0
= R= {A, B, C, D, E}
Bước 2: Tính K
1
Xét K
0
\A = {B, C, D, E}
Tính bao đóng xấp xỉ mức 0.05 của {B, C, D, E}.{B, C, D, E}
+
0.05 = {B, C,
D, E} <>R, do vậy K
1
=K
0
= {A, B, C, D}
Bước 3: Tương tự ta tính được K
2
= K
0
; K
3
+ Không có thuộc tính khoá mà phụ thuộc hàm xấp xỉ vào thuộc tính không
khoá.
Thuật toán kiểm tra BCNF
Bước 1 : Xác định khoá
Bước 2 : Kiểm tra thuộc tính không khoá phải phụ thuộc hàm xấp xỉ đầy đủ
vào khoá chính
Bước 3 : Kiểm tra các thuộc tính không khoá phải phụ thuộc xấp xỉ trực tiếp
vào khoá chính.
Bước 4 : Với mỗi thuộc tính khoá kiểm tra có phụ thuộc hàm xâp xỉ vào
thuộc tính khoá không. Nếu phụ thuộc thì luợc đồ quan hệ không thuộc dạng chuẩn
BCNF
Ví dụ 1: Cho lược đồ quan hệ U = {A, B, C, D} và tập các phụ thuộc hàm
xấp xỉ với mức xấp xỉ (A~>
B, B~>
A, AC ~>
D)
Xác định : AC hoặc BC là khoá
Nếu AC là khoá ta có B~>
A(thuộc tính khoá phụ thuộc hàm xấp xỉ và
thuộc tính không khoá).
Nếu BC là khoá ta có A~>
B(thuộc tính khoá phụ thuộc hàm xấp xỉ và thuộc
tính không khoá).
nó, nhằm nâng cao hiệu quả cho cây được xây dựng [3, 5, 8, 9]. Hơn nữa, có
nhiều trường hợp trong thực tế, các nhóm thuộc tính mặc dầu giữa chúng không
có sự phụ thuộc theo định nghĩa của phụ thuộc hàm thông thường mà lại phụ
thuộc theo kiểu tương quan hàm số nào đó, ta gọi là phụ thuộc hàm xấp xỉ. Các
nhóm thuộc tính này làm phức tạp việc xác định mẫu nên tăng chi phí cho quá
trình huấn luyện, quan trọng hơn là chúng gây nhiễu nên cây được xây dựng
không có hiệu quả cao. Ở đây, chúng ta sẽ xét đến các phụ thuộc dữ liệu loại này
nhằm xây dựng cây quyết định có khả năng dự đoán cao.
2.2 Bảng quyết định
2.2.1 Hệ thống thông tin
2.2.1.1 Định nghĩa
Hệ thống thông tin là một cặp A = (U, A), với U là tập hữu hạn, khá rỗng,
được gọi là tập vũ trụ các đối tượng và A là tập hữu hạn khác rỗng các thuộc tính.
Với mỗi u U và a A, ta ký hiệu u(a) là giá trị của đối tượng u tại thuộc tính a.
Nếu gọi Ia là tập tất cả các giá trị của thuộc tính a, thì u(a) Ia với mọi u U.
Bây giờ, nếu B = {b1, b2,…,bk} A là một tập con các thuộc tính thì ta sẽ ký hiệu
bộ các giá trị u(bi) bởi u(B). Như vậy, nếu u và v là hai đối tượng, thì ta sẽ viết
u(B) = v(B) nếu u(bi) = v(bi) với mọi i = 1,…,k.
Copyright: Tài liệu đại học ©