ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
=======  ======

NGUYỄN NGỌC QUỲNH CHÂU

MỘT SỐ PHƯƠNG PHÁP KHAI PHÁ LUẬT KẾT
HỢP TRÊN CƠ SỞ DỮ LIỆU GIA TĂNG

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

Hà Nội – 2015


ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
=======  ======

NGUYỄN NGỌC QUỲNH CHÂU

MỘT SỐ PHƯƠNG PHÁP KHAI PHÁ LUẬT KẾT
HỢP TRÊN CƠ SỞ DỮ LIỆU GIA TĂNG
Ngành

: Công nghệ thông tin

Chuyên ngành : Kỹ thuật phần mềm
Mã số


Tôi cũng xin bày tỏ lời cảm ơn sâu sắc nhất tới thầy giáo GS Vũ Đức Thi
đã tận tình hướng dẫn, định hướng giải quyết các vấn đề trong luận văn.
Tôi xin cảm ơn Ban lãnh đạo và các đồng nghiệp trong Khoa Công nghệ
thông tin, Đại học Thủy Lợi đã tạo điều kiện cho tôi trong suốt quá trình học tập.
Cuối cùng, tôi xin cảm ơn gia đình, bạn bè đã đồng hành cùng tôi trong quá
trình học tập.


3

MỤC LỤC
LỜI CAM ĐOAN ........................................................................................................ 1
LỜI CẢM ƠN ............................................................................................................. 2
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ................................................... 5
DANH MỤC HÌNH VẼ .............................................................................................. 6
DANH MỤC BẢNG BIỂU ......................................................................................... 7
CHƯƠNG 1:

KHAI PHÁ LUẬT KẾT HỢP ............................................................ 9

1.1 Tổng quan về khai phá dữ liệu ............................................................................. 9
1.2 Giới thiệu về khai phá luật kết hợp .................................................................... 10
1.3 Một số khái niệm cơ bản [3, 5, 7] ...................................................................... 11
1.3.1 Cơ sở dữ liệu giao tác ............................................................................... 11
1.3.2 Tập mục thường xuyên ............................................................................. 13
1.3.3 Luật kết hợp .............................................................................................. 14
1.4 Một số thuật toán khai phá luật kết hợp ............................................................. 16
1.4.1 Thuật toán AIS .......................................................................................... 16
1.4.2 Thuật toán Apriori..................................................................................... 18
CHƯƠNG 2:

Lưu trữ và khôi phục cây gia tăng ............................................................. 41
Ví dụ minh họa ......................................................................................... 44
Nhận xét về thuật toán Gia tăng 2 ............................................................. 47
Đề xuất ý tưởng cải tiến cấu trúc cây gia tăng ........................................... 47

CHƯƠNG 3:

CÀI ĐẶT CHƯƠNG TRÌNH THỬ NGHIỆM.................................. 53

3.1 Mô tả chương trình chạy.................................................................................... 53
3.2 Thử nghiệm đánh giá thuật toán Gia tăng 1 ....................................................... 56
3.2.1 Thử nghiệm và đánh giá thuật toán trên nội dung 1, 2 ............................... 56
3.2.2 Thử nghiệm và đánh giá thuật toán trên nội dung 3 ................................... 60
3.3 Kết luận ............................................................................................................. 62
KẾT LUẬN ............................................................................................................... 64
TÀI LIỆU THAM KHẢO ......................................................................................... 65


5

DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT

