Thạc Sĩ khai thác luật kết hợp bảo đảm tính riêng tư trên dữ liệu phân tán ngang

KHAI THÁC LUẬT KẾT HỢP BẢO ĐẢM TÍNH RIÊNG TƯ TRÊN DỮ LIỆU PHÂN TÁN NGANG
MỤC LỤC
Trang phụ bìa
Lời cảm ơn
Mục lục i
Danh mục các ký hiệu, các chữ viết tắt iii
Danh mục các bảng iv
Danh mục các hình vẽ, ñồ thị v
Chương 1. TỔNG QUAN . 1
1.1. Giới thiệu: . 1
1.2. Khai thác dữ liệu bảo ñảm tính riêng tư: 4
1.3. KTDL phân tán bảo ñảm tính riêng tư: . 6
1.3.1. KTDL phân tán ảnh hưởng ñến tính riêng tư như thế nào ? . 6
1.3.2. Các hướng giải quyết: 7
1.3.3. Các trường hợp tấn công: 8
1.3.4. Tính toán ña thành viên an toàn: 10
1.4. Khai thác luật kết hợp bảo ñảm tính riêng tư trên dữ liệu phân tán ngang:
11
Chương 2. CÔNG TRÌNH LIÊN QUAN . 14
2.1. Giới thiệu chung: 14
2.2. FI (Frequent itemset): 14
2.3. MFI (Maximal Frequent Itemset): . 21
2.4. Apriori: 25
2.5. FPTree (Frequent Pattern Tree): 26
2.6. Ma trận tương tự: 26
2.7. Luật kết hợp số lượng: . 26
Chương 3. KIẾN THỨC NỀN TẢNG 28
3.1. Itemset tối ñại: . 28
3.2. Thuật toán GENMAX: 28
3.3. Mã hoá công khai ñồng hình Paillier: . 32
3.3.1. Mã hoá công khai ñồng hình: 32
3.3.2. Mã hoá Paillier: . 33


ii
3.3.3. Mã hoá Paillier cải tiến: 36
Chương 4. GIAO THỨC ĐỀ XUẤT 38
4.1. Đặt vấn ñề: . 38
4.2. Các bước thực hiện: 39
4.3. Đánh giá: 43
4.3.1. Tính riêng tư: . 43
4.3.2. Độ chính xác: . 43
4.3.3. Hiệu năng: 45
4.3.4. So sánh với các giao thức khác: 47
4.4. Kết luận: . 48
4.5. Chương trình cài ñặt: 49
4.5.1. Giới thiệu: 49
4.5.2. Kết quả thực nghiệm: . 51
4.5.3. Đánh giá kết quả: . 54
4.6. Tổng kết: . 54
4.6.1. Kết luận: 54
4.6.2. Hướng phát triển: . 55
TÀI LIỆU THAM KHẢO 56
Chương 1. TỔNG QUAN
Với lượng dữ liệu gia tăng nhanh chóng thì KTDL là một công cụ hữu ích
ñể rút trích những thông tin có ích từ dữ liệu, tuy nhiên trong các lĩnh vực ñặc thù
như y khoa, bảo hiểm, ngân hàng, có chứa dữ liệu và thông tin nhạy cảm, không
cho phép tiết lộ dữ liệu và thông tin nhạy cảm này do ñó gây khó khăn cho quá trình
khai thác, từ ñó ñòi hỏi cần có các nghiên cứu ñể có thể khai thác dữ liệu nhưng
không tiết lộ tính riêng tư của dữ liệu.
Luận văn tập trung tìm hiểu về khai thác luật kết hợp bảo ñảm tính riêng tư
trên dữ liệu phân tán ngang, trong chương này giới thiệu về tính riêng tư trong khai
thác dữ liệu (KTDL) và tính riêng tư trong khai thác dữ liệu phân tán, phân tích
những nguyên nhân làm ảnh hưởng ñến tính riêng tư, trình bày các phương pháp
bảo ñảm tính riêng cùng với ưu ñiểm và nhược ñiểm của các phương pháp này.
Phần tiếp theo trình bày về các giao thức tính toàn ña thành viên an toàn và áp dụng
các giao thức này trong KTDL phân tán bảo ñảm tính riêng tư. Phần cuối ñi sâu
phân tích tính riêng tư trong khai thác luật kết hợp trên dữ liệu phân tán ngang, xác
ñịnh thông tin cần phải bảo ñảm tính riêng tư và ñưa ra các phương pháp ñể giải
quyết.
1.1. Giới thiệu:
Khai thác dữ liệu (KTDL) là một kỹ thuật ñể rút trích tri thức từ lượng dữ
liệu lớn và ñược xem là giai ñoạn chính trong quá trình khám phá tri thức. KTDL
ñược ứng dụng trong nhiều lĩnh vực như tiếp thị, kinh doanh, khám phá khoa học,
công nghệ sinh học, tìm kiếm trên Internet, giải trí ña phương tiện,
Các ứng dụng gần ñây của KTDL cho việc thu thập và phân tích dữ liệu
trong các ứng dụng liên quan ñến bảo mật, y học, kinh doanh, ñã ñặt ra mối
quan tâm về vấn ñề tính riêng tư, khi áp dụng các kỹ thuật KTDL có thể làm tiết lộ
dữ liệu và thông tin nhạy cảm.


