ĐẠI HỌC QUỐC GIA TP. HCM
TRƯỜNG ĐẠI HỌC BÁCH KHOA

------------------------

NGUYỄN PHÚC PHI HỔ

ẨN DANH HĨA DỮ LIỆU
BẰNG THUẬT TỐN DI CHUYỂN TUPLE
Chuyên ngành : Khoa học máy tính
Mã số

: 8480101

LUẬN VĂN THẠC SĨ

TP. HỒ CHÍ MINH, THÁNG 7 NĂM 2023


CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI
TRƯỜNG ĐẠI HỌC BÁCH KHOA – ĐHQG-HCM
Cán bộ hướng dẫn khoa học : TS. Phan Trọng Nhân, TS. Trương Tuấn Anh
Cán bộ chấm nhận xét 1 : PGS.TS. Nguyễn Tuấn Đăng
Cán bộ chấm nhận xét 2 : TS. Nguyễn Quang Hùng
Luận văn thạc sĩ được bảo vệ tại Trường Đại học Bách Khoa, ĐHQG TP. HCM
ngày 12 tháng 7 năm 2023.
Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm:
1. Chủ tịch: PGS.TS Trần Minh Quang
2. Thư ký: TS. Nguyễn Thị Ái Thảo
3. Phản biện 1: PGS.TS. Nguyễn Tuấn Đăng
4. Phản biện 2: TS. Nguyễn Quang Hùng

5. Ủy viên:TS. Đặng Trần Trí
Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trưởng Khoa quản lý chuyên
ngành sau khi luận văn đã được sửa chữa (nếu có).
CHỦ TỊCH HỘI ĐỒNG

TRƯỞNG KHOA
KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH


ĐẠI HỌC QUỐC GIA TP.HCM

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM

TRƯỜNG ĐẠI HỌC BÁCH KHOA

Độc lập - Tự do - Hạnh phúc

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ tên học viên: NGUYỄN PHÚC PHI HỔ................................ MSHV: 2070099
Ngày, tháng, năm sinh: 04/11/1998 ........................................... Nơi sinh: Phú Yên
Chuyên ngành: Khoa học máy tính ......................................... Mã số: 8480101
I. TÊN ĐỀ TÀI: Ẩn danh hóa dữ liệu bằng thuật tốn di chuyển tuple.
Tên đề tài tiếng Anh: Data anonymization through tuple migration approach.
II. NHIỆM VỤ VÀ NỘI DUNG:
• Tìm hiểu về ẩn danh hóa dữ liệu và phân loại các tiêu chí khi thực hiện ẩn danh.
• Tìm hiểu những giải thuật đã được đề xuất để xử lý ẩn danh dữ liệu.
• Phân tích những đặc trưng riêng trong giải thuật di chuyển tuple với các giải thuật
khác. Từ đó cải tiến những giải thuật đã tìm hiểu , đưa ra giải thuật mới.
• Đánh giá giải thuật mới được đề xuất trong luận văn.
III. NGÀY GIAO NHIỆM VỤ: 06/02/2023

IV. NGÀY HOÀN THÀNH NHIỆM VỤ: 12/07/2023
V. CÁN BỘ HƯỚNG DẪN : TS. Phan Trọng Nhân , TS. Trương Tuấn Anh
TP. HCM, ngày tháng 7 năm 2023
CÁN BỘ HƯỚNG DẪN

TS. Phan Trọng Nhân

HỘI ĐỒNG NGÀNH

TS. Trương Tuấn Anh

TRƯỞNG KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH


GVHD: TS TRƯƠNG TUẤN ANH

LỜI CẢM ƠN
Lời nói đầu, em xin được gửi lời cảm ơn chân thành và sâu sắc đến các thầy giảng
viên hướng dẫn TS. Trương Tuấn Anh và TS. Phan Trọng Nhân đã hỗ trợ và có
những đóng góp hết sức quý báu để giúp em hoàn thành luận văn thạc sĩ này một
cách tốt nhất. Trong suốt quá trình nghiên cứu đề tài, hai thầy luôn là người định
hướng và đề xuất những kiến thức mới về mặt khoa học cho đề tài.
Bên cạnh đó, em cũng muốn thay mặt cho toàn thể sinh viên gửi lời biết ơn đến với
quý thầy cô của trường Đại học Bách Khoa TPHCM nói chung và của Khoa Khoa
học và Kỹ thuật máy tính nói riêng vì đã tận tình chỉ bảo và truyền tải kiến thức thức
vơ giá cho sinh viên trong khoảng thời gian học tập tại trường cũng như trong con
đường sự nghiệp sau này.
Cuối cùng em xin gửi lời cảm ơn đến gia đình, bạn bè, những người đã luôn bên
cạnh, động viên và khuyến khích trong q trình thực hiện đề tài nghiên cứu của
mình.

Xin chân thành cảm ơn.
Trân trọng.

TP. Hồ Chí Minh, ngày tháng năm 2023

Tác giả

i
HVTH: NGUYỄN PHÚC PHI HỔ


GVHD: TS TRƯƠNG TUẤN ANH

TÓM TẮT LUẬN VĂN
Với mức độ phổ biến ngày càng tăng của việc thu thập và phân tích dữ liệu,
ngày càng có nhiều lo ngại về rủi ro quyền riêng tư do dữ liệu cá nhân gây ra. Vi
phạm dữ liệu, đánh cắp danh tính và các hình thức tội phạm mạng khác chỉ là một
số rủi ro liên quan đến việc lạm dụng dữ liệu cá nhân.Một yếu tố quan trọng cần
phải xem xét là sự đánh đổi giữa chất lượng dữ liệu và quyền riêng tư khi quyết định
phương pháp ẩn danh dữ liệu . Vì vậy trong luận văn này,tơi sẽ đặt trọng tâm phát
triển thuật tốn ẩn danh để bảo vệ tính riêng tư của người dùng khi dữ liệu cá nhân
được sử dụng tuy nhiên vẫn đảm bảo dữ liệu được xử lý khi khai phá vẫn cho ra kết
quả tốt. Thuật toán được xây dựng theo phương pháp di chuyển tuple để biến đổi dữ
liệu, giảm bớt số lượng luật kết hợp sinh ra và mất đi trong quá trình xử lý. Ngồi ra
đề tài cịn đi sâu hơn vào các mơ hình khác ngồi k-anonymity như l-diversity để
khắc phục một số điểm yếu của mơ hình k-anonymity trước các kiểu tấn công tái
định danh cá nhân.

