Đề án tốt nghiệp Thạc sĩ Kỹ thuật: Nghiên cứu phương pháp ẩn các tập mục có độ hữu ích trung bình cao nhạy cảm trong cơ sở dữ liệu giao tác

Chia sẻ: Cảnh Phương Thanh | Ngày: | Loại File: PDF | Số trang:79

Thêm vào BST

Báo xấu

7
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề án "Nghiên cứu phương pháp ẩn các tập mục có độ hữu ích trung bình cao nhạy cảm trong cơ sở dữ liệu giao tác" nhằm nghiên cứu các phương pháp ẩn tập mục có độ hữu ích trung bình cao nhạy cảm hiện có dựa trên các công trình đã công bố gần đây. Từ đó chỉ ra những ưu điểm và hạn chế của nó để đề xuất giải pháp hiệu quả hơn về mặt thời gian chạy cũng như các phép đo về mặt hiệu ứng phụ tạo ra bởi quá trình ẩn. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề án tốt nghiệp Thạc sĩ Kỹ thuật: Nghiên cứu phương pháp ẩn các tập mục có độ hữu ích trung bình cao nhạy cảm trong cơ sở dữ liệu giao tác

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Tô Phú Khương NGHIÊN CỨU PHƯƠNG PHÁP ẨN CÁC TẬP MỤC CÓ ĐỘ HỮU ÍCH TRUNG BÌNH CAO NHẠY CẢM TRONG CƠ SỞ DỮ LIỆU GIAO TÁC ĐỀ ÁN THẠC SĨ KỸ THUẬT (Theo định hướng ứng dụng) TP.HỒ CHÍ MINH – NĂM 2023
ii HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Tô Phú Khương NGHIÊN CỨU PHƯƠNG PHÁP ẨN CÁC TẬP MỤC CÓ ĐỘ HỮU ÍCH TRUNG BÌNH CAO NHẠY CẢM TRONG CƠ SỞ DỮ LIỆU GIAO TÁC Chuyên ngành: Hệ thống thông tin Mã số: 8.48.01.04 ĐỀ ÁN THẠC SĨ KỸ THUẬT (Theo định hướng ứng dụng) NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. NGUYỄN KHẮC CHIẾN TP.HỒ CHÍ MINH - NĂM 2023
i LỜI CAM ĐOAN Tôi cam đoan đề án: “Nghiên cứu phương pháp ẩn các tập mục có độ hữu ích trung bình cao nhạy cảm trong cơ sở dữ liệu giao tác” là công trình nghiên cứu của chính tôi. Các số liệu được sử dụng trong đề án là trung thực và chính xác. Ngoài những nội dung nghiên cứu của đề án, các vấn đề được trình bày đều là những tìm hiểu và nghiên cứu của tôi hoặc là được trích dẫn từ các nguồn tài liệu có ghi tham khảo rõ ràng, hợp pháp. Trong đề án, tôi có tham khảo một số tài liệu của một số tác giả được liệt kê tại danh mục tài liệu tham khảo. TP.HCM, Ngày 12 tháng 10 năm 2023 Học viên thực hiện đề án Tô Phú Khương
ii LỜI CẢM ƠN Trong suốt quá trình học tập và nghiên cứu thực hiện đề án tốt nghiệp thạc sĩ, ngoài nỗ lực của bản thân, tôi đã nhận được sự hướng dẫn nhiệt tình quý báu của quý Thầy Cô, cùng với sự động viên và ủng hộ của gia đình, bạn bè và đồng nghiệp. Với lòng kính trọng và biết ơn sâu sắc, tôi xin gửi lời cảm ơn chân thành tới: Thầy TS. Nguyễn Khắc Chiến, người thầy kính yêu đã hết lòng giúp đỡ, hướng dẫn, động viên, tạo điều kiện cho tôi trong suốt quá trình thực hiện và hoàn thành đề án tốt nghiệp thạc sĩ. Ban Giám đốc, Phòng Đào tạo sau đại học và quý Thầy Cô đã tạo mọi điều kiện thuận lợi giúp tôi hoàn thành đề án. Tôi xin chân thành cảm ơn gia đình, bạn bè, đồng nghiệp trong cơ quan đã động viên. Hỗ trợ tôi trong lúc khó khăn để tôi có thể học tập và hoàn thành đề án. Mặc dù đã có nhiều cố gắng, nỗ lực, nhưng do thời gian và kinh nghiệm nghiên cứu khoa học còn hạn chế nên không thể tránh khỏi những thiếu sót. Tôi rất mong nhận được sự góp ý của quý Thầy Cô cùng bạn bè đồng nghiệp để kiến thức của tôi ngày một hoàn thiện hơn. Xin chân thành cảm ơn! TP.HCM, Ngày 12 tháng 10 năm 2023 Học viên thực hiện đề án Tô Phú Khương
iii MỤC LỤC LỜI CAM ĐOAN ....................................................................................................... i LỜI CẢM ƠN ............................................................................................................ii MỤC LỤC ................................................................................................................ iii DANH MỤC CÁC THUẬT NGỮ, CHỮ VIẾT TẮT ............................................ v DANH SÁCH BẢNG ..............................................................................................vii DANH SÁCH HÌNH VẼ ....................................................................................... viii MỞ ĐẦU .................................................................................................................... 1 1. Lý do chọn đề tài ..................................................................................................1 2. Tổng quan về vấn đề nghiên cứu .........................................................................2 3. Mục tiêu nghiên cứu của đề tài ............................................................................6 4. Đối tượng nghiên cứu ..........................................................................................6 5. Những nội dung chính yếu cần nghiên cứu .........................................................6 CHƯƠNG 1: MỘT SỐ VẤN ĐỀ LIÊN QUAN ĐẾN TẬP MỤC CÓ ĐỘ HỮU ÍCH TRUNG BÌNH CAO ......................................................................................... 8 1.1. Các khái niệm liên quan đến khai thác tập mục có độ hữu ích trung bình cao 8 1.1.1. Khai phá tri thức và khai thác dữ liệu ......................................................8 1.1.1.1. Các bước chính của quá trình khai phá dữ liệu ..................................8 1.1.1.2. Kiến trúc một hệ thống khai phá dữ liệu ..........................................10 1.1.1.3. Ứng dụng của khai phá dữ liệu ........................................................13 1.1.2. Khai phá tập mục độ hữu ích trung bình cao .........................................13 1.1.3. Ứng dụng khai thác tập mục độ hữu ích trung bình cao ........................16 1.1.4. Phương pháp khai phá tập mục hữu ích trung bình cao ........................16 1.2. Bài toán ẩn tập mục có độ hữu ích trung bình cao .........................................19 1.3. Một số thuật toán khai phá tập mục độ hữu ích trung bình cao .....................22 1.4. Kết luận Chương 1 ..........................................................................................23 CHƯƠNG 2: PHƯƠNG PHÁP ẨN TẬP MỤC CÓ ĐỘ HỮU ÍCH TRUNG BÌNH CAO NHẠY CẢM ....................................................................................... 24
iv 2.1. Phương pháp khai thác tập mục có độ hữu ích trung bình cao nhạy cảm ......24 2.2. Tác dụng phụ ..................................................................................................26 2.3. Phương pháp ẩn các tập mục có độ hữu ích trung bình cao nhạy cảm...........29 2.4. Ưu điểm và hạn chế của các phương pháp .....................................................38 2.5. Kết luận Chương 2 ..........................................................................................40 CHƯƠNG 3: ĐỀ XUẤT PHƯƠNG PHÁP HIỆU QUẢ ĐỂ ẨN TẬP MỤC CÓ ĐỘ HỮU ÍCH TRUNG BÌNH CAO NHẠY CẢM .............................................. 41 3.1. Một số thông số dùng để đánh giá tính hiệu quả của phương pháp ẩn các tập mục có độ hữu ích trung bình cao nhạy cảm. ........................................................41 3.1.1. Xác định giá trị hữu ích tối thiểu cần giảm hay xóa mục: .......................42 3.1.2. Xác định mục mục tiêu và hệ số :..........................................................42 3.2. Đề xuất phương pháp ẩn tập phổ biến có độ hữu ích trung bình cao nhạy cảm hiệu quả. .................................................................................................................43 3.3. Kết luận Chương 3 ..........................................................................................50 CHƯƠNG 4: THỬ NGHIỆM VÀ ĐÁNH GIÁ ................................................... 51 4.1. Môi trường thực nghiệm và dữ liệu sử dụng ..................................................51 4.2. Kết quả thực nghiệm .......................................................................................51 a. Thời gian thực thi ..........................................................................................52 b. DSS (Tỷ lệ tương đồng về cấu trúc của CSDL sửa đổi D' so với CSDL gốc D) ..................................................................................................................53 c. DUS (Tỷ lệ tương đồng về hữu ích giữa CSDL D' với CSDL D) ..................54 d. IUS (Tỷ lệ tương đồng về hữu ích trung bình của tập các HAUI trong CSDL sửa đổi D' (HAUIs') so với tập các HAUI trong CSDL gốc D (HAUIs)). ........55 4.3. Kết luận Chương 4. .........................................................................................56 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ............................................................. 57 DANH MỤC TÀI LIỆU THAM KHẢO ............................................................... 58
v DANH MỤC CÁC THUẬT NGỮ, CHỮ VIẾT TẮT Viết tắt Tiếng Anh Tiếng Việt CSDL Database Cơ sở dữ liệu DIF Difference Sự khác biệt Database Structure Tỷ lệ tương đồng về cấu trúc của CSDL DSS Similarity. sửa đổi D' so với CSDL gốc D. Tỷ lệ tương đồng về hữu ích giữa DUS Database utility similarity CSDL D' với CSDL D High Average Utility HAUI Tập mục hữu ích trung bình cao Itemset High Average Utility Khai thác tập mục có độ hữu ích HAUIM Itemset Mining trung bình cao Tỷ lệ tập mục hữu ích trung bình HF Hiding Failure cao nhạy cảm không ẩn được Tỷ lệ tương đồng về hữu ích trung bình của tập các HAUIs trong CSDL IUS Itemsets Utility Similarity sửa đổi D' so với tập các HAUIs trong CSDL gốc D Knowledge Discovery KDD Phát hiện tri thức từ CSDL in Databases KPDL Data Mining Khai phá dữ liệu Tỷ lệ tập mục hữu ích trung bình MC Miss Cost cao không nhạy cảm bị mất Privacy Preserving Bảo vệ tính riêng tư trong khai phá PPAUIM Average Utility Itemset tập mục hữu ích trung bình cao Mining Privacy Preserving Data Khai phá dữ liệu bảo vệ quyền PPDM Mining riêng tư
vi Quantitative QTDB Cơ sở dữ liệu giao tác định lượng Transaction Database Sensitive High Average Tập mục hữu ích trung bình cao SHAUI Utility Itemset nhạy cảm
vii DANH SÁCH BẢNG Bảng 1.1: Cơ sở dữ liệu giao tác (biểu diện dạng ngang) .................................... 14 Bảng 1.2: Cơ sở dữ liệu giao tác (biểu diễn dạng dọc) ........................................ 15 Bảng 1.3: Cơ sở dữ liệu giao tác (biểu diễn dạng ma trận).................................. 15 Bảng 1.4: CSDL giao tác D.................................................................................. 20 Bảng 1.5: Giá trị lợi nhuận của CSDL D ............................................................. 21 Bảng 1.6: Tập mục hữu ích trung bình cao HAUIs ............................................. 21 Bảng 2.1: Xác định tập ST chứa giao tác hỗ trợ S1 ............................................. 32 Bảng 2.2: CSDL giao tác D.................................................................................. 33 Bảng 2.3: Tập mục hữu ích trung bình cao .......................................................... 34 Bảng 2.4: Xác định tập ST chứa giao tác hỗ trợ S2 ............................................. 34 Bảng 2.5: CSDL giao tác D.................................................................................. 35 Bảng 2.6: Tập mục hữu ích trung bình cao .......................................................... 36 Bảng 2.7: Xác định tập ST chứa giao tác hỗ trợ S3 ............................................. 36 Bảng 2.8: CSDL giao tác D.................................................................................. 37 Bảng 2.9: Tập mục hữu ích trung bình cao .......................................................... 37 Bảng 3.1: T-table .................................................................................................. 45 Bảng 3.2: Xác định tập ST chứa giao tác hỗ trợ S1 ............................................. 46 Bảng 3.3: CSDL giao tác D.................................................................................. 47 Bảng 3.4: Tập mục hữu ích trung bình cao .......................................................... 47 Bảng 3.5: Xác định tập ST chứa giao tác hỗ trợ S2 ............................................. 48 Bảng 3.6: CSDL giao tác D.................................................................................. 49 Bảng 3.7: Tập mục hữu ích trung bình cao .......................................................... 49 Bảng 4.1: Cơ sở dữ liệu dùng cho thực nghiệm ................................................... 51
viii DANH SÁCH HÌNH VẼ Hình 1.1: Khai thác dữ liệu là một bước trong quá trình khám phá tri thức ................. 9 Hình 1.2: Kiến trúc hệ thống khai thác dữ liệu ........................................................... 11 Hình 2.1. Quy trình PPUM chung ............................................................................... 24 Hình 2.2. Mối quan hệ giữa các tập mục trước và sau quá trình PPDM..................... 26 Hình 2.3. Tập hợp các tập mục nhạy cảm mà quy trình PPDM không ẩn được ......... 27 Hình 2.4. Mising cost do quy trình làm sạch .............................................................. 27 Hình 2.5. Artificial cost phát sinh từ quy trình PPDM ............................................... 28 Hình 4.1: Kết quả so sánh thời gian thực thi của hai thuật toán ................................. 52 Hình 4.2: DSS Tỷ lệ tương đồng về cấu trúc dữ liệu khi thực hiện ẩn ...................... 53 Hình 4.3: DUS Tỷ lệ tương đồng về giá trị hữu ích của CSDL khi thực hiện ẩn ...... 54 Hình 4.4: IUS Tỷ lệ tương đồng về giá trị hữu ích trung bình của tập SHAUIs giữa CSDL gốc D và CSDL sửa đổi D' khi thực hiện ẩn .................................................... 55
1 MỞ ĐẦU 1. Lý do chọn đề tài Bài toán khai thác tập mục có độ hữu ích cao trong cơ sở dữ liệu (CSDL) giao tác đã trở thành một vấn đề quan trọng trong những thập kỷ gần đây. Trong khai thác tập mục có độ hữu ích cao truyền thống, độ hữu ích của một tập mục được định nghĩa là tổng các hữu ích của các mục của nó, trong các giao tác mà nó xuất hiện. Một vấn đề quan trọng với định nghĩa này là nó không tính đến độ dài của tập mục. Bởi vì độ hữu ích của tập mục lớn thường lớn hơn độ hữu ích của tập mục nhỏ, thuật toán khai thác tập mục có độ hữu ích cao truyền thống có xu hướng thiên về việc tìm kiếm một tập hợp các tập mục lớn. Vì vậy, định nghĩa này không phải là một phép đo hợp lý về độ hữu ích. Để cung cấp một đánh giá tốt hơn về độ hữu ích của từng tập mục, bài toán khai thác tập mục độ hữu ích trung bình cao đã được đề xuất. Nó giới thiệu phép đo độ hữu ích trung bình, xem xét cả độ dài của tập mục và độ hữu ích của chúng, và do đó phù hợp hơn trong các tình huống thực tế. Khai thác tập mục có độ hữu ích trung bình cao (HAUIM) bao gồm phân tích cơ sở dữ liệu giao tác định lượng của khách hàng để xác định các tập mục độ hữu ích trung bình cao, đó là tập hợp các mục có độ hữu ích trung bình cao (ví dụ: Lợi nhuận). Nhiều thuật toán đã được thiết kế để nhận dạng cái mới, hữu ích và những mẫu bất ngờ trong dữ liệu, có thể giúp hiểu dữ liệu, hỗ trợ ra quyết định và cung cấp thông tin chi tiết về sở thích của người dùng. Tuy nhiên, một vấn đề chính là tri thức được phát hiện bởi các kỹ thuật này cũng có thể tiết lộ thông tin riêng tư, nhạy cảm hoặc thông tin chiến lược như thông tin thẻ tín dụng, các mẫu mua hàng từ các cá nhân và số nhận dạng cá nhân. Do đó, các cá nhân có thể phải đối mặt với các mối đe dọa về quyền riêng tư và dữ liệu của họ có thể bị lạm dụng. Điều quan trọng nữa là bảo vệ thông tin riêng tư và nhạy cảm của các doanh nghiệp mang lại cho họ lợi thế chiến lược so với đối thủ cạnh tranh cũng như bảo vệ quyền riêng tư của nhân viên và khách hàng của họ. Chẳng hạn, nếu một công ty công khai dữ liệu hoặc chia sẻ dữ liệu với các cộng tác viên, thì có nguy cơ một số thông tin nhạy cảm có thể bị trích xuất từ đó
2 bằng thuật toán khai phá dữ liệu. Để giải quyết mối lo ngại này, bài toán ẩn các tập mục có độ hữu ích trung bình cao được nghiên cứu, đó là sửa đổi cơ sở dữ liệu giao tác để đảm bảo rằng các tập mục có độ hữu ích trung bình cao nhạy cảm không thể bị phát hiện. Tập mục hữu ích trung bình cao nhạy cảm là tập mục được sử dụng để hỗ trợ ra quyết định. Thông tin này rất quan trọng đối với chủ sở hữu cơ sở dữ liệu. Nếu nó bị phát hiện bởi các đối thủ cạnh tranh, hoạt động kinh doanh của chủ sở hữu cơ sở dữ liệu có thể bị ảnh hưởng. Để đảm bảo rằng thông tin này được bảo toàn, tập mục hữu ích trung bình cao nhạy cảm phải được ẩn khỏi cơ sở dữ liệu trước khi được chia sẻ ra bên ngoài. Xuất phát từ những lý do trên, tôi chọn đề tài “Nghiên cứu phương pháp ẩn các tập mục có độ hữu ích trung bình cao nhạy cảm trong cơ sở dữ liệu giao tác” làm đề tài nghiên cứu cho đề án tốt nghiệp của mình. 2. Tổng quan về vấn đề nghiên cứu Các kỹ thuật khai phá dữ liệu trong đó có các kỹ thuật khai thác tập mục có độ hữu ích trung bình cao đã đóng một vai trò quan trọng để phân tích CSDL giao tác. Nhiều thuật toán đã được thiết kế để rút trích ra tri thức mới, hữu ích và những mẫu bất ngờ trong dữ liệu, có thể giúp người sử dụng hiểu dữ liệu, hỗ trợ ra quyết định và cung cấp thông tin chi tiết về sở thích của người dùng. Khai thác tập mục có độ hữu ích trung bình cao sử dụng độ hữu ích trung bình để loại bỏ sự phụ thuộc của ràng buộc độ dài vào hữu ích tập mục. TPAU [1] là thuật toán khai thác HAUI đầu tiên, về bản chất là hai pha. TPAU xác định giới hạn trên được gọi là giới hạn trên độ hữu ích trung bình (AUUB) để duy trì tính chất downward closure. Nếu giá trị AUUB của một tập mục không thỏa ngưỡng độ hữu ích trung bình tối thiểu, thì tập mục đó và tất cả các tập cha (supersets) của nó không thể là HAUI. TPAU thực hiện tìm kiếm theo cấp độ đòi hỏi thời gian chạy dài. Một giải pháp khác, PBAU [5] phát triển một kỹ thuật dựa trên phép chiếu và cấu trúc lập chỉ mục để tăng tốc quá trình khai thác HAUI. Ngoài PBAU, Lan và cộng sự [4] đã trình
3 bày một giới hạn trên chặt chẽ hơn dựa trên khái niệm tiền tố để giảm số lượng tập mục ứng viên. Tien Lu [12] đã đề xuất một thuật toán HAUI dựa trên cây sử dụng cây HAUI và một cấu trúc mới cho các tập mục để tăng tốc độ tính toán. HAUI- growth [7] là một thuật toán khai thác HAUI dựa trên cây khác để tránh quét cơ sở dữ liệu nhiều lần. Ngoài ra, mỗi nút trong cây duy trì một mảng để giữ thông tin về độ hữu ích trung bình của các tập mục. Sau đó, thuật toán HAUI-Miner [8] một pha hiệu quả được trình bày kết hợp cấu trúc danh sách có tên là danh sách độ hữu ích trung bình (AU) để khai thác HAUI. Nó áp dụng mô hình AUUB để loại bỏ các ứng viên yếu khỏi không gian tìm kiếm. EHAUPM [10] là một thuật toán khác để khai thác HAUI, thuật toán này bổ sung hai giới hạn trên chặt chẽ hơn có tên là Tiện ích giới hạn trên lỏng lẻo hơn (Looser Upper - Bound Utility - LUB) và Giới hạn trên chặt chẽ hơn được sửa đổi (Revised Tighter Upper Bound - RTUB) để loại bỏ đáng kể các tập mục ứng viên không tiềm năng. Ngoài ra, nó kết hợp một cấu trúc danh sách mới được gọi là danh sách độ hữu ích trung bình được sửa đổi (MAU) và các chiến lược cắt tỉa khác nhau để cải thiện hiệu suất. Trong khi đó, MHAI [21] đã đưa ra một cấu trúc danh sách mới HAI-list và nhiều chiến lược cắt tỉa để thúc đẩy quá trình khai thác HAUI. Một số công trình nghiên cứu khác về vấn đề khai thác HAUI đã được thảo luận trong [11], [15], [16], [19]. HAUIM có ứng dụng trong nhiều lĩnh vực. Chẳng hạn, HAUIM có thể được sử dụng trong bối cảnh kinh doanh để tiếp thị chéo và phát triển các chiến lược quảng bá mới để tăng doanh số bán các sản phẩm có lợi nhuận cao [17], để phân tích dữ liệu phát trực tuyến (ví dụ: Phân tích luồng nhấp chuột vào web dựa trên thời gian dành cho mỗi trang web), và để khám phá các mẫu gen quan trọng trong dữ liệu y tế [22]. Nhưng các HAUI được tìm thấy trong CSDL giao tác có thể tiết lộ thông tin cá nhân hoặc chiến lược, điều này có thể gây ra vấn đề. Ví dụ: Một công ty thương mại điện tử có thể muốn chia sẻ dữ liệu về các giao tác khách hàng của mình với một công ty khác dưới dạng CSDL giao tác để cộng tác nhưng có thể không muốn tiết lộ các mẫu có lợi nhất (HAUI) xuất hiện trong dữ liệu để công ty kia không thể sử dụng thông tin này để làm lợi thế cho mình. Đây là một mối quan tâm quan trọng vì dữ liệu do
4 các công ty thu thập về khách hàng đặc biệt khó thu thập và có giá trị đối với các nhiệm vụ khác nhau như giới thiệu sản phẩm. Do đó, mong muốn có quyền kiểm soát những gì có thể tìm thấy trong dữ liệu bằng thuật toán HAUIM. Ví dụ thứ hai là dữ liệu được thu thập từ các công cụ tìm kiếm lớn về các truy vấn tìm kiếm. Một truy vấn tìm kiếm có thể được biểu diễn dưới dạng một CSDL giao tác trong đó mỗi giao tác là một tập hợp các từ khóa trong một truy vấn và trong đó độ hữu ích của các từ khóa có thể là thước đo tầm quan trọng của các từ (ví dụ: Tần suất thuật ngữ). Vì dữ liệu truy vấn tìm kiếm rất có giá trị đối với doanh nghiệp, nên việc ẩn các liên kết quan trọng giữa các từ khóa trước khi công khai dữ liệu truy vấn tìm kiếm để giữ lợi thế cạnh tranh cũng là điều hợp lý. Do đó, như được thúc đẩy bởi những ví dụ này, việc chia sẻ một CSDL giao tác có thể dẫn đến các mối đe dọa về quyền riêng tư, bảo mật hoặc tổn thất lợi nhuận. Do đó, rõ ràng cần phải ẩn các HAUI nhạy cảm để ngăn người dùng trái phép phát hiện ra chúng. Ẩn tập mục hữu ích trung bình cao nhạy cảm là công việc nhằm mục đích che giấu các thông tin riêng tư/nhạy cảm mà chủ sở hữu không muốn chúng bị khai thác bởi các thuật toán HAUIM, để tránh các rủi ro gặp phải khi các thông tin này bị khai thác và sử dụng vào các mục đích mà có thể gây ra các tác động xấu cho chủ sở hữu CSDL hoặc các cá nhân có liên quan. Năm 2018, các tác giả trong [2] đề xuất phương pháp và thuật toán ẩn tập mục hữu ích trung bình cao nhạy cảm có tên là HHAUSI. Phương pháp tiếp cận của thuật toán này là sửa cơ sở dữ liệu gốc để giảm giá trị hữu ích trung bình của tập mục nhạy cảm xuống thấp hơn ngưỡng hữu ích trung bình tối thiểu. Thuật toán HHAUSI sử dụng ba đơn vị đo lường để đánh giá hiệu ứng phụ của thuật toán, gồm: HF (Tỷ lệ tập mục hữu ích trung bình cao nhạy cảm không ẩn được); MC (Tỷ lệ tập mục hữu ích trung bình cao không nhạy cảm bị mất); DIF (Tỷ lệ sai khác giữa CSDL gốc so với CSDL sửa đổi). Phương pháp chọn mục mục tiêu và giao tác mục tiêu để sửa dữ liệu của thuật toán HHAUSI là tương tự như thuật toán HHUIF [20] nên hiệu ứng phụ của thuật toán vẫn còn cao, bởi vì phương pháp lựa chọn mục mục tiêu và giao tác mục tiêu để sửa của thuật toán HHUIF là dựa vào mục có độ hữu ích cao nhất. Để giải quyết hạn chế của thuật toán HHAUSI, công trình của Huỳnh
5 Triệu Vỹ và cộng sự [18] đã đề xuất thuật toán có tên gọi là EHSHA-UI, thuật toán EHSHA-UI sử dụng các phương pháp chọn lựa mục mục tiêu và giao tác mục tiêu khác nhau cho từng trường hợp mục mục tiêu được xóa và sửa để giảm hiệu ứng phụ. Để giảm thiểu hiệu ứng phụ của quá trình sửa đổi dữ liệu gây ra, nhóm tác giả sử dụng các phương pháp lựa chọn mục mục tiêu và giao tác mục tiêu khác nhau cho trường hợp giảm giá trị hữu ích nội của mục mục tiêu và trường hợp xóa mục mục tiêu. Mặc dù kết quả thực nghiệm của thuật toán EHSHA-UI mang lại một số hiệu quả nhất định, tuy nhiên thời gian thực hiện của thuật toán EHSHA-UI cũng như các hiệu ứng phụ vẫn được sinh ra đáng kể. Trong công trình [6] nghiên cứu vấn đề ẩn các HAUI phổ biến (FHAUI) trong một CSDL giao tác. Bài toán này bao gồm việc sửa đổi cơ sở dữ liệu để ẩn tất cả các FHAUI đối với ngưỡng hỗ trợ và độ hữu ích tối thiểu nhất định, được ký hiệu là ms và ms. Trong công trình này, FHAUI là tập mục có độ hữu ích trung bình cao có tần số xuất hiện không nhỏ hơn ms. Lý do để xem xét không chỉ độ hữu ích trung bình mà cả tần suất xuất hiện là do các ràng buộc về tần suất cũng được sử dụng theo cách truyền thống trong khai thác mẫu để lọc ra các mẫu nhiễu (có thể xuất hiện tình cờ hoặc không đáng kể do tần suất xuất hiện thấp của chúng). Ví dụ: Nếu một số hành vi của khách hàng chỉ được quan sát một vài lần trong cơ sở dữ liệu giao tác của khách hàng hoặc nếu một số từ khóa chỉ xuất hiện một vài lần trong các truy vấn tìm kiếm, những mẫu đó có thể bị bỏ qua. Do đó, ẩn các mẫu bằng cách xem xét cả hai yếu tố (độ hữu ích và tần số xuất hiện) hơn là chỉ xem xét một yếu tố. Bài báo này giải quyết những vấn đề này bằng cách thiết kế một thuật toán hiệu quả cho FHAUIH có tên là H-FHAUI. Thuật toán sử dụng cách tiếp cận biên lấy ý tưởng từ công việc trước đó về ẩn tập mục phổ biến [14] trong đó tính chất downward closure của phép đo độ hỗ trợ được sử dụng để giảm không gian tìm kiếm. Tuy nhiên, việc mở rộng cách tiếp cận biên này cho bài toán FHAUIH không dễ dàng bởi vì hàm độ hữu ích trung bình không thỏa mãn tính chất downward closure. Nghiên cứu này đề xuất một đường biên dưới mở rộng, được áp dụng cho các giới hạn trên yếu trên au và được
6 tích hợp vào thuật toán H-FHAUI được đề xuất để ẩn các FHAUI một cách hiệu quả bằng cách chỉ ẩn một tập hợp con nhỏ các FHAUI. Tuy nhiên, trong đề án này, tôi chỉ tập trung xem xét một yếu tố là độ hữu ích trung bình cao dùng để ẩn các tập mục có độ hữu ích trung bình cao trong CSDL giao tác. Phương pháp đề xuất trong đề án này sẽ tập trung so sánh, đánh giá với các thuật toán trong công trình năm 2018 [2] và năm 2021 [18]. Mục tiêu của đề án là đề xuất được phương pháp ẩn các tập mục có độ hữu ích trung bình cao nhạy cảm trong CSDL giao tác sao cho giảm thời gian thực hiện cũng như giảm thiểu các hiệu ứng phụ: Tạo ra tập mục mới, ẩn nhầm các tập mục không nhạy cảm khác, giảm tối thiểu sự sai khác giữa CSDL trước và sau khi sửa đổi,… 3. Mục tiêu nghiên cứu của đề tài Nghiên cứu các phương pháp ẩn tập mục có độ hữu ích trung bình cao nhạy cảm hiện có dựa trên các công trình đã công bố gần đây. Từ đó chỉ ra những ưu điểm và hạn chế của nó để đề xuất giải pháp hiệu quả hơn về mặt thời gian chạy cũng như các phép đo về mặt hiệu ứng phụ tạo ra bởi quá trình ẩn. 4. Đối tượng nghiên cứu - Các kỹ thuật khai thác tập mục có độ hữu ích trung bình cao trong CSDL giao tác. - Các kỹ thuật ẩn các tập mục có độ hữu ích trung bình cao nhạy cảm trong CSDL giao tác. 5. Những nội dung chính yếu cần nghiên cứu - Nghiên cứu và tìm hiểu những công trình đã công bố liên quan đến khai thác tập mục có độ hữu ích trung bình cao (HAUI). - Nghiên cứu và tìm hiểu những công trình liên quan bài toán ẩn các tập mục có độ hữu ích trung bình cao nhạy cảm trong cơ sở dữ liệu giao tác: Chỉ ra được những ưu điểm và hạn chế của nó, từ đó đề xuất hướng nghiên cứu tiếp theo.
7 - Tìm hiểu các thông số đánh giá tính hiệu quả của các phương pháp ẩn tập mục có độ hữu ích trung bình cao nhạy cảm trong cơ sở dữ liệu giao tác. - Tiến hành cài đặt phương pháp ẩn tập mục có độ hữu ích trung bình cao nhạy cảm đề xuất để so sánh với các phương pháp cùng loại khác. - Thực nghiệm trên các cơ sở dữ liệu giao tác được lấy trên trang web http://www.philippe-fournier-viger.com/spmf/index.php?link=datasets.php. - Môi trường thực nghiệm: Máy vi tính cài hệ điều hành Win 10 và ngôn ngữ lập trình là Java, Python,…
8 CHƯƠNG 1: MỘT SỐ VẤN ĐỀ LIÊN QUAN ĐẾN TẬP MỤC CÓ ĐỘ HỮU ÍCH TRUNG BÌNH CAO 1.1. Các khái niệm liên quan đến khai thác tập mục có độ hữu ích trung bình cao 1.1.1. Khai phá tri thức và khai thác dữ liệu Khai phá tri thức là việc rút trích tri thức một cách tự động và hiệu quả từ một khối dữ liệu lớn. Tri thức đó thường ở dạng các mẫu có tính chất không tầm thường, không tường minh chưa được biết đến và có tiềm năng mang lại lợi ích. “Phát hiện tri thức trong CSDL là một quá trình không tầm thường nhận ra những mẫu có giá trị, mới, hữu ích tiềm năng và hiểu được trong dữ liệu” [3]. Là lĩnh vực nghiên cứu và triển khai được phát triển nhanh chóng và rộng lớn, lại được rất nhiều nhóm nghiên cứu tại nhiều địa điểm khác nhau trên thế giới đồng thời quan tâm, nên tồn tại rất nhiều cách tiếp cận khác nhau đối với lĩnh vực KDD. Vì lý do đó mà trong nhiều tài liệu, các nhà khoa học trên thế giới đã sử dụng nhiều thuật ngữ khác nhau mà chúng được coi là mang cùng nghĩa với KDD như chiết lọc tri thức (knowledge extraction), phát hiện thông tin (information discovery), thu hoạch thông tin (information harvesting), khai quật dữ liệu (data archaeology) và xử lý mẫu dữ liệu (data pattern processing). Mô hình quá trình khai phá dữ liệu cũng được cải tiến, phù hợp với mục tiêu kinh doanh và mục tiêu phát triển của từng tổ chức. Tồn tại một số mô hình thiên hướng công nghệ. 1.1.1.1. Các bước chính của quá trình khai phá dữ liệu Nhiều người xem khai thác dữ liệu như là một từ đồng nghĩa với một thuật ngữ phổ biến được sử dụng, khám phá tri thức từ dữ liệu, hoặc KDD, trong khi những người khác xem khai thác dữ liệu chỉ đơn thuần là một bước cần thiết trong quá trình khám phá tri thức. Quá trình khám phá tri thức được thể hiện trong Hình 1.1 là một chuỗi lặp đi lặp lại các bước sau:
9 Evaluation & Presentation Data Mining Knowledge Selection & Transformation Cleaning & Integration Data warehouse Data Base Fla t file s Bước 1: Trích Bước 2: Tiền Bước 3: Chuyển Bước 4: Khai Bước 5: Đánh giá và lọc dữ liệu xử lý dữ liệu đổi dữ liệu phá dữ liệu biểu diễn tri thức Hình 1.1: Khai thác dữ liệu là một bước trong quá trình khám phá tri thức Làm sạch dữ liệu (để loại bỏ nhiễu và dữ liệu không phù hợp). Tích hợp dữ liệu, nơi mà nhiều nguồn dữ liệu có thể được kết hợp (Một xu hướng phổ biến trong ngành công nghiệp thông tin là để thực hiện làm sạch dữ liệu và tích hợp dữ liệu như là một bước tiền xử lý, nơi mà các dữ liệu kết quả được lưu trữ trong một kho dữ liệu). Chọn lựa dữ liệu, nơi dữ liệu có liên quan đến nhiệm vụ phân tích được lấy từ cơ sở dữ liệu: Là bước trích chọn những tập dữ liệu cần được khai phá từ các tập dữ liệu lớn (databases, data warehouses, data repositories) ban đầu theo một số tiêu chí nhất định. Bước 1: Biến đổi dữ liệu, nơi mà dữ liệu được biến đổi và hợp nhất thành các hình thức thích hợp cho khai thác bằng cách thực hiện tóm tắt hoặc tập hợp các hoạt động (đôi khi chuyển đổi dữ liệu và hợp nhất được thực hiện trước khi quá trình lựa chọn dữ liệu, đặc biệt là trong trường hợp các kho dữ liệu. Giảm dữ liệu cũng có thể được thực hiện để có được một đại diện nhỏ hơn của dữ liệu gốc mà không bị mất toàn vẹn của nó).
10 Bước 2: Khai thác dữ liệu (một quá trình cần thiết mà các phương pháp thông minh được áp dụng để trích xuất các mẫu dữ liệu): Đây được xem là bước quan trọng nhất trong quá trình KDD. Nó áp dụng một số kỹ thuật KPDL (chủ yếu là từ học máy và các lĩnh vực khác) để khai phá, trích chọn được những mẫu (patterns) thông tin, những mối liên hệ (relationships) đặc biệt trong dữ liệu. Bước 3: Đánh giá mẫu (để xác định các mô hình thực sự thú vị đại diện cho kiến thức dựa trên các biện pháp): Thành phần này thường sử dụng các độ đo và tương tác với thành phần KPDL để tập trung tìm kiếm các mẫu. Nó có thể sử dụng các ngưỡng để lọc ra các mẫu phát hiện được. Ngoài ra, thành phần đánh giá mẫu có thể được tích hợp với thành phần KPDL, phụ thuộc vào các phương pháp KPDL được sử dụng. Bước 4: Biểu diễn tri thức (nơi trực quan và kỹ thuật biểu diễn tri thức được sử dụng để trình bày kiến thức khai thác cho người sử dụng): Những mẫu thông tin và mối liên hệ trong dữ liệu đã được khai phá ở bước trên được chuyển dạng và biểu diễn ở một dạng gần gũi với người sử dụng như đồ thị, cây, bảng biểu, luật,... Đồng thời bước này cũng đánh giá những tri thức khám phá được những tiêu chí nhất định. Từ bước 1 đến 4 là các hình thức khác nhau của tiền xử lý dữ liệu, nơi dữ liệu được chuẩn bị cho khai thác. Các bước khai thác dữ liệu có thể tương tác với người sử dụng hoặc một cơ sở tri thức. Các mẫu thú vị được trình bày cho người sử dụng và có thể được lưu trữ như kiến thức mới trong cơ sở tri thức. 1.1.1.2. Kiến trúc một hệ thống khai phá dữ liệu Kiến trúc của hệ thống KPDL có thể có các thành phần chính sau: