Ẩ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
1Trường Đại học Phạm Văn Đồng
2Trường Cao đẳng Sư phạm Quảng Trị
3Trường Đại học Bách khoa Đà Nẵng
4Trường Đại học Kinh tế Luật - Đại học Quốc gia TP. HCM
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ự
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.
{
}
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
Phát biểu: Cho
{
}
{
}
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 2. Giá trị hữu ích ngoại của CSDL D
Bảng 1. CSDL Giao tác D
Transaction Tid Transaction
A B C D E F G
H
2
Item
Tid
T1 A(4), C(1), E(6), F(2)
T6 B(1), F(2), H(1)
T7 D(1), E(1), F(4), G(1), H(1)
T8 B(1), D(1), E(1)
T9 B (5), D(4), G(10)
T10 F(1)
3
4 5 2 1 1 1
Utility
T2 D(1), E(4), F(5)
T3 B(3), D(1), E(5), F(1)
T4 D(1), E(2), F(6)
T5 A(3), C(1), E(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
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
AE
ACE
ACEF
31
28
38
25
B
40
48
30
26
BDG
DEF
EF
38
36
36
BD
BG
BDE
Đị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
AE
ACE
31
28
38
0,2
0,2
0,2
B
BD
BDE
40
48
26
0,4
0,3
0,2
DEF
EF
36
36
0,3
0,5
Đị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
và đã chứng minh được rằng lự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
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
- 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
7
8
;
;
lặp quá trình sửa dữ liệu
then // thực hiện theo Phương án 1
;
⌉;
9
⌈
10
11
12
13
14
15
16
17
; //kết thúc quá trình sửa dữ liệu vì đã được ẩn
;
;
;
18
19
22
20
21
22
// thực hiện theo Phương án 2
;
;
;
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 6. Mô tả thông tin của các tập nhạy cảm
Bảng 5. Mô tả tập CSDL thực nghiệm
#|D| #|I| #AvgLen #MaxLen
88.162 16.470
8.124 119
CSDL
Retail
Mushroom
Retail
Mushroom
Kích thước
10,3
23
76
23
Kích thước
SHUFIs
SHUFIs
15
5
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.
20
10
15
20
0,04 0,3
12
4
25
30
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]
[4]
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.
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]
[7]
[8]
[9]
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.
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.
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.
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.”
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.
10 trang
18400
Free
Bạn đang xem tài liệu "Ẩn tập mục hữu ích cao và phổ biến nhạy cảm", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- an_tap_muc_huu_ich_cao_va_pho_bien_nhay_cam.pdf
