1
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
VÀ TRUYỀN THÔNG

BẾ QUANG HUẤN

NGHIÊN CỨU MỘT SỐ THUẬT TOÁN KHAI PHÁ TẬP
MỤC THƢỜNG XUYÊN VÀ TẬP MỤC CỔ PHẦN CAO
TRONG CƠ SỞ DỮ LIỆU
Chuyên nghà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
Ngƣời hƣớng dẫn khoa học: GS. TS Vũ Đức Thi THÁI NGUYÊN 2012

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vni
LỜI CAM ĐOAN
Tôi xin cam đoan toàn bộ nội dung trong Luận văn hoàn toàn theo đúng
nội dung đề cƣơng cũng nhƣ nội dung mà cán bộ hƣớng dẫn giao cho. Nội dung
luận văn, các phần trích lục các tài liệu hoàn toàn chính xác. Nếu có sai sót tôi
hoàn toàn chịu trách nhiệm.


1.3 KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN 14
1.3.1 Các cách tiếp cận khai phá tập mục thƣờng xuyên 14
1.3.2 Thuật toán Apriori 16
1.3.3 Thuật toán FP-growth 22
1.4 MỞ RỘNG BÀI TOÁN KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN 31
1.5 KẾT LUẬN CHƢƠNG 1 33
Chƣơng 2 KHAI PHÁ TẬP MỤC CỔ PHẦN CAO 34
2.1 GIỚI THIỆU 34
2.2 BÀI TOÁN KHAI PHÁ TẬP MỤC CỔ PHẦN CAO 35
2.3 THUẬT TOÁN FSM 41
2.3.1 Cở sở lý thuyết của thuật toán FSM 41
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vniii
2.3.2 Thuật toán FSM 42
2.3.3 Nhận xét thuật toán FSM 44
2.4 THUẬT TOÁN AFSM 45
2.4.1 Cơ sở lý thuyết của thuật toán AFSM 45
2.4.2 Thuật toán AFSM 52
2.4.3 Đánh giá thuật toán AFSM 59
2.5 KẾT LUẬN CHƢƠNG 2 60
Chƣơng 3 THỰC NGHIỆM VÀ ĐÁNH GIÁ THUẬT TOÁN 61
3.1 ĐẶT BÀI TOÁN 61
3.2 THIẾT KẾ MODUL CHƢƠNG TRÌNH VÀ GIẢI THUẬT 62
3.3 GIAO DIỆN SỬ DỤNG VÀ CHỨC NĂNG CHƢƠNG TRÌNH 67
3.4 ĐÁNH GIÁ KẾT QUẢ VÀ HƢỚNG PHÁT TRIỂN CỦA CHƢƠNG
TRÌNH 70
KẾT LUẬN 72
TÀI LIỆU THAM KHẢO 73

db
Cơ sở dữ liệu giao tác con của DB, db

DB
i
p

Mục dữ liệu thứ p
T
q
Giao tác thứ q
n
Số mục dữ liệu một cơ sở dữ liệu giao tác
m
Số giao tác của một cơ sở dữ liệu giao tác
A, B, C,…
Tên các mục dữ liệu trong cơ sở dữ liệu giao tác
X, Y,…
Tập con của tập mục dữ liệu I, X, Y

