Một số kỹ thuật khai phá luật kết hợp có bảo đảm tính riêng tư trong các tập gia

1 ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CNTT VÀ TRUYỀN THÔNG ------------------ o0o------------------ Họ và tên tác giả: Nguyễn Thị Thùy MỘT SỐ KỸ THUẬT KHAI PHÁ LUẬT KẾT HỢP CÓ BẢO ĐẢM TÍNH RIÊNG TƢ TRONG CÁC TẬP GIAO DỊCH PHÂN TÁN NGANG LUẬN VĂN THẠC SỸ KHOA HỌC Thái Nguyên – 2014 Số hóa bởi Trung tâm Học liệu http://www.vn/ 2 ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CNTT VÀ TRUYỀN THÔNG Họ và tên tác giả: Nguyễn Thị Thùy MỘT SỐ KỸ THUẬT KHAI PHÁ LUẬT KẾT HỢP CÓ BẢO ĐẢM TÍNH RIÊNG TƢ TRONG CÁC TẬP GIAO DỊCH PHÂN TÁN NGANG Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 LUẬN VĂN THẠC SỸ KHOA HỌC NGƢỜI HƢỚNG DẪN KHOA HỌC TS. TRẦN ĐỨC SỰ Thái Nguyên - 2014 Số hóa bởi Trung tâm Học liệu http://www.vn/ 3 LỜI CAM ĐOAN Những kết quả nghiên cứu được trình bày trong luận văn là hoàn toàn trung thực, không vi phạm bất cứ điều gì trong luật sở hữu trí tuệ và pháp luật Việt Nam. Nếu sai, tôi hoàn toàn chịu trách nhiệm trước pháp luật. TÁC GIẢ LUẬN VĂN Nguyễn Thị Thùy Số hóa bởi Trung tâm Học liệu http://www.vn/ 4 LỜI CẢM ƠN Trước hết, tôi xin bày tỏ lòng cảm ơn chân thành tới thầy giáo,TS.

Trần Đức Sự, người tận tình hướng dẫn tôi trong suốt thời gian làm luận văn tốt nghiệp. Tôi xin cảm ơn các thầy, cô giáo ở khoa Công nghệ thông tin trường Đại học CNTT và truyền thông - Đại học Thái Nguyên đã giảng dạy tôi trong suốt thời gian học tập tại trường và tạo điều kiện giúp đỡ tôi hoàn thành luận văn này. Cảm ơn các bạn bè, đồng nghiệp đã cổ vũ động viên tôi trong suốt quá trình học tập tại trường. Tuy đã có những cố gắng nhất định nhưng do thời gian và trình độ có hạn nên chắc chắn luận văn này còn nhiều thiếu sót và hạn chế nhất định.

Kính mong nhận được sự góp ý của thầy cô và các bạn. Số hóa bởi Trung tâm Học liệu http://www.vn/ 5 MỤC LỤC LỜI CAM ĐOAN. DANH MỤC CÁC TỪ VIẾT TẮT. DANH MỤC CÁC BẢNG.

DANH MỤC CÁC HÌNH VẼ. TỔNG QUAN VỀ KHAI PHÁ LUẬT KẾT HỢP CÓ ĐẢM BẢO TÍNH RIÊNG TƢ. Một số khái niệm cơ bản. Khai phá dữ liệu.

Khai phá dữ liệu đảm bảo tính riêng tư. Khai phá luật kết hợp. Luật kết hợp. Khai phá luật kết hợp.

Các phương pháp khai phá luật kết hợp có đảm bảo tính riêng tư. Khai phá luật kết hợp có đảm bảo tính riêng tư với dữ liệu tập trung. Khai phá luật kết hợp có đảm bảo tính riêng tư với dữ liệu phân tán. Khai phá dữ liệu trong mô hình phân tán.

Ẩn các luật nhạy cảm trong khai phá luật kết hợp. Một số kỹ thuật khai phá luật kết hợp có đảm bảo tính riêng tư. Phương pháp biến đổi dữ liệu. Sử dụng thành viên thứ ba đáng tin cậy.

Tính toán đa thành viên bảo mật. MỘT SỐ PHƢƠNG PHÁP TÌM LUẬT KẾT HỢP. Bài toán tìm luật kết hợp. 17 Số hóa bởi Trung tâm Học liệu http://www.

