Tài liệu Luận án 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 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 LUẬN ÁN TIẾN SĨ KỸ THUẬT ĐÀ NẴNG, 02/2023 ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI 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 LUẬN ÁN TIẾN SĨ KỸ THUẬT Người hướng dẫn khoa học: 1. TS. TRƯƠNG NGỌC CHÂU 2. TS. LÊ QUỐC HẢI ĐÀ NẴNG, 02/2023 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu do tôi thực hiện, dưới sự hướng dẫn của TS. Trương Ngọc Châu và TS. Lê Quốc Hải. Tôi cam đoan các kết quả nghiên cứu được trình bày trong luận án là trung thực và không sao chép từ bất kỳ luận án nào khác. Một số nhiệm vụ nghiên cứu là thành quả tập thể và đã được các đồng tác giả đồng ý cho sử dụng. Mọi trích dẫn đều có ghi nguồn gốc xuất xứ rõ ràng và đầy đủ. Tác giả NCS. Huỳnh Triệu Vỹ i LỜI CẢM ƠN Trước tiên, tôi xin gởi lời tri ân đến thầy TS. Trương Ngọc Châu và thầy TS. Lê Quốc Hải là người trực tiếp hướng dẫn và đồng hành cùng tôi từ khi bắt đầu nghiên cứu cho đến khi hoàn thành luận án. Xin được bày tỏ lòng biết ơn đối với Quý thầy PGS-TS. Nguyễn Tấn Khôi, PGS-TS. Nguyễn Thanh Bình, PGS-TS. Võ Trung Hùng, TS. Huỳnh Hữu Hưng là những thầy đã trực tiếp giảng dạy tôi trong các chuyên đề nghiên cứu của nghiên cứu sinh. Tôi xin trân trọng cảm ơn Ban Sau Đại học - Đại học Đà Nẵng, Phòng Đào tạo Trường Đại học Bách khoa đã tạo mọi điều kiện thuận lợi cho tôi trong thời gian học tập, nghiên cứu và thực hiện luận án. Tôi xin gởi lời cảm ơn chân thành đến Ban Lãnh đạo và tập thể giảng viên Khoa Công nghệ Thông tin - Trường Đại học Bách khoa đã tạo môi trường học thuật thân thiện và tích cực cho các nghiên cứu sinh. Xin cảm ơn các đồng tác giả đã đồng ý cho tôi sử dụng các kết quả nghiên cứu chung cho luận án. Cuối cùng, tôi xin được gởi lời cảm ơn sâu sắc nhất đến gia đình và bạn bè, những người đã luôn dành cho tôi tình yêu và niềm tin, để tôi có thể vững tâm trên hành trình nhiều thách thức này. NCS. Huỳnh Triệu Vỹ ii DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ TIẾNG ANH AC Artificial Cost DUS Database Utility Similarity DSS Database Structure Similarity EHSHUI EHSHAUI GAbased HAUIM HAUIs Mẫu xuất hiện giả mạo Sự tương đồng của giá trị hữu ích giữa CSDL gốc và CSDL sửa đổi Sự tương đồng cấu trúc giữa CSDL gốc và CSDL sửa đổi Efficient algorithm for Hiding Thuật toán ẩn các tập mục hữu ích Sensitive High Utility Itemsets Efficient algorithm for Hiding Sensitive High Average-Utility Itemsets cao nhạy cảm hiệu quả Thuật toán ẩn các tập mục hữu ích trung bình cao nhạy cảm hiệu quả Thuật toán dựa trên giải thuật di Genetic Algorithm-based truyền High Average-Utility Itemset Khai phá tập mục hữu ích trung Mining bình cao High Average-Utility Itemset Tập các tập mục hữu ích trung bình cao Hiding Sensitive Utility and Ẩn tập mục hữu ích cao và phổ biến Frequent Based on Lattice nhạy cảm dựa trên giàn HUM High Utility Mining Khai phá hữu ích cao HUIM High Utility Itemset Mining Khai phá tập mục hữu ích cao HUIs High Utility Itemsets Tập các tập mục hữu ích cao HSUFIBL HURIM High Utility Rare Itemset Mining Khai phá tập mục hữu ích cao hiếm High Utility and Frequent Khai phá tập mục hữu ích cao và phổ Itemset Mining biến High Utility and Frequent Tập các tập mục hữu ích cao và phổ Itemsets biến HF Hiding Failure Mẫu nhạy cảm không ẩn được IUS Itemsets Utility Similarity HUFIM HUFIs iii Sự tương đồng của hữu ích tập mục giữa CSDL gốc và CSDL sửa đổi MC PPDM PPUM SHUIs SHAUIs SHUFIs TWU UPGrowth UP-Tree Miss Cost Mẫu bị mất Privacy Preserving Data Min- Bảo vệ tính riêng tư trong khai phá ing dữ liệu Privacy Preserving Utility Bảo vệ tính riêng tư trong khai phá Mining hữu ích cao Sensitive High Utility Itemsets Tập các tập mục hữu ích cao nhạy cảm Sensitive High Average Utility Tập các tập mục hữu ích trung bình Itemsets cao nhạy cảm Sensitive High Utility and Fre- Tập các tập mục hữu ích cao và phổ quent Itemsets biến nhạy cảm Transaction-Weighted- Trọng số hữu ích giao tác Utilization Utility Pattern Growth Mẫu hữu ích cao tăng trưởng Utility Pattern Tree Cây mẫu hữu ích cao iv DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ TIẾNG VIỆT ATMTU Ẩn tập mục hữu ích cao và phổ biến nhạy cảm tối ưu CSDL Cơ sở dữ liệu KPDL Khai phá dữ liệu v MỤC LỤC Lời cam đoan Lời cảm ơn Danh mục các từ viết tắt và thuật ngữ tiếng Anh Danh mục các từ viết tắt và thuật ngữ tiếng Việt Mục lục Danh mục bảng, biểu Danh mục hình vẽ TÓM TẮT LUẬN ÁN MỞ ĐẦU 1 TỔNG QUAN VỀ KHAI PHÁ HỮU ÍCH CAO VÀ CHE GIẤU i ii iii v vi ix x xii 1 THÔNG TIN NHẠY CẢM TRONG KHAI PHÁ HỮU ÍCH CAO TỪ CƠ SỞ DỮ LIỆU GIAO TÁC 1.1 Tổng quan về khai phá hữu ích cao từ CSDL giao tác . . . . . . . . . . 1.1.1 Cơ sơ lý thuyết của khai phá hữu ích cao . . . . . . . . . . . . . 1.1.2 Tổng quan tình hình nghiên cứu về khai phá hữu ích cao . . . . 1.2 Che giấu thông tin nhạy cảm trong khai phá hữu ích cao . . . . . . . . 1.2.1 Một số kỹ thuật che giấu mẫu nhạy cảm trong khai phá dữ liệu 1.2.2 Tổng quan về che giấu thông tin nhạy cảm trong khai phá hữu 7 7 7 12 16 17 ích cao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Các đơn vị đo lường trong đánh giá hiệu ứng phụ của thuật toán 18 che giấu thông tin nhạy cảm trong khai phá hữu ích cao . . . . Ứng dụng lý thuyết giàn trong khai phá dữ liệu . . . . . . . . . . . . . Mô tả các CSDL giao tác được sử dụng để chạy thực nghiệm của các 20 22 thuật toán trong luận án . . . . . . . . . . . . . . . . . . . . . . . . . . Tổng kết Chương 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 CHE GIẤU THÔNG TIN NHẠY CẢM TRONG KHAI PHÁ HỮU 23 24 1.2.3 1.3 1.4 ÍCH CAO DỰA TRÊN KỸ THUẬT HEURISTIC 2.1 Quy trình che giấu thông tin nhạy cảm trong khai phá hữu ích cao từ 2.2 25 CSDL giao tác dựa trên kỹ thuật heuristic . . . . . . . . . . . . . . . . Tình hình nghiên cứu về che giấu thông tin nhạy cảm trong khai phá 26 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 . . . . . . . . . . . . . . . . 27 27 vi 2.2.2 Ẩn tập mục hữu ích cao và phổ biến nhạy cảm . . . . . . . . . . 2.2.3 Ẩn tập mục hữu ích trung bình cao nhạy cảm . . . . . . . . . . 2.2.4 Ẩ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 . . . . . . . . . 2.3.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.2 Cơ sở lý thuyết của thuật toán đề xuất . . . . . . . . . . . . . . 2.3.3 Thuật toán đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.4 Ví dụ minh họa thuật toán . . . . . . . . . . . . . . . . . . . . . 2.3.5 Độ phức tạp tính toán của thuật toán . . . . . . . . . . . . . . 2.3.6 Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . 2.3.7 Nhận xét thuật toán đề xuất . . . . . . . . . . . . . . . . . . . . 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 . . . 2.4.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.2 Cơ sở lý thuyết của thuật toán đề xuất . . . . . . . . . . . . . . 2.4.3 Thuật toán đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.4 Ví dụ minh họa thuật toán . . . . . . . . . . . . . . . . . . . . . 2.4.5 Độ phức tạp tính toán của thuật toán . . . . . . . . . . . . . . 2.4.6 Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . 2.4.7 Nhận xét thuật toán đề xuất . . . . . . . . . . . . . . . . . . . . 2.5 Thuật toán ẩn tập mục hữu ích trung bình cao nhạy cảm đề xuất . . . 2.5.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.2 Cơ sở lý thuyết của thuật toán đề xuất . . . . . . . . . . . . . . 2.5.3 Thuật toán đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.4 Ví dụ minh họa thuật toán . . . . . . . . . . . . . . . . . . . . . 2.5.5 Độ phức tạp tính toán của thuật toán . . . . . . . . . . . . . . 2.5.6 Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . 2.5.7 Nhận xét thuật toán đề xuất . . . . . . . . . . . . . . . . . . . . 2.6 Thuật toán ẩn luật kết hợp hữu ích cao nhạy cảm đề xuất . . . . . . . 2.6.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . . 2.6.2 Cơ sở lý thuyết của thuật toán đề xuất . . . . . . . . . . . . . . 2.6.3 Thuật toán ẩn luật kết hợp hữu ích cao nhạy cảm đề xuất . . . 2.6.4 Ví dụ minh họa thuật toán . . . . . . . . . . . . . . . . . . . . . 2.6.5 Độ phức tạp tính toán của thuật toán . . . . . . . . . . . . . . 2.6.6 Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . 2.6.7 Nhận xét thuật toán đề xuất . . . . . . . . . . . . . . . . . . . . Tổng kết Chương 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 CHE GIẤU THÔNG TIN NHẠY CẢM TRONG KHAI PHÁ HỮU 29 30 30 30 31 31 34 38 39 40 45 46 46 47 52 54 56 56 59 60 60 60 63 64 66 66 68 70 70 71 72 73 75 76 76 77 ÍCH CAO DỰA TRÊN LÝ THUYẾT GIÀN 78 3.1 Lý thuyết giàn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 3.1.1 Quan hệ hai ngôi [14] . . . . . . . . . . . . . . . . . . . . . . . . 79 vii 3.2 3.1.2 Giàn sắp thứ tự (Lattice as orders) [14] . . 3.1.3 Giàn đại số (Lacttice as algebras) [14] . . . 3.1.4 Giàn của tập hợp [14] . . . . . . . . . . . 3.1.5 Giàn giao của tập phổ biến [37] . . . . . . Che giấu thông tin nhạy cảm trong khai phá hữu . . . . . . . . . . . . . . . . . . . . . . . . . . . . ích cao dựa . . . . . . . . . . . . . . . . . . . . trên lý 81 82 84 85 thuyết Giàn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Giàn giao của tập các tập mục hữu ích cao và phổ biến . . . . . 3.2.2 Thuật toán ẩn tập mục hữu ích cao và phổ biến nhạy cảm dựa 85 86 trên Giàn giao đề xuất . . . . . . . . . . . . 3.2.3 Ví dụ minh họa thuật toán . . . . . . . . . . 3.2.4 Độ phức tạp tính toán của thuật toán . . . 3.2.5 Kết quả thực nghiệm . . . . . . . . . . . . . 3.2.6 Nhận xét thuật toán đề xuất . . . . . . . . . Tổng kết Chương 3 . . . . . . . . . . . . . . . . . . . . . KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN DANH MỤC CÁC CÔNG TRÌNH CỦA TÁC GIẢ Tài liệu tham khảo viii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 . 90 . 93 . 93 . 96 . 104 105 107 109 DANH MỤC BẢNG, BIỂU 1.1 1.2 1.3 CSDL Giao tác D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hữu ích ngoại của CSDL D. . . . . . . . . . . . . . . . . . . . . . . . . Mô tả CSDL thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . 8 8 24 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 Tập HUIs khai thác từ CSDL D với ε = 40 . . . . . . . . . . Mô tả CSDL chạy thực nghiệm của thuật toán EHSHUI . . Tập HUFIs khai thác từ CSDL D với ε = 30 và δ = 30% . . Mô tả tập các tập mục SHUFIs . . . . . . . . . . . . . . . . Tập HAUIs khai thác từ CSDL D với β = 18 . . . . . . . . . Mô tả tập HAUIs được khai thác bởi thuật toán HAUIMiner Mô tả tập SHAUIs chạy thực nghiệm thuật toán EHSHA-UI Tập HRs khai thác từ CSDL D với ε = 40 và µ = 70% . . . Mô tả kết quả ẩn luật kết hợp hữu ích cao nhạy cảm . . . . . . . . . . . . . 39 41 54 57 66 67 67 74 76 3.1 Các thông số của tập SHUFIs . . . . . . . . . . . . . . . . . . . . . . . 94 ix . . . . . . . . . . . . . . . [25] . . . . . . . . . . . . . . . . . . . . . . . . . . . DANH MỤC HÌNH VẼ 1.1 1.2 Sơ đồ che giấu mẫu nhạy cảm trong khai phá hữu ích cao . . . . . . . . Mối quan hệ của ba loại hiệu ứng phụ khi thực hiện sửa đổi CSDL . . . 19 21 2.1 2.2 Sơ đồ biểu diễn quá trình ẩn tập mục hữu ích cao nhạy cảm . . . . . . Tỷ lệ MC giữa các thuật toán khi thực nghiệm trên các CSDL với các 32 42 2.3 tập nhạy cảm khác nhau . . . . . . . . . . . . . . . . . . . . . . . . . . Thời gian thực thi của các thuật toán khi thực nghiệm trên các CSDL 43 2.4 với các tập nhạy cảm khác nhau . . . . . . . . . . . . . . . . . . . . . . Tỷ lệ DSS giữa các thuật toán khi thực nghiệm trên các CSDL với các 44 2.5 tập nhạy cảm khác nhau . . . . . . . . . . . . . . . . . . . . . . . . . . Tỷ lệ DUS giữa các thuật toán khi thực nghiệm trên các CSDL với các 44 2.6 tập nhạy cảm khác nhau . . . . . . . . . . . . . . . . . . . . . . . . . . Tỷ lệ IUS giữa các thuật toán khi thực nghiệm trên các CSDL với các tập nhạy cảm khác nhau . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 Sơ đồ biểu diễn quá trình ẩn các tập mục SHUFIs . . . . . . . . . . . . 2.8 So sánh tỷ lệ MC giữa thuật toán HUFI và ATMTU . . . . . . . . . . 2.9 So sánh thời gian thực thi giữa thuật toán HUFI và ATMTU . . . . . . 2.10 So sánh tỷ lệ DSS giữa thuật toán HUFI và ATMTU . . . . . . . . . . 2.11 So sánh tỷ lệ DUS giữa thuật toán HUFI và ATMTU . . . . . . . . . . 2.12 Tỷ lệ IUS khi thực hiện ẩn các tập SHUFIs bởi thuật toán HUFI và 45 47 57 58 59 59 2.13 2.14 2.15 2.16 2.17 ATMTU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . So sánh tỷ lệ MC giữa thuật toán HHAUSI và EHSHA-UI . . . . . So sánh thời gian thực thi giữa thuật toán HHAUSI và EHSHA-UI So sánh tỷ lệ DSS giữa thuật toán HHAUSI và EHSHA-UI . . . . . So sánh tỷ lệ DUS giữa thuật toán HHAUSI và EHSHA-UI . . . . . Tỷ lệ IUS giữa thuật toán HHAUSI và EHSHA-UI . . . . . . . . . . . . . . . . 59 69 69 70 70 70 3.1 3.2 Giàn của tập hợp P = {a, b, c} . . . . . . . . . . . . . . . . . . . . . . . Giàn L∩H của HUFIs trong Bảng 2.3 (bên trong mỗi nút là độ hỗ 84 3.3 3.4 3.5 trợ(%)/giá trị hữu ích của nút tương ứng) . Tỷ lệ MC theo kích thước của tập nhạy cảm Tỷ lệ MC theo ngưỡng hỗ trợ . . . . . . . . Tỷ lệ MC theo ngưỡng hữu ích . . . . . . . 87 97 97 98 x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17 Tỷ lệ DSS theo kích thước của tập nhạy cảm . . Tỷ lệ DSS theo ngưỡng hỗ trợ . . . . . . . . . . Tỷ lệ DSS theo ngưỡng hữu ích . . . . . . . . . Tỷ lệ DUS theo kích thước của tập nhạy cảm . Tỷ lệ DUS theo ngưỡng hỗ trợ . . . . . . . . . . Tỷ lệ DUS theo ngưỡng hữu ích . . . . . . . . . Tỷ lệ IUS kích thước của tập nhạy cảm . . . . . Tỷ lệ IUS theo ngưỡng hỗ trợ . . . . . . . . . . Tỷ lệ IUS theo ngưỡng hữu ích . . . . . . . . . Thời gian thực thi theo kích thước của tập nhạy Thời gian thực thi theo ngưỡng hỗ trợ . . . . . Thời gian thực thi theo ngưỡng hữu ích . . . . . xi . . . . . . . . . . . . . . . . . . . . . . . . . . . cảm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 99 99 100 100 101 101 102 102 103 103 104 TÓM TẮT LUẬN ÁN Tê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. Chuyên ngành: Khoa học máy tính. Mã số: 94.80.101 Tóm tắt: Luận án đã 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, kết quả đạt được gồm: Thứ nhất, dựa trên kỹ thuật heuristic: Đề xuất 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 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; mô hình và thuật toán ẩn luật kết hợp hữu ích cao nhạy cảm. Thứ hai, đề xuất 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 để làm cơ sở xây dựng mô hình và đề xuất thuật toán ẩn tập mục hữu ích cao và phổ biến nhạy cảm. Từ khóa: Khai phá hữu ích cao, che giấu thông tin riêng tư trong khai phá hữu ích cao, giàn giao. ABSTRACT Thesis title: Research and develop a number of techniques to hide sensitive information in high utility mining. Major: Computer science. Code: 94.80.101 Abstract: The thesis has researched and developed a number of techniques to hide sensitive information in high utility mining. Namely, include: First, based on the heuristic technique propose the algorithm for hiding sensitive high utility itemset; the algorithm for hiding sensitive high utility and frequent itemsets; propose a model and algorithm for hiding sensitive high average-utility itemsets; and propose a model and algorithm for hiding sensitive high utility association rules. Second, propose a constrained intersection lattice of the high utility and frequent itemsets for proposing the sensitive high utility and frequent itemset hiding algorithm. Keywords: High utility mining, privacy-preserving utility mining, intersection lattice. xii MỞ ĐẦU 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. Đây là một kỹ thuật quan trọng nhằm phát hiện mối quan hệ giữa các mục dữ liệu trong CSDL. Việc xác định các quan hệ này không phân biệt vai trò khác nhau cũng như không dựa vào các đặc tính dữ liệu vốn có của các mục dữ liệu, mà chỉ dựa vào sự xuất hiện cùng lúc của chúng. 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. 1 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ủ 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 [2, 18, 42, 21] hoặc khóa dữ liệu [40, 36]; theo tiếp cận border-based [43, 34]; theo tiếp cận exact [33, 10, 11],... Để 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ự [53] đề 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 hai thuật toán được đề xuất là HHUIF (Hiding High Utility Item First) và MSICF (Maximum Sensitive Itemsets Conflict First). 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 [26, 23, 24, 28]. 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. 2 1. 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, luận án nhằm 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, luận án nhằm 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. 2. Đối tượng nghiên cứu Đối tượng nghiên cứu chính của luận án này 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 cao và phổ biến nhạy cảm; ẩ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. - Về cơ sở toán học: Giàn giao của tập hợp. 3. Phạm vi nghiên cứu Phạm vi nghiên cứu của luận án gồm: - 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, từ đó 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 và ẩ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 3 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 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. Ý 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 che giấu thông tin nhạy cảm của cá nhân và tổ chức trong CSDL. 5. Cấu trúc của luận án: Trên cơ sở các nhiệm vụ nghiên cứu nêu trên, để đạt mục tiêu đề ra và đảm bảo tính logic và chỉnh thể của vấn đề nghiên cứu, ngoài phần mở đầu, phần kết luận và hướng phát triển, luận án được cấu trúc gồm ba chương với mối quan hệ về kiến thức giữa các chương như hình sau: 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 4 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 giàn giao này, đề xuất thuật toán tìm mục 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. Đó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 một số 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ứ 15 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ả; 5 - 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ứ 13 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ứ 14 về 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ứ 14 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. 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 nghị Quốc gia lần thứ 10 về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR 10), năm 2017; (2) Kỷ yếu Hội thảo 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 năm 2022. Xem tài liệu số 8 trong danh mục các công trình của tác giả. 6