ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
GIANG THỊ THU HUYỀN
NGHIÊN CỨU CÁC LUẬT KẾT HỢP SONG SONG
TRONG KHAI PHÁ DỮ LIỆU
Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60 48 05
LUẬN VĂN THẠC SĨ
NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS Đoàn Văn Ban
Hà Nội – 2010
LỜI CẢM ƠN
Để có được kết quả như ngày hôm nay, tôi luôn ghi nhớ công ơn của các thầy
cô, bạn bè, đồng nghiệp và gia đình, những người đã dạy bảo và ủng hộ tôi trong suốt
quá trình học tập.
Trước hết, tôi muốn gửi lời cảm ơn đến các thầy cô giáo trường Đại học Công
Nghệ, Đại học Quốc Gia Hà Nội đã quan tâm tổ chức chỉ đạo và trực tiếp giảng dạy
khoá cao học của chúng tôi. Đặc biệt, tôi xin gửi lời cảm ơn sâu sắc đến thầy giáo
hướng dẫn PGS.TS Đoàn Văn Ban, người đã tận tình chỉ bảo và góp ý về mặt chuyên
môn cho tôi trong suốt quá trình làm luận văn. Nếu không có sự giúp đỡ của thầy thì
tôi khó có thể hoàn thành được luận văn này.
Cũng qua đây, tôi xin gửi lời cảm ơn đến ban lãnh đạo Khoa Hệ thống thông
tin Kinh tế thuộc Học viện Ngân hàng, nơi tôi đang công tác, đã tạo mọi điều kiện
thuận lợi cho tôi trong thời gian hoàn thành các môn học cũng như trong suốt quá
trình làm luận văn tốt nghiệp.
Cuối cùng, tôi xin cảm ơn bố mẹ, chồng và các bạn bè, đồng nghiệp đã luôn
ủng hộ, động viên để tôi yên tâm nghiên cứu và hoàn thành luận văn.
Trong suốt quá trình làm luận văn, bản thân tôi đã cố gắng tập trung tìm hiểu,
nghiên cứu và tham khảo thêm nhiều tài liệu liên quan. Tuy nhiên, do bản thân mới bắt
đầu trên con đường nghiên cứu khoa học, chắc chắn bản luận văn vẫn còn nhiều thiếu
sót. Tôi rất mong được nhận sự chỉ bảo của các Thầy Cô giáo và các góp ý của bạn bè,
đồng nghiệp để luận văn được hoàn thiện hơn.
Hà Nội, tháng 04 năm 2010
Giang Thị Thu Huyền
LỜI CAM ĐOAN
Tôi xin cam đoan đề tài “Nghiên cứu các luật kết hợp song song trong khai
phá dữ liệu” là kết quả của tự bản thân tôi tìm hiểu, nghiên cứu. Các tài liệu tham
khảo được trích dẫn và chú thích đầy đủ. Tôi xin chịu trách nhiệm về luận văn của
mình.
MỤC LỤC
MỞ ĐẦU.....................................................................................................................1
CHƯƠNG 1 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU.............................................3
1. 1. Khai phá dữ liệu...............................................................................................3
1. 1. 1. Khái niệm Khai phá dữ liệu ......................................................................3
1. 1. 2. Kiến trúc của một hệ thống khai phá dữ liệu .............................................5
1. 1. 3. Một số kỹ thuật khai phá dữ liệu ...............................................................6
1. 1. 4. Lựa chọn phương pháp khai phá dữ liệu....................................................8
1. 2. Ứng dụng của khai phá dữ liệu .........................................................................9
1. 3. Một số khó khăn trong khai phá dữ liệu..........................................................10
1. 4. Kết luận chương 1 ..........................................................................................11
CHƯƠNG 2 KHAI PHÁ CÁC LUẬT KẾT HỢP SONG SONG.............................12
2. 1. Luật kết hợp trong khai phá dữ liệu.................................................................12
2. 1. 1. Một số hướng tiếp cận trong khai phá luật kết hợp..................................12
2. 1. 2. Các tính chất của luật kết hợp .................................................................13
2. 1. 3. Bài toán khai phá luật kết hợp.................................................................17
2. 1. 4. Một số thuật toán khai phá luật kết hợp...................................................17
2. 2. Các thuật toán song song phát hiện luật kết hợp .............................................26
2. 2. 1. Thuật toán song song ..............................................................................27
2. 2. 2. Khai phá các luật kết hợp song song .......................................................30
2. 3. Kết luận chương 2 ..........................................................................................49
CHƯƠNG 3 CÀI ĐẶT THUẬT TOÁN KHAI PHÁ CÁC LUẬT KẾT HỢP SONG
SONG TRONG KHAI PHÁ DỮ LIỆU......................................................................50
3. 1. Cài đặt thuật toán khai phá các luật kết hợp song song ...................................50
3. 1. 1. Môi trường cài đặt chương trình thử nghiệm...........................................50
3. 1. 2. Mô tả dữ liệu của bài toán.......................................................................51
3. 1. 3. Giao diện chương trình ...........................................................................52
3. 2. Đánh giá kết quả.............................................................................................58
3. 2. 1. Phương pháp đánh giá các chương trình song song .................................58
3. 2. 2. Kết quả cài đặt chương trình thử nghiệm.................................................59
KẾT LUẬN...............................................................................................................60
TÀI LIỆU THAM KHẢO..........................................................................................62
PHỤ LỤC..................................................................................................................64
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
Tên viết tắt Diễn giải
Ck Tập các k-itemset ứng viên (Candidate sets)
Conf Độ tin cậy (Confidence)
D Cơ sở dữ liệu giao dịch
Di Phần thứ i của cơ sở dữ liệu D
Item Mục
Itemset Tập mục
k-itemset Tập mục gồm k mục
Lk Tập các k-itemset phổ biến
MPI Truyền thông điệp (Message Passing Interface)
minconf Ngưỡng tin cậy tối thiểu (minimum confidence)
minsup Ngưỡng hỗ trợ tối thiểu (minimum support)
SC Số đếm hỗ trợ (Support count)
Sup Độ hỗ trợ (Support)
T Giao dịch (Transaction)
TID Định danh của giao dịch (Unique Transaction Identifer)
Tid-List Danh sách các định danh của giao dịch
X Y Luật kết hợp (Với X là tiền đề, Y là hệ quả)