ii
HVTH: NGUYỄN PHÚC PHI HỔ



GVHD: TS TRƯƠNG TUẤN ANH

ABSTRACT
With the increasing prevalence of data collection and analysis, there is a
growing concern over the privacy risks posed by personal data. Data breaches,
identity theft, and other forms of cybercrime are just some of the risks associated with
the misuse of personal data. An important factor to consider is the trade-off between
data quality and privacy when deciding on a data anonymization method. Therefore,
in this thesis, I will focus on developing an anonymization algorithm to protect the
privacy of users when personal data is used, while still ensuring that the data is
processed effectively for data mining purposes. The algorithm will be built using the
tuple migration method to transform data, reducing the number of new generated
association rules and lost ones during processing. In addition, the thesis will delve
deeper into other models beyond k-anonymity, such as l-diversity, to overcome some
of the weaknesses of the k-anonymity model against personal re-identification
attacks.

LỜI CAM ĐOAN

iii
HVTH: NGUYỄN PHÚC PHI HỔ


GVHD: TS TRƯƠNG TUẤN ANH

Tôi xin cam đoan đây là cơng trình nghiên cứu của bản thân.
Các số liệu, kết quả trình bày trong luận văn là trung thực và chưa từng được
ai cơng bố trong bất kỳ cơng trình nào trước đây.


Học viên
NGUYỄN PHÚC PHI HỔ

iv
HVTH: NGUYỄN PHÚC PHI HỔ


GVHD: TS TRƯƠNG TUẤN ANH

Mục lục
CHƯƠNG 1: MỞ ĐẦU .............................................................................................. 1
1.1.

Giới thiệu đề tài ............................................................................................. 1

1.2.

Mục đích nghiên cứu ..................................................................................... 3

1.3.

Giới hạn đề tài ............................................................................................... 3

1.4.

Ý nghĩa khoa học và thực tiễn ....................................................................... 3

1.4.1.


Ý nghĩa khoa học .................................................................................... 3

1.4.2.

Ý nghĩa thực tiễn..................................................................................... 4

CHƯƠNG 2: CƠ SỞ LÝ THUYẾT ........................................................................... 6
2.1. Quyền riêng tư và chất lượng dữ liệu ............................................................... 6
2.2. Thuật toán Apriori ............................................................................................. 7
2.3. Khai phá luật kết hợp trong dữ liệu .................................................................. 9
2.4. Các định nghĩa liên quan khi ẩn danh dữ liệu ................................................ 11
2.5. Tác động đến chất lượng dữ liệu khi thực hiện ẩn danh ................................. 12
CHƯƠNG 3: CÁC CƠNG TRÌNH NGHIÊN CỨU LIÊN QUAN .......................... 17
3.1. Mơ hình K-anonymity .................................................................................... 17
3.2. Mơ hình L-diversity ........................................................................................ 18
3.3. Một số thuật toán ẩn danh ............................................................................... 22
3.3.1. Thuật toán Datafly .................................................................................... 22
3.3.2. Thuật toán Incognito ................................................................................ 23
3.3.3. Thuật toán Flash ....................................................................................... 24
3.3.4. Thuật toán Mondrian ................................................................................ 24
3.4. Kỹ thuật di chuyển tuple ................................................................................. 25
CHƯƠNG 4: HƯỚNG TIẾP CẬN VÀ THUẬT TOÁN .......................................... 28
4.1. Yêu cầu của giải thuật ..................................................................................... 28
4.2. Ý tưởng giải thuật ........................................................................................... 30
CHƯƠNG 5: ĐÁNH GIÁ GIẢI THUẬT ................................................................. 34
5.1. Hiện thực giải thuật......................................................................................... 34
5.2. Đánh giá thuật toán ......................................................................................... 39
CHƯƠNG 6: TỔNG KẾT......................................................................................... 44
6.1. Kết luận ........................................................................................................... 44


v
HVTH: NGUYỄN PHÚC PHI HỔ


GVHD: TS TRƯƠNG TUẤN ANH

6.2. Hướng phát triển ............................................................................................. 46
TÀI LIỆU THAM KHẢO ......................................................................................... 47
Mục lục hình
Hình 1: Tổng quan về bảo vệ quyền riêng tư khi xuất bản dữ liệu ............................. 1
Hình 2: Tập dữ liệu khơng ẩn danh gồm hồ sơ bệnh nhân một bệnh viện giả định . 17
Hình 3: Tập dữ liệu từ hình 1 đã được ẩn danh ........................................................ 18
Hình 4: Dữ liệu bệnh nhân nội trú ............................................................................ 19
Hình 5: Dữ liệu bệnh nhân nội trú đạt 4-anonymity ................................................. 19
Hình 6: Dữ liệu bệnh nhân nội trú đạt 3-diversity .................................................... 21
Hình 7: Cơng thức tính entropy của lớp tương đương G .......................................... 21
Hình 8: Sơ đồ thuật tốn Datafly .............................................................................. 22
Hình 9: Sơ đồ thuật tốn Incognito ........................................................................... 23
Hình 10: Sơ đồ thuật tốn Mondrian......................................................................... 25
Hình 11: Kỹ thuật MM để chuyển đổi dữ liệu đạt được mơ hình k-anonymity ....... 27
Hình 12: Mã giả của chương trình ............................................................................ 31
Hình 13: Kiến trúc tổng quát của chương trình ........................................................ 34
Hình 14: Phần trăm luật kết hợp mất đi của 2 giải thuật MAST và M3AR ............. 41
Hình 15: Phần trăm luật kết hợp mới sinh ra của 2 giải thuật MAST và M3AR ..... 41
Hình 16: Tỷ lệ của số lượng tuple có khả năng lộ thơng tin nhạy cảm .................... 42
Hình 17: Phần trăm luật kết hợp mất đi của 2 giải thuật MAST và Flash ................ 43
Hình 18: Phần trăm luật kết hợp mới sinh ra của 2 giải thuật MAST và Flash ........ 43

