intTypePromotion=1
ADSENSE

Ẩn tập mục hữu ích trung bình cao nhạy cảm

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

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

Bảo vệ tính riêng tư trong khai phá tập mục hữu ích trung bình cao (PPAUIM) có mục đích che giấu đi các thông tin riêng tư/nhạy cảm ẩn chứa trong cơ sở dữ liệu (CSDL) sao cho chúng không thể được khai thác bởi các thuật toán khai phá tập mục hữu ích trung bình cao (HAUIM) khi chia sẻ CSDL ra bên ngoài. Bài viết này tập trung nghiên cứu và đề xuất thuật toán ẩn tập mục hữu ích trung bình cao nhạy cảm có tên gọi là EHSHA-UI dựa trên phương pháp tối ưu cục bộ.

Chủ đề:
Lưu

Nội dung Text: Ẩn tập mục hữu ích trung bình cao nhạy cảm

  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.0063 ẨN TẬP MỤC HỮU ÍCH TRUNG BÌNH CAO NHẠY CẢM Huỳnh Triệu Vỹ1, Lê Quốc Hải2, Trương Ngọc Châu3, Lê Quốc Hiếu4 Trường Đại học Phạm Văn Đồng 1 Trường Cao đẳng Sư phạm Quảng Trị 2 3 Trường Đại học Bách khoa Đà Nẵng 4 Trường Đại học Kinh tế Luật, Đại học Quốc gia TP. Hồ Chí Minh htvy@pdu.edu.vn, hailq79@gmail.com, truongngocchau@yahoo.com, hieulq@uel.edu.vn TÓM TẮT: Bảo vệ tính riêng tư trong khai phá tập mục hữu ích trung bình cao (PPAUIM) có mục đích che giấu đi các thông tin riêng tư/nhạy cảm ẩn chứa trong cơ sở dữ liệu (CSDL) sao cho chúng không thể được khai thác bởi các thuật toán khai phá tập mục hữu ích trung bình cao (HAUIM) khi chia sẻ CSDL ra bên ngoài. Có nhiều phương pháp tiếp cận để giải quyết vấn đề này, trong đó phương pháp phổ biến nhất hiện nay là sử dụng kỹ thuật sửa đổi một số mục dữ liệu tại một số giao tác của CSDL gốc để tạo ra một bản sao CSDL sao cho các thông tin riêng tư/nhạy cảm không thể khai thác được từ bản sao CSDL. Việc sửa đổi các mục dữ liệu có thể gây ra các hiệu ứng phụ đối với bản sao CSDL như: làm mất đi các mục không nhạy cảm hoặc sinh ra các mục dữ liệu mới, làm thay đổi về cấu trúc của CSDL gốc. Vì vậy, mục tiêu của các thuật toán trong PPAUIM là giấu đi các thông tin riêng tư/nhạy cảm sao cho hiệu ứng phụ là thấp nhất. Bài báo này tập trung nghiên cứu và đề xuất thuật toán ẩn tập mục hữu ích trung bình cao nhạy cảm có tên gọi là EHSHA-UI dựa trên phương pháp tối ưu cục bộ. Để giảm hiệu ứng phụ, chúng tôi đưa ra các điều kiện lựa chọn mục mục tiêu và giao tác mục tiêu hiệu quả cho từng trường hợp sửa các mục dữ liệu. Thuật toán được chạy thực nghiệm trên 4 CSDL thực. Kết quả cho thấy thuật toán mà chúng tôi đề xuất có hiệu ứng phụ thấp hơn thuật toán hiện tại. Từ khóa: Che giấu dữ liệu, khai phá hữu ích cao, tập mục hữu ích trung bình cao, tập mục hữu ích trung bình cao nhạy cảm. I. GIỚI THIỆU Khai phá tập mục hữu ích cao (HUIM) là kỹ thuật trích chọn những tập mục có độ hữu ích không nhỏ hơn ngưỡng hữu ích tối thiểu [1-5]. Giá trị hữu ích của tập mục được định nghĩa là tổng hữu ích của các mục trong tập mục đó tại các giao tác chứa tập mục. Điều này có nghĩa là giá trị hữu ích của một tập mục trong cùng một giao tác sẽ tăng lên theo độ dài của nó. Như vậy, khai phá tập mục hữu ích cao chỉ dựa trên cùng một ngưỡng hữu ích tối thiểu để áp dụng cho tất cả các tập mục có độ dài khác nhau là không mang tính phổ quát cao [6]. Để khắc phục hạn chế này, Hong Tzung-Pei và cộng sự [6] đề xuất một mô hình khai phá mới dựa trên hữu ích trung bình của tập mục gọi là khai phá tập mục hữu ích trung bình cao với thuật toán hai pha: Pha thứ nhất tìm tập ứng viên, trong pha này sử dụng đơn vị đo chặn trên của hữu ích trung bình (average utility upper bound) để tỉa tập ứng viên; pha thứ hai thực hiện quét qua CSDL 1 lần để kiểm tra các ứng viên có phải là hữu ích trung bình cao hay không. Dựa trên nền tảng này nhiều thuật toán khai phá tập mục hữu ích trung bình cao hiệu quả hơn cũng được đề xuất [7-10]. Trong thời đại công nghệ số phát triển thì lĩnh vực khai phá dữ liệu càng trở nên hữu ích đối với cuộc sống của con người. Các công cụ khai phá và phân tích dữ liệu được sử dụng để trích xuất ra các thông tin hữu ích ẩn chứa trong các CSDL mà con người không thể nhìn thấy được bằng mắt thường hoặc các công cụ phân tích đơn giản. Các thông tin khai thác được có thể bao gồm các thông tin mang tính chất riêng tư hoặc nhạy cảm mà chủ sở hữu hay các đối tượng liên quan không muốn bị tiết lộ ra bên ngoài (ví dụ: Thông tin về bí mật kinh doanh trong CSDL kinh doanh, thông tin về bệnh án của bệnh nhân,...) bởi vì các thông tin này có thể gây ra các mối đe dọa về quyền riêng tư hoặc bí mật kinh doanh. Chính vì vậy, vấn đề bảo vệ quyền riêng tư trong quản lý dữ liệu là một vấn đề quan trọng. Phương pháp được sử dụng phổ biến hiện nay để thực hiện bảo vệ quyền riêng tư trong khai phá dữ liệu là kỹ thuật chuyển đổi dữ liệu để đảm bảo thông tin riêng tư/nhạy cảm không bị khai thác từ CSDL chuyển đổi [11]. Để giải quyết bài toán che giấu dữ liệu trong khai phá tập mục hữu ích cao (PPUIM), Jieh-Shan Yeh và cộng sự [12] đề xuất phương pháp ẩn tập mục hữu ích cao nhạy cảm bằng phương pháp giảm hữu ích nội của mục hoặc xóa mục trong tập mục nhạy cảm với hai thuật toán có tên là 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 [13-15]. Không thể áp dụng các thuật toán PPUIM để giải quyết bài toán che giấu dữ liệu trong khai phá tập mục hữu ích trung bình cao vì tính chất của hai bài toán này là khác nhau. Chính vì vậy, năm 2018 các tác giả trong [16] đề xuất phương pháp và thuật toán ẩn tập mục hữu ích trung bình cao nhạy cảm có tên là HHAUSI. Phương pháp tiếp cận của thuật toán này là sửa cơ sở dữ liệu gốc để giảm giá trị hữu ích trung bình của tập mục nhạy cảm xuống thấp hơn ngưỡng hữu ích trung bình tối thiểu. Thuật toán HHAUSI sử dụng ba đơn vị đo lường để đánh giá hiệu ứng phụ của thuật toán, gồm: HF (Tỷ lệ tập mục hữu ích trung bình cao nhạy cảm không ẩn được); MC (Tỷ lệ tập mục hữu ích trung bình cao không nhạy cảm bị mất); DIF (Tỷ lệ sai khác giữa CSDL gốc so với CSDL sửa đổi). Phương pháp chọn mục mục tiêu và giao tác mục tiêu để sửa dữ liệu của thuật toán HHAUSI là tương tự như thuật toán HHUIF [15] nên hiệu ứng phụ của thuật toán vẫn còn cao, bởi vì phương pháp lựa chọn mục mục tiêu và giao tác mục tiêu để sửa của thuật toán HHUIF là dựa vào mục có độ hữu ích cao nhất. Để giải quyết hạn chế của thuật toán HHAUSI, trong bài báo này chúng tôi đề xuất thuật toán có tên gọi là EHSHA-UI (an Efficient algorithm for Hiding Sensitive High Average-Utility Itemsets), thuật toán EHSHA-UI sử dụng các phương pháp chọn lựa mục mục tiêu và giao tác mục tiêu khác nhau cho từng trường hợp mục mục tiêu được xóa và sửa để giảm hiệu ứng phụ.
  2. 228 ẨN TẬP MỤC HỮU ÍCH TRUNG BÌNH CAO NHẠY CẢM Phần còn lại của bài báo được trình bày như sau: Phần II trình bày về các vấn đề liên quan đến khai phá tập mục hữu ích trung bình cao và ẩn tập mục hữu ích trung bình cao nhạy cảm. Phần III là phần quan trọng nhất của bài báo là đề xuất thuật toán và kết quả thực nghiệm và phần cuối là kết luận của bài báo. II. CÁC VẤN ĐỀ LIÊN QUAN A. Khai phá tập mục hữu ích trung bình cao Mô hình khai phá tập phổ biến [17] không đề cập đến vai trò của các mục và xem chúng có vai trò như nhau trong CSDL. Tuy nhiên, trong thực tế nếu vai trò của các mục được xem xét đến sẽ có ý nghĩa hơn, chính vì vậy Hong Yao và các cộng sự [1] đã đề xuất một mô hình để khai phá tập mục khi vai trò của các mục trong CSDL được xem xét, mô hình này gọi là khai phá tập mục hữu ích cao. Các đơn vị đo lường về hữu ích trong HUIM được phát biểu vắn tắt lại như sau: Phát biểu: Cho một tập mục hữu hạn 𝐼 = {𝑥1 , 𝑥2 , … , 𝑥𝑚 }. Mỗi mục 𝑥𝑖 ∈ 𝐼 có một giá trị hữu ích ngoại, ký hiệu là 𝑝(𝑥𝑖 ). Một CSDL giao tác 𝐷 = {𝑇1 , 𝑇2 , … , 𝑇𝑛 } gồm n giao tác, mỗi giao tác 𝑇𝑐 ⊆ 𝐼, 1 ≤ 𝑐 ≤ 𝑛 có một định danh gọi là Tid. Một tập mục 𝑋 = {𝑥1 , 𝑥2 , … , 𝑥𝑘 }, với 𝑥𝑖 ∈ 𝐼, 1 ≤ 𝑖 ≤ 𝑘. 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, ký hiệu là 𝑞(𝑥𝑖 , 𝑇𝑐 ). Bảng 1. CSDL Giao tác D Bảng 2. Giá trị hữu ích ngoại của CSDL D Tid Transaction Tid Transaction Item A B C D E F G H T1 A:4, C:1, E:6, F:2 T6 B:1, F:2, H:1 Utility 3 4 5 2 1 1 1 2 T2 D:1, E:4, F:5 T7 D:1, E:1, F:4, G:1, H:1 T3 B:3, D:1, E:5, F:1 T8 B:1, D:1, E:1 T4 D:1, E:2, F:6 T9 B:5, D:4, G:10 T5 A:3, C:1, E:1 T10 F:1 Giá trị hữu ích của một mục 𝑥𝑖 trong giao tác 𝑇𝑐 , ký hiệu là 𝑢(𝑥𝑖 , 𝑇𝑐 ), được xác định là 𝑢(𝑥𝑖 , 𝑇𝑐 ) = 𝑞(𝑥𝑖 , 𝑇𝑐 ) ∗ 𝑝(𝑥𝑖 ). Giá trị hữu ích của một tập muc X trong giao tác 𝑇𝑐 , ký hiệu là 𝑢(𝑋, 𝑇𝑐 ), được xác định là 𝑢(𝑋, 𝑇𝑐 ) = ∑𝑥𝑖 ∈𝑋 𝑢(𝑥𝑖 , 𝑇𝑐 ). Giá trị hữu ích của tập mục X trong CSDL giao tác D, ký hiệu là𝑢(𝑋), được xác định là 𝑢(𝑋) = ∑𝑋⊆𝑇𝑐,𝑇𝑐∈𝐷 𝑢(𝑋, 𝑇𝑐 ). HUIM là quá trình khai thác từ CSDL giao tác D tất cả các tập mục X có giá trị hữu ích không nhỏ hơn ngưỡng hữu ích tối thiểu ℰ cho trước. Gọi HUIs là tập gồm tất cả tập mục hữu ích cao được khai thác từ CSDL D với ngưỡng hữu ích tối thiểu ℰ thì 𝐻𝑈𝐼𝑠 = {𝑋|𝑢(𝑋) ≥ ℰ}. Ví dụ, 𝑢(𝐴, 𝑇1 ) = 12; 𝑢(𝐴, 𝑇5 ) = 9; 𝑢(𝐴) = 21; 𝑢({𝐴𝐶}, 𝑇1 ) = 17; 𝑢({𝐴𝐶}, 𝑇5 ) = 14; 𝑢({𝐴𝐶}) = 31 HAUIM là một mở rộng của HUIM để khai phá tập mục hữu ích cao dựa trên ngưỡng hữu ích trung bình được đề xuất bởi Hong Tzung-Pei và cộng sự [6], cụ thể: Cho trước một ngưỡng hữu ích trung bình tối thiểu 𝛽, HAUIM là một quá trình khai phá từ CSDL D tất cả các tập mục X có giá trị hữu ích trung bình không nhỏ hơn 𝛽. Các định nghĩa cơ sở về HAUIM [6] được định nghĩa như sau: Định nghĩa 1: Hữu ích trung bình của tập mục X trong một CSDL D, ký hiệu là 𝑎𝑢(𝑋), được định nghĩa: 𝑎𝑢(𝑋) = ∑𝑋⊆𝑇𝑐,𝑇𝑐∈𝐷 𝑎𝑢(𝑋, 𝑇𝑐 ), trong đó, 𝑎𝑢(𝑋, 𝑇𝑐 ) là hữu ích trung bình của tập mục X trong giao tác 𝑇𝑐 , được định nghĩa: ∑𝑥𝑖∈𝑋 𝑢(𝑥𝑖 , 𝑇𝑐 ) 𝑎𝑢(𝑋, 𝑇𝑐 ) = |𝑋| Ví dụ, 𝑎𝑢(𝐴, 𝑇1 ) = 12; 𝑎𝑢(𝐴, 𝑇5 ) = 9; 𝑎𝑢(𝐴) = 21; 𝑎𝑢({𝐴𝐶}, 𝑇1 ) = 8,5; 𝑎𝑢({𝐴𝐶}, 𝑇5 ) = 7; 𝑎𝑢({𝐴𝐶}) = 15.5. Định nghĩa 2: Một tập mục X được gọi là tập mục hữu ích trung bình cao trong CSDL D nếu giá trị hữu ích trung bình của X không nhỏ hơn ngưỡng hữu ích trung bình tối thiểu 𝛽 cho trước. Gọi HAUIs là tập gồm các tập mục hữu ích trung bình cao, khi đó HAUIs được xác định: 𝐻𝐴𝑈𝐼𝑠 = {𝑋|𝑎𝑢(𝑋) ≥ 𝛽} B. Ẩn tập mục hữu ích trung bình cao nhạy cảm Định nghĩa 3 (Tập mục hữu ích trung bình cao nhạy cảm): Một tập mục 𝑆𝑖 ∈ 𝐻𝐴𝑈𝐼𝑠 được xác định là tập mục mà chủ sở hữu CSDL không muốn bị khai thác bởi các thuật toán HAUIM khi CSDL được chia sẻ hoặc công bố ra bên ngoài, khi đó tập mục 𝑆𝑖 được gọi là tập mục hữu ích trung bình cao nhạy cảm. Gọi SHAUIs là tập gồm các tập mục hữu ích trung bình cao nhạy cảm thì: 𝑆𝐻𝐴𝑈𝐼𝑠 = {𝑆𝑖 |𝑆𝑖 ∈ 𝐻𝐴𝑈𝐼𝑠}. Định nghĩa 4: Ẩn tập các tập mục 𝑆𝐻𝐴𝑈𝐼𝑠 là quá trình sửa đổi CSDL gốc D trở thành CSDL sửa đổi D' (để chia sẻ hoặc công bố ra bên ngoài), sao cho chỉ duy nhất các tập mục hữu ích trung bình cao không nhạy cảm có thể được khai phá từ CSDL D' bởi các thuật toán HAUIM.
  3. Huỳnh Triệu Vỹ, Lê Quốc Hải, Trương Ngọc Châu, Lê Quốc Hiếu 229 Định nghĩa 5 (Mục mục tiêu): Mục mục tiêu (𝑥𝑣𝑖𝑐 ) là mục thuộc tập mục hữu ích trung bình cao nhạy cảm 𝑆𝑖 cần ẩn, sao cho khi giảm giá trị hữu ích nội của mục 𝑥𝑣𝑖𝑐 tại giao tác hỗ trợ tập mục 𝑆𝑖 sẽ giảm thiểu được hiệu ứng phụ của quá trình sửa đổi này gây ra trên CSDL. Định nghĩa 6 (Giao tác mục mục tiêu): Giao tác mục tiêu (𝑇𝑣𝑖𝑐 ) là giao tác mà khi giảm giá trị hữu ích nội của mục 𝑥𝑣𝑖𝑐 tại giao tác 𝑇𝑣𝑖𝑐 sẽ giảm thiểu được hiệu ứng phụ của quá trình sửa đổi này gây ra trên CSDL. Vấn đề PPUIM theo hướng tiếp cận sửa đổi dữ liệu gốc để tạo ra một bản dữ liệu sửa đổi luôn gây ra các hiệu ứng phụ, tức là CSDL sửa đổi luôn luôn có sự sai khác so với CSDL gốc. Chính vì vậy, mục tiêu của các thuật toán PPUIM là che giấu được tất cả thông tin riêng tư nhưng đảm bảo giảm thiểu được hiệu ứng phụ. Các đơn vị đo lường về hiệu ứng phụ của thuật toán PPUIM được các nhà nghiên cứu sử dụng phổ biến hiện nay [12-15]: Tập ma (Appearing Ghost): Là tập mục không phải là tập mục hữu ích cao trong CSDL gốc nhưng trở thành tập mục hữu ích cao trong CSDL sửa đổi; Tập mục bị mất (Missing Cost ): Là tập mục hữu ích cao không nhạy cảm trong CSDL gốc nhưng không là tập mục hữu ích cao không nhạy cảm trong CSDL sửa đổi; Ẩn lỗi (Hiding Failures): Tập mục hữu ích cao nhạy cảm vẫn khai thác được từ CSDL sửa đổi. Các đơn vị đo lường về sự tương đồng giữa CSDL sửa đổi so với CSDL gốc: Tỷ lệ tương đồng về cấu trúc giữa hai CSDL (Database Structure Similarity); Tỷ lệ tương đồng về giá trị hữu ích của CSDL (Database utility similarity); Tỷ lệ tương đồng về giá trị hữu ích của tập mục (Itemsets Utility Similarity) được khai thác từ các CSDL. Để đánh giá hiệu ứng phụ của thuật toán ẩn tập mục hữu ích trung bình cao nhạy cảm, chúng tôi định nghĩa các đơn vị đo lường này dựa trên các đơn vị đo lường được sử dụng trong PPUIM như sau: Định nghĩa 7 (AG-Appearing Ghost): AG là số lượng tập mục HAUI không nhạy cảm được khai phá từ CSDL sửa đổi (nonHAUIs') nhưng không phải là HAUI không nhạy cảm được khai phá từ CSDL gốc (nonHAUIs), được xác định như sau: 𝐴𝐺 = |𝑛𝑜𝑛𝐻𝐴𝑈𝐼𝑠′\𝑛𝑜𝑛𝐻𝐴𝑈𝐼𝑠| Định nghĩa 8 (HF-Hiding Failure): HF là số lượng tập mục SHAUI vẫn khai thác được từ CSDL sửa đổi, được xác định như sau: 𝐻𝐹 = |𝑆𝐻𝐴𝑈𝐼𝑠 ∩ 𝐻𝐴𝑈𝐼𝑠′| Định nghĩa 9 (MC- Miss cost): MC là tỷ lệ giữa tập mục HAUI không nhạy cảm (nonSHAUIs) không thể khai thác được từ CSDL sửa đổi so với số lượng HAUI không nhạy cảm (nonSHAUIs) được khai thác từ CSDL gốc, được xác định như sau: |𝑛𝑜𝑛𝑆𝐻𝐴𝑈𝐼𝑠| − |𝑛𝑜𝑛𝑆𝐻𝐴𝑈𝐼𝑠′| 𝑀𝐶 = |𝑛𝑜𝑛𝑆𝐻𝐴𝑈𝐼𝑠| Định nghĩa 10 (DSS - Database Structure Similarity): DSS là tỷ lệ tương đồng về cấu trúc của CSDL sửa đổi D' so với CSDL gốc D, được xác định như sau: 𝐷 ∪𝑡𝑝 𝐷′ | |𝑡𝑝𝑘 𝑘 𝐷𝑆𝑆 = � � (𝑓𝑟𝑒𝑞(𝑡𝑝𝑘𝐷 ) − 𝑓𝑟𝑒𝑞(𝑡𝑝𝑘𝐷 ))2 𝑘=1 trong đó 𝑡𝑝𝑘𝐷 và 𝑡𝑝𝑘𝐷 ′ lần lượt là mẫu giao tác thứ k trong CSDL D và D'. 𝑓𝑟𝑒𝑞(𝑡𝑝𝑘𝐷 ) và 𝑓𝑟𝑒𝑞(𝑡𝑝𝑘𝐷 ′) lần lượt là độ phổ biến của mẫu giao tác thứ k trong CSDL D và D'. Định nghĩa 11 (DUS - Database utility similarity): DUS là tỷ lệ tương đồng về hữu ích giữa CSDL D' với CSDL D, được xác định như sau: ∑𝑇 ∈𝐷′ 𝑡𝑢(𝑇𝑐 ) 𝑐 𝐷𝑈𝑆 = ∑𝑇𝑐 ∈𝐷 𝑡𝑢(𝑇𝑐 ) , với 𝑡𝑢(𝑇𝑐 ) là hữu ích của giao tác 𝑇𝑐 và được định nghĩa: 𝑡𝑢(𝑇𝑐 ) = ∑𝑥𝑖 ∈𝑇𝑐 𝑢( 𝑥𝑖 , 𝑇𝑐 ) Định nghĩa 12 (IUS - Itemsets Utility Similarity): IUS là tỷ lệ tương đồng về hữu ích trung bình của tập các HAUI trong CSDL sửa đổi D' (HAUIs') so với tập các HAUI trong CSDL gốc D (HAUIs), được xác định như sau: ∑𝑋∈𝐻𝐴𝑈𝐼𝑠′ 𝑎𝑢(𝑋) 𝐼𝑈𝑆 = ∑𝑋∈𝐻𝐴𝑈𝐼𝑠 𝑎𝑢(𝑋) III. THUẬT TOÁN ẨN TẬP MỤC HỮU ÍCH TRUNG BÌNH CAO ĐỀ XUẤT A. Đề xuất thuật toán Đề ẩn tập mục hữu ích trung bình cao nhạy cảm, các tác giả trong [16] đề xuất thuật toán HHAUSI theo hướng tiếp cận can thiệp vào CSDL gốc để sửa giá trị hữu ích nội của mục thuộc tập mục nhạy cảm tại các giao tác hỗ trợ tập mục nhạy cảm. Mục đích giảm độ hữu ích trung bình của các tập mục cần ẩn xuống thấp hơn ngưỡng hữu ích trung bình tối thiểu để tạo ra một bản CSDL sửa đổi D' sao cho các tập mục hữu ích trung bình cao nhạy cảm không thể khai thác
  4. 230 ẨN TẬP MỤC HỮU ÍCH TRUNG BÌNH CAO NHẠY CẢM được bởi các thuật toán HAUIM từ CSDL D'. Ưu điểm của thuật toán HHAUSI là không có hiệu ứng phụ về AG và HF. Tuy nhiên, nhược điểm của thuật toán này là hiệu ứng phụ MC vẫn còn cao do phương pháp chọn mục mục tiêu và giao tác mục tiêu trong HHAUSI là hoàn toàn giống nhau cho trường hợp xóa mục mục tiêu cũng như trường hợp giảm giá trị hữu ích nội của mục mục tiêu. Để khắc phục hạn chế này, trong phần này chúng tôi đề xuất thuật toán thực hiện ẩn SHAUIs có tên gọi EHSHA-UI với cách chọn giao tác mục tiêu và mục mục tiêu hiệu quả cho mỗi trường hợp. 1. Phương pháp tiếp cận của thuật toán EHSHA-UI Với phương pháp tiếp cận sửa các mục dữ liệu của CSDL gốc để ẩn các SHAUI thì hiệu ứng phụ của thuật toán phụ thuộc vào: (a) Phương pháp chọn mục mục tiêu và giao tác mục tiêu; (b) Xác định giá trị hữu ích nội tối thiểu cần giảm hay xóa mục. (a) Xác định giá trị hữu ích nội tối thiểu cần giảm hay xóa mục: Giả sử mục mục tiêu và giao tác mục tiêu được chọn để sửa dữ liệu nhằm mục đích ẩn tập mục 𝑆𝑖 lần lượt là 𝑥𝑣𝑖𝑐 và 𝑇𝑣𝑖𝑐 . Theo Định nghĩa 2, khi 𝑆𝑖 là tập mục hữu ích trung bình cao thì 𝑑 = 𝑎𝑢(𝑆𝑖 ) − 𝛽 ≥ 0. Để ẩn được 𝑆𝑖 ta cần lặp quá trình giảm giá trị hữu ích trung bình của 𝑆𝑖 cho đến khi 𝑑 = 𝑎𝑢(𝑆𝑖 ) − 𝛽 < 0. Để giảm giá trị hữu ích trung bình của 𝑆𝑖 , có thể thực hiện bằng cách giảm giá trị hữu ích nội của mục 𝑥𝑣𝑖𝑐 ∈ 𝑆𝑖 tại giao tác 𝑇𝑣𝑖𝑐 . Gọi 𝑘 là giá trị hữu ích nội cần giảm từ mục 𝑥𝑣𝑖𝑐 ∈ 𝑆𝑖 tại giao tác 𝑇𝑣𝑖𝑐 , để 𝑑 < 0. Khi đó ta có: 𝑘 ∗ 𝑝(𝑥𝑣𝑖𝑐 ) 𝑑 ∗ |𝑆𝑖 | 𝑑− (1) |𝑆𝑖 | 𝑝(𝑥𝑣𝑖𝑐 ) 𝑑∗|𝑆𝑖 | Vì 𝑞(𝑥𝑣𝑖𝑐 , 𝑇𝑣𝑖𝑐 ) ∈ ℤ+ ⇒ 𝑘 = � + 1�. 𝑝(𝑥𝑣𝑖𝑐 ) Nếu 𝑘 ≥ 𝑞(𝑥𝑣𝑖𝑐 , 𝑇𝑣𝑖𝑐 ) đồng nghĩa với việc xóa mục 𝑥𝑣𝑖𝑐 ∈ 𝑆𝑖 ra khỏi giao tác 𝑇𝑣𝑖𝑐 . Quá trình sửa dữ liệu để ẩn tập mục 𝑆𝑖 chỉ kết thúc khi 𝑘 ≤ 𝑞(𝑥𝑣𝑖𝑐 , 𝑇𝑣𝑖𝑐 ). (b) Xác định mục mục tiêu và giao tác mục tiêu: Gọi SA là tập các tập mục hữu ích trung bình cao không nhạy cảm chịu tác động bởi quá trình sửa dữ liệu để ẩn tập mục nhạy cảm 𝑆𝑖 . Khi đó: - Nếu giảm giá trị hữu ích nội của mục 𝑥𝑣𝑖𝑐 ∈ 𝑆𝑖 tại giao tác 𝑇𝑣𝑖𝑐 , giá trị hữu ích trung bình của tập mục 𝑆𝑖 và các tập mục 𝑋 ∈ 𝑆𝐴 chịu tác động sẽ bị giảm lần lượt là: 𝑘 ∗ 𝑝(𝑥𝑣𝑖𝑐 ) 𝑎𝑢(𝑆𝑖 ) = 𝑎𝑢(𝑆𝑖 ) − (2) |𝑆𝑖 | 𝑘 ∗ 𝑝(𝑥𝑣𝑖𝑐 ) 𝑎𝑢(𝑆𝑖 ) = 𝑎𝑢(𝑆𝑖 ) − (3) |𝑆𝑖 | 𝑘 ∗ 𝑝(𝑥𝑣𝑖𝑐 ) (4) 𝑎𝑢(𝑋) = 𝑎𝑢(𝑋) − , 𝑋 ∈ 𝑆𝐴 |𝑋| - Nếu một mục 𝑥𝑣𝑖𝑐 ∈ 𝑆𝑖 được xóa khỏi giao tác 𝑇𝑣𝑖𝑐 thì giá trị hữu ích trung bình của tập mục 𝑆𝑖 và các tập mục 𝑋 ∈ 𝑆𝐴 chịu tác động sẽ bị giảm lần lượt là: 𝑢(𝑆𝑖 ) = 𝑎𝑢(𝑆𝑖 ) − 𝑎𝑢(𝑆𝑖 , 𝑇𝑣𝑖𝑐 ) (5) 𝑎𝑢(𝑋) = 𝑎𝑢(𝑋) − 𝑎𝑢(𝑋, 𝑇𝑣𝑖𝑐 ), 𝑋 ∈ 𝑆𝐴 (6) 𝑘∗𝑝(𝑥𝑣𝑖𝑐 ) Bởi vì, 𝑎𝑢(𝑋, 𝑇𝑣𝑖𝑐 ) > |𝑋| , nên khi xóa mục 𝑥𝑣𝑖𝑐 ∈ 𝑆𝑖 tại giao tác 𝑇𝑣𝑖𝑐 sẽ làm cho hữu ích trung bình của các tập mục chịu tác động bị giảm nhiều hơn khi giảm giá trị hữu ích nội của mục 𝑥𝑣𝑖𝑐 ∈ 𝑆𝑖 tại giao tác 𝑇𝑣𝑖𝑐 , điều này sẽ dẫn đến số tập mục bị tác động sẽ bị ẩn theo sẽ nhiều hơn. Vì vậy, khi giảm giá trị hữu ích nội của một mục 𝑥𝑣𝑖𝑐 ∈ 𝑆 tại giao tác 𝑇𝑣𝑖𝑐 sẽ ẩn được 𝑆𝑖 được ưu tiên lựa chọn để giảm hiệu ứng phụ. Nghĩa là cặp mục mục tiêu và giao tác mục tiêu được ưu tiên lựa chọn là cặp 𝑝𝑎𝑖𝑟(𝑥𝑣𝑖𝑐 , 𝑇𝑣𝑖𝑐 ) sao cho 𝑞(𝑥𝑣𝑖𝑐 , 𝑇𝑣𝑖𝑐 ) > 𝑘. Ngược lại, nếu không tồn tại cặp 𝑝𝑎𝑖𝑟(𝑥𝑣𝑖𝑐 , 𝑇𝑣𝑖𝑐 ) sao cho 𝑞(𝑥𝑣𝑖𝑐 , 𝑇𝑣𝑖𝑐 ) > 𝑘, cần phải lặp quá xóa mục 𝑥𝑣𝑖𝑐 ∈ 𝑆 ra khỏi giao tác mục tiêu 𝑇𝑣𝑖𝑐 mới có thể ẩn được tập mục 𝑆𝑖 . Để quá trình ẩn tập mục 𝑆𝑖 nhanh hội tụ và giảm được số lần xóa dữ liệu nhằm giảm sự thay đổi về cấu trúc giữa CSDL gốc so với CSDL sửa đổi, trong trường hợp này giao tác mục tiêu được ưu tiên lựa chọn là giao tác 𝑇𝑣𝑖𝑐 sao cho 𝑎𝑢(𝑆𝑖 , 𝑇𝑣𝑖𝑐 ) đạt cực đại. Mục mục tiêu được ưu tiên lựa chọn là mục 𝑥𝑣𝑖𝑐 ∈ 𝑆𝑖 , sao cho khi xóa mục này tại giao tác 𝑇𝑣𝑖𝑐 ít tác động đến các tập mục hữu ích trung bình cao không nhạy cảm nhất. 2. Đề xuất thuật toán a) Mô tả thuật toán EHSHA-UI Thuật toán EHSHA-UI được viết dưới dạng giải mã ở Mục b) và được mô tả như sau: - Đầu vào: CSDL gốc D là CSDL sẽ khai thác được các tập mục hữu ích trung bình cao nhạy cảm; tập các tập mục SHAUIs là các tập mục hữu ích trung bình cao nhạy cảm được khai thác từ CSDL D cần được ẩn; ngưỡng hữu ích trung bình tối thiểu 𝛽.
  5. Huỳnh Triệu Vỹ, Lê Quốc Hải, Trương Ngọc Châu, Lê Quốc Hiếu 231 - Đầu ra: CSDL sửa đổi D' là CSDL đã được sửa đổi sao cho tập SHAUIs không thể khai thác được bởi các thuật toán HAUIM với ngưỡng hữu ích trung bình 𝛽. - Thực hiện ẩn lần lượt các tập mục hữu ích trung bình cao nhạy cảm 𝑺𝒊 ∈ 𝑺𝑯𝑨𝑼𝑰𝒔. Với mỗi tập mục 𝑆𝑖 , thực hiện các bước: + Tính giá trị sai khác giữa giá trị hữu ích trung bình của 𝑆𝑖 so với ngưỡng hữu ích trung bình tối thiểu 𝛽 (dòng 2). Quét qua CSDL D một lần để rút ra từ D tất cả các giao tác chứa 𝑆𝑖 (tập ST ) nhằm hỗ trợ cho quá trình tìm giao tác mục tiêu và mục mục tiêu (dòng 3). + Lặp quá trình sửa dữ liệu cho đến khi 𝑑 < 0. Với mỗi lần lặp, thực hiện: Duyệt qua tập ST để tìm cặp 𝑑∗|𝑆𝑖 | (𝑥𝑣𝑖𝑐 , 𝑇𝑣𝑖𝑐 ) thỏa mãn điều kiện 𝑞(𝑥𝑣𝑖𝑐 , 𝑇𝑣𝑖𝑐 ) > � + 1�(dòng 5). Nếu tồn tại (𝑥𝑣𝑖𝑐 , 𝑇𝑣𝑖𝑐 ) chỉ cần sửa giá trị 𝑝(𝑥𝑣𝑖𝑐 ) 𝑑∗|𝑆𝑖 | 𝑞(𝑥𝑣𝑖𝑐 , 𝑇𝑣𝑖𝑐 ) thành 𝑞(𝑥𝑣𝑖𝑐 , 𝑇𝑣𝑖𝑐 ) − � + 1� là ẩn được 𝑆𝑖 (dòng 6-8). Ngược lại, nếu không tồn tại cặp (𝑥𝑣𝑖𝑐 , 𝑇𝑣𝑖𝑐 ) 𝑝(𝑥𝑣𝑖𝑐 ) 𝑑∗|𝑆𝑖 | thỏa mãn điều kiện 𝑞(𝑥𝑣𝑖𝑐 , 𝑇𝑣𝑖𝑐 ) > � + 1�, cần phải thực hiện xóa mục mục tiêu ra khỏi giao tác mục tiểu. Trong 𝑝(𝑥𝑣𝑖𝑐 ) trường hợp này giao tác mục tiêu và mục mục tiêu cần được xác định lại như sau: Quét lại ST để tìm giao tác 𝑇𝑣𝑖𝑐 sao cho 𝑎𝑢(𝑆𝑖 , 𝑇𝑣𝑖𝑐 ) đạt cực đại (dòng 10) nhằm mục đích làm cho quá trình ẩn tập mục 𝑆𝑖 nhanh hội tụ. Sau khi giao tác mục tiêu được xác định, mục mục tiêu được chọn là mục 𝑥𝑣𝑖𝑐 sao cho khi xóa mục này tại giao tác 𝑇𝑣𝑖𝑐 tác động đến ít tập mục hữu ích trung bình cao không nhạy cảm nhất (dòng 11). Cập nhật lại giá trị của 𝑑, xóa mục 𝑥𝑣𝑖𝑐 ra khỏi 𝑇𝑣𝑖𝑐 và loại 𝑇𝑣𝑖𝑐 ra khỏi ST (dòng 12-14). b) Mã giả thuật EHSHA-UI EHSHA-UI(D; SHAUIs; 𝛽){ 1 𝑓𝑜𝑟𝑒𝑎𝑐ℎ(𝑆𝑖 ∈ 𝑆𝐻𝐴𝑈𝐼𝑠) 𝑑𝑜 2 𝑇í𝑛ℎ 𝑑 = 𝑎𝑢(𝑆𝑖 ) − 𝛽; 3 𝑋á𝑐 đị𝑛ℎ 𝑡ậ𝑝 𝑆𝑇 𝑔ồ𝑚 𝑐á𝑐 𝑔𝑖𝑎𝑜 𝑡á𝑐 ℎỗ 𝑡𝑟ợ 𝑆𝑖 ;// nhằm giới hạn không gian tìm kiếm mục mục tiêu và giao tác mục tiêu 4 𝑤ℎ𝑖𝑙𝑒((𝑑 ≥ 0)𝑑𝑜 //lặp quá trình sửa dữ liệu 𝑑∗|𝑆𝑖 | 5 𝑄𝑢é𝑡 𝑞𝑢𝑎 𝑡ậ𝑝 𝑆𝑇 để 𝑡ì𝑚 𝑐ặ𝑝 𝑝𝑎𝑖𝑟(𝑥𝑣𝑖𝑐 , 𝑇𝑣𝑖𝑐 ) 𝑠𝑎𝑜 𝑐ℎ𝑜 𝑞(𝑥𝑣𝑖𝑐 , 𝑇𝑣𝑖𝑐 ) > 𝑘, 𝑘 = � + 1�; 𝑝(𝑥𝑣𝑖𝑐 ) 6 𝑖𝑓(∃ 𝑝𝑎𝑖𝑟(𝑥𝑣𝑖𝑐 , 𝑇𝑣𝑖𝑐 ))// giảm giá trị hữu ích nội là ẩn được 𝑆𝑖 7 𝑞(𝑥𝑣𝑖𝑐 , 𝑇𝑣𝑖𝑐 ) = 𝑞(𝑥𝑣𝑖𝑐 , 𝑇𝑣𝑖𝑐 ) − 𝑘; 8 𝑑 = −1; //kết thúc sửa dữ liệu vì 𝑆𝑖 đã được ẩn 9 𝑒𝑙𝑠𝑒 10 𝑄𝑢é𝑡 𝑞𝑢𝑎 𝑡ậ𝑝 𝑆𝑇 để 𝑡ì𝑚 𝑇𝑣𝑖𝑐 𝑠𝑎𝑜 𝑐ℎ𝑜 𝑎𝑢(𝑆𝑖 , 𝑇𝑣𝑖𝑐 ) đạ𝑡 𝑐ự𝑐 đạ𝑖; 11 𝑇ì𝑚 𝑥𝑣𝑖𝑐 ∈ 𝑆𝑖 , 𝑠𝑎𝑜 𝑐ℎ𝑜 𝑥𝑣𝑖𝑐 í𝑡 𝑝ℎổ 𝑏𝑖ế𝑛 𝑛ℎấ𝑡 𝑡𝑟𝑜𝑛𝑔 𝑡ậ𝑝 {𝑋 ∈ 𝑛𝑜𝑛𝐻𝐴𝑈𝐼𝑠|𝑋 ⊆ 𝑇𝑣𝑖𝑐 }; 12 𝐶ậ𝑝 𝑛ℎậ𝑡 𝑙ạ𝑖 𝑑 = 𝑑 − 𝑎𝑢(𝑆𝑖 , 𝑇𝑣𝑖𝑐 ); 13 𝑞(𝑥𝑣𝑖𝑐 , 𝑇𝑣𝑖𝑐 ) = 0; //𝑋ó𝑎 𝑥𝑣𝑖𝑐 𝑟𝑎 𝑘ℎỏ𝑖 𝑇𝑣𝑖𝑐 ; 14 𝐿𝑜ạ𝑖 𝑇𝑣𝑖𝑐 𝑟𝑎 𝑘ℎỏ𝑖 𝑆𝑇; 15 Cập nhật CSDL; 16 Return D'; 17 } B. Kết quả thực nghiệm 1. Mô tả CSDL Các cơ sở dữ liệu chạy thực nghiệm chúng tôi sử dụng được công bố tại [18], chi tiết về các CSDL này được mô tả trong bảng 3. Tập nhạy cảm được chọn ngẫu nhiên từ tập HAUIs được khai thác bởi thuật toán HAUIMiner [7] với ngưỡng hữu ích trung bình tối thiểu được xác định theo tỷ lệ phần trăm của của giá trị hữu ích của CSDL, chi tiết được mô tả trong bảng 4. Bảng 3. Mô tả tập CSDL thực nghiệm CSDL #|D| #|I| #AvgLen #MaxLen Retail 88.162 16.470 10,3 76 Foodmart 4,141 1,559 4 11 Mushroom 8.124 119 23 23 Chess 3.196 75 37 40 Chú thích: #|D|: Tổng số giao tác; #|I|: Tổng số mục trong CSDL; #AvgLen: Độ dài trung bình của giao tác trong CSDL; #MaxLen: Độ dài cực đại của giao tác trong CSDL. 2. Mô tả hệ thống máy tính: CPU Core I5 2.4GHz, RAM 8GB, Windows 10. 3. Ngôn ngữ cài đặt: Các thuật toán chạy thực nghiệm được cài đặt bởi ngôn ngữ Java. 4. So sánh và đánh giá kết quả thực nghiệm.
  6. 232 ẨN TẬP MỤC HỮU ÍCH TRUNG BÌNH CAO NHẠY CẢM Bảng 4. Mô tả thông tin của các tập nhạy cảm Retail Foodmart Mushroom Chess Kích Kích Kích Kích β(%) β(%) β(%) β(%) thước thước thước thước |HAUIs|=6221 |HAUIs|=1936 |HAUIs|=1334 |HAUIs|=704 SHAUIs SHAUIs SHAUIs SHAUIs 30 30 10 10 40 40 20 20 0.01 0.015 0.015 0.035 50 50 30 30 60 60 40 40 a) MC: Đơn vị đo MC nhằm cho biết tỷ lệ tập mục hữu ích trung bình cao không nhạy cảm không thể khai thác được từ CSDL sửa đổi so với số tập mục hữu ích trung bình cao không nhạy cảm được khai thác từ CSDL gốc. Đơn vị đo lường này rất qua trọng trong việc đánh giá tỷ lệ sai lệch về tập HAUIs được khai thác từ CSDL sửa đổi trước khi chủ sở hữu chia sẻ dữ liệu. Quá trình thực nghiệm cho thấy quá trình sửa dữ liệu để ẩn tập SHAUIs của thuật toán EHSHA-UI gây ra hiệu ứng phụ MC thấp hơn thuật toán HHAUSI, bởi vì thuật toán EHSHA-UI áp dụng phương pháp heuristic để lựa chọn giao tác mục tiêu và mục mục tiêu khác nhau cho trường hợp giảm giá trị hữu ích của mục tiêu và trường hợp xóa mục mục tiêu tại giao tác mục tiêu nhằm giảm thiểu các tác động lên các tập mục chịu ảnh hưởng của quá trình sửa dữ liệu. Hình 1 là kết quả so sánh về hiệu ứng phụ MC giữa các thuật toán trên các CSDL. 4 a) Retail 6 b) Foodmart 100 c) Mushroom 100 d) Chess 3 Miss cost(%) Miss cost(%) Miss cost(%) Miss cost(%) 4 2 50 50 2 1 0 0 0 0 30 40 50 60 30 40 50 60 10 20 30 40 10 20 30 40 Sensitive itemsets size Sensitive itemsets size Sensitive itemsets size Sensitive itemsets size Hình 1. Tỷ lệ MC khi thực hiện ẩn các tập SHAUIs b) HF và AG: Đơn vị đo HF dùng để đánh giá xem tập các tập mục hữu ích trung bình cao nhạy cảm đã được ẩn hoàn toàn từ CSDL sửa đổi hay chưa. Đơn vị đo AG được sử dụng để đánh giá CSDL sửa đổi có sinh ra tập mục hữu ích trung bình mới so với CSDL gốc hay không. Kết quả thực nghiệm cho thấy cả hai thuật toán đều cho kết quả HF=0 và AG=0. Bởi vì, cả hai thuật toán đều thực hiện ẩn lần lượt từng tập mục nhạy cảm cho đến khi tất cả các tập mục nhạy cảm được ẩn bằng phương pháp 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 tại giao tác mục tiêu nên không làm tăng giá trị hữu ích trung bình của các tập mục, chính vì vậy không xảy ra trường hợp vẫn còn tập mục nhạy cảm không ẩn được và cũng không xuất hiện tập mục hữu ích trung bình cao mới trong quá trình ẩn. c) Thời gian thực thi: Thời gian thực thi của thuật toán HHAUSI và EHSHA-UI phụ thuộc vào chiến lượt chọn giao tác mục tiêu và mục mục tiêu, đồng thời còn phụ thuộc vào cấu trúc của từng CSDL và độ dài của các tập mục nhạy cảm cần ẩn. Đối với thuật toán HHAUSI chỉ áp dụng duy nhất một phương pháp chọn mục mục tiêu và giao tác mục tiêu, còn thuật toán EHSHA-UI ưu tiên tìm giao tác mục tiêu và mục mục tiêu thỏa mãn điều kiện để giảm giá trị hữu ích nội của mục mục tiêu có thể ẩn được tập nhạy cảm, trường hợp không có cặp mục mục tiêu và giao tác mục tiêu thỏa mãn điều kiện này thì quá trình chọn mục mục tiêu và giao tác mục tiêu được thực hiện trở lại cho trường hợp xóa mục mục tiêu, việc này nhằm mục đích giảm thiểu hiệu ứng phụ về MC và giảm thiểu các thay đổi về cấu trúc của dữ liệu nên thời gian thực thi sẽ tăng lên. Việc giảm hiệu ứng phụ là quan trọng nên thuật toán EHSHA-UI có thời gian thực thi chậm hơn thuật toán HHAUSI. Hình 2 là kết quả so sánh thời gian thực thi của hai thuật toán. 40 a) Retail 1 b) Foodmart 100 c) Mushroom 80 d) Chess 30 1 60 Runtime(s) Runtime(s) Runtime(s) Runtime(s) 20 0 50 40 10 0 20 0 0 0 0 30 40 50 60 30 40 50 60 10 20 30 40 10 20 30 40 Sensitive itemsets size Sensitive itemsets size Sensitive itemsets size Sensitive itemsets size Hình 2. Thời gian thực hiện ẩn các tập SHAUIs
  7. Huỳnh Triệu Vỹ, Lê Quốc Hải, Trương Ngọc Châu, Lê Quốc Hiếu 233 d) DSS, DUS và IUS: Để có nhiều góc nhìn về trong đánh giá sự sai lệch giữa CSDL gốc so với CSDL sửa đổi do quá trình sửa dữ liệu để ẩn SHAUIs, bài báo này sử dụng 3 đơn vị đo lường, bao gồm: DSS cho biết tỷ lệ tương đồng về cấu trúc dữ liệu; DUS cho biết tỷ lệ tương đồng về giá trị hữu ích của CSDL và IUS cho biết tỷ lệ tương đồng về giá trị hữu ích trung bình của tập HAUIs giữa CSDL gốc và CSDL sửa đổi. Kết quả thực nghiệm (Hình 3, 4 và 5) cho thấy rằng thuật toán EHSHA-UI ít làm thay đổi cấu trúc của CSDL hơn so với thuật toán HHAUSI. Bởi vì, chiến lược chọn giao tác mục tiêu và mục mục tiêu của thuật toán EHSHA-UI tối ưu hơn thuật toán HHAUSI nên dẫn đến hiệu ứng phụ về DSS, DUS và IUS của thuật toán EHSHA-UI là tốt hơn thuật toán HHAUSI. 100.0 a) Retail 98 b) Foodmart 100 c) Mushroom 100 d) Chess 99.9 96 80 80 DSS(%) DSS(%) DSS(%) DSS(%) 99.8 94 60 60 99.7 99.6 92 40 40 99.5 90 20 20 30 40 50 60 30 40 50 60 10 20 30 40 10 20 30 40 Sensitive itemsets size Sensitive itemsets size Sensitive itemsets size Sensitive itemsets size Hình 3. Tỷ lệ DSS khi thực hiện ẩn các tập SHAUIs 100.0 a) Retail 99 b) Foodmart 100 c) Mushroom 100 d) Chess 99.6 99 98 DUS(%) DUS(%) DUS(%) DUS(%) 98 99.2 96 98 98.8 94 96 98.4 98 92 98.0 97 90 94 30 40 50 60 30 40 50 60 10 20 30 40 10 20 30 40 Sensitive itemsets size Sensitive itemsets size Sensitive itemsets size Sensitive itemsets size Hình 4. Tỷ lệ DUS khi thực hiện ẩn các tập các tập SHAUIs 100.0 a) Retail 99 b) Foodmart 100 c) Mushroom 100 d) Chess 99.0 98 80 80 IUS(%) IUS(%) IUS(%) IUS(%) 98.0 97 60 60 97.0 96 40 40 96.0 95 20 20 95.0 94 0 0 30 40 50 60 30 40 50 60 10 20 30 40 10 20 30 40 Sensitive itemsets size Sensitive itemsets size Sensitive itemsets size Sensitive itemsets size Hình 5. Tỷ lệ IUS khi thực hiện ẩn các tập các tập SHAUIs IV. KẾT LUẬN Ẩn tập mục hữu ích trung bình cao nhạy cảm là công việc nhằm mục đích che giấu các thông tin riêng tư/nhạy cảm mà chủ sở hữu không muốn chúng bị khai thác bởi các thuật toán HAUIM, để tránh các rủi ro gặp phải khi các thông tin này bị khai thác và sử dụng vào các mục đích mà có thể gây ra các tác động xấu cho chủ sở hữu CSDL hoặc các cá nhân có liên quan. Trong bài báo này chúng tôi đã đề xuất thuật toán để ẩn các tập mục hữu ích trung bình cao nhạy cảm có tên gọi là EHSHA-UI theo hướng tiếp cận sửa CSDL gốc một cách tự động để tạo ra một bản CSDL sao chép sao cho các tập hữu ích trung bình cao nhạy cảm không thể khai thác được từ CSDL sao chép trước khi chúng được chia sẻ ra bên ngoài. Để giảm thiểu hiệu ứng phụ của quá trình sửa đổi dữ liệu gây ra, chúng tôi sử dụng các phương pháp lựa chọn mục mục tiêu và giao tác mục tiêu khác nhau cho trường hợp giảm giảm giá trị hữu ích nội của mục mục tiêu và trường hợp xóa mục mục tiêu. Thuật toán được chạy thực nghiệm trên 4 CSDL có đặc tính khác nhau (được mô tả trong Bảng 3) với số lượng tập mục hữu ích trung bình cao nhạy cảm khác nhau được chọn ngẫu nhiên từ tập HAUIs được khai thác bởi thuật toán HAUIMiner[7]. Kết quả thực nghiệm cũng cho thấy rằng thuật toán EHSHA- UI hiệu quả hơn thuật toán HHAUSI.
  8. 234 ẨN TẬP MỤC HỮU ÍCH TRUNG BÌNH CAO NHẠY CẢM Mặc dù thuật toán EHSHA-UI hiệu quả hơn thuật toán HHAUSI, tuy nhiên cách tiếp cận của thuật toán EHSHA-UI dựa trên phương pháp tối ưu cục bộ nên chưa phải là thuật toán tối ưu nhất. Chính vì vậy, chúng tôi tiếp tục nghiên cứu để tối ưu hóa thuật toán. TÀI LIỆU THAM KHẢO [1] H. Yao, H. J. Hamilton, and C. J. Butz, “A foundational approach to mining itemset utilities from databases”, Proceedings of the 2004 SIAM International Conference on Data Mining, pp. 482-486: SIAM, 2004. [2] M. Liu and J. Qu, “Mining high utility itemsets without candidate generation”, Proceedings of the 21st ACM international conference on Information and knowledge management, pp. 55-64: ACM, 2012. [3] P. Fournier-Viger, C. W. Wu, S. Zida, and V. S. Tseng, “FHM: Faster high-utility itemset mining using estimated utility co- occurrence pruning”, International symposium on methodologies for intelligent systems, pp. 83-92: Springer, 2014. [4] J. M. T. Wu, J. C. W. Lin, and A. Tamrakar, “High-utility itemset mining with effective pruning strategies”, ACM Transactions on Knowledge Discovery from Data, vol. 13, No. 6, pp. 1-22, 2019. [5] M. K. Sohrabi, “An efficient projection-based method for high utility itemset mining using a novel pruning approach on the utility matrix”, Knowledge Information Systems, vol. 62, No. 11, pp. 4141-4167, 2020. [6] T. P. Hong, C. H. Lee, and S. L. Wang, “Mining high average-utility itemsets”, Systems, Man and Cybernetics, SMC. IEEE International Conference on, pp. 2526-2530: IEEE, 2009. [7] J. C. W. Lin, T. Li, P. Fournier-Viger, T. P. Hong, J. Zhan, and M. Voznak, “An efficient algorithm to mine high average- utility itemsets”, Advanced Engineering Informatics, vol. 30, No. 2, pp. 233-243, 2016. [8] T. Truong, H. Duong, B. Le, P. J. I. T. O. K. Fournier-Viger, and D. Engineering, “Efficient vertical mining of high average- utility itemsets based on novel upper-bounds”, vol. 31, No. 2, pp. 301-314, 2018. [9] T. Truong, H. Duong, B. Le, P. Fournier-Viger, and U. J. K.-B. S. Yun, “Efficient high average-utility itemset mining using novel vertical weak upper-bounds”, vol. 183, p. 104847, 2019. [10] K. K. Sethi and D. J. T. J. o. S. Ramesh, “A fast high average-utility itemset mining with efficient tighter upper bounds and novel list structure”, pp. 1-31, 2020. [11] W. Gan, J. Chun-Wei, H. C. Chao, S. L. Wang, and S. Y. Philip, “Privacy preserving utility mining: a survey”, IEEE International Conference on Big Data (Big Data), pp. 2617-2626: IEEE, 2018. [12] J. S. Yeh and P. C. Hsu, “HHUIF and MSICF: Novel algorithms for privacy preserving utility mining”, Expert Systems with Applications, vol. 37, No. 7, pp. 4779-4786, 2010. [13] C. W. Lin, T. P. Hong, J. W. Wong, G. C. Lan, and W. Y. Lin, “A GA-based approach to hide sensitive high utility itemsets”, The Scientific World Journal, vol. 2014. [14] J. C. W. Lin, T. Y. Wu, P. Fournier-Viger, G. Lin, J. Zhan, and M. Voznak, “Fast algorithms for hiding sensitive high-utility itemsets in privacy-preserving utility mining”, Engineering Applications of Artificial Intelligence, vol. 55, pp. 269-284, 2016. [15] V. Huynh Trieu, H. Le Quoc, and C. Truong Ngoc, “An efficient algorithm for hiding sensitive-high utility itemsets”, Intelligent Data Analysis, vol. 24, No. 4, pp. 831-845, 2020. [16] V. H. Trieu, H. L. Quoc, C. T. Ngoc, and N. N. Thanh, “A novel algorithm for hiding sensitive high average-utility itemsets”, 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, Trường ĐH Hồng Đức, Thanh Hóa, 2018, pp. 7-12: NXB Khoa học và Kỹ thuật. [17] R. Agrawal, T. Imieliński, and A. Swami, “Mining association rules between sets of items in large databases”, Acm sigmod record, 1993, vol. 22, No. 2, pp. 207-216: ACM. [18] P. Fournier-Viger, An open-source data mining library, 2019. Available: http://www.philippe-fournier- viger.com/spmf/index.php?link=datasets.php HIDING SENSITIVE HIGH AVERAGE-UTILITY ITEMSET Huynh Trieu Vy, Le Quoc Hai, Truong Ngoc Chau, Le Quoc Hieu ABSTRACT: Privacy presering sensitive high average-utility itemset mining (PPAUIM) aims at removing sensitive information implicit in a database such that it cannot be discovered by high average-utility itemset mining algorithms when sharing the database outside a party. To solve this problem, many approaches were proposed. The popular approach is to modify data items at some transactions in the original database in order to create a copy database in such a way that the sensitive information cannot be discovered from the copy one. However, modifying data items always cause side effects such as to hide non-sensitive itemsets, create new itemsets, and change database structure. The target of PPAUIM therefore is to hide all sensitive high average-utility itemsets (SHAUIs) with the least side effects. This paper proposes a heuristic algorithm, named EHSHA-UI, for hiding SHAUIs. In order to minimize side effects, the EHSHA-UI specifies victim item and victim transaction based on efficient estimation technique. The experiment is executed with four real databases. The experimental results indicate that the proposed algorithm achieves better performance in comparing with previous work.
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2