BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ TP. HỒ CHÍ MINH

------------------------------

ĐẶNG CÔNG QUỐC

ĐÁNH GIÁ CÁC THUẬT TOÁN
KHAI THÁC TẬP MỤC LỢI ÍCH CAO

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 10 năm 2015


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ TP. HỒ CHÍ MINH

------------------------------

ĐẶNG CÔNG QUỐC

ĐÁNH GIÁ CÁC THUẬT TOÁN
KHAI THÁC TẬP MỤC LỢI ÍCH CAO

LUẬN VĂN THẠC SĨ
Chuyên ngành: Công Nghệ Thông Tin
Mã ngành: 60480201


Phản biện 1

3

TS. Võ Đình Bảy

Phản biện 2

4

TS. Trần Đức Khánh

5

TS. Nguyễn Thị Thúy Loan

Ủy viên
Ủy viên, Thƣ ký

Xác nhận của Chủ tịch Hội đồng đánh giá Luận văn sau khi Luận văn đã sửa chữa.
Chủ tịch Hội đồng đánh giá LV


TRƢỜNG ĐẠI HỌC
CÔNG NGHỆ TP.HỒ CHÍ MINH

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập – Tự do – Hạnh phúc

PHÒNG QLKH – ĐTSĐH


i

LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết
quả đánh giá, nhận xét và các đề xuất cải tiến mới nêu trong Luận văn là trung thực
và chƣa từng đƣợc ai công bố trong bất kỳ công trình nào khác.
Tôi xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện Luận văn này
cũng nhƣ các trích dẫn hay tài liệu học thuật tham khảo đã đƣợc cảm ơn đến tác giả
hay ghi rõ ràng nguồn gốc thông tin trích dẫn trong Luận văn.

Học viên thực hiện Luận văn

Đặng Công Quốc


ii

LỜI CẢM ƠN
Lời đầu tiên tôi xin gửi lời cảm ơn chân thành và biết ơn sâu sắc tới TS. Tô
Hoài Việt – Trƣờng Đại học Sài Gòn, PGS.TSKH. Nguyễn Xuân Huy – Viện Hàn
lâm KHCN Việt Nam, TS. Võ Đình Bảy – Trƣờng Đại học Công nghệ TP. Hồ Chí
Minh, TS. Lƣ Nhật Vinh – Trƣờng Đại học Công nghiệp Thực phẩm TP. Hồ Chí
Minh, PGS.TS Lê Hoài Bắc – Trƣờng Đại học Khoa học Tự nhiên TP. Hố Chí
Minh, TS. Nguyễn Quốc Huy – Trƣờng Đại học Sài Gòn, những ngƣời thầy đã chỉ
bảo và hƣớng dẫn tận tình cho tôi trong suốt quá trình nghiên cứu khoa học và thực
hiện luận văn này.
Tôi xin chân thành cảm ơn sự dạy bảo, giúp đỡ, tạo điều kiện và khuyến
khích tôi trong quá trình học tập và nghiên cứu của các thầy cô giáo, cán bộ quản lý


Xác định đƣợc thuật toán Two-Phase trong SPMF cài đặt không đúng với bài
báo ban đầu (cài đặt theo cây WIT-TREE, sử dụng Tidset)

-

Cài đặt bổ sung thuật toán Diffset-Two-Phase (mở rộng của Two-Phase có
dùng thêm tính chất Diffset của Zaki)

-

Thực nghiệm lại tất cả các thực nghiệm đã đƣợc thực hiện trong các công
trình công bố để xác định tính đúng đắn của thuật toán.
Các kết quả này hoàn thành mục tiêu đánh giá khách quan ƣu điểm và khuyết

điểm của các thuật toán mới. Đánh giá một số thuật toán theo cấu trúc cây, một số
thuật toán theo utility-list; So sánh hiệu quả giữa cấu trúc cây và utility-list. Kiểm
tra tính đúng đắn của mã nguồn các thuật toán khai thác tập có ích cao trong công
cụ SPMF so với mã giả của các thuật toán đƣa ra trong các bài báo. Hiện thực lại
các thực nghiệm cho từng thuật toán đã trình bày trong các bài báo đã công bố. Qua


