BỘ GIÁO DỤC VÀ ĐÀO TẠO
VIỆN HÀN LÂM KHOA HỌC
VÀ CÔNG NGHỆ VIỆT NAM
HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ
……..….***…………
TRẦN HUY DƯƠNG
KHAI PHÁ MẪU DÃY CÓ TRỌNG SỐ
TRONG CƠ SỞ DỮ LIỆU DÃY
Chuyên ngành: Hệ thống thông tin
Mã số: 62 48 01 04
TÓM TẮT LUẬN ÁN TIẾN SỸ NGÀNH MÁY TÍNH
Hà Nội – 2021
Công trình được hoàn thành tại: Học viện Khoa học và Công nghệ -
Viện Hàn lâm Khoa học và Công nghệ Việt Nam
Người hướng dẫn khoa học 1: TS. Nguyễn Trường Thắng
Người hướng dẫn khoa học 2: GS.TS. Vũ Đức Thi
Phản biện 1: …
Phản biện 2: …
Phản biện 3: ….
Luận án sẽ được bảo vệ trước Hội đồng chấm luận án tiến sĩ, họp tại Học
viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt
Nam vào hồi … giờ ..’, ngày … tháng … năm 201….
Có thể tìm hiểu luận án tại:
- Thư viện Học viện Khoa học và Công nghệ
- Thư viện Quốc gia Việt Nam
1
MỞ ĐẦU
1. Tổng quan
Khai phá các mẫu dãy thường xuyên là một trong những vấn đề quan trọng và được
nhiều học giả nghiên cứu trong lĩnh vực khai phá dữ liệu. Trong nhiều lĩnh vực như
khai phá văn bản, phân tích trình tự gen, chống xâm nhập mạng trái phép dựa trên phân
tích nhật ký truy cập... thì thứ tự của các mục đóng vai trò rất quan trọng. Để có thể
giải quyết vấn đề này, bài toán khai phá mẫu dãy thường xuyên đã được Agrawal và
Srikant đề xuất trong [2]. Các mẫu dãy thường xuyên không chỉ thể hiện số lần xuất
hiện của các phần tử trong nó mà còn thể hiện được thứ tự của các phần tử đó. Khai
phá mẫu dãy thường xuyên được ứng dụng trong nhiều lĩnh vực như phân tích hành vi
mua sắm, phân tích các mẫu truy cập web, phân tích thảm họa tự nhiên, phân tích sự
hình thành các chuỗi protein...
Thông thường, khai phá mẫu dãy thường xuyên cổ điển thực hiện khai phá mẫu
dãy thường xuyên mà không có thêm các thông tin mở rộng khác. Trong khi đó, việc
mở rộng các thông tin của dãy dữ liệu rất đa dạng như đưa thêm các thông tin về trọng
số của các mục trong dãy, thông tin về định lượng của các mục trong dãy, thông tin về
khoảng cách thời gian giữa các thành phần trong dãy …
Đối với các CSDL dãy có yếu tố thời gian tức là có thêm thông tin về khoảng cách
thời gian xuất hiện của các dãy dữ liệu cho phép phân tích xem sau khoảng thời gian
bao lâu thì các mẫu dãy sẽ xuất hiện. Các nghiên cứu đến nay đều tập trung phát hiện
các mẫu dãy có khoảng cách thời gian xảy ra giữa các thành phần trong các CSDL dãy
có khoảng cách thời gian, ở đó khoảng cách thời gian là giá trị số được xác định rõ
ràng.
Các thuật toán khai phá mẫu dãy cổ điển thông thường không quan tâm tới mức độ
quan trọng của từng mục dữ liệu trong dãy (trọng số) cũng như số lượng dữ liệu của
từng mục dữ liệu trong dãy (định lượng) . Tuy nhiên trên thực tế, mỗi dãy dữ liệu đều
có độ quan trọng khác nhau bao gồm cả giá trị lợi ích trong (định lượng) và lợi ích
ngoài (trọng số) của các dãy dữ liệu trong CSDL.
Đến nay chưa có nhiều các nghiên cứu về khai phá mẫu dãy có trọng số trong
CSDL dãy có khoảng cách thời gian trong đó quan tâm đến cả đến trọng số của mỗi
mục trong dãy dữ liệu và khoảng cách thời gian giữa các dãy. Đồng thời cũng chưa có
nhiều nghiên cứu về khai phá mẫu dãy lợi ích cao trong CSDL dãy định lượng có
khoảng cách thời gian trong đó quan tâm đến cả đến trọng số của mỗi mục trong dãy
dữ liệu, giá trị định lượng của các mục xuất hiện và khoảng cách thời gian giữa các dãy
trong CSDL dãy định lượng có khoảng cách thời gian.
Đó là lý do đề xuất luận án “Khai phá mẫu dãy có trọng số trong Cơ sở dữ liệu
dãy”. Luận án đề xuất và giải quyết vấn đề về khai phá mẫu dãy thường xuyên trọng
số trong CSDL dãy có khoảng cách thời gian và khai phá mẫu dãy lợi ích cao trong
CSDL dãy định lượng có khoảng cách thời gian. Việc nghiên cứu giải quyết những vấn
đề đó là thực sự cần thiết không chỉ ở phương diện phát triển lý thuyết mà cả ở phương
diện ứng dụng thực tế.
2
2. Mục tiêu và phạm vi nghiên cứu của luận án
Mục tiêu của luận án là đề xuất giải pháp khai phá các mẫu dãy có trọng số có
khoảng cách thời gian giữa các dãy trong các CSDL dãy có khoảng cách thời gian và
CSDL dãy định lượng có khoảng cách thời gian.
Cụ thể luận án tập trung đề xuất các giải pháp nhằm:
• Phát hiện các mẫu dãy có trọng số trong các CSDL dãy khoảng cách thời gian. Các
mẫu dãy tìm được khi đó được gọi là mẫu dãy thường xuyên trọng số với khoảng
cách thời gian.
• Phát hiện các mẫu dãy có trọng số trong các CSDL dãy định lượng có khoảng cách
thời gian. Các mẫu dãy tìm được khi đó được gọi là mẫu dãy thường xuyên lợi ích
cao với khoảng cách thời gian.
NCS tập trung vào nghiên cứu đề xuất các thuật toán mới để khai phá các mẫu dãy
thường xuyên; chứng minh tính đúng đắn và tính đầy đủ, phân tích độ phức tạp tính
toán của các thuật toán; thử nghiệm và phân tích ý nghĩa của mẫu dãy thường xuyên
khai phá được.
3. Phương pháp nghiên cứu
Luận án nghiên cứu các mẫu dãy, trọng số của các mục trong dãy, khoảng cách
thời gian giữa các dãy, các CSDL dãy có khoảng cách thời gian và CSDL dãy định
lượng có khoảng cách thời gian.
Các nghiên cứu, thuật toán và phương pháp khai phá mẫu dãy hiện nay trên CSDL
dãy, CSDL dãy định lượng có các yếu tố khoảng cách thời gian, trọng số, lợi ích cao.
4. Các đóng góp của luận án
Những đóng góp chính của luận án là đề xuất và giải quyết các vấn đề sau:
• Đề xuất 01 thuật toán khai phá top-k mẫu dãy có tính đến trọng số của các mục và
khoảng cách thời gian trong các CSDL dãy có khoảng cách thời gian. Kết quả công
trình được đăng trong kết quả tại [CT1].
• Đề xuất 02 thuật toán khai phá mẫu dãy lợi ích cao có tính đến trọng số của các
mục, giá trị định lượng của mỗi mục và khoảng cách thời gian trong các CSDL dãy
định lượng có khoảng cách thời gian. Kết quả công trình được đăng trong kết quả
tại [CT2], [CT3], [CT4], [CT5].
5. Bố cục luận án
Luận án gồm phần mở đầu, 03 chương nội dung và phần kết luận:
• Phần mở đầu: Trình bày tổng quan của luận án; mục tiêu, đối tượng, phạm vi nghiên
cứu; phương pháp nghiên cứu; những đóng góp chính và cấu trúc của luận án.
• Chương 1: Tổng quan tình hình nghiên cứu và các định nghĩa về khai phá mẫu dãy
có trọng số trong CSDL dãy, trong CSDL dãy có khoảng cách thời gian và trong
CSDL dãy định lượng có khoảng cách thời gian.
• Chương 2: Khai phá mẫu dãy có trọng số trong CSDL dãy có khoảng cách thời
gian. Chương này nêu vấn đề và đề xuất 01 thuật toán khai phá top-k mẫu dãy
thường xuyên trọng số trong CSDL dãy có khoảng cách thời gian. Tính đúng đắn
và đầy đủ của thuật toán, việc thực nghiệm thuật toán trên các bộ dữ liệu thực và so
sánh với các nghiên cứu trước đó.
3
• Chương 3: Khai phá mẫu dãy lợi ích cao trong CSDL dãy định lượng có khoảng
cách thời gian. Chương này nêu đặt vấn đề và đề xuất 02 thuật toán khai phá mẫu
dãy lợi ích cao trong CSDL dãy định lượng có khoảng cách thời gian. Tính đúng
đắn và đầy đủ của thuật toán, việc thực nghiệm thuật toán trên các bộ dữ liệu thực
và so sánh với các nghiên cứu trước đó.
• Phần kết luận: Trình bày một số kết luận những đóng góp của luận án, hướng phát
triển và những vấn đề quan tâm của NCS.
TỔNG QUAN KHAI PHÁ MẪU DÃY CÓ TRỌNG SỐ TRONG
CƠ SỞ DỮ LIỆU DÃY
Chương này trình bày tổng quan và những định nghĩa cơ bản những vấn đề khai
phá các mẫu dãy trong CSLD dãy, mẫu dãy có trọng số trong CSDL dãy, mẫu dãy
trong CSDL dãy định lượng và mẫu dãy trong CSDL dãy có khoảng cách thời gian.
Chương này cũng chỉ ra các khoảng trống chưa được giải quyết để từ đó xác định vấn
đề nghiên cứu của luận án.
1.1. Khai phá mẫu dãy trong các CSDL dãy
CSDL dãy SDB: Gọi I={i1, i2, …, in} là tập hợp các mục duy nhất. Một tập con
khác rỗng của I được gọi là một tập mục. Một dãy dữ liệu S là một danh sách sắp xếp
theo thứ tự của các tập mục, ký hiệu 𝑆=〈(𝑠1),(𝑠2),…,(𝑠𝑚)〉, trong đó sj là một tập
mục hay một phần tử của dãy (𝑠𝑗⊆𝐼) .
Một cơ sở dữ liệu dãy SDB là một bộ <sid, Sk>, trong đó sid là một định danh của
dãy và Sk là một dãy dữ liệu.
Kích thước của dãy: dãy 𝑆=〈(𝑠1),(𝑠2),…,(𝑠𝑚)〉 được ký hiệu |S| là tổng số dãy
sj trong dãy S. Ví dụ: dãy S= <(a)(abd)(f)(a)(d)> có kích thước |S| =5.
Độ dài của dãy: dãy 𝑆=〈(𝑠1),(𝑠2),…,(𝑠𝑚)〉 trong đó sj là một tập mục hay một
phần tử của dãy (𝑠𝑗⊆𝐼) được ký hiệu l(S) là tổng số mục 𝑖𝑗∈𝐼 có trong dãy S. Một
dãy có độ dài l được gọi là l-sequence. Ví dụ: dãy S= <(a)(abd)(f)(a)(d)> có độ dài là
l(S) =7.
Dãy con và dãy chứa: Dãy α=〈(𝑆1),(𝑆2),…,(𝑆𝑚)〉 được gọi là dãy con của dãy
𝛽=〈(𝑆′1),(𝑆′2),…,(𝑆′𝑚),…,(𝑆′𝑛)〉 nếu và chỉ nếu 𝑆𝑖⊆𝑆′𝑖 Ký hiệu là 𝛼≼𝛽. Dãy
β cũng được gọi là dãy chứa của dãy α. Ví dụ: Dãy <(abd)(f)> và dãy <(ab)(d)> là một
trong các dãy con của dãy chứa <(a)(abd)(f)(a)(d)> .
Độ hỗ trợ của dãy: Độ hỗ trợ (tuyệt đối) của dãy α trong CSDL dãy SDB là tổng
số dòng có chứa α trong SDB, ký hiệu là sup(α).
𝑠𝑢𝑝(𝛼)=|{𝛼|𝛼≼𝑆𝑖∧𝑆𝑖∈𝑆𝐷𝐵}|
Một dãy α được gọi là mẫu dãy thường xuyên khi và chỉ khi độ hỗ trợ của α không
nhỏ hơn độ hộ trợ cực tiểu minsup cho trước, tức là sup(α) minsup.
Các thuật toán khai phá mẫu dãy thường xuyên trong các CSDL dãy thường được
thực hiện theo các phương pháp sau:
• Thực hiện sinh mẫu dãy bằng phương pháp tìm kiếm theo bề rộng (breath-first
search). Các thuật toán điển hình nhất được phát triển theo cách tiếp cận này gồm
AprioriAll[2], GSP[10]...