vi
HVTH: NGUYỄN PHÚC PHI HỔ



GVHD: TS TRƯƠNG TUẤN ANH

CHƯƠNG 1: MỞ ĐẦU
1.1.

Giới thiệu đề tài
Sự tiến bộ của công nghệ thông tin đã làm tăng khối lượng dữ liệu theo cấp số

nhân theo từng năm. Trong số những dữ liệu này ngày càng chứa nhiều thông tin cá
nhân. Lượng dữ liệu cá nhân này đã thu hút sự chú ý của nhiều bên nhằm tạo ra các
dịch vụ phù hợp và cá nhân hóa hơn, dựa trên thơng tin nhân khẩu học có sẵn. Vì lý
do này, các doanh nghiệp và tổ chức trong các lĩnh vực khác nhau thu thập dữ liệu cá
nhân có thể được chia sẻ trong nhiều hồn cảnh khác nhau (vì lý do kinh doanh, xã
hội hoặc pháp lý). Điều này đã mang lại những thách thức mới để bảo vệ quyền riêng
tư của những người có dữ liệu trong tập dữ liệu đã xuất bản.
Do đó, bảo vệ quyền riêng tư khi xuất bản dữ liệu (PPDP) đã trở thành một
lĩnh vực được các nhà nghiên cứu và học viên quan tâm. Một kịch bản điển hình của
PPDP được mơ tả trong Hình 1, thể hiện các giai đoạn khác nhau của quá trình xử lý
dữ liệu. Một giả định chính của mơ hình PPDP là những kẻ tấn cơng có thể tồn tại
trong số những người nhận dữ liệu, những kẻ có ý định khám phá thơng tin nhạy cảm
về các cá nhân. Do đó, mục tiêu của các kỹ thuật PPDP là sửa đổi dữ liệu bằng cách
làm cho dữ liệu ít cụ thể hơn để có thể bảo vệ quyền riêng tư của cá nhân; trong khi
vẫn duy trì tính hữu ích của dữ liệu được ẩn danh.

Hình 1: Tổng quan về bảo vệ quyền riêng tư khi xuất bản dữ liệu

1
HVTH: NGUYỄN PHÚC PHI HỔ



GVHD: TS TRƯƠNG TUẤN ANH

Bản chất của PPDP là tạo ra các tập dữ liệu hữu ích cho nhiều tác vụ khác
nhau, vì thơng thường, tất cả các kịch bản tiềm năng của việc sử dụng dữ liệu đều
chưa được biết tại thời điểm xuất bản. Ví dụ khi cơng bố dữ liệu, không thể xác định
tất cả những người nhận dữ liệu. Do đó, bất kỳ bên kiểm sốt dữ liệu nào liên quan
đến việc chia sẻ dữ liệu cá nhân đều cần áp dụng các cơ chế bảo vệ quyền riêng tư.
Tuy nhiên, đây không phải là một nhiệm vụ dễ dàng, vì những nhân viên của
đơn vị xuất bản dữ liệu thường không phải là chuyên gia trong lĩnh vực bảo mật dữ
liệu. Hơn nữa, thường không có phương pháp nào đảm bảo rằng việc ẩn danh được
tiến hành hiệu quả trong một tổ chức. Điều này có thể khiến họ sử dụng các phương
pháp hủy nhận dạng đơn giản (ví dụ: xóa tất cả các thuộc tính nhận dạng trực tiếp
như tên và số căn cước công dân), trước khi công bố dữ liệu. Tuy nhiên, người ta đã
chứng minh rằng chỉ riêng phương pháp này là không đủ để bảo vệ quyền riêng tư
[1]. Sự cố vẫn có thể xảy ra do kết hợp các tuple khác nhau hoặc có kiến thức cơ bản
về các cá nhân để suy luận về danh tính của họ. Việc xác định lại một cá nhân đạt
được bằng cách liên kết các thuộc tính, được gọi là thuộc tính khả định danh (quasiidentifiers-QID), chẳng hạn như giới tính, ngày sinh hoặc mã ZIP.
Mơ hình ẩn danh nổi tiếng nhất là k-anonymity [2], cung cấp khả năng bảo vệ
quyền riêng tư bằng cách hiển thị dữ liệu không thể phân biệt được với ít nhất k-1 dữ
liệu khác. Tuy nhiên, thông tin nhạy cảm được ẩn danh bằng k-anonymity không tuyệt
đối an toàn và tồn tại nhược điểm với một số kiểu tấn cơng. Nhiều mơ hình được đề
xuất để khắc phục các điểm yếu này, trong đó có l-diversity [3] , kèm theo đó là nhiều
kỹ thuật liên quan để đạt được mơ hình này [4] [5].
Do đó, trọng tâm của đề tài sẽ tập trung giải quyết vấn đề phát triển một thuật
toán ẩn danh để bảo vệ danh tính của người dùng bằng cách chuyển đổi dữ liệu sang
mơ hình l-diversity, đồng thời vẫn giữ được tính hữu ích của tập dữ liệu để phục vụ
cho việc khai phá dữ liệu, ví dụ như khi một bệnh viện muốn công bố dữ liệu nhập
viện của các bệnh nhân cho các bên thứ ba để phục vụ cho cơng tác thống kê hoặc

phân tích dữ liệu.

2
HVTH: NGUYỄN PHÚC PHI HỔ


GVHD: TS TRƯƠNG TUẤN ANH

1.2.

Mục đích nghiên cứu
Khi thực hiện ẩn danh hóa dữ liệu, một trong những tiêu chí quan trọng cần

cân nhắc là sự đánh đổi giữa độ bảo mật và chất lượng của dữ liệu. Mặt khác, dữ liệu
thường được khai thác bằng nhiều mơ hình , trong đó sử dụng luật kết hợp là phương
thức phổ biến. Mục tiêu của đề tài là phát triển giải thuật ẩn danh để bảo vệ quyền
riêng tư khi thực hiện công khai dữ liệu thu thập tuy nhiên vẫn có khả năng đảm bảo
chất lượng dữ liệu được giữ lại tốt nhất. Giải thuật ẩn danh hóa dữ liệu đạt bằng cách
biến đổi dữ liệu đạt được mơ hình l-diversity để cải thiện điểm yếu trước một số kiểu
tấn cơng so với mơ hình k-anonymity đồng thời đảm bảo dữ liệu đầu ra vẫn có chất
lượng khi được sử dụng cho các bên khai phá dữ liệu.
1.3.

