ĐẠ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

Trƣớc tiên, tôi xin chân thành cảm ơn tới các thầy cô giáo trong Khoa Công
nghệ thông tin, Đại học công nghệ, Đại học quốc gia đã nhiệt tình giảng dạy,
truyền đạt kiến thức.
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] ......................... Error! Bookmark not defined.
1.3.1 Cơ sở dữ liệu giao tác ................................... Error! Bookmark not defined.
1.3.2 Tập mục thƣờng xuyên................................. Error! Bookmark not defined.
1.3.3 Luật kết hợp.................................................. Error! Bookmark not defined.
1.4 Một số thuật toán khai phá luật kết hợp ................ Error! Bookmark not defined.

2.3.7 Đề xuất ý tƣởng cải tiến cấu trúc cây gia tăng ........... Error! Bookmark not
defined.
CHƢƠNG 3: CÀI ĐẶT CHƢƠNG TRÌNH THỬ NGHIỆM ....................... ERROR!
BOOKMARK NOT DEFINED.
3.1 Mô tả chƣơng trình chạy ....................................... Error! Bookmark not defined.
3.2 Thử nghiệm đánh giá thuật toán Gia tăng 1 .......... Error! Bookmark not defined.
3.2.1 Thử nghiệm và đánh giá thuật toán trên nội dung 1, 2 ..... Error! Bookmark
not defined.
3.2.2 Thử nghiệm và đánh giá thuật toán trên nội dung 3 .. Error! Bookmark not
defined.
3.3 Kết luận ................................................................. Error! Bookmark not defined.
KẾT LUẬN ............................................... ERROR! BOOKMARK NOT DEFINED.
TÀI LIỆU THAM KHẢO ............................................................................................. 11


5

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

Ký hiệu
xi
tj
I
T
X = {𝑥𝑖1 , … , 𝑥𝑖𝑘 }
sup(X)
S0
𝐹𝑆0
||X||
CSDL

Hình 3-4: Dữ liệu tăng thêm T’ ..................................... Error! Bookmark not defined.
Hình 3-5: Kết quả chạy Apriori và Gia tăng 1 trên T+T’............ Error! Bookmark not
defined.
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
....................................................................................... Error! Bookmark not defined.
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 ................................................................................ Error! Bookmark not defined.
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
....................................................................................... Error! Bookmark not defined.
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 ................................................................................ Error! Bookmark not defined.
Hình 3-10: Kết quả chạy của Apriori và Gia tăng 1 trong trƣờng hợp 1 .............. Error!
Bookmark not defined.
Hình 3-11: Kết quả chạy của Apriori và Gia tăng 1 trong trƣờng hợp 1 .............. Error!
Bookmark not defined.
Hình 3-12: Kết quả chạy của Apriori và Gia tăng 1 trong trƣờng hợp 3 .............. Error!
Bookmark not defined.


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 ............. Error! Bookmark not
defined.
Bảng 1.2: Biểu diễn ngang của cơ sở dữ liệu giao tác T ............. Error! Bookmark not
defined.
Bảng 1.3: Biểu diễn dọc của cơ sở dữ liệu giao tác T ... Error! Bookmark not defined.
Bảng 3.1: Giải thích tiêu đề ........................................... Error! Bookmark not defined.
Bảng 3.2: Bộ cơ sở dữ liệu thứ nhất .............................. Error! Bookmark not defined.
Bảng 3.3: Kết quả thu đƣợc trên bộ cơ sở dữ liệu thứ nhất......... Error! Bookmark not

 Chƣơng 1: Khai phá luật kết hợp. Chƣơng này giới thiệu về khai phá dữ liệu,
các bƣớc trong khai phá dữ liệu, một số kỹ thuật đƣợc sử dụng trong khai phá
dữ liệu. Tiếp theo, chƣơng này đƣa ra những khái niệm trong khai phá luật kết
hợp nhƣ tập mục dữ liệu, cơ sở dữ liệu giao tác, độ hỗ trợ, độ tin cậy của luật
kết hợp. Hai thuật toán khai phá luật kết hợp đƣợc đề cập trong chƣơng 1 là
AIS và Apriori.
 Chƣơng 2: Khai phá luật kết hợp trên cơ sở dữ liệu gia tăng. Chƣơng này tập
trung vào nghiên cứu hai thuật toán khai phá dữ liệu trên cơ sở dữ liệu gia tăng:
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 dọc và
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ợp v.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à

trong bƣớc 5 của khai phá dữ liệu):
Phân loại: phƣơng pháp phân loại cho phép chúng ta phân loại một đối tƣợng
vào một lớp. Mỗi lớp đƣợc đặc trƣng bởi một số thuộc tính nào đó. Ví dụ chúng ta có


10
thể phân loại thành các lớp xe máy khác nhau theo các thuộc tính nhƣ nhãn hiệu, phân
khối, màu sắc. Khi có một chiếc xe mới chúng ta so sánh thuộc tính của nó với thuộc
tính của những lớp đã đƣợc định nghĩa để phân xe đó vào một lớp cụ thể. 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


[3] Nguyễn Hữu Trọng (2007), “Một số thuật toán khai phá luật kết hợp trên cơ sở dữ
liệu tăng trƣởng”, Luận án tiến sĩ toán học, Viện công nghệ thông tin.
[4] Vũ Ðức Thi (2012), “Một số vấn đề tính toán liên quan đến cơ sở dữ liệu và khai
phá dữ liệu", Tạp chí Khoa học và Công nghệ, Viện Khoa học và Công nghệ Việt
Nam, số 6, tập 50, trang 679-703.
Tiếng Anh
[5] Rakesh Agrawal, Tomasz Imielinski T, Arun Swami (1993) “Mining association
rules between sets of items in large database”. In: Proceedings of the 1993 ACM
SIGMOD International Conference on Management of Data, pp 207–216.
[6] Rakesh Agrawal, Ramarkrishnan Srikant (1994) “Fast algorithms for mining
association rules”. In: Proceedings of the 20thVLDB conference, pp 487–499.
[7] Jiawei Han, Michelin Kamber, Jian Pei, “Data Mining: Concepts and Techniques”,
Third Edition, Morgan Kaufmann, pp 243-278.
[8] Jiawei Han, Michelin Kamber, Jian Pei, Slide “Concepts and Techniques, 3re ed –
Chapter 6”.