Phương pháp khai thác theo chiều ngang để trích xuất các tập phổ biến

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC THÀNH PHỐ HỒ CHÍ MINH

NGUYỄN QUÝ TÍN

PHƯƠNG PHÁP KHAI THÁC THEO CHIỀU NGANG ĐỂ TRÍCH XUẤT CÁC TẬP PHỔ BIẾN

LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN

Mã số: 60480201

TP. HỒ CHÍ MINH – tháng 06 năm 2019

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC THÀNH PHỐ HỒ CHÍ MINH

NGUYỄN QUÝ TÍN

PHƯƠNG PHÁP KHAI THÁC THEO CHIỀU NGANG ĐỂ TRÍCH XUẤT CÁC TẬP PHỔ BIẾN

LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN

Mã số: 60480201

NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. CAO TÙNG ANH

TP. HỒ CHÍ MINH – tháng 06 năm 2019

CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI

TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC THÀNH PHỐ HỒ CHÍ MINH

Người hướng dẫn khoa học: TS. Cao Tùng Anh

- Học viên đã bảo vệ thành công luận văn ngày 04 tháng 06 năm 2019, tại Hội đồng đánh giáluận văn thạc sĩ thành lập theo Quyết định số …. ngày …. /…./2019 của Hiệu trưởng Trường ĐH Ngoại ngữ -Tin học TP.HCM, với sự tham gia của:

Chủ tịch Hội đồng: PGS.TS. Phạm Thế Bảo Phản biện 1: TS. Trần Minh Thái

Phản biện 2: PGS.TS. Lê Hoàng Thái

Ủy viên: PGS.TS Nguyễn Thanh Bình

Thư ký: TS. Nguyễn Đức Cường

- Có thể tìm hiểu Luận văn tại Thư viện Trường ĐH Ngoại ngữ-Tin học TP HCM, hoặc trên cổng thông tin điện tử, website của đơn vị quản lý sau đại học của Trường.

LỜI CAM ĐOAN

Tôi xin cam đoan nội dung của luận văn này là công trình nghiên cứu của chính bản thân tôi. Tất cả các tài liệu tham khảo từ các nghiên cứu có liên quan đều đã được nêu rõ nguồn gốc trong phần tài liệu tham khảo. Các số liệu, kết quả nêu trong luận văn do tôi tự thực nghiệm.

Tác giả luận văn

Nguyễn Quý Tín

LỜI CẢM ƠN

Tôi xin bày tỏ lòng biết ơn sâu sắc đến Thầy, TS. Cao Tùng Anh, người đã hết lòng hướng dẫn, động viên và giúp đỡ cho tôi hoàn thành luận văn này.

Tôi cũng xin chân thành gửi lời cám ơn đến quý Thầy Cô trường Đại Học Ngoại ngữ - Tin học TP.HCM đã tận tình dạy dỗ, chỉ bảo kiến thức quý báu giúp tôi hoàn thành khóa học đúng tiến độ và là nền tảng cho nghiên cứu của mình. Xin cảm ơn Ban Hợp tác và Đào tạo Sau đại học đã nhiệt tình hỗ trợ trong suốt quá trình học tập tại trường.

Cuối cùng, xin chân thành cảm ơn cha mẹ, vợ, bạn bè và đồng nghiệp đã khích lệ, động viên, tạo điều kiện thuận lợi cho tôi trong suốt thời gian thực hiện luận văn.

TP. HCM, tháng 06 năm 2019 Tác giả luận văn

Nguyễn Quý Tín

TÓM TẮT

Khai thác tập phổ biến là một trong những phương pháp khai thác dữ liệu quan trọng nhất được sử dụng rộng rãi để trích xuất các quy tắc kết hợp hiệu quả từ khối lượng lớn dữ liệu. Một số thuật toán đã được đề xuất để khai thác các tập phổ biến như: Apriori, FP-Growth,… được áp dụng trong nhiều lĩnh vực. Vì thuật toán khai thác tập phổ biến truyền thống tạo ra một số lượng lớn các tập phổ biến. Hơn nữa, sự bùng nổ tổ hợp của các tập hợp trong bộ dữ liệu rất lớn làm khó khăn thêm trong khai thác. Trong luận văn này sẽ nghiên cứu cài đặt một thuật toán hiệu quả hơn, để tiến hành khai thác các tập phổ biến trong các tập dữ liệu rất lớn. Thuật toán Mining Row Item Horizontal (MRIH), sử dụng phương pháp khai thác từ dưới lên theo chiều ngang để thiết lập một sự cân bằng giữa kích thước ngang và dọc của cơ sở dữ liệu đầu vào của mỗi cấp khai thác. Với mục đích này, mỗi cơ sở dữ liệu sẽ được sắp xếp theo thứ tự tăng dần độ phổ biến của các hạng mục. Trong thuật toán, cơ sở dữ liệu giao tác chính được chia thành một số cơ sở dữ liệu nhỏ hơn và do đó giảm kích thước của vấn đề khai thác ở mỗi cấp. Kết quả thử nghiệm cho thấy rằng thuật toán đạt được hiệu quả khai thác tốt trên một số các tập dữ liệu đầu vào khác nhau. Hơn nữa, nghiên cứu về hiệu suất cho thấy rằng thuật toán này tốt hơn đáng kể.

DANH MỤC CÁC KÝ HIỆU VIẾT TẮT

KÍ HIỆU

Ý NGHĨA TIẾNG ANH	Ý NGHĨA TIẾNG VIỆT
BFS	Breadth First Search	Tìm kiếm theo chiều rộng
cond	Conditional	Điều kiện
CSDL	Database	Cơ sở dữ liệu
DB	Transaction database of conditional database	Cơ sở dữ liệu giao tác có điều kiện
DB\|i	Transaction database of conditional database i	Cơ sở dữ liệu giao tác có điều kiện i
DFS	Depth-first search	Tìm kiếm theo chiều sâu
F.C.I	Frequent closed itemset	Tập phổ biến đóng
FI	Frequent Itemset	Tập phổ biến
FP-array	Frequent Pairs Array	Mảng phổ biến
FP-Tree	Frequent Pattern Tree	Cây phổ biến
Item	Items	Hạng mục
Itemset	Itemset	Tập hạng mục
minsup	Minsup	Độ phổ biến tối thiểu
MRIH	Mining Row Item Horizontal	Thuật toán khai thác theo phương pháp ngang
PIETM	Principle of Inclusion– Exclusion and Transaction Mapping	Thuật toán khai thác tập phổ biến dựa trên nguyên lý Bao gồm - Loại trừ và ánh xạ giao tác
rowset	Rowset	Tập dòng
sup	Support	Độ phổ biến
TDB	Transaction Database	Cơ sở dữ liệu giao tác
tid	Transaction ID	Mã giao tác
tid-list	Transaction ID-List	Danh sách mã giao tác