Giới hạn đề tài
Đề tài này sẽ tập trung tìm hiểu:
• Các giải thuật phù hợp để ẩn danh tập dữ liệu dạng bảng đạt được
mơ hình l-diversity
• Giải thuật cung cấp dữ liệu khi ẩn danh vẫn hữu ích khi thực hiện
khai thác bằng các kỹ thuật dựa trên luật kết hợp.
• Giải thuật sẽ hoạt động với các thuộc tính khả định danh và thuộc

tính nhạy cảm được người dùng định sẵn.

1.4.

Ý nghĩa khoa học và thực tiễn

1.4.1. Ý nghĩa khoa học
Chương trình ẩn danh dữ liệu là một phương pháp để bảo vệ quyền
riêng tư của người dùng trong việc chia sẻ dữ liệu. Khi chương trình ẩn danh
dữ liệu được áp dụng, các bên tham gia sẽ chỉ có thể truy cập thơng tin được
ẩn danh, thay vì thơng tin cá nhân của từng người. Tuy nhiên, việc áp dụng
chương trình ẩn danh dữ liệu có thể dẫn đến việc mất mát thơng tin quan trọng
trong q trình xử lý dữ liệu.

3
HVTH: NGUYỄN PHÚC PHI HỔ


GVHD: TS TRƯƠNG TUẤN ANH

Thuật toán di chuyển tuple là một phương pháp để giải quyết vấn đề
này bằng cách di chuyển các giá trị trong các tuple để tạo ra các tuple mới.
Việc di chuyển các giá trị này có thể giúp giảm thiểu số lượng luật kết hợp bị
mất đồng thời hạn chế số lượng luật kết hợp mới được sinh ra mà vẫn đảm bảo
tính ẩn danh của dữ liệu.
Ngồi tiêu chí k-anonymity , giải thuật cịn đạt được tiêu chí l-diversity,
khác phục được những vấn đề mà mơ hình trước cịn gặp phải. Vì vậy, trong
lĩnh vực ẩn danh hóa dữ liệu để bảo vệ quyền riêng tư của người dùng, đề tài
này có những ý nghĩa khoa học sau:
• Nghiên cứu và tổng kết các giải thuật hiện có cũng như các ưu

điểm của mỗi thuật giải.
• Đề xuất giải thuật mới tập trung chủ yếu vào việc khai thác luật
kết hợp có trong dữ liệu, đồng thời dữ liệu cũng đạt được mơ
hình l-diversity có tiêu chí ẩn danh tốt hơn so với mơ hình kanonymity.
• Phân tích những hướng phát triển tiếp theo để giải quyết bài toán
đảm bảo chất lượng của dữ liệu sau khi thực hiện ẩn danh một
cách tổng quát.
1.4.2. Ý nghĩa thực tiễn
Số lượng người dùng internet và lượng dữ liệu được tạo ra đều tăng
theo cấp số nhân do sự phát triển của internet. Người dùng tạo ra khối lượng
dữ liệu khổng lồ mỗi ngày khi mạng xã hội, thương mại điện tử và các hoạt
động trực tuyến khác trở nên phổ biến hơn. Bên cạnh đó, các tổ chức sử dụng
dữ liệu này cho nhiều mục đích khác nhau như nghiên cứu, dự đốn hành vi,...
Do đó, việc ẩn danh dữ liệu ngày càng trở nên cần thiết để bảo vệ tính bảo mật
và quyền riêng tư cho thông tin cá nhân của mọi người, đồng thời dữ liệu vẫn
phải lưu giữ được chất lượng để phục vụ mục đích khai thác của các bên thu
thập.

4
HVTH: NGUYỄN PHÚC PHI HỔ


GVHD: TS TRƯƠNG TUẤN ANH

Đề tài mang những ý nghĩa thực tiễn sau:
• Về phía người dùng: với mục tiêu ẩn danh dữ liệu, người dùng
khi cung cấp các thông tin sẽ hạn chế khả năng bị nhận diện và
khám phá các thông tin nhạy cảm của cá nhân. Các tổ chức áp
dụng quy trình ẩn danh dữ liệu đảm bảo các tiêu chí về sự ẩn
danh và riêng tư của người dùng đều được cân nhắc và xử lý.

• Về phía người quản trị: các tổ chức thu thập dữ liệu thơng
thường sẽ khơng có những chun gia về lĩnh vực bảo mật tính
riêng tư của dữ liệu, do đó giải thuật có thể giúp cho qui trình
ẩn danh dữ liệu trở nên dễ dàng hơn, cũng như đảm bảo chất
lượng dữ liệu được lưu giữ tốt nhất có thể.

5
HVTH: NGUYỄN PHÚC PHI HỔ


GVHD: TS TRƯƠNG TUẤN ANH

CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
2.1. Quyền riêng tư và chất lượng dữ liệu
Sự đánh đổi giữa quyền riêng tư và chất lượng của dữ liệu là sự cân bằng mà
các nhà nghiên cứu và tổ chức phải cân nhắc khi quyết định cách xử lý dữ liệu nhạy
cảm. Một mặt, quyền riêng tư dữ liệu rất quan trọng để bảo vệ thông tin cá nhân của
các cá nhân và đảm bảo rằng dữ liệu không bị sử dụng sai mục đích hoặc lạm dụng.
Mặt khác, chất lượng của dữ liệu rất quan trọng để cho phép nghiên cứu và phân tích
có thể dẫn đến những hiểu biết và khám phá ý nghĩa.
Mức độ bảo mật dữ liệu và chất lượng dữ liệu được yêu cầu sẽ tùy thuộc vào
trường hợp sử dụng và bối cảnh cụ thể. Ví dụ: trong một số trường hợp, quyền riêng
tư dữ liệu nghiêm ngặt có thể cần thiết để tuân thủ các yêu cầu pháp lý hoặc đạo đức,
trong khi trong các trường hợp khác, tiện ích dữ liệu có thể được ưu tiên để hỗ trợ các
hoạt động kinh doanh hoặc nghiên cứu quan trọng.
Tuy nhiên, thường có sự đánh đổi giữa quyền riêng tư của dữ liệu và chất
lượng dữ liệu. Ví dụ: để bảo vệ quyền riêng tư của thơng tin cá nhân, dữ liệu có thể
cần được ẩn danh hoặc tổng hợp, điều này có thể dẫn đến mất thông tin chi tiết và
giảm độ chính xác cũng như tính hữu ích của dữ liệu đối với một số loại phân tích.
Ngồi ra, nếu dữ liệu không được ẩn danh hoặc bảo vệ đầy đủ, dữ liệu đó có thể dễ