iv

đó, đảm bảo môi trƣờng thực nghiệm là hoàn toàn đáng tin cậy để so sánh và đánh
giá với các kết quả mới sau này nếu có.


v


All experiments in proposed papers of HUI mining are implemented again to
identify the correctness of algorithms.
These results help us measure objectively the advantages and disadvantages

of novel algorithms. Especially, we focus on algorithms using lattice structure and
utility-list, and identify the correctness of source code of SPMF is based on the
pseudo-code proposed in HUI papers. Then, the correctness of experiments in HUI
papers is also reviewed by re-running the algorithms with experiment data. From


vi

that, we can claim that experiment environment is confident already to test every
new algorithms as well as new data in future if possible.


vii

MỤC LỤC

TÓM TẮT

iii

ABSTRACT

v

MỤC LỤC


Đối tƣợng và phạm vi nghiên cứu

2

5.

Phƣơng pháp nghiên cứu

3

CHƢƠNG 1: TỔNG QUAN

4

1.1. Giới thiệu

4

1.2. Tổng quan về khai thác dữ liệu

5

1.3. Khai thác tập có ích

9

1.4. Cấu trúc luận văn
CHƢƠNG 2: CƠ SỞ LÝ THUYẾT

14

3.2.3. Thuật toán Two-Phase

37

3.2.4. Cấu trúc cây IT-tree và các lớp tƣơng đƣơng

40

3.2.5. Thuật toán Diffset-Two-Phase

43

3.3. Các thuật toán theo cấu trúc dàn kết hợp cấu trúc utiity-list

45

3.3.1. Thuật toán Hui-Miner

48

3.3.2. Thuật toán FHM

50

3.4. Thực nghiệm
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN

52
62


Transaction

Giao tác, giao dịch

Count

Count

Số lƣợng

Item

Item

Mục

Itemset

Itemset

Tập mục

Profit

Profit

Lợi nhuận

FIM


Cây WIT – Tree

TWU – Mining

Thuật toán TWU – Mining

HUI-MINER

High Utility Itemset Miner

Giải thuật Hui-Miner

FHM

Fast High –utility Miner

Giải thuật FHM

EUCS

Estimated Utility

Cấu trúc EUCS

Co-Occurrence Structure

Weighted Itemset – Tidset
Tree
Transaction Weighted
Utility Mining

Bảng 2.4: Các phép đo độ quan tâm dựa trên độ có ích

30

Bảng 2.5: Tầm quan trọng ngữ nghĩa của hàm tính độ có ích

31

Bảng 2.6: Các phép đo độ quan tâm dựa trên độ có ích

31

Bảng 2.7: Các tính chất toán học của các phép đo dựa trên độ có ích.

33

Bảng 3.1: Cơ sở dữ liệu giao tác

34

Bảng 3.2: Lợi nhuận đơn vị cho các item

35

Bảng 3.3: Một thành phần trong danh sách utility-list

47

Bảng 3.4: Minh họa bảng EUCS


36

Hình 3.2: Cấu trúc của các tập item của Bảng 1.1 và 1.2, với minutil = 150.

39

Hình 3.3: Cây tìm kiếm IT-tree và các lớp tƣơng đƣơng

41

Hình 3.4: Search tree using WIT-tree

42

Hình 3.5: SPMF ban đầu

43

Hình 3.6: SPMF có cài đặt thêm thuật toán Diffset-Two-Phase

44

Hình 3.7: Minh họa Diffset

45

Hình 3.8: Minh họa cách mở rộng itemset từ các item.

46


57

Hình 3.17: Đồ thị minh họa cho dữ liệu Mushroom*

57

Hình 3.18: Đồ thị minh họa cho dữ liệu Pumsb

58

Hình 3.19: Đồ thị minh họa cho dữ liệu Pumsb*

58

Hình 3.20: Đồ thị minh họa cho dữ liệu Connect

59

Hình 3.21: Đồ thị minh họa cho dữ liệu Connect*

59


xii

Hình 3.22: Đồ thị minh họa cho dữ liệu Accidents

60

Hình 3.23: Đồ thị minh họa cho dữ liệu Accidents*