2
Tính riêng tư: dữ liệu nhạy cảm như ñịnh danh, tên, ñịa chỉ, ñiện thoại, thu
nhập, của các cá nhân, tổ chức, và tri thức nhạy cảm ñược khai thác từ cơ sở dữ
liệu thông qua các thuật toán khai thác dữ liệu. Các thông tin này là bí mật kinh
doanh, những thông tin gây bất lợi cho cá nhân, tổ chức, hay do quy ñịnh của
pháp luật nên không thể tiết lộ ra [1][2][4]. Một số ví dụ:
Ví dụ 1, trung tâm kiểm soát dịch bệnh (CDC, Mỹ) muốn khai thác hồ sơ sức
khỏe ñể tìm hiểu về vi khuẩn kháng thuốc kháng sinh từ ñó làm giảm gia tăng của
vi khuẩn này. Các công ty bảo hiểm có thông tin dịch bệnh liên quan như ñơn
thuốc, thông tin bệnh nhân. CDC muốn khai thác các luật kết hợp có dạng X
Y,
tìm ra luật Augmentin & Mùa hè
Nhiễm bệnh & Mùa thu, nghĩa là, người dùng
Augmentin trong mùa hè có thể bị nhiễm bệnh tái phát trong mùa thu. Các công ty
bảo hiểm ngoài việc bảo ñảm tính riêng tư của bệnh án, họ không muốn chia sẻ
thông tin khai thác ñược này. Nếu người dùng bảo hiểm biết ñược thông tin này họ
có thể cải thiện chính sách chăm sóc bệnh nhân, ñiều này có thể gây thiệt hại cho
các công ty bảo hiểm. Với những rủi ro này các công ty bảo hiểm sẽ không muốn
cung cấp dữ liệu cho CDC [4][7].
Ví dụ 2, một nhóm công ty kinh doanh muốn xác ñịnh các mẫu tốt nhất ñể
giúp ñỡ các thành viên nhưng một số mẫu là bí mật kinh doanh. Vậy làm thế nào ñể
có thể cung cấp các kết quả cho các thành viên nhưng vẫn bảo ñảm bí mật ? Ví dụ:
việc sản xuất sử dụng chất hóa học ñược cung cấp từ nhà cung cấp X có tỷ lệ thất
bại cao, quy trình sản xuất Y cho tỷ lệ thành công thấp [26].
Ví dụ 3, các công ty ña quốc gia muốn khai thác dữ liệu của các công ty ñể
có ñược kết quả toàn cục, nhưng luật pháp của các quốc gia có thể ngăn chặn việc
chia sẻ dữ liệu [26].
Ví dụ 4, KTDL nghiên cứu về dân cư nhưng người dân không muốn ñể lộ
thông tin cá nhân [26].
Ví dụ 5, người sử dụng KTDL trên một CSDL mà họ không sở hữu, họ
không muốn ñể lộ ra các câu truy vấn của mình với người quản trị CSDL [2].


3
Dó ñó cần có giải pháp ñể có thể khai thác dữ liệu nhưng vẫn bảo ñảm tính
riêng tư. Với các ứng dụng sử dụng CSDL phân tán có kích thước dữ liệu lớn, hạn
chế về chi phí, tốc ñộ truyền thông và tính riêng tư của dữ liệu nên không thể tập
trung dữ liệu, từ ñó cần ñưa ra giải pháp bảo ñảm tính riêng tư trong khai thác dữ
liệu phân tán. Giải pháp cần phải phù hợp loại dữ liệu, nhu cầu về tính riêng tư, hạ
tầng mạng, yêu cầu về ñộ chính xác của kết quả khai thác ñể có thể ứng dụng ñược
trong thực tế.
Khai thác luật kết hợp ñược sử dụng phổ biến, ứng dụng ñể phân tích giỏ
mua hàng, phân tích chiến lược bán hàng, web log, . Đã có nhiều giao thức ñề
xuất ñể khai thác luật kết hợp cho dữ liệu tập trung và phân tán, tuy nhiên các giao
thức vẫn còn hạn chế về tính riêng tư và chi phí tính toán và truyền thông.
Luận văn ñề xuất giao thức khai luật kết hợp bảo ñảm tính riêng tư trên dữ
liệu phân tán ngang có tính riêng tư cao và chi phí truyền thông thấp, giao thức
cải tiến giao thức do Mahmoud Hussein và các ñồng nghiệp ñề xuất năm 2008 trong
[14], giao thức ñề xuất cải tiến bước tìm tập ứng viên bằng cách sử dụng hướng tiếp
cận sử dụng itemset tối ñại cục bộ (MFI) và cải tiến bước tính ñộ hỗ trợ toàn cục
bằng cách sử dụng mã hóa Paillier, từ ñó cho tính riêng tư cao hơn và chi phí truyền
thông thấp hơn. Sử dụng bộ dữ liệu thực tế ñể cài ñặt thử nghiệm giao thức và cho
kết quả khai thác hoàn toàn chính xác.
Nội dung luận văn gồm 4 chương:
Chương 1: Tổng quan - trình bày về tính riêng tư và các phương pháp ñể bảo
ñảm tính riêng tư cho dữ liệu tập trung và dữ liệu phân tán, cuối chương trình phân
tích các vấn ñề trong khai thác luật kết hợp bảo ñảm tính riêng tư trên dữ liệu phân
tán ngang.
Chương 2: Các công trình liên quan - trình bày về các giao thức ñã ñề xuất
ñể khai thác luật kết hợp bảo ñảm tính riêng tư trên dữ liệu phân tán ngang.
Chương 3: Kiến thức nền tảng - trình bày nội dung liên quan ñến giao thức
ñề xuất như itemset phổ biến tối ñại, thuật toán GenMax, mã hoá ñồng hình Paillier.


4
Chương 4: Giao thức ñề xuất - trình bày về những cải tiến của giao thức ñề
xuất, ñánh giá tính riêng tư và hiệu năng của giao thức, so sánh giao thức ñề xuất
với các giao thức trước ñó, tiếp theo là kết quả cài ñặt với dữ liệu thực tế, kết luận
và hướng phát triển.