Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CNTT&TT

ĐỖ THỊ HẢI YẾN
KHAI PHÁ TẬP MỤC LỢI ÍCH CAO
TRONG CƠ SỞ DỮ LIỆU LỚN LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
TRONG CƠ SỞ DỮ LIỆU LỚN

CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH
MÃ SỐ: 60 48 01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

HƢỚNG DẪN KHOA HỌC: PGS.TS. NGUYỄN THANH TÙNG THÁI NGUYÊN - 2011

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

LỜI CAM ĐOAN

Tôi xin cam đoan Luận văn "Khai phá tập mục lợi ích cao trong cơ sở dữ liệu
lớn" là công trình nghiên cứu của riêng tôi dưới sự hướng dẫn của PGS.TS Nguyễn

khích tôi trong cuộc sống và trong công việc.
Tôi xin chân thành cảm ơn!

Thái Nguyên, ngày 30 tháng 9 năm 2011

Tác giả
Đỗ Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
i
MỤC LỤC
Trang
Trang bìa phụ
Lời cảm ơn
Lời cam đoan
Mục lục i
Danh mục các từ, các ký hiệu viết tắt iii
Danh mục các bảng iv
Danh mục các hình v
LỜI MỞ ĐẦU 1
Chƣơng 1. KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU VÀ BÀI TOÁN KHAI
PHÁ TẬP MỤC THƢỜNG XUYÊN 4

3.2.5. Khai phá tương tác với cây TWU-tree 59
3.3. Kết luận chương 3 60
KẾT LUẬN 62
TÀI LIỆU THAM KHẢO 64

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
iii

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

STT
Cụm từ viết tắt
Nghĩa của cụm từ viết tắt
1
CNTT
Công nghệ thông tin
2
CSDL
Cơ sở dữ liệu
3
KDD
Khám phá tri thức trong cơ sở dữ liệu
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
iv
DANH MỤC CÁC BẢNG
Trang
Bảng 1.1: Biểu diễn ngang của cơ sở dữ liệu giao tác 9

Hình 2.3. Không gian tìm kiếm tập mục lợi ích cao theo thuật toán UMining-H 33
Hình 2.4. Không gian tìm kiếm tập mục lợi ích cao theo thuật toán HUMining 39
Hình 3.1: Cây TWUI-tree sau khi lưu thao tác T1. 47
Hình 3.2: Cây TWUI-tree sau khi lưu thao tác T1 và T2. 47
Hình 3.3: Cây TWUI-tree của cơ sở dữ liệu bảng 3.1 và 3.2. 47
Hình 3.4: Cây C-COUI-tree sau khi lưu mẫu CBE 49
Hình 3.5: Cây C-COUI-tree sau khi lưu mẫu CBE và CE 50
Hình 3.6: Cây C-COUI-tree sau khi xây dựng xong. 50
Hình 3.8: Cây B-COUI-tree 51
Hình 3.9: Các bước khai phá cây D-COUI-tree. 52 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
1

LỜI MỞ ĐẦU

Trong những năm gần đây, cùng với sự phát triển vượt bậc của công nghệ
thông tin, truyền thông, khả năng thu thập và lưu trữ thông tin của các hệ thống thông
tin không ngừng được nâng cao. Với lượng dữ liệu khổng lồ và luôn gia tăng theo
thời gian, rõ ràng các phương pháp phân tích dữ liệu truyền thống sẽ không còn hiệu
quả, gây tốn kém và dễ dẫn đến những kết quả sai lệch. Để có thể khai thác hiệu quả
các cơ sở dữ liệu lớn, một lĩnh vực khoa học mới đã ra đời: Khám phá tri thức trong
cơ sở dữ liệu (Knowledge Discovery in Databases – KDD). Khai phá dữ liệu (Data
Mining) là một công đoạn chính trong qúa trình khám phá tri thức, nhằm tìm kiếm,
phát hiện các tri thức mới, hữu ích tiềm ẩn trong các cơ sở dữ liệu lớn.
Khai phá luật kết hợp là một nhiệm vụ quan trọng của khai phá dữ liệu. Bài
toán truyền thống (hay còn gọi bài toán nhị phân) khai phá luật kết hợp do R.
Agrawal, T. Imielinski và A. N. Swami đề xuất và nghiên cứu lần đầu tiên vào năm
1993 khi phân tích các cơ sở dữ liệu của các siêu thị. Mục tiêu của nó là phát hiện

