Cải thiện thuật giải Cuckoo trong vấn đề ẩn luật kết hợp

TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT Tập 8, Số 2, 2018 45–58 
45 
CẢI THIỆN THUẬT GIẢI CUCKOO 
TRONG VẤN ĐỀ ẨN LUẬT KẾT HỢP 
Đoàn Minh Khuêa*, Lê Hoài Bắcb 
aKhoa Công nghệ Thông tin, Trường Đại học Đà Lạt, Lâm Đồng, Việt Nam 
bKhoa Công nghệ Thông tin, Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia TP. Hồ Chí Minh, 
TP. Hồ Chí Minh, Việt Nam 
*Tác giả liên hệ: Email: khuedm@dlu.edu.vn 
Lịch sử bài báo 
Nhận ngày 23 tháng 01 năm2018 
Chỉnh sửa ngày 24 tháng 04 năm 2018 | Chấp nhận đăng ngày 14 tháng 05 năm 2018 
Tóm tắt 
Hiện nay, vấn đề bảo mật dữ liệu ngày càng được quan tâm hơn trong quá trình khai thác 
dữ liệu. Làm sao để vừa có thể khai thác hợp pháp mà vừa tránh lộ ra các thông tin nhạy 
cảm. Có rất nhiều hướng tiếp cận nhưng nổi trội trong số đó là khai thác luật kết hợp đảm 
bảo sự riêng tư nhằm ẩn các luật nhạy cảm. Gần đây, có một thuật toán meta heuristic khá 
hiệu quả để đạt mục đích này, đó là thuật toán tối ưu hóa Cuckoo (COA4ARH). Trong bài 
báo này, một đề xuất cải tiến của COA4ARH được đưa ra để tính toán số lượng tối thiểu 
các item nhạy cảm cần được xóa để ẩn luật, từ đó hạn chế việc mất các luật không nhạy 
cảm. Các kết quả thực nghiệm tiến hành trên ba tập dữ liệu thực cho thấy trong một số 
trường hợp thì cải tiến đề xuất có kết quả khá tốt so với thuật toán ban đầu. 
Từ khóa: Ẩn luật nhạy cảm; Khai thác dữ liệu đảm bảo sự riêng tư; Tác dụng phụ; Thuật 
toán tối ưu hóa Cuckoo. 
Mã số định danh bài báo:  
Loại bài báo: Bài báo nghiên cứu gốc có bình duyệt 
Bản quyền © 2018 (Các) Tác giả. 
Cấp phép: Bài báo này được cấp phép theo CC BY-NC-ND 4.0 
TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG] 
46 
 IMPROVEMENT OF CUCKOO ALGORITHM FOR 