bị nhận dạng lại hoặc sử dụng sai mục đích, điều này có thể ảnh hưởng đến quyền
riêng tư và bảo mật của các cá nhân.
Thất thốt thơng tin là một yếu tố quan trọng phải được xem xét khi cân bằng
quyền riêng tư dữ liệu và tiện ích dữ liệu. Khi dữ liệu được chuyển đổi hoặc xử lý để
bảo vệ quyền riêng tư, một số thơng tin có thể bị mất trong q trình này. Điều này
có thể làm giảm độ chính xác và tính hữu ích của dữ liệu đối với một số loại phân
tích nhất định, điều này có thể hạn chế những hiểu biết sâu sắc và khám phá có thể
được thực hiện từ dữ liệu.
Lượng thông tin bị mất có thể chấp nhận được sẽ phụ thuộc vào trường hợp
và bối cảnh sử dụng cụ thể. Ví dụ: trong một số trường hợp, mức độ riêng tư dữ liệu

6
HVTH: NGUYỄN PHÚC PHI HỔ


GVHD: TS TRƯƠNG TUẤN ANH

cao có thể rất quan trọng và các nhà nghiên cứu có thể sẵn sàng chấp nhận mức độ
mất thông tin cao hơn để bảo vệ thơng tin cá nhân. Trong các trường hợp khác, tiện
ích dữ liệu có thể được ưu tiên và các nhà nghiên cứu có thể sẵn sàng chấp nhận mức
độ riêng tư dữ liệu thấp hơn để cho phép phân tích chi tiết và chính xác hơn.
Để quản lý sự đánh đổi giữa quyền riêng tư và chất lượng dữ liệu, các nhà
nghiên cứu và tổ chức phải xem xét cẩn thận các yêu cầu cụ thể và rủi ro tiềm ẩn liên
quan đến dữ liệu của họ. Điều này có thể liên quan đến việc tiến hành đánh giá tác
động đến quyền riêng tư để xác định các rủi ro tiềm ẩn về quyền riêng tư và phát triển
các chiến lược để giảm thiểu những rủi ro đó. Nó cũng có thể liên quan đến việc đánh
giá hiệu quả của các kỹ thuật ẩn danh và nâng cao quyền riêng tư khác nhau để xác
định mức độ mất thông tin có thể chấp nhận được đối với một tập dữ liệu cụ thể.
Nhìn chung, sự đánh đổi giữa quyền riêng tư dữ liệu và tiện ích dữ liệu cũng
như lượng thơng tin bị mất có thể chấp nhận được sẽ phụ thuộc vào trường hợp và

bối cảnh sử dụng cụ thể. Bằng cách cân bằng cẩn thận các yếu tố này, các nhà nghiên
cứu và tổ chức có thể đảm bảo rằng dữ liệu nhạy cảm được bảo vệ trong khi vẫn cho
phép nghiên cứu và phân tích quan trọng.
Trong đề tài này, giải thuật ẩn danh sẽ sử dụng một kỹ thuật phi truyền thống
như Tổng quát hóa hay Loại bỏ, mà sử dụng kỹ thuật di chuyển các tuples với khả
năng cung cấp dữ liệu có chất lượng tốt hơn khi khai thác bằng luật kết hợp so với
các kỹ thuật truyền thống. Các kỹ thuật sẽ được trình bày cụ thể ở chương tiếp theo.
2.2. Thuật tốn Apriori
Thuật toán Apriori [6] là một thuật toán phổ biến được sử dụng để khai thác
tập phổ biến và học luật kết hợp trong khai thác dữ liệu và học máy. Nó được sử dụng
để xác định các tập phổ biến trong một tập dữ liệu nhất định và trích xuất các quy tắc
kết hợp từ chúng, có thể được sử dụng để phân tích nhu cầu mua sắm, hệ thống đề
xuất và các ứng dụng khác.
Thuật toán hoạt động bằng cách trước tiên xác định tất cả các mục riêng lẻ
xuất hiện phổ biến trong tập dữ liệu, sau đó lặp lại việc tạo các tập phổ biến lớn hơn
7
HVTH: NGUYỄN PHÚC PHI HỔ


GVHD: TS TRƯƠNG TUẤN ANH

bằng cách nối các tập mục phổ biến từ lần lặp trước. Ý tưởng là nếu một tập phổ biến
thì tất cả các tập con của nó cũng phải phổ biến. Tính chất này được gọi là "ngun
tắc Apriori".
Thuật tốn Apriori gồm các bước :
1. Tính độ hỗ trợ: Bước đầu tiên của thuật toán Apriori là tính số lần xuất hiện
của từng mục trong tập dữ liệu, là số lượng giao dịch có chứa mục đó. Bước
này liên quan đến việc qt tồn bộ tập dữ liệu và đếm số lần xuất hiện của
từng mục.
2. Tạo tập phổ biến: Sau khi đã đếm được độ hỗ trợ của từng mục, bước tiếp theo

