1. Trang Chủ
  2. Cơ sở dữ liệu
  3. Chiến lược hiệu quả ẩn các tập mục hữu ích cao nhạy cảm trên cơ sở dữ liệu giao tác

Chiến lược hiệu quả ẩn các tập mục hữu ích cao nhạy cảm trên cơ sở dữ liệu giao tác

Bài viết này đề xuất chiến lược sửa đổi một cách hiệu quả để ẩn các tập mục độ hữu ích cao nhạy cảm làm giảm thiểu các hiệu ứng phụ trên các thông tin không nhạy cảm và làm tăng độ tương tự về cơ sở dữ liệu. Kỷ yếu Hội nghị KHCN 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), TP. HCM, ngày 23-24/12/2021 DOI: 10.15625/vap.2021.0084 CHIẾN LƯỢC HIỆU QUẢ ẨN CÁC TẬP MỤC HỮU ÍCH CAO NHẠY CẢM TRÊN CƠ SỞ DỮ LIỆU GIAO TÁC Nguyễn Khắc Chiến1, Nguyễn Trọng Nghĩa2 1 Khoa Ng

Thể loại Tài liệu miễn phí Cơ sở dữ liệu

Số trang 11

Ngày tạo 4/8/2023 3:03:49 PM +00:00

Loại tệp PDF

Kích thước 0.44 M

Tên tệp

Tải Chiến lược hiệu quả ẩn các tập mục hữu ích cao nhạ... (.pdf)