ASSOCIATION RULE HIDING PROBLEM 
Doan Minh Khuea*, Le Hoai Bacb 
aThe Faculty of Information Technology, Dalat University, Lamdong, Vietnam 
bThe Faculty of Information Technology, University of Science, VNU Hochiminh City, 
Hochiminh City, Vietnam 
*Corresponding author: Email: khuedm@dlu.edu.vn 
Article history 
Received: January 23rd, 2018 
Received in revised form: April 24th, 2018 | Accepted: May 14th, 2018 
Abstract 
Nowadays, the problem of data security in the process of data mining receives more 
attention. The question is how to balance between exploiting legal data and avoiding 
revealing sensitive information. There have been many approaches, and one remarkable 
approach is privacy preservation in association rule mining to hide sensitive rules. 
Recently, a meta-heuristic algorithm is relatively effective for this purpose, which is cuckoo 
optimization algorithm (COA4ARH). In this paper, an improved version of COA4ARH is 
presented for calculating the minimum number of sensitive items which should be removed 
to hide sensitive rules, as well as limit the loss of non-sensitive rules. The experimental 
results gained from three real datasets showed that the proposed method has better results 
compared to the original algorithm in several cases. 
Keywords: Cuckoo optimization algorithm; Privacy-preserving data mining; Sensitive 
association rule hiding; Side effect. 
Article identifier:  
Article type: (peer-reviewed) Full-length research article 
Copyright © 2018 The author(s). 
Licensing: This article is licensed under a CC BY-NC-ND 4.0 
Đoàn Minh Khuê và Lê Hoài Bắc 
47 
1. GIỚI THIỆU 
Trong hợp tác kinh doanh, việc chia sẻ dữ liệu giữa các tổ chức là rất phổ biến. 
Việc này có thể cung cấp các thông tin có giá trị, chẳng hạn như mô hình mua sắm của 
khách hàng tại các siêu thị hay phát hiện gian lận xảy ra trong ngành ngân hàng. Tuy 
nhiên, điều này dẫn đến một lo ngại là để lộ ra các thông tin nhạy cảm không mong 
muốn cho các bên thứ ba. Trong tình huống này rất cần thiết có một lĩnh vực nghiên cứu 
để vừa có thể khai thác dữ liệu vừa đảm bảo không làm lộ những tri thức nhạy cảm 
trong cơ sở dữ liệu ấy. Chính vì lý do này, lĩnh vực khai thác dữ liệu đảm bảo sự riêng 
tư đã ra đời và đang được phát triển trong những năm gần đây. 
Kể từ khi công trình tiên phong của Agrawal và Srikant (2000, tr. 439-450) và 
Lindell và Pinkas (2000), một vài phương pháp đã được đề xuất nhằm mục đích đảm 
bảo sự riêng tư trong khai thác dữ liệu. Bài báo này sẽ tập trung vào hướng nghiên cứu 
tiếp cận được biết nhiều là tập phổ biến và khai thác luật kết hợp đảm bảo sự riêng tư 
nhằm ẩn các luật kết hợp nhạy cảm. Luật kết hợp là các phép kéo theo được rút ra từ 
một cơ sở dữ liệu giao dịch theo các tham số được chỉ định bởi người dùng. Luật kết 
hợp sẽ cung cấp tri thức cô đọng nhất cho người khai thác dữ liệu vì chúng là bản tóm 
tắt dữ liệu, trong đó có chứa các mối quan hệ giữa các item trong dữ liệu. Thuật ngữ "ẩn 
luật kết hợp" đã được đề cập lần đầu tiên bởi Atallah, Bertino, Elmagarmid, Ibrahim, và 
Verykios (1999, tr. 45-52) trong một hội thảo về kỹ thuật tri thức và dữ liệu. Các tác giả 
của công trình này đã tìm cách sửa đổi cơ sở dữ liệu ban đầu theo một cách sao cho các 
luật kết hợp nhạy cảm sẽ được ẩn, nhưng điều này có thể gây ảnh hưởng đến tập dữ liệu 
gốc và các luật kết hợp không nhạy cảm. 
Có thể xem quá trình ẩn luật kết hợp nhạy cảm là quá trình biến đổi tập dữ liệu 
ban đầu, với các luật kết hợp nhạy cảm được chỉ định bởi người dùng, quá trình này 
thường được gọi là quá trình thanh trùng (sanitization) dữ liệu. Kết quả quá trình thanh 
trùng là sẽ tạo ra tập dữ liệu thanh trùng để cho dù bất kỳ thuật toán khai thác luật kết 
hợp nào được áp dụng trên tập dữ liệu này thì sẽ không có khả năng để phát hiện ra các 
luật nhạy cảm theo các thiết lập tham số chỉ định và sẽ có thể khai thác tất cả các luật 
không nhạy cảm đã xuất hiện trong các tập dữ liệu ban đầu (theo các thiết lập tham số 
tương tự hoặc cao hơn) và không có thêm các luật khác được tạo ra. 
Do đó, thách thức đặt ra là làm thế nào để cân bằng giữa nhu cầu ẩn luật nhạy 
cảm với việc khai thác thông tin hợp pháp của dữ liệu người dùng. Trong trường hợp lý 
tưởng là tất cả các luật nhạy cảm được ẩn, không có luật không nhạy cảm từ cơ sở dữ 
liệu gốc bị mất và không có luật ma được tạo ra. Tuy nhiên, thực tế chứng minh rằng rất 
khó để đạt được một mục tiêu lý tưởng như vậy mà không phát sinh bất kỳ tác dụng phụ 
nào. Bởi lẽ nó còn phụ thuộc các yếu tố như tập dữ liệu ban đầu đa dạng ra sao hay các 
luật nhạy cảm được định nghĩa bởi người dùng là đơn giản hay phức tạp. Để giải quyết 
vấn đề này, đã có rất nhiều kỹ thuật được đề xuất, chẳng hạn như sửa đổi dữ liệu 
(distortion) (Oliveira & Zaïane, 2004) là thêm mới hay xóa bỏ các item hiện có trong dữ 
liệu gốc, còn kỹ thuật ngăn chặn (blocking) (Chang & Moskowitz, 1998) thì thay thế 
TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG] 
48 
các item bằng ẩn số (unknowns). Cho đến thời điểm hiện tại thì các hoạt động để bảo vệ 
sự riêng tư trong khai thác luật kết hợp có thể được chia thành ba loại chính là: i) Tiếp 
cận heuristic; ii) Tiếp cận dựa vào biên; và iii) Tiếp cận chính xác. 
Trong những năm gần đây, các thuật toán meta heuristic đã được sử dụng để 
khai thác luật kết hợp nhằm đảm bảo sự riêng tư, chẳng hạn như thuật toán tối ưu hóa 
Cuckoo (Walton, Hassan, Morgan, & Brown, 2011) và ẩn luật kết hợp sử dụng thuật 
toán tối ưu hóa Cuckoo (Mahtab, Mohammad, & Mehdi, 2016). Tuy nhiên, các thuật 
toán này để bảo vệ thông tin nhạy cảm tránh bị tiết lộ thì chưa thật sự hoàn hảo và vẫn 
còn một số hiệu ứng phụ, đặc biệt là về việc mất luật còn rất cao. Chẳng hạn, trong công 
trình nghiên cứu và thực nghiệm “thuật toán tối ưu hóa Cuckoo” của Mahtab và ctg. 
(2016), chúng tôi nhận thấy rằng trong một vài trường hợp thì “thuật toán tối ưu hóa 
Cuckoo” không thể ẩn hoàn toàn các luật nhạy cảm. Đó là khi tập các luật kết hợp được 
định nghĩa bởi người dùng khá nhập nhằng. Do vậy, chúng tôi đề xuất một cải thiện để 
khắc phục nhược điểm này của thuật toán. Giải pháp của chúng tôi tập trung vào việc 
tính toán số lượng nhỏ nhất các item nhạy cảm để vừa đảm bảo ẩn hết các luật nhạy 
cảm, vừa hạn chế thao tác xóa lên dữ liệu ban đầu. Kết quả thực nghiệm với một số 
trường hợp đã cho thấy cải tiến của chúng tôi có thể ẩn hoàn toàn các luật nhạy cảm 
cùng một lúc. Để đạt được hiệu suất như vậy là do cải tiến dựa trên mối tương quan 
giữa các luật nhạy cảm mà tính toán ra item nhạy cảm. 
2. ĐỊNH NGHĨA BÀI TOÁN 
Giả sử rằng I = {i1, i2, i3, ..., im} là một tập của các item. D là một cơ sở dữ liệu 
bao gồm nhiều giao dịch. Mỗi giao dịch là một tập con của I. Tập các luật kết hợp được 
rút ra từ D là R và tập các luật kết hợp nhạy cảm là Rs, với Rs⊂R. Mỗi luật kết hợp được 
biểu diễn như A → B trong đó A là tiền đề hoặc phía bên trái và B là kết quả hoặc phía 
bên phải, để A, B ⊂I và A ∩ B = ∅. Mục đích là để thay đổi D thành D’, để các luật hiện 
hành trong Rs không thể được khai thác từ D’ trong khi các luật hiện hành trong R - Rs 
có thể được có thể khai thác. Hai tiêu chí được xem xét trong việc khai thác luật kết hợp 
bao gồm: 
 Tiêu chí đầu tiên được gọi là độ hỗ trợ item cho biết tần suất của một luật 
