Đề xuất mô hình khai thác luật hiếm trên cơ sở dữ liệu phân tán dọc bảo toàn tính riêng tư

192 ĐỀ XUẤT MÔ HÌNH KHAI THÁC LUẬT HIẾM TRÊN CSDL PHÂN TÁN DỌC BẢO TOÀN TÍNH RIÊNG TƢ Cao Tùng Anh, Võ Hoàng Khang, Văn Nhƣ Bích B Trường Đại học Công nghệ TP. Hồ Chí Minh TÓM TẮT Khai phá tri thức tiềm ẩn trong cơ sở dữ liệu hiện nay là một mục tiêu quan trọng của ngành khoa học khai thác dữ liệu và được rất nhiều nhà nghiên cứu quan tâm. Luật hiếm là luật không thường xuyên xảy ra nhưng lại có giá trị và tính ứng dụng cao trong một số điều kiện, môi trường cụ thể. Khai thác luật hiếm trong thực tế cũng là một bài toán đã nhận được nhiều quan tâm từ các nhà khoa học. Tuy nhiên trong dữ liệu thường có chứa những dữ liệu nhạy cảm, việc bảo toàn tính riêng tư trong khai thác dữ liệu để tránh tiết lộ những dữ liệu nhạy cảm cũng là một hướng nghiên cứu cấp thiết hiện nay. Khai thác luật hiếm trên cơ sở dữ liệu (CSDL) phân tán bảo toàn tính riêng tư tập trung vào việc khai thác được các luật hiếm có trong dữ liệu được chia sẻ từ nhiều bên nhưng không làm tiết lộ dữ liệu của các bên tham gia. Trong phạm vi bài báo này, chúng tôi đề xuất một mô hình khai thác tập hiếm trên môi trường cơ sở dữ liệu phân tán dọc và bảo toàn tính riêng tư cho dữ liệu của các bên cung cấp dữ liệu trong qua trình khai thác. Từ khóa: Bảo toàn tính riêng tư, cơ sở dữ liệu phân tán dọc, khai thác dữ liệu, luật hiếm. 1. GIỚI THIỆU Mục đích của bài toán phát hiện luật kết hợp là tìm ra mối quan hệ giữa các tập mục dữ liệu trong các CSDL lớn và các mối quan hệ này là có ích trong việc hỗ trợ ra quyết định. Ví dụ: trong CSDL siêu thị, việc phát hiện được quan hệ "76% số khách hàng mua kem đánh răng và bàn chải cũng mua khăn mặt" sẽ rất có ích cho quyết định kinh doanh. Chẳng hạn, quyết định về số lượng nhập các mặt hàng này hoặc bố trí chúng tại các ngăn hàng liền kề nhau. Phát hiện luật kết hợp hiếm là một phần của bài toán phát hiện luật kết hợp và hiện đã nhận được nhiều sự quan tâm của các nhà nghiên cứu. Luật kết hợp hiếm được ứng dụng ở nhiều lĩnh vực khác nhau. Các luật hiếm sẽ giúp xác định ảnh hưởng của các hoạt động trong việc học trực tuyến đến kết quả đánh giá cuối cùng của sinh viên, xác định được các bệnh hiếm gặp trong y khoa, dự báo việc hỏng thiết bị truyền thông, hay giúp xác định được các mặt hàng tuy ít xảy ra trong các giao dịch mua bán nhưng lại có giá trị lớn hoặc mang lại lợi nhuận cao trong kinh tế. Ví dụ: luật kết hợp hiếm “máy pha cà phê” → “máy xay cà phê” có độ hỗ trợ rất thấp dưới 10% song có độ tin cậy khá cao tới 80% và giá trị bán hai mặt hàng này cùng nhau là rất đáng kể. Trong [1], các tác giả đã định nghĩa luật hiếm tuyệt đối: luật XY được gọi là luật hiếm tuyệt đối khi: conf(X Y) ≥ minconf, minsup ≤ sup((X Y)) < maxsup, x  (X Y), sup(x) < maxsup. Trong đó, minsup, maxsup, minconf là các giá trị do người sử dụng đưa vào. Với minsup nhằm hạn chế các tập có độ hỗ trợ quá nhỏ không mong đợi. Như vậy chúng ta chỉ tìm các tập hiếm tuyệt đối mà trong đó các phần tử của tập hiếm có độ hỗ trợ không nhỏ hơn minsup sẽ mang lại nhiều lợi ích và giảm được khối lượng dữ liệu quá lớn khi khai thác. maxsup để tìm các tập hiếm không phổ biến (không lớn hơn ngưỡng maxsup) và minconf để phát hiện các luật hiếm từ các tập hiếm đã tìm được. Trong sự phát triển 193 nhanh chóng của dữ liệu và công nghệ thông tin, nhiều doanh nghiệp, đơn vị hành chính, tổ chức y tế mong muốn cùng chia sẻ thông tin với các bên khác nhau để cùng tận dụng những lợi ích chung từ dữ liệu của họ. Tuy nhiên, trong dữ liệu thường chứa thông tin nhạy cảm nên đây là mặt hạn chế khi các bên muốn chia sẻ dữ liệu để cùng khai thác. Để khắc phục vấn đề trên, một lĩnh vực nghiên cứu bảo toàn tính riêng tư trong quá trình khai thác dữ liệu phân tán ra đời. Mục đích chính của các nghiên cứu là khai thác những thông tin hữu ích từ các tập dữ liệu của các bên tham gia, nhưng chắc chắn được rằng dữ liệu của các bên phải được bảo mật, không bị lộ và không bị đánh cắp từ các bên còn lại. Mục đích của bài báo này là hướng tới cung cấp một mô hình khai thác luật hiếm trên CSDL phân tán dọc và bảo toàn tính riêng tư cho dữ liệu của các bên tham gia chia sẻ dữ liệu để khai thác. Ở phần 2 sẽ giới thiệu một số nghiên cứu liên quan. Phần 3 trình bày phương pháp mà chúng tôi đã nghiên cứu và đề xuất trong bài báo này. Trong phần 4 sẽ thực hiện mô hình đề xuất với 4 bên tham gia khai thác và trình bày các số liệu đã được kiểm chứng thực tế. Phần 5 là phần kết luận, đánh giá những ưu điểm và nêu ra một số nhược điểm cần cải tiến. 2. CÁC NGHIÊN CỨU LIÊN QUAN Trong thời gian qua, đã có nhiều tác giả nghiên cứu các mô hình nhằm tăng độ bảo toàn tính riêng tư trong quá trình khai thác trên CSDL phân tán dọc và đã có những đóng góp quan trọng. Trong [4], Muthu Lakshmi và cộng sự đã nghiên cứu và thực hiện mô hình bảo toàn tính riêng tư trên CSDL phân tán dọc với n bên (site) bằng cách tìm tập phổ biến ở từng site, sau đó chuẩn bị một ma trận Mk ( ) thể hiện thông tin của các tập phổ biến và một vector enVk bao gồm các thuộc tính đã được mã hóa. Sitek sẽ gửi Mk và enVk sang site tiếp theo. Site này sử dụng ma trận Mk+1 và enVk+1 của mình kết hợp với Mk và enVk để tìm tập phổ biến mới Mk+1' và enVk+1' (bản chất là tập phổ biến của tập CSDL kết hợp từ sitek và sitek+1). Sau đó, sitek+1 tiếp tục gửi Mk+1' và enVk+1' đến site tiếp theo, điều này được lặp lại cho đến siten và kết quả được gởi đến DM để giải mã và gửi kết quả đến từng site. Từ nghiên cứu của Muthu Lakshmi và các công sự, trong [4] các tác giả đã đề xuất một mô hình cải tiến để giảm thời gian thực hiện việc khai thác bằng cách chia n site thành 2 nhóm và thực hiện việc khai thác cùng lúc trên 2 nhóm, từ đó tránh được việc dồn dữ liệu của n-1 bên vào bên n. Mô hình này giảm thời gian khai thác đáng kể khi các có nhiều bên tham gia. Trong [1] các tác giả đã đề xuất thuật toán khai thác luật hiếm không tuyệt đối hai ngưỡng và trong [2] các tác giả cũng đã đề xuất mô hình khai thác luật hiếm bảo toàn tính riêng tư trên CSDL phân tán ngang. Qua tìm hiểu từ các nghiên cứu liên quan, trong bài báo này chúng tôi đề xuất mô hình khai thác luật hiếm trên CSDL phân tán dọc bảo toàn tính riêng tư. 3. MÔ HÌNH KHAI THÁC Trong [4], các tác giả đã đề xuất mô hình khai thác luật kết hợp có bảo toàn tính riêng tư trên CSDL phân tán dọc với n bên tham gia. Trong bài báo này, chúng tôi sẽ đề xuất một số thay đổi để có thể khai thác được tập hiếm trên CSDL phân tán dọc và bảo toàn tính riêng tư. Trong [3], các tác giả đã chứng minh được rằng: với mô hình khai thác này, việc bảo toàn tính riêng tư vẫn được đảm bảo khi có n-1 bên (trong số n bên tham gia) thông đồng. Trong bài báo này, chúng tôi vẫn sử dụng mô hình của [4] để chia n site thành 2 nhóm (group) với số lượng site tại mỗi nhóm như sau: group1 gồm các sitei với {1,,n/2} và group2 là các site còn lại. Việc chia n bên thành 2 nhóm theo [4] đã giảm được đáng kể thời gian khai thác. Quá trình khai thác diễn ra song song ở Group1 và Group2. Kết quả tại site cuối cùng của mỗi group được gửi đến DM để khai thác luật hiếm toàn cục và gửi kết quả cho tất cả các bên. Các bước trao đổi dữ liệu và tiến hành tại các bên được thực hiện như sau: 194 Bƣớc 1: DM đánh số các site tham gia từ 1 đến n (với mô hình 2 nhóm, số bên tham gia n>=4) và gom các site thành 2 nhóm: Group1 gồm các sitei với i {1,,n/2}, và Group2 là các site còn lại. Sau đó DM gửi ngưỡng minsup, maxsup, và mã khóa công khai (public key) cho tất cả các bên. Hình 1. Mô hình trao đổi dữ liệu giữa các bên Bƣớc 2: Mỗi bên tiến hành khai thác các tập hiếm của mình từ tập các giao dịch trong dữ liệu hiện có dựa trên ngưỡng minsup, maxsup đã nhận được từ DM. Bƣớc 3: Đối với mỗi sitek, tạo ra một ma trận Mk và một vector Vk. Với Mk mỗi hàng thể hiện giao dịch của một tập hiếm được tìm thấy trong các giao dịch tại CSDL cục bộ. Trong ma trận này, nếu Mk (i, j) = 1, nghĩa là trong giao dịch ở cột thứ j xuất hiện tập hiếm tại hàng i này. Tập các vector Vk chứa các tập hiếm đã được tìm thấy tại sitek. Giữa Vk và Mk duy trì một mối quan hệ là: tập hiếm thứ i trong vector Vk tương ứng với các giao dịch cho dòng thứ i của ma trận Mk. Bƣớc 4: Mỗi bên sẽ mã hóa tất cả các tập hiếm trong vector Vk thành enVk bằng cách sử dụng khóa công khai đã nhận được từ DM. Từ Bước 5 đến Bước 8 được thực hiện đồng thời tại cả 2 group. Dữ liệu được gửi từ site1 đến siten/2 tại group1 và từ siten đến siten/2+1 tại group2. Bƣớc 5: Site1 gửi ma trận M1 và enV1 đến site2. (Hoặc siten gửi ma trận Mn và enVn đến siten-1). Bƣớc 6: Site2 thực hiện M1 x M2 bằng cách sử dụng khái niệm về tích Descartes và tạo ra một ma trận M12 trong đó bao gồm tập hiếm của M1 x M2. Site2 sau đó tạo ra ma trận M2' từ các ma trận M1, M2 và M12. Bƣớc 7: Site2 tạo ra vector enV2' trong đó bao gồm danh sách đã mã hóa các tập hiếm có trong enV1, enV2 và enV12 với enV12 là đại diện cho các tập hiếm được mã hóa của M12. Site2 sẽ gửi ma trận M2' cùng với vector enV2' đến bên kế tiếp của nó. Bảng 1. Một số từ viết tắt Thuật ngữ Mô tả minsup Độ hỗ trợ tối thiểu maxsup Độ hỗ trợ tối đại minconf Độ tin cậy tối thiểu Mi Ma trận thể hiện dữ liệu tập hiếm của bên thứ i Mi’ Ma trận thể hiện dữ liệu tập hiếm của bên thứ i và i+1 (hoặc i-1 tùy theo hướng khai thác) Vi Vector thể hiện các thuộc tính tương ứng với Mi enVi Vector đã mã hóa các thuộc tính từ Vi DM Data Miner – Nơi độc lập, nhận dữ liệu từ bên n/2 và n/2+1 195 Bƣớc 8: Các sitei còn lại thực hiện Bước 6 và 7 dựa vào ma trận và vector nhận được từ bên thứ i-1 và ma trận riêng của mình Mi và vector mã hóa enVi. Bƣớc 9: Bên cuối cùng của mỗi group (siten/2 và siten/2+1) gửi ma trận Mn/2', vector enVn/2' và ma trận Mn/2+1', vector enVn/2+1' đến DM. Bƣớc 10: Sau khi nhận được dữ liệu từ siten/2 và siten/2+1. DM thực hiện tương tự ở Bước 6 và 7 để có MDM' và vector enVDM'. Bƣớc 11: Tại DM, sắp xếp lại enVDM' dựa vào độ dài các tập hiếm đã mã hóa theo thứ tự giảm dần. Dựa theo vị trí của các tập hiếm đặt trong danh sách sắp xếp enVDM', ma trận MDM' được sắp xếp lại để theo đúng thứ tự. DM giải mã bằng khóa riêng cho mỗi tập hiếm trong vector enVDM' để có được những tập hiếm toàn cục. DM tìm độ hỗ trợ của từng tập hiếm toàn cục bằng cách đếm số lần xuất hiện của mỗi tập mục trong hàng tương ứng của ma trận MDM' và sinh ra một danh sách bao gồm các tập hiếm toàn cục và độ hỗ trợ của nó. Bƣớc 12: Dựa trên danh sách này, DM tạo ra các luật hiếm toàn cục dựa vào minconf do người sử dụng nhập vào. Sau đó các luật hiếm này sẽ được gửi đến tất cả các bên. Quy trình khai thác kết thúc. 4. THỰC HIỆN MÔ HÌNH Giả sử trong mô hình ví dụ của chúng ta có 4 bên tham gia và các bên có dữ liệu đã được phân tán dọc như trong các bảng 2, 3, 4 và 5. Dữ liệu của các bên đều bao gồm 6 giao dịch và với các thuộc tính khác nhau từ A1 đến A12 tương đương với các mặt hàng khác nhau mà các bên có. Bảng 2. Dữ liệu cục bộ tại Site1 TID\Item A1 A2 T1 1 1 T2 1 0 T3 1 0 T4 0 1 T5 1 0 T6 0 0 Bảng 3. Dữ liệu cục bộ tại Site2 TID\Item A3 A4 A5 T1 1 1 0 T2 1 0 1 T3 1 0 0 T4 1 1 1 T5 1 1 0 T6 0 0 0 Đầu tiên, DM yêu cầu cả bốn bên tham gia vào quá trình khai thác để tìm tập hiếm toàn cục bằng cách gửi maxsup= 40% và minsup=5%. Mỗi bên áp dụng thuật toán tìm tập hiếm để tìm các tập hiếm thỏa maxsup và minsup này. Tại group1- site1: Site1 tạo ra ma trận M1 và vector V1 có giá trị như sau: [ ] và V1 = {A2, (A1,A2)}. Site1 mã hóa tên các thuộc tính của vector V1 dựa vào khóa công khai: enV1 = {e(A2), e(A1, A2)}. Sau đó gửi M1 và enV1 đến site2. Tại group1 - site2: Site2 có ma trận M2 và vector enV2 đã mã hóa các thuộc tính như sau: 196 [ ] enV2 = {e(A5), e(A3,A5)}. Site2 tìm ma trận M12 và vector enV12 dựa trên M1, enV1, M2 và enV2. Ma trận M12 được tạo ra bằng cách tính tích Descartes của ma trận M1 và M2. Sau đó chọn ra những dòng thỏa điều kiện của tập hiếm. Kết quả M12 như sau: , - và vector V12={(A2, A3, A5)} M2' được tạo ra bằng cách hội M2, M12 vào M1 và enV2’ tạo ra bằng cách kết hợp enV2, enV12 vào enV1. Ta có kết quả như sau: [ ] và enV2'={e(A2), e(A1,A2), e(A5), e(A3,A5), e(A2, A3, A5)}. Sau đó site2 sẽ gửi M2' và enV2' cho DM. Tại group2 giả sử dữ liệu của site3 và site4 lần lượt như trong Bảng 4 và Bảng 5. Site4 thực hiện tìm M4 và enV4 sau đó gửi qua site3. Tại đây, site3 thực hiện tương tự như site2 của group1. Bảng 4. Dữ liệu cục bộ tại Site3 TID\Item A6 A7 A8 T1 1 0 0 T2 0 1 0 T3 0 1 1 T4 1 1 0 T5 0 0 1 T6 1 0 1 Bảng 5. Dữ liệu cục bộ tại Site4 TID\Item A9 A10 A11 A12 T1 1 1 0 0 T2 0 1 0 0 T3 1 0 0 1 T4 0 0 0 1 T5 0 0 1 1 T6 1 1 0 0 Kết quả tại site3 sau khi kết hợp với kết quả của site4 như sau: [ ] enV3' = {e(A6,A7), e(A6,A8), e(A7,A8), e(A11), e(A9, A10), e(A9, A12), e(A11, A12), e(A6, A8, A9, A10), e(A7, A8, A9, A12)}. Sau đó, site3 gửi M3' và enV3' đến DM. Tại DM: Sau khi nhận được dữ liệu từ site2, site3, DM thực hiện tương tự như ở các group với M2', enV2' và M3', enV3' để tìm ra MDM' và enVDM': 197 enVDM’ = { e(A2), e(A1,A2), e(A5), e(A3,A5), e(A2, A3, A5), e(A6,A7), e(A6,A8), e(A7,A8), e(A11), e(A9, A10), e(A9,A12), e(A11,A12), e(A6,A8, A9,A10), e(A7, A8, A9, A12)}. DM sắp xếp enVDM' dựa vào độ dài các tập hiếm đã mã hóa theo thứ tự giảm dần. Dựa theo vị trí của các tập hiếm đặt trong danh sách sắp xếp enVDM', ma trận MDM' được sắp xếp lại để theo đúng trật tự. enVDM' ={e(A6, A8, A9, A10), e(A7, A8, A9, A12), e(A2, A3, A5), e(A6, A7), e(A6, A8), e(A7, A8), e(A9, A10), e(A9,A12), e(A11,A12), e(A1,A2), e(A3,A5), e(A2), e(A5), e(A11)}. DM áp dụng giải mã enVDM' với private key để có các tập hiếm, lúc này các tập hiếm đã trộn lẫn của nhiều bên nên DM không phát hiện ra một tập hiếm X chính xác thuộc site nào. DM cũng tìm độ hỗ trợ (Support) cho từng tập hiếm bằng cách đếm các giá trị 1 trong các hàng tương ứng từ ma trận MDM' đã sắp xếp. Từ đó, DM cũng sẽ tìm các luật hiếm cho từng tập hiếm toàn cục dựa trên minconf. (Trong ví dụ này minconf=80%). Ta xét tập hiếm toàn cục (A3, A5) ta có luật hiếm A3 A5 do độ tin cậy của luật này là 100%> minconf. Tương tự cách tìm luật hiếm như trên, DM sẽ tìm tất cả luật hiếm trong các tập hiếm và truyền kết quả về cho từng bên tham gia. Bảng 6. Tập hiếm toàn cục và độ hỗ trợ Item Sets Sup Item Sets Sup (A2) (A5) (A11) (A1,A2) (A3,A5) (A6,A7) (A6,A8) 2 2 2 1 2 2 2 (A7,A8) (A9,A10) (A9,A12) (A11,A12) (A2,A3,A5) (A6,A8,A9,A10) (A7,A8,A9,A12) 1 2 1 1 1 1 1 Chúng tôi đã cài đặt chương trình để kiểm tra kết quả. Kết quả cho thấy mô hình đề xuất có kết quả số luật hiếm tìm thấy tương đương với nghiên cứu [2]. Máy tính sử dụng tại các bên tham gia là Intel 3.2GHz, bộ xử lý Core i5, Ram 4GB, hệ điều hành Window 10 – 64 bit. Chúng tôi cũng thực nghiệm trên nhiều site khác nhau để đo thời gian thực hiện. Thời gian đo được tính từ khi DM gửi maxsup, minsup và khóa công khai cho các bên và được tính là tổng thời gian thực hiện ở tất cả các bên và ở DM. Thời gian truyền dữ liệu được coi là không đáng kể. Số liệu thực nghiệm được đo từ dữ liệu Mushroom gồm 8418 dòng và 119 thuộc tính. Chúng tôi lần lượt chia số thuộc tính ra làm 4, 10 và 20 cho số lượng các bên tham gia. Kết quả trong bảng 7. Bảng 7. Thời gian thực nghiệm Số bên Thời gian (Milisecond) 4 3250 10 3824 20 4422 Bảng 8. Kết quả thực hiện trên các CSDL Tên CSDL minsup maxsup minconf Số luật hiếm Mushroom 30% 70% 75% 23 Chess 30% 70% 75% 135 C20d10k 30% 70% 75% 15 198 Trong Bảng 8, số lượng các bên tham gia là 4, chúng tôi tiến hành thực nghiệm để kiểm tra tính đúng đắn của mô hình khai thác đề xuất. Kết quả cho thấy: số luật hiếm khai thác được trên mô hình đề xuất trùng vời số luật hiếm được tìm thấy khi khai thác trên CSDL tập trung. 5. KẾT LUẬN Bài báo đã đề xuất mô hình khai thác tập hiếm trên CSDL phân tán dọc bảo toàn tính riêng tư cho dữ liệu của các bên tham gia. Thông tin các bên đã được mã hóa, và chỉ DM mới có thể giải mã. Lúc này dữ liệu các bên đã được trộn lại và DM không thể biết chính xác dữ liệu của từng bên, như vậy mô hình sẽ đảm bảo thông tin được giữ kín, không thể bị đánh cắp từ các bên khác. Dựa vào kết quả thực nghiệm, chúng tôi cũng nhận xét rằng kết quả khai thác trên CSDL tập trung và kết quả khai thác trên CSDL phân tán dọc bảo toàn tính riêng tư theo mô hình đã đề xuất là như nhau. Hạn chế đối với mô hình 2 nhóm là: số lượng các bên tham gia phải lớn hơn hoặc bằng 4. Nếu số lượng các bên tham gia là 2 hoặc 3 chúng tôi đề xuất sử dụng mô hình một bên để đảm bảo dữ liệu được trộn ít nhất là của 2 bên tham gia nhằm tránh bị lộ thông tin tại DM. TÀI LIỆU THAM KHẢO [1] Cu Thu Thuy, Do Van Thanh (2010), “Mining Imperfectly Sporadic Rules with Tow Thresholds”, International Journal of Computer Theory and Engineering, Vol.2(5) 2010, pp.718-723. [2] Huỳnh Ngọc Ca, Cao Tùng Anh, Nguyễn Hoàng Tú Anh (2017), “Khai thác luật hiếm bảo toàn tính riêng tư trên CSDL phân tán ngang”, Hội thảo quốc gia về công nghệ thông tin và truyền thông, Quy Nhơn 23-24/11/2017, tr 123-128. [3] N. V. Muthu Lakshmi and K. Sandhya Rani (2012), “Privacy Preserving Association Rule Mining in Vertically Partitioned Databases”, International Journal of Computer Science and Information Technologies, Vol. 39-No.13, 2012, pp.0975 - 8887. [4] Nguyễn Hữu Lộc, Cao Tùng Anh, Nguyễn Hoàng Tú Anh (2017), “Bảo toàn tính riêng tư trong khai thac CSDL phân tán dọc”, Hội thảo quốc gia về công nghệ thông tin và truyền thông, Quy Nhơn 23-24/11/2017, tr 18-23. [5] Nikunj Domadiya, Udai Pratap Rao (2019), “Privacy Preserving Distributed Association Rule Mining Approach on Vertically Partitioned Healthcare Data”, Procedia computer science 148, (2019), pp.303-312.