B
TRƯỜNG Đ
KHAI THÁC TOP
TRÊN CƠ S
Chuyên
TP. H
BỘ GIÁO DỤC VÀ ĐÀO TẠO
NG ĐẠI HỌC CÔNG NGHỆ TP.HCM
MAI NGỌC THU
KHAI THÁC TOP-RANK K CHO TẬP ĐÁNH TR
TRÊN CƠ SỞ DỮ LIỆU CÓ TRỌNG SỐ
LUẬN VĂN THẠC SĨ
Chuyên ngành: CÔNG NGHỆ THÔNG TIN
Mã ngành: 60480201
TP. HỒ CHÍ MINH, tháng 01 năm 2015
TP.HCM
P ĐÁNH TRỌNG
Ố
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP.HCM
—————————
MAI NGỌC THU
KHAI THÁC TOP-RANK K CHO TẬP ĐÁNH TRỌNG
TRÊN CƠ SỞ DỮ LIỆU CÓ TRỌNG SỐ
LUẬN VĂN THẠC SĨ
Chuyên ngành: CÔNG NGHỆ THÔNG TIN
Mã ngành: 60480201
CÁN BỘ HƯỚNG DẪN KHOA HỌC: TS. VÕ ĐÌNH BẢY
TP. HỒ CHÍ MINH, tháng 01 năm 2015
CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP.HCM
Cán bộ hướng dẫn khoa học: TS. Võ Đình Bảy
(Ghi rõ họ, tên, học hàm, học vị và chữ ký)
Luận văn Thạc sĩ được bảo vệ tại Trường Đại học Công nghệ TP. HCM
ngày tháng 02 năm 2015
Thành phần Hội đồng đánh giá Luận văn Thạc sĩ gồm:
(Ghi rõ họ, tên, học hàm, học vị của Hội đồng chấm bảo vệ Luận văn Thạc sĩ)
TT
Họ và tên
Chức danh Hội đồng
1
PGS. TS. Lê Hoàng Thái
Chủ tịch
2
PGS. TS. Vũ Hải Quân
Phản biện
3
TS. Tô Hoài Việt
Phản biện
4
TS. Vũ Thanh Hiền
Ủy viên
5
TS. Lê Mạnh Hải
Ủy viên
Xác nhận của Chủ tịch Hội đồng đánh giá luận văn sau khi luận văn đã được
sửa chữa (nếu có).
Chủ tịch Hội đồng đánh giá luận văn
TRƯỜNG ĐH CÔNG NGHỆ TP. HCM
PHÒNG QLKH – ĐTSĐH
CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập – Tự do – Hạnh phúc
TP. HCM, ngày 07 tháng 01 năm 2015
NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ tên học viên:
Mai Ngọc Thu
Giới tính:
Nữ
Ngày, tháng, năm sinh:
24/10/1979
Nơi sinh:
Bình Dương
Chuyên ngành:
Công nghệ thông tin
MSHV:
1241860021
I- Tên đề tài:
KHAI THÁC TOP-RANK K CHO TẬP ĐÁNH TRỌNG TRÊN CƠ SỞ
DỮ LIỆU CÓ TRỌNG SỐ
II- Nhiệm vụ và nội dung:
Đề tài nghiên cứu chỉ đơn giản là tập trung vào nghiên cứu các thuật toán khai
thác các tập được đánh trọng số dựa trên các thuật toán khai thác tập phổ biến trên
cơ sở dữ liệu giao dịch nhị phân. Đề xuất ra thuật toán khai thác các Top-rank-k của
các tập được đánh trọng số dựa trên cơ sở dữ liệu giao dịch có trọng số
III- Ngày giao nhiệm vụ:
01/10/2014
IV- Ngày hoàn thành nhiệm vụ: 20/01/2015
V- Cán bộ hướng dẫn: (Ghi rõ học hàm, học vị, họ, tên)
TS. VÕ ĐÌNH BẢY
CÁN BỘ HƯỚNG DẪN
KHOA QUẢN LÝ CHUYÊN NGÀNH
(Họ tên và chữ ký)
(Họ tên và chữ ký)
TS. VÕ ĐÌNH BẢY
i
LỜI CAM ĐOAN
Công trình nghiên cứu đề tài luận văn này là do chính tôi thực hiện, tôi
cam đoan không sao chép bất kỳ dữ liệu nào từ các công trình nghiên cứu khác.
Tất cả những tham khảo từ các nghiên cứu có liên quan đều được nêu rõ nguồn gốc
sử dụng, danh mục các tài liệu tham khảo có nêu rõ trong luận văn.
Nội dung luận văn có tham khảo và sử dụng các tài liệu, thông tin được
đăng tải trên các tác phẩm, tạp chí và các trang web theo danh mục tài liệu của luận
văn.
Tác giả luận văn
Mai Ngọc Thu
ii
Lời Cảm Ơn
Lời đầu tiên, em xin bày tỏ lòng biết ơn sâu sắc đến Thầy, TS. Võ Đình Bảy
bởi nhờ sự động viên, chỉ bảo tận tình, truyền đạt những kiến thức mới cũng như tạo
mọi điều kiện tốt nhất để em có thể hoàn thành luận văn này.
Em cũng xin gửi lời cảm ơn đến quý Thầy Cô trong khoa Công nghệ
Thông tin trường Đại học Công Nghệ Tp. HCM đã động viên và hỗ trợ em rất nhiều
kiến thức quý báu giúp em hoàn thành tốt luận văn.
Em cũng xin cảm ơn quý Thầy Cô, Anh chị làm việc tại Phòng Sau đại học
đã hỗ trợ em rất nhiều về các thủ tục văn bản, giấy tờ liên quan đến luận văn.
Xin cảm ơn gia đình, đồng nghiệp, bạn bè đã động viên em trong suốt thời
gian thực hiện luận văn này.
Tp. Hồ Chí Minh, ngày 20 tháng 01 năm 2015
Học viên Mai Ngọc Thu
iii
TÓM TẮT
Đề tài nghiên cứu bài toán khai thác các tập phổ biến trên cơ sở dữ liệu số
lượng, nghiên cứu bài toán khai thác Top-rank-k tập phổ biến, nhằm phát triển thuật
toán khai thác Top-rank-k các tập phổ biến trên cơ sở dữ liệu được đánh trọng số.
Các nghiên cứu được trình bày ở trên cho thấy việc khai thác các mẫu phổ biến
chủ yếu dựa vào cơ sở dữ liệu nhị phân, chỉ cho thấy người mua có mua sản phẩm
nào đó hay không, nhưng chưa hỗ trợ việc khai thác các trọng số của từng sản
phẩm. Vì vậy việc khai thác các mẫu phổ biến Top-rank-k được đánh trọng có giá
trị hiệu quả cao trong khai thác dữ liệu.
Thông tin từ cơ sở dữ liệu nhị phân chỉ cho biết khách hàng có mua sản phẩm
hay không, không khai thác được những thông tin khác như tần suất sản phẩm hay
giá thành. Tương tự mỗi một hạng mục trong giao dịch cũng có các trọng số khác
nhau tùy theo từng loại cơ sở dữ liệu cụ thể. Vì vậy khai thác các tập phổ biến được
đánh trọng số trên cơ sở dữ liệu trọng số là một hướng mới cho kết quả nghiên cứu
mang tính thực tiễn cao.
Luận văn nghiên cứu các thuật toán khai thác tập đánh trọng, áp dụng Diffset, cùng
thuật toán WIT-FWI-DIFF, và đề nghị thuật toán khai khác Top-rank-k sử dụng
Diffset nhằm giảm thời gian khai thác và tiết kiệm bộ nhớ lưu trữ.
iv
ABSTRACT
Thesis researches topics of itemset mining problem on the quantitative
databases, researches exploiting Top-rank-k itemset, to develop algorithms to
exploit Top-rank-k itemset in the database that data is weighted.
The researches presented above show that the exploitation of the common
template based primarily on the basis of binary data, indicating buyers to purchase
any product or not, but does not support the exploitation of the weight of each
product yet. So exploiting the popular Top-sample rank-k-value is considered
significant efficiency in data mining.
Information from the quantitative database only provides if customers buy the
product or not, does not mining other information such as the frequency of product
or price. Similarly each item in the transaction have different weights depending on
the specific type of database that occur subsequently exploiting the common
practice is weighted on the basis of weighted data is a new direction research results
for practical.
The thesis applies Diffset, the algorithm WIT-FWI-DIFF, and propose an
algorithm mining Top-rank-k by used Diffset to reduce extraction time and save
memory storage.
v
MỤC LỤC
LỜI CAM ĐOAN ………………………………………………………………………………………….. i
LỜI CÁM ƠN ………………………………………………………………………………………………. ii
TÓM TẮT …………………………………………………………………………………………………… iii
ABSTRACT ………………………………………………………………………………………………… iv
DANH MỤC HÌNH …………………………………………………………………………………….. vii
DANH MỤC BẢNG ………………………………………………………………………………….. viii
DANH MỤC TỪ VIẾT TẮT ………………………………………………………………………… ix
CHƯƠNG 1: MỞ ĐẦU …………………………………………………………………………………. 1
1.1. Đặt vấn đề ……………………………………………………………………………………………. 1
1.2. Mục tiêu của đề tài ………………………………………………………………………………… 1
1.3. Giới hạn của đề tài ………………………………………………………………………………… 2
1.4. Bố cục của đề tài …………………………………………………………………………………… 2
CHƯƠNG 2: TỔNG QUAN CÁC LĨNH VỰC NGHIÊN CỨU VÀ CƠ SỞ LÝ
THUYẾT …………………………………………………………………………………………………. 3
2.1. Các khái niệm, định nghĩa ………………………………………………………………………. 3
2.1.1. Tổng quan về khai thác luật kết hợp ………………………………………………………… 3
2.1.2.
Phương pháp Apriori ………………………………………………………………………… 5
2.1.3.
Phương pháp IT-tree ……………………………………………………………………….. 10
2.1.4.
Phương pháp FP-tree ………………………………………………………………………. 14
2.2.
Tổng quan về khai thác luật kết hợp trên CSDL được đánh trọng số ……………. 19
2.2.1.
Định nghĩa và tính chất của tập được đánh trọng số ……………………………… 19
2.2.2.
Thuật toán khai thác dựa trên WIT-tree[9] ………………………………………….. 20
2.3.
Phương pháp khai thác Top-rank-k các mẫu phổ biến bằng Node-list ………….. 25
2.3.1. Cấu trúc PPC-tree
……………………………………………………………………………….. 25
2.4.
Tổng kết chương ………………………………………………………………………………… 33
CHƯƠNG 3: THUẬT TOÁN KHAI THÁC TOP-RANK-K TẬP ĐÁNH TRỌNG
PHỔ BIẾN ……………………………………………………………………………………………… 34
vi
3.1. Top-rank-k tập phổ biến được đánh trọng phổ biến …………………………………. 34
3.1.1.
Định nghĩa về Top-rank-k tập được đánh trọng phổ biến ……………………… 34
3.1.2.
Nghiên cứu liên quan ………………………………………………………………………. 35
3.2. Top-rank-k được đánh trọng số sử dụng Diffset ………………………………………. 35
3.2.1.
Giới thiệu Diffset …………………………………………………………………………….. 35
3.2.2.
Thuật toán dựa trên Diffset ………………………………………………………………. 36
3.2.2.1. Thuật toán WIT-FWI-DIFFdựa trên Diffset ……………………………………….. 36
3.2.2.2. Thuật toán Top-rank-k dựa trên Diffset ……………………………………………… 39
3.3. Tổng kết chương …………………………………………………………………………………. 44
CHƯƠNG 4: THỰC NGHIỆM VÀ ĐÁNH GIÁ ……………………………………………. 45
4.1 Môi trường thực nghiệm ………………………………………………………………………. 45
4.2 Đặc điểm cơ sở dữ liệu thực nghiệm ……………………………………………………… 45
4.3 Kết quả thực nghiệm ……………………………………………………………………………. 46
CHƯƠNG 5: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ………………………………….. 49
5.1. Kết luận ……………………………………………………………………………………………… 49
5.2. Nhận xét ưu điểm và hạn chế ………………………………………………………………… 49
5.3. Hướng phát triển …………………………………………………………………………………. 50
TÀI LIỆU THAM KHẢO
………………………………………………………………………….. 51
vii
DANH MỤC HÌNH
Hình 2.1 Apriori 1-itemset thỏa minsup …………………………………………………………. 15
Hình 2.2 Apriori 2-itemset thỏa minsup …………………………………………………………. 15
Hình 2.3 Apriori 3-itemset thỏa minsup …………………………………………………………. 16
Hình 2.4 Apriori 4-itemset thỏa minsup …………………………………………………………. 16
Hình 2.5Khởi tạo nút root trên cây FP …………………………………………………………… 20
Hình 2.6 Cây FP hoàn chỉnh 20 …………………………………………………………………….. 21
Hình 2.7 Khởi tạo lớp tương đương rỗng trên cây IT-tree ………………………………… 23
Hình 2.8 Cây IT-tree với lớp tương đương ở mức 2 ………………………………………… 23
Hình 2.9 Cây IT-tree với lớp tương đương ở mức 3 ………………………………………… 24
Hình 2.10 Cây IT-tree với lớp tương đương ở mức 4 ………………………………………. 24
Hình 2.11 Khởi tạo lớp tương đương rỗng cho WIT-tree …………………………………. 29
Hình 2.12 Cây WIT-tree với tập Lc
………………………………………………………………… 29
Hình 2.13 Cây WIT-tree sau khi tiến hành tỉa các tập không thỏa minws …………… 30
Hình 2.14 Cây WIT-tree với tập LCE ……………………………………………………………… 30
Hình 2.15 Cây WIT-tree hoàn chỉnh với minws = 0,4 ………………………………………. 31
Hình 2.16 Cây PPC-tree hoàn chỉnh dựa trên CSDL D…………………………………….. 34
Hình 3.1: Kết quả của thuật toán WIT-FWI-DIFF từ cơ sở dữ liệu ……………………. 47
Hình 3.2 WIT-tree với các tập có kích thước là 1 trong Tabk ……………………………. 51
Hình 3.3 Tập LB được khởi tạo ……………………………………………………………………… 51
Hình 3.4 Cây WIT-tree hoàn chỉnh mới mức k = 4 ………………………………………….. 52
Hình 4.1 Biểu đồ thời gian khi khai thác Top-rank-k trên CSDLMushroom ……….. 54
Hình 4.2 Biểu đồ thời gian khi khai thác Top-rank-k trên CSDL Chess ……………… 55
Hình 4.3 Biểu đồ thời gian khi khai thác Top-rank-k trên CSDLConnect …………… 55
Hình 4.4 Biểu đồ thời gian khi khai thác Top-rank-k trên CSDL BMS-POS ………. 56
viii
DANH MỤC BẢNG
Bảng 2.1 Cơ sở dữ liệu giao dịch D ……………………………………………………………….. 14
Bảng 2.2 Cơ sở dữ liệu giao dịch D1 ……………………………………………………………… 19
Bảng 2.3 Độ hỗ trợ của các item trong cơ sở dữ liệu D1 ………………………………….. 19
Bảng 2.4 Các mặt hàng phổ biến thỏa mãn minsup trong CSDL D1 ………………….. 20
Bảng 2.5 Độ hỗ trợ của các item trong cơ sở dữ liệu D1 ………………………………….. 25
Bảng 2.6 Trọng số giao dịch của các giao dịch có trong D ……………………………….. 25
Bảng 2.7 Bảng trọng số hỗ hợ của các item trong CSDL D ………………………………. 26
Bảng 2.8 Rank của 1-pattern …………………………………………………………………………. 28
Bảng 2.9 PP-code của 1-pattern …………………………………………………………………….. 36
Bảng 2.10 Tabk với mức k = 3 sau khi chèn các mẫu có kích thước là 1 ……………. 39
Bảng 2.11 Tabk với mức k = 3 sau khi chèn các mẫu có kích thước là 2 ……………. 39
Bảng 2.12 Tabk với mức k = 3 sau khi chèn các mẫu có kích thước là 3 ……………. 40
Bảng 3.1 Trọng số giao dịch của các giao dịch ở bảng 2.1 ……………………………….. 46
Bảng 3.2: Bảng trọng số hỗ hợ cho tập phổ biến 1 phần tử
……………………………….. 46
Bảng 3.3 Tabk sau khi chèn các tập có kích thước là 1 thỏa k = 4……………………… 50
Bảng 3.4 Tabk sau khi chèn các tập có trong LB thỏa minws……………………………. 51
Bảng 4.1 Cơ sở dữ liệu thực nghiệm có chỉnh sửa …………………………………………… 53
ix
DANH MỤC TỪ VIẾT TẮT
TW
: Transaction weight
FWI
: Frequent weighted itemsets
Minsup
: ngưỡng hỗ trợ tối thiểu
WIT
: Weighted Itemset-Tidset
ܴܶ
: Top-rank-k
Ws
: Weighted support
1
CHƯƠNG 1: MỞ ĐẦU
1.1. Đặt vấn đề
Khai thác dữ liệu là lĩnh vực đã và đang được nghiên cứu nhiều trong thời gian
vừa quavới mục đích hỗ trợ các nhà quản lý tìm ra mối quan hệ giữa các sản phẩm
trong số lượng lớn danh mục sản phẩm và nhờ đó có thể giúp tăng doanh thu. Quá
trình khai thác dữ liệu là quá trình phát hiện ra các mẫu thông tin có giá trị tiềm ẩn
trong cơ sở dữ liệu (CSDL).
Khai thác luật kết hợp là một trong những phương thức hay và phổ biến nhất
để đạt được mục đích này. Việc khai thác các luật kết hợp nhằm mục đích phát hiện
ra các mối quan hệ giữa các tập thuộc tính trong CSDL với nhau, trongđó khai thác
tập phổ biến đóng vai trò quan trọng trong việc khai thác các luật kết hợp. Các tập
phổ biến thường được khai thác từ các cơ sở dữ liệu nhị phân trong đó từng hạng
mục trong một giao dịch có thể có những ý nghĩa khác nhau.
Tuy nhiên những cơ sở dữ liệu nhị phân chỉ quan tâm đến vấn đề khách hàng
có mua hay không mua sản phẩm nào đó. Nhưng trên thực tế, mỗi một sản phẩm mà
khách hàng mua lại có thể có giá khác nhau. Tương tự mỗi một hạng mục trong
giao dịch cũng có các trọng số khác nhau tùy theo từng loại cơ sở dữ liệu cụ thể.
Khai thác các tập được đánh trọng số trên các cơ sở dữ liệu được đánh trọng số
ưu tiên hiện nay vẫn chưa được phát triễn. Vì vậy việc nghiên cứu các kỹ thuật để
khai thác các cơ sở dữ liệu này mang tính thực tiễn rất cao. Luận văn nghiên cứu về
các thuật toán khai thác các tập phổ biến trên cơ sở dữ liệu nhị phân, dựa vào đó
làm nền tảng để tiến hành nghiên cứu bài toán khai thác Top-rank-k các tập phổ
biến được đánh trọng số.
1.2. Mục tiêu của đề tài
Đề tài tập trung vào nghiên cứu các thuật toán khai thác các tập được đánh
trọng số dựa trên các thuật toán khai thác tập phổ biến trên cơ sở dữ liệu giao dịch
nhị phân. Đề xuất ra thuật toán khai thác các Top-rank-k của các tập được đánh
trọng số dựa trên cơ sở dữ liệu giao dịch có trọng số. Từ đó ứng dụng các thuật toán
này vào trong thực tiễn.
2
Nội dung tập trung nghiên cứu:
–
Đề tài nghiên cứu bài toán khai thác các itemset trên cơ sở dữ liệu số
lượng.
–
Nghiên cứu bài toán khai thác Top-rank-k tập phổ biến.
–
Phát triển thuật toán khai thác Top-rank-k itemset trên cơ sở dữ liệu
được đánh trọng số.
1.3. Giới hạn của đề tài
Luận văn nhằm nghiên cứu các thuật toán khai thác các tập được đánh trọng số
dựa trên các thuật toán khai thác tập phổ biến trên cơ sở dữ liệu giao dịch nhị
phân. Cải tiến thuật toán khai thác các Top-rank-k tập được đánh trọng số dựa
trên cơ sở dữ liệu giao dịch có trọng số bằng cách sử dụng diffset.
1.4. Bố cục của đề tài
Luận văn được chia làm 5 chương cụ thể như sau:
Chương 1: Giới thiệu về luận văn gồm các mục: đặt vấn đề, mục tiêu của đề
tài, giới hạn của đề tài, tổng kết chương.
Chương 2: Tổng quan về lĩnh vực nghiên cứu, nêu các khái niệm, định nghĩa,
cơ sở khoa học, các công trình nghiên cứu liên quan, các phương pháp nghiên cứu
và nhận xét ưu khuyết điểm của các phương pháp.
Chương 3: Đề xuất phương pháp khai thác Top-rank-k tập phổ biến được đánh
trọng.
Chương 4: Trình bày về thực nghiệm bao gồm môi trường thực nghiệm, cơ sở
dữ liệu thực nghiêm, đánh giá các kết quả thu được.
Chương 5: Trình bày các kết quả đạt được của luận văn, nhận xét ưu khuyết
điểm và hướng phát triển của đề tài.
3
CHƯƠNG 2: TỔNG QUAN CÁC LĨNH VỰC NGHIÊN CỨU VÀ
CƠ SỞ LÝ THUYẾT
2.1. Các khái niệm, định nghĩa
Khai thác dữ liệu là một công cụ giúp khai thác những thông tin hữu ích từ
những kho dữ liệu được tích trữ trong suốt quá trình hoạt động của một công ty, tổ
chức nào đó. Khai thác dữ liệu được dùng để mô tả quá trình tìm kiếm, chắt lọc và
khai phá tri thức trong cơ sở dữ liệu hay chỉ việc tìm kiếm một tập hợp nhỏ có giá
trị từ một số lượng lớn các dữ liệu thô. Quá trình này bao gồm tập hợp nhiều kỹ
thuật được sử dụng trong tiến trình khám phá tri thức để tự động khai thác và chỉ ra
sự khác biệt giữa các mối quan hệ và các mẫu chưa biết bên trong dữ liệu.
Khai thác luật kết hợp là một phần quan trọng trong quá trình khám phá tri
thức trong dữ liệu (KDD) [2]. Khai thác luật kết hợp được sử dụng để xác định mối
quan hệ giữa các sản phẩm trong cơ sở dữ liệu giao dịch và điều này dẫn đến việc
nó chỉ quan tâm đến việc khách hàng có mua hay không mua sản phẩm nào đó.
Thực tế, mỗi một sản phẩm có thể có giá trị khác nhau. Tương tự mỗi item trong cơ
sở dữ liệu giao dịch cũng có trọng số khác nhau tùy thuộc từng cơ sở dữ liệu cụ thể.
Vì vậy việc khai thác trên loại dữ liệu này mang tính thực tiễn cao.
Năm 1998, Ramkumar, Ranka và Tsur [4] cũng như Cai, Fu, Cheng và Kwong
[3] đã đề xuất một mô hình để mô tả các khái niệm về việc khai thác luật kết hợp có
trọng số và dựa trên giải thuật Apriori để tìm ra các tập phổ biến được đánh trọng.
Từ đó nhiều kỹ thuật khai thác luật kết hợp có trọng số được đề xuất như: Wang,
Yang, và Yu [6] và Tao, Murtagh, và Farid [5].
2.1.1. Tổng quan về khai thác luật kết hợp
Trong lĩnh vực khai thác dữ liệu, mục đích của luật kết hợp (Association Rule –
AR) là tìm ra các mối quan hệ giữa các đối tượng trong khối lượng lớn dữ liệu. Nội
dung cơ bản của luật kết hợp được tóm tắt như dưới đây.
Cho cơ sở dữ liệu gồm các giao dịch T là tập các giao dịchT = {t1, t2, …, tn}.
Cho I = {i1,i2,…,im} là một tập các item. Mỗi tập con trong I được gọi một
itemset, số lượng các phần tử trong một itemset được gọi là kích thước của một
itemset.
4
Mục đích của luật kết hợp là tìm ra sự kết hợp (association) hay tương quan
(correlation) giữa các items.
Cho X, Y là các itemset, trong đó X và Y là hai tập không giao nhau khác rỗng.
Một luật kết hợp được ký hiệu là ܺ ⟶ܻ
, thể hiện mối ràng buộc của tập Y với tập
X theo nghĩa là sự xuất hiện của tập X sẽ kéo theo sự xuất hiện của tập Y trong các
giao dịch, có thể hiểu rằng những người mua các mặt hàng trong tập X cũng thường
mua các mặt hàng trong tập Y. Ví dụ, nếu X = {Táo, Chuối} và Y = {Anh Đào, Sầu
Riêng} và ta có luật kết hợp XY thì chúng ta có thể nói rằng những người mua
Táo và Chuối thì cũng thường mua Anh Đào và Sầu Riêng.
Tập X được gọi là xuất hiện trong giao dịch t nếu như nó là tập con của t. Độ
hỗ trợ và độ tin cậy là hai tham số dùng để đo lường luật kết hợp.
Thuật toán phổ biến nhất tìm các luật kết hợp là Apriori sử dụng các luật kết
hợp nhị phân.
Định nghĩa 2.1: Độ hỗ trợ
Độ hỗ trợ (Sup) của luật kết hợp ܺ ⟶ܻ
là tần suất giao dịch chứa tất cả các
item trong cả hai tập X và Y. Ví dụ: độ hỗ trợ của luật ܺ ⟶ܻ
là 40%, có nghĩa là
40% các giao dịch X và Y được mua cùng nhau.
Công thức:
ܵݑ
(ܺ ⟶ܻ
) = ܲ
(ܺ∪ܻ
) =
݊(ܺ ∪ܻ)
ܰ
Trong đó n(ܺ ∪ܻ
) là số giao dịch có chứa cả X lẫn Y vàN là tổng số giao
dịchtrong CSDL.
Định nghĩa 2.2: Độ tin cậy (Conf) là xác suất xảy ra khi Y đã biết X.
Ví dụ độ tin cậy của {Táo}⟶{Chuối} là 80% có nghĩa là 80% khách hàng mua
{Táo} cũng mua {Chuối}.
Công thức:
ܥ݂݊(ܺ ⟶ܻ
) = ܲ
(ܻ|ܺ) =
݊(ܺ∪ܻ
)
݊(ܺ)
Để thu được các luật kết hợp, ta thường áp dụng 2 tiêu chí: độ hỗ trợ tối thiểu
minsup và độ tin cậy tối thiểu minconf là hai giá trị ngưỡng tối thiểu cho trước.
5
Luật kết hợp ܺ ⟶ܻ
được coi là một mẫu có giá trị nếu xảy ra đồng thời
ܵݑ
(ܺ ⟶ܻ
) ≥
݉
݅݊ݏݑ và ܥ݂݊(ܺ ⟶ܻ
) ≥
݉
݂݅݊ܿ݊.
Một tập X có độ hỗ trợ vượt quá ngưỡng minsup được gọi là một tập phổ biến.
Định nghĩa 2.3: Lớp tương đương
Cho X⊆I, ta định nghĩa hàm p(X,k)= X[1,k] gồm k phần tử đầu của X và quan
hệ tương đương dựa vào tiền tố sau:
ܺ, ܻ⊆ܫ, ܺ≡ఏೖ, ܻ
(ܺ, ݇
) = (ܻ, ݇)
Tập hợp tất cả itemset có cùng tiền tố là X gọi là lớp tương đương, và được ký
hiệu là [X].
Kết nối Galois
Cho quan hệ hai ngôi ߜ⊆ܫ× ܶ
chứa CSDL cần khai thác, trong đó I là tập
các danh mục còn T là tập các giao tác. Đặt ܺ⊆ܫ
và ܻ⊆ܶ
. Ta định nghĩa hai ánh
xạ giữa P(I) và P(T) như sau:
I. ݐ: ܫ ⟼ܶ, ݐ
(ܺ) = {ݕ ∈ܶ
|∀ݔ∈ܺ, ݔ
ߜ
ݕ
}
II. ݅: ܶ ⟼ܫ, ݅
(ܻ) = {ݔ ∈ܫ
|∀ݕ∈ܻ, ݔ
ߜ
ݕ}
Ánh xạ t(X) là tập hợp tất cả các giao dịch có chứa X trong CSDL giao dịch, và
ánh xạ i(Y) là tập hợp tất cả các item chứa trong tất cả giao dịch Y
Cho X, X1, X2 ∈P(I) và Y,Y1,Y2 ∈ P(T). Dựa theo Galois [9] ta có các tính chất
sau:
(i). ܺଵ⊂ܺ
ଶ⇒ݐ
(ܺଵ) ⊇ݐ
(ܺଶ)
(ii). ܻ
ଵ⊂ܻ
ଶ⇒݅(ܻ
ଵ) ⊇݅(ܻ
ଶ)
(iii). ܺ⊆݅
൫ݐ(ܺ)൯ݒ
à ܻ⊆ݐ(݅
(ܻ))
2.1.2. Phương pháp Apriori
Khai thác tập phổ biến được đề xuất bởi Agrawal và các đồng sự năm 1993 [3]
là một phương thức dành cho doanh nghiệp để phân tích giỏ hàng, nhằm mục đích
tìm ra những quy luật trong việc mua sắm của khách hàng, siêu thị, v.v…
Thuật toán Apriori là thuật toán sinh ứng viên được đề xuất bởi Agrawal và
Srikant vào năm 1994 [2]. Tư tưởng chính của thuật toán Apriori là:
– Tìm ra tất cả các tập phổ biến có thể có trong cơ sở dữ liệu: k-itemset (tập
danh mục gồm k phẩn tử) được dùng để tìm (k+1)-itemset.
6
– Đầu tiên tìm 1-itemset (ký hiệu L1). L1 được dùng để tìm L2 (2-itemset). L2
được dùng để tìm L3 (3-itemset) và tiếp tục cho đến khi không có k-itemset được
tìm thấy.
– Từ phổ biến sinh ra các luật kết hợp mạnh (các luật kết hợp thỏa mãn minsup
và minconf)
Thuật toán Apriori dùng cách tiếp cận lặp được biết đến như tìm kiếm theo
mức, với các tập có kích thước là k gọi là k-itemset được dùng để thăm dò các tập có
kích thước k+1 gọi là (k+1)-itemset.
Tính chất 2.1: Mọi tập con của tập phổ biến đều phổ biến, nghĩa là ∀ܺ⊆ܻ
,
có nghĩa là nếu ܵݑ(ܻ) ≥
݉
݅݊ݏݑ thì ܵݑ(ܺ) ≥
݉
݅݊ݏݑ.
Tính chất 2.2: Mọi tập cha của tập không phổ biến đều không phổ biến, nghĩa
là ∀ܻ⊇ܺ
, nếu ܵݑ(ܺ) <
݉
݅݊ݏݑ thì ܵݑ(ܻ) <
݉
݅݊ݏݑ
Các bước của giải thuật Apriori:
Bước 1: Tính độ hỗ trợ cho mỗi item có kích thước là 1, sau đó lọc ra các item
thỏa mãn yêu cầu minsup và đặt nó là tập L1: 1-itemset là tập kết quả tìm được.
Chọn L1 là tập hạt giống.
Bước 2: Bắt đầu từ tập hạt giống 1-itemset là tập phổ biến có kích thước là 1
đã tìm được ở trên, phát sinh ra các tập phổ biến có kích thước là 2 gọi là các tập
ứng viên (C) và tính độ hỗ trợ cho mỗi tập (C) này, từ đó chọn ra các tập phổ biến
thỏa yêu cầu và đặt nó là tập L2: 2-itemset được dùng làm tập hạt giống cho bước kế
tiếp.
Bước 3: Lặp lại bước 2, từ việc tiến hành chọn tập hạt giống có kích thước l là
l-itemset để tìm ra các tập ứng viên có kích thước là (l+1)-itemset, quá trình này sẽ
kết thúc khi không còn tìm được tập phổ biến nào thỏa yêu cầu minsup.
7
Giải thuật Apriori:
Đầu vào:
Tập các giao dịch D, ngưỡng hỗ trợ tối thiểu cminsup
Đầu ra:
L các tập phổ biến có trong D.
Phương thức:
Apriori()
{
Gọi Ck Tập các ứng viên có kích thước k
Lk Các tập phổ biến có kích thước k
L1 = { các tập phổ biến có kích thước là 1 thỏa cminsup};
for ( k = 1; Lk!= ∅; k++ )
{
Ck + 1= Apriori_gen(Fk) // Các ứng viên được tạo ra từ Fk
for each t in D
{
Ct = {ܿ∈ܥ
ା
ଵ|ܿ⊆ݐ
}
for ܿ∈ܥ
௧
{
c.count++
}
ܨା
ଵ= {ܿ∈ܥ
ା
ଵ|ܿ. ܿݑ
݊ݐ≥ܿ݉
݅݊ݏݑ}
}
return ⋃ܨ
}
Thuật toán Apriori sử dụng độ hỗ trợ tối thiểu dưới dạng số đếm (cminsup-
minsup count) để loại bỏ các ứng viên. Giá trị cminsup do người dùng đưa ra.
Hàm Apriori_gen có nhiệm vụ sinh ra các tập itemset có kích thước k + 1 từ
tập hạt giống có kích thước là k trong tập Lk. Thủ tục này được thực thi bằng cách
nối (join) các tập item có chung các tiền tố (prefix) và sau đó áp dụng tính chất 1.1
để loại bỏ các tập không thỏa mãn:
8
Bước nối: sinh ra các tập Lk+1 là ứng viên của tập phổ biến có kích thước k+1
bằng cách kết hợp tập phổ biến Pk và Qk có kích thước k và trùng nhau ở k-1 tập đầu
tiên. Ví dụ ta có: ܮ+ 1 = ܲ
+ ܳ
= {݅
ଵ, ݅
ଶ , … , ݅
ି
ଵ, ݅
} với Với ܲ =
{݅ଵ, ݅
ଶ , … , ݅
ି
ଵ, ݅
} vàܳ = {݅
ଵ, ݅
ଶ , … , ݅
ି
ଵ, ݅
} trong đó ݅ଵ≤݅
ଶ≤⋯≤݅
ି
ଵ≤
݅≤݅
ᇱ
Bước tỉa: Giữ lại tất cả các ứng viên Lk+1 thỏa thỏa mãn tính chất Apriori (tính
chất 1.1) tức là mọi tập con có kích thước k của nó đều là tập phổ biến (∀X ⊆ Lk+1
và |X| = k thì X ∈ Fk).
Ta có cơ sở dữ liệu D gồm 4 giao dịch với các tập item sau:
Bảng 2.1 Cơ sở dữ liệu các giao dịch D
Transaction
Item
1
A, B, D, E
2
B, C, E
3
A, B, D, E
4
A, B, C, E
5
A, B, C, D, E
6
B, C, D
Áp dụng giải thuật Apriori, cho CSDL giao dịch D với ngưỡng minsup = 0.4
Bước 1: Quét CSDL Dđể xác định độ hỗ trợ cho các tập phổ biến có kích
thước là 1. Các tập item nào có độ hỗ trợ nhỏ hơn 40% sẽ bị loại bỏ. Sau lần quét
đầu tiên thì tất cả các tập phổ biến đều thỏa ngưỡng minsup, ta có:
ܮଵ= ൛{ܣ}, {ܤ}, {ܥ}, {ܦ}, {ܧ}ൟ
9
Hình 2.1 Apriori 1-itemset thỏa minsup
Bước 2: Tạo ra các tập phổ biến có kích thước là 2 dựa trên các tập phổ biến
có kích thước là 1 thỏa điều kiện minsup vừa tìm được, quét cơ sở dữ liệu D để xác
định độ hỗ trợ cho từng tập phổ biến và loại bỏ tất cả các tập phổ biến có độ hỗ trợ
nhỏ hơn minsup. Sau khi quét ta có:
Hình 2.2 Apriori 2-itemset thỏa minsup
Bước 3: Tạo ra các tập phổ biến có kích thước là 3 dựa trên các tập phổ biến
có kích thước là 2 thỏa minsup vừa tìm được, quét cơ sở dữ liệu D để xác định độ
hỗ trợ cho từng tập phổ biến và loại bỏ tất cả các tập phổ biến có độ hỗ trợ nhỏ hơn
minsup.
10
Hình 2.3 Apriori 3-itemset thỏa minsup
Bước 4: Tạo ra các tập phổ biến có kích thước là 4 dựa trên các tập phổ biến
có kích thước là 3 vừa tìm được, quét cơ sở dữ liệu D để xác định độ hỗ trợ cho
từng tập phổ biến và loại bỏ tất cả các tập phổ biến có độ hỗ trợ nhỏ hơn minsup.
Hình 2.4 Apriori 4-itemset thỏa minsup
Bước 5: Tổng hợp tất cả các tập phổ biến tìm được thỏa điều kiện ngưỡng hỗ
trợ minsup = 40%, ta có:
2.1.3. Phương pháp IT-tree
Phương pháp IT-tree được Zaki đề xuất vào năm 1997 [8]. IT-Tree có cách tiếp
cận đơn giản là dựa trên phần giao nhau của tập các giao tác để tính độ phổ biến và
khái niệm mới lớp tương đương nhằm chia không gian xử lý ban đầu thành tập các
không gian nhỏ độc lập giúp cho việc tìm kiếm nhanh hơn. Một điểm mới nữa của
phương pháp IT-tree là dựa trên phần khác nhau trên Tidset của các tập dữ liệu
11
nhằm làm giảm kích thước bộ nhớ yêu cầu và giúp cho việc tính độ phổ biến nhanh
hơn.
Ứng dụng IT-Tree trong giai đoạn khai thác tập phổ biến:
Nhận xét: chỉ những itemset nào có tập giao tác khác rỗng thì mới có thể xuất
hiện trong giao tác, lúc đó mới tính độ hỗ trợ và so sánh với minsup. Còn lại những
itemset có tập giao tác bằng rỗng thì không xuất hiện trong cơ sở dữ liệu đó. Ví dụ
một tập các món hàng mà không được bán lần nào hết thì tập món hàng đó không
xuất hiện trong hoá đơn bán hàng. Do vậy ta có thể tỉa bớt những tập đó trong quá
trình sinh tập k-itemset từ tập (k-1)-itemset để giảm bớt không gian xử lí.
Để ứng dụng IT-Tree ta cần thay thế hàm Apriori_gen trong thuật toán Apriori
thành hàm IT_Tree, như trong hình 2.2, để sinh ra một k-itemset từ hai (k-1)-
itemset ta cần phải xét đến hai yếu tố:
1. Hai (k-1)-itemset phải cùng tiền tố
2. Giao hai tập giao tác của hai (k-1)-itemset, nếu lực lượng của phần giao lớn
hơn hay bằng minsup thì k-itemset được thêm vào tập Ck.
Giải thuật Eclat
Bước 1: Đầu tiên quét cơ sở dữ liệu, khởi tạo lớp tương đương rỗng với tiền tố
{} ( hay [∅]) chứa tất cả các tập phổ biến có kích thước là 1 thỏa điều kiện
≥minsup.
Bước 2: Gọi hàm ENUMERATE_FREQUENT với đầu vào là lớp tương
đương với tiền tố {}. Thủ tục này sẽ xét mỗi nút li∈[ ࡼ
] với lj∈[ࡼ] đứng sau nó, với
mỗi một cặp (li,lj), thủ tục này sẽ tính Y=t(li ∪ lj) = t(li) ∩ t(lj), nếu|Y|≥ ݉݅݊ݏݑ
nghĩa là độ hỗ trợ của li ∪ lj thỏa minsup thì thêm nút X ×Y vào lớp tương đương
[Pi].
Bước 3: Tiếp tục lặp lại bước 2 cho đến khi không tìm được lớp tương đương
nào thỏa điều kiện minsup.
Giải thuật Eclat
Đầu vào: cơ sở dữ liệu D với ngưỡng phổ biến cminsup
Đầu ra: IT-tree chứa tất cả các tập phổ biến của cơ sở dữ liệu
Phương thức:
12
Eclat( )
1.
[∅] = ݅∈ܫ∧ߪ(݅) ≥ ܿ݉݅݊ݏݑ}
2.
ENUMERATE_FREQUENT([∅])
ENUMERATE_FREQUENT([ܲ])
3. For all li∈[ܲ]do
4.
[Pi]={ ∅}
5.
For all lj∈[ܲ], with j > i do
6.
X=li ∪ lj
7.
Y=t(li) ∩ t(lj)
8.
If |Y| ≥ ܿ݉݅݊ݏݑ then
9.
[Pi]= [Pi] ∪{X×Y}
10.
ENUMERATE_FREQUENT([Pi])
Đầu tiên, thuật toán khởi tạo lớp tương đương rỗng ([∅]) chứa toàn bộ các
nútcó kích thước là 1 gọi 1-itemsets, và chúng đều thỏa điều kiện ngưỡng minsup.
Tất cả các nút ở mức 1 sẽ trở thành một lớp tương đương với tiền tố là [∅] (dòng
1). Sau đó hàm ENUMERATE_FREQUENT với biến đầu vào là lớp tương
đương rỗng sẽ được thực thi. Thủ tục ENUMERATE_FREQUENT sẽ xét mỗi nút
li∈[ܲ] (dòng 3) với nút lj∈[ܲ] (dòng 5) đứng sau nó, với mỗi cặp (li,lj), thủ tục này
sẽ tính Y= t(li ∪ lj)= t(li) ∩ t(lj) (dòng 7), nếu |Y|≥ ܿ݉݅݊ݏݑ nghĩa là độ hỗ trợ
theo số đếm của li ∪ lj thỏa cminsup thì thêm nút X ×Y vào lớp tương đương [Pi]
(được
khởi
tạo
rỗng
ở
dòng
4).
Sau
đó,
gọi
đệ
qui
thủ
tục
ENUMERATE_FREQUENT để sinh ra các lớp tương đương con cho đến khi
không còn lớp tương đương nào được tạo ra (dòng 10).
Sử dụng cơ sở dữ liệu D (Bảng 2.1) để tiến hành khai thác các tập phổ biến có
độ hỗ trợ thỏa minsup = 0.4.
Bước 1: Khởi tạo lớp [∅] chứa tất cả các tập phổ biến có kích thước là 1