I
X=ABC
Thay cho X={A,B,C} trong các cơ sở dữ liệu giao tác
minsup
Ngƣỡng độ hỗ trợ
minShare
Ngƣỡng cổ phần tối thiểu
minconf
Ngƣỡng độ tin cậy tối thiểu
X
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vnvi
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 1.1: Phân loại các thuật toán khai phá tập mục thƣờng xuyên 15
Hình 1.2: Cây FP-tree của CSDL bảng 1.5 28
Hình 1.3: Cây COFI-tree của mục D 28
Hình 1.4: Các bƣớc khai phá cây D-COFI-tree 31
Hình 2.1: Không gian tìm kiếm tập mục cổ phần cao theo thuật toán AFSM 58
Hình 3.1: Giao diện chính của chƣơng trình demo 63
Hình 3.2: Giao diện hiển thị bảng dữ liệu 64
Hình 3.3: Giao diện cập nhật ngƣỡng cổ phần và ngƣỡng tin cậy cho bảng dữ
liệu 65
Hình 3.4: Giao diện hiển thị kết quả tìm tập mục cổ phần cao 66

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn1
MỞ ĐẦU
Một trong những ứng dụng quan trọng nhất của công nghệ thông tin trong
đời sống là giúp giải quyết các bài toán quản lý. Kể từ khi máy tính điện tử trở
thành một công cụ lao động quan trọng thì một trong những nhu cầu đầu tiên là
lƣu trữ, tìm kiếm và xử lý số liệu thống kê. Đến nay, các cơ sở dữ liệu đã trở nên
khổng lồ và ngƣời ta mong muốn kho dữ liệu đó cần đƣợc khai thác hiệu quả
hơn trên nhiều bình diện. Trong những năm gần đây, khai phá dữ liệu (Data
mining) đã trở thành một trong những hƣớng nghiên cứu lớn nhất của lĩnh vực

hợp đã đƣợc các nhóm nghiên cứu tại Viện Công nghệ Thông tin thuộc Viện
Khoa học và Công nghệ Việt Nam, các nhóm nghiên cứu tại một số trƣờng đại
học nhƣ Đại học Quốc gia Hà Nội, Đại học Bách Khoa Hà Nội, Đại học Quốc
gia thành phố Hồ Chí Minh thực hiện và đã có nhiều kết quả đƣợc công bố.
Với mục đích đóng góp vào lĩnh vực nghiên cứu này, tôi đã chọn đề tài
luận văn: “ Nghiên cứu một số thuật toán khai phá tập mục thường xuyên
và tập mục cổ phần cao trong cơ sở dữ liệu” làm chủ đề nghiên cứu của
mình.
Mục đích của luận văn là phát triển một số thuật toán khai phá tập mục cổ
phần cao trong cơ sở dữ liệu giao tác cỡ lớn. Trên cơ sở đó áp dụng vào một bài
toán cụ thể là cài đặt trƣơng trình
Với mục tiêu đó, luận văn đƣợc trình bày trong ba chƣơng:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn3
Chương 1: Khai phá tập mục thƣờng xuyên và một số mở rộng
Trình bày bài toán khai phá tập mục thƣờng xuyên: Các khái niệm cơ bản
và các mô hình khai phá. Sau khi trình bày khái quát các thuật toán khai phá,
trong trƣơng trình bày chi tiết hai thuật toán tiêu biểu cho hai cách tiếp cận khác
nhau là thuật toán Apriori và thuật toán FP-growth. Thuật toán Apriori tiêu biểu
cho phƣơng pháp sinh ra các tập mục ứng viên rồi duyệt cơ sở dữ liệu để tính độ
hỗ trợ của nó. Thuật toán FP-growth là thuật toán đầu tiên giới thiệu cấu trúc cây
FP-tree nén toàn bộ các giao tác của cơ sở dữ liệu lên cây với 2 lần duyệt, sau đó
khai phá theo phƣơng pháp phát triển dần các mẫu ở trên cây mà không cần
duyệt cơ sở dữ liệu nữa. Bên cạnh đó luận văn đã trình bày chi tiết phƣơng pháp
COFI-tree khai phá cây FP-tree thay cho phƣơng pháp FP-growth.
Chương 2: Khai phá tập mục cổ phần cao
Trình bày mô hình khai phá cổ phần cao, giới thiệu thuật toán FSM là

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn5
Chƣơng 1
KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN VÀ MỘT SỐ MỞ RỘNG
1.1 MỞ ĐẦU
Khai phá tập mục thƣờng xuyên đóng vai trò quan trọng trong nhiều
nhiệm vụ khai phá dữ liệu. Khai phá tập mục thƣờng xuyên xuất hiện nhƣ là bài
toán con của nhiều lĩnh vực khai phá dữ liệu nhƣ khám phá luật kết hợp, khám
phá mẫu tuần tự, phân tích tƣơng quan, phân lớp, phân cụm dữ liệu, khai phá
Web,… Bài toán khai phá tập mục thƣờng xuyên đƣợc giới thiệu lần đầu bởi
Agrawal vào năm 1993 khi phân tích cơ sở dữ liệu bán hàng siêu thị trong mô
hình của bài toán khai phá luật kết hợp. Khai phá luật kết hợp là phát hiện những
mối quan hệ giữa các giá trị dữ liệu trong cơ sở dữ liệu, các mối quan hệ đó
chính là các luật kết hợp.
Khai phá luật kết hợp có hai bƣớc: Bƣớc thứ nhất, tìm các tập mục
thƣờng xuyên thỏa mãn ngƣỡng độ hỗ trợ tối thiểu minsup cho trƣớc, bƣớc thứ
hai, từ các tập mục thƣờng xuyên tìm đƣợc, sinh ra các luật kết hợp thỏa mãn
ngƣỡng độ tin cậy minconf cho trƣớc. Mọi khó khăn của bài toán khai phá luật
kết hợp tập trung ở bƣớc thứ nhất, đó là khai phá tất cả các tập mục thƣờng
xuyên thỏa mãn ngƣỡng độ cho trƣớc.
Kể từ khi Agrawal đề xuất, khai phá tập mục thƣờng xuyên đã thu hút
đƣợc sự quan tâm của nhiều nhà nghiên cứu, đã có hàng trăm kết quả nghiên cứu
đƣợc công bố giới thiệu các thuật toán mới hay đề xuất các giải pháp nâng cao
hiệu quả các thuật toán đã có. Tâp mục thƣờng xuyên đã có vai trò quan trọng
trong nhiều ứng dụng thực tế nhƣ quản lý quan hệ khách hàng, nâng cao hiệu