thuật toán này là tính chất Apriori hay còn gọi là tính chất phản đơn điệu (anti
monotone) của tập mục thường xuyên. Đó là tập con khác rỗng của một tập mục
thường xuyên phải là tập thường xuyên. Điều này có nghĩa các (k+1)-tập mục
thường xuyên chỉ có thể sinh ra từ các k-tập mục thường xuyên. Tính chất Apriori
cho phép loại bỏ được phần lớn các tổ hợp mục không thường xuyên ra khỏi không
gian tìm kiếm tại mỗi bước.
Đáng tiếc là ràng buộc lợi ích cao không thỏa mãn tính chất Apriori. Do đó,
việc tìm kiếm, phát hiện tập mục lợi ích cao không thể thực hiện được như trong
khai phá tập mục thường xuyên. Cần phải nghiên cứu tìm ra những thuật toán hiệu
quả cho việc phát hiện tập mục lợi ích cao. Trong những năm gần đây, vấn đề này
đã và đang thu hút sự quan tâm của nhiều nhà nghiên cứu trong và ngoài nước.
Đã có một số thuật toán phát hiện tập mục lợi ích cao được đề xuất. Các thuật
toán này có thể phân thành hai loại:
- Thuật toán kiểu Apriori (Apriori-like) sinh ứng viên, duyệt theo chiều rộng.
- Thuật toán kiểu FP-growth không sinh ứng viên, chuyển đổi cơ sở dữ liệu
thành cấu trúc cây, duyệt đệ quy theo chiều sâu.
Luận văn của học viên nhằm nghiên cứu vấn đề khai phá tập mục lợi ích cao
trong cơ sở dữ liệu lớn. Nội dung chính của luận văn gồm ba chương.
Chương 1: Trình bày khái quát về khai phá dữ liệu, bài toán khai phá tập mục
thường xuyên với hai thuật toán quan trọng làm cơ sở cho việc trình bày nội dung
hai chương tiếp theo.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
3
Chương 2: Phát biểu bài toán và trình bày ba thuật toán khai phá tập mục lợi
ích cao kiểu Apriori. Đó là các thuật toán UMining , UMining-H và HUMining.
Chương 3: Trình bày thuật toán kiểu FP-growth, được cho là hiệu quả nhất
hiện nay, thuật toán COUI-Mine.

Thái nguyên, tháng 09 năm 2011.

công cụ phân tích dữ liệu truyền thống.
Tuy mới ra đời khoảng 20 năm, nhưng khai phá dữ liệu là lĩnh vực khoa học
phát triển vô cùng nhanh chóng. Do sự phát triển nhanh chóng cả về phạm vi áp
dụng lẫn các phương pháp tìm kiếm tri thức, đã có nhiều quan điểm khác nhau về
khai phá dữ liệu. Tuy nhiên, ở một mức độ trừu tượng nhất định, chúng ta định
nghĩa khai phá dữ liệu như sau [9]:
Khai phá dữ liệu là quá trình tìm kiếm, phát hiện các tri thức mới, hữu ích
tiềm ẩn trong cơ sở dữ liệu lớn.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
5
Khám phá tri thức trong CSDL (Knowledge Discovery in Databases – KDD)
là mục tiêu chính của khai phá dữ liệu, do vậy hai khái niệm khai phá dữ liệu và
KDD được các nhà khoa học xem là tương đương nhau. Thế nhưng, nếu phân chia
một cách chi tiết thì khai phá dữ liệu là một bước chính trong quá trình KDD.
Khám phá tri thức trong CSDL là lĩnh vực liên quan đến nhiều ngành như: Tổ
chức dữ liệu, xác suất, thống kê, lý thuyết thông tin, học máy, CSDL, thuật toán, trí
tuệ nhân tạo, tính toán song song và hiệu năng cao, Các kỹ thuật chính áp dụng
trong khám phá tri thức phần lớn được thừa kế từ các ngành này.
Quá trình khám phá tri thức có thể phân thành các công đoạn sau [9]:
 Lựa chọn dữ liệu: Là bước tuyển chọn những tập dữ liệu cần được khai phá