là tạo tập mục phổ biến, là tập mục thường xuyên xuất hiện cùng nhau. Một
tập phổ biến được định nghĩa là một tập hợp các mục có giá trị hỗ trợ lớn hơn
hoặc bằng ngưỡng hỗ trợ tối thiểu do người dùng xác định.Thuật toán Apriori
tạo ra các tập phổ biến bằng cách sử dụng cách tiếp cận "từ dưới lên trên", bắt
đầu với các mục riêng lẻ và dần dần xây dựng thành các tập mục lớn hơn. Các
thuật toán hoạt động như sau:
• Đầu tiên, tất cả các mục riêng lẻ có giá trị hỗ trợ lớn hơn hoặc bằng ngưỡng
hỗ trợ tối thiểu được xác định là tập phổ biến.
• Tiếp theo, thuật tốn lặp lại tạo ra các tập phổ biến ngày càng lớn hơn bằng
cách nối các tập phổ biến từ lần lặp trước. Cụ thể, thuật tốn tạo ra các tập
phổ biến có độ dài k+1 bằng cách nối các tập phổ biến có độ dài k có chung
k-1 mục đầu tiên.
• Độ hỗ trợ của mỗi tập mục ứng cử viên sau đó được tính bằng cách quét
toàn bộ tập dữ liệu và đếm số lượng giao dịch có chứa tập mục ứng cử viên.
• Cuối cùng, các tập mục ứng viên có giá trị hỗ trợ lớn hơn hoặc bằng ngưỡng
hỗ trợ tối thiểu được xác định là tập phổ biến cho lần lặp hiện tại và quá
trình này được lặp lại để tạo ra các tập mục ứng viên cho lần lặp tiếp theo.
3. Tạo luật kết hợp: Khi các tập mục phổ biến đã được tạo, thuật tốn Apriori có
thể được sử dụng để tạo các luật kết hợp, mô tả mối quan hệ giữa các mục
trong tập dữ liệu. Một luật kết hợp là một câu lệnh có dạng X -> Y, trong đó X
8
HVTH: NGUYỄN PHÚC PHI HỔ


GVHD: TS TRƯƠNG TUẤN ANH

và Y là các tập mục, và luật chỉ ra rằng nếu X xảy ra trong một giao dịch thì Y
cũng có khả năng xảy ra.
Để tạo các luật kết hợp, thuật tốn Apriori tính tốn độ tin cậy của từng luật, đó là
xác suất Y xảy ra trong một giao dịch nếu X xảy ra. Độ tin cậy của một quy tắc X ->

Y được định nghĩa là độ hỗ trợ của tập phổ biến (X U Y) chia cho độ hỗ trợ của X.
Sau đó, thuật tốn sẽ chọn các quy tắc đáp ứng ngưỡng độ tin cậy tối thiểu do người
dùng xác định.
Thuật tốn tiếp tục q trình này cho đến khi khơng tìm thấy tập phổ biến nào
nữa. Khi các tập mục phổ biến đã được xác định, thuật tốn có thể tạo ra các luật kết
hợp bằng cách tính tốn độ tin cậy của từng quy tắc (tức là xác suất mà quy tắc đó
tồn tại với tiền đề) và chọn các quy tắc đáp ứng ngưỡng tin cậy tối thiểu do người
dùng xác định.
Nhìn chung, thuật tốn Apriori là một cách hiệu quả để khám phá các tập phổ biến
và rút ra các luật kết hợp từ các tập dữ liệu lớn. Tuy nhiên, nó có thể tốn kém về mặt
tính tốn đối với các bộ dữ liệu rất lớn và ngưỡng hỗ trợ hoặc ngưỡng tin cậy tối thiểu
cao. Ngồi ra cịn có các thuật tốn thay thế có thể hiệu quả hơn trong các tình huống
nhất định.
2.3. Khai phá luật kết hợp trong dữ liệu
Luật kết hợp là một phương pháp xác định mối quan hệ giữa hai hoặc nhiều
giá trị trong tập dữ liệu. Chúng thường được sử dụng trong khai thác dữ liệu và học
máy. Luật kết hợp có thể giúp xác định các mẫu hoặc mối tương quan trong dữ liệu,
có thể được sử dụng để đưa ra dự đốn hoặc cung cấp thơng tin cho việc ra quyết
định. Độ hỗ trợ và độ tin cậy là hai biện pháp quan trọng được sử dụng trong khai
phá luật kết hợp.
• Độ hỗ trợ (support): Độ hỗ trợ của một luật kết hợp là tỷ lệ giao dịch trong tập
dữ liệu chứa tất cả các mục trong quy tắc. Nó đo tần suất mà luật xảy ra trong
tập dữ liệu. Độ hỗ trợ của một luật có thể được tính bằng số lượng giao dịch

9
HVTH: NGUYỄN PHÚC PHI HỔ


GVHD: TS TRƯƠNG TUẤN ANH


chứa tất cả các mục trong luật chia cho tổng số giao dịch trong tập dữ liệu. Giá
trị hỗ trợ cao cho biết rằng luật xảy ra thường xuyên trong tập dữ liệu.
• Độ tin cậy (confidence): Độ tin cậy của luật là tỷ lệ giao dịch chứa tất cả các
mục trong luật, cũng như một mục bổ sung. Nó đo lường sức mạnh của sự liên
kết giữa các mục trong luật. Độ tin cậy của một luật có thể được tính bằng độ
hỗ trợ của luật chia cho độ hỗ trợ của tiền đề (các mục ở phía bên trái của luật).
Giá trị độ tin cậy cao cho thấy luật có tính dự đốn cao.
Để tính tốn độ hỗ trợ và độ tin cậy cho một luật, trước tiên chúng ta cần xác
định các mục và giao dịch trong tập dữ liệu. Giả sử chúng ta có một tập dữ liệu về
các giao dịch mua của khách hàng tại một cửa hàng tạp hóa và chúng ta muốn xác
định các luật cho biết những mặt hàng nào thường được mua cùng nhau. Chúng ta có
thể bắt đầu bằng cách đếm số giao dịch có chứa từng mục hoặc kết hợp các mục.
Khi chúng ta có số lượng mục, ta có thể tính tốn độ hỗ trợ và độ tin cậy cho
từng luật. Ví dụ: giả sử chúng ta muốn tính tốn độ hỗ trợ và độ tin cậy cho luật kết
hợp "Nếu khách hàng mua sữa, họ cũng có khả năng mua bánh mì".
Để tính toán độ hỗ trợ cho luật này, ta sẽ đếm số lượng giao dịch trong tập dữ
liệu chứa cả sữa và bánh mì, rồi chia số này cho tổng số giao dịch trong tập dữ liệu.
Nếu có 1000 giao dịch trong tập dữ liệu và 100 giao dịch trong số đó chứa cả sữa và
bánh mì, thì độ hỗ trợ cho luật này sẽ là 100/1000 = 0,1 hoặc 10%.
Để tính tốn độ tin cậy cho luật này, ta sẽ đếm số lượng giao dịch có cả sữa và
bánh mì, rồi chia số này cho số lượng giao dịch có chứa sữa. Nếu có 200 giao dịch
chứa sữa và 100 giao dịch trong số đó cũng chứa bánh mì, thì độ tin cậy cho quy tắc
này sẽ là 100/200 = 0,5 hoặc 50%.
Cả độ hỗ trợ và độ tin cậy đều có thể nằm trong khoảng từ 0 đến 1, các giá trị
càng cao cho thấy các liên kết càng mạnh. Điều quan trọng cần lưu ý là độ hỗ trợ và
độ tin cậy không phải là thước đo duy nhất của sự liên kết và các thước đo khác như
độ nâng cao(lift) và độ thuyết phục(conviction) cũng có thể được sử dụng tùy thuộc
vào bối cảnh phân tích.
10
HVTH: NGUYỄN PHÚC PHI HỔ



