CHƯƠNG 1. TONG QUAN DE TÀI.1 Động lực nghiên cứu.2 Mục tiêu nghiên cứu 1.3 Đối tượng và phạm vi nghiên cứu 1.1 Đối tượng nghiên cứu 1.2 Phạm vi nghiên cứu 1. Phương pháp nghiên cứu 1.5 Quy trình thực hiện 1.6 Đóng góp của nghiên cứu. TONG QUAN VE TINH HÌNH NGHIÊN CỨU 2.
Khai thac TLIC 2. Khai thác TLIC với lợi nhuận âm 2. Khai thác TLIC có lợi nhuận âm trên CSDL phân tán dọc. Khai thác luật kết hop và tập mục thường xuyên bảo đảm riêng tư trên CSDL phân tán doc:.
Khoảng trồng nghiên cứu và tính mới của đề tài CHƯƠNG 3. Khai thác TLIC 3. KTDL bảo toàn riêng tư trên CSDL phân tán đọc. MÔ HÌNH ĐÈ XUẤT VÀ THỰC NGHIỆM.
Giải pháp và mô hình đề xuất 4. Các bước thực hiện mô hình 4. Thực hiện mô hình trên CSDL minh họa. KET QUA THỰC NGHIEM VÀ THẢO LUẬN 5.
Môi trường thực nghiệm. CSDL thực nghiệm. Chương trình thực nghiệm — Kết quả thực nghiệm. KET LUẬN VÀ HƯỚNG PHÁT TRIEN.
Hướng phát triển DANH MỤC CÔNG BÓ KHOA HỌC CỦA TÁC GIẢ. TAI LIEU THAM KHAO DANH MỤC TU VIET TAT `. Ký hiệu, từ viết tắt | Ý nghĩa tiếng anh Ý nghĩa tiếng việt CSDL Database Cơ sở dữ liệu DC Data Center Trung tâm khai thác dữ liệu en{item} Encrypt{item} Vector mã hóa một item FIs Frequent Itemsets Tập mục phô biến TLIC High Utility Itemsets Tap mục có độ hữu ich cao Ttemset Ttemset Tap muc KTDL Data mining Khai thác dữ liệu Min_util Minimum Utility Ngưỡng hữu ích tối thiểu Các bên tham gia vào quá trình khai MS Member site thác dữ liệu Transaction Identification TID Giao tác trong CSDL Database Total Transaction- Téng trong số độ hữu ích của giao TotalTWU : Weighted Utilization dich Transaction-Weighted. ¬ TWU Trọng sô độ hữu ích của giao dịch Utilization Transaction-Weighted Thuật toán khai thác trọng số độ TWU-mining ¬ Utilization mining hữu ich giao dich Weighted Itemset-Tidset.
WIT-tree Câu trúc dit liệu cây WIT-tree tree High utility-itemset with Tập lợi ich cao có lợi nhuận âm và TLIC-LNA-BTRT negative item and privacy- bảo toàn riêng tư preserving BTRT Privacy-preserving Bảo toàn riêng tư DANH MỤC BANG BIEU socơ Bảng 3.2 CSDL danh mục mặt hàng trong từng giao dịch Bảng 3.3 CSDL biểu diễn sự xuất hiện của từng item theo giao dịch .4 CSDL giao dịch minh họa D.5 Trọng số lợi nhuận của mỗi item trong CSDL giao dịch D.6 Bảng giá trị hữu ích của mỗi item trong từng giao dịch Bang 3.7 Giá trị hữu ích giao dịch trong CSDL, 21 Bang 3.8 Tập các mục phổ biến toàn cục và độ hỗ trợ 33 Bang 4.1 CSDL tập trung va Gia tri lợi nhuận của mỗi item 38 Bang 4.2 Giá trị twu tại CSDL tập trung 38 Bảng 4.3 Tidset, twu tai CSDL tập trung của các item thỏa ngưỡng min_util 39 Bang 4.4 CSDL giao dich và lợi nhuận của từng item tại MS1 Bảng 4.5 CSDL giao dịch và lợi nhuận của từng item tại MS2 Bảng 4.6 CSDL giao dịch và lợi nhuận của từng item tại MS3 Bang 5.1 Dữ liệu thực nghiệm Bang 5.2 Kết quả thực nghiệm. DANH MỤC HÌNH socơ Hình 2.1 Mô hình khai thác TLIC từ CSDL phân tán dọc Hình 3.1 WIT-tree với từng cấp độ k-itemset Hình 3.2 WIT-tree từ CSDL minh họa Hình 3.3 Thuật toán TWU-mining Hình 3.4 Minh họa kết quả thuật toán TWU-mining.5 Mô hình trao đồi dữ liệu giữa các Sitekx và DM Hình 3.6 CSDL minh hoạ phân tán tại 3 Site .1 Mô hình đề xuất khai thác TLIC-LNA-BTRT 36 39 42 45 Hình 5.3 Dataset BMS-POS.6 Dataset 3 — may 3 49 Hình 5.9 Biểu diễn sự xuất hiện của item theo giao dịch trong dataset l.10 Biểu diễn sự xuất hiện của item theo giao dich trong dataset 2.11 Biểu diễn sự xuất hiện của item theo giao dich trong dataset 3.12 Biểu diễn sự xuất hiện của item theo giao dịch trong dataset 4.13 Biểu diễn sự xuất hiện của item theo giao dich trong dataset 5.14 Thời gian chạy với BMS-POS .15 Thời gian chạy với Retais Hình 5.16 Thời gian chạy với Retails Accidents Hình 5.17 Kết quả TLIC trong bài báo [1] TÓM TẮT Hiện nay nghiên cứu về khai thác tập lợi ích cao có trọng số âm trên cơ sở dữ liệu phân tán dọc được các nhà nghiên cứu quan tâm. Đã có nhiều nghiên cứu đề xuất các thuật toán khai thác tập lợi ích cao, khai thác tập lợi ích cao có lợi nhuận âm trên cơ sở dữ liệu tập trung và cơ sở dữ liệu phân tán nhưng chưa có nghiên cứu nào đề xuất thuật toán khai thác tập lợi ích cao có lợi nhuận âm trên cơ sở dit liệu phân tán đọc, bảo toàn tính riêng tư của các bên tham gia. Trong luận văn này, tôi đề xuất một phương pháp khai thác tập lợi ích cao có lợi nhuận âm từ cơ sở dữ liệu phân tán dọc và bảo toàn tính riêng tư dữ liệu của các bên tham gia khai thác (TLIC-LNA-BTRT).
Phương pháp đề xuất sẽ không kết các cơ sở dir liệu từ dữ liệu cục bộ của các bên tham gia để hình thành cơ sở đữ liệu tập trung nhằm giảm thời gian khai thác. Mặt khác, trong dữ liệu thường chứa các thông tin nhạy cảm nên một số tổ chức (công ty) tuy rất muốn chia sẻ đữ liệu để khai thác được các kết quả mang lại lợi ích chung, nhưng mỗi bên lại muốn đảm bảo tính riêng tư cho dữ liệu nhạy cảm của riêng mình. Khai thác tập lợi ích cao có lợi nhuận âm trên cơ sở dữ liệu phân tán dọc bảo toàn tính riêng tư của chúng tôi đề xuất có thời gian khai thác nhanh và bảo toàn được tính riêng tư dit liệu của các bên tham gia khai thác. Từ khóa: tập lợi ích cao, lợi nhuận âm, khai thác dit liệu, cơ sở dữ liệu phân tán dọc, bảo toàn tính riêng tư.
ABSTRACT Currently, the research on mining High utility-itemsets with negative items in vertically distributed databases is of interest to researchers. There have been many studies to propose algorithms for mining high utility itemsets, mining high utility itemsets with a negative item on centralized and distributed databases, but no research has proposed such algorithms High utility-itemset with negative items and privacy- preserving in vertically distributed databases. In this dissertation, I propose a method to mine high utility itemsets with negative items from a vertically distributed database while preserving the privacy of 1 the data of mining parties (TLIC-LNA-BTRT). The proposed method will not join the databases of the local participants to create a centralized database to reduce the mining time.
On the other, the data often contains sensitive information, so some organizations (companies) want to share data to mine for mutual benefit, but each party wants privacy for its sensitive data too. Our proposed method of mining high utility itemsets with negative items and privacy-preserving attributes in a vertically distributed database has fast mining times and preserves the privacy of the parties data. Keywords: high-utility itemset mining, negative utility, data mining, vertically distributed database, privacy-preserving. Tổng quan dé tài CHUONG 1.
TONG QUAN DE TÀI 1.1 Động lực nghiên cứu Trong những năm gần đây, cùng với sự phát triển vượt bậc và nhanh chóng của khoa học kỹ thuật, với việc hàng loạt công nghệ mới được giới thiệu đã đóng góp hiệu quả vào quá trình phát triển đời sống con người: thương mại, giáo dục, y tế,. Theo đó, khi công nghệ càng phát triển, sẽ có một lượng lớn dữ liệu được thu thập, lưu trữ. Vi vậy, khai thác dit liệu (KTDL) — một giai đoạn quan trọng trong khám pha tri thức (KPTT), với việc tìm ra mối quan hệ lẫn nhau của lượng thông tin tiềm an, xuất hiện cùng nhau trong cơ sở dữ liệu (CSDL) lớn, tức là các tập mục phô biến (Frequent Itemsets - FIs) va su két hợp của các tập mục đó sẽ mang lại ý nghĩa thành công cho hoạt động kinh doanh của tổ chức, cá nhân. Khi đó, các khai thác tập hữu ích cao.
(TLIC - High Utility Itemsets) [2,3,9,10,13,16] đã được nhiều tác giả trong và ngoài nước nghiên cứu phát triển, được đề cập như là một bài toán mở rộng của quá trình khai thác FIs, mà ở đó, tính hữu ích cao được thê hiện thông qua giá trị lợi nhuận một FI xuất hiện trong CSDL giao dịch, được đo bằng tổng lợi nhuận mà doanh nghiệp thu về khi bán được FI đó, trong toàn CSDL giao dịch. Hiện nay, trong mô hình dữ liệu phân tán của doanh nghiệp, các bên thành viên tham gia trong cùng hệ thống sẽ khai thác dữ liệu thông qua hệ thống mạng được kết nối thông suốt. Trong mô hình KTDL phân tán, việc đảm bảo tính an toàn cho dữ liệu đã được dé cập [12] nhằm tránh lộ thông tin nhạy cảm, mang tính riêng tư của mỗi bên thành viên, ảnh hưởng đến quá trình kinh doanh. Lấy ví dụ, siêu thị X lưu trữ n mặt hàng (items) trong CSDL và cần thu thập, đồng bộ hoạt động giao dịch của tất cả khách hàng thông qua dữ liệu ghi nhận từ tat cả khu vực, các máy tính được kết nói mạng thông suốt.
Khi đó, đồng nghĩa với việc CSDL tập trung được phân tán ra cho từng khu vực (bên thành viên) thuộc hệ thống. Mỗi khách hàng có thể mua nhiều chủng loại mặt hàng khác nhau tại mỗi bên thành viên (khu vực bày bán: thực phâm, đồ tiêu dùng, vật dụng nhà bếp.) trong đó, mỗi mặt hàng có trọng số lợi nhuận khác nhau, ảnh hưởng nhất định đến lợi nhuận của một tập giao dịch. Ngày nay, do việc cạnh tranh giữa các công ty trở nên ngày càng gay gắt, các chiến dịch khuyến mãi cùng với vô vàn ưu đãi tối đa cho người dùng, với mục tiêu là 3 Tổng quan dé tài kích cầu mua hàng, vì thế một số sản phẩm khuyến mãi đính kèm sản phẩm chính không tránh đến việc lỗ và tạo ra khoản đơn vị lợi nhuận âm. Ngoài ra các công ty cũng có thé hạ giá bán thấp hơn giá mua của một số sản phẩm dé thu hồi vốn va từ đó phát sinh các đơn vị lợi nhuận âm.
Việc khám phá và khai thác hiệu quả tính hữu ích của các tập mục phô biến trong dữ liệu giao dịch phân tán khổng lồ này sẽ mang tính quyết định, thúc đây hoạt động sắp xếp, phân bổ hàng hóa một cách chủ động. nhằm tác động tích cực đến quyết định mua hàng của người tiêu dùng, góp phần cải thiện hoạt động kinh doanh, giảm chi phí vận hành nhưng lợi nhuận sé gia tăng. Tuy nhiên, một vấn đề khác đặt ra trong bài toán khai thác dữ liệu này chính là thông tin của các bên tham gia cung cấp dữ liệu trong quá trình khai thác phải được bảo mật tính riêng tư về chính sách dit liệu của mỗi bên.