từ các tập dữ liệu lớn (databases, data warehouses, data repositories) ban
đầu theo một số tiêu chí nhất định.
 Tiền xử lý dữ liệu: Là bước làm sạch dữ liệu (xử lý dữ liệu thiếu, dữ liệu
nhiễu, dữ liệu không nhất quán, ), tổng hợp dữ liệu, rời rạc hóa dữ liệu,
Biến đổi dữ liệu. Đây được xem là bước quan trọng và tiêu tốn thời gian
nhất của toàn bộ quá trình KDD. Sau bước tiền xử lý này, dữ liệu sẽ nhất
quán, đầy đủ, được rút gọn và rời rạc hóa.
 Khai phá dữ liệu: Là bước áp dụng những kỹ thuật phân tích (phần nhiều là
các kỹ thuật học máy) nhằm khai thác dữ liệu, trích lọc những mẫu tin

lớp các bệnh nhân, Hướng tiếp cận này thường sử dụng một số kỹ thuật

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
7
của học máy như cây quyết định (decision tree), mạng nơ-ron nhân tạo
(neural network),
 Phân cụm (clustering/segmentation): Là việc xếp các đối tượng theo từng
cụm tự nhiên.
 Luật kết hợp (association rules): Là việc phát hiện các luật biểu diễn tri
thức dưới dạng đơn giản. Ví dụ: “70% nữ giới vào siêu thị mua phấn thì
có tới 80% trong số họ cũng mua thêm son”.
 Phân tích hồi quy (regression analysis): Là việc học một hàm ánh xạ một
bộ dữ liệu thành một giá trị thực của đại lượng cần dự đoán. Bài toán phân
tích hồi quy tương tự như bài toán phân lớp, điểm khác nhau là ở chỗ đại
lượng cần dự đoán là liên tục chứ không phải rời rạc như nhãn lớp.
 Phân tích các mẫu theo thời gian (sequential/temporal patterns): Tương tự
như khai phá luật kết hợp nhưng có quan tâm đến tính thứ tự theo thời gian.
 Mô tả khái niệm và tổng hợp (concept description and summari-zation):
Thiên về mô tả, tổng hợp và tóm tắt các khái niệm. Ví dụ tóm tắt văn bản.
Hiện nay, các kỹ thuật khai phá dữ liệu có thể làm việc với rất nhiều kiểu dữ
liệu khác nhau. Một số dạng dữ liệu điển hình là: CSDL quan hệ, CSDL giao tác,
CSDL quan hệ hướng đối tượng, dữ liệu không gian và thời gian, CSDL đa phương
tiện, dữ liệu văn bản và web,
Cho đến nay, khai phá dữ liệu đã và đang được ứng dụng rộng rãi trong nhiều
lĩnh vực như: Phân tích dữ liệu hỗ trợ ra quyết định, Y học, Tin-sinh học
(Bioinformatics), thương mại, tài chính, bảo hiểm, text mining, Rất nhiều tổ
chức và công ty lớn trên thế giới đã và đang áp dụng thành công các kỹ thuật khai
phá dữ liệu vào hoạt động sản xuất, kinh doanh của mình và thu được những lợi ích
to lớn. Các công ty phần mềm lớn trên thế giới cũng rất quan tâm tới việc nghiên
cứu và phát triển kỹ thuật khai phá dữ liệu: Oracle đã tích hợp các công cụ khai phá