đun và các giai đoạn thực hiện đều khó và phức tạp. Nhƣng cốt lõi hơn hết là việc
xử lý dữ liệu lớn hiệu quả. Vì vậy, tác giả ƣu tiên tập trung nghiên cứu các thuật
toán tìm tập các mặt hàng mang lại lợi ích nhất cho cửa hàng đó.
Đóng góp chính của luận văn

2.
-

Xác định mã nguồn và cấu trúc dữ liệu của từng thuật toán đã cài đặt trên
SPMF nhƣ mô tả trong các bài báo đã công bố để xác định độ tin cậy của
công cụ SPMF.

-

Xác định đƣợc thuật toán Two-Phase trong SPMF cài đặt không đúng với bài
báo ban đầu (cài đặt theo cây WIT-tree)

-

Cài đặt bổ sung thuật toán Diffset-Two-Phase (mở rộng của Two-Phase có
dùng thêm tính chất Diffset của Zaki)

-

Thực nghiệm lại tất cả các thực nghiệm đã đƣợc thực hiện trong các công
trình công bố để xác định tính đúng đắn của thuật toán.


2




Các thuật toán về khai thác tập mục lợi ích cao nhƣ: Two-Phase, TWUMINING, Diffset-Two-Phase, HUI-Miner, FHM


4.2.

Dữ liệu thử phổ biến nhƣ: chess, mushroom, pumsb, connect, accidents.

Phạm vi nghiên cứu


Vì có nhiều khó khăn và hạn chế khách quan, nên giai đoạn này tác giả
tìm hiểu các thuật toán khai thác tập có ích cao trên dữ liệu tĩnh (dữ liệu
không có biến động), dữ liệu nghiên cứu đƣợc lấy từ nguồn dữ liệu
nghiên cứu chuẩn (chƣa thử nghiệm trên dữ liệu thực), việc đánh giá chỉ
mới đánh giá dựa trên tốc độ xử lý dữ liệu của các thuật toán (chƣa đánh
giá tính có ích thực sự so với ý kiến thực của khách hàng). Việc xử lý dữ
liệu theo hƣớng tập trung (chƣa nghiên cứu hƣớng phân tán)


3



Các thuật toán chính để tìm hiểu gồm những thuật toán phổ biến và đƣợc
công cụ SPMF cài đặt bao gồm: Two – Phase, Hui – Miner, FHM.




4

CHƢƠNG 1
TỔNG QUAN
1.1.

Giới thiệu
Trong thực tế, một doanh nghiệp bán lẻ cần xác định khách hàng nào có khả

năng có giá trị nhất (khách hàng đóng góp phần lớn lợi nhuận cho công ty). Đây là
những khách hàng, họ có thể mua những món hàng có giá sẵn, những món hàng lợi
nhuận cao, hoặc những món hàng sành điệu, hầu hết khách hàng không mua những
món hàng này mà chỉ có số ít khách hàng mua nên thông tin về những món hàng
nhƣ vậy xuất hiện rất ít trên cơ sở dữ liệu giao tác, nhƣng những món hàng này
mang lại lợi nhuận cao. Trong khai thác luật kết hợp truyền thống, các giao tác thể
hiện khách hàng có thể có lợi ích cao bị bỏ sót. Ví dụ, {sữa, bánh mì} có thể là một
tập phổ biến với độ hỗ trợ 40%, đóng góp 4% tổng lợi ích, và khách hàng tƣơng
ứng thuộc nhóm A, trong khi {bánh sinh nhật, thiệp sinh nhật} có thể là tập không
phổ biến với độ hỗ trợ 8% (giả sử ngƣỡng độ hỗ trợ là 10%), đóng góp 8% tổng lợi
ích, và khách hàng tƣơng ứng thì thuộc nhóm B. Các chuyên gia thị trƣờng phải
quan tâm hơn trong vấn đề tiếp thị bán hàng {bánh sinh nhật, thiệp sinh nhật} bằng
cách thiết kế chiến dịch tiếp thị hoặc thiết kế vé khuyến mãi cho khách hàng nhóm
B (các khách hàng mang nhiều lợi ích), dù itemset này bị bỏ quên trong khai thác
luật kết hợp.
Một ví dụ khác là dữ liệu web log. Một chuỗi các trang web do ngƣời dùng
ghé thăm có thể đƣợc xem nhƣ là một giao tác. Do số lần thăm một trang web và
thời gian ngƣời dùng dành cho một trang web đặc biệt nào đó thì khác nhau, nên
tổng thời gian mà ngƣời dùng dành cho một trang có thể đƣợc xem là độ có ích.
Những ngƣời thiết kế website có thể nắm bắt sự quan tâm và các hành vi của khách
hàng bằng cách nhìn vào độ có ích của các kết hợp trang rồi xem xét việc tái tổ

