Thạc Sĩ Khai thác dữ liệu phân tán bảo toàn tính riêng tư

MỤC LỤC
LỜI CAM ĐOAN 1
LỜI CÁM ƠN 2
MỤC LỤC 3
DANH MỤC CÁC HÌNH .5
DANH MỤC CÁC BẢNG 7
DANH MỤC TỪ VIẾT TẮT 8
PHẦN MỞ ĐẦU 9
CHƯƠNG 1 Một số khái niệm về cơ sở dữ liệu phân tán, khai thác dữ liệu và
bảo toàn tính riêng tư .19
1.1. Cơ sở dữ liệu phân tán 19
1.1.1. Khái niệm cơ sở dữ liệu phân tán 19
1.1.2. Cơ sở dữ liệu phân tán ngang 19
1.1.3. Cơ sở dữ liệu phân tán dọc 21
1.2. Khai thác dữ liệu .23
1.2.1. Khái niệm khai thác dữ liệu .23
1.2.2. Một số thuật toán khai thác dữ liệu 24
1.3. Bảo đảm tính riêng tư .31
1.3.1. Khái niệm .31
1.3.2. Phân loại các phương pháp PPDM 32
1.3.3. Đánh giá một thuật toán PPDM .34
1.4. Một số phương pháp giấu dữ liệu .35
1.4.1. Xáo trộn .35
1.4.2. Ngăn chặn 36
1.4.3. Gom / trộn 36
1.4.4. Đổi chỗ .36
1.4.5. Lấy mẫu .37
1.4.6. Ứng dụng lý thuyết giàn giao 41
1.5. Một số kỹ thuật khai thác dữ liệu bảo đảm tính riêng tư 49
1.5.1. Kỹ thuật chỉnh sửa dữ liệu trong cơ sở dữ liệu nhị phân .49
1.5.2. Kỹ thuật thay giá trị dữ liệu thật bằng giá trị không xác định .53
1.5.3. Phương pháp tái tạo .56
1.6. Kết chương .58
CHƯƠNG 2 Khai thác dữ liệu trên CSDL phân tán .60
2.1. Giới thiệu 604
2.2. Khai thác trên cơ sở dữ liệu phân tán dọc 60
2.2.1. Cách thực hiện .60
2.2.2. Thuật toán khai thác trên CSDL phân tán dọc với phép kết ngoại 62
2.2.3. Thuật toán khai thác CSDLPT dọc với phép kết ngoại hai chiều 66
2.2.4. Thuật toán khai thác CSDLPT dọc bằng phép kết tự nhiên 68
2.3. Khai thác trên cơ sở dữ liệu phân tán ngang 73
2.3.1. Cách thực hiện .73
2.3.2. Nhận xét phương pháp .75
2.4. Khai thác song song tập phổ biến trên CSDL phân tán .75
2.4.1. Đặt vấn đề 75
2.4.2. Mô hình khai thác 76
2.4.3. Thuật toán khai thác tập phổ biến trên Master .78
2.5. Khai thác tập mục có lợi ích cao 81
2.5.1. Đặt vấn đề 81
2.5.2. Khai thác tập mục có lợi ích cao 81
2.6. Kết chương .86
CHƯƠNG 3 Khai thác dữ liệu phân tán bảo đảm tính riêng tư 87
3.1. Giới thiệu chương .87
3.2. Khai thác CSDL phân tán dọc bảo đảm tính riêng tư 87
3.2.1. Đặt vấn đề 87
3.2.2. Thuật toán 88
3.2.3. Minh họa thuật toán: 89
3.3. Khai thác CSDL phân tán ngang bảo đảm tính riêng tư 94
3.3.1. Đặt vấn đề 94
3.3.2. Một số công cụ tính toán đa bên an toàn. 95
3.3.3. Giải thuật khai thác tập phổ biến đảm bảo riêng tư và chống thông đồng trên dữ
liệu phân tán ngang. .96
3.4. Giao thức khai thác CSDL phân tán ngang bảo đảm tính riêng tư 107
3.4.1. Đặt vấn đề 107
3.4.2. Cơ sở lý thuyết .108
3.4.3. Giao thức khai thác 109
3.4.4. Đánh giá giao thức .113
3.4.5. Thực nghiệm giao thức 113
3.5. Kết chương .114
PHẦN KẾT LUẬN 116
DANH MỤC CÔNG TRÌNH ĐÃ CÔNG BỐ .120
TÀI LIỆU THAM KHẢO 1215
DANH MỤC CÁC HÌNH
Hình 1.1. Thuật toán IT-Tree phát sinh tập phổ biến thỏa ngưỡng minsup 30
Hình 1.2. Kết quả khai thác với ngưỡng minsup=50% .31
Hình 1.3. Đồ thị dàn các tập mục thường xuyên 43
Hình 1.4. Gian giao đầy đủ của tập Poset (ABE) .44
Hình 1.5. Thuật toán Itemhide- Ẩn tập mục nhạy cảm .46
Hình 1.6. Thuật toán 1a .51
Hình 1.7. Thuật toán 1b .51
Hình 1.8. Thuật toán 2a .52
Hình 1.9. Thuật toán 2b .52
Hình 2.1. Mô hình hoạt động khai thác luật trên CSDL phân tán 60
Hình 2.2. Thuật toán Eclat_Distribute_Left_Join .63
Hình 2.3. Biểu diễn các mục đơn của DB1 .65
Hình 2.4. Biểu diễn các mục đơn của DB1 và DB2 .65
Hình 2.5. Kết quả khai thác trên CSDL phân tán với phép kết Left-join .66
Hình 2.6. Thuật toán Eclat_Distribut_Full_Join .67
Hình 2.7. Kết quả khai thác trên CSDLPT dọc với phép kết ngoại hai chiều .68
Hình 2.8. Thuật toán phát sinh tập phổ biến thỏa ngưỡng minsup .69
Hình 2.9. Cây biểu diễn các mục đơn của DB1 và DB2 71
Hình 2.10. Cây biểu diễn khai thác tập phổ biến trên CSDL phân tán .71
Hình 2.11. Mô hình tổng quát khai thác trên CSDL phân tán ngang .77
Hình 2.12. Trao đổi thông tin và khai thác tâp phổ biến giữa Master và Slaver 77
Hình 2.13. Kết quả khai thác từ Slave 1 theo thuật toán Eclat .78
Hình 2.14. Kết quả khai thác từ Slave 2 theo thuật toán Eclat .78
Hình 2.15. Thuật toán PEclat 79
Hình 2.16. Kết quả của PEClat với minsup=50% .80
Hình 2.17. Cây WIT-Tree .82
Hình 2.18. Thuật toán TWU-Mining 83
Hình 2.19. Minh họa thuật toán TWU-Mining .84
Hình 3.1. Thuật toán phát sinh tập phổ biến .88
Hình 3.2. Sơ đồ hoạt động của thuật toán .89
Hình 3.3. Kết quả tạo ra lớp tương đương [] .91
Hình 3.4. Kết quả khai thác trên CSDL phân tán dọc .91
Hình 3.5. Thủ tục Create_Fitree 98
Hình 3.6. Thủ tục Secure_Support(X) 98
Hình 3.7. Thủ tục Extend_Fitree& Upper_Bound 996
Hình 3.8. Thủ tục Upper_Bound .100
Hình 3.9. Kết quả FITree sau khi xử lý nút gốc 101
Hình 3.10. Kết quả FITree sau khi xử lý nút A .102
Hình 3.11. Sự phụ thuộc thời gian vào số lượng máy trên CSDL Accident 107
Hình 3.12. Sự phụ thuộc thời gian vào số lượng máy trên CSDL bảo hiểm 107
Hình 3.13. Giao thức đảm bảo tính riêng tư 110
Hình 3.14. CSDL tập trung và CSDL phân tán .112
Hình 3.15. Các bên tính độ hỗ trợ cục bộ 112
Hình 3.16. Tính độ hỗ trợ toàn cục và tập phổ biến toàn cục 112
Hình 3.17. So sánh tổng chi phí của GTDX và GT M.Hussein 114