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,.
hay những thông tin do quy định của pháp luật nên không thể tiết lộ ra như bảo hiểm y tế, số tài khoản ngân hàng,. Những loại thông tin như trên gọi là những thông tin có tính riêng tư hay là tri thức nhạy cảm. Khai phá dữ liệu đảm bảo tính riêng tư Số hóa bởi Trung tâm Học liệu http://www.vn/ 4 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 1.
Luật kết hợp * Giao dịch: danh sách các mặt hàng (mục:item) trong một phiếu mua hàng của khách hàng. Giao dịch T là một tập mục. - Toàn bộ tập các mục I={i1,i2,.ik} “tất cả các mặt hàng”. Một giao dịch là một tập con của I: T I.
Mỗi giao dịch T có một định danh TID. - A là một tập mục A I và T là một giao dịch: Gọi T chứa A nếu A T. * Luật kết hợp. - Gọi A → B là một “luật kết hợp” nếu A T, B T và A B=.
- Luật kết hợp A→B có độ hỗ trợ (support) s trong CSDL giao dịch D nếu trong D có s% các giao dịch T chứa AB:chính là xác suất P(AB). Luật kết hợp A→B có độ tin cậy (confidence) c trong CSDL D nếu như trong D có c% các giao dịch T chứa A thì cũng chứa B: chính là xác suất P(B│A). Luật A → B được gọi là bảo đảm độ tin cậy c trong D nếu c(A→B)≥c. Độ hỗ trợ (Support) Số hóa bởi Trung tâm Học liệu http://www.vn/ 5 Độ hỗ trợ của một tập mục X trong cơ sở dữ liệu D là tỉ số giữa các giao tác T D có chứa tập X là tổng số giao tác trong D (hay là phần trăm của các giao tác trong D có chứa tập mục X), kí hiệu là Supp (X).1) Ta có 0 Supp (X) với mọi tập X.
Hay có thế nói Support chỉ mức độ “thường xuyên xảy ra” của mẫu. Độ hỗ trợ của luật X→Y là tỉ số của số giao tác có chứa X Y và số giao tác trong cơ sở dữ liệu D, kí hiệu là Supp (X→Y).2) Như vậy độ hỗ trợ của một luật bằng 50% nghĩa là có 50% số giao tác có chứa tập mục X Y. Độ hỗ trợ có ý nghĩa thống kê của luật kết hợp. Độ tin cậy ( Confidence) Độ tin cậy của luật kết hợp X →Y là xác suất xảy ra Y khi đã biết X.
Ví dụ độ tin cậy của luật kết hợp {Apple} →Banana} là 80% có nghĩa là 80% khách hàng mua Apple cũng mua Banana. Công thức để tính độ tin cậy của luật kết hợp X là xác suất có điều kiện Y khi đã biết X như sau : n( X Y ) Confidence(XY) = P(Y|X) = (2.3) n( X ) Trong đó: n(X) là số giao dịch chứa X * Một số ví dụ về luật kết hợp. Số hóa bởi Trung tâm Học liệu http://www.1 80% khách hàng mua tạp chí thể thao thì đều mua tạp chí về về ô tô =>sự kết hợp giữa tạp chí thể thao với tạp chí về về ô tô .2 Ngân hàng muốn thu thập thông tin về lịch sử tín dụng của khách hàng thấy có một luật: 75% khách hàng vay mua nhà và mua xe và có thu nhập hàng tháng dưới 7 triệu thì không có khả năng thanh toán nợ => sự kết hợp giữa vay mua nhà và mua xe, có thu nhập dưới 7 triệu với khả năng thanh toán nợ.3 20% trên tổng số khách hàng có tài khoản tiết kiệm có thu nhập lớn hơn hoặc bằng 60 triệu một năm với độ tin cậy là 100%.000_max →Tài khoản tiết kiệm= yes [20% ; 100%] 1. 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 gọi là các luật kết hợp.
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ư,. 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. Các phƣơng pháp khai phá luật kết hợp có đảm bảo tính riêng tƣ. Số hóa bởi Trung tâm Học liệu http://www.vn/ 7 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á.
Tuỳ 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 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 Tri thức KPDL Gốc Đã biến đổi Hình 1. Quá trình khai phá luật kết hợp trên CSDL tập trung Ví dụ 1. Một công ty bán hàng muốn nghiên cứu về nhu cầu mua hàng hoá 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 họ.
Để làm được việc này họ đã biến đổi dữ liệu trước khi chuyển giao cho việc nghiên cứu. Số hóa bởi Trung tâm Học liệu http://www.2 Một ngân hàng thực hiện khai phá dữ liệu nghiên cứu về khả năng thanh toán nợ của khách hàng dựa trên lịch sử tín dụng của khách hàng trên CSDL của họ. 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 của khách hàng. Để làm được việc này họ đã biến đổi dữ liệu trước khi chuyển giao cho việc nghiên cứu.
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. 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 Số hóa bởi Trung tâm Học liệu http://www.vn/ 9 KHM 21/12/1992 Hà Nội 098998986x kmh@gmail.