ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
VÀ TRUYỀN THÔNG
NGUYỄN AN KHÁNH KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN
LỢI ÍCH CAO TRONG CƠ SỞ DỮ LIỆU
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
VÀ TRUYỀN THÔNG
NGUYỄN AN KHÁNH
KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN
LỢI ÍCH CAO TRONG CƠ SỞ DỮ LIỆU Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01
Và cuối cùng, tôi xin gửi lời cảm ơn tới gia đình, bạn bè và đồng nghiệp –
những ngƣời luôn ở bên tôi những lúc khó khăn nhất, luôn động viên tôi, khuyế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 20 tháng 6 năm 2012
Tác giả
Nguyễn An Khánh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên LỜI CAM ĐOAN
Tôi xin cam đoan Luận văn “ Khai phá tập mục thƣờng xuyên lợi ích cao
trong cơ sở dữ liệu “ đƣợc thực hiện theo đúng mục tiêu đề ra dƣới sự hƣớng dẫn
của GS. TS Vũ Đức Thi. Trong toàn bộ luận văn, những điều đƣợc trình bày là của
cá nhân hoặc là đƣợc tổng họp từ nhiều nguồn tài liệu. Tất cả các loại tài liệu đều có
xuất xứ rõ ràng và đƣợc trích dẫn hợp pháp. Thái Nguyên, ngày 20 tháng 6 năm 2012
Tác giả
2
,…,T
m
}: Cơ sở dữ liệu có m giao tác.
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 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 ví dụ.
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 ví dụ.
Nếu X Y thì X gọi là tập con của tập Y, Y gọi là tập cha của tập X.
minsup: Ngƣỡng độ hỗ trợ tối thiểu.
minShare: Ngƣỡng cổ phần tối thiểu.
minutil: Giá trị lợi ích tối thiểu.
X: Số phần tử của tập hợp X.
Viết tắt:
CSDL: Cơ sở dữ liệu.
CNTT: Công nghệ Thông tin.
CNTT và TT: Công nghệ Thông tin và Truyền thông.
DL: Dữ liệu.
2.4.3 Ví dụ áp dụng minh họa 61
2.4.3.1 Xây dựng cây UP-tree 62
2.4.3.2 Khai phá cây UP-tree 64
2.4.4 Nhận xét thuật toán COUI-Mine2 68
2.5 THUẬT TOÁN COUI-Mine3 70
2.5.1 Cơ sở của thuật toán 70
2.5.2 Xây dựng và khai phá mảng giao tác 71
2.5.2.1 Xây dựng mảng giao tác 71
2.5.2.2 Khai phá mảng giao tác : 75
2.5.3 Nhận xét thuật toán COUI-Mine3 78
2.6 KẾT LUẬN CHƢƠNG 2 80
Chƣơng 3 THỰC NGHIỆM THUẬT TOÁN KHAI PHÁ TẬP MỤC LỢI ÍCH CAO 81
PHẦN KẾT LUẬN 85
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
7
MỞ ĐẦU
Ngày nay, cùng với sự phát triển không ngừng của ngành công nghệ thông tin
và truyền thông vào nhiều lĩnh vực đời sống văn hóa xã hội, quản lý kinh tế, khoa
học kỹ thuật, … đã tạo ra nhiều cơ sở dữ liệu khổng lồ. Để khai thác hiệu quả nguồn
thông tin dữ liệu lớn, hỗ chợ tiến trình ra quyết định, bên cạnh các phƣơng pháp
khai thác thông tin truyền thống một khuynh hƣớng kỹ thuật mới ra đời đó là Kỹ
thuật Khai phá dữ liệu và khám phá tri thức (KDD – Knownledge Discovery and
DataMining) là một lĩnh vực quan trọng của nghành Công nghệ thông tin. Đây là
lĩnh vực đã thu hút đƣợc đông đảo các nhà khoa học trên thế giới và trong nƣớc
tham gia nghiên cứu. Khai phá tập mục thƣờng xuyên là bài toán có vai trò quan
trọng trong nhiều nhiệm vụ khai phá dữ liệu.
Mô hình khai phá tập mục thƣờng xuyên cơ bản có nhiều ứng dụng trong thực
tế bên cạnh đó còn có những hạn chế, không đáp ứng đƣợc nhu cầu của ngƣời sử
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
9
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 của 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á 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.
Mô hình đầu tiên của bài toán khai phá luật kết hợp là mô hình nhị phân (hay còn
gọi là mô hình cơ bản) đƣợc R.Agrawal, T.Imielinski và A.Swami đề xuất vào năm
1993, xuất phát từ nhu cầu phân tích dữ liệu của cơ sở dữ liệu giao tác, phát hiện
các mối quan hệ giữa các tập mục hàng hóa (Itemsets) đã bán đƣợc tại các siêu thị.
Việc xác định các quan hệ này không phân biệt vai 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:
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 mục X nếu X
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.
Bảng 1.2: Biểu diễn dọc của cơ sở dữ liệu giao tác.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
12
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
C
T1, T2, T4, T5, T6, T7, T8, T11
D
T1, T2, T3, T4, T5
E
T9, T10
F
T4, T7
Ví dụ 1.2: Cơ sở dữ liệu bảng 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
F
T1
0
1
1
1
0
0
T2
0
1
1
1
0
0
T3
1
0
0
1
T8
1
0
1
0
0
0
T9
1
1
0
0
1
0
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
13
T10
1
0
0
0
1
0
T11
1
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
14
Và ta có 0 conf(X Y) 1.
Các luật thỏa mãn cả hai ngƣỡng độ hỗ trợ tối thiểu (minsup) và độ tin cậy
tối thiểu (minconf), tức thỏa 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 và X Y thì sup(X) sup(Y).
(2) Nếu một tập mục là không thƣờng xuyên thì mọi tập cha của nó cũng không
thƣờng xuyên.
(3) Nếu một tập mục là thƣờng xuyên thì mọi tập con khác rỗng của nó cũng là
tập mục thƣờng xuyên.
Tính chất (3) đƣợc gọi là tính chất Apriori, tính chất này là cơ sở để rút gọn
không gian tìm kiếm các tập mục thƣờng xuyên.
1.2.3 Bài toán khai phá luật kết hợp
Cho cơ sở dữ liệu giao tác DB, ngƣỡng độ hỗ trợ tối thiểu minsup và
ngƣỡng độ tin cậy tối thiểu minconf.
Yêu cầu: Tìm tất cả các luật kết hợp X 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
cấu trúc cây, quá trình duyệt gọi đệ quy theo chiều sâu của cây.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
16
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 vă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; Thuật toán FP-
growth, đại diện cho phƣơng pháp không sinh ra tập mục ứng viên, cơ sở dữ liệu
đƣợc nén lên cấu trúc cây, sau đó khai phá bằng cách phát triển dần các mẫu cây
này.
1.3.2 Thuật toán Apriori
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(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 (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 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
k
đƣợc sinh ra bởi việc kết nối
L
k-1
với chính nó. Hai tập mục L
1
và L
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ể là 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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
18
k-tập mục ứng viên mà không có mặt trong L
k-1
k
={ cC
k
/ c.count minsup};
(10) End;
(11) L= L
k;
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
(1) For (each(k-1)-tập mục L
1
L
k-1
) do
(2) For (each(k-1)-tập mục L
2
L
k-1
) do
(3) If (L
1
[k-1],L
2
[k-1]};
//kết nạp k-tập mục mới vào C
k
// Bước tỉa
(5) For (each c
i
C
k
) do
(6) If exist(s c
i
) and (s L
k-1
) then
(7) Delete c
i
from C
k
;
(8) Return C
k
;
Ví dụ minh họa thuật toán Apriori:
Ta minh họa thực hiện thuật toán Apriori trên cơ sở dữ liệu trong bảng 1.4
với minsup =50%, tức xuất hiện ít nhất 2 lần.
Bảng 1.4: Cơ sở dữ liệu giao tác minh họa thực hiện thuật toán Apriori.
TID
2
đƣợc C
3
:
3-tậpmục
{B,C,E}
Duyệt CSDL lần thứ 3: tính độ hỗ trợ cho các 3-tập mục. C
3
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
21
Nối L
3
với L
3
đƣợc L
4
=, thuật toán dừng.
Các tập mục thƣờng xuyên tìm đƣợc theo thuật toán Apriori là:
L=L
1
L
2
L
3
={A,B,C,E,AC,BC,BE,CE,BCE}
22
lƣợng tính toán lớn. Tuy vậy, thuật toán FP-growth khai phá cây FP-tree sử dụng
phƣơng pháp đệ quy, đòi hỏi khối lƣợng tính toán lớn và cần nhiều bộ nhớ. Năm
2003, nhóm tác giả Mohammad El-Hajj và Osmar R. Zaiane ở đại học Alberta
Edmonton, Canada đề xuất thuật toán không đệ quy khai phá cây FP-tree dựa trên
cấu trúc cây COFI-tree có nhiều ƣu điểm hơn thuật toán FP-growth.
Phần sau đây trình bày nội dung cơ bản của thuật toán COFI-tree khai phá
cây FP-tree là cơ sở để phát triển các thuật toán mới trong chƣơng hai của luận văn.
Thuật toán COFI-tree gồm 2 giai đoạn chính. Giai đoạn thứ nhất, xây dựng
cây FP-tree. Giai đoạn thứ hai, khai phá cây FP-tree chia thành nhiều bƣớc tƣơng
ứng với các mục dữ liệu trong bảng đầu mục của cây FP-tree, mỗi bƣớc sử dụng
một cấu trúc dữ liệu phụ trợ là cây COFI-tree của mục dữ liệu đó.
Mỗi nút của cây FP-tree gồm 3 trƣờng: tên mục dữ liệu, độ hỗ trợ và một
con trỏ(con trỏ này trỏ đến nút tiếp theo cùng tên trên cây hoặc là null nếu không
có). Cây FP-tree có một bảng đầu mục(header table). Mỗi mục của bảng có 3
trƣờng: tên mục dữ liệu, độ hỗ trợ và con trỏ, con trỏ này trỏ đến nút đầu tiên biểu
diễn mục dữ liệu này trong cây.
Cây COFI-tree có bảng đầu mục giống nhƣ cây FP-tree nhƣng các mục dữ
liệu có thứ tự ngƣợc lại. Mỗi mục trong bảng đầu mục chứa 3 trƣờng: tên mục dữ
liệu, độ hỗ trợ địa phƣơng(số lần xuất hiện của mục dữ liệu trong cây COFI-tree) và
con trỏ(trỏ đến nút đầu tiên biểu diễn mục dữ liệu này trong cây). Một danh sách
liên kết đƣợc duy trì giữa các nút cùng tên để thuận lợi cho quá trình khai phá. Mỗi
nút của cây COFI-tree có 4 trƣờng: tên mục dữ liệu, hai biến s và p(biến s biểu diễn
độ hỗ trợ của nút, biến p cho biết số lần nút đó đã tham gia tạo mẫu), con trỏ(trỏ đến
nút tiếp theo cùng tên trên cây).
Ta minh họa thuật toán COFI-tree qua xét cơ sở dữ liệu bảng 1.5 với
ngƣỡng độ hỗ trợ minsup=3.
Bảng 1.5: Cơ sơ dữ liệu giao tác minh họa thực hiện thuật toán COFI-tree.
TID
T4
0
0
1
1
0
1
T5
0
0
1
1
0
0
T6
1
0
1
0
0
0
T7
1
1
1
0
0
1
T8
1
Bảng 1.6: Các mục dữ liệu và độ hỗ trợ.
Mục dữ liệu
Độ hỗ trợ
A
7
B
6
C
8
D
5
E
2
F
2
Bảng 1.7: Các mục dữ liệu thƣờng xuyên đã sắp thứ tự
Mục dữ liệu
Độ hỗ trợ
C
8
A
7
B
6
D
5
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
24
T7
C, A, B
T8
C, A
T9
A, B
T10
A
T11
C, A, B
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
25
Hình 1.2: Cây FP-tree của CSDL bảng 1.5
Hình 1.3: Cây COFI-tree của mục D
Khai phá cây D-COFI-tree: xét lần lƣợt các mục dữ liệu trong bảng đầu
mục, bắt đầu từ mục có độ hỗ trợ lớn nhất là C, cuối cùng đến mục có độ hỗ
trợ nhỏ nhất A. Mục C có 2 nhánh trên cây là (C:2, B:3, D:5) và (C:2, D:5).
Nhánh thứ nhất tạo ra mẫu CBD với độ hỗ trợ là s – p = 2 - 0 = 2(s và p là
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Copyright: Tài liệu đại học ©