trong cơ sở dữ liệu và có thể được tính bằng công thức (1): 
Sup(A→B)=
|A∪B|
|D|
 (1) 
Trong đó Sup(A→B) là độ hỗ trợ của luật kết hợp A→B, |A∪B| là số giao dịch 
chứa tất cả các items trong cả hai tập A và B. D là tổng số giao dịch. 
 Tiêu chí thứ hai là độ tin cậy luật cho biết độ mạnh luật trong cơ sở dữ liệu 
và có thể được tính bằng công thức (2): 
Đoàn Minh Khuê và Lê Hoài Bắc 
49 
Conf(A→B)=
|A∪B|
|A|
 (2) 
Đối với mỗi luật kết hợp, một ngưỡng hỗ trợ nhỏ nhất (Minimum Support 
Threshold - MST) và một ngưỡng tin cậy nhỏ nhất (Minimum Confidence Threshold - 
MCT) được xác định. Một luật thỏa mãn khi độ hỗ trợ của nó là cao hơn MST và độ tin 
cậy của nó cao hơn MCT. 
Khai thác luật kết hợp thường bao gồm hai giai đoạn: Giai đoạn 1 là tập các 
itemset phổ biến được khai thác với một ngưỡng MST đã cho và Giai đoạn 2 là luật kết 
hợp mạnh được sinh ra từ các tập phổ biến thu được trong Giai đoạn 1 và phụ thuộc một 
ngưỡng MCT đã cho. Các luật được đề cập đến sau này đều là các luật mạnh. Có ba tác 
dụng phụ có thể có sau khi chuyển từ D thành D': Tập con của các luật nhạy cảm không 
được ẩn trong D' gọi là HF (Hiding Failure), HF = {r ∈ RS|r ∈ R’}. Bất kỳ các luật 
không nhạy cảm nào bị ẩn sai và bị mất trong D', gọi là LR (Lost Rules), LR= {r ∈ (R- 
RS) |r ∉ R’}. Các luật giả tạo sinh ra trong D' được chứa vào GR (Ghost Rules), GR = {r 
∈ R’|r ∉ R}. 
Giả định: Một luật được coi là được ẩn nếu độ hỗ trợ của nó là nhỏ hơn so với 
MST hoặc độ tin cậy của nó là nhỏ hơn MCT. Nói cách khác, nếu một luật mạnh trong D 
không còn là mạnh trong D', chúng ta xem nó là được ẩn. Nhiệm vụ của phương pháp 
ẩn luật là bằng cách nào đó để chuyển từ D sang D’ mà tất cả luật nhạy cảm RS trở nên 
ẩn trong D' trong khi tránh được các dụng phụ (nghĩa là giảm thiểu các thành viên có 
trong HF, LR, và GR). 
Do đó, để che giấu một luật thì đòi hỏi phải giảm độ hỗ trợ hoặc sự tự tin của nó 
đến một mức dưới ngưỡng. Quá trình ẩn thường có thể ảnh hưởng đến các luật không 
nhạy cảm trong D hoặc các luật tiền mạnh trong D. Các luật tiền mạnh là những luật với 
độ hỗ trợ không nhỏ hơn MST và độ tin cậy nhỏ hơn MCT. Một luật tiền mạnh có thể 
trở nên mạnh khi độ tin cậy của nó trên MCT. Một luật không nhạy cảm trong D có thể 
chấm dứt mạnh khi độ hỗ trợ của nó giảm xuống dưới MST hay độ tin cậy của nó giảm 
xuống dưới MCT trong D' do việc loại bỏ item. 
3. ĐỀ XUẤT CẢI THIỆN THUẬT TOÁN 
3.1. Giới thiệu thuật toán 
Phương pháp đề xuất của chúng tôi là một phiên bản cải tiến của COA4ARH 
(Mahtab & ctg., 2016). Vì vậy, hầu hết các bước của đề xuất là tương đồng với thuật 
toán ban đầu, chỉ có khác ở bước xác định các item nhạy cảm trong giai đoạn tiền xử lý. 
Các bước chính của thuật toán COA4ARH được trình bày trong Hình 1. 
TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG] 
50 
Hình 1. Thuật toán COA4ARH 
3.2. Sửa đổi hoạt động tiền xử lý tập dữ liệu ban đầu 
Như trình bày ở trên thì một luật kết hợp nhạy cảm được ẩn khi độ hỗ trợ hay độ 
tin cậy của nó nằm dưới ngưỡng. Để giảm độ tin cậy của một luật X→Y, ta có thể tăng 
độ hỗ trợ của X, là các item bên trái luật, hay giảm độ hỗ trợ của itemset X∪Y. Trường 
hợp thứ hai, nếu ta chỉ giảm độ hỗ trợ của Y, là các item bên phải luật, thì nó sẽ giảm độ 
tin cậy nhanh hơn khi chỉ giảm độ hỗ trợ của X∪Y. Để giảm độ hỗ trợ của một itemset, 
ta sẽ sửa đổi một item bằng cách xóa item này trong các giao dịch hỗ trợ. Dựa vào 
những nhận định này, bài báo gốc của Mahtab và ctg. (2016) đã đưa ra cách xác định 
các item nhạy cảm của riêng nó trong hoạt động tiền xử lý như sau: 
 Nếu một luật nhạy cảm chỉ có duy nhất một item ở bên phải, item độc nhất 