Ký hiệu
xi
tj
I
T
X={
sup(X)
S0

gọn hơn...................................................................................................................... 52
Hình 3-1: Kết quả chạy thử nghiệm ban đầu của Gia tăng 1 ....................................... 54
Hình 3-2: Cơ sở dữ liệu test cho Apriori và Gia tăng 1 .............................................. 54
Hình 3-3: Kết quả chạy Apriori và Gia tăng 1 dữ liệu ban đầu hình 3.2 ..................... 55
Hình 3-4: Dữ liệu tăng thêm T’ .................................................................................. 55
Hình 3-5: Kết quả chạy Apriori và Gia tăng 1 trên T+T’ ............................................ 56
Hình 3-6: Thời gian chạy của Apriori và Gia tăng 1 trên CSDL 1, 2, 3,4 ban đầu ...... 58
Hình 3-7: Thời gian chạy của Apriori và Gia tăng 1 trên CSDL 1, 2,3, 4 sau khi gia
tăng............................................................................................................................ 58
Hình 3-8: Thời gian chạy của Apriori và Gia tăng 1 trên CSDL 5, 6, 7, 8 ban đầu ..... 59
Hình 3-9: Thời gian chạy của Apriori và Gia tăng 1 trên CSDL 5, 6, 7, 8 sau khi gia
tăng............................................................................................................................ 60
Hình 3-10: Kết quả chạy của Apriori và Gia tăng 1 trong trường hợp 1 ..................... 61
Hình 3-11: Kết quả chạy của Apriori và Gia tăng 1 trong trường hợp 1 ..................... 61
Hình 3-12: Kết quả chạy của Apriori và Gia tăng 1 trong trường hợp 3 ..................... 62


7

DANH MỤC BẢNG BIỂU
Bảng 1.1: Ma trận giao tác của cơ sở dữ liệu giao tác T ............................................. 12
Bảng 1.2: Biểu diễn ngang của cơ sở dữ liệu giao tác T ............................................. 12
Bảng 1.3: Biểu diễn dọc của cơ sở dữ liệu giao tác T ................................................. 13
Bảng 3.1: Giải thích tiêu đề ....................................................................................... 57
Bảng 3.2: Bộ cơ sở dữ liệu thứ nhất ........................................................................... 57
Bảng 3.3: Kết quả thu được trên bộ cơ sở dữ liệu thứ nhất ......................................... 57
Bảng 3.4: Bộ cơ sở dữ liệu thứ hai ............................................................................. 58
Bảng 3.5: Kết quả thu được trên bộ cơ sở dữ liệu thứ hai ........................................... 59
Bảng 3.6: Kết quả chạy của Apriori và Gia tăng 1 trong trường hợp 1 ....................... 60
Bảng 3.7: Kết quả chạy của Apriori và Gia tăng 1 trong trường hợp 2 ...................... 61

thuật toán khai phá luật kết hợp trên cơ sở dữ liệu gia tăng theo chiều ngang.
Trong chương này, học viên cũng đề xuất thuật toán cải tiến cấu trúc cây gia
tăng trong thuật toán Gia tăng 2.
 Chương 3: Cài đặt chương trình thử nghiệm. Chương này trình bày về cài đặt
hai thuật toán Apriori và thuật toán Gia tăng 1.Sau đó là phần chạy thử nghiệm
hai thuật toán trên một số cơ sở dữ liệu nhằm đánh giá hai thuật toán trên ba nội
dung: thử nghiệm trên cơ sở dữ liệu ban đầu, thử nghiệm trên cơ sở dữ liệu gia
tăng, thử nghiệm trên cơ sở dữ liệu ổn định với những ngưỡng khai phá khác
nhau. Từ đó rút ra được những so sánh, nhận xét và đánh giá về tính hiệu quả
của thuật toán Gia tăng 1 khi dữ liệu gia tăng.


9

CHƯƠNG 1: KHAI PHÁ LUẬT KẾT HỢP
Nắm được những kiến thức cơ bản về khai phá dữ liệu và những khái
niệm liên quan đến khai phá luật kết hợp như: tập mục dữ liệu, cơ sở
dữ liệu giao tác, biểu diễn của cơ sở dữ liệu giao tác, độ hỗ trợ và độ
tin cậy của tập mục dữ liệu, tập mục thường xuyên, bài toán khai phá
luật kết hợpv.v…Trong phần tiếp theo của chương này, học viên sẽ
trình bày hai thuật toán đầu tiên của khai phá luật kết hợp là AIS và
Apriori.Thuật toán Apriori là một nội dung cơ sở để phục vụ cho nội
dung chính của luận văn.

1.1

Tổng quan về khai phá dữ liệu

Khai phá dữ liệu (Data Mining) là một khái niệm ra đời vào những năm cuối của
thập kỷ 1980. Chúng ta có thể hiểu một cách sơ lược rằng khai phá dữ liệu là quá trình

phân loại dữ liệu thường gồm hai bước: xây dựng mô hình và sử dụng mô hình để
phân loại dữ liệu.
 Bước 1(bước học): Xây dựng mô hình dựa trên việc phân tích các mẫu dữ liệu
cho trước.
 Bước 2 (bước phân loại): Sử dụng mô hình để phân loại dữ liệu.
Phân cụm: Phân cụm dữ liệu là quá trình chia một tập dữ liệu ban đầu vào các
tập con (subsets). Mỗi một tập như vậy gọi là một cụm (cluster). Các phần tử trong
cùng một cụm thì tương tự nhau (similar), các phần tử trong các cụm khác nhau thì sẽ
phi tương tự với nhau (dissimilar). Những phương pháp phân cụm khác nhau có thể sẽ
sinh ra các cụm khác nhau trên cùng tập dữ liệu ban đầu. Phân cụm được sử dụng rộng
rãi trong nhiều ứng dụng như kinh doanh thông minh (business intelligence), nhận
dạng ảnh, tìm kiếm web, sinh học và an ninh,…
Hồi quy: Theo Wikipedia, hồi quy là một phương pháp thống kê mà giá trị kỳ
vọng của một hay nhiều biến ngẫu nhiên được dự đoán dựa vào điều kiện của các biến
ngẫu nhiên (đã tính toán) khác. Cụ thể, có hồi qui tuyến tính, hồi qui lôgic, hồi qui
Poisson và học có giám sát.
Khai phá luật kết hợp: nhằm phát hiện ra những phần tử nào thường hay đi kèm
với nhau.

1.2

Giới thiệu về khai phá luật kết hợp

Khai phá luật kết hợp (Mining association rules) lần đầu được RakeshAgrawal
Agrawal đưa ra vào năm 1993 [5]. Khai phá luật kết hợp là một kỹ thuật được sử dụng
trong khai phá dữ liệu nhằm tìm ra các phần tử thường xuất hiện cùng nhau trong cơ
sở dữ liệu;từ đấyrút ra được các luật về ảnh hưởng của một tập phần tử dẫn đến sự
xuất hiện của tập phần tử khác. Ví dụ, sự xuất hiện của A kéo theo sự xuất hiện của B
nên ta có luật kết hợp (A→B). Dạng luật như vậy được gọi là luật kết hợp và quá trình
tìm ra được các luật kết hợp được gọi là khai phá luật kết hợp. Luật kết hợp là dạng

các luật mô tảcác sựkiện xảy ra đồng thời (một cách thường xuyên) nhưthếnào. Bài
toán khai phá luật kết hợp được chia thành hai bài toán nhỏ:
 Bài toán 1: Tìm các tập mục dữ liệu thường xuyên theo một ngưỡng S0 cho
trước.
 Bài toán 2: Từ các tập mục dữ liệu thường xuyên tìm được ở bài toán 1, tìm các
luật kết hợp thỏa mãn độ tin cậy cho trước.
Bài toán thứ hai là bài toán đơn giản. Hầu hết các nghiên cứu về luật kết hợp tập
trung vào bài toán thứ nhất. Nội dung luận văn này cũng đi sâu vào nghiên cứu một số
thuật toán để tìm các tập mục dữ liệu thường xuyên.

1.3

Một số khái niệm cơ bản [3, 5, 7]

1.3.1

Cơ sở dữ liệu giao tác

Tập hợp các mục dữ liệuI={x1, x2, …, xn} là tập n thuộc tính (mục dữ liệu) riêng
biệt. Mỗi xi ∈ I gọi là một mục dữ liệu (item) hay là một thuộc tính. Ví dụ: I= {bánh
mì, sữa, bỉm,…). Một giao tác chứa một tập con {x , x , … , x } ⊆ I
. Đặt ti =
{x , x , … , x } , ti được gọi là định danh của giao tác{x , x , … , x }.
Một cơ sở dữ liệu giao tác (Transaction Database) trên I là một tập các định
danh giao tác T = {t1, t2,…,tm}, với ti là một định danh giao tác trên Ichứa một tập các
mục dữliệu X ⊆ I. Ví dụ, trong bài toán giỏ hàng, cơ sở dữ liệu giao tác là các lầnmua


12
hàng của mỗi khách hàng, cho biết trong một lần mua hàng, khách hàng mua những


1

0

0

t1

1

1

1

1

1

t2

1

0

1

1

0

t0
t1
t2
t3
t4

Mục dữ liệu
x0, x1, x2
x0, x1, x2, x3, x4
x0, x2, x3
x0, x2, x3, x4
x0, x1, x2, x3

-Biểu diễn dọc: Một cơ sở dữ liệu là danh sách các mục dữ liệu, mỗi một mục dữ liệu


13
có một danh sách tất cả các định danh của giao tác chứa mục dữ liệu này. Như vậy
chúng ta có thể hình dung theo cách này thì các mục dữ liệu được biểu diễn theo chiều
dọc.
Bảng1.3: Biểu diễn dọc của cơ sở dữ liệu giao tác T
Mục dữ liệu
x0
x1
x2
x3
x4

Giao tác
t0, t1, t2, t3, t4

người sử dụng). Tập mục X được gọi là tập mục thường xuyên hay tập mục phổ biến
(Frequent ItemSet hay Large ItemSet) theo độ hỗ trợ tối thiểu minsup khi và chỉ khi
sup(X) ≥ minsup.
Gọi