1
, i
2
, , i
n
}. Một giao tác
(transaction) T là một tập con của I,
T

I
Cơ sở dữ liệu giao tác là tập các giao tác
DB ={ T
1
, T
2
, , T
m
}. Mỗi giao tác được gán một định danh TID. Một tập mục con
X
I
,, gồm k mục phân biệt được gọi là một k –tập mục. Giao tác T gọi là chứa tập
mục X nếu X
T
.
Biểu diễn cơ sở dữ liệu giao tác: cơ sở dữ liệu giao tác thường được biểu
diễn ở dạng biểu diễn ngang, biểu diễn dọc và biểu diễn bởi ma trận giao tác.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
9
Biểu diễn ngang: Cơ sở dữ liệu là một danh sách các giao tác. Mỗi giao tác

Bảng 1.2: Biểu diễn dọc của cơ sở dữ liệu giao tác
Mục dữ liệu
Định danh giao tác
A
T3, T6, T7, T8, T9, T10, T11
S
T1, T2, T3, T7, T9, T11
C
T1, T2, T4, T5, T6, T7, T8, T11
D
T1, T2, T3, T4, T5
E
T9, T10
F
T4, T7

Ma trận giao tác: Cơ sở dữ liệu giao tác
 
n
TTTDB , ,,
1

trên tập các mục
 
n
iiiI , ,,
21

được biểu diễn bởi ma trận nhị phân
mxnpq

C
D
E
F
T1
0
1
1
1
0
0
T2
0
1
1
1
0
0
T3
1
1
0
1
0
0
T4
0
0
1
1

T9
1
1
0
0
1
0
T10
1
0
0
0
1
0
T11
1
1
1
0
0
0

1.2.2. Tập mục thƣờng xuyên và luật kết hợp
Định nghĩa 1.2: Cho tập mục
IX 
. Ta gọi độ hỗ trợ (Support) của X trong cơ sở
dữ liệu giao tác DB, ký hiệu sup(X), là tỷ lệ các giao tác chứa X trên tổng số các
giao tác trong DB, tức là:
 
sup( ) .