Xem mẫu

  1. Kỷ yếu Hội nghị KHCN 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), TP. HCM, ngày 23-24/12/2021 DOI: 10.15625/vap.2021.0084 CHIẾN LƯỢC HIỆU QUẢ ẨN CÁC TẬP MỤC HỮU ÍCH CAO NHẠY CẢM TRÊN CƠ SỞ DỮ LIỆU GIAO TÁC Nguyễn Khắc Chiến1, Nguyễn Trọng Nghĩa2 1 Khoa Ngoại ngữ - Tin học, Trường Đại học Cảnh sát nhân dân 2 Trường Đại học Thủ Dầu Một nkchienster@gmail.com, trongnghia939@gmail.com TÓM TẮT: Bài toán ẩn các tập mục độ hữu ích cao nhạy cảm đang là chủ đề được nhiều nhà nghiên cứu quan tâm. Mục tiêu của bài toán là bảo vệ các thông tin nhạy cảm trong các cơ sở dữ liệu giao tác, sao cho chúng không thể khám phá được bằng các phương pháp khai thác tập mục độ hữu ích cao với cùng một ngưỡng độ hữu ích tối thiểu do người dùng đưa vào. Bên cạnh đó, các phương pháp ẩn tập mục độ hữu ích cao nhạy cảm cố gắng giảm thiểu các hiệu ứng phụ trên các thông tin không nhạy cảm và tính toàn vẹn của cơ sở dữ liệu ban đầu. Một số phép đo hiệu ứng phụ thường được sử dụng như chi phí ẩn nhầm các tập mục không nhạy cảm (MC), độ tương tự về độ hữu ích của cơ sở dữ liệu trước và sau quá trình ẩn (DUS), độ tương tự về độ hữu ích của các tập mục độ hữu ích cao trước và sau quá trình ẩn (IUS),... Hiện đã có một số phương pháp ẩn hiệu quả để giải quyết vấn đề này, tuy nhiên những phương pháp này vẫn còn tạo ra các hiệu ứng phụ không mong muốn, như ẩn nhầm nhiều tập mục không nhạy cảm, các độ tương tự về độ hữu ích của cơ sở dữ liệu thấp... Bài báo này đề xuất chiến lược sửa đổi một cách hiệu quả để ẩn các tập mục độ hữu ích cao nhạy cảm làm giảm thiểu các hiệu ứng phụ trên các thông tin không nhạy cảm và làm tăng độ tương tự về cơ sở dữ liệu. Kết quả thực nghiệm cho thấy thuật toán đề xuất hiệu quả hơn các thuật toán hiện có về mặt các hiệu ứng phụ, như ẩn nhầm các thông tin không nhạy cảm ít hơn, đảm bảo chất lượng của cơ sở dữ liệu sau quá trình ẩn. Từ khóa: High utility itemset, high utility mining, hiding high utility itemset, privacy-preserving utility mining. I. GIỚI THIỆU Khai phá dữ liệu được sử dụng để khám phá tri thức và thông tin ra quyết định từ dữ liệu khổng lồ [3]. Trong các dự án hợp tác, dữ liệu được chia sẻ giữa các công ty khác nhau để cùng có lợi. Tuy nhiên, điều này mang lại nguy cơ để lộ thông tin nhạy cảm chứa trong cơ sở dữ liệu (CSDL) [13]. Các thông tin nhạy cảm có thể được biểu diễn dưới dạng tập hợp các mẫu phổ biến và các mẫu có độ hữu ích cao có tính bảo mật. Do đó, người sở hữu dữ liệu muốn che giấu thông tin nhạy cảm này đi trước khi chia sẻ CSDL này với đối tác. Để giải quyết bài toán này, khai thác dữ liệu bảo vệ tính riêng tư đã được đề xuất và trở thành một hướng nghiên cứu quan trọng [1]. Các phương pháp khai thác dữ liệu bảo vệ tính riêng tư đã được áp dụng trong nhiều lĩnh vực khác nhau, chẳng hạn như trong điện toán đám mây, sức khỏe điện tử, mạng cảm biến không dây và các dịch vụ định vị [12]. Phương pháp để che giấu các thông tin nhạy cảm là sửa đổi CSDL ban đầu thành một CSDL đã sửa đổi bằng cách sửa đổi một số mục trong CSDL ban đầu. Atallah và cộng sự [2] đã chứng minh bài toán che giấu các thông tin nhạy cảm trong CSDL tối ưu là bài toán NP-khó và nhóm tác giả đã đề xuất một thuật toán sửa đổi dữ liệu dựa trên chiến lược heuristic. Sau đó, đã có nhiều công trình nghiên cứu về lĩnh vực này. Tuy nhiên, hiện có rất ít công trình nghiên cứu về phương pháp ẩn thông tin nhạy cảm để bảo vệ các tập mục độ hữu ích cao nhạy cảm trong CSDL giao tác dựa trên khái niệm về độ hữu ích. Yeh và cộng sự (2010) [17] lần đầu tiên đưa ra hai thuật toán heuristic HHUIF và MSICF để ẩn các tập mục có độ hữu ích cao nhạy cảm. Hai thuật toán này mới chỉ xem xét đến các mục có độ hữu ích cao để sửa đổi, chưa xem xét việc ảnh hưởng đến các hiệu ứng phụ như ẩn nhầm các tập mục không nhạy cảm hay độ tương tự về dữ liệu trước và sau quá trình sửa đổi. Sau đó cũng có một số công trình khác đã được công bố, như [16], [14], [8], [10], [5] và [11] nhằm cải tiến các thuật toán trong [17] và quan tâm cải thiện các hiệu ứng phụ như giảm thiểu chi phí ẩn nhầm các thông tin không nhạy cảm và tăng độ tương tự của dữ liệu trước và sau quá trình ẩn các tập mục nhạy cảm. Các hiệu ứng phụ được tạo ra khi thực hiện sửa đổi một số mục trong cơ sở dữ liệu giao tác nhằm làm giảm độ hữu ích của các tập mục nhạy cảm xuống dưới ngưỡng độ hữu ích tối thiểu do người dùng đưa vào. Trong công trình [11] đã đề xuất ba thuật toán heuristic SMAU, SMIU và SMSE nhằm để ẩn các tập mục độ hữu ích cao nhạy cảm đồng thời làm giảm thiểu các hiệu ứng phụ tạo ra trong quá trình ẩn. Tuy nhiên, các thuật toán trong [11] vẫn tạo ra các hiệu ứng phụ không mong muốn. Bài báo này đề xuất phương pháp cải tiến các thuật toán SMAU và SMIU trong [11] nhằm giảm thiểu các hiệu ứng phụ, như giảm số tập mục không nhạy cảm bị ẩn nhầm và tăng độ tương tự của cơ sở dữ liệu trước và sau quá trình ẩn. Thuật toán đề xuất sẽ tập trung vào việc lựa chọn các tập mục nhạy cảm nào được ẩn trước, đưa ra chiến lược chọn lựa giao tác sửa đổi và mục cần phải sửa đổi một cách hiệu quả để giảm thiểu các hiệu ứng phụ không mong muốn và bảo đảm chất lượng CSDL cao nhất có thể. Kết quả thực nghiệm đã cho thấy thuật toán đề xuất hiệu quả hơn các thuật toán trong [11] về chi phí ẩn nhầm các thông tin không nhạy cảm và tính ổn định của CSDL sau khi sửa đổi. Phần còn lại của bài báo được tổ chức như sau. Phần II đánh giá các công trình liên quan. Trong Phần III các khái niệm cơ bản và phát biểu bài toán ẩn tập mục độ hữu ích cao nhạy cảm. Phần IV đề xuất thuật toán ẩn tập mục độ hữu ích cao nhạy cảm. Phần V trình bày kết quả thực nghiệm và đánh giá. Cuối cùng, kết luận của bài báo trình bày trong Phần VI.
  2. 414 CHIẾN LƯỢC HIỆU QUẢ ẨN CÁC TẬP MỤC HỮU ÍCH CAO NHẠY CẢM TRÊN CƠ SỞ DỮ LIỆU GIAO TÁC II. CÁC CÔNG TRÌNH LIÊN QUAN Trong những năm gần đây, các phương pháp khai thác độ hữu ích bảo vệ tính riêng tư được nhiều nhà nghiên cứu quan tâm. Bài toán này trở nên quan trọng vì nó xem xét cả số lượng và lợi nhuận của mỗi mục có trong CSDL giao tác để ẩn các tập mục có độ hữu ích cao nhạy cảm. Vì mục đích của khai phá độ hữu ích cao bảo vệ tính riêng tư để ẩn các thông tin nhạy cảm (các các tập mục độ hữu ích cao nhạy cảm) trong CSDL, trong khi đó vẫn đảm bảo các thông tin quan trọng khác vẫn được cung cấp cho đối phương, bài toán này được xem như là bài toán tối ưu. Việc tìm ra các giao tác và các mục để sửa đổi trong quá trình ẩn các tập mục có độ hữu ích cao nhạy cảm một cách tối ưu là một bài toán khó và không khả thi [2]. Trong năm 2010, Yeh và cộng sự [17] là nhóm tác giả đầu tiên đưa ra hai thuật toán heuristic HHUIF và MSICF để ẩn các tập mục có độ hữu ích cao nhạy cảm. Hai thuật toán này chọn mục có độ hữu ích cao nhất làm mục sửa đổi cho quá trình ẩn. Thuật toán HHUIF loại bỏ các mục có độ hữu ích cao nhất. Thuật toán MSICF xem xét số lượng xung đột trong quá trình ẩn. Các thuật toán trong [17] chưa quan tâm đến các hiệu ứng phụ. Sau đó, có một số công trình đã đề xuất các thuật toán nhằm cải tiến hai thuật toán trong [17], như công trình của Vo và cộng sự (2013) [16] đề xuất thuật toán nhằm cải tiến thuật toán HHUIF về mặt thời gian, nhưng chưa có sự đánh giá về các hiệu ứng phụ. Selvaraj và cộng sự (2013) [14] đề xuất một thuật toán cải tiến MHIS ở việc chọn mục sửa đổi trong trường hợp độ hữu ích của chúng như nhau. Kết quả cho thấy thuật toán MHIS tốt hơn thuật toán HHUIF về các hiệu ứng phụ HF (không ẩn được) và MC (ẩn nhầm). Yun và Kim (2015) [18] đề xuất thuật toán FPUTT để cải thiện tính hiệu quả của thuật toán HHUIF bằng cách sử dụng cấu trúc cây. Kết quả, thuật toán FPUTT nhanh hơn HHUIF khoảng 5 đến 10 lần. Tuy nhiên, các hiệu ứng phụ do FPUTT tạo ra cũng giống như HHUIF. Lin và cộng sự [8] (2015) đề xuất ba phép đo tương tự để sử dụng như một tiêu chuẩn mới cho việc đánh giá các hiệu ứng phụ trong khai thác độ hữu ích bảo vệ tính riêng tư. Công trình của Lin và cộng sự (2016) [10] đề xuất hai thuật toán MSU-MAU và MSU-MUI để bảo vệ các tập mục có độ hữu ích cao. Cả hai thuật toán này chọn giao tác chứa tập mục nhạy cảm cần ẩn có độ hữu ích lớn nhất để sửa đổi. Hai thuật toán này áp dụng tính chất Max-Min của độ hữu ích để giảm các hiệu ứng phụ và tăng tốc độ của quá trình sửa đổi dữ liệu so với các thuật toán HHUIF và MSICF. Hơn nữa, thuật toán MSU-MIU tốt hơn thuật toán MSU-MAU do trong thuật toán MSU-MIU sử dụng phép chiếu tối ưu. Trieu và cộng sự (2020) [5] đề xuất thuật toán cải tiến thuật toán HHUIF. Thuật toán này nhằm mục đích sửa số lượng các mục trong giao tác sửa đổi để ẩn các tập mục có độ hữu ích cao nhạy cảm. Kết quả cho thấy, thuật toán này hiệu quả hơn HHUIF và MSICF về các hiệu ứng phục và thời gian thực hiện. Xuan Liu và cộng sự (2020) [11] đề xuất ba thuật toán heuristic là SMAU, SMIU và SMSE để ẩn các tập mục nhạy cảm trong CSDL giao tác. Cả ba thuật toán trong [11] lựa chọn giao tác hỗ trợ số tập mục không nhạy cảm ít nhất làm giao tác sửa đổi. Các thuật toán này sử dụng hai cấu trúc bảng T-table và HUI-table giúp giảm thiểu số lần quét CSDL. Trong đó, thuật toán SMAU lựa chọn mục có độ hữu ích cao nhất để sửa đổi, điều này có thể làm sai lệch nhiều về độ hữu ích của CSDL trước và sau sửa đổi. Ngược lại, thuật toán SMIU lựa chọn mục có độ hữu ích nhỏ nhất để sửa đổi, các mục sửa đổi này có thể nằm trong nhiều tập mục không nhạy cảm, do đó khi giảm số lượng hoặc loại bỏ mục đó ra khỏi CSDL có thể làm ẩn đi các tập mục không nhạy cảm. Do vậy, trong bài báo này sẽ đề xuất chiến lược hiệu quả để lựa chọn các giao tác sửa đổi và mục sửa đổi sao cho có thể ẩn được tất cả các tập mục nhạy cảm đồng thời giảm thiểu các hiệu ứng phụ trên các thông tin không nhạy và có gắng giảm thiểu việc thay đổi giá trị độ hữu ích của toàn bộ CSDL và các tập mục độ hữu ích cao. III. CÁC KHÁI NIỆM CƠ BẢN VÀ BÀI TOÁN NGHIÊN CỨU A. Các khái niệm cơ bản Một số khái niệm về khai thác tập mục độ hữu ích cao được trình bày trong [6]. Cho 𝐼 = {𝑖1 , 𝑖2 , … , 𝑖𝑚 } là một tập 𝑚 mục phân biệt, trong đó mỗi mục 𝑖𝑝 ∈ 𝐼 có độ hữu ích bên ngoài (được gọi là lợi nhuận) 𝑒𝑢�𝑖𝑝 �, 1 ≤ 𝑝 ≤ 𝑚 và 𝐷 = {𝑇1 , 𝑇2 , … , 𝑇𝑛 } là một CSDL giao tác, trong đó 𝑇𝑖 là một giao tác chứa một tập các mục được chứa trong 𝐼. Mỗi giao tác được gán cho một định danh duy nhất là 𝑇𝐼𝐷. Một tập gồm một hoặc nhiều mục được gọi làm tập mục. Một giao tác 𝑇 hỗ trợ một tập mục 𝑋 nếu 𝑋 ⊆ 𝐼. Một tập mục 𝑋 = {𝑖1 , 𝑖2 , … , 𝑖𝑘 } chứa k mục được gọi là k- itemset. Mỗi mục 𝑖𝑝 trong giao tác 𝑇𝑞 được kết hợp với một số lượng các mục 𝑖𝑝 có trong giao tác 𝑇𝑞 . Cho một CSDL giao tác như trong Bảng 1 và Bảng 2. Trong Bảng 1, CSDL gồm có 10 giao tác. Trong Bảng 2 là bảng lợi nhuận của từng mục có trong CSDL. Định nghĩa 1: Số lượng mục 𝑖𝑝 trong giao tác 𝑇𝑞 , ký hiệu là 𝑖𝑢(𝑖𝑝 , 𝑇𝑞 ). Ví dụ: trong Bảng 1 có 𝑖𝑢(𝑏, 𝑇8 ) = 15 và 𝑖𝑢(𝑑, 𝑇8 ) = 35. Định nghĩa 2: Lợi nhuận của mục 𝑖𝑝 , nó thể hiện độ quan trọng của mục 𝑖𝑝 , ký hiệu là 𝑒𝑢�𝑖𝑝 �. Ví dụ: trong Bảng 2 có 𝑒𝑢(𝑏) = 3 và 𝑒𝑢(𝑑) = 1. Định nghĩa 3: Độ hữu ích của mục 𝑖𝑝 trong giao tác 𝑇𝑞 , ký hiệu là 𝑢(𝑖𝑝 , 𝑇𝑞 ), được tính như sau: 𝑢�𝑖𝑝 , 𝑇𝑞 � = 𝑖𝑢�𝑖𝑝 , 𝑇𝑞 � ∗ 𝑒𝑢(𝑖𝑝 ).
  3. Nguyễn Khắc Chiến, Nguyễn Trọng Nghĩa 415 Ví dụ: 𝑢(𝑏, 𝑇8 ) = 𝑖𝑢(𝑏, 𝑇8 ) ∗ 𝑒𝑢(𝑏) = 15 ∗ 3 = 45. Định nghĩa 4: Độ hữu ích của tập mục X trong giao tác 𝑇𝑞 , ký hiệu là 𝑢(𝑋, 𝑇𝑞 ), được tính như sau: 𝑢�𝑋, 𝑇𝑞 � = � 𝑢�𝑖𝑝 , 𝑇𝑞 � 𝑖𝑝 ∈𝑋 Ví dụ: 𝑢(𝑏𝑑, 𝑇8 ) = 𝑢(𝑏, 𝑇8 ) + 𝑢(𝑑, 𝑇8 ) = 15 ∗ 3 + 35 ∗ 1 = 80. Bảng 1. Cho cơ sở dữ liệu giao tác sau Bảng 3. Các tập mục độ hữu ích cao (𝑚𝑖𝑛𝑢𝑡𝑖𝑙 = 160) TID Giao tác (Mục, số lượng) HID HUIs Utility (Độ hữu ích) T1 (a,2),(b,1),(e,3) 1 abcde 200 T2 (c,1), (d,6) 2 abcdef 167 T3 (b,1), (c,2), (e,1), (f,1) 3 abce 168 T4 (a,3), (b,4), (c,2), (d,2), (e,5) 4 acd 206 T5 (b,3), (c,5) 5 ae 162 T6 (a,2), (e,7), (f,3) 6 bcde 160 T7 (a,4), (c,15), (d,40) 7 bde 214 T8 (b,15), (d,35), (e,3) 8 be 177 T9 (a,5), (b,10), (c,20), (d,30), (e,2), (f,3) 9 cef 160 T10 (c,12), (e,4), (f,1) 10 ef 164 Bảng 2. Bảng lợi nhuận Mục a b c d e f Lợi nhuận 5 3 2 1 6 10 Định nghĩa 5: Độ hữu ích của tập mục X, ký hiệu là 𝑢(𝑋), được tính như sau: 𝑢(𝑋) = � 𝑢�𝑋, 𝑇𝑞 � 𝑋⊆𝑇𝑞 ∧𝑇𝑞 ∈𝐷 Ví dụ: 𝑢(𝑏𝑑) = 𝑢(𝑏𝑑, 𝑇4 ) + 𝑢(𝑏𝑑, 𝑇8 ) + 𝑢(𝑏𝑑, 𝑇9 ) = 14 + 80 + 60 = 154. Định nghĩa 6: Độ hữu ích của giao tác 𝑇𝑞 , ký hiệu là 𝑡𝑢(𝑇𝑞 ), được tính như sau: 𝑡𝑢(𝑇𝑞 ) = � 𝑢�𝑖𝑝 , 𝑇𝑞 � 𝑖𝑝 ∈𝑇𝑞 Ví dụ: 𝑡𝑢(𝑇8 ) = 𝑢(𝑏, 𝑇8 ) + 𝑢(𝑑, 𝑇8 ) + 𝑢(𝑒, 𝑇8 ) = 15 ∗ 3 + 35 ∗ 1 + 3 ∗ 6 = 98. Định nghĩa 7: Bài toán khai tác tập mục độ hữu cao. Một tập mục X được gọi là tập mục độ hữu ích cao nếu độ hữu ích của X lớn hơn hoặc bằng ngưỡng độ hữu ích tối thiểu do người dùng đưa vào, ký hiệu là 𝑚𝑖𝑛𝑢𝑡𝑖𝑙. Gọi 𝐻𝑈𝐼 là tập hợp các tập mục độ hữu ích cao, ta có 𝐻𝑈𝐼 = {𝑋 | 𝑋 ∈ 𝐼, 𝑢(𝑋) ≥ 𝑚𝑖𝑛𝑢𝑡𝑖𝑙}. Với CSDL giao tác cho trong Bảng 1, Bảng 2 và ngưỡng độ hữu ích tối thiểu 𝑚𝑖𝑛𝑢𝑡𝑖𝑙 = 160, các tập mục độ hữu ích cao (HUI) khai thác được thể hiện trong Bảng 3. B. Bài toán nghiên cứu Bài toán nghiên cứu được phát biểu như sau: Cho một tập hợp các tập mục độ hữu ích cao nhạy cảm (gọi tắt là: tập mục nhạy cảm) cần phải ẩn, ký hiệu là 𝑆𝐻𝑈𝐼 = {𝑠1 , 𝑠2 , … , 𝑠𝑚 }, trong đó 𝑠𝑑 ∈ 𝐻𝑈𝐼, (1 ≤ 𝑑 ≤ 𝑚). Bài toán ẩn tập mục nhạy cảm là việc sửa đổi CSDL ban đầu D thành CSDL được sửa đổi D’ sao cho độ hữu ích của tất cả các tập mục nhạy cảm 𝑠𝑖 ∈ 𝑆𝐻𝑈𝐼 phải nhỏ hơn ngưỡng độ hữu ích tối thiểu do người dùng đưa vào, tức là 𝑢(𝑠𝑖 ) < 𝑚𝑖𝑛𝑢𝑡𝑖𝑙, 𝑣ớ𝑖 𝑖 = 1 ÷ 𝑚. Định nghĩa 8: Gọi 𝑆𝐻𝑈𝐼 = {𝑠1 , 𝑠2 , … , 𝑠𝑚 } là tập hợp các tập mục nhạy cảm, trong đó si là một tập mục nhạy cảm cần được ẩn trước khi đưa CSDL ra bên ngoài, ta có 𝑆𝐻𝑈𝐼 ⊆ 𝐻𝑈𝐼. Gọi 𝑁𝑆𝐻𝑈𝐼 là tập hợp các tập mục độ hữu ích cao không nhạy cảm (gọi tắt là: tập mục không nhạy cảm), ta có 𝑆𝐻𝑈𝐼 ∪ 𝑁𝑆𝐻𝑈𝐼 = 𝐻𝑈𝐼. Định nghĩa 9: Gọi 𝑆𝑇 là tập hợp các giao tác nhạy cảm mà mỗi giao tác trong 𝑆𝑇 có chứa ít nhất một tập mục nhạy cảm. Quá trình sửa đổi dữ liệu của bài toán ẩn các tập mục nhạy cảm gồm ba bước sau:
  4. 416 CHIẾN LƯỢC HIỆU QUẢ ẨN CÁC TẬP MỤC HỮU ÍCH CAO NHẠY CẢM TRÊN CƠ SỞ DỮ LIỆU GIAO TÁC Bước 1: Áp dụng các thuật toán khai thác độ hữu ích cao trên CSDL giao tác 𝐷 để có được tất cả các tập mục độ hữu ích cao (HUI); Bước 2: Xác định tập hợp các tập mục nhạy cảm SHUI dựa trên các yêu cầu của người dùng; Bước 3: Áp dụng thuật toán ẩn các tập mục nhạy cảm để tạo ra CSDL giao tác được sửa đổi 𝐷’. Quá trình sửa đổi thường tạo ra các hiệu ứng phụ [4, 7, 9, 15]. Các phép đo hiệu ứng phụ được sử dụng để đánh giá hiệu suất của thuật toán đề xuất bao gồm: (1) Chi phí ẩn nhầm các tập mục không nhạy cảm (𝑴𝑪): |𝑁𝑆𝐻𝑈𝐼(𝐷) − 𝑁𝑆𝐻𝑈𝐼(𝐷′)| 𝑀𝐶 = |𝑁𝑆𝐻𝑈𝐼(𝐷)| trong đó 𝑁𝑆𝐻𝑈𝐼(𝐷) và 𝑁𝑆𝐻𝑈𝐼(𝐷’) là tập hợp các tập mục không nhạy cảm trong CSDL giao tác 𝐷 và 𝐷’. Với phép đo này, thuật toán nào tạo ra giá trị 𝑀𝐶 càng nhỏ càng hiệu quả vì chứng tỏ việc ẩn nhầm các tập không nhạy cảm ít xảy ra. (2) Độ tương tự về độ hữu ích của cơ sở dữ liệu (𝑫𝑼𝑺) Độ tương tự về độ hữu ích của CSDL (𝐷𝑈𝑆) được sử dụng để đo mức độ giảm độ hữu ích trong toàn bộ CSDL. Gọi D và D’ lần lượt là CSDL ban đầu và CSDL sau sửa đổi. Độ hữu ích bị giảm sau quá trình ẩn được thể hiện là độ tương tự về độ hữu ích của CSDL (DUS), được tính như sau: ∑Tq∈D′ tu(Tq ) 𝐷𝑈𝑆 = ∑Tq∈D tu(Tq ) trong đó ∑Tq∈D tu(Tq ) và ∑Tq∈D′ tu(Tq ) là tổng các độ hữu ích của các giao tác trong CSDL ban đầu D và CSDL sau khi sửa đổi D’. (3) Độ tương tự về độ hữu ích của các tập mục độ hữu ích cao (IUS) Độ tương tự về độ hữu ích của các tập mục độ hữu ích cao (IUS) là phép đo khác chỉ ra các độ hữu ích bị giảm của các HUI trước và sau quá trình sửa đổi. Gọi HUI D v à HUI D′ là các tập mục độ hữu ích cao (HUI) được khai thác từ CSDL ban đầu D và CSDL đã sửa đổi D’. Độ hữu ích bị giảm xuống của các các tập mục độ hữu ích cao được khai thác trước và sau sửa đổi có thể biểu thị là độ tương tự về độ hữu ích của các tập mục độ hữu ích cao (IUS), được tính như sau: ∑X∈HUID′ u(X) 𝐼𝑈𝑆 = ∑X∈HUID u(X) trong đó ∑X∈HUID u(X) và ∑X∈HUID′ u(X) là tổng độ hữu ích của các tập mục độ hữu ích cao trong 𝐷 và 𝐷’. Ngoài ra, còn một số phép đo khác như ẩn lỗi (𝐻𝐹) - không ẩn được hết các tập mục nhạy cảm và phép đo tạo ra các tập mục độ hữu ích cao mới (𝐴𝐶). Các phương pháp ẩn được xem xét trong bài báo này đều thực hiện ẩn được tất cả các tập mục nhạy cảm và không tạo ra các tập mục độ hữu ích cao mới, các phép đo này đều bằng 0, nên không nêu ra ở đây. Mục tiêu của bài toán ẩn các tập mục nhạy cảm để bảo vệ tính riêng tư không chỉ ẩn tất cả các tập mục nhạy cảm mà còn làm giảm thiểu các hiệu ứng phụ trên các thông tin không nhạy cảm và tính toàn vẹn của CSDL ban đầu. Thuật toán được đề xuất trong bài báo này cũng nhằm vào mục tiêu này. IV. THUẬT TOÁN ĐỀ XUẤT A. Cơ sở đề xuất thuật toán Phương pháp ẩn các tập mục nhạy cảm là sửa đổi CSDL ban đầu bằng cách xóa hoặc giảm số lượng của một số mục để độ hữu ích của các tập mục nhạy cảm giảm xuống dưới ngưỡng độ hữu ích 𝑚𝑖𝑛𝑢𝑡𝑖𝑙. Trên cơ sở phương pháp ẩn tổng quát này, bài toán ẩn tập mục nhạy cảm cần phải xác định được: Giao tác nào được chọn để sửa đổi? và mục nào được chọn để sửa đổi trong giao tác sửa đổi? Mục được sửa đổi để ẩn tập mục nhạy cảm được gọi là mục sửa đổi 𝐼𝑣𝑖𝑐 . Giao tác chứa mục sửa đổi được gọi là giao tác sửa đổi 𝑇𝑣𝑖𝑐 . Trong bài báo này, chúng ta chỉ xem xét những giao tác hỗ trợ các tập mục nhạy cảm, vì các giao tác khác không có ảnh hưởng gì đến quá trình ẩn. Để giảm các hiệu ứng phụ, thuật toán được đề xuất chỉ chọn những giao tác nào hỗ trợ số lượng các tập mục không nhạy cảm ít nhất làm giao tác sửa đổi, nếu có nhiều giao tác thỏa mãn điều kiện này thì chọn giao tác nào hỗ trợ nhiều tập mục nhạy cảm nhất để làm giao tác sửa đổi, gọi là 𝑇𝑣𝑖𝑐 . Định nghĩa 10: Số lượng tập mục nhạy cảm được hỗ trợ bởi giao tác 𝑇 được ký hiệu là 𝑆𝐻𝐶(𝑇).
  5. Nguyễn Khắc Chiến, Nguyễn Trọng Nghĩa 417 Định nghĩa 11: Số lượng tập mục không nhạy cảm được hỗ trợ bởi giao tác T được ký hiệu là 𝑁𝑆𝐻𝐶(𝑇). Định nghĩa 12: Xác định giao tác sửa đổi 𝑇𝑣𝑖𝑐 . Giao tác nào có số lượng 𝑁𝑆𝐻𝐶(𝑇) nhỏ nhất được chọn làm giao tác sửa đổi. Nếu có nhiều giao tác như vậy thì chọn giao tác nào hỗ trợ số lượng tập mục nhạy cảm 𝑆𝐻𝐶(𝑇) nhiều nhất được chọn làm giao tác sửa đổi 𝑇𝑣𝑖𝑐 . Định nghĩa 13: Xác định mục cần loại bỏ 𝐼𝑠𝑖 : là mục có số lần xuất hiện trong các tập mục không nhạy cảm mà 𝑇𝑣𝑖𝑐 hỗ trợ ít nhất. Nếu có nhiều mục như vậy, thuật toán đề xuất sẽ chọn mục nào có số lần xuất hiện trong các tập mục nhạy cảm mà 𝑇𝑣𝑖𝑐 hỗ trợ nhiều nhất, ký hiệu là Isi để loại bỏ khỏi 𝑇𝑣𝑖𝑐 . Sau khi xác định được giao tác sửa đổi 𝑇𝑣𝑖𝑐 , một mục có trong tập mục nhạy cảm đang cần ẩn được chọn để sửa đổi làm giảm độ hữu ích của tập mục nhạy cảm này xuống dưới ngưỡng 𝑚𝑖𝑛𝑢𝑡𝑖𝑙. Khi thực hiện ẩn các tập mục nhạy cảm, thứ tự lựa chọn tập mục nhạy cảm nào được ẩn trước cũng ảnh hưởng đến quá trình ẩn và tạo ra các hiệu ứng phụ không mong muốn. Trong bài báo này, chúng tôi đề xuất lựa chọn tập mục nhạy cảm nào có độ hữu ích lớn nhất được thực hiện ẩn trước. Vì khi thực hiện ẩn các tập mục nhạy cảm này, có thể làm ẩn đi các tập mục nhạy cảm khác, khi đó chúng ta không cần phải đi ẩn tập mục nhạy cảm đó nữa. Điều này được chứng minh trong phần ví dụ minh họa. Do đó, có thể làm tăng tính hiệu quả của quá trình ẩn. Ngoài ra, trong quá trình ẩn, việc loại bỏ đi các mục có độ hữu ích cao nhất (như thuật toán SMAU [11]) hay mục có độ hữu nhỏ nhất (như thuật toán SMIU [11]) có thể tạo ra nhiều hiệu ứng phụ không mong muốn trên các thông tin không nhạy cảm như: làm sai lệch về độ hữu ích của toàn bộ CSDL và độ hữu ích của các tập mục độ hữu ích cao trước và sau khi sửa đổi. Bên cạnh đó có thể gây ra việc ẩn nhầm nhiều tập mục không nhạy cảm. Để giảm thiểu các hiệu ứng phụ trên, trong bài báo này đề xuất một chiến lược hiệu quả như sau: Đối với trường hợp phải loại bỏ mục nhạy cảm ra khỏi giao tác sửa đổi 𝑇𝑣𝑖𝑐 , thuật toán đề xuất sẽ chọn mục 𝐼𝑠𝑖 (Định nghĩa 13) để loại bỏ khỏi 𝑇𝑣𝑖𝑐 . Điều này sẽ giúp cho quá trình ẩn ít ảnh hưởng đến các tập mục không nhạy cảm nhiều nhất. Đối với trường hợp phải loại bỏ số lượng các mục trong giao tác 𝑇𝑣𝑖𝑐 , thuật toán đề xuất sẽ kiểm tra xem mục 𝐼𝑠𝑖 (Định nghĩa 13) có thỏa mãn để giảm số lượng hay không, nếu thỏa mãn thì loại bỏ số lượng của mục 𝐼𝑠𝑖 . Nếu không thỏa mãn thì thuật toán đề xuất sẽ loại bỏ số lượng mục có độ hữu ích lớn nhất. Gọi 𝑋 là tập mục nhạy cảm. Để ẩn 𝑋, độ hữu ích của 𝑋 phải giảm ít nhất là: 𝑑𝑖𝑓𝑓𝑢 = 𝑢(𝑋) − 𝑚𝑖𝑛𝑡𝑢𝑖𝑙 + 1 Giả sửa 𝐼𝑣𝑖𝑐 là mục sửa đổi được sử dụng để ẩn 𝑋 và 𝑇𝑣𝑖𝑐 là giao tác sửa đổi chứa 𝐼𝑣𝑖𝑐 . Nếu loại bỏ 𝐼𝑣𝑖𝑐 khỏi giao tác 𝑇𝑣𝑖𝑐 , khi đó độ hữu ích của 𝑋 sẽ giảm một lượng là: 𝑢(𝑋, 𝑇𝑣𝑖𝑐 ). Vì khi loại bỏ 𝐼𝑣𝑖𝑐 , 𝐼𝑣𝑖𝑐 ∈ 𝑋 từ 𝑇𝑣𝑖𝑐 , khi đó 𝑇𝑣𝑖𝑐 sẽ không hỗ trợ 𝑋 nữa, giá trị độ hỗ trợ của 𝑋 phải giảm là: 𝑢(𝑋) − 𝑢(𝑋, 𝑇𝑣𝑖𝑐 ). Bảng 4. Thuật toán đề xuất (ProAlg) Input: CSDL giao tác 𝐷, ngưỡng tối thiểu 𝑚𝑖𝑛𝑢𝑡𝑖𝑙, tập mục nhạy cảm 𝑆𝐻𝑈𝐼 = {𝑆1 , 𝑆2 , . . . , 𝑆𝑘 } Output: CSDL đã sửa đổi 𝐷’ 1 Tạo hai bảng T-table và HUI-table 2 Sắp xếp các 𝑆𝑖 giảm dần theo độ hữu ích 𝑢(𝑆𝑖 ). 3 For each 𝑆𝑖 ∈ 𝑆𝐻𝑈𝐼 4 diffu = u(Si) – minutil +1 5 while diffu > 0 6 Tìm tập các giao tác nhạy cảm ST, 𝑆𝑖 ∈ 𝑆𝑇 7 Xác định 𝑇𝑣𝑖𝑐 (Định nghĩa 12) 8 𝐼𝑚𝑎𝑥 = 𝑎𝑟𝑔𝑚𝑎𝑥𝐼𝜖𝑆𝑖 𝑢(𝐼, 𝑇𝑣𝑖𝑐 ) 9 If 𝑑𝑖𝑓𝑓𝑢 > 𝑢(𝐼𝑚𝑎𝑥 , 𝑇𝑣𝑖𝑐 ) − 𝑒𝑢(𝐼𝑚𝑎𝑥 ) 10 Loại bỏ mục 𝐼𝑠𝑖 (Định nghĩa 13) else 11 if 𝑑𝑖𝑓𝑓𝑢
  6. 418 CHIẾN LƯỢC HIỆU QUẢ ẨN CÁC TẬP MỤC HỮU ÍCH CAO NHẠY CẢM TRÊN CƠ SỞ DỮ LIỆU GIAO TÁC Ví dụ trong Bảng 1, I-list của T8 là . Định nghĩa 15: Cho một CSDL 𝐷, một tập hợp các tập mục độ hữu ích cao 𝐻𝑈𝐼 = {𝑋 | 𝑋 ∈ 𝐼, 𝑢(𝑋) ≥ 𝑚𝑖𝑛𝑢𝑡𝑖𝑙}, một bảng tập mục độ hữu ích cao (HUI-table) chứa thông tin về các tập mục độ hữu ích cao được khai thác từ CSDL giao tác D. Mỗi tập mục độ hữu ích cao 𝑋 trong bảng HUI-table có bốn thành phần: 𝑋 =< 𝐻𝐼𝐷, 𝐼𝑡𝑒𝑚𝑠, 𝐻𝑈𝐼 − 𝑢𝑡𝑖𝑙𝑖𝑡𝑦, 𝑇𝐼𝐷𝑠 >. Trong đó 𝐻𝐼𝐷 là định danh duy nhất của 𝑋, 𝐼𝑡𝑒𝑚𝑠 là danh sách các mục có trong 𝑋, 𝐻𝑈𝐼 − 𝑢𝑡𝑖𝑙𝑖𝑡𝑦 là độ hữu ích của 𝑋, 𝑇𝐼𝐷𝑠 cho biết các giao tác hỗ trợ 𝑋 trong 𝐷. Với CSDL giao tác cho trong Bảng 1 và Bảng 2 với ngưỡng độ hữu ích tối thiểu là 𝑚𝑖𝑛𝑢𝑡𝑖𝑙 = 160. Chúng ta xây dựng được bảng HUI-Table như trong Bảng 6. Định nghĩa 16: Cho CSDL D, một tập hợp các tập mục nhạy cảm 𝑆𝐻𝑈𝐼 = {𝑆1 , 𝑆2 , . . . , 𝑆𝑘 } , Bảng giao tác (T- table) chứa thông tin của các giao tác nhạy cảm trong D. Mỗi giao tác T trong bảng T-table có bốn thành phần: T = . Trong đó TID là mã định danh duy nhất của T, SID và NSID lần lượt là mã định danh các tập mục nhạy cảm và tập mục không nhạy cảm được hỗ trợ bởi T. I-list là danh sách mục của T. Giả sử tập mục độ hữu ích cao nhạy cảm cần phải ẩn là 𝑆𝐻𝑈𝐼 = {< 𝑎𝑒 >, < 𝑏𝑑𝑒 >, < 𝑎𝑏𝑐𝑑𝑒 >}, chúng ta xây dựng được bảng T-Table như trong Bảng 7. Thuật toán đề xuất được trình bày trong Bảng 4. Thuật toán được thực hiện như sau: Đầu tiền là xây dựng hai bảng T-Table và HUI-Table (dòng 1). Các tập mục nhạy cảm SHi được sắp xếp giảm dần theo độ hữu ích (dòng 2). Tiếp theo thực hiện vọng lặp để lần lượt ẩn các tập mục nhạy từ dòng 3 -20. Tính độ hữu ích cần phải giảm đối với mỗi tập mục nhạy cảm (dòng 4). Thực hiện vòng lặp để thực hiện ẩn tập mục nhạy cảm: Trong khi 𝑑𝑖𝑓𝑓𝑢 > 0, tìm tập các giao tác nhạy cảm ST. Xác định giao tác cần sửa đổi Tvic theo Định nghĩa 14 và mục cần sửa đổi Imax, Isi theo định nghĩa 15 từ dòng 7-17. Sau đó cập nhật các giá trị tương ứng và cập nhật cho bảng T-Table v à HUI-Table. Thực hiện cho tới khi ẩn được hết các tập mục nhạy cảm thì kết thúc thuật toán. Thuật toán đề xuất đảm bảo ẩn được hết các tập mục nhạy cảm. B. Ví dụ minh họa Với CSDL cho trong Bảng 1 và Bảng 2 với ngưỡng độ hữu ích tối thiểu minutil =160, chúng ta có bảng các tập mục độ hữu ích cao HUI trong Bảng 3. Giải sử tập mục nhạy cảm cần ẩn là 𝑆𝐻𝑈𝐼 = {< 𝑎𝑒 >, < 𝑏𝑑𝑒 >, < 𝑎𝑏𝑐𝑑𝑒 >}. Đầu tiên, chúng ta đi xây dựng các bảng I-List của các giao tác T trong CSDL (Bảng 5). Bảng 5. Bảng cơ sở dữ liệu có dạng cấu trúc I-List Bảng 6. Bảng HUI-Table TID I-List HID Items HUI-Utility TIDs T1 (a,2,10) (b,1,3) (e,3,18) 1 abcde 200 T4, T9 T2 (c,1,2) (d,6,6) 2 abcdef 167 T9 T3 (b,1,3) (c,2,4) (e,1,6) (f,1,10) 3 abce 168 T4,T9 T4 (a,3,15)(b,4,12)(c,2,4)(d,2,2)(e,5,30) 4 acd 206 T4,T7,T9 T5 (b,3,9)(c,5,10) 5 ae 162 T1,T4,T6,T9 T6 (a,2,10)(e,7,42)(f,3,30) 6 bcde 160 T4,T9 T7 (a,4,20)(c,15,30)(d,40,40) 7 bde 214 T4,T8,T9 T8 (b,15,45)(d,35,35)(e,3,18) 8 be 177 T1,T3,T4,T8,T9 T9 (a,5,25)(b,10,30)(c,20,40)(d,30,30)(e,2,12)(f,3,30) 9 cef 160 T3,T9 T10 (c,12,24)(e,4,24)(f,1,10) 10 ef 164 T3,T6,T9,T10 Bảng 7. Bảng T-Table TID SID NSID I-List T1 5 8 (a,2,10) (b,1,3) (e,3,18) T4 1,5,7 3,4,6,8 (a,3,15)(b,4,12)(c,2,4)(d,2,2)(e,5,30) T6 5 10 (a,2,10)(e,7,42)(f,3,30) T8 7 8 (b,15,45)(d,35,35)(e,3,18) T9 1,5,7 2,3,4,6,8,9,10 (a,5,25)(b,10,30)(c,20,40)(d,30,30)(e,2,12)(f,3,30) Tiếp theo, sắp xếp giảm dần theo độ hữu ích: 𝑆𝐻𝑈𝐼 = {< 𝑏𝑑𝑒 > (214), < 𝑎𝑏𝑐𝑑𝑒 > (200), < 𝑎𝑒 > (162)} Như vậy, thuật toán chọn tập mục nhạy cảm S1= ẩn trước: tính độ hữu ích cần phải giảm: diffu = 214 -160+1 = 55.
  7. Nguyễn Khắc Chiến, Nguyễn Trọng Nghĩa 419 Tập mục nhạy cảm S1 = có các giao tác T4, T8 và T9 hỗ trợ, vập tập hợp các giao tác nhạy cảm ST = . Tính số lượng các tập mục không nhạy cảm mà các giao tác nhạy cảm hỗ trợ. Ta có NSHC(T4) =4, NSHC(T8)=1 và NSHC(T9)=7. Vậy chúng ta chọn giao tác T8 có số lượng hỗ trợ các tập mục không nhạy cảm ít nhất làm giao tác sửa đổi Tvic = T8. Tiếp theo, thuật toán tìm mục cần sửa đổi để giảm độ hữu ích của tập mục nhạy cảm. Ta có: u(b,T8)=45, u(d,T8)=35 và u(e,T8)=18. Trong đó u(b,T8) có gía trị độ hữu ích lớn nhất. Vì diffu =55 > u(b,T8) – eu(b) =45-3=42, do đó, bắt buộc phải loại bỏ một mục nhạy cảm trong S1 ra khỏi giao tác T8. (Đối với thuật toán SMAU [11] thì chọn mục b để loại bỏ khỏi giao tác T8, thuật toán SMIU [11] thì chọn mục e loại bỏ khỏi giao tác T8). Đối với thuật toán đề xuất sẽ chọn mục nào xuất hiện trong các tập mục không nhạy cảm mà T8 hỗ trợ ít nhất, nếu có nhiều mục thỏa mãn thì chọn mục nào xuất hiện trong các tập mục nhạy cảm mà T8 hỗ trợ nhiều nhất (Định nghĩa 13). Ở đây, ta thấy mục b, e cùng xuất hiện trong một tập mục không nhạy cảm mà T8 hỗ trợ là , mục d không xuất hiện trong tập mục không nhạy cảm mà T8 hỗ trợ. Như vậy, thuật toán đề xuất sẽ chọn mục d để loại bỏ khỏi giao tác T8. Khi loại bỏ mục d, ta thấy nó không ảnh hưởng đến bất kỳ tập mục không nhạy cảm nào. Khi loại bỏ mục d ra khỏi giao tác T8, khi đó T8 không hỗ trợ tập mục nhạy cảm nữa. Độ hữu ích của tập mục sẽ bị giảm xuống còn lại là: 𝑢(< 𝑏𝑑𝑒 >) = 214 – 𝑢(< 𝑏𝑑𝑒 >, 𝑇8) = 214 – 98 = 116 < 𝑚𝑖𝑛𝑢𝑡𝑖𝑙. Như vậy tập mục nhạy cảm S1 = đã được ẩn thành công. Thuật toán sẽ cập nhật lại các giá trị trong các bảng HUI-table (Bảng 8) và T-table (Bảng 9). Bảng 8. Bảng HUI-Table cập nhật lần 1 HID Items HUI-Utility TIDs 1 abcde 200 T4,T9 2 abcdef 167 T9 3 abce 168 T4,T9 4 acd 206 T4,T7,T9 5 ae 162 T1,T4,T6,T9 6 bcde 160 T4,T9 7 bde 116 T4,T9 8 be 177 T1,T3,T4,T8,T9 9 cef 160 T3,T9 10 ef 164 T3,T6,T9,T10 Bảng 9. Bảng T-Table cập nhật lần 1 TID SID NSID I-List T1 5 8 (a,2,10) (b,1,3) (e,3,18) T4 1,5,7 3,4,6,8 (a,3,15)(b,4,12)(c,2,4)(d,2,2)(e,5,30) T6 5 10 (a,2,10)(e,7,42)(f,3,30) T8 (b,15,45)(e,3,18) T9 1,5,7 2,3,4,6,8,9,10 (a,5,25)(b,10,30)(c,20,40)(d,30,30)(e,2,12)(f,3,30) Thuật toán tiếp tục chọn tập mục nhạy cảm S2= để thực hiện ẩn. Tính 𝑑𝑖𝑓𝑓𝑢 = 200 − 160 + 1 = 41. Tập hợp các giao tác nhạy cảm hỗ trợ tập mục S2 là ST=. Ta có NSHC(T4) =4 và NSHC(T9)=7, như vậy chọn giao tác T4 làm giao tác sửa đổi Tvic = T4. Tìm mục sửa đổi, ta có u(a,T4)=15, u(b,T4)=12, u(c,T4)=4, u(d,T4)=2 và u(e,T4)=30. Ta thấy mục e có giá trị độ hỗ trợ lớn nhất và diffu =41 > u(e,T4)-eu(e) = 30-5=25, như vậy bắt buộc phải loại bỏ một mục nhạy cảm trong S2 = ra khỏi giao tác T4 để giảm độ hữu ích của tập mục nhạy S2. (Đối với thuật toán SMAU [11] thì chọn mục e để loại bỏ khỏi giao tác T4, thuật toán SMIU [11] thì chọn mục d loại bỏ khỏi giao tác T8). Bảng 10. Bảng so sánh kết quả chạy thuật toán đề xuất với các thuật toán SMAU, SMIU [11] Số lần thực hiện Số tập mục Độ hữu ích của Độ hữu ích của các Thuật toán để ẩn các tập không nhạy cảm toàn bộ CSDL tập mục độ hữu mục nhạy cảm bị ẩn nhầm bị giảm đi ích cao bị giảm đi SMAU 3 3 81 476 SMIU 3 3 23 437 ProAlg 2 1 50 260
  8. 420 CHIẾN LƯỢC HIỆU QUẢ ẨN CÁC TẬP MỤC HỮU ÍCH CAO NHẠY CẢM TRÊN CƠ SỞ DỮ LIỆU GIAO TÁC Trong thuật toán đề xuất, tìm mục xuất hiện trong các tập mục không nhạy cảm do T4 hỗ trợ ít nhất để loại bỏ. Ta có giao tác T4 hỗ trợ các tập mục không nhạy cảm là: , , , . Như vậy, ta thấy NSHC(a,T4)=2, NSHC(b,T4)=3, NSHC(c,T4)=3, NSHC(d,T4)=2 và NSHC(e,T4)=3. Có hai mục a và d có cùng giá trị nhỏ nhất bằng 2. Thuật toán đề xuất tiêp tục xét hai mục a và d. Xem mục nào xuất hiện trong các tập mục nhạy cảm nhiều nhất. Giao tác T4 hỗ trợ hai tập mục nhạy cảm và (không tính tập mục vì đã được ẩn rồi). Ta thấy SHC(a,T4) =2 và SHC(d,T4) =1. Như vậy, thuật toán sẽ chọn mục a để loại khỏi giao tác T4, T4 không còn hỗ trợ tập mục , giá trị độ hữu ích của sẽ giảm xuống còn lại: u() = 200 – 63 = 137 < minutil, như vậy đã ẩn được tập mục S2 = . Ngoài ra, ta thấy tập mục nhạy cảm S3 = cũng bị ẩn theo, vì T4 cũng hỗ trợ tập mục . Khi loại bỏ a ra khỏi T4 thì T4 cũng không còn hỗ trợ tập mục nữa, độ hữu ích của tập mục còn lại là: 𝑢(< 𝑎𝑒 >) = 162 – 45 = 117 < 𝑚𝑖𝑛𝑢𝑡𝑖𝑙. Vậy tập mục nhạy S3 = cũng được ẩn. Thuật toán cập nhật lại các giá trị cho bảng HUI-table, bảng T-Table. Thuật toán đã ẩn xong tất cả các tập mục nhạy cảm và kết thúc thuật toán. Đối với ví dụ này, thuật toán đề xuất đã thực hiện ẩn thành công các tập mục nhạy và đã ẩn nhầm một tập mục không nhạy cảm . Về giá trị độ hữu ích của toàn bộ CSDL đã bị giảm đi 50 (DUS) và tổng độ hữu ích của các tập mục độ hữu ích cao bị giảm đi 260 (IUS). Các kết quả này được so sánh với kết quả chạy thuật toán SMAU và SMIU [11] trong Bảng 10. Bảng 11. Cơ sở dữ liệu dùng cho thực nghiệm Cơ sở dữ liệu Số giao tác Số lượng mục BMS_2 77512 3340 Mushroom 8124 119 Như vậy, với thuật toán đề xuất, có thể ẩn nhầm tập mục không nhạy cảm ít hơn, sự thay đổi về CSDL trước và sau khi sửa đổi cũng có thể ít hơn. Về giá trị độ hữu ích của toàn bộ CSDL có thể ít hơn so với thuật toán SMAU, có thể nhiều hơn thuật toán SMIU. Về thay đổi độ hữu ích của các tập mục độ hữu ích cao thì thuật toán đề xuất có thể ít hơn hẳn so với hai thuật toán SMAU và SMIU. Để có cơ sở đánh giá khách quan hơn, thuật toán đề xuất được chạy thực nghiệm trên CSDL thực tế và được trình bày trong phần V. BMS_2 BMS_2 20000 99.5 Thời gian thực hiện (ms) 15000 99 DUS(%) 10000 98.5 5000 98 0 97.5 150 180 200 250 280 300 150 180 200 250 280 300 Số tập mục nhạy cảm Số tập mục nhạy cảm SMAU SMIU ProAlg SMAU SMIU ProAlg (a) (b) BMS_2 BMS_2 12000 30 11000 20 MC(%) IUS(%) 10000 10 9000 0 150 180 200 250 280 300 150 180 200 250 280 300 Số tập mục nhạy cảm Số tập mục nhạy cảm SMAU SMIU ProAlg SMAU SMIU ProAlg (c) (d) Hình 1. Kết quả chạy thực nghiệm trên dữ liệu BMS_2
  9. Nguyễn Khắc Chiến, Nguyễn Trọng Nghĩa 421 V. KẾT QUẢ THỰC NGHIỆM A. Mô tả dữ liệu và hệ thống thực nghiệm Thực nghiệm được thực hiện trên máy tính Intel ® Core™ i7 CPU 2.00GHz, RAM 8GB chạy trên Windows 10. Các thuật toán được cài đặt bằng ngôn ngữ Java. CSDL thực ngiệm được lấy trên trang web http://www.philippe- fournier-viger.com/spmf/index.php?link=datasets.php được mô tả trong Bảng 11. CSDL được thực hiện tạo thêm số lượng các mục trong từng giao tác một cách ngẫu nhiên, lấy các giá trị trong khoảng �1-10� và các giá trị lợi nhuận của mỗi mục cũng được tạo ra một cách ngẫu nhiên. Thuật toán đề xuất được so sánh với các thuật toán SMAU và SMIU trong công trình [11]. Các thuật toán được so sánh về thời gian thực hiện, chi phí ẩn nhầm các tập mục không nhạy cảm (MC), độ tương tự về độ hữu ích của CSDL trước và sau quá trình ẩn (DUS) và độ tương tự về độ hữu ích của các tập mục độ hữu ích cao trước và sau quá trình ẩn (IUS). Với các phép đo này, nếu giá trị của MC càng lớn, tức là việc ẩn nhầm các tập mục không nhạy càng nhiều do đó thuật toán không hiệu quả. Nếu giá trị DUS và IUS càng lớn, tức là việc sửa đổi dữ liệu diễn ra ít hơn, việc giảm độ hữu ích của toàn bộ CSDL (DUS) và độ hữu ích của các tập mục độ hữu ích cao (IUS) trước và sau quá trình ẩn ít hơn thì thuật toán được đánh giá là hiệu quả trên các phép đo này. Mushroom Mushroom 60000 100 Thời gianthwcj hiện (ms) 40000 99 DUS (%) 20000 98 0 97 50 60 70 80 90 100 50 60 70 80 90 100 Số tập mục nhạy cảm Số tập mục nhạy cảm SMAU SMIU ProAlg SMAU SMIU ProAlg (a) (b) Mushroom Mushroom 100 20 95 15 MC (%) IUS (%) 90 10 85 80 5 75 0 50 60 70 80 90 100 50 60 70 80 90 100 Số tập mục nhạy cảm Số tập mục nhạy cảm SMAU SMIU ProAlg SMAU SMIU ProAlg (c) (d) Hình 2. Kết quả chạy thực nghiệm trên dữ liệu Mushroom Trong quá trình ẩn các tập mục nhạy cảm làm sao để giảm thiểu các hiệu ứng phụ trên các thông tin không nhạy cảm thường quan trọng hơn việc giảm thời gian thực hiện. Do đó, trong bài báo này sẽ tập trung vào việc giảm các hiệu ứng phụ được tạo ra trong quá trình ẩn các tập mục độ hữu ích cao nhạy cảm. Trong thực nghiệm chạy các thuật toán đề xuất (ProAlg) và các thuật toán trong [11], các phép đo để đánh giá là thời gian thực hiện, MC, DUS và IUS trên hai bộ dữ liệu thực là BMS_2 và Mushroom. Hai bộ dữ liệu này đã được nhiều công trình sử dụng để đánh giá các thuật toán của mình. B. Kết quả thực nghiệm Trong phần này, sử dụng thuật toán EFIM [19] để khai thác các tập mục độ hữu ích cao trong CSDL BMS_2 và Mushroom.
  10. 422 CHIẾN LƯỢC HIỆU QUẢ ẨN CÁC TẬP MỤC HỮU ÍCH CAO NHẠY CẢM TRÊN CƠ SỞ DỮ LIỆU GIAO TÁC Trong Hình 1 là kết quả so sánh thuật toán đề xuất (ProAlg) với các thuật toán SMAU và SMIU với số lượng số tập mục nhạy cảm được lấy một cách ngẫu nhiên, với số lượng lần lượt là: 150, 180, 200, 250, 280 và 300 chạy trên CSDL thưa BMS_2. Hình 1a cho thấy thời gian thực hiện của thuật toán đề xuất thường nhiều hơn so với hai thuật toán còn lại. Tuy nhiêu, trong Hình 1(b), cho thấy thuật toán SMIU hiệu quả nhất về phép đo DUS. Thuật toán đề xuất (ProAlg) hiệu quả hơn thuật toán SMAU về độ đo DUS. Bên cạnh đó, Hình 1(d) lại cho thấy thuật toán đề xuất (ProAlg) lại hiệu quả nhất về độ đo độ tương tự độ hữu ích các tập mục độ hữu ích cao (IUS), độ hữu ích của các tập mục độ hữu ích cao của CSDL sau quá trình ần của thuật toán đề xuất lớn nhất, điều này cũng chứng tỏ việc ẩn nhầm các tập mục không nhạy cảm của thuật toán đề xuất là ít nhất, như được thể hiện trong Hình 1c. Tương tự, Hình 2 là kết quả chạy thực nghiệm trên CSDL Mushroom với số lượng số tập mục nhạy cảm được lấy một cách ngẫu nhiên, với số lượng lần lượt là: 50, 60, 70, 80, 90 và 100. Kết quả cũng tương tự như trên, thời gian thực hiện của thuật toán đề xuất (ProAlg) nhiều nhất. Tuy nhiên, thuật toán đề xuất (ProAlg) lại tốt nhất trên hai độ đo MC và IUS. Về độ đo DUS, thuật toán đề xuất hiệu quả hơn nhiều so với thuật toán SMAU, nhưng vẫn kém thuật toán SMIU. Điều này cũng đúng vì thuật toán SMIU thường loại bỏ các mục có độ hữu ích nhỏ nhất. Còn thuật toán SMAU thường loại bỏ các mục có độ hữu ích cao nhất. VI. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Bài báo đã đề xuất được một thuật toán ẩn các tập mục độ hữu ích cao nhạy cảm trong CSDL giao tác hiệu quả dựa vào chiến lược lựa chọn giao tác sửa đổi và mục sửa đổi đã được trình bày ở trên. Kết quả thực nghiệm đã cho thấy, thuật toán đề xuất hiệu quả hơn thuật toán SMAU và SMIU trong công trình [11] về chi phí ẩn nhầm các tập mục không nhạy (MC) và độ tương tự về độ hữu ích của các tập mục độ hữu ích cao (IUS) trên CSDL thực nghiệm. Về độ đo độ tương tự của CSDL (DUS), thuật toán đề xuất tốt hơn thuật toán SMAU và kém hơn so với thuật toán SMIU. Ngược lại, thời gian thực hiện của thuật toán đề xuất lại nhiều hơn hai thuật toán còn lại. Trong tương lai, chúng tôi tiếp tục cải tiến và thử nghiệm thuật toán đề xuất trên các CSDL giao tác khác và so sánh với các thuật toán ẩn khác để đánh giá tính hiệu quả của thuật toán đề xuất. TÀI LIỆU THAM KHẢO [1]. Agrawal, R. and R. Srikant. Privacy-preserving data mining. Proceedings of the 2000 ACM SIGMOD international conference on Management of data, 2000. [2]. Atallah, M., et al. Disclosure limitation of sensitive rules. Proceedings 1999 Workshop on Knowledge and Data Engineering Exchange (KDEX'99)(Cat. No. PR00453). 1999. IEEE. [3]. Fournier‐Viger, P., et al., A survey of itemset mining. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 7(4): p. e120, 2017. [4]. Gkoulalas-Divanis, A., J. Haritsa, and M. Kantarcioglu, Privacy issues in association rule mining, in Frequent Pattern Mining. Springer. p. 369-401, 2014. [5]. Huynh Trieu, V., H. Le Quoc, and C. Truong Ngoc, An efficient algorithm for hiding sensitive-high utility itemsets. Intelligent Data Analysis, 24(4): p. 831-845, 2020. [6]. Krishnamoorthy, S., Pruning strategies for mining high utility itemsets. Expert Systems with Applications, 42(5): p. 2371- 2381, 2015. [7]. Lee, G. and Y. C. Chen, Protecting sensitive knowledge in association patterns mining. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2(1): p. 60-68, 2012. [8]. Lin, C. W., et al., A GA-based approach to hide sensitive high utility itemsets. The Scientific World Journal, 2014. [9]. Lin, J. C. W., et al. A sanitization approach of privacy preserving utility mining. in International Conference on Genetic and Evolutionary Computing, 2015. Springer. [10]. Lin, J. C. W., et al., Fast algorithms for hiding sensitive high-utility itemsets in privacy-preserving utility mining. Engineering Applications of Artificial Intelligence, 55: p. 269-284, 2016. [11]. Liu, X., S. Wen, and W. Zuo, Effective sanitization approaches to protect sensitive knowledge in high-utility itemset mining. Applied Intelligence, 50(1): p. 169-191, 2020. [12]. Mendes, R. and J. P. Vilela, Privacy-preserving data mining: methods, metrics, and applications. IEEE Access, 5: p. 10562- 10582, 2017. [13]. O'Leary, D. E., Knowledge Discovery as a Threat to Database Security. Knowledge discovery in databases, 9: p. 507-516, 1991. [14]. Selvaraj, R. and V. M. Kuthadi, A modified hiding high utility item first algorithm (HHUIF) with item selector (MHIS) for hiding sensitive itemsets, 2013. [15]. Verykios, V. S., Association rule hiding methods. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 3(1): p. 28-36, 2013. [16]. Vo, B., et al. An Efficient Method for Hiding High Utility Itemsets. in KES-AMSTA, 2013. [17]. Yeh, J. S. and P. C. Hsu, HHUIF and MSICF: Novel algorithms for privacy preserving utility mining. Expert Systems with Applications 37(7): p. 4779-4786, , 2010. [18]. Yun, U. and J. Kim, A fast perturbation algorithm using tree structure for privacy preserving utility mining. Expert Systems with Applications, 42(3): p. 1149-1165, 2015. [19]. Zida, S., et al. EFIM: a highly efficient algorithm for high-utility itemset mining. Mexican international conference on artificial intelligence, 2015. Springer.
  11. Nguyễn Khắc Chiến, Nguyễn Trọng Nghĩa 423 AN EFFECTIVE STRATEGY TO HIDE SENSITIVE HIGH UTILITY ITEMSETS IN TRANSACTION DATABASE Nguyen Khac Chien, Nguyen Trong Nghia ABSTRACT: The problem of hiding sensitive high utility itemsets is a topic of interest to many researchers. The goal of the problem is to protect sensitive information in transactional databases, so that they cannot be discovered by methods of mining high utility itemsets with the same minimum utility threshold. In addition, methods for hiding sensitive high utility itemsets attempt to minimize side effects on non-sensitive information and on the integrity of the original database. Some commonly side effect measures are being used, such as the Missing Cost (MC) of hiding non-sensitive itemsets, Database Utility Similarity (DUS) before and after the hiding process, Itemset Utility Similarity (IUS) before and after the hidden process, etc. There are already some effective hiding methods to deal with this problem, but these methods still cause undesirable side effects, such as hiding multiple non-sensitive itemsets, similarity of low utility of database, etc. This paper proposes an efficient modification strategy to hide sensitive high utility itemsets while minimizing side effects on non-sensitive information and increase database similarity. Experimental results show that the proposed algorithm is more efficient than the existing algorithms in terms of side effects, such as hiding less sensitive information, ensuring the quality of the database after the hiding process.
nguon tai.lieu . vn
Tin học văn phòng Đồ họa - Thiết kế - Flash Quản trị Web Cơ sở dữ liệu Quản trị mạng Kỹ thuật lập trình Hệ điều hành Phần cứng An ninh - Bảo mật Chứng chỉ quốc tế Thủ thuật máy tính Điện - Điện tử Kinh tế học Hoá học Xã hội học Môi trường