là tập tất cả các tập mục dữ liệu thường xuyên theo ngưỡng hỗ trợ tối

thiểu S0 của cơ sở dữ liệu giao tác T trên I. Ta có các tính chất sau:
Tính chất 1: Mọi tập con của tập thường xuyên là một tập thường xuyên:
∀ ∈

à∀ ⊆

ℎỏ

⊆

ℎì

∈

Tính chất 2: Mọi tập mục dữ liệu chứa một tập con không thường xuyên thì là
một tập không thường xuyên:


14
∀ ∉

à∀ ⊆


sup(x0x1→ x2) = sup(x0x1x2) = 3
sup(x0→ x4) = sup(x0x4) = 2
Luật kết hợp A→ B là thường xuyên theo ngưỡng S0 nếu sup(A→ B) ≥ S0. Ở ví
dụ trên, với S0 = 2, luật sup(x0→ x1), sup(x0x1→ x2) là luật thường xuyên theo ngưỡng
hỗ trợ S0.
Ý nghĩa của độ hỗ trợ: độ hỗ trợ mang ý nghĩa thống kê của luật. Nói rằng độ hỗ
trợ của luật A→ B là 20 nghĩa là có 20 giao tác chứa {AB}.
Độ tin cậy (Confidence) của luật A→ Blà tỷ lệ giữa số lượng các giao dịch trong
T chứa A ∪ và số giao dịch chứa A:
( → ) =
( )/
( ).
Luật kết hợp → được gọi là luật tin cậy (confidence rule) theo ngưỡng S0 và
( → )≥
C0 nếu → là luật thường xuyên theo ngưỡng S0và
ớ 0

