Ẩn tập mục hữu ích cao và phổ biến nhạy cảm

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

Thêm vào BST

Báo xấu

17
lượt xem 2
download

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

Bài viết nghiên cứu và đề xuất thuật toán có tên gọi là ATMTU để ẩn các tập mục hữu ích cao và phổ biến nhạy cảm (SHUFIs). Thuật toán ATMTU thực hiện qua 3 bước chính, gồm: (1) Xác định giảm độ hỗ trợ hay giảm giá trị hữu ích là hiệu quả hơn để ẩn SHUFIs; (2) Xác định giao tác mục tiêu và mục mục tiêu để sửa dữ liệu; (3) Sửa CSDL với mục và giao tác bị sửa được chọn ở bước 2. Kết quả thực nghiệm 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.

Chủ đề:

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

Lưu

Nội dung Text: Ẩn tập mục hữu ích cao và phổ biến nhạy cảm

Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR), Nha Trang, ngày 8-9/10/2020 DOI: 10.15625/vap.2020.00145 ẨN TẬP MỤC HỮU ÍCH CAO VÀ PHỔ BIẾN 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 1 Trường Đại học Phạm Văn Đồng 2 Trường Cao đẳng Sư phạm Quảng Trị 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. HCM htvy@pdu.edu.vn, hailq79@gmail.com, truongngocchau@yahoo.com, hieulq@uel.edu.vn TÓM TẮT: Mục đích của bài toán bảo vệ tính riêng tư trong khai phá hữu ích cao (PPUM) là can thiệp vào cơ sở dữ liệu (CSDL) để ẩn đi các thông tin nhạy cảm được khai thác bởi các thuật toán khai phá hữu ích cao (HUM) nhằm hạn chế các rủi ro mà chủ sở hữu dữ liệu gặp phải khi chia sẻ CSDL ra bên ngoài. Tuy nhiên, việc tác động vào dữ liệu để che giấu thông tin thường sinh ra các hiệu ứng phụ như mất mát hoặc dư thừa thông tin. Mục đích của các thuật toán PPUM là thực hiện thao tác che dấu các dữ liệu riêng tư hay nhạy cảm của CSDL trước khi chúng được chia sẻ ra bên ngoài sao cho hiệu ứng phụ của quá trình che dấu là tối thiểu. Bài báo này chúng tôi nghiên cứu và đề xuất thuật toán có tên gọi là ATMTU để ẩn các tập mục hữu ích cao và phổ biến nhạy cảm (SHUFIs). Thuật toán ATMTU thực hiện qua 3 bước chính, gồm: (1) Xác định giảm độ hỗ trợ hay giảm giá trị hữu ích là hiệu quả hơn để ẩn SHUFIs; (2) Xác định giao tác mục tiêu và mục mục tiêu để sửa dữ liệu. Ở bước này chúng tôi đưa ra các chiến lược heuristic khác nhau để xác định mục mục tiêu và giao tác mục tiêu cho từng phương án được lựa chọn ở bước thứ nhất nhằm giảm thiểu hiệu ứng phụ; (3) Sửa CSDL với mục và giao tác bị sửa được chọn ở bước 2. Kết quả thực nghiệm 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: Tập mục hữu ích cao, tập mục hữu ích cao và phổ biến, tập mục hữu ích cao và phổ biến nhạy cảm. I. GIỚI THIỆU Khai phá tập mục hữu ích cao (HUIM) là mô hình trích chọn những tập mục (mẫu) có giá trị hữu ích lớn hơn hoặc bằng ngưỡng tối thiểu cho trước từ CSDL. Các mô hình HUIM hiện nay đang được các nhà nghiên cứu quan tâm phát triển và đưa vào ứng dụng trong nhiều lĩnh vực như quản lý chuỗi cung ứng, tài chính, y khoa, … Mô hình HUIM lần đầu tiên được đề xuất bởi H. Yao và cộng sự [1] và được cải tiến bởi nhiều thuật toán hiệu quả hơn [2-6]. Bên cạnh HUIM, nhiều mô hình HUIM biến thể hoặc mở rộng cũng được đề xuất, như: Khai phá tập mục hữu ích trung bình cao (HAUIM) [7], khai phá tập mục hữu ích cao đóng (HCUIM) [8], khai phá tập mục hữu ích cao hiếm (HURIM) [9], khai phá tập mục hữu ích cao và phổ biến (HUFIM) [10], khai phá mẫu hữu ích cao tuần tự từ CSDL tuần tự (HUSPM) [11],... Ngày nay, sự phát triển nhanh chóng của Công nghệ thông tin đang tạo môi trường thuận lợi để thúc đẩy hợp tác thương mại toàn cầu và kinh doanh xuyên quốc gia. Trong môi trường kinh doanh quốc tế, việc chia sẻ dữ liệu giữa các đối tác hoặc công bố ra bên ngoài internet là rất cần thiết để thúc đẩy sự phát triển. Tuy nhiên, bên trong dữ liệu có thể ẩn chứa các thông tin riêng tư hoặc nhạy cảm (gọi chung là thông tin nhạy cảm) mà chủ 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. Để đảm bảo các thông tin nhạy cảm không bị khai thác, dữ liệu trước khi chia sẻ cần phải được gọt, tỉa sao cho các thông tin nhạy cảm không thể bị khai thác trong khi vẫn duy trì được việc khai thác từ CSDL các thông tin có giá trị khác. Chính vì yêu cầu thực tế này, hơn một thập kỷ qua chủ đề bảo về tính riêng tư trong khai phá dữ liệu (PPDM) trở thành một chủ đề nghiên cứu quan trọng, được nhiều nhà nghiên cứu quan tâm [12-14]. Các mở rộng của PPDM cũng đã được đề xuất như: PPUM [15-18], Bảo vệ tính riêng tư trong khai phá mẫu hữu ích cao tuần tự (PPUSPM) [19], Bảo vệ tính riêng tư trong khai phá tập mục hữu ích cao và phổ biến (PPUFIM) [20]. Các thuật toán ẩn tập mục hữu ích cao và phổ biến nhạy cảm nói chung đều ẩn tập mục bằng cách tác động lên dữ liệu như giảm độ hữu ích, loại bỏ các mục trong một số các giao tác hoặc thêm vào các giao tác mới để làm cho độ hữu ích hoặc độ phổ biến của tập mục nhạy cảm đó giảm xuống dưới ngưỡng tối thiểu cho trước. Việc tác động lên dữ liệu thường làm sinh ra các hiệu ứng phụ như làm biến đổi số lượng tập mục hữu ích cao và thay đổi dữ liệu. Hiệu ứng phụ càng cao thì chất lượng của dữ liệu được chia sẻ càng thấp. Vì vậy, mục tiêu của hầu hết các bài toán PPUFIM [20] là giảm độ hữu ích hoặc độ hỗ trợ (hoặc cả hai tiêu chí) của tập mục nhạy cảm xuống dưới ngưỡng tối thiểu sao cho hiệu ứng phụ và chi phí là thấp nhất. Trong bài báo này, chúng tôi đề 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 các heuristics để (1) lựa chọn chính xác mục mục tiêu và giao tác mục tiêu, (2) lựa chọn giải pháp là giảm độ hữu ích hay giảm độ hỗ trợ của tập mục nhạy cảm xuống thấp hơn ngưỡng tối thiếu sao cho ít tác động đến kết quả khai phá dữ liệu nhất. Phần còn lại của bài báo được bố cục như sau: Phần II trình bày các vấn đề liên quan đến ẩn tập mục hữu ích cao và phổ biến nhạy cảm. 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 được trình bày trong phần III và cuối cùng là kết luận của bài báo. II. CÁC VẤN ĐỀ LIÊN QUAN A. Ẩn tập mục hữu ích cao và phổ biến nhạy cảm Bài toán ẩn tập mục hữu ích cao nhạy cảm được đề xuất lần đầu tiên bởi J.S. Yeh và các cộng sự [15] vào năm 2010. Trong nghiên cứu này, các tác giả đề xuất phương pháp ẩn tập mục hữu ích cao nhạy cảm bằng kỹ thuật can thiệp
Huỳnh Triệu Vỹ, Lê Quốc Hải, Trương Ngọc Châu, Lê Quốc Hiếu 17 vào CSDL gốc để giảm giá trị hữu ích của tập mục hữu ích cao nhạy cảm cần ẩn xuống thấp hơn ngưỡng hữu ích tối thiểu, bằng cách giảm giá trị hữu ích nội của mục mục tiêu hoặc xóa mục mục tiêu trong giao tác mục tiêu. Hai thuật toán được đề xuất trong [15] có tên là HHUIF (Hiding High Utility Item First Algorithm) và MSICF (Maximum Sensitive Itemsets Conflict First Algorithm). Phương pháp tối ưu để lựa chọn mục mục tiêu và giao tác mục tiêu mà thuật toán HHUIF áp dụng là chọn mục tại một giao tác thích hợp sao cho hữu ích của nó tại giao tác được chọn là cao nhất. Trong khi đó, để giảm số lần sửa dữ liệu, thuật toán MSICF lựa chọn mục mục tiêu là mục xuất hiện nhiều nhất trong các tập mục nhạy cảm. Nhược điểm của các thuật toán trong [15] là một số trường hợp tập mục nhạy cảm đã được ẩn nhưng quá trình sửa CSDL vẫn tiếp tục được thực hiện nên dẫn đến nhiều tập mục hữu ích cao bị mất; hơn nữa, trường hợp nếu giá trị hữu ích của tập mục nhạy cảm bằng với ngưỡng hữu ích tối thiểu thì tập mục nhạy cảm sẽ không được ẩn. C.W. Lin và cộng sự [17] đề xuất hai thuật toán có tên là MSU-MAU (Maximum Sensitive Utility-MAximum item Utility) và MSU-MIU(Maximum Sensitive Utility-Minimum Item Utility), các thuật toán này sử dụng lý thuyết Max-Min của hữu ích để giảm thiểu hiệu ứng phụ và sử dụng CSDL chiếu để tăng tốc độ sửa đổi dữ liệu trong quá trình ẩn tập mục nhạy cảm so với hai thuật toán được đề xuất trong [15]. Tuy nhiên, các thuật toán này vẫn không khắc phục được nhược điểm của các thuật toán trong [15]. Để khắc phục các hạn chế trong [17], V.H. Trieu và cộng sự [18] đề xuất thuật toán có tên HHUSI áp dụng heuristics vào lựa chọn mục mục tiêu và giao tác mục tiêu sao cho việc sửa đổi chúng trong CSDL tác động tối thiểu lên các mục hữu ích cao không nhạy cảm. Dựa trên giải thuật di truyền, C.W. Lin và cộng sự [16] đề xuất thuật toán ẩn tập mục nhạy cảm bằng phương pháp chèn vào CSDL các giao tác với thuật toán di truyền có tên là GA-based. Điểm nổi bật của thuật toán GA-based là áp dụng giải thuật di truyền để tính toán số giao tác tối thiểu cần chèn vào CSDL sao cho có thể ẩn được tập mục nhạy cảm. Kết quả thực nghiệm cho thấy thuật toán GA-based hiệu quả hơn các thuật toán trước đó. Tuy nhiên, nhược điểm của phương pháp chèn giao tác là làm xuất hiện các tập mục hữu ích cao mới, hay còn gọi là tập ma, là tập mà 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 bởi thuật toán này. Cũng dựa trên giải thuật di truyền, C.W. Lin và cộng sự [22] tiếp tục đề xuất thuật toán có tên gọi là PPUMGAT. Để ẩn tập mục hữu ích cao nhạy cảm PPUMGAT sử dụng phương pháp xóa giao tác chứ không phải chèn giao tác như trong [16]. Để xác định số giao tác cần xóa PPUMGAT dựa trên giải thuật di truyền đồng thời lý thuyết pre-large cũng được sử dụng để tăng tốc độ tính toán của thuật toán. Bài toán ẩn tập mục hữu ích cao và phổ biến nhạy cảm được đề xuất lần đầu tiên bởi Rajalaxmi và cộng sự [23]. Trong nghiên cứu này, các tác giả đề xuất 2 thuật toán có tên gọi là MSMU (Minimum Support and Maximum Utility) và MCRSU (Maximum Conflict Ratio for Support and Utility). Phương pháp tiếp cận trong [23] là sửa dữ liệu để giảm cả độ hỗ trợ và hữu ích của tập mục nhạy cảm xuống thấp hơn ngưỡng hỗ trợ tối thiểu và ngưỡng hữu ích tối thiểu. Cả hai thuật toán này ẩn tập mục nhạy cảm qua hai phiên sửa dữ liệu: Phiên 1 giảm độ hỗ trợ của các tập mục nhạy cảm xuống dưới ngưỡng hỗ trợ tối thiểu; Phiên 2 kiểm tra lại hữu ích của các tập mục nhạy cảm, nếu hữu ích của các tập mục nhạy cảm vẫn còn lớn hơn ngưỡng hữu ích tối thiểu thì tiếp tục sửa dữ liệu để giảm hữu ích của tập nhạy cảm xuống dưới ngưỡng hữu ích tối thiểu. Nhược điểm của hai thuật toán này là làm mất nhiều tập mục không nhạy cảm do phải thực hiện sửa dữ liệu để giảm cả độ hỗ trợ và hữu ích của tập mục nhạy cảm xuống thấp hơn ngưỡng tối thiểu. Để khắc phục hạn chế này, X. Liu [20] đề xuất thuật toán ẩn tập mục hữu ích cao và phổ biến nhạy cảm dựa trên kỹ thuật sửa dữ liệu gốc có tên là HUFI. Thuật toán này thực hiện lặp quá trình sửa dữ liệu cho đến khi hoặc là độ hỗ trợ hoặc là hữu ích của tập mục nhạy cảm thấp hơn ngưỡng tối thiểu. Để giảm hiệu ứng phụ trong [20] đưa ra khái niệm về giá trị biên cực đại và dựa vào biên cực đại để xác định là giảm độ hỗ trợ hay giảm hữu ích để ẩn tập mục nhạy cảm là hiệu quả hơn. Tuy nhiên, phương pháp chọn giao tác mục tiêu và mục mục tiêu của thuật toán HUFI là hoàn toàn giống nhau cho cả trường hợp giảm độ hỗ trợ và giảm giá trị hữu ích để ẩn tập mục nhạy cảm. Đây là nguyên nhân làm cho phương pháp này có thể làm tăng hiệu ứng phụ. Trên cơ sở phân tích các ưu, nhược điểm của các thuật toán đã được đề xuất, để giảm hiệu ứng phụ của quá trình ẩn luật, trong bài báo này chúng tôi đề xuất phương pháp heuristic để cực tiểu hóa quá trình ẩn tập mục bằng cách: (1) chọn cách ẩn tập mục một cách linh hoạt dựa trên giá trị biên cực đại đã đề xuất bởi X. Liu [20], (2) 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 độ hỗ trợ hay giảm hữu ích của tập mục. B. Phát biểu và các định nghĩa cơ sở Trong phần này chúng tôi trình bày lại các định nghĩa cơ bản trong FIM [24], HUIM [1] và HUFIM [10] mà chúng tôi sử dụng trong phần đề xuất thuật toán. Phát biểu: Cho { } là một tập hữu hạn gồm các mục . Mỗi mục có một giá trị hữu ích ngoại, ký hiệu là . Một tập mục { }, với . Một CSDL giao tác { } chứa n giao tác, mỗi giao tác có một định danh gọi là Tid. Mỗi mục trong giao tác kết hợp với một trọng số gọi là hữu ích nội (số lượng), ký hiệu là . CSDL cho trong Bảng 1 và 2 sẽ được sử dụng cho tất cả ví dụ trong bài báo này. Định nghĩa 1: Độ hỗ trợ của tập mục X trong CSDL D, ký hiệu là support(X), được định nghĩa: , Trong đó: { } Ví dụ, support({AC})
18 ẨN TẬP MỤC HỮU ÍCH CAO VÀ PHỔ BIẾN NHẠY CẢM 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) Định nghĩa 2: Một tập mục X được gọi là tập mục phổ biến trong CSDL D, nếu độ hỗ trợ của nó lớn hơn hoặc bằng ngưỡng hỗ trợ tối thiểu cho trước . Cho FIs là tập các tập mục phổ biến trong CSDL D thì FIs khi đó ta có: { } Định nghĩa 3: Hữu ích của mục trong một giao tác , ký hiệu là và được định nghĩa: . Ví dụ, u(A,T1) = q(A,T1) * p(A) = 3 * 4=12; u(C,T1) = q(C,T1) * p(C) = 1 * 5 = 5 Định nghĩa 4: Hữu ích của tập mục X trong một giao tác Tc, ký hiệu là , được định nghĩa: ∑ . Ví dụ, u({A,C},T1) = u(A,T1)+u(C,T1) = 17; u({A,C},T5) = u(A,T5)+u(C,T5) = 14 Định nghĩa 5: Hữu ích của tập mục X trong một CSDL giao tác D, ký hiệu là , được định nghĩa: ∑ HUIs X|X I,u X Ví dụ: u({A,C}) = u({A,C},T1)+u({A,C},T5) = 17+14 = 31. Định nghĩa 6: Giá trị hữu ích của giao tác Tc ký hiệu là ), được định nghĩa: ∑ Ví dụ: TU(T1) = 3*4+5*1+1*6+1*2 = 25. Định nghĩa 7: Hữu ích của CSDL D, ký hiệu u(D) và được định nghĩa: ∑ Ví dụ: u(D) = TU(T1) + TU(T2) + TU(T3) + TU(T4) + TU(T5) + TU(T6) + TU(T7) + TU(T8) + TU(T9)+ TU(T10) = 25+11+20+10+14+8+10+7+38+1 = 144. Định nghĩa 8: Tập mục X được gọi là tập mục hữu ích cao trong CSDL D, nếu giá trị hữu ích của X không nhỏ hơn ngưỡng hữu ích tối thiểu cho trước . Gọi HUIs là tập các tập mục hữu ích cao thì: { }. Ví dụ: với , tập mục hữu ích cao khai thác được từ CSDL cho trong Bảng 1 và 2 gồm các tập mục ở Bảng 3. Bảng 3. Tập các tập mục hữu ích cao Itemset Utility Itemset Utility Itemset Utility AC 31 B 40 BDG 38 AE 28 BD 48 DEF 36 ACE 38 BG 30 EF 36 ACEF 25 BDE 26 Định nghĩa 9: Tập mục X được gọi là tập mục hữu ích cao và phổ biến trong CSDL D, nếu tập mục X thỏa mãn đồng thời tập mục phổ biến và tập mục hữu ích cao. Gọi HUFIs là tập chứa các tập mục hữu ích cao và phổ biến, khi đó ta có: { } Ví dụ: bảng 4 là tập các tập mục hữu ích cao và phổ biến được khai phá từ CSDL cho ở bảng 1 và 2 với và .
Huỳnh Triệu Vỹ, Lê Quốc Hải, Trương Ngọc Châu, Lê Quốc Hiếu 19 Bảng 4. Tập các tập mục hữu ích cao và phổ biến Itemset Utility support Itemset Utility Support Itemset Utility support AC 31 0,2 B 40 0,4 DEF 36 0,3 AE 28 0,2 BD 48 0,3 EF 36 0,5 ACE 38 0,2 BDE 26 0,2 Định nghĩa 10: Tập các tập mục hữu ích cao và phổ biến nhạy cảm ký hiệu là SHUFIs, được định nghĩa: { } Định nghĩa 11: Ẩn tập các tập mục trong là quá trình sửa đổi CSDL gốc D trở thành CSDL D', sao cho chỉ duy nhất các tập mục hữu ích cao và phổ biến không nhạy cảm có thể được khai phá từ CSDL D'. Các thuật toán thực hiện bảo vệ thông tin riêng tư trong khai phá hữu ích cao theo hướng tiếp cận sửa dữ liệu gốc đều để lại các hiệu ứng phụ. Để đánh giá hiệu quả thuật toán, chúng tôi đã sử dụng các đơn vị đo lường được đề xuất bởi các tác giả trong [15, 17, 20], cụ thể các đơn vị đo lường này được định nghĩa như sau: Định nghĩa 12: (HF-Hiding Failure): HF là tỷ lệ tập mục hữu ích cao và phổ biến nhạy cảm được khai thác từ CSDL sửa đổi D' (SHUFIs') so với SHUFIs ban đầu: Định nghĩa 13: (MC- Miss cost): MC là tỷ lệ tập mục hữu ích cao và phổ biến không nhạy cảm (nonSHUFIs) đã bị mất do quá trình sửa đổi dữ liệu để ẩn SHUFIs gây ra, được định nghĩa như sau: Định nghĩa 14: (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 định nghĩa như sau: √ ∑ 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 15: (DUS - Database utility similarity): DUS là tỷ lệ tương đồng về hữu ích giữa CSDL D' với CSDL D, được định nghĩa như sau: ∑ ∑ Định nghĩa 16: (IUS - Itemsets Utility Similarity): IUS là tỷ lệ tương đồng về hữu ích của tập các tập mục hữu ích cao và phổ biến trong CSDL D' (HUFIs') so với tập các tập mục hữu ích cao và phổ biến trong CSDL D (HUFIs), được định nghĩa: ∑ ∑ III. THUẬT TOÁN ẨN TẬP MỤC HỮU ÍCH CAO VÀ PHỔ BIẾN NHẠY CẢM A. Đề xuất thuật toán Trong phần này chúng tôi đề xuất thuật toán thực hiện ẩn tập các tập mục hữu ích cao, phổ biến và nhạy cảm có tên gọi ATMTU (Ẩn tập mục tối ưu). 1. Mô tả thuật toán Phát biểu: Cho CSDL giao tác D, ngưỡng hữu ích tối thiểu và ngưỡng hỗ trợ tối thiểu , là một tập mục hữu ích cao và phổ biến nhạy cảm cần ẩn. Tập mục không còn là tập mục hữu ích cao và phổ biến nhạy cảm khi và chỉ khi hoặc hoặc . Để giảm độ hỗ trợ hay giá trị hữu ích của , cách tiếp cận trong thuật toán này là sửa CSDL gốc D bằng cách giảm giá trị hữu ích nội của mục mục tiêu hoặc xóa mục mục tiêu tại giao tác mục tiêu. Định nghĩa 17: Gọi là mục mục tiêu sao cho khi sửa mục tại các giao tác nhằm mục đích ẩn thì gây ra hiệu ứng phụ thấp nhất.
20 ẨN TẬP MỤC HỮU ÍCH CAO VÀ PHỔ BIẾN NHẠY CẢM Định nghĩa 18: Giao tác mục tiêu, ký hiệu , là giao tác chứa sao cho khi sửa mục tại giao tác nhằm mục đích ẩn thì cho hiệu ứng phụ là thấp nhất. Như vậy, để ẩn được tập mục , ta có 2 phương án để lựa chọn hoặc là giảm giá trị hữu ích của xuống thấp hơn ngưỡng hữu ích tối thiểu hoặc là giảm độ hỗ trợ của xuống thấp hơn ngưỡng hỗ trợ tối thiểu. Vấn đề cần giải quyết ở đây là chọn phương án nào là hiệu quả hơn? - Phương án 1: Giảm giá trị hữu ích của để : Thực hiện lặp quá trình giảm giá trị hữu ích nội của mục mục tiêu tại giao tác mục tiêu với giá trị hữu ích tối thiểu của cần giảm là: . - Phương án 2: Giảm độ hỗ trợ của để : Thực hiện lặp quá trình xóa mục mục tiêu ra khỏi giao tác mục tiêu với số lần tối thiểu là: ⌈ ⌉ Định nghĩa 19: Gọi SA là tập mục chịu tác động khi được sửa hoặc xóa tại thì tập các tập mục chịu sự tác động của quá trình sửa đổi dữ liệu này ký hiệu là setSA, được định nghĩa: { } Tất cả các thuật toán trong PPUM theo hướng tiếp cận sửa đổi dữ liệu gốc đều phải giải quyết được vấn đề chính là ẩn được tất cả thông tin nhạy cảm cho trước nhưng đảm bảo giảm thiểu hiệu ứng phụ của quá trình thực hiện ẩn gây ra. Với mỗi tập mục hữu ích cao và phổ biến nhạy cảm cần được ẩn, thuật toán mà chúng tôi đề xuất thực hiện qua ba bước chính: (1) Bước 1: Xác định chọn Phương án 1 hay Phương án 2 để ẩn tập mục là hiệu quả hơn. (2) Bước 2: Xác định mục mục tiêu và giao tác mục tiêu để sửa dữ liệu nhằm mục đích ẩn được tập mục sao cho hiệu ứng phụ là thấp nhất. (3) Bước 3: Sửa dữ liệu của mục mục tiêu tại giao tác mục tiêu đã được chọn ở bước 2. Như vậy, hiệu ứng phụ sẽ phụ thuộc vào chiến lược được lựa chọn ở bước 1 và bước 2. - Bước 1 (Lựa chọn phương án): Để lựa chọn phương án ẩn các tập mục SHUFIs các tác giả trong [20] đã đưa ra hai khái niệm về biên hữu ích cực đại và biên hữu ích cực tiểu và đã chứng minh được rằng lựa chọn Phương án 1 là hiệu quả hơn khi , ngược lại chọn Phương án 2 là hiệu quả hơn. Trong thuật toán ATMTU mà chúng tôi đề xuất trong bài báo này sẽ chọn phương án ẩn tập mục hữu ích cao và phổ biến nhạy cảm tương tự như phương án lựa chọn trong thuật toán HUFI [20]. - Bước 2 (Xác định mục mục tiêu và giao tác mục tiêu): Chiến lược lựa chọn giao tác mục tiêu và mục mục tiêu của thuật toán HUFI [20] là giống nhau cho cả Phương án 1 và Phương án 2. Thuật toán ATMTU mà chúng tôi đề xuất sẽ có chiến lược chọn mục mục tiêu và giao tác mục tiêu là khác nhau cho mỗi phương án được chọn nhằm giảm thiểu hiệu ứng phụ:  Trường hợp ở Bước 1 chọn Phương án 1: Để giảm hữu ích của tập nhạy cảm Si ta cần giảm giá trị hữu ích nội của mục mục tiêu ivic tại giao tác mục tiêu Tvic một lượng ⌈ ⌉. - Nếu , chỉ cần một lần giảm giá trị hữu ích nội của mục tại giao tác một lượng k là ẩn được tập mục Si. Vì nên , hữu ích nội của mục tại giao tác Tvic được cập nhật lại là . Như vậy, Si được ẩn chỉ sau 1 lần sửa dữ liệu. Hữu ích của các tập mục chịu tác động chỉ bị giảm một lượng và độ hỗ trợ của các tập mục này giảm 1 lượng ⁄ trong trường hợp và không bị ảnh hưởng trong trường hợp . - Ngược lại, nếu , suy ra , tức là cần xóa mục ra khỏi giao tác và tập mục Si vẫn chưa được ẩn nên quá trình sửa dữ liệu vẫn phải tiếp tục thực hiện. Hữu ích của các tập mục chịu tác động bị giảm một lượng và độ hỗ trợ của các tập mục này cũng giảm 1 lượng ⁄ . Như vậy, cặp mục mục tiêu và giao tác mục tiêu cần được ưu tiên lựa chọn là cặp sao cho để sửa dữ liệu nhằm mục đích ẩn tập Si đồng thời giảm hiệu ứng phụ. Có thể tồn tại nhiều hơn một cặp thỏa mãn điều kiện , trong trường hợp này sẽ chọn cặp có lớn nhất, mục đích là tránh trường hợp và ưu tiên gọt tỉa mục có hữu ích lớn. Trong trường hợp không tồn tại cặp sao cho thì mục phải được xóa khỏi giao tác Tvic để giảm hữu ích của Si nhằm mục đích ẩn Si. Trong trường hợp này chúng tôi chọn phương án hạn chế số lần sửa dữ liệu, nghĩa là cần làm cho nhanh đạt điều kiện , vì vậy, cần chọn giao tác mà ở đó hữu ích của tại giao tác này đạt cực đại. Và mục mục tiêu được chọn là mục ít xuất hiện nhiều nhất trong các tập mục nhạy cảm SHUFIs được hỗ trợ bởi giao tác mục tiêu, mục đích của cách lựa chọn này là có thể ẩn được nhiều tập mục nhạy cảm đồng thời.
Huỳnh Triệu Vỹ, Lê Quốc Hải, Trương Ngọc Châu, Lê Quốc Hiếu 21  Trường hợp ở Bước 1 chọn Phương án 2: Để ẩn được tập dựa vào điều kiện giảm độ hỗ trợ, tức thực hiện lặp quá trình 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 chiến lược chọn giao tác mục tiêu là chọn giao tác sao cho là đạt cực tiểu nhằm mục đích giảm thiểu hữu ích của các tập mục không nhạy cảm bị ảnh hưởng. Và mục mục tiêu được lựa chọn tương tự như trường hợp chọn mục mục tiêu ở phương án 1 cho trường hợp , nhằm mục đích có thể ẩn được nhiều tập mục nhạy cảm đồng thời. 2. Thuật toán ATMTU input: D: CSDL gốc; SHUFIs: tập các tập mục hữu ích cao và phổ biến nhạy cảm; : ngưỡng hữu ích tối thiểu; δ: ngưỡng hỗ trợ tối thiểu. output: D’: CSDL sửa đổi. 1 2 3 ; 4 ; 5 6 lặp quá trình sửa dữ liệu 7 then // thực hiện theo Phương án 1 8 ; 9 10 ⌈ ⌉; 11 ; //kết thúc quá trình sửa dữ liệu vì đã được ẩn 12 13 ; 14 15 16 ; 17 ; 18 // thực hiện theo Phương án 2 19 ; 22 20 21 ; 22 ; 23 Cập nhật CSDL; B. Kết quả thực nghiệm 1. Mô tả CSDL Các cơ sở dữ liệu liệu chạy thực nghiệm chúng tôi sử dụng được công bố tại [25], chi tiết về các CSDL này được mô tả trong Bảng 5. Tập nhạy cảm được chọn ngẫu nhiên từ tập HUFIs được khai thác bởi thuật toán HI-FIMi[10], chi tiết được mô tả trong Bảng 6. 2. Mô tả hệ thống máy tính: CPU Core I5 2.4GHz, RAM 8GB, Windows 10. 3. So sánh và đánh giá kết quả thực nghiệm a) HF: Kết quả thực nghiệm cho thấy thuật toán ATMTU và HUFI đều có tỷ lệ HF là 0 %, lý do là hai thuật toán này đề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 và quá trình sửa dữ liệu không làm tăng giá trị hữu ích hoặc độ hỗ trợ của các tập mục nên không xảy ra hiện tượng tập mục nhạy cảm đã được ẩn và xuất hiện trở lại.
22 ẨN TẬP MỤC HỮU ÍCH CAO VÀ PHỔ BIẾN NHẠY CẢM Bảng 5. Mô tả tập CSDL thực nghiệm Bảng 6. Mô tả thông tin của các tập nhạy cảm CSDL #|D| #|I| #AvgLen #MaxLen Retail Mushroom Retail 88.162 16.470 10,3 76 Kích thước Kích thước Mushroom 8.124 119 23 23 SHUFIs SHUFIs Chú thích: #|D|: Tổng số giao tác; #|I|: Tổng số mục 15 5 trong CSDL; #AvgLen: Độ dài trung bình của giao tác 20 10 trong CSDL; #MaxLen: Độ dài cực đại của giao tác trong 0,04 0,3 12 4 CSDL. 25 15 30 20 b) MC: Hình 1 biểu diễn kết quả so sánh về MC giữa thuật toán ATMTU với thuật toán HUFI. Kết quả cho thấy thuật toán ATMTU có tỷ lệ MC thấp hơn thuật toán HUFI, lý do mang đến kết quả này là thuật toán ATMTU sử dụng các chiến lược heuristics khác nhau để chọn mục mục tiêu và giao tác mục tiêu cho từng phương án sửa dữ liệu để ẩn các tập mục SHUFIs. Hình 1. Tỷ lệ MC khi thực hiện ẩn các tập SHUFIs bởi thuật toán HUFI và ATMTU c) Thời gian thực thi: Thời gian để thực hiện ẩn các tập mục SHUFI của thuật toán ATMTU là nhanh hơn thuật toán HUFI, bởi vì thuật ATMTU thực hiện tiêu chí hạn chế số lần sửa dữ liệu khi chọn giao tác mục tiêu và mục mục tiêu đồng thời với mỗi tập mục nhạy cảm thực hiện tìm kiếm trên tập dữ liệu chỉ chứa các giao tác hỗ trợ tập mục nhạy cảm đang thực hiện ẩn, còn thuật toán HUFI mất nhiều thời gian để xây dựng các bản chỉ mục để hỗ trợ cho quá trình sửa dữ liệu và phương pháp chọn giao tác mục tiêu và mục mục tiêu của HUFI không xét đến tiêu chí hạn chế số lần sửa dữ liệu nên dẫn đến HUFI thực hiện nhiều lần sửa dữ liệu hơn ATMTU để ẩn được 1 tập mục nhạy cảm. Hình 2 là kết quả so sánh về thời gian thực thi của hai thuật toán khi thực hiện ẩn các tập các tập mục SHUFI. Hình 2. Thời gian thực hiện ẩn các tập SHUFIs bởi thuật toán HUFI và ATMTU d) DSS, DUS và IUS: Chiến lược chọn giao tác mục tiêu và mục mục tiêu luôn ảnh hưởng đến hiệu ứng phụ về MC và các hiệu ứng phụ về độ tương đồng của CSDL trước và sau sửa đổi. Thuật toán ATMTU có chiến lược chọn giao tác mục tiêu và mục mục tiêu khác nhau cho từng phương án thực hiện ẩn các tập mục SHUFI và đồng thời cũng xem xét đến tiêu chí hạn chế số lần sửa CSDL và các tập mục trong tập HUFIs bị ảnh hưởng. Kết quả về hiệu ứng phụ DSS, DUS và IUS của thuật toán ATMTU và HUFI được biểu diễn lần lượt trong Hình 3, 4 và 5 và cho thấy rằng thuật toán ATMTU là tốt hơn thuật toán HUFI.
Huỳnh Triệu Vỹ, Lê Quốc Hải, Trương Ngọc Châu, Lê Quốc Hiếu 23 Hình 3. Tỷ lệ DSS khi thực hiện ẩn các tập SHUFIs bởi thuật toán HUFI và ATMTU Hình 4. Tỷ lệ DUS khi thực hiện ẩn các tập SHUFIs bởi thuật toán HUFI và ATMTU Hình 5. Tỷ lệ IUS khi thực hiện ẩn các tập SHUFIs bởi thuật toán HUFI và ATMTU IV. KẾT LUẬN Ẩn tập mục hữu ích cao và phổ biến nhạy cảm là một chủ đề trong lĩnh vực bảo vệ tính riêng tư trong khai phá hữu ích cao đang được các nhà nghiên cứu quan tâm. Mục đích của chủ đề nghiên cứu này là đề xuất các thuật toán để sửa dữ liệu một cách tự động để tạo ra một bản CSDL sao chép với hiệu ứng phụ thấp, để công bố ra bên ngoài hoặc chia sẻ cho các đối tác, sao cho các thông tin được chủ sở hữu cho là thông tin nhạy cảm không thể bị khai thác bởi các thuật toán khai phá tập mục hữu ích cao và phổ biến. Trong bài báo này chúng tôi đã đề xuất thuật toán có tên gọi là ATMTU để ẩn tập mục SHUFI theo hướng tiếp cận heuristic để sửa dữ liệu gốc. Trong thuật toán này chúng tôi đã đề xuất 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á trị hữu ích hoặc giảm độ hỗ trợ của tập mục SHUFI để ẩn được tập mục nhạy cảm. Bằng cách áp dụng các heuristic khéo léo cho từng trường hợp giảm độ hỗ trợ hoặc giảm độ hữu ích của tập mục nhạy cảm dựa trên giá trị hữu ích của các mục thuộc tập mục nhạy cảm để lựa chọn cặp mục mục tiêu và tập mục mục tiêu, thuật toán ATMTU đã ẩn thành công tất cả các tập mục nhạy cảm trong khi cực tiểu hóa được các hiệu ứng phụ do quá trình ẩn tập mục gây ra. Kết quả thực nghiệm cũng cho thấy rằng thuật toán ATMTU tốt hơn thuật toán HUFI cả về các chỉ số hiệu ứng phụ và thời gian thực thi. 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”, in Proceedings of the 2004 SIAM International Conference on Data Mining, 2004: SIAM, pp. 482-486.
24 ẨN TẬP MỤC HỮU ÍCH CAO VÀ PHỔ BIẾN NHẠY CẢM [2] V. S. Tseng, C.-W. Wu, B.-E. Shie, and P. S. Yu, “UP-Growth: an efficient algorithm for high utility itemset mining”, in Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, 2010: ACM, pp. 253-262. [3] M. Liu and J. Qu, “Mining high utility itemsets without candidate generation”, in Proceedings of the 21st ACM international conference on Information and knowledge management, 2012: ACM, pp. 55-64. [4] P. Fournier-Viger, C.-W. Wu, S. Zida, and V. S. Tseng, “FHM: Faster high-utility itemset mining using estimated utility co-occurrence pruning”, in International symposium on methodologies for intelligent systems, 2014: Springer, pp. 83-92. [5] S. Zida, P. Fournier-Viger, J. C.-W. Lin, C.-W. Wu, and V. S. Tseng, “EFIM: a highly efficient algorithm for high-utility itemset mining”, in Mexican International Conference on Artificial Intelligence, 2015: Springer, pp. 530-546. [6] Q.-H. Duong, P. Fournier-Viger, H. Ramampiaro, K. N{\o}rv{\aa}g, and T.-L. Dam, “Efficient high utility itemset mining using buffered utility-lists”, Applied Intelligence, vol. 48, no. 7, p. 20, 2018. Springer. [7] J. C.-W. a. L. Lin, Ting, 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, 2016. Elsevier. [8] T.-L. Dam, K. Li, P. Fournier-Viger, and Q.-H. Duong, “CLS-Miner: efficient and effective closed high-utility itemset mining”, Frontiers of Computer Science, vol. 13, no. 2, p. 26, 2019. Springer. [9] V. a. D. Goyal, Siddharth and A. Sureka, “High utility rare itemset mining over transaction databases”, International Workshop on Databases in Networked Information Systems, p. 15, 2015. Springer. [10] R. U. Kiran, T. Y. Reddy, P. Fournier-Viger, M. Toyoda, P. K. Reddy, and M. Kitsuregawa, “Efficiently Finding High Utility-Frequent Itemsets Using Cutoff and Suffix Utility”, Pacific-Asia Conference on Knowledge Discovery and Data Mining, p. 14, 2019. Springer. [11] O. K. Alkan and P. Karagoz, “CRoM and HuspExt: Improving efficiency of high utility sequential pattern extraction”, IEEE Transactions on Knowledge and Data Engineering, vol. 27, no. 10, p. 14, 2015. IEEE. [12] R. Agrawal and R. Srikant, “Privacy-preserving data mining”, ACM Sigmod Record, vol. 29, no. 2, p. 13, 2000. ACM. [13] H. Quoc Le, S. Arch-Int, and N. Arch-Int, “Association rule hiding based on intersection lattice”, Mathematical Problems in Engineering, vol. 2013, 2013. Hindawi. [14] P. Cheng, I. Lee, J.-S. Pan, C.-W. Lin, and J. F. Roddick, “Hide association rules with fewer side effects”, IEICE TRANSACTIONS on Information and Systems, vol. 98, no. 10, p. 12, 2015. The Institute of Electronics, Information and Communication Engineers. [15] 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. [16] 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, 2014. [17] 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. [18] V. H. Trieu, C. T. Ngoc, H. Le Quoc, and L. N. Thanh, “HHUSI: An Efficient Algorithm for Hiding Sensitive High Utility Itemsets”, in International Conference on Industrial Networks and Intelligent Systems, Vietnam, 2018: Springer, pp. 145-154. [19] B. Le, D.-T. Dinh, V.-N. Huynh, Q.-M. Nguyen, and P. Fournier-Viger, “An efficient algorithm for hiding high utility sequential patterns”, International Journal of Approximate Reasoning, vol. 95, p. 17, 2018. Elsevier. [20] X. Liu, F. Xu, and X. Lv, “A novel approach for hiding sensitive utility and frequent itemsets”, Intelligent Data Analysis, vol. 22, p. 33, 2018. IOS Press. [21] W. Gan, J. Chun-Wei, H.-C. Chao, S.-L. Wang, and S. Y. Philip, “Privacy preserving utility mining: A survey”, 2018 IEEE International Conference on Big Data (Big Data), p. 11, 2018. IEEE. [22] J. C.-W. Lin, T.-P. Hong, P. Fournier-Viger, Q. Liu, J.-W. Wong, and J. Zhan, “Efficient hiding of confidential high-utility itemsets with minimal side effects”, Journal of Experimental & Theoretical Artificial Intelligence, vol. 29, no. 6, pp. 1225-1245, 2017. [23] R. Rajalaxmi and A. Natarajan, “Effective sanitization approaches to hide sensitive utility and frequent itemsets”, Intelligent Data Analysis, vol. 16, p. 20, 2012. IOS Press. [24] R. Agarwal and R. Srikant, “Fast algorithms for mining association rules”, in Proc. of the 20th VLDB Conference, 1994, pp. 487-499. [25] P. Fournier-Viger. “An Open-Source Data Mining Library.” http://www.philippe-fournier- viger.com/spmf/index.php?link=datasets.php (accessed 2019).
Huỳnh Triệu Vỹ, Lê Quốc Hải, Trương Ngọc Châu, Lê Quốc Hiếu 25 HIDING SENSITIVE HIGH UTILITY AND FREQUENT ITEMSET Huynh Trieu Vy, Le Quoc Hai, Truong Ngoc Chau, Le Quoc Hieu ABSTRACT: Privacy preserving in high utility mining (PPUM) is the process that modifies data item in the database in such a way that sensitive information which can be explored by high utility mining (HUI) algorithms cannot be discovered in the modified database. This process aims at avoiding the risk of disclosed sensitive information to competitor of database owner. However, modifying database usually affects to non-sensitive information such as lost or redundant high utility patterns which is known as the side effect. The target of PPUM algorithm is to hide sensitive information before sharing data outside the parties such that the side is minimal. In this paper, we propose a novel algorithm named ATMTU that hides sensitive high utility and frequent itemsets (SHUFIs) by three steps: (1) Specify which method between hiding SHUFIs by reducing utility of sensitive item and hiding SHUFIs by reducing frequency of sensitive item is more efficient; (2) Specify victim item and victim transaction in such a way that modifying victim item in the victim item results in minimal side effect; and (3) Modify victim item in victim transaction selected at the second step. The experimental result indicates that ATMTU algorithm achieves better performance compared to previous algorithm when hiding random SHUFIs discovered from Retail and Mushroom datasets.