TRƯỜNG Đ

H

ĐẠI HỌC THÁI NGUYÊN
Ệ THÔNG TIN & TRUYỀN THÔNG

Thái Nguyên 9 - 2015
Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

TRƯỜ

ĐẠI HỌC THÁI NGUYÊN
Ệ THÔNG TIN & TRUYỀN THÔNG

Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01.01

Người hướng dẫn khoa học
TS. Nguyễn Huy Đức
Thái Nguyên 9 - 2015
Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

i
LỜI CAM ĐOAN
Tôi xin cam đoan luận văn này của tự bản thân tôi tìm hiểu, nghiên cứu
dưới sự hướng dẫn của TS. Nguyễn Huy Đức. Các chương trình thực nghiệm

Trong quá trình viết luận văn, bản thân em đã hết sức cố gắng
nhưng do khả năng, vốn kinh nghiệm nghiên cứu và thời gian có hạn nên
luận văn không tránh khỏi những thiếu sót. Vì vậy, em rất mong nhận
được sự chỉ bảo, góp ý của các nhà khoa học, các thầy, cô để
.
!

,

Số hóa bởi Trung tâm Học liệu - ĐHTN

08 năm 2015

/>

iii
MỤC LỤC
LỜI CAM ĐOAN .............................................................................................. i
................................................................................................... ii
MỤC LỤC ........................................................................................................ iii
N VĂN .... v

DANH MỤC VIẾT TẮ
DANH MỤ

ẢNG BIỂU .................................................................... vi

DANH MỤ

Ẽ ........................................................................ vii

iv
....................... 36
....................................... 40
2 ........................................................................................... 42
Chương 3. T

. 43
........................................................................................... 43
................................................................................. 44
............................................................................ 46
.............................................................................. 48

Kết luận chương 3 ........................................................................................... 54
...................................................... 55
............................................................................... 57
PHỤ LỤC ........................................................................................................ 59

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

v
DANH MỤC VIẾT TẮT
Ký hiệu

Diễn giải

RU
U


X
X

Y
Y
X

Y

X

IY

IX

Y

IY

LĐQH
CSDL

Cơ sở dữ liệu

PTH
LKH

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

2.3. Một số LKH trong TD tương ứng với PTH xấp xỉ trong R ............ 28
............................................................ 45

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

vii
DANH MỤ

HÌNH VẼ

Hình 1.1. Phân loại các thuật toán khai phá tập mục phổ biến ....................... 17
................................................... 44
....................................... 46
................................................................... 47
................................. 48
...................................................... 49
.......................................... 49
Hình 3.7. Giao diện kết quả khai phá PHT xấp xỉ .......................................... 51
Hình 3.8. Giao diện kết quả khai phá PTH xấp xỉ .......................................... 52

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

1
MỞ ĐẦU
1. Tính cấp thiết của đề tài
Sự phát triển nhanh chóng của công nghệ thông tin (CNTT) đã tác động

, tôi chọn đề tài: “Khai phá phụ thuộc hàm xấp xỉ

sử dụng luật kết hợp và ứng dụng” làm đề tài luận văn tốt nghiệp của mình.
2. Đối tượng và phạm vi nghiên cứu
Tìm hiểu về phụ thuộc hàm, phụ thuộc hàm xấp xỉ và các tính chất, độ
đo lỗi của nó, khái niệm luật kết hợp, các tính chất và thuật toán điển hình
khai phá luật kết hợp.


2
Luận văn đi sâu vào khai phá phụ thuộc hàm xấp xỉ sử dụng luật kết
hợp và các vấn đề liên quan thuộc lĩnh vực phát hiện tri thức từ dữ liệu. Xây
dựng một ứng dụng thực nghiệm phát hiện phụ thuộc hàm xấp xỉ trong cơ sở
dữ liệu bán hàng của siêu thị.
3. Hướng nghiên cứu của đề tài
- Nghiên cứu về phụ thuộc hàm, phụ thuộc hàm xấp xỉ và các độ đo lỗi
của nó.
- Nghiên cứu về khai phá luật kết hợp: Bài toán xuất phát, các khái
niệm tập mục phổ biến, luật kết hợp cùng các khái niệm độ hỗ trợ, độ tin
cậy… Thuật toán điển hình tìm tập phổ biến và luật kết hợp.
- Biểu diễn phụ thuộc hàm xấp xỉ trên quan hệ thông qua luật kết hợp
và các độ đo của chúng. Thuật toán xác định phụ thuộc hàm xấp xỉ dựa trên
luật kết hợp.
4. Phương pháp nghiên cứu
Phương pháp nghiên cứ