này sẽ được chọn làm item nhạy cảm. 
Input: 
Tập dữ liệu gốc D, Rs, MST và MCT; 
α, Npop, Nmax, MinNNS, MaxNNS, MaxIteration; 
Output: 
Một tập dữ liệu đã làm sạch D’; 
begin 
Tiền xử lý mới cho tập dữ liệu gốc: 
Khởi tạo 1 quần thể ban đầu; 
call FitnessFunction; 
 call BestSolutionFunction; 
repeat 
 // Tạo ra giải pháp mới 
for each solution in population 
K = (Max NNS - Min NNS) × Rand [0, 1] + Min NNS; // Xác định K 
MR = [∝ ×
Current solution's K
Total of all solution's K
] × (Varhi - Varlow); //Xác định MR 
for K times do 
 for MR times do 
Chọn ngẫu nhiên một item trong số các item nhạy cảm; 
 Đặt Rand [0,1] cho item đã chọn; 
end for 
 end for 
end for 
call FitnessFunction; 
 call BestSolutionFunction; 
Limit number of solutions to Nmax; 
for each solution in population 
call ImmigrationFunction; // Di chuyển tất cả các giải pháp hiện tại đến giải pháp tốt nhất 
end for 
call FitnessFunction; 
 call BestSolutionFunction; 