trò khác nhau cũng nhƣ không dựa vào các đặc tính dữ liệu vốn có của các thuộc
tính mà chỉ dựa vào sự xuất hiện cùng lúc của chúng.
Phần tiếp sau đây nêu một số khái niệm cơ bản và phát biểu bài toán khai
phá luật kết hợp, bài toán đầu tiên dẫn đến bài toán khai phá tập mục thƣờng
xuyên.
1.2.1 Cơ sở dữ liệu giao tác
Định nghĩa 1.1:
i
gdfg
Cho tập các mục (item) I={i
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à một 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
X nếu X

A, C
T7
A, B, C, F
T8
A, C
T9
A, B, E
T10
A, E
T11
A, B, C

Biểu diễn dọc: Cơ sở dữ liệu là một danh sách các mục dữ liệu, mỗi mục
dữ liệu có một danh sách tất cả các định danh của các giao tác chứa mục dữ liệu
nà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.vn9

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
B
T1, T2, T3, T7, T9, T11


T
p

m
pq
=
0 khi i
q

T
p Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn10

Ví dụ 1.2: Cơ sở bản dữ liệu 1.1 biểu diễn ở dạng ma trận giao tác là:
Bảng 1.3: Ma trận giao tác của cơ sở dữ liệu bảng 1.1.
TID
A
B
C
D
E

0
0
1
1
0
0
T6
1
0
1
0
0
0
T7
1
1
1
0
0
1
T8
1
0
1
0
0
0
T9
1
1


I.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn11
Định nghĩa 1.3: Cho tập mục X

I và ngƣỡng hỗ trợ tối thiểu (minimum
support) minisup 0,1  (đƣợc xác định trƣớc bởi ngƣời sử dụng). X đƣợc gọi là
tập mục thƣờng xuyên(frequent itemset hoặc large itemset) với độ hỗ trợ tối
thiểu minisup nếu sup(X)  minisup, ngƣợc lại X gọi là tập mục không thƣờng
xuyên.
Định nghĩa 1.4: Một luật kết hợp là biểu thức dạng X

Y, trong đó X và Y là
các tập con của I, X

Y =

; X gọi là tiền đề, Y gọi là kết luận của luật.
Luật kết hợp có hai thông số quan trọng là độ hỗ trợ và độ tin cậy.
Định nghĩa 1.5: Độ hỗ trợ (Support) của một luật kết hợp X

Y, ký hiệu là
sup(X

Y), là độ hỗ trợ của tập mục X

Y, sup(X

X
YX 

Độ tin cậy của luật kết hợp X

Y chính là xác suất có điều kiện P(Y/X):
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn12
P(Y/X) =
 
 
TXDBT
TYTXDBT


=
 
 
TXDBT
TYXDBT


=
)sup(
)sup(
X
YX 



Y trên cơ sở dữ liệu DB sao cho
sup(X

Y)  minsup và conf(X

Y)  minconf.
Bài toán khai phá luật kết hợp này đƣợc gọi là bài toán cơ bản hay bài toán
nhị phân, vì ở đây, giá trị của mục dữ liệu trong cơ sở dữ liệu là 0 hoặc 1 (xuất
hiện hay không xuất hiện).
Bài toán khai phá luật kết hợp đƣợc chia thành hai bài toán con. Bài toán
thứ nhất là tìm tất cả các tập mục thỏa mãn độ hỗ trợ tối thiểu cho trƣớc, tức là
tìm tất cả các tập mục thƣờng xuyên. Bài toán thứ hai là sinh ra các luật kết hợp
từ các tập mục thƣờng xuyên đã tìm đƣợc thỏa mãn độ tin cậy tối thiểu cho
trƣớc.
Bài toán thứ hai đƣợc giải quyết nhƣ sau: Giả sử đã tìm đƣợc X là tập mục
thƣờng xuyên, ta sinh ra các luật kết hợp bằng cách tìm

Y

X, kiểm tra độ tin
cậy của luật X\Y

Y có thỏa 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.



tập mục ứng viên có k mụ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.vn15
Duyệt theo chiều sâu là duyệt qua cơ sở dữ liệu đã đƣợc chuyển đổi thành
cấu trúc cây, quá trình duyệt gọi đệ quy theo chiều sâu của cây.
Với cơ sở dữ liệu có n mục dữ liệu, không gian tìm kiếm có tất cả 2
n
tập
con, rõ ràng đây là bài toán NP khó, do vậy cần phải có phƣơng pháp duyệt thích
hợp, tỉa nhanh các tập ứng viên.
Phƣơng pháp xác định độ hỗ trợ của tập mục X đƣợc chia làm hai cách:
cách thứ nhất là đếm số giao tác chứa X trong cơ sở dữ liệu và cách thứ hai là
tính phần giao của các tập chứa định danh của các giao tác chứa X.
Các thuật toán khai phá có thể phân loại nhƣ sau:

Hình 1.1: Phân loại các thuật toán khai phá tập mục thƣờng xuyên.
Phần tiếp sau mô tả chi tiết nội dung hai thuật toán tiêu biểu và là cơ sở để
phát triển các thuật toán mới trong luận án: Thuật toán Apriori tiêu biểu cho
phƣơng pháp sinh ra các tập mục ứng viên và kiểm tra độ hỗ trợ của chúng;

DFS

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:
Tập k mục
Chức năng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn17
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(itemsets)
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(itemsets)
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

1
[k-2]=L
2
[k-2])  (L
1
[k-1]<L
2
[k-1])
Dạng của tập mục nhận đƣợc bởi nối L
1
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
=apriori_gen(L
k-1
,minsup);//Sinh tập ứng viên mới từ L
k-1

(4) For(each TDB) do begin
(5) C=subset(C
k
,T);//Các tập mục ứng viên chứa trong T
(6) For(each cC)
(7) c.count++; //tăng số đếm c lên một đơn vị
(8) End;
(9) L
k
={ cC
k
/ c.count  minsup};
(10) End;
(11) L=  L
k
;
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

Trích đoạn Thuật toán FSM Thuật toán AFSM ĐÁNH GIÁ KẾT QUẢ VÀ HƢỚNG PHÁT TRIỂN CỦA CHƢƠNG

---