bơ, sữa
trứng, sữa
bánh mì, bơ, trứng
bánh mì, bơ, sữa
bơ, trứng, sữa
bánh mì, bơ, trứng, sữa

Độ hỗ trợ
50%
100%
50%
25%
50%
25%
0%
50%
25%
25%
25%
0%
25%
0%

Từ đó, ta tìm được tập mục thường xuyên là (bánh mì, bơ), (bơ, trứng), ta tính
được độ tin cậy của các luật kết hợp thường xuyên.


16
Luật kết hợp
bánh mì → bơ


1.4.1

Thuật toán AIS

Thuật toán AIS [5] là thuật toán đầu tiên được đề xuất cho khai phá luật kết hợp.
Nội dung cơ bản của thuật toán AIS:
 Duyệt cơ sở dữ liệu lần thứ nhất để tính độ hỗ trợ của từng mục dữ liệu, lấy ra
tập L1 gồm những mục dữ liệu có độ hỗ trợ ≥ngưỡng hỗ trợ tối thiểu S0 cho
trước.
 Từ L1 (là tập 1 mục dữ liệu thường xuyên), tìm C2 là tập ứng viên có 2 mục dữ
liệu bằng cách: duyệt từng giao tác, ghép từng cặp mục dữ liệu có trong giao tác
thành tập ứng viên. Ứng với mỗi tập ứng viên, duyệt lại cơ sở dữ liệu để đếm số
giao tác có chứa tập mục này để tính độ hỗ trợ và thu được tập các tập thường
xuyên có 2 mục dữ liệu.