until Điều kiện dừng được thỏa mãn; 
end. 
Đoàn Minh Khuê và Lê Hoài Bắc 
51 
 Nếu một luật nhạy cảm có nhiều hơn một item ở bên phải, một item trong số 
chúng sẽ được chọn làm item nhạy cảm mà item này có tần suất xuất hiện 
nhiều nhất ở phía bên phải của các luật nhạy cảm và có tần suất ít nhất của 
các luật không nhạy cảm. 
Dễ nhận thấy rằng, trong trường hợp một luật nhạy cảm có nhiều item ở bên 
phải, một item có thể có tần suất xuất hiện nhiều nhất ở phía bên phải của các luật nhạy 
cảm và có thể có tần suất nhiều nhất ở phía bên phải của các luật không nhạy cảm so với 
các item còn lại trong luật nhạy cảm này. Điều này dẫn đến vấn đề là không có item 
nhạy cảm cho luật nhạy cảm, hay luật này không được ẩn (HF ≠ 0). Như vậy, trong tình 
huống này, thuật toán ban đầu đã bị thất bại trong mục tiêu hàng đầu của mình là ẩn hết 
hoàn toàn và cùng một lúc các luật nhạy cảm. Do vậy, cần có một phương pháp để khắc 
phục nhược điểm này của “thuật toán tối ưu hóa Cuckoo”. Chúng tôi đề xuất phương 
pháp xác định các item nhạy cảm bằng “lược đồ nhạy cảm”, được mô tả chi tiết trong 
phần dưới đây. 
3.2.1. Các định nghĩa cho đề xuất 
Dựa vào mối tương quan giữa các luật nhạy cảm mà chọn ra item nhạy cảm 
nhưng cũng phải đảm bảo gây ảnh hưởng đến cơ sở dữ liệu ở mức thấp nhất có thể 
được. Chúng tôi đưa ra định nghĩa một “lược đồ nhạy cảm” để đại diện cho một item 
nhạy cảm. Một lược đồ cho biết độ phủ các luật nhạy cảm và các ảnh hưởng lên cơ sở 
dữ liệu ban đầu của item mà nó đại diện. Một thời điểm chỉ chọn ra được một lược đồ 
có lợi nhất. “Lược đồ nhạy cảm” tốt nhất (có lợi) là lược đồ có độ phủ thông tin về số 
lượng các luật nhạy cảm nhiều nhất, đồng thời có tác động thấp nhất đến cơ sở dữ liệu 
các giao dịch. 
 Định nghĩa 1: “Lược đồ nhạy cảm” của một item nhạy cảm được định nghĩa 
như sau: 
L = (3) 
Trong đó: SI là item nhạy cảm mà lược đồ đại diện; CV là độ phủ luật của lược 
đồ; và AM (Affect Measure) là độ đo mức độ ảnh hưởng của một lược đồ đến các giao 
dịch. 
 Định nghĩa 2: (Giao dịch của lược đồ): Một giao dịch t được xem là chứa 
trong một lược đồ L nếu thỏa mãn hai điều kiện sau: i) NIL ⊆ t và ii) SIL ∈ 
t. Với tập tất cả các giao dịch được chứa trong L là TL. ∀ t ∈ TL. 
 Định nghĩa 3: (Độ bao phủ luật nhạy cảm r của một lược đồ L): Giả sử tập 
tất cả các luật nhạy cảm được phủ bởi L là SRL. Một luật nhạy cảm r: X → Y 
được xem là phủ bởi một lược đồ L nếu SIL ∈ Y. ∀ r ∈ SRL. Độ phủ (CV) 
của một L được định nghĩa là số lượng các luật trong SRL. Độ phủ CV được 
TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG] 
52 
tính theo công thức (4). 
CV = |SRL| (4) 
 Định nghĩa 4: (Minimal Count - MC của một luật nhạy cảm): Cho một lược 
đồ L và một luật r: X → Y. Để đặc trưng cho tác động ẩn của một luật nhạy 
cảm r chứa trong một lược đồ L gây ra ảnh hưởng lên cơ sở dữ liệu các giao 
dịch TL. Để ảnh hưởng này là nhỏ nhất ta đưa ra định nghĩa MCr. MCr chính 
là số lượng nhỏ nhất các giao dịch bị ảnh hưởng khi ta ẩn các luật r trong 
SRL và MC của luật r được tính như công thức (5). 
MCr, L = min {MSCr, MCCCr} (5) 
Trong đó: MSC là số lượng tối thiểu các giao dịch mà cần phải được sửa đổi để 
giảm độ hỗ trợ của luật r; MCCC là số lượng tối thiểu các giao dịch mà cần phải được 
sửa đổi để giảm độ tin cậy của luật r. Công thức tính MSC và MCCC đã được Wu, 
Chiang, và Arbee (2007) trình bày chi tiết tại hội nghị IEEE về tri thức và dữ liệu. 
 Định nghĩa 5: (Độ đo ảnh hưởng - AM): Cho một lược đồ L, tập các luật 