1.2.1. Khai thác dữ liệu [1, 2, 3, 7]
Khai thác dữ liệu – Data Mining (KTDL) là một quá trình trích xuất tri thức
từ lƣợng lớn dữ liệu. KTDL đó là tiến trình trích lọc, sản sinh những tri thức hoặc
các mẫu tiềm ẩn, chƣa biết nhƣng hữu ích từ các CSDL lớn. KTDL là tiến trình khái
quát các sự kiện rời rạc trong dữ liệu thành các tri thức mang tính khái quát, tính
quy luật hỗ trợ tích cực cho các tiến trình ra quyết định.


6

Tăng khả năng hỗ trợ
quyết định kinh doanh
Ngƣời dùng

Ra quyết
định

Nhà phân tích
kinh doanh

Trình bày dữ liệu
Các công cụ trực quan

Mẫu kết quả
Data Mining

từ khai thác dữ

Khảo sát dữ liệu


KTDL cho phép ngƣời ra quyết định kinh doanh hỏi và trả lời cho những câu hỏi
nhƣ là “Ai là khách hàng chính yếu của công ty đối với một mặt hàng cụ thể?” hoặc
“Dòng sản phẩm nào sẽ bán trong khu vực này và ai sẽ mua chúng, dựa vào việc
bán những sản phẩm tƣơng tự ở ở khu vực đó?”.Vị trí của KTDL đƣợc thể hiện qua
sơ đồ ở hình 1.1
Đánh giá mẫu và biểu
diễn tri thức

Tri
thức

Khai thác dữ liệu

Chọn lọc dữ liệu

Làm sạch dữ liệu
Các nguồn
dữ liệu

Kho dữ
liệu

Dữ liệu cụ
thể sẽ đƣợc
khai thác
Biến đổi dữ liệu

Tích hợp dữ liệu

Hình 1.2: Quá trình khám phá tri thức từ CSDL

với:
 Các nguồn dữ liệu
 Kho dữ liệu
 Dữ liệu cụ thể sẽ đƣợc khai thác
 Mẫu kết quả từ khai thác dữ liệu
 Tri thức đạt đƣợc
1.2.2. Các ứng dụng của Khai thác dữ liệu [3, 4]
Khai thác dữ liệu đƣợc ứng dụng rộng rãi trong rất nhiều lĩnh vực nhƣ [2,3]:
a. Ngân hàng
 Xây dựng mô hình dự báo rủi ro tín dụng
 Tìm kiếm tri thức, quy luật của thị trƣờng chứng khoán và đầu tƣ bất
động sản


9

b. Thƣơng mại điện tử
 Công cụ tìm hiểu, định hƣớng, thúc đẩy, giao tiếp với khách hàng
 Phân tích khách hàng duyệt web
 Phân tích hành vi mua sắm trên mạng và cho biết thông tin tiếp thị phù
hợp với loại khách hàng trong một phân khu thị trƣờng nhất định
c. Công nghệ sinh học và dƣợc phẩm
Xây dựng công cụ KTDL trực quan cho phép phát hiện sự hiện diện
của dƣợc chất, phân tích dữ liệu di truyền.
d. Nhân sự
 Giúp nhà tuyển dụng chọn ứng viên thích hợp nhất theo nhu cầu của
công ty.
 Phát hiện giả mạo thẻ trong lĩnh vực viễn thông
 Phát hiện dùng thẻ tín dụng giả trên mạng và là công cụ hữu ích cho
dịch vụ quản lý rủi ro cho thƣơng mại điện tử