Tóm tắt Luận án Tiến sĩ Kỹ thuật: 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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

11
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tóm tắt Luận án Tiến sĩ Kỹ thuật "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" được nghiên cứu với mục tiêu là: 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; 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án Tiến sĩ Kỹ thuật: 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

ĐẠ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
4 hữu ích cao và phổ biến, từ giàn giao này xây dựng thuật toán chọn mục mục tiêu cho quá trình sửa CSDL để ẩn tập mục hữu ích cao và phổ biến nhạy cảm nhằm giảm hiệu ứng phụ. 4. Phương pháp nghiên cứu Phương pháp lý thuyết và phương pháp thực nghiệm 5. Ý nghĩa khoa học và thực tiễn của đề tài Luận án nghiên cứu có ý nghĩa khoa học và giá trị thực tiễn, đóng góp mới trong lĩnh vực nghiên cứu về che giấu thông tin nhạy cảm trong khai phá hữu ích cao nhằm góp phần giải quyết bài toán bảo vệ các thông tin nhạy cảm của cá nhân và tổ chức trong CSDL. 6. Bố cục của luận án Luận án được tổ chức thành ba chương và mở đầu, kết luận Chương 1: 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. Chương này trình bày 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 để làm cơ sở đề 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 dựa trên kỹ thuật heuristic ở chương 2. Ngoài ra, trong chương này cũng giới thiệu tổng quan về ứng dụng lý thuyết Giàn trong KPDL, là một cơ sở toán học mà luận án này tập trung nghiên cứu để ứng dụng vào việc tối ưu hóa thuật toán che giấu thông tin nhạy cảm trong khai phá hữu ích cao được trình bày ở chương 3. Chương 2: 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. Phần đầu của chương trình bày về vấn đề che giấu thông tin nhạy cảm trong khai phá hữu ích cao. Phần còn lại, tập trung vào trình bày các mô hình và thuật toán cải tiến để che giấu thông tin nhạy cảm trong khai phá hữu ích cao, cụ thể: Thuật toán ẩn tập mục hữu ích cao nhạy cảm; thuật toán ẩn tập mục hữu ích cao và phổ biến nhạy cảm; thuật toán ẩn tập mục hữu ích trung bình cao nhạy cảm; thuật toán ẩn luật kết hợp hữu ích cao nhạy cảm. Chương 3: Che giấu thông tin nhạy cảm trong khai phá hữu ích cao dựa trên lý thuyết Giàn. Nội dung chính của chương này trình bày một phần nội dung của lý thuyết Giàn có liên quan đến vấn đề che giấu thông tin nhạy cảm trong KPDL. Dựa trên cơ sở lý thuyết Giàn, phần tiếp theo của chương xây dựng Giàn giao có ràng buộc của tập các tập mục hữu ích cao và phổ biến. Dựa trên các giàn Giao này, đề xuất các thuật toán tìm mục
5 mục tiêu dựa trên Giàn giao có ràng buộc của tập các tập mục hữu ích cao và phổ biến để cải tiến thuật toán ẩn tập mục hữu ích cao và phổ biến đã đề xuất ở chương 2. 7. Đóng góp chính của luận án Luận án đã đạt được một số kết quả nghiên cứu và cũng là các đóng góp chính sau đây: 1) Đề 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 dựa trên kỹ thuật heuristic, bao gồm: - Thuật toán ẩn tập mục hữu ích cao nhạy cảm. Có ba kết quả nghiên cứu được công bố trong kỷ yếu hội nghị và tạp chí: (1) Kỷ yếu Hội thảo quốc tế INISCOM, xuất bản bởi Springer, năm 2018; (2) Tạp chí Intelligent Data Analysis (thuộc danh mục ISI, Q3), số 24, năm 2020; (3) Kỷ yếu Hội nghị Quốc gia lần thứ XV về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR’ 15), năm 2022. Xem tài liệu số 4, 6 và 9 trong danh mục các công trình của tác giả; - Thuật toán ẩn tập mục hữu ích cao và phổ biến nhạy cảm. Kết quả nghiên cứu được công bố trong Kỷ yếu Hội nghị Quốc gia lần thứ XII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR’ 13), năm 2020. Xem tài liệu số 5 trong danh mục các công trình của tác giả; - Thuật toán ẩn tập mục hữu ích trung bình cao nhạy cảm. Có hai kết quả nghiên cứu được công bố trong kỷ yếu hội nghị: (1) Kỷ yếu Hội thảo Quốc gia lần thứ XXI: Một số vấn đề chọn lọc của Công nghệ thông tin và Truyền thông, năm 2018; (2) Kỷ yếu Hội nghị Quốc gia lần thứ XIV về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR’ 14), năm 2021. Xem tài liệu số 3 và 7 trong danh mục các công trình của tác giả; - Thuật toán ẩn luật kết hợp hữu ích cao nhạy cảm. Kết quả nghiên cứu được công bố trong Kỷ yếu Hội nghị Quốc gia lần thứ X về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR’ 10), năm 2017 và Hội nghị quốc tế MAPR, xuất bản bởi IEEE, năm 2018. Xem tài liệu số 1 và 2 trong danh mục các công trình của tác giả. 2) Đề xuất thuật toán ẩn tập mục hữu ích cao và phổ biến nhạy cảm dựa trên lý thuyết giàn, cụ thể: Thuật toán ẩn tập mục hữu ích cao và phổ biến nhạy cảm dựa trên giàn giao có ràng buộc của tập các tập mục hữu ích cao và phổ biến. Kết quả nghiên cứu đã được đăng trên tạp chí Cybernetics And Information Technologies (thuộc danh mục Scopus, Q2), số 1/2022. Xem tài liệu số 8 trong danh mục các công trình của tác giả.
6 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Ừ CƠ SỞ DỮ LIỆU GIAO TÁC Nội dung chính của chương tập trung 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. Ngoài ra, việc lựa chọn một công cụ toán học để ứng dụng vào trong KPDL là quan trọng. Chính vì vậy, chương này cũng trình bày tổng quan về ứng dụng lý thuyết Giàn trong KPDL. Phần cuối của chương mô tả về các CSDL được sử dụng để chạy thực nghiệm trong các thuật toán đề xuất của luận án. Kết quả nghiên cứu của chương này là cơ sở lý thuyết nền tảng để xây dựng các thuật toán giấu thông tin nhạy cảm trong khai phá hữu ích cao được trình bày trong chương 2 và chương 3 của luận án. 1.1. Tổng quan về khai phá hữu ích cao từ CSDL giao tác Khai phá hữu ích cao là một mở rộng của khai phá tập phổ biến khi vai trò của các mục trong CSDL được xem xét đến. Cơ sở lý thuyết của mô hình khai phá hữu ích cao được đề xuất bởi Hong Yao và cộng sự năm 2004 để khai phá từ CSDL giao tác tập các tập mục thỏa mãn một ngưỡng hữu ích tối thiểu cho trước và được gọi là khai phá tập mục hữu ích cao. Cho đến nay, khai phá tập mục hữu ích cao có nhiều hướng nghiên cứu mở rộng để đáp ứng nhu cầu thực tế của xã hội: Khai phá tập mục hữu ích cao và phổ biến; khai phá tập mục hữu ích trung bình cao; khai phá luật kết hợp hữu ích cao,... Cơ sở lý thuyết của khai phá hữu ích cao Phát biểu: Cho tập hữu hạn gồm các mục 𝐼 = {𝑥1 , 𝑥2 , … , 𝑥 𝑚 }, mỗi mục 𝑥 𝑖 có một giá trị hữu ích ngoại, ký hiệu là p(𝑥 𝑖 ). Tập mục 𝑋= {𝑥1 , 𝑥2 , … , 𝑥 𝑘 }, với 𝑥 𝑖 ∈ 𝐼, 1 ≤ 𝑖 ≤ 𝑘 và k là độ dài của X. CSDL giao tác 𝐷 = {𝑇1 , 𝑇2 , … , 𝑇 𝑛 } chứa n giao tác, mỗi giao tác 𝑇 𝑐 ⊆ 𝐼 có một định danh gọi là Tid. Mỗi mục 𝑥 𝑖 trong giao tác 𝑇 𝑐 kết hợp với một trọng số gọi là hữu ích nội (số lượng), ký hiệu là q(𝑥 𝑖 ,𝑇 𝑐 ). 1.1.1.1. Khai phá tập mục hữu ích cao Khai phá tập mục hữu ích cao là quá trình khai thác từ CSDL giao tác tất cả các tập mục có giá trị hữu ích không nhỏ hơn một ngưỡng hữu ích tối thiểu cho trước. - Giá trị hữu ích của mục x trong giao tác Tc, ký hiệu u(x,Tc), được xác định: 𝑢( 𝑥, 𝑇 𝑐 ) = 𝑞( 𝑥, 𝑇 𝑐 ) ∗ 𝑝(𝑥)
7 - Giá trị hữu ích của tập mục X trong giao tác Tc, ký hiệu u(X,Tc), được xác định: 𝑢 ( 𝑋, 𝑇 𝑐 ) = ∑ 𝑥∈𝑋 𝑢(𝑥, 𝑇 𝑐 ) - Giá trị hữu ích của tập mục X trong CSDL D, ký hiệu u(X), được xác định: 𝑢( 𝑋) = ∑ 𝑋⊆𝑇 𝑐 ∧𝑇 𝑐 ∈𝐷 𝑢(𝑥, 𝑇 𝑐 ) 1.1.1.2. Khai phá tập mục hữu ích cao và phổ biến. Khai phá tập mục hữu ích cao và phổ biến là khai thác từ CSDL giao tác tất cả các tập mục thỏa mãn đồng thời ngưỡng hữu ích tối thiểu và độ hỗ trợ tối thiểu cho trước. 1.1.1.3. Khai phá tập mục hữu ích trung bình cao. Khai phá tập mục hữu ích trung bình cao là khai thác từ CSDL giao tác tất cả các tập mục thỏa mãn ngưỡng hữu ích trung bình tối thiểu cho trước. - Giá trị hữu ích trung bình của tập mục X trong giao tác T c, ký hiệu 𝑢(𝑋,𝑇 𝑐 ) au(X,Tc), được xác định: 𝑎𝑢( 𝑋, 𝑇 𝑐 ) = |𝑋| - Giá trị hữu ích trung bình của tập mục X trong CSDL D, ký hiệu au(X), được xác định: 𝑎𝑢( 𝑋) = ∑ 𝑋⊆𝑇 𝑐 ∧𝑇 𝑐 ∈𝐷 𝑎𝑢(𝑋, 𝑇 𝑐 ) 1.1.1.4. Khai phá luật kết hợp hữu ích cao Với tập mục hữu ích cao XY (𝑋 ∩ 𝑌 = ∅), luật kết hợp 𝑅: 𝑋 → 𝑌 là luật kết hợp hữu ích cao nếu độ tin cậy hữu ích của luật R không nhỏ hơn độ tin cậy hữu ích tối thiểu cho trước. - Giá trị hữu ích cục bộ của một mục x trong tập mục X tại giao tác Tc ký hiệu luv(x,X,Tc), được định nghĩa: 𝑙𝑢𝑣( 𝑥, 𝑋, 𝑇 𝑐 ) = 𝑢(𝑥, 𝑇 𝑐 )|𝑥 ∈ 𝑋 ∧ 𝑋 ⊆ 𝑇𝑐 ∧ 𝑇𝑐 ∈ 𝐷 - Giá trị hữu ích cục bộ của tập mục X trong tập mục Y tại giao tác Tc ký hiệu luv(X,Y,Tc), được định nghĩa: 𝑙𝑢𝑣( 𝑋, 𝑌, 𝑇 𝑐 ) = ∑ 𝑥∈𝑋∧𝑋⊆𝑌∧𝑌⊆𝑇 𝑐 𝑙𝑢𝑣(𝑥, 𝑋, 𝑇 𝑐 ) - Giá trị hữu ích cục bộ của tập mục X trong tập mục Y trong CSDL D, ký hiệu là luv(X,Y), được định nghĩa: 𝑙𝑢𝑣( 𝑋, 𝑌) = ∑ 𝑋⊆𝑌∧𝑌⊆𝑇 𝑐 ∑ 𝑥∈𝑋 𝑙𝑢𝑣(𝑥, 𝑋, 𝑇 𝑐 ) - Độ tin cậy hữu ích của luật𝑅: 𝑋 → 𝑌 ký hiệu uconf(R) được định 𝑙𝑢𝑣(𝑋,𝑋𝑌) nghĩa: 𝑢𝑐𝑜𝑛𝑓 ( 𝑅) = 𝑢(𝑋) Tổng quan tình hình nghiên cứu
8 Năm 2004, Hong Yao và cộng sự đã đề xuất mô hình khai phá tập mục hữu ích cao. Liu. Y và cộng sự đề xuất thuật toán hai pha TwoPhase để khai phá tập mục hữu ích cao. Đơn vị đo TWU (Transaction-Weighted-Utilization) được sử dụng để tỉa không gian tìm kiếm. Năm 2012, Liu và cộng sự đề xuất thuật toán HUI-Miner (High Utility Itemset Miner) để khai phá tập mục hữu ích cao không qua bước sinh tập ứng viên. HUI-Miner sử dụng một cấu trúc lưu trữ mới có tên gọi là utility- list để lưu trữ thông tin về hữu ích của mỗi tập mục và thông tin heuristic để phục vụ cho việc tỉa không gian tìm kiếm. Dựa trên cấu trúc utility-list nhiều thuật toán cải tiến cũng được đề xuất. Mô hình khai phá tập mục hữu ích cao dựa trên ngưỡng hữu ích tối thiểu để xác định tập các tập mục hữu ích cao nên chỉ cho biết thông tin duy nhất về giá trị hữu ích của các tập mục. Tuy nhiên, trong ứng dụng thực tế nhiều trường hợp sử dụng cần một số điều kiện khác để phục vụ tốt hơn cho các mục đích khác nhau, chính vì vậy nhiều mô hình khai phá tập mục hữu ích cao mở rộng được đề xuất, phổ biến có thể kể đến gồm: Khai phá tập mục hữu ích cao và phổ biến, khai phá tập mục hữu ích trung bình cao,... 1.2. Che giấu thông tin nhạy cảm trong khai phá hữu ích cao Các vấn đề che giấu thông tin nhạy cảm trong KPDL có thể được phân thành hai loại: Che giấu dữ liệu nhạy cảm (sensitive data); Che giấu mẫu nhạy cảm (sensitive patterns). Trong khuôn khổ của luận án này chỉ nghiên cứu về che giấu mẫu nhạy cảm trong khai phá hữu ích cao từ CSDL giao tác, cụ thể: tập mục hữu ích cao nhạy cảm; tập mục hữu ích cao và phổ biến nhạy cảm; tập mục hữu ích trung bình cao nhạy cảm và luật kết hợp hữu ích cao nhạy cảm. 1.2.1. Một số kỹ thuật che giấu thông tin nhạy cảm trong KPDL Hiện nay có rất nhiều kỹ thuật được áp dụng để phát triển thuật toán che giấu mẫu nhạy cảm trong KPDL, tuy nhiên phổ biến nhất hiện nay có thể chia ra thành ba kỹ thuật tiếp cận chính: dựa trên kỹ thuật heuristic (heuristic-based techniques); dựa trên kỹ thuật bảo vệ biên (Border-based techniques); dựa trên kỹ thuật Exact (Exact-based techniques).
9 1.2.2. Tổng quan về che giấu thông tin nhạy cảm trong khai phá hữu ích cao Mô hình che giấu thông tin nhạy cảm trong khai phá tập mục hữu ích cao từ CSDL giao tác được Jieh-Shan Yeh và cộng sự đề xuất năm 2010. Trong nghiên cứu này, các tác giả đề xuất phương pháp ẩn tập mục hữu ích cao nhạy cảm dựa trên kỹ thuật heuristic để sửa CSDL gốc nhằm giảm giá trị hữu ích của tập mục hữu ích cao nhạy cảm cần ẩn xuống thấp hơn ngưỡng hữu ích tối thiểu, bằng cách giảm giá trị hữu ích nội của mục mục tiêu hoặc xóa mục mục tiêu trong giao tác mục tiêu. 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ư: các thuật toán sửa CSDL để ẩn tập các tập mục hữu ích cao nhạy cảm dựa trên giải thuật di truyền: GA-based, PPUMGAT; các thuật toán sửa CSDL để ẩn tập các tập mục hữu ích cao nhạy cảm dựa vào lý thuyết Max-Min: MSU-MAU, MSU- MIU, SMAU, SMIU, SMSE; các thuật toán sửa CSDL để ẩn tập các tập mục hữu ích cao và phổ biến nhạy cảm dựa vào lý thuyết Max-Min: MSMU, MCRSU, HUFI,... Dựa trên các kết quả nghiên cứu được công bố trong những năm gần đây về chủ đề che giấu mẫu nhạy cảm trong khai phá hữu ích cao, kỹ thuật được áp dụng phổ biến nhất là dựa trên kỹ thuật heuristic để xáo trộn CSDL gốc. 1.2.3. Các đơn vị đo lường trong đánh giá hiệu ứng phụ của thuật toán che giấu thông tin nhạy cảm trong khai phá hữu ích cao Các thuật toán thực hiện che giấu thông tin nhạy cảm trong khai phá hữu ích cao theo hướng tiếp cận heuristic để sửa dữ liệu gốc đều để lại các hiệu ứng phụ. Để đánh giá hiệu ứng phụ do quá trình sửa dữ liệu gây ra, các nghiên cứu trước đây đã đề xuất các đơn vị đo lường: Tỷ lệ ẩn không thành công (HF - Hiding Failure); Tỷ lệ mẫu hữu ích cao bị mất (MC - Missed Cost); Tỷ lệ mẫu giả mạo (AC - Artificial Cost); Tỷ lệ tương đồng về cấu trúc dữ liệu (DSS - Database structure similarity); ): DSS là tỷ lệ tương đồng về cấu trúc của CSDL sửa đổi so với CSD; Tỷ lệ tương đồng về giá trị hữu ích của CSDL (DUS - Database utility similarity); Tỷ lệ tương đồng về giá trị hữu ích của các tập mẫu hữu ích cao(IUS - Itemsets utility similarity). 1.2. Ứng dụng lý thuyết giàn trong khai phá dữ liệu Hiện nay, trong khai phá tập phổ biến và luật kết hợp có nhiều hướng tiếp cận khác nhau với mục đích nâng cao hiệu quả trong khai phá dữ liệu. Trong các hướng tiếp cận này, hướng tiếp cận dựa trên Lý thuyết giàn là
10 một hướng tiếp cận mà các nhà nghiên cứu sử dụng đã cho ra nhiều kết quả tốt. Dựa trên các kết quả nghiên cứu, chúng ta thấy rằng lý thuyết giàn được ứng dụng rất rộng rãi và hiệu quả trong khai phá tri thức. Trong đó nổi trội nhất là ứng dụng trong bài toán khai phá luật kết hợp. Đối với bài toán che giấu thông tin riêng tư trong khai phá luật kết hợp, năm 2013 Hai Quoc Le và cộng sự đã đề xuất thuật toán ẩn luật kết nhạy cảm dựa trên giàn. Ưu điểm của thuật toán là việc tính toán để lựa chọn mục mục tiêu để sửa CSDL đựa tính toán dựa trên các tính chất của giàn, đảm bảo phương án lựa chọn là cực tiểu hóa hiệu ứng phụ. 1.3. Mô tả các CSDL giao tác được sử dụng để chạy thực nghiệm của các thuật toán trong luận án Các CSDL được lựa chọn để chạy thực nghiệm trong các thuật toán đề xuất của luận án này có các đặc tính khác nhau về: Số lượng mục trong tập I, tổng số giao tác trong CSDL, độ dài trung bình của mỗi giao tác trong CSDL, độ dài lớn nhất của giao tác trong CSDL. Các CSDL gồm: - T1000_200_40: CSDL được sinh ngẫu nhiên bởi chương trình viết bằng ngôn ngữ Java. - Foodmart, Retail, Mushroom, Chess và Chainstore: Các cơ sở dữ liệu này được lấy từ thư viên mã nguồn mở (http://www.philippe-fournier- viger.com/spmf/), đây là thư viên chia sẻ mã nguồn của hơn 226 thuật toán khai phá dữ liệu đã được công bố trên các tạp chí lớn của thế giới về lĩnh vực công nghệ thông tin, kèm theo các thuật toán là CSDL chạy thực nghiệm của hơn 226 thuật toán này. Hiện thư viện đã có hơn 1 triệu lượt truy cập. 1.4. Tổng kết chương Trong chương này đã tập trung trình bày tổng quan về vấn khai phá hữu ích cao và che giấu thông tin nhạy cảm trong khai phá hữu ích cao, cụ thể: 1) Trình bày cơ sở lý thuyết nền tảng của khai phá hữu ích cao, bao gồm khai phá tập mục hữu ích cao và các mở rộng của khai phá tập mục hữu ích cao từ CSDL giao tác; 2) Đánh giá tổng quan tình hình nghiên cứu về khai phá hữu ích cao; 3) Trình bày cơ sở lý thuyết về che giấu thông tin nhạy cảm trong KPDL, trong đó chủ yếu tập trung vào vấn đề 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 để
11 sửa đổi CSDL gốc; giới thiệu tổng quan về che giấu thông tin nhạy cảm trong khai phá hữu ích cao. Việc đánh giá tình hình nghiên cứu một cách chi tiết không được trình bày trong phần này, nhưng nội dung này sẽ được trình bày chi tiết trong chương 2. 4) Giới thiệu tổng quan về ứng dụng lý thuyết Giàn trong KPDL. Là một cơ sở toán học được vận dụng để tối ưu trong bài toán che giấu thông tin nhạy cảm trong khai phá hữu ích cao, cụ thể được trình bày trong chương 3. 5) Tập CSDL được sử dụng trong thực nghiệm của các thuật toán đề xuất của luận án cũng được mô tả trong chương này. Kết quả nghiên cứu của chương này là kiến thức nền tảng để giải quyết các vấn đề nhằm đạt được mục tiêu của luận án đã đề ra.
12 CHE GIẤU THÔNG TIN NHẠY CẢM TRONG KHAI PHÁ HỮU ÍCH CAO DỰA TRÊN KỸ THUẬT HUERISTIC 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 các thông tin nhạy cảm không bị khai thác khi CSDL được chia sẻ hoặc công bố ra bên ngoài. Chương này tập trung nghiên cứu về vấn đề che giấu thông tin nhạy cảm trong khai phá hữu ích cao nhằm mục đích đề xuất các thuật toán để ẩn thông tin nhạy cảm từ CSDL giao tác dựa trên kỹ thuật heuristic. 2.1 Quy trình che đấ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 hueristic Mô hình 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 được đề xuất vào năm 2010 để che giấu tập các tập mục hữu ích cao nhạy cảm. Nhìn chung, quy trình 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 được thực hiện qua ba bước chính sau: - Bước 1: Xác định tập các mẫu hữu ích cao nhạy cảm cần che giấu (bước này cần có sự tham gia của các chuyên gia phân tích dữ liệu) - Bước 2: Áp dụng thuật toán che giấu tập mẫu hữu ích cao nhạy cảm được xác định ở Bước 1, bước này được mô tả như sau: Với tập gồm các mẫu hữu ích cao nhạy cảm, lặp quá trình sửa đổi CSDL gốc nhằm mục đích làm cho mẫu hữu ích cao nhạy cảm không còn thỏa mãn ngưỡng tối thiểu được xác định ở Bước 1. Kết quả ở bước này là CSDL sửa đổi (sử dụng để chia sẻ hoặc công bố ra bên ngoài). - Bước 3: Đánh giá kết quả của CSDL sửa đổi trước khi công bố ra bên ngoài. 2.2. Tình hình nghiên cứu về che đấ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 2.2.1. Ẩn tập mục hữu ích cao nhạy cảm Mô hình che giấu thông tin nhạy cảm trong khai phá tập mục hữu ích cao từ CSDL giao tác lần đầu tiên được đề xuất bởi J.S. Yeh và cộng sự vào năm 2010 với hai thuật toán heuristic có tên là HHUIF (Hiding High Utility Item First Algorithm) và MSICF (Maximum Sensitive Itemsets Conflict First Algorithm). Nhược điểm của hai thuật toán này là phương pháp chọn mục mục tiêu và giao tác mục tiêu để sửa CSDL là giống nhau cho cả trường hợp xóa mục mục tiêu và sửa mục mục tiêu.
13 Năm 2014, Lin và cộng sự đề xuất thuật toán ẩn tập mục hữu ích cao nhạy cảm bằng phương pháp chèn vào CSDL gốc một số giao tác giả. Để xác định số lượng giao tác giả cần chèn vào CSDL gốc, các tác giả sử dụng thuật toán di truyền có tên là GA-based (Genetic Algorithm-based). Nhược điểm của phương pháp chèn giao tác giả là làm xuất hiện các tập mục hữu ích cao giả mạo. Cũng dựa trên giải thuật di truyền, C.W. Lin và cộng sự tiếp tục đề xuất thuật toán có tên gọi là PPUMGAT. PPUMGAT sử dụng phương pháp xóa giao tác dựa trên giải thuật di truyền. Thuật toán này có nhược điểm như thuật toán GA-based là làm phát sinh các tập mục hữu ích cao giả mạo. Năm 2016, Lin và cộng sự đề xuất hai thuật toán có tên là MSU-MAU (Maximum Sensitive Utility-Maximum item Utility) và MSU-MIU (Maximum Sensitive Utility-Minimum Item Utility). Phương pháp tiếp cận của hai thuật toán này là sửa giá trị hữu ích nội của mục mục tiêu hoặc xóa mục mục tiêu tại giao tác mục tiêu. Nhược điểm của các thuật toán là phương pháp chọn mục mục tiêu là hoàn toàn giống nhau cho cả trường hợp sửa giá trị hữu ích nội của mục mục tiêu và xóa mục mục tiêu tại giao tác mục tiêu dẫn đến làm tăng số lượng tập mục hữu ích cao không nhạy cảm bị mất. Cũng theo hướng tiếp cận tương tự, năm 2020 Xuan Liu và cộng sự đề xuất ba thuật toán heuristic, gồm: SMAU (Selecting Maximum Utility item first), SMIU (Selecting Minimum Utility item first)và SMSE (Selecting Minimum Side Effects item first). Ba thuật toán này có cùng phương pháp chọn giao tác mục tiêu (giao tác được chọn là giao tác hỗ trợ tập mục hữu ích cao nhạy cảm cần ẩn và hỗ trợ ít tập mục hữu ích cao không nhạy cảm nhất). Mục mục tiêu được chọn để sửa trong thuật toán SMAU là mục có giá trị hữu ích lớn nhất tại giao tác mục tiêu so với các mục còn lại trong tập mục hữu ích cao nhạy cảm. Ngược lại, thuật toán SMIU chọn mục mục tiêu là mục có giá trị hữu ích nhỏ nhất nhất tại giao tác mục tiêu so với các mục còn lại trong tập mục hữu ích cao nhạy cảm. Thuật toán SMSE chọn mục mục tiêu là mục xuất hiện nhiều nhất trong các tập mục hữu ích cao nhạy cảm được hỗ trợ bởi giao tác mục tiêu, trường hợp có nhiều hơn một mục được xác định thì mục mục tiêu được chọn là mục ít được hỗ trợ nhất trong số các tập mục hữu ích cao không nhạy cảm được hỗ trợ bởi giao tác mục tiêu. Nhược điểm của các thuật toán là phương pháp chọn mục mục tiêu là hoàn toàn giống nhau cho cả trường hợp sửa giá trị hữu ích nội của mục mục tiêu và xóa mục mục tiêu tại giao tác mục tiêu dẫn đến làm tăng số lượng tập mục hữu ích cao không nhạy cảm bị mất. 2.2.2 Ẩn tập mục hữu ích cao và phổ biến nhạy cảm
14 Bài toán ẩn tập mục hữu ích cao và phổ biến nhạy cảm được đề xuất bởi Rajalaxmi và cộng sự năm 2012. Trong nghiên cứu này, các tác giả đề xuất 2 thuật toán có tên gọi là MSMU (Minimum Support and Maximum Utility) và MCRSU(Maximum Conflict Ratio for Support and Utility). Phương pháp tiếp cận là sửa dữ liệu để giảm cả độ hỗ trợ và giá trị hữu ích của tập mục nhạy cảm xuống thấp hơn ngưỡng hỗ trợ tối thiểu tối thiểu và ngưỡng hữu ích tối thiểu. Nhược điểm của hai thuật toán này là làm mất nhiều tập mục không nhạy cảm do phải thực hiện sửa dữ liệu để giảm cả độ hỗ trợ và hữu ích của tập mục nhạy cảm xuống thấp hơn ngưỡng tối thiểu. Để khắc phục hạn chế này, năm 2018 X. Liu đề xuất thuật toán ẩn tập mục hữu ích cao và phổ biến nhạy cảm dựa trên kỹ thuật sửa dữ liệu gốc có tên là HUFI (Hiding Utility Frequent Itemset). Thuật toán này thực hiện lặp quá trình sửa dữ liệu cho đến khi hoặc là độ hỗ trợ hoặc là hữu ích của tập mục nhạy cảm thấp hơn ngưỡng tối thiểu. Để giảm hiệu ứng phụ tác giả đưa ra khái niệm về giá trị biên cực đại và dựa vào biên cực đại để xác định là giảm độ hỗ trợ hay giảm hữu ích để ẩn tập mục nhạy cảm là hiệu quả hơn. Tuy nhiên, phương pháp chọn giao tác mục tiêu và mục mục tiêu của thuật toán HUFI là hoàn toàn giống nhau cho cả trường hợp giảm độ hỗ trợ và giảm giá trị hữu ích để ẩn tập mục nhạy cảm. Đây là nguyên nhân làm cho phương pháp này có thể làm tăng hiệu ứng phụ. 2.2.3. Ẩn tập mục hữu ích trung bình cao nhạy cảm Những năm gần đây chủ đề khai phá tập mục hữu ích trung bình cao từ CSDL giao tác được nhiều nhà nghiên cứu quan tâm và có nhiều kết quả nghiên cứu được công bố. Song song với việc phát triển các thuật toán khai phá tập mục hữu ích trung bình cao thì việ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 trung bình cao nhằm đảm bảo thông tin nhạy cảm không thể khai thác được bởi các thuật toán khai phá tập mục hữu ích trung bình cao từ CSDL chia sẻ cho đối tác hoặc công bố ra bên ngoài là cần thiết. Tuy nhiên, với hiểu biết của tác giả luận án này cho đến thời điểm hiện tại chưa thấy các công bố nào liên quan đến vấn đề che giấu thông tin nhạy cảm trong khai phá tập mục hữu ích trung bình cao. Chính vì vậy, chương này đề 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 nhằm giải quyết bài toán che giấu thông tin nhạy cảm trong khai phá tập mục hữu ích trung bình cao. 2.2.4. Ẩn luật kết hợp hữu ích cao nhạy cảm Cũng như các tập mục hữu ích cao nhạy cảm, các luật kết hợp hữu ích cao chứa những thông tin liên quan đến chiến lược/bí mật kinh doanh cũng là những luật kết hợp hữu ích cao nhạy cảm và cần phải được che giấu
15 trước khi CSDL được chia sẻ hoặc công bố ra bên ngoài. Tuy nhiên theo hiểu biết của tác giả luận án, cho đến thời điểm hiện tại chưa thấy có công bố nào liên quan đến vấn đề ẩn luật kết hợp hữu ích cao nhạy cảm. Chính vì vậy, luận án này cũng nghiên cứu, đề xuất mô hình và thuật toán ẩn luật kết hợp hữu ích cao nhạy cảm. 2.3. Thuật toán ẩn tập mục hữu ích cao nhạy cảm đề xuất Ẩn tập mục hữu ích cao nhạy cảm theo kỹ thuật heuristic để sửa đổi CSDL gốc là một quả trình được mô tả trong Hình 3.1. Hiệu ứng phụ của quá trình này phụ thuộc vào chiến lược chọn mục mục tiêu và giao tác mục tiêu để sửa dữ liệu. Hình 3.1: Sơ đồ biểu diễn quá trình ẩn tập mục hữu ích cao nhạy cảm Thuật toán đề xuất thực hiện qua ba bước chính: (1) Xác định giao tác mục tiêu; (2) Xác định mục mục tiêu; (3) Sửa mục mục tiêu để giảm giá trị trị hữu ích nội hoặc xóa mục mục tiêu ra khỏi giao tác mục tiêu. Thuật toán đề xuất nhằm cải thiện hiệu ứng phụ của quá trình ẩn tập mục hữu ích cao nhạy cảm gây ra. Để giảm hiệu ứng phụ thuật toán đề xuất đưa ra các định lý và tính chất quan trọng chọn mục mục tiêu của quá trình cắt tỉa dữ liệu để ẩn tập mục hữu ích cao và phổ biến nhạy cảm để giảm tối đa tác động đến CSDL gốc và giảm tối đa các tập mục hữu ích cao không nhạy cảm bị ẩn nhầm.
16 Thuật toán đề xuất có độ phức tạp tính toán: 𝑂(| 𝑆𝐻𝑈𝐼| + |D| + | 𝐷𝑆| ∗ 𝑡 𝑚𝑎𝑥 + | 𝐻𝑈𝐼𝑠| ∗ 𝑡 2𝑚𝑎𝑥 ), trong đó tmax là độ dài của giao tác dài nhất trong số các giao tác chứa tập mục nhạy cảm. Kết quả thực nghiệm cũng cho thấy thuật toán đề xuất gây ra hiệu ứng phụ thấp hơn so với thuật toán hiện tại trên các CSDL thực nghiệm. Nhận xét thuật toán đề xuất: - Ưu điểm: Thuật toán đã đưa ra các chiến lược chọn mục mục tiêu và giao tác mục tiêu để sửa CSDL dựa trên tiêu chí ưu tiên giảm giá trị hữu ích nội, hạn chế số lần sửa dữ liệu và tính toán số tập mục hữu ích cao không nhạy cảm bị mất nếu như một mục ứng viên được sửa để quyết định chọn mục mục tiêu gây ra số tập mục hữu ích cao không nhạy cảm bị ẩn nhầm là ít nhất. - Nhược điểm: Thuật toán đề xuất dựa trên phương pháp heuristic để sửa CSDL nhằm hướng đến giảm hiệu ứng phụ của quá trình sửa CSDL gây ra nên chưa phải là cực tiểu hóa hiệu ứng phụ. Thuật toán có thời gian thực thi cao hơn các thuật toán còn lại khi số tập mục hữu ích cao không nhạy cảm tăng lên. 2.4. Thuật toán ẩn tập mục hữu ích cao và phổ biến nhạy cảm đề xuất Thuật toán ẩn tập mục hữu ích cao và phổ biến nhạy cảm đề xuất được mô tả trong Hình 3.2. Dựa trên các phân tích các hạn chế của các thuật toán ẩn tập mục hữu ích cao và phổ biến nhạy cảm hiện tại. Thuật toán đề xuất áp dụng các chiến lược thực hiện ẩn tập mục hữu ích cao và phổ biến và chiến lược chọn mục mục tiêu và giao tác mục tiêu dựa trên phương pháp tối ưu cục bộ để cải thiện hiệu ứng phụ so với các thuật toán hiện tại. Dựa vào đơn vị đo Biên cực đại và Biên cực tiểu để xác định chọn phương án giảm độ hỗ trợ hay giảm giá trị hữu ích để ẩn tập mục là tối ưu hơn. Khi đã xác định được phương án thuật toán đề xuất áp dụng các chiến lược chọn giao tác mục tiêu và mục mục tiêu khác nhau cho từng phương án thay vì áp dụng chung một chiến lược như các thuật toán trước đó. Phương pháp chọn giao tác mục mục tiêu và giao tác mục tiêu của thuật toán vẫn áp dụng theo hướng tiếp cận như thuật toán ẩn tập mục hữu ích cao nhạy cảm đề xuất.
17 Hình 3.2. Sơ đồ biểu diễn quá trình ẩn tập mục hữu ích cao và phổ biến nhạy cảm Thuật toán đề xuất có độ phức tạp tính toán: O(n+h*log(h)+(h+m*l)) Trong đó: n là kích thước CSDL, h = |STSi|, l = |SHUFIs|, m là độ dài lớn nhất của tập mục thuộc SHUFIs. Đối với CSDL lớn, khi giá trị của n là lớn hơn rất nhiều so với giá trị các đại lượng còn lại thì độ phức tạp tính toán của thuật toán có thể xấp xỉ O(n). Kết quả thực nghiệm trên các CSDL có đặc trưng khác nhau đều cho thấy thuật toán đề xuất có hiệu ứng phụ thấp hơn các thuật toán hiện tại. Nhận xét thuật toán đề xuất: - Ưu điểm: Thuật toán có chiến lược chọn mục mục tiêu và giao tác mục tiêu hướng đến giảm hiệu ứng phụ MC, hạn chế số lần giảm giá trị hữu ích nội hoặc xóa các mục tại một số giao tác trong CSDL. Để giảm hiệu ứng phụ MC thuật toán ưu tiên giảm giá trị hữu ích nội của mục mục tiêu hơn là xóa mục mục tiêu, đồng thời thuật toán có chiến lược chọn mục mục tiêu và giao tác mục tiêu riêng cho trường hợp giảm giá trị hữu ích nội của mục mục tiêu và xóa mục mục tiêu.
18 - Nhược điểm: Trong trường hợp phải giảm độ hỗ trợ để ẩn tập mục nhạy cảm, phương pháp chọn mục mục tiêu của thuật toán chỉ phù hợp khi số tập mục hữu ích cao và phổ biến nhạy cảm cần ẩn lớn và các tập mục này có mối quan hệ tập mục cha, tập mục con. 2.5. Thuật toán ẩn tập mục hữu ích trung bình cao nhạy cảm đề xuất Tương tự như hướng tiếp cận trong thuật toán ẩn tập mục hữu ích cao nhạy cảm đề xuất, thuật toán ẩn tập mục hữu ích trung bình cao nhạy cảm đề xuất cũng thực hiện qua 3 bước chính để thực hiện sửa dữ liệu: (1) Xác định giao tác mục tiêu; (2) Xác định mục mục tiêu; (3) Sửa mục mục tiêu. Hiệu ứng phụ của thuật toán phụ thuộc vào: (1) Xác định giá trị hữu ích nội tối thiểu cần giảm hay xóa mục; (2) Phương pháp chọn mục mục tiêu và giao tác mục tiêu. Các định lý đảm bảo đúng về mặt toán học được đưa ra để xác định chính xác giá trị hữu ích nội tối thiểu cần giảm hay xóa mục. Đồng thời để mục mục tiêu và giao tác mục tiêu nhằm giảm hiệu ứng phụ thuật toán được xây dựng trên các lập luận logic để chứng minh phương pháp chọn là giảm được hiệu ứng phụ. Thuật toán có độ phức tạp tính toán: 𝑂(| 𝐷| + |𝑛𝑜𝑛𝐻𝐴𝑈𝐼𝑠|) Kết quả thực nghiệm cho thấy thuật toán đạt đã đạt được mục tiêu là ẩn được tất cả các tập mục hữu ích trung bình cao nhạy cảm. Hiệu ứng phụ được so sánh với thuật toán của chính nhóm tác giả đã công bố năm 2018 và cho thấy hiệu ứng phụ của thuật toán đề xuất hiện tại là thấp hơn. Nhận xét thuật toán đề xuất: - Ưu điểm: Phương pháp chọn mục mục tiêu và giao tác mục tiêu hướng đến giảm số lần phải sửa CSDL và hạn chế xóa dữ liệu nhằm giảm số tập mục hữu ích cao và phổ biến không nhạy cảm bị ẩn nhầm, đồng thời hạn chế sự khác biệt giữa CSDL gốc so với CSDL sửa đổi. - Hạn chế: Do chưa tìm thấy thuật toán ẩn tập mục hữu ích trung bình cao nhạy cảm nào đã được công bố, vì vậy quá trình chạy thực nghiệm chỉ so sánh giữa thuật toán EHSHA-UI được trình bày trong luận án với thuật toán HHAUSI cũng do chính tác giả của luận án đề xuất nên chưa mang tính khách quan.