nhạy cảm SRL và các giao dịch TL. Xét luật r: X → Y, ∀ r ∈ SRL. Luật r có 
một giá trị MCr, L. Mức độ ảnh hưởng của một lược đồ L đến các giao dịch 
TL được định nghĩa là số lượng ảnh hưởng MC lớn nhất của luật r được phủ 
trong L lên các giao dịch TL để đảm bảo ẩn tất cả các luật trong SRL. 
AML = max {MCri, L} (6) 
Trong đó: ri ∈ SRL và được phủ trong L. 
 Định nghĩa 6: (Rút gọn lược đồ): Một lược đồ L1 có thể rút gọn được nếu 
tồn tại lược đồ L2 sao cho SIL1 = SIL2. 
3.2.2. Chiến lược tìm kiếm các item nhạy cảm dựa vào “lược đồ nhạy cảm” 
Chiến lược này có thể theo các bước như sau: 
 Bước 1: Duyệt các luật nhạy cảm ban đầu, tính toán giá trị MSC và MCCC 
cho từng luật nhạy cảm; 
 Bước 2: Xây dựng bảng “lược đồ nhạy cảm”: Duyệt tất cả các luật nhạy 
cảm; Tạo các lược đồ tương ứng với mỗi item bên phải trong luật; Rút gọn 
các lược đồ dư thừa; 
 Bước 3: Chọn ra một lược đồ tốt nhất trong số các lược đồ còn lại ở Bước 2. 
Mục tiêu là để xác định ra item nhạy cảm: Nếu lược đồ có CV lớn nhất được 
chọn làm item nhạy cảm; Nếu nhiều lược đồ có cùng giá trị CV thì lược đồ 
Đoàn Minh Khuê và Lê Hoài Bắc 
53 
có AM nhỏ nhất được chọn làm item nhạy cảm; Nếu nhiều lược đồ có cùng 
giá trị AM nhỏ nhất thì chọn ngẫu nhiên một lược đồ làm item nhạy cảm; 
Bộ các luật nhạy cảm hiện hành = bộ các luật nhạy cảm ban đầu - CV của 
lược đồ tốt nhất; 
 Bước 4: Xuất ra danh sách các item nhạy cảm. 
Nếu mô hình tốt nhất tìm được ở Bước 3 có CV bằng số lượng các luật nhạy cảm 
ban đầu thì dừng, ngược lại, lặp lại Bước 2, Bước 3, Bước 4 để tìm các item nhạy cảm 
khác. 
4. VÍ DỤ MINH HỌA 
Cho một cơ sở dữ liệu gốc bao gồm 10 giao dịch (được thể hiện trong Bảng 1). 
Với MST = 10% và MCT = 70%. Giả sử tập các luật nhạy cảm cần được ẩn được trình 
bày trong Bảng 2. 
Bảng 1. Tập dữ liệu ban đầu 
 TID Items TID Items 
T1 a, b, c, e, f T6 b, c, e 
T2 e T7 a, b, c, d, e, f 
T3 b, c, e, f T8 a, b 
T4 d, f T9 c, e, f 
T5 a, b, d, f T10 a, b, c, e 
Bảng 2. Các luật nhạy cảm 
 ID SAR 
1 c, d f, a 
2 a, e, d c, f 
3 e b 
Đề xuất của chúng tôi được tiến hành như sau: 
 Bước 1: Tính toán MSC và MCCC cho từng luật nhạy cảm (Bảng 3); 
Bảng 3. MSC và MCCC cho từng luật nhạy cảm 
 ID SAR MSC MCCC 
1 c, d f, a 1 1.3 
2 a, e, d c, f 1 1.3 
3 e b 5 1.1 
TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG] 
54 
 Bước 2: Xây dựng bảng các “lược đồ nhạy cảm” (Bảng 4): Bộ các luật 
nhạy cảm bao gồm {c, d f, a; a, e, d c, f; e b}; Sau đó ta rút gọn 
các lược đồ dư thừa. Kết quả thể hiện trong Bảng 5; 
Bảng 4. Các lược đồ nhạy cảm 
 ID SI CV AM 
1 f 2 Max (1, 1) = 1.0 
2 a 1 Max (1) = 1.0 
3 c 1 Max (1) = 1.0 
4 f 2 Max (1, 1) = 1.0 
5 b 1 Max (1.1) = 1.1 
Bảng 5. Lược đồ nhạy cảm sau khi tinh chỉnh 
 ID SI CV AM 