Phát biểu bài toán. Thuật toán Apriori. Thuật toán Apriori. Thuật toán khai phá luật kết hợp phân tán.

Thuật toán khai phá luật kết hợp phân tán nhanh(FDM). Thuật toán khai phá phân tán luật kết hợp (DMAR) .MỘT SỐ THUẬT TOÁN KHAI PHÁ LUẬT KẾT HỢP CÓ ĐẢM BẢO TÍNH RIÊNG TƢ. Phương pháp dựa trên tính tổng bảo mật chống lại sự thông đồng. Thuật toán khai phá dữ liệu đảm bảo tính riêng tư chống lại sự thông đồng.

Tính tổng bảo mật với Secure Sum. Mô hình khai thác bằng CRDM. Một số giao thức tiếp cận theo hướng FI (Frequent itemset):. Giao thức sử dụng mã hóa giao hoán KCS.

Giao thức sử dụng thành viên thứ ba bán tin cậy sử dụng mã hóa Paillier. Kỹ thuật tính tổng bảo mật cải tiến dựa trên mô hình hai thành viên bán tin cậy. So sánh hai phương pháp Secure Sum và Two Mixer Sum. Cài đặt thuật toán Secure Sum.

Yêu cầu về càiđặt thuật toán. Quá trình cài đặt và thử nghiệm thuật toán Secure Sum. Cài đặt thuật toán Two Mixer Sum. 62 Số hóa bởi Trung tâm Học liệu http://www.vn/ 7 KẾT LUẬN VÀ KIẾN NGHỊ.

67 TÀI LIỆU THAM KHẢO. 68 Số hóa bởi Trung tâm Học liệu http://www.vn/ 8 DANH MỤC CÁC TỪ VIẾT TẮT A.sup: Ðộ hỗ trợ toàn cục của itemset A (tính theo số lần xuất hiện) A.supi: Ðộ hỗ trợ cục bộ của itemset A tại site i (tính theo số lần xuất hiện) conf: Ðộ tin cậy (toàn cục) tối thiểu CSDL: Cơ sở dữ liệu DB: Cơ sở dữ liệu tập trung hay toàn cục DBi: Cơ sở dữ liệu cục bộ tại site i FI: Tập itemset phổ biến FIi: Tập itemset phổ biến cục bộ tại site i KTDL: Khai thác dữ liệu MFI: Tập itemset tối đại MFIi: Tập itemset tối đại cục bộ tại site i Public key: Khoá công khai Private key: Khoá bí mật SMC: Các giao thức tính toán đa thành viên an toàn sup: Ðộ hỗ trợ (toàn cục) tối thiểu (tính theo tần số %) SUP: Ðộ hỗ trợ (toàn cục) tối thiểu (tính theo số lần xuất hiện) Trusted-party: Thành viên thứ 3 đáng tin cậy Số hóa bởi Trung tâm Học liệu http://www.vn/ 9 DANH MỤC CÁC BẢNG Bảng 1. Ví dụ về mô hình dữ liệu phân tán ngang. Ví dụ về mô hình dữ liệu phân tán dọc.

Các tập phổ biến. So sánh 2 phương pháp Secure Sum và Two Mixer Sum. 55 Số hóa bởi Trung tâm Học liệu http://www.vn/ 10 DANH MỤC CÁC HÌNH VẼ Hình 1. Quá trình khai phá luật kết hợp trên CSDL tập trung.

Giao thức sử dụng Trusted-party. Mô hình tính toán SMC. CSDL giao dịch. Quá trình tìm tập phổ biến.

Giai đoạn 1 của ví dụ sử dụng SecureSum. Giai đoạn 2 của ví dụ về sử dụng SecureSum. Một ví dụ minh họa CRDM .Giai đoạn 1, tìm itemset ứng viên chung. Giai đoạn 2, tính độ hỗ trợ toàn cục.

Giao thức sử dụng Semi-trusted-mixer. Giai đoạn 1 ví dụ về thuật toán Two – MixerSum. Giai đoạn 2 ví dụ về thuật toán Two – MixerSum. Giao diện chính của chương trình.

