Luận án Tiến sĩ Khoa học máy tính: Đề xuất một số giải pháp khai phá dữ liệu phân tán đảm bảo tính riêng tư

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:117

Thêm vào BST

Báo xấu

14
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án Tiến sĩ Khoa học máy tính "Đề xuất một số giải pháp khai phá dữ liệu phân tán đảm bảo tính riêng tư" trình bày các nội dung chính sau: Tổng quan về khai phá dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư; Các khái niệm cơ bản về mật mã và tính toán bảo mật nhiều thành viên; Đề xuất các giải pháp khai phá dữ liệu đảm bảo tính riêng tư cho mô hình dữ liệu phân tán dựa trên các giao thức tính toán bảo mật nhiều thành viên.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Khoa học máy tính: Đề xuất một số giải pháp khai phá dữ liệu phân tán đảm bảo tính riêng tư

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Nguyễn Văn Chung ĐỀ XUẤT MỘT SỐ GIẢI PHÁP KHAI PHÁ DỮ LIỆU PHÂN TÁN ĐẢM BẢO TÍNH RIÊNG TƯ LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - NĂM 2023
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Nguyễn Văn Chung ĐỀ XUẤT MỘT SỐ GIẢI PHÁP KHAI PHÁ DỮ LIỆU PHÂN TÁN ĐẢM BẢO TÍNH RIÊNG TƯ Chuyên ngành : Khoa học máy tính Mã số : 9480101 LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC 1. PGS.TS. Trần Đức Sự 2. TS. Nguyễn Văn Tảo THÁI NGUYÊN - NĂM 2023
i LỜI CAM ĐOAN Tác giả xin cam đoan các kết quả nghiên cứu và các kết luận trong luận án này là trung thực, khách quan. Những nội dung trong luận án là kết quả nghiên cứu của bản thân tác giả. Các kết quả viết chung với các tác giả khác đều được sự đồng ý của đồng tác giả trước khi đưa vào nôi dung luận án. Việc tham khảo các nguồn tài liệu được trích dẫn và ghi nguồn tài liệu tham khảo đúng quy định. Thái Nguyên, tháng 6 năm 2023 NCS Nguyễn Văn Chung
ii LỜI CẢM ƠN Luận án này được hoàn thành tại trường Đại học Công nghệ thông tin và Truyền thông - Đại học Thái Nguyên dưới sự hướng dẫn tận tình của thầy PGS. TS Trần Đức Sự và thầy TS Nguyễn Văn Tảo, tác giả xin bày tỏ lòng biết ơn sâu sắc nhất tới hai Thầy. Tác giả xin chân thành cảm ơn Ban lãnh đạo Trường Đại học Công nghệ thông tin và Truyền thông - Đại học Thái Nguyên, Ban Lãnh đạo khoa cùng toàn thể quý Thầy, Cô khoa Công nghệ thông tin đã quan tâm, giúp đỡ tác giả trong suốt thời gian nghiên cứu tại Trường. Tác giả xin chân thành cảm ơn Ban giám hiệu trường Cao đẳng Kinh tế - Kỹ thuật Vĩnh Phúc; cám ơn anh, chị, em và đồng nghiệp phòng Tổ chức - Hành chính, khoa Công nghệ thông tin đã tạo điều kiện, động viên giúp đỡ tác giả trong thời gian làm nghiên cứu sinh. Xin được cảm ơn anh, chị, em nghiên cứu sinh và bạn bè đồng nghiệp gần xa đã trao đổi, động viên, khích lệ tác giả trong quá trình học tập, nghiên cứu và làm luận án. Thái Nguyên, tháng 6 năm 2023 NCS Nguyễn Văn Chung
iii MỤC LỤC MỤC LỤC ...................................................................................................... i DANH MỤC CÁC TỪ VIẾT TẮT ............................................................. vi DANH MỤC BẢNG ................................................................................... vii DANH MỤC HÌNH VẼ ............................................................................. viii MỞ ĐẦU ....................................................................................................... 1 CHƯƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU TỪ NHIỀU NGUỒN CÓ ĐẢM BẢO TÍNH RIÊNG TƯ........................................................ 6 1.1. Giới thiệu chương ............................................................................... 6 1.2. Giới thiệu về khai phá dữ liệu có đảm bảo tính riêng tư.................... 6 1.3. Tổng quan về các phương pháp khai phá dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư ......................................................................................... 9 1.3.1. Khai phá dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư dựa trên phương pháp biến đổi ngẫu nhiên.................................................................. 9 1.3.2. Khai phá dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư dựa trên phương pháp ẩn danh ................................................................................... 10 1.3.3. Khai phá dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư dựa trên phương pháp tính toán bảo mật nhiều thành viên (SMC) ........................... 12 1.4. Xác định các vấn đề luận án cần giải quyết ..................................... 16 1.5. Kết luận chương ............................................................................... 17 CHƯƠNG 2. PHÁT TRIỂN PHƯƠNG PHÁP TÍNH TOÁN BẢO MẬT NHIỀU THÀNH VIÊN ....................................................................................... 18 2.1. Giới thiệu chương ............................................................................. 18 2.2. Một số khái niệm cơ bản .................................................................. 19 2.2.1. Nhóm cyclic và phần tử sinh ..................................................... 19 2.2.2. Bài toán logarithm rời rạc trong nhóm cyclic và các giả thuyết Diffie-Hellman ............................................................................................. 21 2.2.3. Phát biểu bài toán tính toán bảo mật nhiều thành viên ................... 23
iv 2.2.4. Các tính chất cơ bản của một giao thức tính toán bảo mật nhiều thành viên ............................................................................................................... 25 2.2.5. Mô hình tính toán ...................................................................... 25 2.2.6. Biến thể của hệ mật ElGamal .................................................... 26 2.2.7. Mô hình bán trung thực ............................................................. 27 2.3. Một số giao thức tính toán bảo mật nhiều thành viên phổ biến ....... 28 2.3.1. Giao thức tổng bảo mật ............................................................. 28 2.3.2. Giao thức tích vô hướng bảo mật .............................................. 31 2.3.3. Giao thức đánh giá đa thức bảo mật .......................................... 34 2.4. Phát triển một số một số giao thức tính toán bảo mật nhiều thành viên .... 36 2.4.1. Giao thức tổng bảo mật cải tiến [CT1] ...................................... 36 2.4.2. Giao thức tính tổng bảo mật tổng quát [CT2] ........................... 38 2.4.3. Giao thức tích ba véc tơ bảo mật ............................................... 45 2.4.4. Giao thức Bảo mật độ hỗ trợ ..................................................... 49 2.4.5. Giao thức Tính độ hỗ trợ bảo mật [CT5]................................... 61 2.5. Kết luận chương ............................................................................... 68 CHƯƠNG 3. ĐỀ XUẤT MỘT SỐ GIẢI PHÁP KHAI PHÁ DỮ LIỆU CÓ ĐẢM BẢO TÍNH RIÊNG TƯ DỰA TRÊN PHƯƠNG PHÁP TÍNH TOÁN BẢO MẬT NHIỀU THÀNH VIÊN ............................................................................. 70 3.1. Giới thiệu chương ............................................................................. 70 3.2. Xây dựng giải pháp phân lớp dữ liệu Naive Bayes có đảm bảo tính riêng tư cho mô hình dữ liệu phân tán ngang .................................................. 70 3.2.1. Giới thiệu ................................................................................... 70 3.2.2. Bài toán phân lớp Naïve Bayes trong mô hình dữ liệu phân tán ngang có ràng buộc tính riêng tư ................................................................. 73 3.2.3. Giao thức phân lớp Naive Bayes có đảm bảo tính riêng tư....... 75 3.2.4. Đánh giá giao thức đề xuất ........................................................ 76 3.3. Giải pháp khai phá luật kết hợp có đảm bảo tính riêng tư cho mô hình dữ liệu phân mảnh dọc trên ba thành viên....................................................... 81 3.3.1. Đặt vấn đề .................................................................................. 81
v 3.3.2. Bài toán khai phá luật kết hợp trong mô hình dữ liệu phân mảnh dọc trên ba thành viên .................................................................................. 83 3.3.3. Giao thức khai phá luật kết hợp đảm bảo tính riêng tư cho mô hình dữ liệu phân mảnh dọc trên ba thành viên ................................................... 84 3.3.4. Đánh giá giao thức đề xuất ........................................................ 85 3.4. Kết luận chương ............................................................................... 91 KẾT LUẬN ................................................................................................. 92 DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ ............ 94 TÀI LIỆU THAM KHẢO........................................................................... 95 PHỤ LỤC .................................................................................................. 105 A. Một số đoạn lệnh Python mẫu trong thực nghiệm của mục 3.2 ....... 105 B. Một số đoạn lệnh Python mẫu trong thực nghiệm của mục 3.3 ....... 106
vi DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt Tên đầy đủ CR-SSP Eﬃcient Collusion-Resisting Secure Sum Protocol DDH Decisional Diffie–Hellman DDM Distributed Data Mining GSSP General Secure Sum Protocol HE Homomorphic Encryption DM Data Mining PPDM Privacy-Preserving Data Mining SMC Secure Multyparty Computation SSL/TLS Secure Sockets Layer/ Transport Layer Security SSP Secure Sum Protocol OPE Oblivious polynomial evaluation
vii DANH MỤC BẢNG Bảng 2.1. So sánh giao thức GSSP với một vài giải pháp tổng bảo mật điển hình ...................................................................................................................... 43 Bảng 2.2. Kết quả thực nghiệm khả năng chống thông đồng của GSSP và CR-SSP................................................................................................................ 44 Bảng 2.3. Chi phí truyền thông ................................................................... 60 Bảng 2.4. Độ phức tạp tính toán của giao thức tính độ hỗ trợ bảo mật ...... 61 Bảng 2.5. Chi phí truyền thông ................................................................... 68 Bảng 2.6. Độ phức tạp tính toán của giao thức tính độ hỗ trợ bảo mật ...... 68 Bảng 3.1. Thông tin bộ dữ liệu thực nghiệm .............................................. 77 Bảng 3.2. Kết quả thực nghiệm chương trình huấn luyện mô hình Naïve Bayes có đảm bảo tính riêng tư trên bộ dữ liệu tin nhắn .................................... 80 Bảng 3.3. Các thông tin cơ bản của bộ dữ liệu thực nghiệm ...................... 87 Bảng 3.4. Kết quả thực nghiệm chương trình khai phá luật kết hợp có đảm bảo tính riêng tư trên bộ dữ liệu giỏ hàng ........................................................... 88 Bảng 3.5. Các luật được khai phá trên bộ dữ liệu giỏ hàng ........................ 89
viii DANH MỤC HÌNH VẼ Hình 1.1. Khai phá dữ liệu đảm bảo quyền riêng tư trên mô hình phân mảnh dữ liệu .................................................................................................................. 13 Hình 2.1. Mô hình toán toán bảo mật nhiều thành viên.............................. 24 Hình 2. 2. Giai đoạn 1, giao thức tổng bảo mật cải tiến có 6 thành viên.... 36 Hình 2.3. Mô hình giai đoạn 1 của giao thức tính tổng bí mật tổng quát ... 39 Hình 2.4. Mô hình giai đoạn 2 của giao thức tính tổng bí mật tổng quát ... 40 Hình 3.1. Ví dụ về mô hình dữ liệu phân tán ngang ................................... 72 Hình 3.2. Mô hình dữ liệu phân tán dọc ba thành viên............................... 83 Hình 3.3 Ví dụ về bộ dữ liệu mẫu ............................................................... 87
1 MỞ ĐẦU 1. Tính cấp thiết Ngày nay, sự phát triển của các hệ thống thông tin và ứng dụng web tạo ra lượng dữ liệu lớn. Mỗi ngày, hàng triệu giao dịch điện tử có thể được thực hiện, hay hàng tỷ bình luận/cảm xúc được bày tỏ trên các trang mạng xã hội. Bằng việc khai phá, phân tích những nguồn dữ liệu này, các tri thức hoặc thông tin có giá trị đã được tìm ra và đem lại nhiều lợi ích đáng kể cho những tổ chức, cá nhân [1], ví dụ như: ra quyết định kinh doanh, am hiểu sở thích của khách hàng, giảm chi phí vận hành. Trên thực tế, bất kỳ một tập dữ liệu nào cũng chứa những thông tin mang tính chất riêng tư, nhạy cảm như: bệnh lý của bệnh nhân, thu nhập của khách hàng, quan điểm chính trị của người dùng. Vấn đề này là cản trở lớn đối với hoạt động khai phá dữ liệu bởi một là, do lo ngại bị xâm phạm tới quyền riêng tư hoặc bị ràng buộc về chính sách bảo vệ quyền riêng tư nên bên sở hữu không sẵn sàng cung cấp dữ liệu thật cho bên khai phá; hai là, tiến trình khai phá dữ liệu có thể làm lộ ra ngoài những thông tin nhạy cảm của các tổ chức, cá nhân. Trước thách thức đó, nghiên cứu và phát triển các giải pháp khai phá tri thức và thông tin hữu ích tiềm ẩn trong các tập dữ liệu trong khi những thông tin riêng tư, nhạy cảm tồn tại bên trong dữ liệu vẫn được giữ an toàn và bí mật bởi các bên sở hữu trở thành một nhiệm vụ rất cần thiết và quan trọng, thu hút được nhiều sự quan tâm từ cộng đồng nghiên cứu [2]. Với những ý nghĩa như đã phân tích, luận án này lựa chọn đề tài “Đề xuất một số giải pháp khai phá dữ liệu phân tán đảm bảo tính riêng tư”. 2. Mục tiêu nghiên cứu Mục tiêu tổng quát của luận án này là nghiên cứu nâng cao tính an toàn và hiệu quả cho một số giải pháp khai phá dữ liệu đảm bảo tính riêng tư (PPDM) dựa trên tính toán bảo mật nhiều thành viên trong mô hình dữ liệu phân tán. Để hiện thực hóa mục tiêu này, luận án tập trung nghiên cứu ba vấn đề chính sau đây:
2 - Vấn đề thứ nhất là nghiên cứu, đánh giá các giải pháp khai phá dữ liệu đảm bảo tính riêng tư hiện có, đặc biệt là những giải pháp dựa trên lĩnh vực tính toán bảo mật nhiều thành viên. - Vấn đề thứ hai là phát triển một số kỹ thuật tính toán bảo mật nhiều thành viên và chứng minh các đề xuất mới hiệu quả hơn và có khả năng ứng dụng cao hơn các phương pháp đã có. - Vấn đề thứ ba là dựa trên các kỹ thuật tính toán bảo mật nhiều thành viên mới phát triển, đề xuất một số giao thức khai phá dữ liệu đảm bảo tính riêng tư cho cả hai mô hình dữ liệu phân mảnh theo chiều ngang và chiều dọc; đánh giá hiệu quả và tính riêng tư của các giải pháp mới. 3. Đối tượng và phạm vi nghiên cứu - Đối tượng nghiên cứu của luận án là các phương pháp khai phá dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư dựa trên phương pháp tính toán bảo mật nhiều thành viên. - Phạm vi nghiên cứu của luận án tập trung vào bài toán khai dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư. 4. Cách tiếp cận và phương pháp nghiên cứu - Cách tiếp cận: luận án tổng hợp, phân tích, đánh giá các công trình có liên quan tới vấn đề khai phá dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư, từ đó đề xuất giải pháp phù hợp để giải quyết các vấn đề đã đặt ra. - Phương pháp nghiên cứu của luận án là nghiên cứu lý thuyết và nghiên cứu thực nghiệm. Về nghiên cứu lý thuyết: các định lý, mệnh đề trong luận án được chứng minh chặt chẽ dựa vào các kiến thức cơ bản và các kết quả nghiên cứu đã công bố. Về nghiên cứu thực nghiệm: luận án thực hiện cài đặt các thuật toán, chạy thử nghiệm thuật toán, so sánh và đánh giá kết quả thực nghiệm so với kết quả nghiên cứu lý thuyết, từ đó kết luận tính đúng đắn của kết quả nghiên cứu.
3 5. Các nội dung nghiên cứu chính, đóng góp mới của luận án - Thứ nhất, luận án góp phần làm rõ bức tranh khái quát về lĩnh vực khai phá dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư, đồng thời phát hiện ra những khoảng trống nghiên cứu dựa trên việc đánh giá một số công trình nghiên cứu liên quan. - Thứ hai, luận án phát triển một số giao thức tính toán bảo mật nhiều thành viên. Các giao thức này cho phép các thành viên tham gia tính toán và nhận được kết quả tính toán chính xác mà không tiết lộ thông tin riêng tư của thành viên này cho mỗi thành viên khác: giao thức thứ nhất tính tổng bảo mật cải tiến quá trình gửi và nhận dữ liệu của mỗi thành viên với nhau bằng cách thực hiện ngẫu nhiên hóa về số lượng thành viên gửi và ngẫu nhiên về giá trị gửi; giao thức thứ hai tính tổng bảo mật tổng quát cho phép các nhà phát triển ứng dụng có thể tùy chọn các mức độ bảo vệ tính riêng tư và yêu cầu về tính hiệu quả phù hợp với ngữ cảnh bài toán ứng dụng; giao thức thứ ba cho phép tính toán tích vô hướng bảo mật trong mô hình ba thành viên dựa trên giao thức đánh giá đa thức bảo mật, và hai giao thức cuối cùng tính độ hỗ trợ bảo mật cũng cho mô hình tính toán ba thành viên. - Thứ ba, luận án đề xuất các giao thức an toàn và hiệu quả để khai phá dữ liệu đảm bảo tính riêng tư cho ngữ cảnh phân tán. Trong trường hợp dữ liệu phân mảnh ngang, luận án áp dụng giao thức tính tổng bảo mật tổng quát đã đề xuất nhằm nâng cao hiệu quả cho quá trình phân lớp dữ liệu Naive Bayes có đảm bảo tính riêng tư trên tập dữ liệu phân tán ngang. Các đánh giá về lý thuyết và thực nghiệm đã cho thấy thuật toán đề xuất bảo toàn được độ chính xác của kết quả phân lớp và thời gian thực thi tương đối thấp. Với dữ liệu phân mảnh dọc, dựa trên giao thức tính tích vô hướng bảo mật ba thành viên đã đề xuất, luận án phát triển kỹ thuật khai phá luật kết hợp đảm bảo tính riêng tư cho phép ba thành viên hợp tác mà không tiết lộ dữ liệu của mỗi thành viên cho các thành viên khác. Luận án chỉ ra giao thức đề xuất an toàn hơn các giao thức hiện có để chống lại sự thông đồng, mức độ thông đồng là hai thành viên không trung thực, nghĩa là trong ba thành viên tham gia tính toán thì hai thành viên thông đồng với nhau cũng không
4 thể tìm ra dữ liệu riêng tư của thành viên còn lại. Đồng thời, các thí nghiệm trên bộ dữ liệu thật cũng đã chứng minh khả năng ứng dụng thực tế của những giải pháp đề xuất. 6. Ý nghĩa khoa học và thực tiễn 6.1. Ý nghĩa khoa học - Đề xuất một số giao thức tính toán bảo mật nhiều thành viên an toàn và hiệu quả. - Đề xuất giải pháp phân lớp dữ liệu Naïve Bayes đảm bảo tính riêng tư cho mô hình dữ liệu phân tán ngang và giải pháp khai phá luật kết hợp đảm bảo tính riêng tư cho kịch bản dữ liệu phân tán dọc ba thành viên. 6.2. Ý nghĩa thực tiễn Kết quả nghiên cứu của luận án có thể được sử dụng làm cơ sở phát triển các ứng dụng khai phá dữ liệu đảm bảo tính riêng tư cho các kịch bản mô hình dữ liệu phân tán. Ngoài ra, các giao thức và giải pháp được đề xuất trong luận án có thể được kết hơp, áp dụng để tạo ra những giải pháp PPDM cho nhiều bài toán khai phá dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư khác nhau trong thực tế. 7. Bố cục luận án Bố cục của luận án gồm phần mở đầu và ba chương nội dung, phần cuối là kết luận của luận án tóm tắt những kết quả đạt được và những vấn đề cần nghiên cứu tiếp theo và danh mục các tài liệu tham khảo. - Chương 1 trình bày tổng quan về khai phá dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư. - Chương 2 trình bày các khái niệm cơ bản về mật mã và tính toán bảo mật nhiều thành viên; phân tích đánh giá một số giao thức tính toán bảo mật nhiều thành viên điển hình để từ đó phát triển các giao thức tính toán bảo mật nhiều thành viên, bao gồm: giao thức tính tổng bảo mật cải tiến, giao thức tính tổng bảo mật tổng quát, giao thức tính tích vô hướng bảo mật trong mô hình ba thành viên, hai giao thức tính độ hỗ trợ bảo mật cũng cho mô hình tính toán ba thành viên.
5 - Chương 3 đề xuất các giải pháp khai phá dữ liệu đảm bảo tính riêng tư cho mô hình dữ liệu phân tán dựa trên các giao thức tính toán bảo mật nhiều thành viên mới được trình bày trong chương 2. Trong trường hợp dữ liệu phân mảnh ngang: luận án đề xuất giao thức tính tổng bảo mật tổng quát nhằm nâng cao hiệu quả trong phân lớp dữ liệu Naive Bayes có đảm bảo tính riêng tư. Với dữ liệu phân mảnh dọc, luận án đề xuất giải pháp khai phá luật kết hợp đảm bảo tính riêng tư trong kịch bản ba thành viên hợp tác về mặt dữ liệu dựa trên giao thức tính tích vô hướng bảo mật của ba thành viên đã phát triển.
6 CHƯƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU TỪ NHIỀU NGUỒN CÓ ĐẢM BẢO TÍNH RIÊNG TƯ 1.1. Giới thiệu chương Trong chương này, luận án trình bày tổng quan về khai phá dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư, trong đó giới thiệu một số phương pháp phá dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư phổ biến: Phương pháp biến đổi ngẫu nhiên, phương pháp tính toán bảo mật nhiều thành viên, phương pháp ẩn danh dữ liệu. Cuối chương này, luận án đánh giá một số giải pháp khai phá luật kết hợp từ nhiều nguồn có đảm bảo có đảm bảo tính riêng tư và xác định các vấn đề luận án cần giải quyết. 1.2. Giới thiệu về khai phá dữ liệu có đảm bảo tính riêng tư Khai phá dữ liệu là một hướng nghiên cứu điển hình trong khoa học dữ liệu nhằm tìm ra thông tin hoặc tri thức từ một tập dữ liệu lớn [3]. Tuy nhiên, quá trình khai phá có thể tiết lộ thông tin nhạy cảm về các cá nhân/tổ chức và xâm phạm quyền riêng tư của họ. Với sự phát triển nhanh chóng của Internet, công nghệ lưu trữ dữ liệu và xử lý dữ liệu, khai phá dữ liệu có đảm bảo tính riêng tư (PPDM: Privacy Preserving Data Mining) đã trở thành một lĩnh vực nghiên cứu ngày càng quan trọng [4]. Mục đích chính của lĩnh vực PPDM là xây dựng các kỹ thuật khác nhau nhằm tìm kiếm ra các tri thức hoặc thông tin có giá trị trong khi dữ liệu và thông tin nhạy cảm vẫn được giữ riêng bởi các nhà sở hữu. Nói một cách khác, dữ liệu cần thiết cho các nhiệm vụ khai phá quan trọng vẫn được nắm giữ bởi một số thành viên mà không cần họ chia sẻ trực tiếp. Như đã đề cập, để đảm bảo tính riêng tư, dữ liệu vẫn được nắm giữ bởi các thành viên sở hữu nên lĩnh vực khai phá dữ liệu có đảm bảo tính riêng tư thường xuyên phải làm việc với mô hình dữ liệu phân tán (DDM: Distributed Data Mining). Các nghiên cứu về khai phá dữ liệu phân tán có đảm bảo quyền riêng tư liên quan đến ba vấn đề chính sau đây [5]. Thứ nhất, các tổ chức như các cơ quan chính phủ muốn công bố dữ liệu cho các nhà nghiên cứu hay cộng đồng. Tuy nhiên, do các ràng buộc khác nhau mà họ phải bảo vệ quyền riêng tư dữ liệu, ví
7 dụ dữ liệu riêng tư về sức khỏe và tài chính. Thứ hai, một nhóm các tổ chức mong muốn cùng nhau đạt được kết quả khai phá trên tập dữ liệu chung mà không tiết lộ tập dữ liệu riêng của mỗi bên. Thứ ba, một người khai phá dữ liệu muốn triển khai các mô hình khai phá dữ liệu từ dữ liệu người dùng, trong khi mỗi người vẫn giữ bí mật dữ liệu của họ. Do đó, PPDM hình thành ba nhóm bài toán sau: - Công bố dữ liệu đảm bảo tính riêng tư: mô hình của nhóm bài toán này chỉ bao gồm một chủ sở hữu dữ liệu đáng tin cậy, họ muốn chia sẻ dữ liệu của mình cho người khác hoặc cộng đồng nghiên cứu với mối quan tâm là làm thế nào để công bố dữ liệu hữu ích cho các ứng dụng khai phá dữ liệu mà vẫn bảo vệ được thông tin riêng tư trong bộ dữ liệu. Ví dụ, một số bệnh viện chia sẻ dữ liệu bệnh nhân để sử dụng cho các nghiên cứu y tế cần thiết [6]. Có nhiều bằng chứng cho thấy dữ liệu công bố có thể làm mất quyền riêng tư của cá nhân. Cuộc tấn công tái định danh như đã chỉ ra trong [7] rằng 87% dân số Mỹ có các đặc điểm cho phép chúng ta định danh duy nhất ra họ dựa trên một số thuộc tính công bố, cụ thể là mã zip, ngày sinh và giới tính. Công bố dữ liệu đảm bảo tính riêng tư đã nhận được sự quan tâm trong những năm gần đây nhằm mục đích ngăn chặn cuộc tấn công tái định danh, trong khi vẫn đảm bảo thông tin hữu ích cho các ứng dụng khai phá từ dữ liệu được công bố [8]. - Khai phá dữ liệu phân tán có đảm bảo tính riêng tư: bài toán này nhằm triển khai các thuật toán khai phá trên nhiều bộ dữ liệu khác nhau mà không cần truy cập dữ liệu gốc [9], [10], [11]. Khác với công bố dữ liệu đảm bảo tính riêng tư, nghiên cứu về khai phá dữ liệu phân tán đảm bảo tính riêng tư thường để giải quyết nhiệm vụ khai phá dữ liệu cụ thể. Mô hình nghiên cứu này bao gồm một số thành viên, mỗi thành viên có một bộ dữ liệu riêng. Mục đích là cho phép các thành viên cùng khai phá trên tập hợp các bộ dữ liệu riêng của họ để có được các mô hình khai phá dữ liệu mà không tiết lộ thông tin cá nhân cho các thành viên tham gia khác. Ở đây, cách phân mảnh dữ liệu đóng vai trò quan trọng, dữ liệu có thể được phân thành nhiều mảnh theo chiều dọc hoặc chiều ngang.
8  Phân mảnh dữ liệu theo chiều ngang: một bộ dữ liệu được phân mảnh thành nhiều phần, mỗi phần chứa một số bản ghi với cùng một bộ thuộc tính. Ví dụ cơ sở dữ liệu khách hàng được tập hợp từ các ngân hàng khác nhau.  Phân mảnh dữ liệu theo chiều dọc: một bộ dữ liệu được phân chia cho một số thành viên. Mỗi thành viên sở hữu một phần dọc của mỗi bản ghi trong cơ sở dữ liệu (giữ các bản ghi là tập con của tập thuộc tính). Ví dụ trong [12], Jaideep Vaidya và cộng sự minh họa về hai cơ sở dữ liệu phân mảnh dọc, một cơ sở dữ liệu chứa hồ sơ y tế, một cơ sở dữ liệu chứa thông tin điện thoại di động của cùng một nhóm người. Khai phá cơ sở dữ liệu dùng chung này có thể đạt được thông tin có giá trị, ví dụ như mối quan hệ giữa việc sử dụng điện thoại di động với pin Li/Ion dẫn đến khối u não ở bệnh nhân tiểu đường. - Khai phá dữ liệu người dùng có đảm bảo tính riêng tư: trong bài toán này, tồn tại một bên khảo sát một lượng lớn người dùng để tìm ra tri thức và thông tin hữu ích dựa trên dữ liệu người dùng trong khi các thuộc tính nhạy cảm của họ vẫn được giữ nguyên bí mật [13], [14]. Trong tình huống này, mỗi người dùng chỉ giữ một bản ghi dữ liệu, giống với cơ sở dữ liệu được phân mảnh theo chiều ngang, trong đó mỗi giao dịch được sở hữu bởi một người dùng khác nhau. Một ví dụ điển hình của bài toán này là Du và cộng sự [15] nghiên cứu xây dựng cây quyết định trên dữ liệu riêng tư. Trong nghiên cứu này, một người khai phá muốn thu thập dữ liệu từ người dùng và tạo cơ sở dữ liệu trung tâm, sau đó tiến hành khai phá dữ liệu trên cơ sở dữ liệu này. Họ đưa ra một cuộc khảo sát có chứa một số câu hỏi, mỗi người dùng được yêu cầu trả lời những câu hỏi đó, tuy nhiên có chứa một số câu hỏi nhạy cảm và người dùng có thể cảm thấy không thoải mái khi tiết lộ câu trả lời của mình. Vấn đề là làm thế nào người khai phá vẫn có thể đạt được kết quả khai phá dữ liệu mà không cần người dùng cung cấp trực tiếp câu trả lời của một số câu hỏi nhạy cảm. Một yêu cầu quan trọng nữa đối với các giải pháp PPDM cho bài toán này là không có bất kỳ tương tác nào giữa các cặp người dùng, mỗi người dùng chỉ giao tiếp với người khai phá dữ liệu.
9 1.3. Tổng quan về các phương pháp khai phá dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư Những năm gần đây, đã có rất nhiều nghiên cứu lý thuyết và ứng dụng của lĩnh vực khai phá dữ liệu đã được công bố trên các hội nghị và tạp chí hàng đầu quốc tế. Trong quá trình khai phá dữ liệu nói chung, các nhà khai phá thường phải sử dụng dữ liệu từ nhiều nguồn khác nhau, ví dụ các tổ chức tài chính muốn xây dựng mô hình phát hiện hành vi gian lận từ dữ liệu giao dịch do ngân hàng cung cấp và dữ liệu mua sắm trực tuyến do bên bán hàng cung cấp. Trong các trường hợp như vậy, dữ liệu thường được phân tán tại nơi mà các tổ chức sở hữu. Vì vậy, việc nghiên cứu và phát triển các giải pháp khai phá dữ liệu phân tán đảm bảo tính riêng tư (PPDDM) trở thành vấn đề trọng tâm và thách thức [4], [16], [17]. Về cơ bản, có ba hướng tiếp cận để xây dựng một giải pháp PPDM: ngẫu nhiên (randomization), ẩn danh (anonymity), và tính toán bảo mật nhiều thành viên (secure multi-party computation-SMC). 1.3.1. Khai phá dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư dựa trên phương pháp biến đổi ngẫu nhiên Ý tưởng cơ bản của phương pháp biến đổi ngẫu nhiên: cơ sở dữ liệu ban đầu chứa những thông tin riêng tư được biến đổi thành một cơ sở dữ liệu mới nhằm che giấu các thông tin riêng tư nhưng kết quả của quá trình khai phá dữ liệu trên cơ sở dữ liệu ban đầu và cơ sở dữ liệu sau khi đã được biến đổi là tương đồng hoặc độ chính xác có sự sai lệch không đáng kể. Trong phương pháp biến đổi ngẫu nhiên, hai kỹ thuật chính được sử dụng là biến đổi dữ liệu và ngẫu nhiên hóa dữ liệu. Biến đổi dữ liệu là kỹ thuật thay thế mỗi bản ghi trong tập dữ liệu gốc ban đầu bằng một bản ghi có cùng cấu trúc nhưng ẩn đi các giá trị thực [18], [19], [20], [21]. Ngẫu nhiên hóa dữ liệu là kỹ thuật thêm các giá trị nhiễu vào tập dữ liệu gốc nhưng vẫn đảm bảo phân bố dữ liệu không thay đổi [22], [23], [24], [25]. Trong những năm gần đây, rất nhiều công trình khoa học đã đề xuất những thuật toán hiệu quả dựa trên phương pháp biến đổi ngẫu nhiên cho bài toán PPDDM. Ví dụ điển hình là thuật toán của Agrawal và Srikant [26], đã rời rạc
10 hóa các thuộc tính trong dữ liệu căn cứ trên việc chia khoảng và đề xuất giải pháp PPDM cho kỹ thuật phân lớp Bayes. Trong [22], Agrawal và cộng sự đã phát triển một cách tiếp cận dựa trên tối đa hóa kỳ vọng đồng thời cũng đưa ra định nghĩa chính xác hơn về quyền riêng tư và thuật toán cải tiến. Polat và cộng sự [27] đề xuất một phương pháp lọc cộng tác đảm bảo quyền riêng tư bằng kỹ thuật ngẫu nhiên. Chaytor và Wang [28] đã đưa ra thuật toán biến đổi ngẫu nhiên dữ liệu nhạy cảm, được gọi là ngẫu nhiên hóa miền nhỏ. Mặc dù phương pháp biến đổi ngẫu nhiên khá hiệu quả nhưng các giải pháp PPDM theo hướng tiếp cận này phải đánh đổi giữa độ chính xác về kết quả của bài toán khai phá dữ liệu và tính riêng tư [10], [29]. Nếu chúng ta yêu cầu tính riêng tư cao hơn đối với bài toán khai phá dữ liệu thì độ chính xác sẽ giảm xuống và ngược lại. Kargupta và cộng sự [30] phân tích sự riêng tư của một số kỹ thuật ngẫu nhiên và cho thấy nhiều trường hợp tiết lộ thông tin riêng tư. Evmievski và cộng sự [31] chỉ ra sự hạn chế của kỹ thuật biến đổi dữ liệu trong khai phá dữ liệu đảm bảo quyền riêng tư. Huang và cộng sự [32] đã chỉ ra trong một số kiểu dữ liệu, việc thêm nhiễu và chuyển đổi dữ liệu không đảm bảo được quyền riêng tư. Sheela và Vijayalakshmi [33] cũng chỉ ra rằng phương pháp ngẫu nhiên làm ảnh hưởng đến kết quả khai phá dữ liệu nếu chúng ta cố gắng che giấu thông tin riêng tư bằng cách bổ sung các thông tin gây nhiễu vào tập dữ liệu gốc. 1.3.2. Khai phá dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư dựa trên phương pháp ẩn danh Một phương pháp đảm bảo quyền riêng tư cũng tương đối phổ biến là ẩn danh (anonymity). Khác với kỹ thuật biến đổi ngẫu nhiên, ẩn danh yêu cầu dữ liệu công bố có số lượng thuộc tính nhất định, khiến những kẻ tấn công không tìm thấy thuộc tính cụ thể bằng thông tin riêng tư và ngăn chặn thông tin riêng tư cá nhân bị rò rỉ. Do vậy, phương pháp này có khả năng bảo vệ sự riêng tư của dữ liệu trong một số trường hợp.