1 f 2 Max (1, 1) = 1.0 
2 a 1 Max (1) = 1.0 
3 c 1 Max (1) = 1.0 
4 b 1 Max (1.1) = 1.1 
 Bước 3: Xác định lược đồ có CV lớn nhất là lược đồ tốt nhất: Bảng 5 cho 
thấy Lược đồ 1 có CV = 2 là lớn nhất, như vậy Lược đồ 1 là tốt nhất; 
 Bước 4: Tập hợp các item nhạy cảm S = {1} = {f}: Do Lược đồ 1 có CV = 2 
bé hơn số lượng các luật nhạy cảm ban đầu nên bộ các luật nhạy cảm hiện 
hành là {e b} có số lượng = số lượng các luật nhạy cảm ban đầu trừ đi 
CV của Lược đồ 1 (3 - 2 = 1). Lặp lại Bước 2 với bộ các luật nhạy cảm hiện 
hành là {e b} có số lượng là 1 (Bảng 6); 
Bảng 6. Các lược đồ nhạy cảm 
 ID SI CV AM 
1 b 1 Max (1.1) = 1.1 
 Bước 5: Bảng 6 cho thấy chỉ còn một lược đồ và lược đồ này là lược đồ tốt 
nhất; 
 Bước 6: Tập hợp các item nhạy cảm S = {f, b}. 
Thuật toán dừng khi bộ các luật nhạy cảm hiện hành là rỗng ({∅}). Từ đó ta có 
kết luận là tập hợp các item nhạy cảm S = {f, b}. Trong khi đó với thuật toán ban đầu 
Đoàn Minh Khuê và Lê Hoài Bắc 
55 
chỉ xác định được b là item nhạy cảm. Điều này không đảm bảo ẩn hết ba luật nhạy cảm 
đã chỉ định trước đó. 
5. ĐÁNH GIÁ HIỆU SUẤT 
5.1. Tập dữ liệu 
Các tập dữ liệu được sử dụng để làm thực nghiệm bao gồm các tập dữ liệu thực 
lấy từ UCI (2018): Mushroom; Chess; và Cylinder Bands. Đặc điểm của các bộ dữ liệu 
cụ thể được trình bày trong Bảng 7. 
Bảng 7. Đặc tính của các tập dữ liệu 
Cơ sở dữ liệu Số lượng giao dịch Chiều dài trung bình giao dịch Số lượng item 
Mushroom 8124 23 119 
Chess 3196 37 75 
Cylinder Bands 512 39 1756 
5.2. Các độ đo hiệu suất 
Các tiêu chí quan trọng sẽ được sử dụng để so sánh đề xuất cải tiến so với thuật 
toán ban đầu COA4ARH bao gồm: 
 Hiding Failure (HF): Cho biết số lượng các luật nhạy cảm mà thuật toán 
