ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI BÁCH KHOA
HUỲNH TRIỆU VỸ
NGHIÊN CỨU VÀ PHÁT TRIỂN MỘT SỐ KỸ THUẬT
CHE GIẤU THÔNG TIN NHẠY CẢM TRONG KHAI
PHÁ HỮU ÍCH CAO
LUẬN ÁN TIẾN SĨ KỸ THUẬT
ĐÀ NẴNG, 02/2023
ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI BÁCH KHOA
HUỲNH TRIỆU VỸ
NGHIÊN CỨU VÀ PHÁT TRIỂN MỘT SỐ KỸ THUẬT
CHE GIẤU THÔNG TIN NHẠY CẢM TRONG KHAI
PHÁ HỮU ÍCH CAO
CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH
MÃ SỐ: 9480101
LUẬN ÁN TIẾN SĨ KỸ THUẬT
Người hướng dẫn khoa học:
1. TS. TRƯƠNG NGỌC CHÂU
2. TS. LÊ QUỐC HẢI
ĐÀ NẴNG, 02/2023
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu do tôi thực hiện, dưới sự hướng
dẫn của TS. Trương Ngọc Châu và TS. Lê Quốc Hải.
Tôi cam đoan các kết quả nghiên cứu được trình bày trong luận án là trung thực
và không sao chép từ bất kỳ luận án nào khác. Một số nhiệm vụ nghiên cứu là thành
quả tập thể và đã được các đồng tác giả đồng ý cho sử dụng. Mọi trích dẫn đều có ghi
nguồn gốc xuất xứ rõ ràng và đầy đủ.
Tác giả
NCS. Huỳnh Triệu Vỹ
i
LỜI CẢM ƠN
Trước tiên, tôi xin gởi lời tri ân đến thầy TS. Trương Ngọc Châu và thầy TS. Lê
Quốc Hải là người trực tiếp hướng dẫn và đồng hành cùng tôi từ khi bắt đầu nghiên
cứu cho đến khi hoàn thành luận án. Xin được bày tỏ lòng biết ơn đối với Quý thầy
PGS-TS. Nguyễn Tấn Khôi, PGS-TS. Nguyễn Thanh Bình, PGS-TS. Võ Trung Hùng,
TS. Huỳnh Hữu Hưng là những thầy đã trực tiếp giảng dạy tôi trong các chuyên đề
nghiên cứu của nghiên cứu sinh.
Tôi xin trân trọng cảm ơn Ban Sau Đại học - Đại học Đà Nẵng, Phòng Đào tạo Trường Đại học Bách khoa đã tạo mọi điều kiện thuận lợi cho tôi trong thời gian học
tập, nghiên cứu và thực hiện luận án.
Tôi xin gởi lời cảm ơn chân thành đến Ban Lãnh đạo và tập thể giảng viên Khoa
Công nghệ Thông tin - Trường Đại học Bách khoa đã tạo môi trường học thuật thân
thiện và tích cực cho các nghiên cứu sinh.
Xin cảm ơn các đồng tác giả đã đồng ý cho tôi sử dụng các kết quả nghiên cứu
chung cho luận án.
Cuối cùng, tôi xin được gởi lời cảm ơn sâu sắc nhất đến gia đình và bạn bè, những
người đã luôn dành cho tôi tình yêu và niềm tin, để tôi có thể vững tâm trên hành
trình nhiều thách thức này.
NCS. Huỳnh Triệu Vỹ
ii
DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT
NGỮ TIẾNG ANH
AC
Artificial Cost
DUS
Database Utility Similarity
DSS
Database Structure Similarity
EHSHUI
EHSHAUI
GAbased
HAUIM
HAUIs
Mẫu xuất hiện giả mạo
Sự tương đồng của giá trị hữu ích
giữa CSDL gốc và CSDL sửa đổi
Sự tương đồng cấu trúc giữa CSDL
gốc và CSDL sửa đổi
Efficient algorithm for Hiding Thuật toán ẩn các tập mục hữu ích
Sensitive High Utility Itemsets
Efficient algorithm for Hiding
Sensitive High Average-Utility
Itemsets
cao nhạy cảm hiệu quả
Thuật toán ẩn các tập mục hữu ích
trung bình cao nhạy cảm hiệu quả
Thuật toán dựa trên giải thuật di
Genetic Algorithm-based
truyền
High Average-Utility Itemset Khai phá tập mục hữu ích trung
Mining
bình cao
High Average-Utility Itemset
Tập các tập mục hữu ích trung bình
cao
Hiding Sensitive Utility and
Ẩn tập mục hữu ích cao và phổ biến
Frequent Based on Lattice
nhạy cảm dựa trên giàn
HUM
High Utility Mining
Khai phá hữu ích cao
HUIM
High Utility Itemset Mining
Khai phá tập mục hữu ích cao
HUIs
High Utility Itemsets
Tập các tập mục hữu ích cao
HSUFIBL
HURIM
High Utility Rare Itemset Mining
Khai phá tập mục hữu ích cao hiếm
High Utility and Frequent
Khai phá tập mục hữu ích cao và phổ
Itemset Mining
biến
High Utility and Frequent
Tập các tập mục hữu ích cao và phổ
Itemsets
biến
HF
Hiding Failure
Mẫu nhạy cảm không ẩn được
IUS
Itemsets Utility Similarity
HUFIM
HUFIs
iii
Sự tương đồng của hữu ích tập mục
giữa CSDL gốc và CSDL sửa đổi
MC
PPDM
PPUM
SHUIs
SHAUIs
SHUFIs
TWU
UPGrowth
UP-Tree
Miss Cost
Mẫu bị mất
Privacy Preserving Data Min-
Bảo vệ tính riêng tư trong khai phá
ing
dữ liệu
Privacy
Preserving
Utility Bảo vệ tính riêng tư trong khai phá
Mining
hữu ích cao
Sensitive High Utility Itemsets
Tập các tập mục hữu ích cao nhạy
cảm
Sensitive High Average Utility Tập các tập mục hữu ích trung bình
Itemsets
cao nhạy cảm
Sensitive High Utility and Fre-
Tập các tập mục hữu ích cao và phổ
quent Itemsets
biến nhạy cảm
Transaction-Weighted-
Trọng số hữu ích giao tác
Utilization
Utility Pattern Growth
Mẫu hữu ích cao tăng trưởng
Utility Pattern Tree
Cây mẫu hữu ích cao
iv
DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT
NGỮ TIẾNG VIỆT
ATMTU
Ẩn tập mục hữu ích cao và phổ biến nhạy cảm tối ưu
CSDL
Cơ sở dữ liệu
KPDL
Khai phá dữ liệu
v
MỤC LỤC
Lời cam đoan
Lời cảm ơn
Danh mục các từ viết tắt và thuật ngữ tiếng Anh
Danh mục các từ viết tắt và thuật ngữ tiếng Việt
Mục lục
Danh mục bảng, biểu
Danh mục hình vẽ
TÓM TẮT LUẬN ÁN
MỞ ĐẦU
1 TỔNG QUAN VỀ KHAI PHÁ HỮU ÍCH CAO VÀ CHE GIẤU
i
ii
iii
v
vi
ix
x
xii
1
THÔNG TIN NHẠY CẢM TRONG KHAI PHÁ HỮU ÍCH CAO
TỪ CƠ SỞ DỮ LIỆU GIAO TÁC
1.1 Tổng quan về khai phá hữu ích cao từ CSDL giao tác . . . . . . . . . .
1.1.1 Cơ sơ lý thuyết của khai phá hữu ích cao . . . . . . . . . . . . .
1.1.2 Tổng quan tình hình nghiên cứu về khai phá hữu ích cao . . . .
1.2 Che giấu thông tin nhạy cảm trong khai phá hữu ích cao . . . . . . . .
1.2.1 Một số kỹ thuật che giấu mẫu nhạy cảm trong khai phá dữ liệu
1.2.2 Tổng quan về che giấu thông tin nhạy cảm trong khai phá hữu
7
7
7
12
16
17
ích cao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Các đơn vị đo lường trong đánh giá hiệu ứng phụ của thuật toán
18
che giấu thông tin nhạy cảm trong khai phá hữu ích cao . . . .
Ứng dụng lý thuyết giàn trong khai phá dữ liệu . . . . . . . . . . . . .
Mô tả các CSDL giao tác được sử dụng để chạy thực nghiệm của các
20
22
thuật toán trong luận án . . . . . . . . . . . . . . . . . . . . . . . . . .
Tổng kết Chương 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 CHE GIẤU THÔNG TIN NHẠY CẢM TRONG KHAI PHÁ HỮU
23
24
1.2.3
1.3
1.4
ÍCH CAO DỰA TRÊN KỸ THUẬT HEURISTIC
2.1 Quy trình che giấu thông tin nhạy cảm trong khai phá hữu ích cao từ
2.2
25
CSDL giao tác dựa trên kỹ thuật heuristic . . . . . . . . . . . . . . . .
Tình hình nghiên cứu về che giấu thông tin nhạy cảm trong khai phá
26
hữu ích cao từ CSDL giao tác dựa trên kỹ thuật heuristic . . . . . . . .
2.2.1 Ẩn tập mục hữu ích cao nhạy cảm . . . . . . . . . . . . . . . .
27
27
vi
2.2.2 Ẩn tập mục hữu ích cao và phổ biến nhạy cảm . . . . . . . . . .
2.2.3 Ẩn tập mục hữu ích trung bình cao nhạy cảm . . . . . . . . . .
2.2.4 Ẩn luật kết hợp hữu ích cao nhạy cảm . . . . . . . . . . . . . .
2.3 Thuật toán ẩn tập mục hữu ích cao nhạy cảm đề xuất . . . . . . . . .
2.3.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.2 Cơ sở lý thuyết của thuật toán đề xuất . . . . . . . . . . . . . .
2.3.3 Thuật toán đề xuất . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.4 Ví dụ minh họa thuật toán . . . . . . . . . . . . . . . . . . . . .
2.3.5 Độ phức tạp tính toán của thuật toán . . . . . . . . . . . . . .
2.3.6 Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . .
2.3.7 Nhận xét thuật toán đề xuất . . . . . . . . . . . . . . . . . . . .
2.4 Thuật toán ẩn tập mục hữu ích cao và phổ biến nhạy cảm đề xuất . . .
2.4.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.2 Cơ sở lý thuyết của thuật toán đề xuất . . . . . . . . . . . . . .
2.4.3 Thuật toán đề xuất . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.4 Ví dụ minh họa thuật toán . . . . . . . . . . . . . . . . . . . . .
2.4.5 Độ phức tạp tính toán của thuật toán . . . . . . . . . . . . . .
2.4.6 Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . .
2.4.7 Nhận xét thuật toán đề xuất . . . . . . . . . . . . . . . . . . . .
2.5 Thuật toán ẩn tập mục hữu ích trung bình cao nhạy cảm đề xuất . . .
2.5.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . .
2.5.2 Cơ sở lý thuyết của thuật toán đề xuất . . . . . . . . . . . . . .
2.5.3 Thuật toán đề xuất . . . . . . . . . . . . . . . . . . . . . . . . .
2.5.4 Ví dụ minh họa thuật toán . . . . . . . . . . . . . . . . . . . . .
2.5.5 Độ phức tạp tính toán của thuật toán . . . . . . . . . . . . . .
2.5.6 Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . .
2.5.7 Nhận xét thuật toán đề xuất . . . . . . . . . . . . . . . . . . . .
2.6 Thuật toán ẩn luật kết hợp hữu ích cao nhạy cảm đề xuất . . . . . . .
2.6.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . .
2.6.2 Cơ sở lý thuyết của thuật toán đề xuất . . . . . . . . . . . . . .
2.6.3 Thuật toán ẩn luật kết hợp hữu ích cao nhạy cảm đề xuất . . .
2.6.4 Ví dụ minh họa thuật toán . . . . . . . . . . . . . . . . . . . . .
2.6.5 Độ phức tạp tính toán của thuật toán . . . . . . . . . . . . . .
2.6.6 Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . .
2.6.7 Nhận xét thuật toán đề xuất . . . . . . . . . . . . . . . . . . . .
Tổng kết Chương 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 CHE GIẤU THÔNG TIN NHẠY CẢM TRONG KHAI PHÁ HỮU
29
30
30
30
31
31
34
38
39
40
45
46
46
47
52
54
56
56
59
60
60
60
63
64
66
66
68
70
70
71
72
73
75
76
76
77
ÍCH CAO DỰA TRÊN LÝ THUYẾT GIÀN
78
3.1 Lý thuyết giàn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.1.1 Quan hệ hai ngôi [14] . . . . . . . . . . . . . . . . . . . . . . . . 79
vii
3.2
3.1.2 Giàn sắp thứ tự (Lattice as orders) [14] . .
3.1.3 Giàn đại số (Lacttice as algebras) [14] . . .
3.1.4 Giàn của tập hợp [14] . . . . . . . . . . .
3.1.5 Giàn giao của tập phổ biến [37] . . . . . .
Che giấu thông tin nhạy cảm trong khai phá hữu
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
ích cao dựa
. . . . .
. . . . .
. . . . .
. . . . .
trên lý
81
82
84
85
thuyết Giàn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1 Giàn giao của tập các tập mục hữu ích cao và phổ biến . . . . .
3.2.2 Thuật toán ẩn tập mục hữu ích cao và phổ biến nhạy cảm dựa
85
86
trên Giàn giao đề xuất . . . . . . . . . . . .
3.2.3 Ví dụ minh họa thuật toán . . . . . . . . . .
3.2.4 Độ phức tạp tính toán của thuật toán . . .
3.2.5 Kết quả thực nghiệm . . . . . . . . . . . . .
3.2.6 Nhận xét thuật toán đề xuất . . . . . . . . .
Tổng kết Chương 3 . . . . . . . . . . . . . . . . . . . . .
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
DANH MỤC CÁC CÔNG TRÌNH CỦA TÁC GIẢ
Tài liệu tham khảo
viii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. 88
. 90
. 93
. 93
. 96
. 104
105
107
109
DANH MỤC BẢNG, BIỂU
1.1
1.2
1.3
CSDL Giao tác D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Hữu ích ngoại của CSDL D. . . . . . . . . . . . . . . . . . . . . . . . .
Mô tả CSDL thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . .
8
8
24
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
Tập HUIs khai thác từ CSDL D với ε = 40 . . . . . . . . . .
Mô tả CSDL chạy thực nghiệm của thuật toán EHSHUI . .
Tập HUFIs khai thác từ CSDL D với ε = 30 và δ = 30% . .
Mô tả tập các tập mục SHUFIs . . . . . . . . . . . . . . . .
Tập HAUIs khai thác từ CSDL D với β = 18 . . . . . . . . .
Mô tả tập HAUIs được khai thác bởi thuật toán HAUIMiner
Mô tả tập SHAUIs chạy thực nghiệm thuật toán EHSHA-UI
Tập HRs khai thác từ CSDL D với ε = 40 và µ = 70% . . .
Mô tả kết quả ẩn luật kết hợp hữu ích cao nhạy cảm . . . .
.
.
.
.
.
.
.
.
.
39
41
54
57
66
67
67
74
76
3.1
Các thông số của tập SHUFIs . . . . . . . . . . . . . . . . . . . . . . .
94
ix
. . .
. . .
. . .
. . .
. . .
[25]
. . .
. . .
. . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
DANH MỤC HÌNH VẼ
1.1
1.2
Sơ đồ che giấu mẫu nhạy cảm trong khai phá hữu ích cao . . . . . . . .
Mối quan hệ của ba loại hiệu ứng phụ khi thực hiện sửa đổi CSDL . . .
19
21
2.1
2.2
Sơ đồ biểu diễn quá trình ẩn tập mục hữu ích cao nhạy cảm . . . . . .
Tỷ lệ MC giữa các thuật toán khi thực nghiệm trên các CSDL với các
32
42
2.3
tập nhạy cảm khác nhau . . . . . . . . . . . . . . . . . . . . . . . . . .
Thời gian thực thi của các thuật toán khi thực nghiệm trên các CSDL
43
2.4
với các tập nhạy cảm khác nhau . . . . . . . . . . . . . . . . . . . . . .
Tỷ lệ DSS giữa các thuật toán khi thực nghiệm trên các CSDL với các
44
2.5
tập nhạy cảm khác nhau . . . . . . . . . . . . . . . . . . . . . . . . . .
Tỷ lệ DUS giữa các thuật toán khi thực nghiệm trên các CSDL với các
44
2.6
tập nhạy cảm khác nhau . . . . . . . . . . . . . . . . . . . . . . . . . .
Tỷ lệ IUS giữa các thuật toán khi thực nghiệm trên các CSDL với các
tập nhạy cảm khác nhau . . . . . . . . . . . . . . . . . . . . . . . . . .
2.7 Sơ đồ biểu diễn quá trình ẩn các tập mục SHUFIs . . . . . . . . . . . .
2.8 So sánh tỷ lệ MC giữa thuật toán HUFI và ATMTU . . . . . . . . . .
2.9 So sánh thời gian thực thi giữa thuật toán HUFI và ATMTU . . . . . .
2.10 So sánh tỷ lệ DSS giữa thuật toán HUFI và ATMTU . . . . . . . . . .
2.11 So sánh tỷ lệ DUS giữa thuật toán HUFI và ATMTU . . . . . . . . . .
2.12 Tỷ lệ IUS khi thực hiện ẩn các tập SHUFIs bởi thuật toán HUFI và
45
47
57
58
59
59
2.13
2.14
2.15
2.16
2.17
ATMTU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
So sánh tỷ lệ MC giữa thuật toán HHAUSI và EHSHA-UI . . . . .
So sánh thời gian thực thi giữa thuật toán HHAUSI và EHSHA-UI
So sánh tỷ lệ DSS giữa thuật toán HHAUSI và EHSHA-UI . . . . .
So sánh tỷ lệ DUS giữa thuật toán HHAUSI và EHSHA-UI . . . . .
Tỷ lệ IUS giữa thuật toán HHAUSI và EHSHA-UI . . . . . . . . . .
.
.
.
.
.
.
59
69
69
70
70
70
3.1
3.2
Giàn của tập hợp P = {a, b, c} . . . . . . . . . . . . . . . . . . . . . . .
Giàn L∩H của HUFIs trong Bảng 2.3 (bên trong mỗi nút là độ hỗ
84
3.3
3.4
3.5
trợ(%)/giá trị hữu ích của nút tương ứng) .
Tỷ lệ MC theo kích thước của tập nhạy cảm
Tỷ lệ MC theo ngưỡng hỗ trợ . . . . . . . .
Tỷ lệ MC theo ngưỡng hữu ích . . . . . . .
87
97
97
98
x
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.6
3.7
3.8
3.9
3.10
3.11
3.12
3.13
3.14
3.15
3.16
3.17
Tỷ lệ DSS theo kích thước của tập nhạy cảm . .
Tỷ lệ DSS theo ngưỡng hỗ trợ . . . . . . . . . .
Tỷ lệ DSS theo ngưỡng hữu ích . . . . . . . . .
Tỷ lệ DUS theo kích thước của tập nhạy cảm .
Tỷ lệ DUS theo ngưỡng hỗ trợ . . . . . . . . . .
Tỷ lệ DUS theo ngưỡng hữu ích . . . . . . . . .
Tỷ lệ IUS kích thước của tập nhạy cảm . . . . .
Tỷ lệ IUS theo ngưỡng hỗ trợ . . . . . . . . . .
Tỷ lệ IUS theo ngưỡng hữu ích . . . . . . . . .
Thời gian thực thi theo kích thước của tập nhạy
Thời gian thực thi theo ngưỡng hỗ trợ . . . . .
Thời gian thực thi theo ngưỡng hữu ích . . . . .
xi
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
cảm
. . .
. . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
98
99
99
100
100
101
101
102
102
103
103
104
TÓM TẮT LUẬN ÁN
Tên đề tài: Nghiên cứu và phát triển một số kỹ thuật che giấu thông tin nhạy
cảm trong khai phá hữu ích cao.
Chuyên ngành: Khoa học máy tính.
Mã số: 94.80.101
Tóm tắt: Luận án đã nghiên cứu và phát triển một số kỹ thuật che giấu thông
tin nhạy cảm trong khai phá hữu ích cao, kết quả đạt được gồm: Thứ nhất, dựa trên
kỹ thuật heuristic: Đề xuất thuật toán ẩn tập mục hữu ích cao nhạy cảm; thuật toán
ẩn tập mục hữu và phổ biến nhạy cảm; đề xuất mô hình và thuật toán ẩn tập mục
hữu ích trung bình cao nhạy cảm; mô hình và thuật toán ẩn luật kết hợp hữu ích cao
nhạy cảm. Thứ hai, đề xuất Giàn giao có ràng buộc của tập các tập mục hữu ích cao
và phổ biến để làm cơ sở xây dựng mô hình và đề xuất thuật toán ẩn tập mục hữu
ích cao và phổ biến nhạy cảm.
Từ khóa: Khai phá hữu ích cao, che giấu thông tin riêng tư trong khai phá hữu
ích cao, giàn giao.
ABSTRACT
Thesis title: Research and develop a number of techniques to hide sensitive
information in high utility mining.
Major: Computer science.
Code: 94.80.101
Abstract: The thesis has researched and developed a number of techniques to
hide sensitive information in high utility mining. Namely, include: First, based on
the heuristic technique propose the algorithm for hiding sensitive high utility itemset;
the algorithm for hiding sensitive high utility and frequent itemsets; propose a model
and algorithm for hiding sensitive high average-utility itemsets; and propose a model
and algorithm for hiding sensitive high utility association rules. Second, propose a
constrained intersection lattice of the high utility and frequent itemsets for proposing
the sensitive high utility and frequent itemset hiding algorithm.
Keywords: High utility mining, privacy-preserving utility mining, intersection
lattice.
xii
MỞ ĐẦU
Ngày nay, với sự phát triển nhanh chóng của ứng dụng công nghệ thông tin trong
hầu hết các lĩnh vực, lượng dữ liệu từ các hệ thống thông tin, ứng dụng ngày càng gia
tăng và được lưu trữ thành các kho dữ liệu lớn. Các phương pháp khai thác dữ liệu
truyền thống không còn đáp ứng đầy đủ những yêu cầu về phân tích, đánh giá, dự
đoán, dự báo dựa trên dữ liệu. Do đó, kỹ thuật phát hiện tri thức trong cơ sở dữ liệu
(CSDL) đã ra đời nhằm giải quyết bài toán khai phá dữ liệu đang được áp dụng một
cách rộng rãi trong nhiều lĩnh vực khác nhau của đời sống. Mục đích của khai phá dữ
liệu (KPDL) là khám phá tri thức nhằm tìm ra những mẫu mới, những thông tin tiềm
ẩn mang tính dự đoán chưa được biết đến, có khả năng mang lại lợi ích cho người sử
dụng, trong đó quan trọng nhất là tìm ra các mẫu chứa đựng những thông tin có thể
hỗ trợ ra quyết định tồn tại trong CSDL. Có nhiều kỹ thuật đã được nghiên cứu và
đề xuất trong KPDL. Một trong những kỹ thuật quan trọng được ứng dụng rộng rãi
là khai phá tập mục thường xuyên và luật kết hợp. Đây là một kỹ thuật quan trọng
nhằm phát hiện mối quan hệ giữa các mục dữ liệu trong CSDL. Việc xác định các
quan hệ này không phân biệt vai trò khác nhau cũng như không dựa vào các đặc tính
dữ liệu vốn có của các mục dữ liệu, mà chỉ dựa vào sự xuất hiện cùng lúc của chúng.
Trong khai phá tập mục thường xuyên vai trò của các mục xuất hiện trong các
giao tác là như nhau. Mỗi mục không thể xuất hiện nhiều hơn một lần trong mỗi giao
tác. Tập mục xuất hiện phổ biến hơn trong CSDL sẽ có ý nghĩa hơn đối với người
dùng. Như vậy, các tập mục thường xuyên khai thác được chỉ mang ngữ nghĩa thống
kê nên nó chỉ đáp ứng một phần nhu cầu ứng dụng thực tiễn. Chẳng hạn như nhà
kinh doanh quan tâm đến tần suất xuất hiện đồng thời của các mặt hàng trong cùng
một giao dịch của khách hàng thì có thể sử dụng kỹ thuật khai thác tập mục thường
xuyên để dự đoán xu thế mua sắm của khách hàng. Tuy nhiên, nhà quản lý có thể cần
đến những thông tin chi tiết hơn như lợi ích mang lại của một hoặc một nhóm mặt
hàng được khách hàng mua sắm cùng nhau trong một giao dịch. Khai phá tập mục
thường xuyên không đáp ứng được điều này. Chính vì điều này mà một khái niệm mới
ra đời, đó là Khai phá hữu ích cao, tức là có xét đến yếu tố hữu ích của mỗi mục trong
CSDL (ví dụ: số lượng, lợi nhuận của mỗi mặt hàng trong mỗi giao tác của CSDL).
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.
1
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,... Do đó, hiện nay có nhiều mô hình và kỹ thuật đang
được nghiên cứu để giải quyết vấn đề đặt ra, làm thế nào để cho phép thực hiện quá
trình KPDL trên các tập dữ liệu trong khi vẫn bảo vệ được các thông tin nhạy cảm.
Như vậy, để đảm bảo các thông tin nhạy cảm không bị khai thác khi CSDL được
chia sẻ ra bên ngoài, thuật toán che giấu thông tin nhạy cảm trong KPDL được áp
dụng để sửa dữ liệu nhằm loại bỏ các mẫu dữ liệu có thể suy luận ra các thông nhạy
cảm từ kết quả KPDL. Quá trình thực hiện che giấu thông tin nhạy cảm luôn gây ra
các hiệu ứng phụ. Hiệu ứng phụ được xác định là sự sai khác của bản thân dữ liệu và
kết quả KPDL của CSDL gốc so với CSDL sửa đổi. Như vậy, vấn đề chính cần giải
quyết trong bài toán che giấu thông tin nhạy cảm trong KPDL là đề xuất các thuật
toán che giấu được tất cả thông tin nhạy cảm nhưng giảm thiểu các hiệu ứng phụ.
Có nhiều phương pháp tiếp cận để giải quyết bài toán này: Theo tiếp cận heuristic để
thay đổi dữ liệu [2, 18, 42, 21] hoặc khóa dữ liệu [40, 36]; theo tiếp cận border-based
[43, 34]; theo tiếp cận exact [33, 10, 11],...
Để giải quyết bài toán che giấu thông tin nhạy cảm trong khai phá hữu ích cao,
năm 2010, Jieh-Shan Yeh và cộng sự [53] đề xuất phương pháp ẩn tập mục hữu ích
cao nhạy cảm theo hướng tiếp cận heuristic để sửa CSDL gốc với hai thuật toán được
đề xuất là HHUIF (Hiding High Utility Item First) và MSICF (Maximum Sensitive
Itemsets Conflict First). Dựa trên nền tảng này, nhiều thuật toán hiệu quả hơn cũng
được đề xuất [26, 23, 24, 28]. Nhìn chung, hướng tiếp cận của các thuật toán đã được
đề xuất đều dựa trên hướng tiếp cận heuristic để sửa CSDL nhằm tối ưu cục bộ. Tuy
nhiên, mỗi thuật toán đều tập trung đưa ra phương pháp tối ưu cục bộ cho một hoặc
một số tiêu chí cực tiểu hiệu ứng phụ, những tiêu chí khác của hiệu ứng phụ vẫn còn
cao. Chính vì vậy, việc tiếp tục nghiên cứu và đề xuất các thuật toán che giấu thông
tin nhạy cảm trong khai phá hữu ích cao hiệu quả hơn các thuật toán hiện tại là một
hướng nghiên cứu cần thiết.
Nhằm góp phần giải quyết một phần vấn đề nêu trên, nghiên cứu sinh đã chọn
đề tài "Nghiên cứu và phát triển một số kỹ thuật che giấu thông tin nhạy cảm trong
khai phá hữu ích cao" làm nội dung nghiên cứu luận án tiến sĩ kỹ thuật của mình.
2
1. Mục tiêu nghiên cứu
Luận án được thực hiện nhằm nghiên cứu giải quyết một phần các thách thức
trong giải quyết bài toán che giấu thông tin nhạy cảm trong khai phá hữu ích cao,
nhằm mục đích đảm bảo cho chủ sở hữu CSDL che giấu được thông tin nhạy cảm khi
thực hiện chia sẻ CSDL ra bên ngoài hoặc cho các đối tác. Cụ thể hơn, luận án nhằm
hướng đến hai mục tiêu chính sau:
- Thứ nhất, luận án nhằm nghiên cứu và đề xuất các thuật toán ẩn tập mục hữu
ích cao nhạy cảm và luật kết hợp hữu ích cao nhạy cảm dựa trên kỹ thuật heuristic.
- Thứ hai, luận án nhằm nghiên cứu và áp dụng lý thuyết Giàn để giảm hiệu ứng
phụ trong quá trình che giấu thông tin nhạy cảm trong khai phá hữu ích cao.
2. Đối tượng nghiên cứu
Đối tượng nghiên cứu chính của luận án này gồm:
- Về cơ sở dữ liệu cần thực hiện che giấu thông tin nhạy cảm: CSDL giao tác.
- Về thuật toán, gồm: Ẩn tập mục hữu ích cao nhạy cảm; ẩn tập mục hữu ích cao
và phổ biến nhạy cảm; ẩn tập mục hữu ích trung bình cao nhạy cảm; ẩn luật kết hợp
hữu ích cao nhạy cảm.
- Về cơ sở toán học: Giàn giao của tập hợp.
3. Phạm vi nghiên cứu
Phạm vi nghiên cứu của luận án gồm:
- Thứ nhất, nghiên cứu tổng quan về khai phá hữu ích cao và che giấu thông tin
nhạy cảm trong khai phá hữu ích cao từ CSDL giao tác dựa trên kỹ thuật heuristic,
từ đó xác định các hạn chế của các thuật toán hiện tại, các vấn đề hiện nay chưa được
đề xuất và giải quyết.
- Thứ hai, dựa trên các kết quả phân tích tổng quan khai phá hữu ích cao và che
giấu thông tin nhạy cảm trong khai phá hữu ích cao dựa trên kỹ thuật heuristic, đề
xuất một số thuật toán cải tiến:
+ Đề xuất thuật toán cải tiến ẩn tập mục hữu ích cao nhạy cảm và thuật toán ẩn
tập mục hữu ích cao và phổ biến nhạy cảm.
+ Đề xuất mô hình và thuật toán ẩn tập mục hữu ích trung bình cao nhạy cảm
và ẩn luật kết hợp hữu ích cao nhạy cảm.
- Thứ ba, áp dụng các tính chất của lý thuyết Giàn để chọn mục mục tiêu hiệu
3
quả nhằm giảm hiệu ứng phụ của quá trình sửa dữ liệu để ẩn thông tin nhạy cảm. Cụ
thể, xây dựng giàn giao có ràng buộc của tập các tập mục hữu ích cao và phổ biến,
từ giàn giao này xây dựng thuật toán chọn mục mục tiêu cho quá trình sửa CSDL để
ẩn tập mục hữu ích cao và phổ biến nhạy cảm nhằm giảm hiệu ứng phụ.
4. Ý nghĩa khoa học và thực tiễn của đề tài
Luận án nghiên cứu có ý nghĩa khoa học và giá trị thực tiễn, đóng góp mới trong
lĩnh vực nghiên cứu về che giấu thông tin nhạy cảm trong khai phá hữu ích cao, nhằm
góp phần giải quyết bài toán che giấu thông tin nhạy cảm của cá nhân và tổ chức
trong CSDL.
5. Cấu trúc của luận án:
Trên cơ sở các nhiệm vụ nghiên cứu nêu trên, để đạt mục tiêu đề ra và đảm bảo
tính logic và chỉnh thể của vấn đề nghiên cứu, ngoài phần mở đầu, phần kết luận và
hướng phát triển, luận án được cấu trúc gồm ba chương với mối quan hệ về kiến thức
giữa các chương như hình sau:
Chương 1: Tổng quan về khai phá hữu ích cao và che giấu thông tin
nhạy cảm trong khai phá hữu ích cao từ CSDL giao tác.
Chương này trình bày tổng quan về khai phá hữu ích cao và che giấu thông tin
nhạy cảm trong khai phá hữu ích cao để làm cơ sở đề xuất các thuật toán che giấu
4
thông tin nhạy cảm trong khai phá hữu ích cao dựa trên kỹ thuật heuristic ở chương
2. Ngoài ra, trong chương này cũng giới thiệu tổng quan về ứng dụng lý thuyết Giàn
trong KPDL, là một cơ sở toán học mà luận án này tập trung nghiên cứu để ứng dụng
vào việc tối ưu hóa thuật toán che giấu thông tin nhạy cảm trong khai phá hữu ích
cao được trình bày ở chương 3.
Chương 2: Che giấu thông tin nhạy cảm trong khai phá hữu ích cao
dựa trên kỹ thuật heuristic.
Phần đầu của chương trình bày về vấn đề che giấu thông tin nhạy cảm trong khai
phá hữu ích cao. Phần còn lại, tập trung vào trình bày các mô hình và thuật toán cải
tiến để che giấu thông tin nhạy cảm trong khai phá hữu ích cao, cụ thể: Thuật toán
ẩn tập mục hữu ích cao nhạy cảm; thuật toán ẩn tập mục hữu ích cao và phổ biến
nhạy cảm; thuật toán ẩn tập mục hữu ích trung bình cao nhạy cảm; thuật toán ẩn
luật kết hợp hữu ích cao nhạy cảm.
Chương 3: Che giấu thông tin nhạy cảm trong khai phá hữu ích cao
dựa trên lý thuyết Giàn.
Nội dung chính của chương này trình bày một phần nội dung của lý thuyết Giàn
có liên quan đến vấn đề che giấu thông tin nhạy cảm trong KPDL. Dựa trên cơ sở lý
thuyết Giàn, phần tiếp theo của chương xây dựng giàn giao có ràng buộc của tập các
tập mục hữu ích cao và phổ biến. Dựa trên giàn giao này, đề xuất thuật toán tìm mục
mục tiêu dựa trên Giàn giao có ràng buộc của tập các tập mục hữu ích cao và phổ
biến để cải tiến thuật toán ẩn tập mục hữu ích cao và phổ biến đã đề xuất ở chương
2.
Đóng góp chính của luận án
Luận án đã đạt được một số kết quả nghiên cứu và cũng là các đóng góp chính
sau đây:
1) Đề xuất một số thuật toán che giấu thông tin nhạy cảm trong khai phá hữu ích
cao dựa trên kỹ thuật heuristic, bao gồm:
- Thuật toán ẩn tập mục hữu ích cao nhạy cảm. Có ba kết quả nghiên cứu được
công bố trong kỷ yếu hội nghị và tạp chí: (1) Kỷ yếu Hội thảo quốc tế INISCOM, xuất
bản bởi Springer, năm 2018; (2) Tạp chí Intelligent Data Analysis (thuộc danh mục
ISI, Q3), số 24 năm 2020; (3) Kỷ yếu Hội nghị quốc gia lần thứ 15 về Nghiên cứu cơ
bản và ứng dụng Công nghệ thông tin (FAIR 15), năm 2022. Xem tài liệu số 4, 6 và
9 trong danh mục các công trình của tác giả;
5
- Thuật toán ẩn tập mục hữu ích cao và phổ biến nhạy cảm. Kết quả nghiên cứu
được công bố trong Kỷ yếu Hội nghị Quốc gia lần thứ 13 về Nghiên cứu cơ bản và
ứng dụng Công nghệ thông tin (FAIR 13), năm 2020. Xem tài liệu số 5 trong danh
mục các công trình của tác giả;
- Thuật toán ẩn tập mục hữu ích trung bình cao nhạy cảm. Có hai kết quả nghiên
cứu được công bố trong kỷ yếu hội nghị: (1) Kỷ yếu Hội thảo Quốc gia lần thứ 14 về
Một số vấn đề chọn lọc của Công nghệ thông tin và Truyền thông, năm 2018; (2) Kỷ
yếu Hội nghị Quốc gia lần thứ 14 về Nghiên cứu cơ bản và ứng dụng Công nghệ thông
tin (FAIR 14), năm 2021. Xem tài liệu số 3 và 7 trong danh mục các công trình của
tác giả;
- Thuật toán ẩn luật kết hợp hữu ích cao nhạy cảm. Có hai kết quả nghiên cứu
được công bố trong kỷ yếu hội nghị: (1) Kỷ yếu Hội nghị Quốc gia lần thứ 10 về
Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR 10), năm 2017; (2) Kỷ
yếu Hội thảo quốc tế MAPR, xuất bản bởi IEEE, năm 2018. Xem tài liệu số 1 và 2
trong danh mục các công trình của tác giả.
2) Đề 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
lý thuyết giàn. Cụ thể, 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 giàn giao có ràng buộc của tập các tập mục hữu ích cao và phổ biến. Kết
quả nghiên cứu đã được đăng trên tạp chí Cybernetics And Information Technologies
(thuộc danh mục Scopus, Q2), số 1 năm 2022. Xem tài liệu số 8 trong danh mục các
công trình của tác giả.
6
- Xem thêm -