ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA
HUỲNH TRIỆU VỸ
NGHIÊN CỨU VÀ PHÁT TRIỂN MỘT SỐ KỸ
THUẬT CHE GIẤU THÔNG TIN NHẠY CẢM
TRONG KHAI PHÁ HỮU ÍCH CAO
Chuyên ngành : KHOA HỌC MÁY TÍNH
Mã số : 9480101
TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT
Đà Nẵng, 02/2023
Công trình được hoàn thành tại
TRƯỜNG ĐẠI HỌC BÁCH KHOA
Người hướng dẫn khoa học:
1. TS. Trương Ngọc Châu
2. TS. Lê Quốc Hải
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 cấp
Trường, Trường Đại học Bách khoa
Vào hồi … giờ … ngày … tháng … năm 20....
Có thể tìm hiểu luận án tại:
- Thư viện quốc gia Việt Nam.
- Trung tâm Học liệu và Truyền thông, Trường Đại học Bách khoa,
Đại học Đà Nẵng.
1
MỞ ĐẦU
1. Đặt vấn đề
Ngày nay, với sự phát triển nhanh chóng của ứng dụng công nghệ thông
tin trong hầu hết các lĩnh vực, lượng dữ liệu từ các hệ thống thông tin, ứng
dụng ngày càng gia tăng và được lưu trữ thành các kho dữ liệu lớn. Các
phương pháp khai thác dữ liệu truyền thống không còn đáp ứng đầy đủ
những yêu cầu về phân tích, đánh giá, dự đoán, dự báo dựa trên dữ liệu. Do
đó, kỹ thuật phát hiện tri thức trong cơ sở dữ liệu (CSDL) đã ra đời nhằm
giải quyết bài toán khai phá dữ liệu đang được áp dụng một cách rộng rãi
trong nhiều lĩnh vực khác nhau của đời sống. Mục đích của khai phá dữ liệu
(KPDL) là khám phá tri thức nhằm tìm ra những mẫu mới, những thông tin
tiềm ẩn mang tính dự đoán chưa được biết đến, có khả năng mang lại lợi ích
cho người sử dụng, trong đó quan trọng nhất là tìm ra các mẫu chứa đựng
những thông tin có thể hỗ trợ ra quyết định tồn tại trong CSDL. Có nhiều
kỹ thuật đã được nghiên cứu và đề xuất trong KPDL. Một trong những kỹ
thuật quan trọng được ứng dụng rộng rãi là khai phá tập mục thường xuyên
và luật kết hợp.
Trong khai phá tập mục thường xuyên vai trò của các mục xuất hiện
trong các giao tác là như nhau. Mỗi mục không thể xuất hiện nhiều hơn một
lần trong mỗi giao tác. Tập mục xuất hiện phổ biến hơn trong CSDL sẽ có ý
nghĩa hơn đối với người dùng. Như vậy, các tập mục thường xuyên khai
thác được chỉ mang ngữ nghĩa thống kê nên nó chỉ đáp ứng một phần nhu
cầu ứng dụng thực tiễn. Chẳng hạn như nhà kinh doanh quan tâm đến tần
suất xuất hiện đồng thời của các mặt hàng trong cùng một giao dịch của
khách hàng thì có thể sử dụng kỹ thuật khai thác tập mục thường xuyên để
dự đoán xu thế mua sắm của khách hàng. Tuy nhiên, nhà quản lý có thể cần
đến những thông tin chi tiết hơn như lợi ích mang lại của một hoặc một
nhóm mặt hàng được khách hàng mua sắm cùng nhau trong một giao dịch.
Khai phá tập mục thường xuyên không đáp ứng được điều này. Chính vì
điều này mà một khái niệm mới ra đời, đó là Khai phá hữu ích cao, tức là có
xét đến yếu tố hữu ích của mỗi mục trong CSDL (ví dụ: số lượng, lợi nhuận
của mỗi mặt hàng trong mỗi giao tác của CSDL).
Ngày nay, sự phát triển nhanh chóng của Công nghệ thông tin đang tạo
môi trường thuận lợi để thúc đẩy hợp tác thương mại toàn cầu và kinh
doanh xuyên quốc gia. Trong môi trường kinh doanh quốc tế, việc chia sẻ
dữ liệu giữa các đối tác hoặc công bố ra bên ngoài internet là rất cần thiết
để thúc đẩy sự phát triển. Tuy nhiên, bên trong dữ liệu có thể ẩn chứa các
thông tin riêng tư hoặc nhạy cảm (gọi chung là thông tin nhạy cảm) mà chủ
2
sở hữu không muốn tiết lộ ra bên ngoài, vì việc lộ những thông tin nhạy
cảm ra bên ngoài có thể khiến cho bên sở hữu dữ liệu đánh mất bí mật kinh
doanh hoặc lợi thế cạnh tranh,... Do đó, hiện nay có nhiều mô hình và kỹ
thuật đang được nghiên cứu để giải quyết vấn đề đặt ra, làm thế nào để cho
phép thực hiện quá trình KPDL trên các tập dữ liệu trong khi vẫn bảo vệ
được các thông tin nhạy cảm.
Như vậy, để đảm bảo các thông tin nhạy cảm không bị khai thác khi
CSDL được chia sẻ ra bên ngoài, thuật toán che giấu thông tin nhạy cảm
trong KPDL được áp dụng để sửa dữ liệu nhằm loại bỏ các mẫu dữ liệu có
thể suy luận ra các thông nhạy cảm từ kết quả KPDL. Quá trình thực hiện
che giấu thông tin nhạy cảm luôn gây ra các hiệu ứng phụ. Hiệu ứng phụ
được xác định là sự sai khác của bản thân dữ liệu và kết quả KPDL của
CSDL gốc so với CSDL sửa đổi. Như vậy, vấn đề chính cần giải quyết
trong bài toán che giấu thông tin nhạy cảm trong KPDL là đề xuất các thuật
toán che giấu được tất cả thông tin nhạy cảm nhưng giảm thiểu các hiệu
ứng phụ. Có nhiều phương pháp tiếp cận để giải quyết bài toán này: Theo
tiếp cận heuristic để thay đổi dữ liệu hoặc khóa dữ liệu; theo tiếp cận
border-based; theo tiếp cận exact,...
Để giải quyết bài toán che giấu thông tin nhạy cảm trong khai phá hữu
ích cao, năm 2010 Jieh-Shan Yeh và cộng sự đề xuất phương pháp ẩn tập
mục hữu ích cao nhạy cảm theo hướng tiếp cận heuristic để sửa CSDL gốc
với 2 thuật toán được đề xuất HHUIF (Hiding High Utility Item First
Algorithm) và MSICF (Maximum Sensitive Itemsets Conflict First
Algorithm). Dựa trên nền tảng này nhiều thuật toán hiệu quả hơn cũng được
đề xuất. Nhìn chung, hướng tiếp cận của các thuật toán đã được đề xuất đều
dựa trên hướng tiếp cận heuristic để sửa CSDL nhằm tối ưu cục bộ. Tuy
nhiên, mỗi thuật toán đều tập trung đưa ra phương pháp tối ưu cục bộ cho
một hoặc một số tiêu chí cực tiểu hiệu ứng phụ, những tiêu chí khác của
hiệu ứng phụ vẫn còn cao. Chính vì vậy, việc tiếp tục nghiên cứu và đề xuất
các thuật toán che giấu thông tin nhạy cảm trong khai phá hữu ích cao hiệu
quả hơn các thuật toán hiện tại là một hướng nghiên cứu cần thiết.
Nhằm góp phần giải quyết một phần vấn đề nêu trên, nghiên cứu sinh đã
chọn đề tài "Nghiên cứu và phát triển một số kỹ thuật che giấu thông tin
nhạy cảm trong khai phá hữu ích cao" làm nội dung nghiên cứu luận án tiến
sĩ kỹ thuật của mình.
3
2. Mục tiêu nghiên cứu
Luận án được thực hiện nhằm nghiên cứu giải quyết một phần các thách
thức trong giải quyết bài toán che giấu thông tin nhạy cảm trong khai phá
hữu ích cao nhằm mục đích đảm bảo cho chủ sở hữu CSDL che giấu được
thông tin nhạy cảm khi thực hiện chia sẻ CSDL ra bên ngoài hoặc cho các
đối tác. Cụ thể hơn, luận án nhằm hướng đến hai mục tiêu chính sau:
- Thứ nhất, nghiên cứu và đề xuất các thuật toán ẩn tập mục hữu ích cao
nhạy cảm và luật kết hợp hữu ích cao nhạy cảm dựa trên kỹ thuật heuristic.
- Thứ hai, nghiên cứu và áp dụng lý thuyết Giàn để giảm hiệu ứng phụ
trong quá trình che giấu thông tin nhạy cảm trong khai phá hữu ích cao.
3. Đối tượng và phạm vi nghiên cứu
3.1. Đối tượng nghiên cứu của luận án gồm:
- Về cơ sở dữ liệu cần thực hiện che giấu thông tin nhạy cảm: CSDL
giao tác.
- Về thuật toán, gồm: Ẩn tập mục hữu ích cao nhạy cảm; ẩn tập mục hữu
ích trung bình cao nhạy cảm; ẩn tập mục hữu ích cao và phổ biến nhạy cảm;
ẩn luật kết hợp hữu ích cao nhạy cảm.
- Về cơ sở toán học: Giàn giao của tập hợp.
3.2. Phạm vi nghiên cứu của luận án:
- Thứ nhất, nghiên cứu tổng quan về khai phá hữu ích cao và che giấu
thông tin nhạy cảm trong khai phá hữu ích cao từ CSDL giao tác dựa trên
kỹ thuật heuristic để xác định các hạn chế của các thuật toán hiện tại, các
vấn đề hiện nay chưa được đề xuất và giải quyết.
- Thứ hai, dựa trên các kết quả phân tích tổng quan khai phá hữu ích cao
và che giấu thông tin nhạy cảm trong khai phá hữu ích cao dựa trên kỹ thuật
heuristic, đề xuất một số thuật toán cải tiến:
+ Đề xuất thuật toán cải tiến ẩn tập mục hữu ích cao nhạy cảm và thuật
toán ẩn tập mục hữu ích cao và phổ biến nhạy cảm.
+ Đề xuất mô hình và thuật toán ẩn tập mục hữu ích trung bình cao nhạy
cảm, ẩn luật kết hợp hữu ích cao nhạy cảm.
- Thứ ba, áp dụng các tính chất của lý thuyết Giàn để chọn mục mục tiêu
hiệu quả nhằm giảm hiệu ứng phụ của quá trình sửa dữ liệu để ẩn thông tin
nhạy cảm, cụ thể: Xây dựng giàn giao có ràng buộc của tập các tập mục