làm sạch không thể ẩn và vẫn đang được khai thác từ cơ sở dữ liệu đã làm 
sạch D'. Công thức tính toán như sau: 
HF= 
|Rs(D
')|
|Rs(D)|
 (7) 
Trong đó: Rs(D
') là số lượng luật nhạy cảm tìm thấy trong cơ sở dữ liệu làm 
sạch; D' và Rs(D) là số lượng luật nhạy cảm trong cơ sở dữ liệu gốc ban đầu D. 
 Lost Rules (LR): Cho biết số lượng các luật không nhạy cảm bị mất do hoạt 
động thanh trùng sanitization và sẽ không còn được khai thác từ tập dữ liệu 
đã thanh trùng D'. Công thức tính toán là: 
LR=
|~Rs(D)|−|~Rs(D
')|
|~Rs(D)|
 (8) 
Trong đó: |~Rs(D)| là số lượng các luật không nhạy cảm trong tập dữ liệu ban 
đầu D; |~Rs(D
')| là số lượng các luật không nhạy cảm trong tập dữ liệu đã làm sạch D'. 
 Ghost Rules (GR): Cho biết số lượng các luật giả không có trong cơ sở dữ 
TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG] 
56 
liệu gốc ban đầu D và được tạo ra do hoạt động làm sạch sanitization và 
được khai thác từ cơ sở dữ liệu D’. Công thức tính toán: 
GR= 
|R'| -|R∩R'|
|R'|
 (9) 
Trong đó: |R'| là số lượng các luật khai thác từ D'; |R| là số lượng các luật khai 
thác từ D. 
 Số vòng lặp: Số lần lặp yêu cầu để đạt được giải pháp tối ưu. 
5.3. Các kết quả thực nghiệm 
Các thí nghiệm ở cả hai thuật toán đều được tiến hành trên cùng một nền tảng là 
ngôn ngữ Java, thực hiện trên một máy tính PC với cấu hình @Intel CPU core i7 2.50 
GHz và RAM 16GB, Windows 10 (64-bit). Qua một số kiểm thử cụ thể, chúng tôi thu 
được các kết quả như trong Hình 2, Hình 3, và Hình 4. 
Hình 2. So sánh HF trên tập dữ liệu Mushroom 
Hình 3. So sánh HF trên tập dữ liệu Chess 
Đoàn Minh Khuê và Lê Hoài Bắc 
57 
Hình 4. So sánh HF trên tập dữ liệu Cylinder Bands 
Các hình trên cho thấy trong cả ba tập cơ sở dữ liệu, giá trị HF trong phương 
pháp cải tiến đều bằng 0, trong khi thuật toán ban đầu thì HF khác 0. Điều này nói lên 
rằng trong một số trường hợp thì thuật toán ban đầu không thể ẩn hết các luật nhạy cảm, 
còn phương pháp của chúng tôi thì khắc phục được nhược điểm này một cách triệt để. 
Có được hiệu quả này là do đề xuất cải tiến của chúng tôi tìm thấy được mối tương quan 
giữa luật nhạy cảm và các giao dịch hỗ trợ của nó, từ đó đưa ra phương pháp tính toán 
số lượng nhỏ nhất các item nhạy cảm để vừa đảm bảo ẩn hết các luật nhạy cảm và vừa 
gây ảnh hưởng thấp nhất lên các giao dịch hỗ trợ. 
6. KẾT LUẬN 
Bảo đảm sự riêng tư trong khai thác luật kết hợp là một chủ đề nghiên cứu quan 
trọng trong lĩnh vực bảo mật cơ sở dữ liệu. Bài báo này đã đề xuất một phương pháp cải 
tiến khá hiệu quả để giải quyết vấn đề ẩn hoàn toàn các luật kết hợp nhạy cảm bị nhập 
nhằng mà trước đó thuật toán gốc không xử lý được. Đề xuất cải tiến đã đề ra phương 
pháp tính toán chính xác số lượng các item nhạy cảm đảm bảo phủ hết các luật nhạy 
cảm nhưng cũng ít gây ảnh hưởng nhất đến các giao dịch dữ liệu. Các kết quả thực 
nghiệm trên các tập dữ liệu thực đã chứng tỏ hiệu quả của phương pháp cải tiến để ẩn 
hết các luật nhạy cảm. Trong tương lai, chúng tôi sẽ cố gắng tìm ra một cơ chế thích 
nghi cho các tham số đầu vào của thuật toán. Ngoài ra, tìm hiểu thêm về các cách tiếp 
cận khác (biên, chính xác) để từ đó cải tiến thuật toán tốt hơn trong trường hợp mất các 
luật không nhạy cảm cũng như đẩy nhanh tốc độ xử lý của thuật toán nhằm đạt được 
giải pháp tối ưu nhanh hơn. 
TÀI LIỆU THAM KHẢO 
Agrawal, R., & Srikant, R. (2000). Privacy-preserving data mining. SIGMOD Record, 
29(2), 439-450. 
Atallah, M., Bertino, E., Elmagarmid, A., Ibrahim, M., & Verykios, V. (1999). 
Disclosure limitation of sensitive rules. Paper presented at The IEEE Knowledge 
and Data Engineering Exchange Workshop (KDEX), USA. 
TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG] 
58 
Chang, L., & Moskowitz, I. (1998). Parsimonious downgrading and decision trees 
applied to the inference problem. Paper presented at The Workshop on New 
Security Paradigms (NSPW), USA. 
Lindell, Y., & Pinkas, B. (2000). Privacy-preserving data mining. Journal of 
Cryptology, 15(3), 36-54. 
Mahtab, H. A., Mohammad, N. D., & Mehdi, A. (2016). Association rule hiding using 
Cuckoo optimization algorithm. Expert Systems with Applications, 64, 340-351. 
Oliveira, S., & Zaïane, O. (2004). Achieving privacy preservation when sharing data for 
clustering. Paper presented at The International Conference on Data Mining 
(SDM), Canada. 
UCI. (2018). Machine learning repository. Retrieved from https://archive.ics.uci.edu/ 
ml/index.php 
Walton, S., Hassan, O., Morgan, K., & Brown, M. (2011). Modified Cuckoo search: A 
new gradient-free optimisation algorithm. Chaos, Solitons & Fractals, 44, 710-
718. 
Wu, Y. H., Chiang, C. M., & Arbee, L. P. C. (2007). Hiding sensitive association rules 
with limited side effects. IEEE Transactions on Knowledge and Data 
Engineering, 19(1), 29-42.