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ư được đề cập ở đây là những thông tin, 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, những thông tin nếu để lộ ra sẽ 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. Những loại thông tin như trên gọi là tính riêng tư của thông tin hay là tri thức nhạy cảm. Khai phá dữ liệu đảm bảo tính riêng tư Vậy khai phá dữ liệu có đảm bảo tính riêng tư là việc dùng các thuật toán để trích rút ra những tri thức quan trọng cần thiết cho mục đích khai phá dữ liệu mà không làm lộ ra các thông tin nhạy cảm của các cá nhân, tổ chức có trong tập dữ liệu.
Khai phá luật kết hợp Khai phá luật kết hợp: Là tìm các mẫu phổ biến, sự kết hợp, sự tương quan, hay các cấu trúc nhân quả giữa các tập đối tượng trong các cơ sở dữ liệu giao tác, cơ sở dữ liệu quan hệ, và những kho thông tin khác. Các ứng dụng: Luật kết hợp có ứng dụng trong nhiều lĩnh vực khác nhau của đời sống như: khoa học, hoạt động kinh doanh, tiếp thị, thương mại, phân tích thị trường chứng khoán, tài chính và đầu tư,. Ví dụ về luật kết hợp: o Bia => Lạc [0,5% ; 60%] Luật này có nghĩa: Nếu mua bia thì mua lạc trong 60% trường hợp. Bia và lạc được mua chung trong 0.5% tổng giao dịch.000_max => Tài khoản tiết kiệm= yes [20% ; 100%] Luật này có nghĩa: Nếu thu nhập lớn hơn hoặc bằng 60 triệu một năm thì khách hàng có tài khoản tiết kiệm với độ tin cậy là 100%.
Từ các luật kết hợp được trích rút từ chính các cơ sở dữ liệu giao dịch, cơ sở dữ liệu khách hàng mà các siêu thị, các ngân hàng sẽ có chiến lược kinh doanh (sắp xếp các mặt hàng, số lượng các mặt hàng,.), chiến lược tiếp thị, quảng cáo,… để từ đó thúc đẩy hoạt động kinh doanh của mình. Phát biểu bài toán khai phá luật kết hợp có đảm bảo tính riêng tư. 5 Khai phá luật kết hợp có đảm bảo tính riêng tư là quá trình khai phá các luật kết hợp trong các cơ sở dữ liệu, đồng thời vẫn đảm bảo các thông tin riêng tư của các cá nhân hoặc tổ chức trong các cơ sở dữ liệu không bị lộ cho người khai phá. Tùy thuộc vào đặc trưng của nguồn dữ liệu, mô hình dữ liệu mà chúng ta có thể phân chia thành các loại bài toán khai phá luật kết hợp có đảm bảo đảm tính riêng tư khác nhau: 1.
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 Trong bài toán này, người ta giả thiết có một tổ chức sở hữu tập dữ liệu, trong tập dữ liệu có một số thuộc tính nhạy cảm. Tổ chức này mong muốn công bố tập dữ liệu cho mục đích nghiên cứu, ví dụ: Khai phá luật kết hợp, đồng thời mong muốn bảo vệ các thông tin riêng tư trong tập dữ liêu. Một phương pháp cơ bản để giải quyết bài toán này là thực hiện biến đổi dữ liệu để ẩn các thông tin nhạy cảm trước khi đưa vào khai thác như vậy sẽ không tiết lộ thông tin nhạy cảm. CSDL Biến đổi CSDL KPDL Tri thức Gốc Đã biến đổi Hình 1.
Ví dụ về cơ sở dữ liệu tập trung Ví dụ 1.1: Một công ty bán hàng muốn nghiên cứu về nhu cầu mua hàng hóa vào mùa hè sắp tới để có phương pháp huy động vốn và đầu tư mặt hàng cho phù hợp và hiệu quả. Họ sẽ cung cấp dữ liệu cho chuyên gia để nghiên cứu, tuy nhiên họ lại không muốn để lộ các thông tin về bán hàng của 6 họ. Vì vậy cần phải biến đổi dữ liệu trước khi chuyển giao cho việc nghiên cứu này.2: KTDL (không viết tắt) 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 của họ. 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 1.
Tập hợp dữ liệu phân tán đã được biến đổi: (bỏ phần này) 1. Khai phá dữ liệu trong mô hình phân tán Giả thiết rằng tập dữ liệu được phân tán thành nhiều phần theo chiều ngang hoặc theo chiều dọc trên một nhóm các tổ chức (thành viên), mỗi thành viên sở hữu một tập dữ liệu riêng. Vấn đề đặt ra là làm thế nào để các tổ chức có thể chia sẻ tập dữ liệu cho nhau nhăm khai phá ra các luật kết hợp trên tập dữ liệu liên kết của các thành viên, trong khi vẫn bảo vệ được tính riêng tư của mỗi thành viên tham gia. Phân tán ngang Các site khác nhau thu thập cùng các đặc trưng về thông tin của các thực thể khác nhau.
Cũng có thể hiểu là các Site khác nhau nắm giữ cùng các thuộc tính của các đối tượng khác nhau Bảng 1. Ví dụ về mô hình dữ liệu phân tán ngang Mô hình toàn cục Họ tên Ngày sinh Nơi sinh Số điện thoại Email Site A ABC 10/10/1992 Nghệ An 097994898x abc@gmail. Site B KHM 21/12/1992 Hà Nội 098998986x kmh@gmail.1: 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? Chẳng hạn như 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.
Phân tán dọc Các site thu thập các đặc trưng khác nhau của cùng tập thực thể, ví dụ: Bệnh viện thu thập các thông tin về bệnh nhân, các chứng bệnh. Nhà cung cấp dịch vụ viễn thông cung cấp về thông tin khách hàng, thời gian gọi điện, thời lượng gọi điện… Tổng hợp 2 cơ sở dữ liệu này lại để nghiên cứu về một mối tương quan giữa các bệnh có thể sinh ra do nguyên nhân sử dụng điện thoại di động Bảng 1. Ví dụ về mô hình dữ liệu phân tán dọc Dữ liệu toàn cục Họ tên Số CMT Thời lượng Bị u não Bị viêm tai Dữ liệu tại hãng viễn thông Họ tên Số CMT Thời lượng(phút)/ngày Nguyễn Văn A 18613377x 20 ………. Dữ liệu tại bệnh viện 8 Họ tên Số CMT Bị u não Bị viêm tai Nguyễn Văn A 18613377x Có không ……….
Ẩn các luật nhạy cảm trong khai phá luật kết hợp Trong quá trình khai phá dữ liệu có thể có những luật nhạy cảm không muốn bị lộ ra, ví dụ: Trong ngân hàng có một số luật được tìm thấy nhưng lại rất nhạy cảm, ngân hàng không muốn tiết lộ ra vì nếu tiết lộ ra sẽ làm ảnh hưởng đến khách hàng, hoặc ảnh hưởng đến ngân hàng, giả dụ như Khách hàng sử dụng dịch vu A và sử dụng dịch vụ B thì thường dẫn đến không có khả năng thanh toán nợ… Chính vì lí do đó nên trong bài toán khai phá luật kết hợp có đảm bảo tính riêng tư chúng ta cần tính đến việc ẩn đi các luật nhạy cảm. Các kỹ thuật khai phá luật kết hợp có đảm bảo tính riêng tư 1. Phương pháp biến đổi dữ liệu Tư tưởng của phương pháp biến đổi dữ liệu là trước khi đưa dữ liệu vào khai phá thì dữ liệu sẽ được biến đổi, tuy nhiên việc biến đổi chỉ nhằm che dấu những thông tin nhạy cảm mà không làm ảnh hưởng đến kết quả tính toán. Một trong nhưng phương pháp thường được sử dụng trong trường hợp này là phương pháp cộng nhiễu.
Sử dụng thành viên thứ ba đáng tin cậy Thành viên thứ 3 đáng tin cậy (Trusted-party) là một thành viên bên ngoài, hoạt động hoàn toàn độc lập, tính toán và đưa ra kết quả, sau khi đưa ra kết quả thành viên đáng tin cậy này xoá tất cả những gì đã biết. 9 Cách thực hiện như trong hình 1.3, tất cả các thành viên gửi dữ liệu cục bộ hoặc các mô hình khai thác cục bộ cho Trusted-part, Trusted-party tính toán và gửi kết quả khai thác về cho các thành viên. Hướng tiếp cận này an toàn tuyệt đối nhưng Trusted-party thì không thực tế [27][4][2].3 – Giao thức sử dụng Trusted-party 1. Tính toán đa thành viên bảo mật Tính toán đa thành viên bảo mật (Secure Multi-party Computation – SMC) là một tính toán giữa hai hay nhiều thành viên dựa vào các yếu tố đầu vào, tiến hành tính toán mà không để lộ bất kỳ thông tin gì ngoại trừ kết quả và các yếu tố đầu vào của mỗi thành viên.
Ý tưởng của SMC tương tự như giao thức với thành viên thứ ba đáng tin cậy, mỗi thành viên tham gia gửi yếu tố đầu vào tới thành viên thứ ba đáng tin cậy này và chỉ nhận lại kết quả tính toán. SMC giả lập thành viên thứ ba đáng tin cậy này dựa vào một giao thức giữa các thành viên [2] như trong hình 1.4 - Mô hình tính toán SMC Đã có nhiều giao thức SMC được đề xuất như: tính tổng an toàn, phép giao an toàn, phép hợp an toàn, tích vô hướng an toàn. Ta có thể kết hợp các giao thức con để tạo ra các giao thức an toàn mới, nếu thuật toán/giao thức phụ thuộc vào một số giao thức con, việc thực hiện các giao thức con hiệu quả sẽ cải thiện đáng kể hiệu quả tổng thể.