17
 Lặp lại, tìm được tập mục ứng viên có k phần tử từ những tập mục dữ liệu k
phần tử lấy từ các phần tử trong giao tác. Tiếp tục cho đến khi tập những tập
mục dữ liệu thường xuyên có k+1 phần tử là rỗng.
Ví dụ: chạy thuật toán AIS với độ hỗ trợ tối thiểu S0 = 3 và cơ sở dữ liệu như
sau:
t0
t1
t2
t3
t4

x0

0
1
0

Ta có các bước khi chạy thuật toán AIS như sau:
Bước 1:
Mục dữ liệu
x0
x1
x2
x3
x4

Độ hỗ trợ
5
3
5
4
2

L1
x0
x1
x2
x3

Bước 2:
Mục dữ liệu
x0 x1
x0 x2

x0 x1 x2
x0 x1 x3
x0 x1 x4
x1 x2 x3
x1 x2 x4
x2 x3 x4
x0 x2 x3
x0 x2 x4

Độ hỗ trợ
3
2
1
2
1
2
2
2

L3
x0 x1 x 2

Độ hỗ trợ
2
1
2
1

L4
∅

for ( k = 2; Lk-1 Ø; k++ ) do begin
Ck = apriori-gen(Lk-1); // sinh ra tập ứng viên Ck
forall transactions tTdo begin
Ct = subset(Ck, t); // những tập ứng viên nằm trong t
forall candidates cCtdo
c.count++;
endfor;
Lk = {cCk | c.count  minsup}
Endfor;
Answer = kLk;

Hàm apriori_gen
Input: Lk-1
Output: Ck
Method:
Ck = ∅ ;
For each (p, q) in Lk-1
If p.item1 = q.item1, …, p.itemk – 2 = q.itemk – 2 and p.itemk – 1 q.itemk – 1
Ck = Ck ∪ {p.item1, p.item2, …, p.itemk – 1, q.itemk – 1};
forall itemsets c Ckdo
forall (k – 1)-subsets s of c do
if (s Lk – 1) thendelete c from Ck;
enfor;
endfor;
endfor;

Ví dụ: Chạy thuật toán Apriori với cơ sở dữ liệu T sau:

t0


1

1

t2

1

0

1

1

0

t3
t4

1
1

0
1

1
1

1
1

x1 x2
x1 x3
x2 x3

C2
x0 x1
x0 x2
x0 x3
x1 x2
x1 x3
x2 x3

Độ hỗ trợ
3
4
4
3
2
4

L2
x0 x1
x0 x2
x0 x3
x1 x2
x2 x3

C3
x0 x1 x2



Mở đầu