GVHD: TS TRƯƠNG TUẤN ANH

Cần lưu ý rằng việc lựa chọn ngưỡng của độ hỗ trợ và độ tin cậy có thể có tác
động đáng kể đến số lượng và chất lượng của các quy tắc được phát hiện. Việc đặt
ngưỡng hỗ trợ thấp có thể dẫn đến các luật có ý nghĩa thống kê thấp, trong khi việc
đặt ngưỡng độ tin cậy cao có thể dẫn đến các luật q cụ thể để trở nên hữu ích. Việc
tìm kiếm sự cân bằng phù hợp giữa các biện pháp này đòi hỏi phải xem xét cẩn thận
dữ liệu và mục tiêu của phân tích.
2.4. Các định nghĩa liên quan khi ẩn danh dữ liệu
Trong một cơ sở dữ liệu dạng bảng, mỗi hàng của bảng là một bộ (tuple) và
mỗi cột là một thuộc tính. Có các loại thuộc tính được định nghĩa trong một cơ sở dữ
liệu:
• Quasi-Identifier (QIDs): Là một nhóm các thuộc tính trong bảng dữ liệu, sao
cho khi kết hơp các thuộc tính này lại có thể xác định từ một mẫu dữ liệu danh
tính thật sự một cá nhân trong dữ liệu đó. Hay cịn gọi là nhóm thuộc tính khả
định danh.
• Sensitive attributes (SA): là các thuộc tính chứa các thơng tin đặc biệt nhạy
cảm của một cá nhân. Một cá nhân chắc chắn sẽ khơng muốn bị lộ thơng tin
này.
• Non-Sensitive attibutes (non-SA): là những thuộc tính cịn lại khơng có tính
chất đặc biệt.
• Equivalence class (EQ): lớp tương đương là một nhóm các tuple có giá trị các
thuộc tính QID giống nhau.
Một mẫu dữ liệu được cho là có các thuộc tính k-anonymity hoặc l-diversity
nếu nó thỏa các tính chất như bên dưới.
• K-Anonymity: nếu thơng tin cho mỗi người có trong mẫu đó khơng thể phân
biệt với ít nhất k − 1 cá nhân khác trong mẫu.
• L-diversity: tính chất l-diversity đảm bảo bằng mỗi nhóm đã đạt k-anonymity

tồn tại thêm ít nhất l giá trị sensitive attributes khác nhau. Một vấn đề khiến kanonymity có điểm yếu là khi một cá nhân đã thuộc một nhóm k-ẩn danh,

11
HVTH: NGUYỄN PHÚC PHI HỔ


GVHD: TS TRƯƠNG TUẤN ANH

nhưng nhóm này lại có chung giá trị của thuộc tính nhạy cảm (SA). Nếu biết
được các cá nhân thuộc nhóm này, thơng tin nhạy cảm của cá nhân sẽ bị lộ.
Vấn đề này sẽ được giải quyết nếu ràng buộc l-diversity được áp dụng.
Giải thuật sẽ cố gắng lưu giữ nhiều luật kết hợp nhất có thể khi chuyển đổi ,
tuy nhiên thực tế việc này sẽ gặp nhiều khó khăn vì số lượng luật trong tập dữ liệu là
rất lớn. Do đó giải thuật sẽ chỉ tập trung lưu trữ các luật kết hợp thường xuất hiện
trong dữ liệu. Ta gọi đây là các luật kết hợp mạnh, và giải thuật sẽ sử dụng 2 ngưỡng
giới hạn để xác định các luật kết hợp này có mạnh hay khơng là s_m và c_m. Một
luật kết hợp được xem là mạnh nếu nó có độ hỗ trợ lớn hơn s_m và độ tin cậy lớn
hơn c_m. Nếu không thỏa cả 2, luật kết hợp này sẽ được coi là luật kết hợp yếu.
Khi thực hiện di chuyển các tuple giữa hai nhóm a → b, trong đó a và b là các
nhóm, sẽ thay đổi tất cả các giá trị QI của một số tuple trong a thành các giá trị tương
quan trong b. Ví dụ: nhóm a có hai tuple với QI là (x1, y1, t1) và nhóm b có ba tuple
với QI là (x2, y2, t2), sự thay đổi a → b sẽ tạo thành nhóm b có năm tuple. Các tuple
bổ sung là từ nhóm a và các thuộc tính QI của chúng được thay đổi thành (x2, y2, t2).
Việc di chuyển a → b là toàn bộ nếu tất cả các tuple trong nhóm a được chuyển
sang nhóm b. Ngược lại, nếu chỉ một vài tuple được chuyển, việc di chuyển sẽ là một
phần.
2.5. Tác động đến chất lượng dữ liệu khi thực hiện ẩn danh
Sự đánh đổi giữa quyền riêng tư và chất lượng dữ liệu rất quan trọng khi thực
hiện PPDP. Các phương pháp truyền thống đã sử dụng nhiều thước đo khác nhau làm
cơ sở đánh giá các thuật tốn thơng qua việc giảm thiểu sự thất thốt thông tin dữ

