Luận văn Thạc sĩ Hệ thống thông tin: Phương pháp sửa đổi hiệu quả nhằm bảo vệ các tập mục có độ hữu ích cao nhạy cảm trong cơ sở dữ liệu giao tác

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:66

Thêm vào BST

Báo xấu

18
lượt xem 7
download

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

Luận văn "Phương pháp sửa đổi hiệu quả nhằm bảo vệ các tập mục có độ hữu ích cao nhạy cảm trong cơ sở dữ liệu giao tác" được hoàn thành với mục tiêu nhằm tìm hiểu các ưu điểm và hạn chế của các thuật toán ẩn các tập mục có độ hữu ích cao nhạy cảm để từ đó đề xuất ra phương pháp ẩn hiệu quả hơn. Tìm hiểu các thông số đánh giá tính hiệu quả của các thuật toán ẩn tập mục có độ hữu ích cao nhạy cảm. Tiến hành cài đặt thử nghiệm phương pháp đề xuất, đánh giá dựa trên các thông số, so sánh với các phương pháp ẩn hiện có.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Hệ thống thông tin: Phương pháp sửa đổi hiệu quả nhằm bảo vệ các tập mục có độ hữu ích cao nhạy cảm trong cơ sở dữ liệu giao tác

ỦY BAN NHÂN DÂN TỈNH BÌNH DƯƠNG TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT NGUYỄN TRỌNG NGHĨA PHƯƠNG PHÁP SỬA ĐỔI HIỆU QUẢ NHẰM BẢO VỆ CÁC TẬP MỤC CÓ ĐỘ HỮU ÍCH CAO NHẠY CẢM TRONG CƠ SỞ DỮ LIỆU GIAO TÁC LUẬN VĂN THẠC SĨ CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN MÃ SỐ: 8 48 01 04 BÌNH DƯƠNG - 2021
ỦY BAN NHÂN DÂN TỈNH BÌNH DƯƠNG TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT NGUYỄN TRỌNG NGHĨA PHƯƠNG PHÁP SỬA ĐỔI HIỆU QUẢ NHẰM BẢO VỆ CÁC TẬP MỤC CÓ ĐỘ HỮU ÍCH CAO NHẠY CẢM TRONG CƠ SỞ DỮ LIỆU GIAO TÁC LUẬN VĂN THẠC SĨ CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN MÃ SỐ: 8 48 01 04 NGƯỜI HƯỚNG DẪN KHOA HỌC TS. NGUYỄN KHẮC CHIẾN BÌNH DƯƠNG - 2021
LỜI CAM ĐOAN Tôi cam đoan rằng luận văn này: “Phương pháp sửa đổi hiệu quả nhằm bảo vệ các tập mục có độ hữu ích 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 luận văn này là trung thực và chính xác. Ngoài những nội dung tham khảo đã được trích dẫn, tôi cam đoan rằng luận văn này chưa được sử dụng để cấp văn bằng ở các cơ sở đào tạo khác. Bình Dương, ngày 23 tháng 12 năm 2021 Tác giả luận văn Nguyễn Trọng Nghĩa i
LỜI CẢM ƠN Trong quá trình tham gia học tập và nghiên cứu chương trình đào tạo cũng như thực hiện luận văn thạc sĩ, ngoài những nỗ lực và cố gắng của bản thân tôi đã nhân được sự hướng dẫn và giúp đỡ tận tình của thầy cô trong Trường Đại học Thủ Dầu Một. Với lòng biết ơn sâu sắc, tôi xin được gửi lời cảm ơn tới: Ban giám hiệu nhà trường, Viện Đào tạo Sau đại học đã tạo điều kiện giúp tôi hoàn thành khóa học và hoàn thành luận văn. Các thầy cô giảng dạy chương trình Hệ thống thông tin đã giảng dạy và cung cấp các kiến thức quý báu trong quá trình học tập và thực hiện đề tài. Thầy Hoàng Mạnh Hà (Giám đốc chương trình Hệ thống thông tin bậc Sau đại học) đã giúp đỡ và tạo điều kiện để tôi tham gia học tập và thực hiện các thủ tục thực hiện và bảo vệ luận văn. Bạn bè và đồng nghiệp đã luôn bên cạnh động viên và thực hiện đề tài. Đặc biệt, em chân thành cảm ơn Thầy TS. Nguyễn Khắc Chiến đã tận tình hướng dẫn em hoàn thành luận văn này. Dù đã cố gắng trong quá trình thực hiện, tuy nhiên không thể tránh khỏi những sai sót. Tôi mong nhận được những góp ý từ thầy cô, bạn bè và đồng nghiệp để kiến thức của mình ngày càng hoàn thiện hơn Bình Dương, ngày 23 tháng 12 năm 2021 Tác giả luận văn Nguyễn Trọng Nghĩa ii
MỤC LỤC LỜI CẢM ƠN ................................................................................................... ii MỤC LỤC........................................................................................................ iii DANH MỤC CÁC CHỮ VIẾT TẮT, KÍ HIỆU............................................. iv DANH MỤC BẢNG BIỂU ................................................................................v 1. Lý do chọn đề tài ...........................................................................................................1 2. Mục tiêu nghiên cứu ......................................................................................................2 3. Tổng quan nghiên cứu của đề tài....................................................................................2 4. Đối tượng, phạm vi nghiên cứu......................................................................................3 5. Đóng góp của đề tài .......................................................................................................3 Chương 1:TỔNG QUAN VỀ KHAI THÁC TẬP MỤC CÓ ĐỘ HỮU ÍCH CAO ...................................................................................................................4 1.1 Bài toán khai thác tập mục có độ hữu ích cao...................................................................4 1.2 Khai thác tập mục truyền thống .......................................................................................5 1.3 Khai thác tập mục độ hữu ích cao ....................................................................................9 1.4. Kết luận Chương 1 ....................................................................................................... 12 Chương 2: ........................................................................................................13 PHƯƠNG PHÁP ẨN TẬP MỤC CÓ ĐỘ HỮU ÍCH CAO...........................13 2.1. Bài toán ẩn tập mục có độ hữu ích cao nhạy cảm .......................................................... 13 2.2. Một số công trình liên quan .......................................................................................... 14 2.3 Phương pháp ẩn tập mục độ hữu ích cao nhạy cảm ........................................................ 16 2.4. Kết luận Chương 2 ....................................................................................................... 30 Chương 3: ........................................................................................................31 ĐỀ XUẤT PHƯƠNG PHÁP HIỆU QUẢ ĐỂ ẨN CÁC TẬP MỤC .............31 CÓ ĐỘ HỮU ÍCH CAO ..................................................................................31 3.1. Cơ sở để đề xuất thuật toán........................................................................................... 31 3.2. Một số phép đo 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 cao ......................................................................................................................... 34 3.3. Thuật toán đề xuất ........................................................................................................ 35 3.4. Kết luận Chương 3 ....................................................................................................... 42 Chương 4..........................................................................................................43 THỬ NGHIỆM VÀ ĐÁNH GIÁ .....................................................................43 4.1. Mô tả môi trường thực nghiệm và dữ liệu sử dụng ........................................................ 43 4.2. Kết quả thực nghiệm .................................................................................................... 44 4.3. Kết luận Chương 4 ....................................................................................................... 49 KẾT LUẬN ......................................................................................................50 CÔNG TRÌNH ĐÃ CÔNG BỐ .......................................................................51 TÀI LIỆU THAM KHẢO ...............................................................................52 iii
DANH MỤC CÁC CHỮ VIẾT TẮT, KÍ HIỆU Viết tắt Tiếng Anh Tiếng Việt CSDL Database Cơ sở dữ liệu Độ tương tự về độ hữu ích toàn bộ DUS Database Utility cơ sở dữ liệu eu External Utlity Lợi nhuận HUI High Utility Tập mục độ hữu ích cao Độ tương tự về độ hữu ích các tập IUS Itemset Utility mục độ hữu ích cao Chi phí ẩn nhầm tập mục không MC Missing Cost nhạy cảm Sensitive High Utility Tập mục độ hữu ích cao không nhạy NSHUI Itemsets cảm Sensitive High Utility SHUI Tập mục độ hữu ích cao nhạy cảm Itemsets Selecting Maximum Utility Chọn mục có độ hữu ích lớn nhất SMAU item first trước Selecting Minimum Utility Chọn mục có độ hữu ích nhỏ nhất SMIU item first trước ST Sensitive Transaction Giao tác nhạy cảm T Transaction Giao tác iv
DANH MỤC BẢNG BIỂU Bảng 1.1 Cơ sở dữ liệu giao tác (Biểu diện dạng ngang).............................................................6 Bảng 1.2 Cơ sở dữ liệu giao tác (Biểu diễn dạng dọc) ................................................................7 Bảng 1.3 Cơ sở dữ liệu giao tác (Biểu diễn dạng ma trận) ..........................................................7 Bảng 1.4 Bảng cơ sở dữ liệu ......................................................................................................8 Bảng 1.5 Duyệt CSDL lần 1 ........................................................................................................8 Bảng 1.6 Lọc item độ hỗ trợ ≥ 2 ...............................................................................................8 Bảng 1.7 Kết hợp các mục từ 1.3 ...............................................................................................8 Bảng 1.8 Lọc item độ hỗ trợ ≥ 2 ...............................................................................................8 Bảng 1.9 Kết hợp các mục từ 1.3 ...............................................................................................8 Bảng 1.10 Lọc item độ hỗ trợ ≥ 2 .............................................................................................9 Bảng 1.11 CSDL giao tác sau chứa số lượng mục ..................................................................... 10 Bảng 1.12 Bảng lợi nhuận ....................................................................................................... 10 Bảng 1.13 Các tập mục độ hữu ích cao (𝒎𝒊𝒏𝒖𝒕𝒊𝒍 = 𝟏𝟔𝟎) ..................................................... 10 Bảng 2.1 Bảng T-Table thuật toán SMAU ................................................................................. 18 Bảng 2.2 Bảng HUI-Table thuật toán SMAU ............................................................................. 19 Bảng 2.3 Bảng T-Table thuật toán SMAU (cập nhật lần 1) ........................................................ 20 Bảng 2.4 Bảng HUI-Table thuật toán SMAU (cập nhật lần 1) .................................................... 20 Bảng 2.5 Bảng T-Table thuật toán SMAU (cập nhật lần2)......................................................... 21 Bảng 2.6 Bảng HUI-Table thuật toán SMAU (cập nhật lần 2) .................................................... 22 Bảng 2.7 Bảng T-Table thuật toán SMAU (cập nhật lần 3) ........................................................ 23 Bảng 2.8 Bảng HUI-Table thuật toán SMAU (cập nhật lần 3) .................................................... 23 Bảng 2.9 Bảng T-Table thuật toán SMIU .................................................................................. 25 Bảng 2.10 Bảng HUI-Table thuật toán SMIU ............................................................................ 25 Bảng 2.11 Bảng HUI-Table thuật toán SMIU (cập nhật lần 1) ................................................... 26 Bảng 2.12 Bảng HUI-Table thuật toán SMIU (Cập nhật lần 1) ................................................... 27 Bảng 2.13 Bảng HUI-Table thuật toán SMIU (cập nhật lần 2) ................................................... 28 Bảng 2.14 Bảng HUI-Table thuật toán SMIU (Cập nhật lần 2) ................................................... 28 Bảng 2.15 Bảng HUI-Table thuật toán SMIU (cập nhật lần 3) ................................................... 29 Bảng 2.16 Bảng HUI-Table thuật toán SMIU (Cập nhật lần 3) ................................................... 29 Bảng 3.1 Bảng cơ sở dữ liệu có dạng cấu trúc I-List ................................................................. 37 Bảng 3.2. Bảng HUI-Table........................................................................................................ 37 Bảng 3.3 Bảng T-Table ............................................................................................................ 37 Bảng 3.4. Bảng HUI-Table cập nhật lần 1 ................................................................................. 39 Bảng 3.5. Bảng T-Table cập nhật lần 1 ..................................................................................... 39 Bảng 3.6. Bảng HUI-Table cập nhật lần 2 ................................................................................. 41 Bảng 3.7. Bảng T-Table cập nhật lần 2 ..................................................................................... 41 Bảng 3.8. Bảng so sánh kết quả chạy thuật toán đề xuất với các thuật toán SMAU, SMIU [11]. ............................................................................................................................................... 42 Bảng 4.1. Cơ sở dữ liệu dùng cho thực nghiệm ....................................................................... 43 v
DANH MỤC HÌNH, ĐỒ THỊ Hình 2.1 Quá trình sửa đổi cơ sở dữ liệu............................................................14 Hình 4.1 Thời gian thực chạy thử toán với CSDL BMS_2 .................................45 Hình 4.2 Độ tương tự về độ hữu ích trong CSDL BMS_2 .................................45 Hình 4.3 Chi phí ẩn nhầm tập mục CSDL BMS_2 .............................................46 Hình 4.4 Độ tương tự về độ hữu ích của các tập mục độ hữu ích cao trong CSDL BMS_2 ..............................................................................................................46 Hình 4.5 Thời gian thực chạy thử toán với CSDL Mushroom ............................47 Hình 4.6 Độ tương tự về độ hữu ích trong CSDL Mushroom.............................48 Hình 4.7 Chi phí ẩn nhầm tập mục CSDL Mushroom ........................................48 Hình 4.8 Độ tương tự về độ hữu ích của các tập mục độ hữu ích cao trong CSDL Mushroom .........................................................................................................49 vi
PHẦN MỞ ĐẦU 1. Lý do chọn đề tài Hiện nay, việc tính toán doanh số và tối ưu hóa lợi nhuận bán hàng là công việc cực kỳ quan trọng, nó ảnh hưởng trực tiếp đến doanh thu và chiến lược bán hàng của các công ty, siêu thị hay các đơn vị bán lẻ. Đặc biệt, với số lượng hàng hóa lớn, giá cả khác nhau, nên việc tính toán lợi nhuận tối ưu từ bán hàng càng quan trọng. Trong khi số lượng giao dịch mỗi giờ có thể lên đến hàng chục nghìn giao dịch, việc tính toán xem mặt hàng nào đem lại doanh số cao, mặt hàng nào kinh doanh không hiệu quả dù bán với số lượng lớn càng trở nên khó khăn do dữ liệu quá lớn, liên tục. Việc khai thác tập phổ biến thường được mô tả là một quá trình rút trích thông tin có giá trị từ cơ sở dữ liệu lớn, nó bắt nguồn từ mẫu có sẵn tồn tại trong cơ sở dữ liệu, các mẫu này có khuynh hướng gom nhóm lại với nhau và được định nghĩa như là một mô hình khai thác. Khai thác tập mục độ hữu ích cao (high-utility itemset) là một mở rộng của bài toán khai thác tập mục phổ biến, đã được nhiều nhà nghiên cứu quan tâm với mục đích đánh giá ý nghĩa của các tập mục trong khai thác luật kết hợp. Để khai thác tập mục độ hữu ích cao, một giá trị được sử dụng đó là độ hữu ích của tập mục (itemset), chẳng hạn tổng lợi nhuận mà doanh nghiệp thu được nếu bán itemset ấy trong tập giao tác. Khác với khai thác itemset phổ biến, độ hữu ích của itemset không thỏa tính chất bao đóng giảm (downward closure property) nên độ phức tạp của bài toán cao. Trong môi trường cạnh tranh, cơ sở dữ liệu của các bên được chia sẻ với nhau để cùng có lợi trong hợp tác kinh doanh. Tuy nhiên, việc chia sẻ cơ sở dữ liệu mang lại nhiều rủi ro để lộ ra các thông tin nhạy cảm, như số định danh cá nhân, số tài khoản ngân hàng, … Để giải quyết vấn đề này, các tri thức nhạy cảm có thể được che giấu (ẩn) bằng cách chuyển đổi cơ sở dữ liệu ban đầu thành cơ sở dữ liệu được sửa đổi theo một số chiến lược cụ thể nào đó và quá trình ẩn đó được gọi là làm sạch dữ liệu (data sanitization). 1
Trong những năm gần đây, khai thác dữ liệu bảo vệ tính riêng tư (PPDM - Privacy Preserving Data Mining) đã trở thành hướng nghiên cứu quan trọng. Trong phần luận văn này, tôi xin tập trung nghiên cứu bài toán khai thác các tập mục có độ hữu ích cao được bảo vệ tính riêng tư (PPUIM - Privacy Preserving Utility Itemset Mining) để ẩn các tập mục có độ hữu ích cao nhạy cảm (SHUI - Sensitive High Utility Itemsets) trong cơ sở dữ liệu giao tác. Một trong những vấn đề đặt ra khi giải quyết bài toán này là giảm các hiệu ứng phụ: như ẩn nhầm các tập mục có độ hữu ích cao không nhạy cảm, sự khác nhau giữa CSDL ban đầu và CSDL sau khi sửa đổi… được tạo ra trong quá trình ẩn. Luận văn sẽ tập trung nghiên cứu các thuật toán ẩn các tập mục có độ hữu ích cao nhạy cảm và đề xuất ra phương pháp ẩn các tập mục có độ hữu ích cao nhạy cảm hiệu quả hơn nhằm giảm thiểu các hiệu ứng phụ tạo ra trong quá trình ẩn. Từ những lý do trên, tôi chọn đề tài “Phương pháp sửa đổi hiệu quả nhằm bảo vệ các tập mục có độ hữu ích cao nhạy cảm trong cơ sở dữ liệu giao tác” làm đề tài nghiên cứu cho luận văn tốt nghiệp của mình. 2. Mục tiêu nghiên cứu Nghiên cứu các thuật toán ẩn tập mục có độ hữu ích 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ìm hiểu các ưu điểm và hạn chế của các thuật toán ẩn các tập mục có độ hữu ích cao nhạy cảm để từ đó đề xuất ra phương pháp ẩn hiệu quả hơn. Tìm hiểu các thông số đánh giá tính hiệu quả của các thuật toán ẩn tập mục có độ hữu ích cao nhạy cảm. Tiến hành cài đặt thử nghiệm phương pháp đề xuất, đánh giá dựa trên các thông số, so sánh với các phương pháp ẩn hiện có. 3. Tổng quan nghiên cứu của đề tài Bài toán ẩn các tập mục độ hữu ích cao nhạy cảm đang là chủ đề được nhiều nhà nghiên cứu quan tâm. Mục tiêu của bài toán ẩn là để bảo vệ các thông tin nhạy cảm không thể khai thác được bằng các phương pháp khai thác tập mục độ hữu ích 2
cao với cùng một ngưỡng độ hữu ích tối thiểu do người dùng xác định. Bên cạnh đó các phương pháp ẩn tập mục độ hữu ích cao nhạy cảm cố gắng giảm thiếu các hiệu ứng phụ trên các thông tin không nhạy cảm và tính toàn vẹn của cơ sở dữ liệu ban đầu. Hiện đã có một số phương pháp ẩn hiệu quả để giải quyết vấn đề này, tuy nhiên những phương pháp này vẫn còn tạo ra các hiệu ứng phụ không mong muốn. Đề tài này đề xuất chiến lược sửa đổi một cách phù hợp để ẩn các tập mục độ hữu ích cao nhạy cảm một cách hiệu quả làm giảm thiểu các hiệu ứng phụ trên các thông tin không nhạy cảm. Kết quả thực nghiệm cho thấy thuật toán đề xuất hiệu quả hơn các thuật toán hiện có về mặt các hiệu ứng phụ, như ẩn nhầm các thông tin không nhạy cảm, chất lượng của cơ sở dữ liệu sau quá trình ẩn. 4. Đối tượng, phạm vi nghiên cứu Bài toán liên quan đến khai thác tập mục có độ hữu ích cao (HUI). Bài toán ẩn các tập mục có độ hữu ích cao trong cơ sở dữ liệu giao tác. 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 cao trong cơ sở dữ liệu giao tác. 5. Đóng góp của đề tài Luận văn này đề xuất phương pháp cải tiến các thuật toán SMAU, SMIU trong công trình của Xuan Liu và cộng sự [5]. Phương pháp được đề xuất sẽ tập trung vào việc lựa chọn các tập mục nhạy cảm nào được ẩn trước để giảm thiểu các hiệu ứng phụ. Thực nghiệm đã chỉ ra, phương pháp đề xuất hiệu quả hơn thuật toán trong [5] về giảm các hiệu ứng phụ như ẩn nhầm các thông tin không nhạy cảm và tính ổn định của cơ sở dữ liệu sau khi sửa đổi. Tuy nhiên, phương pháp đề xuất có thể tốn thời gian hơn các thuật toán trong [5]. 3
Chương 1: TỔNG QUAN VỀ KHAI THÁC TẬP MỤC CÓ ĐỘ HỮU ÍCH CAO 1.1 Bài toán khai thác tập mục có độ hữu ích cao  Khám phá tri thức và khai thác dữ liệu. Tri thức là tập hợp các thông tin bao gồm các sự kiện và mối quan hệ giữa các sự kiện đã được khám phá hoặc nghiên cứu. Tri thức có thể xem là dữ liệu trừu tượng và tổng quát ở mức cao. Khám phá tri thức là việc trích ra các tri thức chưa được nhận ra tiềm ẩn trong CSDL một cách tự động. Khám phá tri thức trong CSDL là quá trình gồm các bước phân tích các nội dung trong CSDL nhằm phát hiện ra các thông tin có ích, tìm được các giá trị, quy luật có trong cơ sở dữ liệu. Khai thác dữ liệu là quá trình khám phá các tri thức mới và tri thức ở dạng tiềm ẩn trong CSDL. Khai phá dữ liệu là một bước của khai phá tri thức. Các bước khám phá tri thức: Bước 1. Xác định và định nghĩa các vấn đề - Xác định nhiệm vụ, tri thức đã có và mục tiêu. - Tạo hoặc chọn CSDL Bước 2. Thu thập và xử lý - Xử lý và làm sạch dữ liệu. Bỏ các dữ các dữ liệu lỗi, xử lý dữ liệu bị thiếu và chuyển đổi dữ liệu phù hợp - Định dạng các thuộc tính hữu ích để phát hiện tri thức. Bước 3. Khai thác dữ liệu - Chọn nhiệm vụ cần khai thác. - Chọn phương pháp khai thác. - Khai thác dữ liệu để nhận được các mẫu, mô hình. Bước 4. Giải thích và đánh giá kết quả Bước 5. Sử dụng tri thức vừa phát hiện được 4
- Tri thức được phát hiện ra được tích hợp trong CSDL. - Tri thức vừa phát hiện ra có thể hỗ trợ cho quá trình khám phá tri thức khác Có thể thấy, trong các bước của khám phá tri thức thì bước 3 là quan trọng nhất vì đó là bước tìm ra các thông tin hữu ích tiềm ẩn trong CSDL. Khai thác dữ liệu là một bước của khám phá tri thức với việc chủ yếu là xác định bài toán khai thác, lựa chọn phương pháp cách tiến hành và tách các tri thức hữu ích trong CSDL cần thiết. Về bản chất, khai thác dữ liệu là giai đoạn duy nhất tìm ra thông tin tiềm ẩn có trong CSDL chủ yếu phục vụ cho mô tả hoặc dự đoán. Gồm các bước sau: Bước 1. Xác định vấn đề cần thực hiện. Bước 2. Xác định dữ liệu liên quan để xây dựng giải pháp thực hiện. Bước 3. Thu thập và xử lý dữ liệu Bước 4. Chọn thuật toán thích hợp và tiến hành khai thác dữ liệu. Giao tác là một hoạt động hay một chuỗi hoạt hoạt động truy cập vào CSDL hoặc làm thay đổi nội dung của CSDL. Các hoạt động này được tạo ra bởi người dùng hoặc các chương trình máy tính. Một vài ứng dụng của khai thác dữ liệu: - Phân tích và hỗ trợ đưa ra dự đoán. - Điều trị y học: Tìm ra các mối quan hệ giữa triệu chứng, chuẩn đoán và điều trị bệnh. - Thị trường tài chính và bảo hiểm, chứng khoán: phân tích và báo cáo. 1.2 Khai thác tập mục truyền thống Thuật toán Apriori được Agarwal và Srikant đề xuất năm 1994 để tính toán trên các giao tác như bán hàng trong siêu thị hoặc số liệu truy cập website. Các bước thực hiện thuật toán như sau: Bước 1: Duyệt cơ sở dữ liệu để có được độ hữu ích S của tập mục (itemset). So sánh S với ngưỡng tối thiểu minutil để có được 1-itemset (L1) 5
Bước 2: Sử dụng Lk-1 nối với Lk-1 để có được các mục ứng viên k-itemset. Loại bỏ các itemset không phải là ứng viên tiềm năng thu được k-itemset. Bước 3: Duyệt CSDL để có được độ hữu ích của mỗi ứng viên k-itemset, so sánh S với k-itemset thu được ứng viên tiềm năng k-itemset (Lk). Bước 4: Lặp lại bước 2 cho đến khi ứng viên set C bằng ∅, Bước 5. Với mỗi ứng viên tiềm năng Lm, sinh các tập con của S không rỗng của I. Cho tập các mục I={i1, i2,..., in}. Một giao tác (transaction) T là một tập con của I, TI… Cơ sở dữ liệu giao tác là tập các giao tác DB ={ T1, T2,..., Tm}. Mỗi giao tác được gán một định danh TID. Dạng CSDL này thường được sử dụng trong kinh doanh thương mại hoặc các hệ thống ngân hàng. Cơ sở dữ liệu giao tác thường được biểu diễn ở dạng ngang, dạng dọc và bảng ma trận. Biểu diễn giao tác dạng ngang là trình bày giao tác dưới dạng một danh sách, mỗi giao tác có một mã định danh riêng (TID), mỗi giao tác chưa một danh sách các mục. Bảng 1.1 Cơ sở dữ liệu giao tác (Biểu diện dạng ngang) TID Mục T1 a, b, e T2 c, d T3 b, c, e, f T4 a, b, c, d, e T5 b, c T6 a, e, f T7 a, c, d T8 b, d, e T9 a, b, c, d, e, f T10 c, e, f 6
Biểu diễn giao tác dạng dọc là trình bày danh sách các mục dữ liệu, mỗi mục dữ liệu chứa tất cả các mã định danh giao tác. Bảng 1.2 Cơ sở dữ liệu giao tác (Biểu diễn dạng dọc) Mục TID a T1, T4, T6, T7, T9 b T1, T3, T4, T5, T8, T9 c T2, T3, T4, T5, T7, T9, T10 d T2, T4, T7, T8, T9 e T3, T6, T10 f T3, T6, T9, T10 Biểu diễn dạng ma trận Cho CSDL DB = {T1, T2, …, Tn} trên tập các mục I = {I1, I2, …, In} được biểu diễn bởi ma trận nhị phân M = (mpq)mxn 1 𝑘ℎ𝑖 𝑖 𝑞 ∈ 𝑇 𝑞 𝑚 𝑝𝑞 = { 0 𝑘ℎ𝑖 𝑖 𝑞 ∉ 𝑇 𝑞 Với cơ sở dữ liệu từ bảng 1.1 ta có ma trận giao tác như sau: Bảng 1.3 Cơ sở dữ liệu giao tác (Biểu diễn dạng ma trận) TID a b c d e f T1 1 1 0 0 1 0 T2 0 0 1 1 0 0 T3 0 1 1 1 1 0 T4 1 1 1 1 1 0 T5 0 1 1 0 0 0 T6 1 0 0 0 1 1 T7 1 0 1 1 0 0 T8 0 1 0 1 1 0 T9 1 1 1 1 1 1 T10 0 0 1 0 1 1 7
Minh họa thuật toán Apriori: Thuật toán sử dụng cơ sở dữ liệu gồm bốn giao tác T1, T2, T3, T4 thể hiện trong Bảng 1.1. Có năm mặt hàng tương ứng với các mục là a, b, c, d, e. Độ hỗ trợ của một tập hợp X trong cơ sở dữ liệu D là tỷ số giữa các bản ghi T D có chứa tập X và tổng số bản ghi trong D (hay là phần trăm của các bản ghi trong D có chứa tập hợp X), ký hiệu là support(X) hay supp(X). Độ hỗ trợ (Support) được thể hiện trong bảng 1.2. với ngưỡng hỗ trợ nhỏ nhất (Min_sup) bằng 2. Bảng 1.4 Bảng cơ sở dữ liệu Bảng 1.5 Duyệt CSDL lần 1 Mục Độ hỗ trợ TID Mục {a} 2 T1 a, c, d {b} 3 T2 b, c, e {c} 3 T3 a, b, c, e {d} 1 T4 b, e {e} 3 Bảng 1.6 Lọc item độ hỗ trợ ≥ 2 Bảng 1.7 Kết hợp các mục từ 1.3 Mục Độ hỗ trợ Độ hỗ Độ hỗ Mục Mục {a} 2 trợ trợ {b} 3 {a, b} 1 {b, c} 2 {c} 3 {a, c} 2 {b, e} 3 {e} 3 {a, e} 1 {c, e} 2 Bảng 1.8 Lọc item độ hỗ trợ ≥ 2 Bảng 1.9 Kết hợp các mục từ 1.3 Mục Độ hỗ trợ Mục Độ hỗ trợ {a, c} 2 {a, b, c} 1 {b, c} 2 {a, b, e} 1 {b, e} 3 {b, c, e} 2 {c, e} 2 8
Bảng 1.10 Lọc item độ hỗ trợ ≥ 2 Mục Độ hỗ trợ {B, C, E} 2 Với CSDL cho trong Bảng 1.1 Thuật toán này thực hiện như sau: Cho CSDL bảng 1.1. Duyệt bảng 1.1 ta có danh sách các mục và độ hỗ trợ kèm theo (Bảng 1.2). Tiến hành loại các item có độ hỗ trợ < Min_sup ta được bảng 1.3. Duyệt lần 2 ta được bảng 1.4 bao gồm các tập mục và độ hỗ trợ (Bảng 1.4). Tiến hành loại các item có độ hỗ trợ < Min_sup ta được bảng 1.5. Duyệt lần 2 ta được bảng 1.5 bao gồm các tập mục và độ hỗ trợ (Bảng 1.6). Tiến hành loại các item có độ hỗ trợ < Min_sup ta được bảng 1.7. 1.3 Khai thác tập mục độ hữu ích cao Một trong những lý do của khai thác tập mục độ hữu ích cao là tìm ra các tập mục có độ hữu ích cao hơn ngưỡng đã cho. Qua đó, xác định được mức độ hữu ích của các mục trong CSDL. Từ đó xác định được các mục độ hữu ích cao, các mục độ hữu ích cao nhạy cảm. Sau đó xây dựng các chiến lược bảo vệ các dữ liệu nhạy cảm, làm hạn chế các thông tin nhạy cảm bị lộ ra ngoài, nhất là trong kinh doanh. Khai thác tập mục có độ hữu ích cao là tìm ra các tập mục có độ hữu ích lớn hơn một ngưỡng độ hữu ích tối thiểu (minutil) do người dùng quy định. Độ hữu ích trong giao tác là một giá trị số cho biết số (Có thể là số lượng đã bán của các mặt hàng trong siêu thị…). Bài toán Khai thác tập mục độ hữu ích cao được sử dụng trên cơ sở dữ liệu giao tác. Mỗi giao tác có thể là một giao dịch mua hàng, truy cập internet… Luận văn này sử dụng CSDL giao tác như sau: 9
Bảng 1.11 CSDL giao tác sau chứa số lượng mục TID Giao tác (Mục, số lượng) T1 (a,2), (b,1), (e,3) T2 (c,1), (d,6) T3 (b,1), (c,2), (e,1), (f,1) T4 (a,3), (b,4), (c,2), (d,2), (e,5) T5 (b,3), (c,5) T6 (a,2), (e,7), (f,3) T7 (a,4), (c,15), (d,40) T8 (b,15), (d,35), (e,3) T9 (a,5), (b,10), (c,20), (d,30), (e,2), (f,3) T10 (c,12), (e,4), (f,1) Bảng 1.12 Bảng lợi nhuận Mục a b c d e f Lợi nhuận 5 3 2 1 6 10 Bảng 1.13 Các tập mục độ hữu ích cao (𝒎𝒊𝒏𝒖𝒕𝒊𝒍 = 𝟏𝟔𝟎) HID HUIs Utility (Độ hữu ích) 1 abcde 200 2 abcdef 167 3 abce 168 4 acd 206 5 ae 162 6 bcde 160 7 bde 214 8 be 177 9 cef 160 10 ef 164 10
Một số khái niệm về khai thác tập mục độ hữu ích cao: Cho I = {i1 , i2 , … , im } là một tập m mục (item) phân biệt, trong đó mỗi mục ip ∈ I có độ hữu ích bên ngoài (được gọi là lợi nhuận) eu(ip ), 1 ≤ p ≤ m và D = {T1 , T2 , … , Tn } là một cơ sở dữ liệu (CSDL) giao tác, trong đó Ti là một giao tác chứa một tập các mục được chứa trong I. Một tập gồm một hoặc nhiều mục được gọi làm tập mục (itemset). Một giao tác T hỗ trợ một tập mục X nếu X ⊆ I. Một tập mục X = {i1 , i2 , … , ik } chứa k mục được gọi là k-itemset. Mỗi mục ip trong giao tác Tq được kết hợp với một số lượng các mục ip có trong giao tác Tq. Cho CSDL giao tác như Bảng 1.11, Bảng 1.12 chứa lợi nhuận của các giao tác và Bảng 1.13 chứa các tập mục độ hữu ích cao. Luận văn sử dụng một số định nghĩa như sau [3]: Định nghĩa 1.1: Số lượng mục ip trong giao tác Tq, ký hiệu là iu(ip , Tq ). [3] Ví dụ: trong Bảng 1 có iu(b, T8 ) = 15 và iu(d, T8 ) = 35. Định nghĩa 1.2: Lợi nhuận của mục ip , nó thể hiện độ quan trọng của mục ip , ký hiệu là eu(ip ). [3] Ví dụ: trong Bảng 2 có eu(b) = 3 và eu(d) = 1. Định nghĩa 1.3: Độ hữu ích của mục ip trong giao tác Tq, ký hiệu là u(ip , Tq), được tính như sau: u(ip , Tq) = iu(ip , Tq) ∗ eu(ip ). [3] Ví dụ: u(B, T8 ) = iu(b, T8 ) ∗ eu(b) = 15 ∗ 3 = 45. Định nghĩa 1.4: Độ hữu ích của tập mục X trong giao tác Tq, ký hiệu là u(X, Tq ) được tính như sau: u(X, Tq) = ∑ u(ip , Tq) [3] ip ∈X Ví dụ: u(bd, T8 ) = u(b, T8 ) + u(d, T8 ) = 15 ∗ 3 + 35 ∗ 1 = 80. 11
Định nghĩa 1.5: Độ hữu ích của tập mục X, ký hiệu là u(X), được tính như sau: u(X) = ∑X⊆Tq∧Tq∈D u(X, Tq) [3] Ví dụ: u(bd) = u(bd, T4 ) + u(bd, T8 ) + u(bd, T9 ) = 14 + 80 + 60 = 154. Định nghĩa 1.6: Độ hữu ích của giao tác Tq, ký hiệu là tu(Tq ), được tính như sau: tu(Tq ) = ∑ip ∈Tq u(ip , Tq) [3] Ví dụ: tu(T8 ) = u(b, T8 ) + u(d, T8 ) + u(e, T8 ) = 15 ∗ 3 + 35 ∗ 1 + 3 ∗ 6 = 98 Định nghĩa 1.7: Bài toán khai thác tập mục độ hữu ích cao. Một tập mục X được gọi là tập mục độ hữu ích cao nếu độ hữu ích của X lớn hơn hoặc bằng ngưỡng độ hữu ích tối thiểu do người dùng đưa vào, ký hiệu là minutil. Gọi HUI là tập hợp các tập mục độ hữu ích cao, ta có HUI = {X | X ∈ I, u(X) ≥ minutil}. [3] 1.4. Kết luận Chương 1 Bài toán khai thác tập mục độ hữu ích cao đã tìm ra các giá trị hữu ích dựa trên ngưỡng tối thiểu do người dùng quy định. Tuy nhiên, trong thực tế, dữ liệu trong thương mại, ngân hàng cần được chia sẻ. Vấn đề đặt ra là làm thế nào để dữ liệu vẫn được chia sẻ giữa các doanh nghiệp mà vẫn đảm bảo được tính bảo mật trong dữ liệu. Để giải quyết vấn đề đó, bài toán ẩn tập phổ biến có độ hữu ích cao ra đời. Cụ thể tôi sẽ trình bày trong chương 2. 12