Khai phá luật kết hợp là một lĩnh vực được nhiều người quan tâm và có nhiều kết
quả công bố. Tuy nhiên những thuật toán khai phá luật kết hợp này có một đặc điểm là
chỉ khai phá trên cơ sở dữ liệu tĩnh, nghĩa là số lượng các giao tác trong cơ sở dữ liệu
là ổn định, không có sự biến động. Trên thực tế, số lượng các giao tác tăng lên hằng
giờ, hằng ngày. Một cơ sở dữ liệu mà các giao tác (hoặc các mục dữ liệu) tăng lên theo
thời gian như vậy được gọi là cơ sở dữ liệu gia tăng hoặc cơ sở dữ liệu tăng trưởng
(incremental database).Do đó, các tập mục thường xuyên và các luật kết hợp đã được
tính toán không còn giá trị trên tập dữ liệu mới. Khi đó phải tiến hành lại công việc từ
đầu trên cơ sở dữ liệu sau khi gia tăng. Chương này tập trung đi sâu vào vào hai thuật
toán khai phá luật kết hợp trên cơ sở dữ liệu gia tăng:
 Thuật toán xử lý dữ liệu gia tăng theo chiều dọc [2,3]
 Thuật toán xử lý dữ liệu gia tăng theo chiều ngang[1,3]

2.2

Thuật toán xử lý dữ liệu gia tăng theo chiều dọc - Thuật toán
Gia tăng 1

2.2.1

Ý tưởng thuật toán

Thuật toán khai phá cơ sở dữ liệu gia tăng theo chiều dọc còn được gọi là Thuật
toán Gia tăng 1. Cơ sở dữ liệu theo chiều dọc là biểu diễn của cơ sở dữ liệu giao tác
trong đó các giao tác được biểu diễn theo từng giao tác (xem mục 1.1.3). Theo thời
gian, các giao tác mới sẽ được thêm vào cơ sở dữ liệu giao tác (chú ý rằng các mục dữ
liệu là vẫn giữ nguyên, không tăng thêm). Khi đó thuật toán sẽ tìm được tất cả các tập


= {X | (X, Sup) ∈ SC và Sup ≥ S0}
Sau đó nếu cần tìm các tập thường xuyên theo ngưỡng S1, có hai khả năng xảy
ra:
Nếu S1≥ S0 thì chỉ cần lọc trong SC những (X, Sup) thỏa

-

⊆
-

≤

Nếu

⊆

⇒
∉

,

⇒

= { |( ,

)∈

,


3. Tìm các tập mục ứng viên. Tính độ hỗ trợ của các tập mục ứng viên.


23
4. Từ các tập mục ứng viên, lấy ra được những tập mục có độ hỗ trợ lớn hơn hoặc
bằng ngưỡng hỗ trợ cho trước.
2.2.2

Chuyển đổi cơ sở dữ liệu sang chiều dọc

Cơ sở dữ liệu giao tác ban đầu gồm có m giao dịch T = {t1, t2, …, tm} trên tập
mục dữ liệu I = {x1, x2, …, xn}. Gọi tid là số thứ tự của t trong T mà ta gọi là định danh
của giao tác t. Khi đó, PT = {tid | t ∈ T} = {1,2, …,m}.
Thủ tụcVerticalxây dựng n tập hợp {P1, P2, …,Pn} với Pilà tập hợp tất cả các định
danh của các giao tác chứa xitrong T: Pi = {tid ∈ PT | xi ∈ t}. Như vậy Sup(xi) = ||Pi||.
Thủ tục Verticalchuyển đổi cơ sở dữ liệu ban đầu sang thành tập các giao dịch
P={P1, P2, …,Pn}như sau:
Thủ tục Vertical(T, P);
Input:
- T = {t1, t2, …, tm}: cơ sở dữ liệu giao tác trên I = {x1, x2, …, xn};
Output:
- P = {P1, P2, …,Pn} với Pi = {

,

,…,

};

Method:


x3
1
1
1
1
1

x4
0
1
1
1
1

x5
0
1
0
1
0

Trích đoạn Mô tả chương trình chạy

---