sup(
YX 
), là độ hỗ trợ của tập mục
YX 
,
)sup()sup( YXYX 
.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
11
Như vậy độ hỗ trợ của luật kết hợp
YX 
chính là xác suất
)( YXP 
của
sự xuất hiện đồng thời của X và Y trong một giao tác.
Ta có:
1)sup(0  YX
.
Định nghĩa 1.6: Độ tin cậy (Confidence) của một luật
YX 
, ký hiệu
 
YXconf 
, là tỷ lệ phần trăm giữa số giao tác chứa
YX 
và số giao tác chứa X
trong cơ sở dữ liệu DB.
sup( )
()

/









và ta có
0 ( ) 1.conf X Y  

Các luật thoả mãn cả hai ngưỡng độ hỗ trợ tối thiểu (minsup) và độ tin cậy
tối thiểu (minconf), tức thoả mãn
sup( )X Y minsup
và
 
conf X Y

minconf
, được gọi là luật kết hợp mạnh.
Tính chất cơ bản của tập mục thƣờng xuyên:
Cho cơ sở dữ liệu giao tác DB và ngưỡng độ hỗ trợ tối thiểu minsup. Các tập
mục thường xuyên có các tính chất sau:
(1) Nếu X, Y là các tập mục và
YX 
thì
   
sup supXY

thường xuyên, ta sinh ra các luật kết hợp bằng cách tìm
XY 
, kiểm tra độ tin cậy
của luật
YYX \
có thoả mãn độ tin cậy tối thiểu không. Bài toán thứ hai này đơn
giản, mọi khó khăn nằm ở bài toán thứ nhất, hầu hết các nghiên cứu về luật kết hợp
đều tập trung giải quyết bài toán thứ nhất là tìm các tập mục thường xuyên.
Phần tiếp theo sau đây sẽ trình bày chi tiết về khai phá tập mục thường xuyên.
1.3. Các cách tiếp cận khai phá tập mục thƣờng xuyên
Các nghiên cứu về khai phá tập mục thường xuyên tập trung vào tìm các
thuật toán mới hoặc đề xuất giải pháp nâng cao hiệu quả các thuật toán đã có.
Đã có rất nhiều thuật toán tìm tập mục thường xuyên được công bố, 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 và duyệt theo chiều sâu.
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 mục ứng
viên có k mục. Với cơ sở dữ liệu có n mục dữ liệu, lần lặp thứ k phải kiểm tra độ hỗ
trợ của tất cả
)!(!
!
knk
n
C
k
n


ra bằng cách kết nối các tập mục thường xuyên có (k-1) mục và loại bỏ tập mục ứng
viên nếu nó có chứa bất kỳ một tập con nào không phải là thường xuyên.
Giả sử các mục dữ liệu trong mỗi giao tác được lưu theo trật tự từ điển.
Thuật toán sử dụng các ký hiệu sau đây:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
14
Tập k
mục
Chức năng
L
k
Tập các k–tập mục thường xuyên (với độ hỗ trợ tối thiểu minsup)
Mỗi phần tử của tập này có 2 trường:
i) Tập mục (itemset)
ii) Độ hỗ trợ (count)
C
k
Tập các k – tập mục ứng viên (các tập mục thường xuyên tiềm năng)
Mỗi phần tử của tập này có 2 trường:
i) Tập mục (itemset)
ii) Độ hỗ trợ (count)

Thuật toán duyệt cơ sở dữ liệu nhiều lần. Mỗi lần duyệt, thuật toán thực hiện
hai bước; bước kết nối và bước tỉa. Trong lần lặp thứ k, thuật toán nối hai (k-1) –
tập mục để sinh ra k – tập mục, sử dụng tính chất Apriori để tỉa các tập ứng viên.
Bước kết nối và bước tỉa như sau:
Bƣớc kết nối (tìm C
k
): Tập các k – tập mục ứng viên C

và l
2
là: l
1
[1] l
1
[2]… l
1
[k-2] l
1
[k-1] l
2
[k-1].
Bƣớc tỉa: Tập C
k
chứa tập L
k
, tức là tất cả các k – tập mục thường xuyên đều
thuộc tập C
k
. Tập C
k
có thể rất lớn dẫn đến khối lượng tính toán lớn. Thuật toán áp
dụng tính chất Apriori để rút gọn tập C
k
. Nếu có một (k-1) – tập mục con nào đó
của k – tập mục ứng viên mà không có mặt trong L
k-1
thì ứng viên đó không thể là
thường xuyên, có thể loại bỏ khỏi C

DBT 
) do begin
(5) C=subset(C
k
,T); // Các tập mục ứng viên chứa trong T
(6) For (each
Cc
)
(7) c.count++; // tăng số đếm c lên một đơn vị
(8) end;
(9)
 
;supmin./  countcCcL
kk

(10) End;
(11)
;
k
LL 

Sinh các tập mục ứng viên của thuật toán Apriori: hàm Apriori_gen()
Function Apriori_gen()
Input: Tập các (k-1)- tập mục thường xuyên L
k-1

Output: Tập các k- tập mục ứng viên C
k
Method:
// Bước kết nối

2
[k-1])
then
(4) C
k
← { l
1
[1], l1[2], … l
1
[k-2],l
1
[k-1] l
2
[k-1]};
// kết nạp k-tập mục mới vào Ck
// Bước tỉa
(5) For (each c
i

C
k
) do

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
16
(6) If exist (s

c
i
) and (s

Trích đoạn Thuật toán FP-growth Thuật toán hai pha HUMining Nhận xét thuật toán COUI-Mine

---