ứu lý thuyết kết

hợp với đánh giá thực nghiệm cụ thể: Phân tích, tổng hợp các kết quả nghiên
cứu về phụ thuộc hàm, phụ thuộc hàm xấp xỉ, luật kết hợp… T

kết hợp, đi sâu tìm hiểu khai phá phụ thuộc hàm xấp xỉ sử dụng luật kết hợp
có ý nghĩa khoa học và thực tiễn.
6. Cấu trúc luận văn
Cấu trúc
luận

tài liệu tham khảo.

bao gồm phần mở đầu,

, kết

3 chương

Chương 1: Giới thiệu về phụ thuộc hàm, phụ thuộc hàm xấp xỉ và luật
kết hợp.
Chương 2:

.

Chương 3:

.


4
Chương 1
TỔNG QUAN VỀ PHỤ THUỘC HÀM, PHỤ THUỘC HÀM XẤP XỈ VÀ
LUẬT KẾT HỢP
Chương này trình bày tổng quan về phụ thuộc hàm, phụ thuộc hàm xấp

RU

Dom A1

Dom A2

...

Dom Am

R
.
(PTH
X → Y (trong

X, Y ⊆ U)

R (U
X→Y

t, s R | t X

Khi PTH X → Y
X→Y

s X

R. N

R


C

1

a1

b1

c1

2

a2

b2

c2

3

a2

b2

c3

{T} → {A, B, C}, {C} → {T, A, B},

R

X→Y

U

F = X → Y. N
F+. L

F trên U
trên U

R (F). N

(A1) – (A3) như sau:

F
Với ∀ X, Y, Z ⊆ U:
(A1)
Y⊆X

X → Y ∈ F+

ia tăng

(A2)

X → Y ∈ F+

X ⋃ Z → Y ⋃ Z ∈ F+

X → Y ∈ F+

Như vậy
g3 X

Y, R

min{| S || S

R, ( R \ S ) ( X
| R|

Y )}

Một cách tương đương
g3 X

Y, R

1

max{|S || S

R, S ( X
|R|

Y )}

Độ đo lỗi trên còn được gọi là độ đo lỗi g3 .
Có thể thấy nếu X → Y là một PTH đúng trên R thì độ đo lỗi

g3 X


B

C

D

t1

0

0

1

1

t2

0

1

1

1

t3

0


0

2

0

t7

1

1

2

1

Xét PTH AB → C trên R (U).
Rõ ràng bỏ bộ 6 (hoặc bộ 5) thì PTH AB → C sẽ đúng trên quan hệ R.
Tức số bộ ít nhất cần loại khỏi quan hệ R để PTH AB → C đúng trên các bộ
còn lại là 1.
Suy ra: g3 AB

1
7

C, R

Ví dụ 1.3. Xét quan hệ R ở ví dụ 1.2 trên và ngưỡng lỗi = 0,5.
Theo ví dụ trên, ta có: g3 AB


R (U

X, Y ⊆ U.

a.
Độ đo lỗi g2 của Kivinen và Mannila (1995)
Để đo lỗi của một PTH X → Y, ngoài độ đo g3 Kivinen và Mannila
[11] còn đưa ra độ đo lỗi g2 như sau: Tỷ số giữa các bộ ngoại lệ của X → Y
với các bộ trong quan hệ R được gọi là độ đo lỗi g2 của X → Y trên R, ký hiệu
g2 (X → Y, R).

Như vậy

g2 X

t

Y, R

R| s

R, t X

s X vµ t Y

sY

R



hàm

X

.C

X.

Độ đo lỗi g3 Kivinen và Mannila (1995)
Độ đo này đã được giới thiệu trong mục 1.2.1 ở trên. Ở đây chúng ta có
thể định nghĩa lạ

:


9
g3 X

min Re | Re

Y, R

R và R \ Re

X

Y

R


Một cách hình thức:
g1 X

t, s | t, s

Y, R

R, t X

s X vµ t Y
R

sY

2

Ví dụ 1.5. Xét quan hệ R ở ví dụ 1.2 trên. Ta có:

g1( A

4
49

C, R)

Nhận xét:
Độ đo lỗi g1 có giá trị trong khoảng [0, 1]. Khi g1( X
nghĩa sự phụ thuộc của Y vào X là PTH


k

.

1.6. Cho

D trên tập các mục I = {A, H, L, E, F}.

CSDL giao tác D như sau :
D = {{A, F, L, E}; {F, H, E}; {A, F, L, E}; {A, F, H, E}; {A, F, H, L, E}; {F, H, L}}
1.3. V
giao
1

{A, F, L, E}

2

{F, H, E}

3

{A, F, L, E}

4

{A, F, H, E}

5


giữa số các

X.
(hay
minsupp ∈ [0,
.
:


11
1.1. [7]

⊆ Y.

,Y

) supp (X) ≥ supp (Y).

(1) (
(2)

.

(3) N

.

là tập

.


Y

là kết luận của luật.
quan trọng là độ hỗ trợ và độ tin cậy:

Y , ký hiệu là s X

X

X

trong D
:s X

T

Y

D| X

Y.
Y

T

P X

Y


X
c X

supp X Y
supp X

Y

c X
trong D

X

Y l
c X

Y
T

X

Y

T

Y:
c X

Y


[0, 1].

:
Giả sử có

:

.
ung thư ph . T
.
:
1)

.


13
, “ung thư p

2)

.

:
1)

.

2)



Z cũng là LKH mạnh.

1.4. [7] Nếu X

Y

Z là LKH mạnh thì X

Z và Y

Z

chưa chắc LKH mạnh.
1.5. [7] Nếu X

X

Y và Y

Z là LKH mạnh thì chưa chắc

Z là LKH mạnh.
1.3.3. Khai phá luật kết hợ

:


14
1.1. (K

X

Y, Y

X

:

:

hay
X \Y

c Y

minconf

Y

. Trong hai bước ở trên thì

c
gian. B

X \Y

X \Y

(b1



T4

B, E

T5

B, D, F


15
Độ hỗ trợ của các mục (hay tập mục chỉ gồm 1 mục) được minh hoạ
trong bảng 1.6.

đây, mục A xuất hiện trong hai giao tác T1 và T3 c

D ( được mô tả trong bảng 1.5) nên Supp (A) = 2/5 = 40%.
Bảng 1.6. Độ hỗ trợ của các mục
Mục

Số giao tác

Đô hỗ trợ sup (X)

A

2

40%


Tương tự trong bảng 1.7 tính độ hỗ trợ của các tập mục tron
D. Ví dụ AB xuất hiện chỉ l lần trong giao tác T3. Do đó, độ hỗ trợ
của tập mục này là 20%.
Kết quả được thể hiện qua bảng 1.7 sau đây:

Bảng 1.7. Độ hỗ trợ của các tập mục
Tập mục

Số giao tác

Độ hỗ trợ sup(X)

AC

2

40%

AB

1

20%

BD

1

20%


ABCE

1

20%


16
Tính độ tin cậy của một số LKH sinh ra từ các tập mục trong bảng 1.7. Ví
dụ độ tin cậy 100% cho luật A

C (có nghĩa là trong mọi giao tác trong đó

có A xuất hiện thì C cũng xuất hiện). Độ tin cậy của luật này được tính bằng cách
chia số giao tác mà tập mục AC xuất hiện là 2 cho số giao tác mà mục A xuất
hiện trong bảng 1.5. Kết quả độ tin cậy của các luật thể hiện qua bảng 1.8.
Bảng 1.8. Độ tin cậy của các luật
Luật kết hợp

Độ tin cậy conf ( X

A

C

100%

A

B

Bài toán khai phá tập mục phổ biến có thể chia thành hai bài toán nhỏ:
Tìm các tập mục ứng viên và tìm các tập mục phổ biến. Tập mục ứng viên là
tập mục mà ta hy vọng nó là tập mục phổ biến, phải tính độ hỗ trợ của nó để
kiểm tra. Tập mục phổ biến là tập mục có độ hỗ trợ lớn hơn hoặc bằng
ngưỡng hỗ trợ tối thiểu cho trước. Ta có thể phân chúng theo hai tiêu chí sau:
- Phương pháp duyệt qua không gian tìm kiếm.
- Phương pháp xác định độ hỗ trợ của tập mục.

Phương pháp duyệt qua không gian tìm kiếm được phân làm hai cách:
Duyệt theo chiều rộng (Breadth First Search - BFS) và duyệt theo chiều sâu
(Depth First Search - DFS).
Duyệt theo chiều rộng là duyệt qua cơ sở dữ liệu gốc để tính độ hỗ trợ của
tất cả các tập mục ứng viên có (k - 1) mục trước khi tính độ hỗ trợ của các tập