liệu, chẳng hạn như Distortion [7], IL [8], và NCP [9]. Các thước đo này quá chung
chung và khơng tập trung vào việc duy trì chất lượng dữ liệu đối với bất kỳ kỹ thuật
khai thác dữ liệu cụ thể nào. Tuy nhiên, trên thực tế dữ liệu sau khi được sửa đổi sẽ
được khai thác bằng một kỹ thuật khai thác cụ thể. Do đó, dữ liệu được ẩn danh hóa
có thể khơng mang lại chất lượng dữ liệu cao cho bất kỳ kỹ thuật khai thác nào.Vì

12
HVTH: NGUYỄN PHÚC PHI HỔ


GVHD: TS TRƯƠNG TUẤN ANH

vậy, luận văn sẽ trình bày một giải thuật biến đổi dữ liệu phù hợp với kỹ thuật khai
phá dữ liệu dựa theo luật kết hợp.
Gọi I = {i1, i2, . . . , in} là tập các thuộc tính có trong tập dữ liệu D chứa các
tuples. Một luật kết hợp thuộc D được ký hiệu: A→B (trong đó A⸦I, B⸦I, A∩B=∅).
Cho C =

A∪B. Ta gọi độ hỗ trợ của C, ký hiệu Support(A →B) = P(C), là tỉ lệ xuất

hiện các tuple chứa cả A và B trong tập dữ liệu D. Độ tin cậy của C, ký hiệu
Confidence(A→B) = P(B|A) = P(C)/ P(A) là tỉ lệ các tuple cả A và B trên các tuple
chỉ chứa A. Độ phổ biến tối thiểu s_m và độ tin cậy tối thiểu c_m là 2 giá trị được
định nghĩa bởi người dùng, một luật kết hợp A→B được xem là mạnh khi Support(A
→B) = s ≥ s_m và Confidence(A→B) = c ≥ c_m.
Khi D được xử lý ẩn danh, sẽ tồn tại các tuples bị thay đổi giá trị của thuộc
tính khả định danh trong đó bao gồm các giá trị thuộc A và B, làm ảnh hưởng đến luật
kết hợp A→B. Để luật kết hợp A→B được duy trì thì số lượng tuple hỗ trợ luật bị
thay đổi không được vượt quá s – s_m, vì khi đó độ phổ biến Support(A →B) = s’ <
s_m. Tuy nhiên ta còn cần xét đến thay đổi ở độ tin cậy Confidence(A→B).

Trường hợp 1: A bị thay đổi
Gọi n là số lượng tuple bị thay đổi có chứa A, độ phổ biến và độ tin cậy mới
của luật sẽ là:

Trong đó t(A →B) là số lượng tuple chứa cả A và B, t(A) là số lượng tuple chỉ
có A, total là số lượng tuple của D. Để luật tồn tại, thì s’ ≥ s_m và c’ ≥ c_m. Ngoài
ra, độ phổ biến và độ tin cậy cũ được tính theo cơng thức:

13
HVTH: NGUYỄN PHÚC PHI HỔ


GVHD: TS TRƯƠNG TUẤN ANH

Do đó, số lượng tuple tối đa có thể thay đổi sẽ là :

Trường hợp 2: B bị thay đổi
Tương tự, ta có:

Để luật tồn tại, thì s’ ≥ s_m và c’ ≥ c_m. Vì vậy số lượng tuple tối đa có thể
thay đổi sẽ là :

Trường hợp 3: A và B cùng thay đổi
Ta nhận xét thấy trường hợp này giống ở trường hợp 1. Số lượng tuple tối đa
có thể thay đổi sẽ là :

14
HVTH: NGUYỄN PHÚC PHI HỔ



GVHD: TS TRƯƠNG TUẤN ANH

Như vậy với mỗi luật kết hợp A →B, sẽ có số lượng n tuple có thể thay đổi
trong quá trình ẩn danh để luật này vẫn tồn tại, với n được tính theo (1) nếu A bị thay
đổi, và (2) nếu chỉ có B bị thay đổi.
Đối với luật kết hợp yếu A →B , giải thuật cũng phải đảm bảo luật này sẽ
không trở thành luật kết hợp mạnh khi thực hiện bất kỳ thay đổi nào. Khi một tuple
bị thay đổi, giá trị thuộc tính bị thay đổi có thể là A hoặc B, do đó độ hỗ trợ và độ tin
cậy của luật này bị tác động và luật trở thành luật kết hợp mạnh. Trong phần này,
chúng ta sẽ tính tốn số lượng tuple tối đa mà một luật nhận được trước khi nó trở
thành luật kết hợp mạnh. s và c là độ hỗ trợ và độ ưu tiên của luật trước khi thay đổi,
s’ và c’ là kết quả sau khi thay đổi. n là số lượng tuple thêm vào. Ta sẽ cân nhắc các
trường hợp:
Trường hợp 1: Số lượng A được thêm
Ta ln có:

Trong đó t(A →B) là số lượng tuple chứa cả A và B, t(A) là số lượng tuple chỉ
có A, total là số lượng tuple của D. Rõ ràng c’ luôn luôn nhỏ hơn c. Ngồi ra :

Do đó nếu chỉ có giá trị A bị thay đổi, luật kết hợp này sẽ không trở thành luật mạnh.
Trường hợp 2: B được thêm vào. Tương tự trường hợp 1, luật này cũng không
trở thành luật mạnh.
Trường hợp 3: A và B cùng được tăng.

15
HVTH: NGUYỄN PHÚC PHI HỔ


GVHD: TS TRƯƠNG TUẤN ANH


Ta có:

Ngồi ra:

Điều kiện để luật này không trở thành luật kết hợp mạnh là s_m ≥ s’ và c_m
≥ c’. Do đó ta có giá trị của n sẽ là:

Như vậy đối với luật kết hợp không mạnh, khi A và B được thêm vào, số lượng
tuple n tối đa có thể tăng thêm mà khơng ảnh hưởng đến trạng thái của luật sẽ được
tính theo công thức (4).

16
HVTH: NGUYỄN PHÚC PHI HỔ