Tiến trình thử nghiệm của chương trình. Giao diện kết quả chương trình. Giao diện chương trình. Tiến trình thử nghiệm.

Kết quả chương trình. 63 Số hóa bởi Trung tâm Học liệu http://www.vn/ 1 MỞ ĐẦU Khai phá luật kết hợp là một trong các phương pháp quan trọng trong khai phá dữ liệu. Việc khai phá luật kết hợp thường được thực hiện trên các cơ sở dữ liệu giao dịch của người dùng được giữ trong các tổ chức, ví dụ các giao dịch mua hàng tại siêu thị, các giao dịch tài chính tại ngân hàng …. Các ngân hàng rất muốn tìm kiếm khả năng thanh toán nợ của khách hàng, họ cần hợp tác với nhau để tìm ra khả năng này thông qua một số đặc tính nào đó của khách hàng của họ tuy nhiên họ không thể giao dữ liệu khách hàng của họ cho các ngân hàng khác được có thể vì lí do cạnh tranh khách hàng, của luật bảo vệ thông tin người dùng.

Do đó nhu cầu tìm kiếm các luật kết hợp trên dữ liệu phân tán có đảm bảo tính riêng tư là một nhu cầu thiết yếu và cấp bách. Các giải pháp khai phá luật kết hợp có đảm bảo tính riêng tư ra đời là hết sức cần thiết, để cho phép thực hiện việc khai phá luật kết hợp trong khi vẫn bảo vệ được thông tin riêng tư. Do đó việc nghiên cứu, tìm hiểu các thuật toán khai phá luật kết hợp có đảm bảo tính riêng tư để tích hợp cho các ứng dụng là có tính thực tiễn cao. Xuất phát từ thực tiễn trên, mục đích của đề tài là nghiên cứu đánh giá “Một số kỹ thuật khai phá luật kết hợp có bảo đảm tính riêng tƣ trong các tập giao dịch phân tán ngang”.

Nội dung bao gồm 3 chương và phần mở đầu, phần kết luận với nội dung cụ thể như sau: Chương 1: Tổng quan về khai phá luật kết hợp có đảm bảo tính riêng tư. Trong chương 1 sẽ trình bày khái quát chung về vấn đề khai phá dữ liệu có đảm bảo tính riêng tư, vấn đề khai phát luật kết hợp có đám bảo tính riêng Số hóa bởi Trung tâm Học liệu http://www.vn/ 2 tư với dữ liệu tập trung và trên các hệ thống phân tán, một số tiêu chí đánh giá. Chương 2: Một số phương pháp khai phá luật kết hợp. Ở chương 2 chúng ta sẽ tìm hiểu về một số phương pháp tìm luật kết hợp, khai phá luật kết hợp trong dữ liệu phân tán.

Chương 3: Một số thuật toán khai phá luật kết hợp có đảm bảo tính riêng tư trong môi trường phân tán ngang. Chương này sẽ tập chung nghiên cứu về một số thuật toán khai phá luật kết hợp có đảm bảo tính riêng tư trong môi trường phân tán ngang. Trong đó tập trung vào 2 thuật toán chính là: Phương pháp dựa trên tổng bảo mật chống lại sự thông đồng và phương pháp tiếp cận theo hướng FI. Đồng thời trình bày đề mô thuật toán Secure Sum và cải tiến thuật toán.

Số hóa bởi Trung tâm Học liệu http://www.vn/ 3 Chƣơng 1 TỔNG QUAN VỀ KHAI PHÁ LUẬT KẾT HỢP CÓ ĐẢM BẢO TÍNH RIÊNG TƢ 1. Một số khái niệm cơ bản 1. Khai phá dữ liệu Khai phá dữ liệu (KPDL) là các 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. KPDL đượ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, … Với lượng dữ liệu gia tăng nhanh chóng thì KPDL 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 phá dữ liệu nhưng không ảnh hưởng đến tính riêng tư của dữ liệu.

Tính riêng tư Tính riêng tư là tính chất của các 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, một số số liệu thống kê các tổ chức, doanh nghiệp… Các thông tin này là bí mật kinh doanh, mà nếu để lộ ra sẽ gây bất lợi cho cá nhân, tổ chức,.