Nâng cao tính hiệu quả trong việc khai thác tập hữu ích cao hiếm trên cơ sở dữ liệu lớn

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

Thêm vào BST

Báo xấu

28
lượt xem 4
download

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

Bài viết đề xuất và áp dụng cấu trúc dữ liệu phù hợp để xây dựng một thuật toán khai thác tập hữu ích cao hiếm, hiệu quả hơn các thuật toán trước đây về cả không gian tìm kiếm và thời gian thực thi.

Chủ đề:

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

Lưu

Nội dung Text: Nâng cao tính hiệu quả trong việc khai thác tập hữu ích cao hiếm trên cơ sở dữ liệu lớn

Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIV về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR), TP. HCM, ngày 23-24/12/2021 DOI: 10.15625/vap.2021.0064 NÂNG CAO TÍNH HIỆU QUẢ TRONG VIỆC KHAI THÁC TẬP HỮU ÍCH CAO HIẾM TRÊN CƠ SỞ DỮ LIỆU LỚN Vũ Văn Vinh*, Lâm Thị Họa Mi, Dương Thị Mộng Thùy Khoa Công nghệ thông tin, Trường Đại học Công nghiệp thực phẩm TP. HCM vinhvv@hufi.edu.vn, milth@hufi.edu.vn, thuydtm@hufi.edu.vn TÓM TẮT: Khai thác tập hữu ích cao có ý nghĩa to lớn trong hoạt động sản xuất kinh doanh. Trong nhiều tình huống thực tế, các trường hợp hiếm gặp được quan tâm nhiều hơn (ví dụ, trong y học, các triệu chứng hiếm gặp đặt ra thách thức và cung cấp những hiểu biết hữu ích cho các bác sĩ trong chuẩn đoán bệnh). Khai thác tập hữu ích cao hiếm đang là chủ đề được nhiều nhà khoa học quan tâm hiện nay. Một số thuật toán đã được đề xuất để giải quyết vấn đề này, nhưng chúng tiêu tốn nhiều thời gian và không gian lưu trữ. Trong bài báo này, chúng tôi sẽ đề xuất và áp dụng cấu trúc dữ liệu phù hợp để xây dựng một thuật toán khai thác tập hữu ích cao hiếm, hiệu quả hơn các thuật toán trước đây về cả không gian tìm kiếm và thời gian thực thi. Từ khóa: Khai phá luật kết hợp, tập hữu ích cao, tập hữu ích cao hiếm, RCUL. I. GIỚI THIỆU Khai thác dữ liệu được nghiên cứu để chuyển đổi dữ liệu thô thành những thông tin có ý nghĩa phục vụ cho nhiều mục đích khác nhau, đặc biệt hiện nay lại có ý nghĩa to lớn trong hoạt động sản xuất, kinh doanh. Các nhà sản xuất nhận ra rằng mục tiêu “đến gần hơn với khách hàng” là rất quan trọng đối với sự phát triển của một doanh nghiệp. Khai phá luật kết hợp (ARM - Association Rule Mining) là một trong những phương pháp được sử dụng rộng rãi nhất trong khai thác dữ liệu và khám phá tri thức. Tuy nhiên, ARM truyền thống chủ yếu tập trung vào việc khai thác tập mục phổ biến. Các tập mục này được sinh ra chỉ có thể đóng góp một phần nhỏ trên lợi nhuận tổng thể. Trong khi đó, các tập mục (mặt hàng) hiếm khi xuất hiện trong cơ sở dữ liệu, hay còn được gọi là các tập mục hiếm (hoặc không phổ biến) có thể mang lại một số lợi nhuận đặc biệt (hoặc rất lớn). Trong nhiều tình huống thực tế, những trường hợp hiếm gặp lại được quan tâm cao hơn (ví dụ: trong y học, những triệu chứng hiếm gặp đặt ra những thách thức và cung cấp những hiểu biết hữu ích cho bác sĩ trong điều trị bệnh) [1] Vì vậy, khai thác tập mục hiếm là một chủ đề hấp dẫn nhiều nhà khoa học ngày nay. Vào năm 2013, Jyothi và cộng sự đã nghiên cứu và đề xuất thuật toán HURI khai thác vật phẩm hiếm hữu ích cao [2]. HURI đã thực hiện tìm kiếm một cách hiệu quả các tập mục hiếm, có tính tiện ích cao theo người dùng. Các tập mục hiếm đã chứng minh là đáng được mong đợi hơn so với các mẫu phổ biến. Khai thác mẫu hiếm đã và đang được ứng dụng thực tế trong những lĩnh vực như: các bộ dữ liệu sinh học có thể được sử dụng để nhận dạng những bất thường và xác định được sự hiện diện của các gen hiếm, từ đó phát hiện các bệnh nguy hiểm hoặc những bất thường nghiêm trọng trong lĩnh vực tin sinh học; trong ngành dược phẩm, liều lượng và hàm lượng thuốc được nghiên cứu kỹ về hiệu quả trước khi phân phối ra thị trường. Khi đó, nghiên cứu những biểu hiện lâm sàng, giám sát những phản ứng bất lợi không mong muốn khi người bệnh sử dụng thuốc để chứng minh tính hiệu quả của thuốc có thể đáp ứng trong quá trình điều trị, mặc dù những phản ứng này là hiếm khi xảy ra nhưng là một quy trình không thể thiếu. Vấn đề bảo mật và phát hiện gian lận trong sử dụng internet là quan trọng trong việc tăng cường an ninh mạng cho một tổ chức, các hành vi đáng nghi ngờ nên được nghiên cứu và xử lý. Những hành vi này tuy là những hoạt động không phổ biến của người dùng nhưng nên được khai thác và nghiên cứu để tìm ra nghi phạm và cải thiện các chính sách bảo mật. Trong bài báo này, chúng tôi tiếp tục nghiên cứu vấn đề khai thác tập mục hiếm để có thể đề xuất một phương pháp khai thác tập hữu ích cao hiếm từ cơ sở dữ liệu giao dịch đã được thu thập nhằm tìm ra các thông tin hiệu quả phục vụ cho các hoạt động sản xuất kinh doanh trong thực tế. Cụ thể, chúng tôi sẽ đề xuất cấu trúc dữ liệu RCUL (Revised Compact Utility List) được cải tiến từ cấu trúc CUL [3] để có thể lưu trữ thông tin hiệu quả hơn phục vụ cho quá trình khai thác tập HURI, chúng tôi cũng áp dụng các chiến lược tỉa đã được đề xuất trong các nghiên cứu trước đây và tìm ra một phương pháp tỉa hiệu quả mới, cuối cùng chúng tôi áp dụng tất cả vào một thuật toán chúng tôi đề xuất có tên EHURI (Effcient High Utility Rare Itemsets) để nhanh chóng phát hiện được các tập HURI. Phần còn lại của bài báo được tổ chức như sau: Phần II trình bày các nghiên cứu liên quan đến bài toán khác tập mục hữu ích cao và tập mục hiếm hữu ích cao. Phần III trình bày thuật toán đóng góp của chúng tôi bao gồm những định nghĩa được sử dụng, cấu trúc lưu trữ dữ liệu, các chiến lược tỉa hiệu quả được áp dụng để loại bỏ những ứng viên không có tiềm năng nhằm thu gọn không gian sử dụng bộ nhớ và thời gian thực thi và thuật toán đề xuất. Môi trường, kết quả thực nghiệm và đánh giá thuật toán được trình bày trong Phần IV. Cuối cùng, Phần V sẽ trình bày kết luận và hướng phát triển của vấn đề được quan tâm. II. CÁC CÔNG TRÌNH LIÊN QUAN Khai thác luật kết hợp (ARM) đã và đang được nghiên cứu trong nhiều công trình nghiên cứu khoa học. Khai thác luật kết hợp là tìm ra mối liên hệ giữa các đối tượng trong cơ sở dữ liệu lớn. Từ năm 1994, Agrawal và cộng sự [4] đề xuất thuật toán Apriori. Ý tưởng chính của thuật toán này là dựa vào tập phổ biến (FI) và tính chất tỉa DCP để sinh
236 NÂNG CAO TÍNH HIỆU QUẢ TRONG VIỆC KHAI THÁC TẬP HỮU ÍCH CAO HIẾM TRÊN CƠ SỞ DỮ LIỆU LỚN luật kết hợp (Downward Closure Property). Adda và cộng sự đã mô tả thuật toán ARANIM (Apriori for Rare and Non- present Itemset Mining) để khai thác các vật phẩm hiếm và không hiện diện [5]. Apriori for rare là một sự thay đổi của thuật toán Apriori được sử dụng để khai thác các tập phổ biến. Tuy nhiên, khai thác tập phổ biến trong cơ sở dữ liệu truyền thống không đáp ứng được nhu cầu thiết yếu trong các cơ sở dữ liệu có chứa độ hữu ích. Gần đây, có rất nhiều nghiên cứu tập trung vào việc khai thác tập hữu ích cao và đã đạt được một số thành quả nhất định. Liu và cộng sự đề xuất thuật toán Two-Phase [6] để phát sinh ứng viên trong giai đoạn 1 và khai thác tập hữu ích cao trong giai đoạn 2. Các thuật toán cũng được thực hiện qua 2 giai đoạn là UP-Growth [7], TWU-Mining [8], UP-Growth+ [9] được đề xuất để tìm ra tập hữu ích cao hiệu quả. Tuy nhiên, các thuật toán này lại chiếm thời gian thực thi và không gian bộ nhớ rất lớn. Khi đó, vấn đề này tiếp tục được nghiên cứu và một số thuật toán được đề xuất nhằm nâng cao hiệu quả cho bài toán khai thác tập hữu ích cao là HUI-Miner [10], FHM [11], EFIM [12], HMiner [3]. Hầu hết các nghiên cứu về khai thác tập hữu ích cao chủ yếu tập trung vào các tập mục có độ hữu ích cao và phát sinh các luật kết hợp từ chúng mà không quan tâm đến độ phổ biến của các tập mục. Các bộ dữ liệu không thường xuyên hoặc hiếm cũng nên được khám phá vì các bộ này cũng chứa thông tin quan trọng giống như các tập phổ biến. Khai thác tập mục hữu ích cao hiếm là tìm ra những tập mục có lợi nhuận cao nhưng hiếm khi được xuất hiện trong các giao dịch. Tức là, tìm ra những tập mục có tần số xuất hiện nhỏ hơn giá trị độ hỗ trợ tối đa nhưng có lợi ích không nhỏ hơn ngưỡng lợi ích tối thiểu. Một số phương pháp tiếp cận tiện ích đã xem xét cải tiến hiệu suất để cho phép xử lý các bộ ứng cử viên lớn. Các mẫu hiếm cung cấp thông tin rất có giá trị trong các ứng dụng thực tế như bảo mật, chiến lược kinh doanh, sinh học, y học, siêu thị,... Adda và cộng sự [13] đã chứng minh những hành vi thông thường là rất thường xuyên, trong khi hành vi bất thường hoặc đáng ngờ là ít xảy ra hơn. Các tập mục hiếm hữu ích cao là các tập mục chứa các mục có tính tiện ích cao và hiếm khi xuất hiện trong các giao dịch hoặc bộ dữ liệu. Một cách tiếp cận khác biệt đáng kể là Apriori-inverse. Phương pháp này đã được đề xuất bởi Koh và Rountree [14] và là một biến thể phức tạp hơn của thuật toán Apriori truyền thống để sử dụng các tập mục không phổ biến trong quá trình tạo quy tắc. Điểm mới trong phương pháp sử dụng giá trị độ hỗ trợ tối đa, thay vì độ hỗ trợ tối thiểu, để tạo các tập mục ứng viên, tức là chỉ các tập mục có độ hỗ trợ thấp hơn ngưỡng cho phép được khai thác. Năm 2013, Jyothi và cộng sự [2] tiếp tục nghiên cứu và đề xuất một thuật toán hiệu quả để tìm tất cả tập mục hiếm hữu ích cao từ cơ sở dữ liệu giao dịch. Thuật toán này gồm 2 giai đoạn, giai đoạn 1 là tìm ra những tập mục hiếm; giai đoạn 2 độ hữu ích của các tập mục hiếm sẽ được tính và từ đó tìm ra được những tập mục hiếm lợi ích cao. Năm 2015, Vikram Goyal và cộng sự [15] đề xuất thuật toán UP-Rare Growth để tìm tập hiếm có hữu ích cao bằng cách sử dụng cấu trúc UP-Tree. Thuật toán này áp dụng các chiến lược tỉa DGU, DGN trong giai đoạn 1 để tỉa các ứng viên phát sinh và DLU, DLN trong giai đoạn 2 để loại bỏ ứng viên trong quá trình tìm tập hiếm có độ hữu ích cao nhằm tăng hiệu quả của thuật toán. Tuy nhiên, các thuật toán này làm việc trên cơ chế 2 giai đoạn, quá trình phát sinh ứng viên và tính độ hữu ích của các tập mục phải quét cơ sở dữ liệu nhiều lần, điều này dẫn đến nhiều vùng nhớ lưu trữ được sử dụng và thời gian thực hiện khá lớn. III. THUẬT TOÁN ĐỀ XUẤT A. Một số định nghĩa Bảng 1. Tóm tắt một số định nghĩa STT Ký hiệu Mô tả Ví dụ 1 𝐷 Cơ sở dữ liệu giao dịch gồm 𝑛 giao dịch 𝑇𝑗 Cơ sở dữ liệu giao dịch 𝐷 được cho trong 𝐷 = {𝑇1 , 𝑇2 , . . . , 𝑇𝑛 } bảng 2 2 𝐼 Tập mục hữu hạn gồm m mục (item) phân Với cơ sở dữ liệu trong 𝐷: biệt 𝐼 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔} 𝐼 = {𝑥1 , 𝑥2 , . . . , 𝑥𝑚 } 3 𝑝(𝑥𝑖 ) Lợi nhuận cố định của item 𝑥𝑖 𝑝(𝑓) = 3, và 𝑝(𝑎) = 3 4 𝑞(𝑥𝑖 , 𝑇𝑗 ) Số lượng của item 𝑥𝑖 trong giao dịch 𝑇𝑗 (số 𝑞(𝑓, 𝑇1 ) = 2 lượng item 𝑥𝑖 được mua trong giao dịch 𝑇𝑗 𝑞(𝑎, 𝑇1 ) = 2 5 𝑋 Tập mục gồm 𝑘 mục phân biệt Tập mục chứa 1 item: 𝑋 = {𝑎} 𝑋 = {𝑥1 , 𝑥2 , . . . , 𝑥𝑚 } ⊆ 𝑇𝑗 Tập mục chứa 3 items: 𝑋 = {𝑎, 𝑐, 𝑓} 6 𝑈(𝑥𝑖 , 𝑇𝑗 ) Độ hữu ích của item 𝑥𝑖 trong giao dịch 𝑇𝑗 Độ hữu ích của item 𝑓 trong giao dịch 𝑇1 : 𝑈�𝑥𝑖 , 𝑇𝑗 � = 𝑝(𝑥𝑖 ) ∗ 𝑞(𝑥𝑖 , 𝑇𝑗 ) 𝑈(𝑓, 𝑇1 ) = 𝑝(f) ∗ 𝑞(𝑓, 𝑇1 ) = 3 ∗ 2 = 6 7 𝑈(X, 𝑇𝑗 ) Độ hữu ích của tập mục 𝑋 trong 𝑇𝑗 Độ hữu ích của tập mục 𝑋 = {𝑓, 𝑎} trong 𝑇1 : 𝑈({𝑓, 𝑎}, 𝑇1 ) = 𝑈(𝑓, 𝑇1 ) + 𝑈(𝑎, 𝑇1 ) 𝑈�𝑋, 𝑇𝑗 � = � 𝑈�𝑥𝑖 , 𝑇𝑗 � 𝑥𝑖 ∈𝑋 = 6 + 6 = 12
Vũ Văn Vinh, Lâm Thị Họa Mi, Dương Thị Mộng Thùy 237 STT Ký hiệu Mô tả Ví dụ 8 𝑈(𝑋) Độ hữu ích của tập mục 𝑋 trong cơ sở dữ Trong cơ sở dữ liệu 𝐷, độ hữu ích của tập liệu 𝐷, bằng tổng tất cả độ hữu ích của 𝑋 mục 𝑋 = {𝑓, 𝑎} là: trong tất cả giao dịch có chứa 𝑋 𝑈(𝑋) = 𝑈({𝑓, 𝑎}, 𝑇1 ) + 𝑈({𝑓, 𝑎}, 𝑇3 ) 𝑈(𝑋) = � 𝑈�𝑋, 𝑇𝑗 � + 𝑈({𝑓, 𝑎}, 𝑇5 ) + 𝑈({𝑓, 𝑎}, 𝑇6 ) X⊆𝑇𝑗 ∧𝑇𝑗 ∈𝐷 + 𝑈({𝑓, 𝑎}, 𝑇8 ) = 12 + 15 + 9 + 6 + 6 = 48 9 𝑇𝑈�𝑇𝑗 � Độ hữu ích của giao dịch 𝑇𝑗 Độ hữu ích của giao dịch 𝑇1 : 𝑇𝑈(𝑇1 ) = 𝑈(𝑎, 𝑇1 ) + 𝑈(𝑐, 𝑇1 ) + 𝑈(𝑓, 𝑇1 ) 𝑇𝑈�𝑇𝑗 � = � 𝑈�𝑥𝑖 , 𝑇𝑗 � 𝑥𝑖 ∈𝑋∧𝑋⊆𝑇𝑗 = 6 + 2 + 6 = 14 10 𝑇𝑈 Tổng độ hữu ích của cơ sở dữ liệu 𝐷 Tổng độ hữu ích của cơ sở dữ liệu 𝐷 trong bảng 2: 𝑇𝑈 = � 𝑇𝑈 �𝑇𝑗 � 𝑇𝑈 = 𝑇𝑈(𝑇1 ) + 𝑇𝑈(𝑇2 ) + 𝑇𝑈(𝑇3 ) 𝑇𝑗 ∈𝐷 + 𝑇𝑈(𝑇4 ) + 𝑇𝑈(𝑇5 ) + 𝑇𝑈(𝑇6 ) + 𝑇𝑈(𝑇7 ) + 𝑇𝑈(𝑇8 ) + 𝑇𝑈(𝑇9 ) = 216 11 𝑇𝑊𝑈(𝑋) Trọng số hữu ích giao dịch của tập mục 𝑋 TWU của tập mục 𝑋 = {𝑓, 𝑎}: 𝑇𝑊𝑈(𝑋) = � 𝑇𝑈(𝑇𝑗 ) 𝑇𝑊𝑈({𝑓, 𝑎}) = 𝑇𝑈(𝑇1 ) + 𝑇𝑈(𝑇3 ) 𝑋⊆𝑇𝑗, 𝑇𝑗 ∈𝐷 + 𝑇𝑈(𝑇5 ) + 𝑇𝑈(𝑇6 ) + 𝑇𝑈(𝑇8 ) = 14 + 31 + 19 + 17 + 7 = 88 12 𝜀 Ngưỡng độ hữu ích tối thiểu Trong bài báo chúng tôi chọn 𝜀 = 40 13 𝜎 Phần trăm ngưỡng độ hỗ trợ hỗ trợ tối đa Và 𝜎 = 30% 14 𝑚𝑎𝑥𝑠𝑢𝑝𝑝 Ngưỡng độ hỗ trợ hỗ trợ tối đa 𝑚𝑎𝑥𝑠𝑢𝑝𝑝 = 𝜎 ∗ 𝑛 với 𝑛 là số giao dịch của cơ sở dữ liệu 𝐷 15 𝑠𝑢𝑝𝑝(𝑋) Độ hỗ trợ của tập mục 𝑋 trong 𝐷 là số lượng Độ hỗ trợ của tập mục 𝑋 = {𝑓, 𝑎} trong cơ giao dịch chứa 𝑋 trong 𝐷 sở dữ liệu 𝐷:𝑠𝑢𝑝𝑝(𝑋) = 5 16 ≺ Thứ tự của các item Thứ tự của các item được sắp xếp tăng dần theo TWU và được thể hiện trong bảng 4 𝑒≺𝑓≺𝑐≺𝑎≺𝑑≺𝑏 17 𝑇𝑗 ⁄𝑋 Tập các phần tử sau của 𝑋 trong giao dịch 𝑇𝑗 Trong bảng 5, với 𝑋 = {𝑓, 𝑎} và 𝑇5 theo thứ tự ≺ 𝑇5 ⁄𝑋 = {𝑑, 𝑏} 18 𝑆(𝑇𝑗 ⁄𝑋) Kích thước của tập các phần tử sau của 𝑋 Khi đó, trong giao dịch 𝑇𝑗 𝑆(𝑇5 ⁄𝑋) = 2 19 𝐶(𝑋) Kích thước tập mở rộng đóng của 𝑋 Theo thứ tự ≺ và 𝑋 = {𝑓, 𝑎}, ta có: 𝐶(𝑋) = |𝐸(𝑋)| 𝐸(𝑋) = {𝑑, 𝑏} với 𝐸(𝑋) là tập mở rộng của tập mục 𝑋 là tập và tất cả các item sau 𝑋 trong tập có thứ tự của 𝐶(𝑋) = 2 các item 𝐸(𝑋) = {𝑧 ∈ 𝐼 |𝑥 ≺ 𝑧, ∀𝑥 ∈ 𝑋} 20 𝑅𝑈(𝑋, 𝑇𝑗 ) Độ hữu ích của các phần tử sau của tập mục Ta có, 𝑇5 ⁄𝑋 = {𝑑, 𝑏}, với 𝑋 = {𝑓, 𝑎} 𝑋 trong giao dịch 𝑇𝑗 Do đó: 𝑅𝑈(𝑋, 𝑇5 ) = 𝑈(𝑑, 𝑇5 ) + 𝑈(𝑏, 𝑇5 ) = 2 + 8 = 10 𝑅𝑈�𝑋, 𝑇𝑗 � = � 𝑈�𝑥𝑖 , 𝑇𝑗 � 𝑥𝑖 ∈�𝑇𝑗 ⁄𝑋 � 21 𝑅𝑈(𝑋) Độ hữu ích của các phần tử sau của tập mục Khí đó, với 𝑋 = {𝑓, 𝑎} 𝑋 trong cơ sở dữ liệu 𝐷 𝑅𝑈(𝑋) = 𝑅𝑈(𝑋, 𝑇1 ) + 𝑅𝑈(𝑋, 𝑇3 ) 𝑅𝑈(𝑋) = � 𝑅𝑈�𝑋, 𝑇𝑗 � + 𝑅𝑈(𝑋, 𝑇5 ) + 𝑅𝑈(𝑋, 𝑇6 ) + 𝑅𝑈(𝑋, 𝑇8 ) 𝑋⊆𝑇𝑗 ∈𝐷 = 0 + 10 + 10 + 10 + 0 = 30 22 𝑃𝑈�𝑋𝑦, 𝑇𝑗 � Độ hữu ích tiền tố (độ hữu ích của các phần Cho 𝑋 = {𝑓}, độ hữu ích tiền tố của tập mục tử trước) của tập mục 𝑋𝑦, với 𝑦 ∈ 𝐼 là item 𝑋𝑎 trong giao dịch 𝑇1 là: mở rộng của 𝑋: 𝑃𝑈�𝑋𝑦, 𝑇𝑗 � = 𝑈�𝑋, 𝑇𝑗 � 𝑃𝑈(𝑓𝑎, 𝑇1 ) = 𝑈(𝑓, 𝑇1 ) = 6 Nếu 𝑋 = ∅, thì 𝑃𝑈�𝑋𝑦, 𝑇𝑗 � = 0
238 NÂNG CAO TÍNH HIỆU QUẢ TRONG VIỆC KHAI THÁC TẬP HỮU ÍCH CAO HIẾM TRÊN CƠ SỞ DỮ LIỆU LỚN Định nghĩa 1. Tập mục 𝑋 được gọi là đóng trên giao dịch 𝑇𝑗 nếu thỏa mãn điều kiện sau: |𝑋| > 1 và 𝐶(𝑋 − 𝑥𝑘 ) = 𝑆(𝑇𝑗 /{𝑋 − 𝑥𝑘 }), tức là số phần tử đứng sau itemset 𝑋 trong tập 𝐸(𝑋) bằng với số phần tử đứng sau itemset 𝑋 trong giao dịch đang xét. Khi đó một số đại lượng đóng của tập mục 𝑋 sẽ được định nghĩa như sau: Định nghĩa 2. Độ hữu ích đóng của tập mục 𝑋 trong giao dịch 𝑇𝑗 , được ký hiệu là 𝐶𝑈�𝑋, 𝑇𝑗 � và được tính là 𝐶𝑈�𝑋, 𝑇𝑗 � = 𝑈�𝑋, 𝑇𝑗 � nếu 𝑋 đóng trên 𝑇𝑗 . Ngược lại, 𝐶𝑈�𝑋, 𝑇𝑗 � = 0. Ví dụ 1. Với 𝑋 = {𝑓, 𝑎}. Khi đó 𝑋 là đóng trên giao dịch 𝑇5 vì: 𝐶(𝑋) = 𝑆(𝑇5 ⁄𝑋 ) = 2. Do đó: 𝐶𝑈(𝑋, 𝑇5 ) = 𝑈(𝑋, 𝑇5 ) = 9 và 𝑋 là không đóng trên 𝑇1 nên 𝐶𝑈(𝑋, 𝑇1 ) = 0. Độ hữu ích đóng của tập mục 𝑋 có kích thước nhỏ hơn hoặc bằng hai trong cơ sở dữ liệu 𝐷 được xác định là: 𝐶𝑈(𝑋) = ∑𝑋⊆𝑇𝑗 ∈𝐷 𝐶𝑈(𝑋, 𝑇𝑗 ) Ví dụ 2. 𝐶𝑈(𝑋 = {𝑓, 𝑎}) = 𝐶𝑈(𝑋, 𝑇5 ) + 𝐶𝑈(𝑋, 𝑇6 ) = 𝑈(𝑋, 𝑇5 ) + 𝑈(𝑋, 𝑇6 ) = 9 + 6 = 15. Vì 𝐶𝑈(𝑋, 𝑇1 ) = 0, 𝐶𝑈(𝑋, 𝑇3 ) = 0 và 𝐶𝑈(𝑋, 𝑇8 ) = 0 Định nghĩa 3. Độ hữu ích đóng của các phần tử sau của tập mục 𝑋 trong giao dịch 𝑇𝑗 là: 𝐶𝑅𝑈�𝑋, 𝑇𝑗 � = 𝑅𝑈�𝑋, 𝑇𝑗 � nếu 𝑋 đóng trên 𝑇𝑗 . Ngược lại, 𝐶𝑅𝑈�𝑋, 𝑇𝑗 � = 0. Và độ hữu ích đóng của các phần tử sau của tập mục |𝑋| ≤ 2 trong 𝐷 là: 𝐶𝑅𝑈(𝑋) = ∑𝑋⊆𝑇𝑗 ∈𝐷 𝐶𝑅𝑈(𝑋, 𝑇𝑗 ) Ví dụ 3. Tương tự, ta tính được độ hữu ích đóng của các phần tử sau của tập mục 𝑋 = {𝑓, 𝑎} trong giao dịch 𝑇5 : 𝐶𝑅𝑈(𝑋, 𝑇5 ) = 𝑅𝑈(𝑋, 𝑇5 ) = 10 Khi đó: 𝐶𝑅𝑈(𝑋) = 𝐶𝑅𝑈(𝑋, 𝑇5 ) + 𝐶𝑅𝑈(𝑋, 𝑇6 ) = 𝑅𝑈(𝑋, 𝑇5 ) + 𝑅𝑈(𝑋, 𝑇6 ) = 10 + 10 = 20 Định nghĩa 4. Độ hữu ích tiền tố đóng của tập mục 𝑋 trong giao dịch 𝑇𝑗 được tính là: 𝐶𝑃𝑈�𝑋, 𝑇𝑗 � = 𝑃𝑈�𝑋, 𝑇𝑗 � nếu 𝑋 đóng trên 𝑇𝑗 . Ngược lại, 𝐶𝑃𝑈�𝑋, 𝑇𝑗 � = 0. Và khi đó, độ hữu ích tiền tố đóng của tập mục 𝑋 trong cơ sở dữ liệu 𝐷 sẽ là: 𝐶𝑃𝑈(𝑋) = ∑𝑋⊆𝑇𝑗 ∈𝐷 𝐶𝑃𝑈(𝑋, 𝑇𝑗 ), với |𝑋| ≤ 2. Ví dụ 4. 𝐶𝑃𝑈(𝑋) = 𝐶𝑃𝑈(𝑋, 𝑇5 ) + 𝐶𝑃𝑈(𝑋, 𝑇6 ) = 𝑃𝑈(𝑋, 𝑇5 ) + 𝑃𝑈(𝑋, 𝑇6 ) = 𝑈(𝑓, 𝑇5 ) + 𝑈(𝑓, 𝑇6 ) = 6 + 3 = 9. Định nghĩa 5. Độ hữu ích không đóng - NU, độ hữu ích không đóng của các phần tử sau - NRU, và Độ hữu ích tiền tố không đóng - NPU của tập mục 𝑋 trong cơ sở dữ liệu 𝐷 được định nghĩa lần lượt như sau: 𝑁𝑈(𝑋) = 𝑈(𝑋) − 𝐶𝑈(𝑋), 𝑁𝑅𝑈(𝑋) = 𝑅𝑈(𝑋) − 𝐶𝑅𝑈(𝑋), 𝑁𝑃𝑈(𝑋) = 𝑃𝑈(𝑋) − 𝐶𝑃𝑈(𝑋) Định nghĩa 6. Trọng số của tập mục 𝑋 trong giao dịch 𝑇𝑗 là: W�𝑋, 𝑇𝑗 � = �{𝑇𝑘 ∈ 𝐷| 𝐸�𝑋, 𝑇𝑗 � = 𝐸(𝑋, 𝑇𝑘 )}� trong đó 𝐸(𝑋) là tập mục mở rộng của 𝑋 trong 𝑇𝑗 . Ví dụ 5. W({𝑓}, 𝑇1 ) = 2 và W({𝑓, 𝑎}, 𝑇5 ) = 1. Định nghĩa 7. Độ hỗ trợ đóng của tập mục 𝑋 trong cơ sở dữ liệu 𝐷 được định nghĩa như sau: 𝐶𝑠𝑢𝑝𝑝 (𝑋) = ∑𝑋⊆𝑇𝑗 ∈𝐷 𝐶𝑠𝑢𝑝𝑝 (𝑋, 𝑇𝑗 ). Trong đó, 𝐶𝑠𝑢𝑝𝑝 �𝑋, 𝑇𝑗 � = W�𝑋, 𝑇𝑗 � nếu 𝑋 đóng trên 𝑇𝑗 . Ngược lại, 𝐶𝑠𝑢𝑝𝑝 �𝑋, 𝑇𝑗 � = 0. Ví dụ 6. Độ hỗ trợ đóng của tập 𝑋 = {𝑓, 𝑎} trong cơ sở dữ liệu 𝐷 là: 𝐶𝑠𝑢𝑝𝑝 ({𝑓, 𝑎}) = 𝐶𝑠𝑢𝑝𝑝 ({𝑓, 𝑎}, 𝑇1 ) + 𝐶𝑠𝑢𝑝𝑝 ({𝑓, 𝑎}, 𝑇3 ) + 𝐶𝑠𝑢𝑝𝑝 ({𝑓, 𝑎}, 𝑇5 ) + 𝐶𝑠𝑢𝑝𝑝 ({𝑓, 𝑎}, 𝑇6 ) + 𝐶𝑠𝑢𝑝𝑝 ({𝑓, 𝑎}, 𝑇8 ) = 0 + 0 + 1 + 1 + 0 = 2. Định nghĩa 8. Độ hỗ trợ không đóng của tập mục 𝑋 trong cơ sở dữ liệu 𝐷 là: 𝑁𝑠𝑢𝑝𝑝 (𝑋) = 𝑠𝑢𝑝𝑝(𝑋) − 𝐶𝑠𝑢𝑝𝑝 (𝑋) Ví dụ 7. 𝑁𝑠𝑢𝑝𝑝 ({𝑓, 𝑎}) = 𝑠𝑢𝑝𝑝({𝑓, 𝑎}) − 𝐶𝑠𝑢𝑝𝑝 ({𝑓, 𝑎}) = 5 − 2 = 3. B. Bài toán khai thác tập mục hiếm hữu ích cao Cho cơ sở dữ liệu giao dịch 𝐷, ngưỡng độ hữu ích tối thiểu 𝜀 và ngưỡng độ hỗ trợ tối đa 𝑚𝑎𝑥𝑠𝑢𝑝𝑝. Bài toán khai thác tập mục độ hữu ích cao hiếm từ cơ sở dữ liệu 𝐷 là tìm ra những tập mục có lợi nhuận cao nhưng hiếm khi được xuất hiện trong các giao dịch. Tức là, tìm ra những tập mục có tần số xuất hiện nhỏ hơn giá trị độ hỗ trợ tối đa 𝑚𝑎𝑥𝑠𝑢𝑝𝑝 nhưng có độ hữu ích không nhỏ hơn ngưỡng độ hữu ích tối thiểu 𝜀. 𝐻𝑈𝑅𝐼 = {𝑋 | 𝑈(𝑋) ≥ 𝜀 ∧ 𝑠𝑢𝑝𝑝(𝑋) < 𝑚𝑎𝑥𝑠𝑢𝑝𝑝} Ví dụ 1. Cho cơ sở dữ liệu giao dịch sau minh họa tìm tập mục hữu ích cao hiếm:
Vũ Văn Vinh, Lâm Thị Họa Mi, Dương Thị Mộng Thùy 239 Bảng 2. Cơ sở dữ liệu giao dịch Bảng 3. Lợi ích của mỗi Bảng 4. TWU của mỗi Độ hữu ích item trong cơ sở dữ liệu item đã sắp Số lượng Độ hữu Lợi tăng dần Tid Giao dịch giao dịch mua (𝒒) ích (𝑼) Item nhuận (𝑻𝑼) Item TWU 𝑻𝟏 a, c, f 2, 2, 2 6, 2, 6 14 (𝒑) g 39 𝑻𝟐 b, c, d 10, 2, 4 40, 2, 8 50 a 3 e 58 𝑻𝟑 a, d, f, g 3, 5, 2, 6 9, 10, 6, 6 31 b 4 f 86 𝑻𝟒 b, d, g 1, 2, 2 4, 4, 2 10 c 1 c 88 𝑻𝟓 a, b, d, f 1, 2, 1, 2 3, 8, 2, 6 19 d 2 a 96 3, 8, 1, 2, e 6 𝑻𝟔 a, b, c, d, f 1, 2, 1, 3, 1, 1 17 d 125 3 f 3 b 164 𝑻𝟕 a, b 2, 1 6, 4 10 g 1 𝑻𝟖 a, c, f 1, 1, 1 3, 1, 3 7 𝑻𝟗 b, e 1, 54 4, 54 58 Mỗi giao dịch trong cơ sở dữ liệu gốc trong bảng 2 được sắp xếp lại theo thứ tự TWU tăng dần và các item sẽ bị xóa khỏi cơ sở dữ liệu ban đầu nếu có giá trị TWU nhỏ hơn ngưỡng độ hữu ích tối thiểu 𝜀. Bảng 5: Cơ sở dữ liệu sau khi sắp xếp Số lượng Độ hữu Độ hữu ích Tid Giao dịch mua (𝒒) ích (𝑼) giao dịch (𝑻𝑼) 𝑻𝟏 f, c, a 2, 2, 2 6, 2, 6 14 𝑻𝟐 c, d, b 2, 4, 10 2, 8, 40 50 𝑻𝟑 f, a, d 2, 3, 5 6, 9, 10 25 𝑻𝟒 d, b 2, 1 4, 4 8 𝑻𝟓 f, a, d, b 2, 1, 1, 2 6, 3, 2, 8 19 1, 1, 1, 1, 3, 1, 3, 2, 𝑻𝟔 f, c, a, d, b 17 2 8 𝑻𝟕 a, b 2, 1 6, 4 10 𝑻𝟖 f, c, a 1, 1, 1 3, 1, 3 7 𝑻𝟗 e, b 54, 1 54, 4 58 Với ngưỡng độ hữu ích tối thiểu 𝜀 = 40 và phần trăm ngưỡng độ hỗ trợ hỗ trợ tối đa được chọn là 𝜎 = 30%. Khi đó, 𝑚𝑎𝑥𝑠𝑢𝑝𝑝 = 30% ∗ 9 = 2,7. Tập mục độ hữu ích cao hiếm tìm được là: 𝐻𝑈𝑅𝐼 = {𝑒: (#𝑢𝑡𝑖𝑙𝑖𝑡𝑦: 54, #𝑠𝑢𝑝𝑝: 1), 𝑒𝑏: (#𝑢𝑡𝑖𝑙𝑖𝑡𝑦: 58, #𝑠𝑢𝑝𝑝: 1), 𝑐𝑏: (#𝑢𝑡𝑖𝑙𝑖𝑡𝑦: 51, #𝑠𝑢𝑝𝑝: 2), 𝑐𝑑𝑏: (#𝑢𝑡𝑖𝑙𝑖𝑡𝑦: 61, #𝑠𝑢𝑝𝑝: 2)} C. Cấu trúc lưu trữ dữ liệu Trong phần này chúng tôi trình bày cấu trúc lưu trữ dữ liệu được sử dụng trong thuật toán khai thác tập HURI là RCUL (Revised Compact Utility List) được cải tiến từ cấu trúc CUL (Compact Utility List) [3]. Đây là một cấu trúc nhỏ gọn đã được chứng minh hiệu quả và và dễ dàng triển khai các chiến lược tỉa một cách hiệu quả. Việc sử dụng cấu trúc lưu trữ RCUL giúp lưu lại một số thông tin cần thiết gồm có: NU, NRU, CU, CRU, CPU, Csupp, Nsupp. Cơ sở dữ liệu được quét một lần để tính các giá trị trên và lưu vào RCUL mức 1 (1-RCUL của những tập mục chứa một item). Ở các mức tiếp theo (k-RCUL), việc tính toán các thông số của RCUL được thực hiện dựa vào RCUL mức trước đó. Điều này giúp giảm đáng kể thời gian thực thi vì không phải quét lại cơ sở dữ liệu nhiều lần. Cấu trúc RCUL của tập mục 𝑋, ký hiệu là RCUL(X) được mô tả như hình 1. Hình 1. Cấu trúc RCUL của tập X, RCUL(X) RCUL(X) gồm 2 thành phần cơ bản: (1) Các thông tin tổng quát của tập mục X: NU(X), NRU(X), CU(X), CRU(X), CPU(X), Csupp(X), và Nsupp(X).
240 NÂNG CAO TÍNH HIỆU QUẢ TRONG VIỆC KHAI THÁC TẬP HỮU ÍCH CAO HIẾM TRÊN CƠ SỞ DỮ LIỆU LỚN (2) Một tập hợp lưu thông tin của những giao dịch không đóng có chứa 𝑋. Mỗi phần tử trong tập hợp là bộ gồm 6 giá trị, được ký hiệu là TidInfo(X, Tid): < 𝑇𝑖𝑑 , 𝑁𝑈(𝑋, 𝑇𝑖𝑑 ), 𝑁𝑅𝑈(𝑋, 𝑇𝑖𝑑 ), 𝑃𝑈(𝑋, 𝑇𝑖𝑑 ), 𝑃𝑃𝑜𝑠(𝑋, 𝑇𝑖𝑑 ), 𝑊(𝑋, 𝑇𝑖𝑑 ) > Thông tin Csupp , Nsupp trong cấu trúc RCUL lần lượt là số lượng giao dịch đóng, số lượng giao dịch không đóng chứa 𝑋 nhằm dễ dàng hơn trong việc tính độ hỗ trợ của 𝑋 trong toàn cơ sở dữ liệu bằng một phép toán đơn giản 𝑠𝑢𝑝𝑝(𝑋) = 𝐶𝑠𝑢𝑝𝑝 + 𝑁𝑠𝑢𝑝𝑝 . PPos(X, Tid) trong các RCUL giúp xác định vị trí của item trước của một item trong cùng một giao dịch của RCUL đang xét. Nhờ vậy, việc cập nhật thông tin các giao dịch sẽ thực hiện nhanh và hiệu quả hơn rất nhiều, đặc biệt khi các giao dịch trùng nhau. |𝑅𝐶𝑈𝐿[𝑃𝑟𝑒𝑣(𝑥𝑘 , 𝑇𝑖𝑑 )]. 𝑇𝑖𝑑 |, nếu 𝑃𝑟𝑒𝑣(𝑥𝑘 ) ≠ −1 𝑃𝑃𝑜𝑠(𝑋, 𝑇𝑖𝑑 ) = � −1, ngược lại Ví dụ 2. Xét cơ sở dữ liệu trong bảng 5, 𝑅𝐶𝑈𝐿(𝑋) với 𝑋 là những tập mục 1-item (với thứ tự các item được sắp trong bảng 4: Cơ sở dữ liệu sẽ lần lượt duyệt các giao dịch tử trên xuống dưới và thêm chúng lần lượt vào 1-RCUL. Tại mỗi giao dịch, các item sẽ được duyệt theo thứ tự ngược tức là duyệt từ item cuối của giao dịch lần lượt lên tới item đầu tiên của nó. Cách duyệt ngược như vậy sẽ giúp cho việc tính giá trị độ hữu ích của các phần tử sau của các item đang xét được dễ dàng hơn. Trong quá trình xét, giao dịch nào là giao dịch đóng thì thông tin của giao dịch đó sẽ được lưu vào phần thành phần thứ (1) của các RCUL như CU, CPU, CRU, và Csupp. Hình 2. 1- RCUL của cơ sở dữ liệu Tất cả những giao dịch có cùng tập phần tử phía sau của tập mục 𝑋 sẽ được gộp, lưu trữ một lần và những giá trị liên quan đến những giao dịch đó trong RCUL(X) sẽ được cộng dồn. Ví dụ, trong bảng 5, xét giao dịch T1 = {f, c, a} và T8 = {f, c, a} với tập mục 𝑋 = {𝑓}. Ta thấy các phần tử phía sau của 𝑋 giống nhau và là {𝑐, 𝑎}. Khi đó, T1 và T8 sẽ được gộp vào với nhau. Tuy nhiên, khi gộp các giao dịch thì số lượng giao dịch sau khi gộp sẽ không còn đại diện cho độ hỗ trợ của 𝑋, trong khi bài toán cần thiết phải tính độ hỗ trợ của X (𝑠𝑢𝑝𝑝(𝑋)). Để giải quyết vấn đề này, chúng tôi sử dụng đại lượng W để lưu thông tin về số lượng các giao dịch đã được gộp. Việc xây dựng các RCUL được chia thành hai giai đoạn là 1-RCUL và k-MCUL. 1-RCUL là RCUL lưu thông tin các tập mụckj chỉ chứa 1 item, và được xây dựng dựa trên việc quét cơ sở dữ liệu. Đối với k-RCUL (với 𝑘 ∝ 2) sẽ được tạo từ các RCUL của các tập mục ở mức trước mà không cần quét lại cơ sở dữ liệu. k-RCUL được xây dựng từ các RCUL mức (k−1) bằng cách kết hợp 2 (k−1)-RCUL có chung tiền tố. Để xây dựng k-RCUL của tập mục 𝑅𝑥𝑦 là RCUL(Rxy) ta cần có RCUL(Rx) và RCUL(Ry) đã được tạo ra ở bước trước đó. Thuật toán sẽ xác định các giá trị đóng của RCUL(Pxy) như 𝐶𝑈(𝑃𝑥𝑦) = 𝐶𝑈(𝑃𝑥) + 𝐶𝑈(𝑃𝑦) − 𝐶𝑃𝑈(𝑃𝑥), 𝐶𝑅𝑈(𝑃𝑥𝑦) = 𝐶𝑅𝑈(𝑃𝑦), 𝐶𝑃𝑈(𝑃𝑥𝑦) = 𝐶𝑈(𝑃𝑥), và 𝐶𝑆𝑈𝑃(𝑃𝑥𝑦) = 𝐶𝑆𝑈𝑃(𝑃𝑥). Thuật toán sẽ tìm tất cả các TidInfo trong RCUL(Px) mà có 𝑇𝑖𝑑 bằng với 𝑇𝑖𝑑 của một TidInfo trong RCUL(Py) để tiến hành gộp và tạo thành TidInfo mới đưa vào RCUL(Pxy) và cập nhật lại thông tin của các thuộc tính NU, NRU, PU và NSUP cho tới khi không tìm được nữa thì dừng. Tuy nhiên, trong quá trình thực hiện thuật toán, các RCUL(Pxy) không được tạo riêng lẻ mà được tạo đồng bộ cùng một lúc bằng cách kết hợp RCUL ở một vị trí xác định với tất cả các RCUL cùng cấp phía sau nó nhằm dễ dàng xác định thông tin PPos, xác định giao dịch đóng và hạn chế số lần duyệt các TidInfo trong RCUL(Px). D. Một số tính chất tỉa ứng viên hiệu quả − Tỉa CSUP: Nếu số lượng giao dịch đóng lớn hơn ngưỡng support nó và các mở rộng của nó không phải là HURI. Ta có: CSUP(X) + NSUP(X)= supp(X), do đó nếu CSUP(X) > 𝑚𝑎𝑥𝑠𝑢𝑝𝑝 thì supp(X) > 𝑚𝑎𝑥𝑠𝑢𝑝𝑝 nên X sẽ không phải là HURI. Hơn thế nữa CSUP(X) là độ hỗ trợ đóng của X nên các đó cũng là số lượng các giao dịch đóng chứa X nên các giao dịch này cũng chứa các mở rộng của X nên độ hỗ trợ của các mở rộng của X cũng lơn hơn 𝑚𝑎𝑥𝑠𝑢𝑝𝑝 và chúng cũng không phải là HURI.
Vũ Văn Vinh, Lâm Thị Họa Mi, Dương Thị Mộng Thùy 241 − Tỉa TWU: Nếu một tập có TWU nhỏ hơn ngưỡng tối thiểu thì tập đó và tập cha của nó không phải là là HUI và HURI. Hay nếu 𝑇𝑊𝑈(𝑋) < 𝑚𝑖𝑛𝑢𝑡𝑖𝑙 thì ∀𝑋 ′ ⊃ 𝑋: 𝑋 ′ ∉ 𝐻𝑈𝑅𝐼. Khi TWU(X) < 𝑚𝑖𝑛𝑢𝑡𝑖𝑙 thì ∀𝑋 ′ ⊃ 𝑋, 𝑋 ′ không phải là tập HUI, do đó cũng phải là HURI. − Tỉa U + RU: Nếu tổng độ hữu ích của tập X và phần còn lại của X trong các giao dịch nhỏ hơn hoặc bằng ngưỡng tối thiểu thì 𝑋 và các tập mở rộng của nó không phải là tập hữu ích cao và đó cũng phải là tập hữu ích cao hiếm. Do đó nếu 𝑈(𝑋) + 𝑅𝑈(𝑋) < 𝑚𝑖𝑛𝑢𝑡𝑖𝑙 thì ∀𝑋 ′ ⊃ 𝑋: 𝑋 ′ ∉ 𝐻𝑈𝑅𝐼. Khi 𝑈(𝑋) + 𝑅𝑈(𝑋) < 𝑚𝑖𝑛𝑢𝑡𝑖𝑙 thì ∀𝑋 ′ ⊃ 𝑋, 𝑋 ′ sẽ không phải HUI nên cũng không phải là HURI. − Tỉa EUCS: Một ma trận tam giác dự đoán độ hữu ích EUCS và được xác định 𝐸𝑈𝐶𝑆[𝑖, 𝑗] = 𝑇𝑊𝑈(𝑋 = {𝑖, 𝑗}) được đề xuất bởi Fournier-Viger lưu trữ giá trị 𝑇𝑊𝑈 theo từng cặp các item trong CSDL. Với 𝑋 = {𝑥, 𝑦} có 𝐸𝑈𝐶𝑆[𝑥, 𝑦] < 𝑚𝑖𝑛𝑢𝑡𝑖𝑙 thi 𝑋 và tất cả các tập chứa 𝑋 đều không phải là tập HUI và HURI. Hay nếu 𝐸𝑈𝐶𝑆(𝑋) < 𝑚𝑖𝑛𝑢𝑡𝑖𝑙 thì ∀𝑋 ′ ⊃ 𝑋: 𝑋 ′ ∉ 𝐻𝑈𝑅𝐼. − Tỉa LA-prune: Với 2 tập 𝑋 và 𝑌, tổng độ hữu ích của 𝑋 nếu trên giao dịch đóng và giao dịch không đóng không chứa 𝑌 nhỏ hơn ngưỡng tối thiểu thì mọi tập cha của tập 𝑋𝑌 đều không phải là HUI [3] nên cũng phải là HURI. Hay 𝑁𝑈(𝑋) + 𝑁𝑅𝑈(𝑋) + 𝐶𝑅𝑈(𝑋) + 𝐶𝑈(𝑋) − � 𝑁𝑈�𝑋, 𝑇𝑗 � + 𝑁𝑅𝑈�𝑋, 𝑇𝑗 � < 𝑚𝑖𝑛𝑢𝑡𝑖𝑙 ∀𝑇𝑗 ∈𝐷,𝑋⊆𝑇𝑗 ∧ 𝑌⊆ 𝑇𝑗 thì ∀𝑋 ′ ⊇ 𝑋, ∀𝑌 ′ ⊇ 𝑌 ∶ 𝑋 ′ 𝑌 ′ ∉ 𝐻𝑈𝑅𝐼. − Tỉa C-prune: Với 2 tập 𝑋, và 𝑌, tổng độ hữu ích của 𝑋 trên các giao dịch đóng và tổng độ hữu ích và trên các giao dịch chứa cả 𝑋 và 𝑌 nhỏ hơn ngưỡng tối thiểu nên các tập cha của 𝑋𝑌 không phải là HUI [3] từ đó XY cũng phải là HURI. E. Thuật toán Thuật toán EHURI sẽ khai phá tất cả các tập hữu ích cao hiếm trong cơ sở dữ liệu D thỏa ngưỡng độ hữu ích η, ngưỡng độ hỗ trợ nhỏ hơn hoặc bằng 𝑚𝑎𝑥𝑠𝑢𝑝. Vì HURI cũng là tập HUI những có thêm độ hỗ trợ không vượt qua 𝑚𝑎𝑥𝑠𝑢𝑝 nên ta cần phải tính toán và xác định cả độ hữu ích và độ hỗ trợ của các tập hợp trong quá trình khai thác. Đầu tiên thuật toán sẽ quét cơ sở dữ liệu để tính TWU cho tất cả các item, từ đó áp dụng chiến lược tỉa TWU để loại bỏ các item mà không tham gia trong các HURI. Các item còn lại sau khi loại bỏ sẽ được sắp xếp tăng dần theo TWU của chúng để giảm bớt thao tác trong quá trình kết hợp của các RCUL ở các bước sau giảm thời gian thực thi của thuật toán. Bước 3, thuật toán sẽ loại bỏ các item không thỏa TWU ra khỏi các giao dịch trong D và sắp xếp lại các mục trong từng giao dịch theo thứ tự đã được thiết lập ở Bước 2 và loại bỏ các giao dịch rỗng. Bước 4 và 5, thuật toán sẽ xây dựng các RCUL của các tập có 1 mục gọi là 1-RCULs và bảng EUCS phục vụ cho chiến lược tỉa EUCP ở các bước sau. Từ đó thuật toán sẽ được thực hiện đệ quy để tìm tất cả các HURI trong D thông qua hàm Search_HURI. Algorithm: EHURI Input: Cơ sở dữ liệu 𝐷, ngưỡng η, ngưỡng độ hỗ trợ 𝑚𝑎𝑥𝑠𝑢𝑝𝑝 Output: 𝐻𝑈𝑅𝐼𝑠: tập hợp các tập hữu ích cao hiếm.. 1. Quét 𝐷 và tính 𝑇𝑊𝑈 cho tất các 1-itemsets 2. Sắp xếp các mục tăng dần theo 𝑇𝑊𝑈; 3. Quét D và loại bỏ các mục 𝑖 mà 𝑇𝑊𝑈(𝑖) < η, sắp xếp các mục trong mỗi giao dịch theo thứ tự ở Bước 2 và xóa bỏ các giao dịch rỗng. 4. Xây dựng các 1-RCULs; 5. Xây dựng bảng EUCS; 6. 𝐻𝑈𝑅𝐼𝑠 = 𝑆𝑒𝑎𝑟𝑐ℎ_𝐻𝑈𝑅𝐼 (∪ , 1 − 𝑅𝐶𝑈𝐿𝑠, η, 𝑚𝑎𝑥𝑠𝑢𝑝𝑝); Thủ tục Search_HURI sẽ có đầu vào là tập hợp các mục P, các RCULs của các tập hợp có tiền tố là P và các ngưỡng η, 𝑚𝑎𝑥𝑠𝑢𝑝𝑝 do người dùng xác định. Search_HURI sẽ duyệt lần lượt tất cả các RCUL để xác định xem tập mục đang xét X có phải tập hữu ích cao và có độ hỗ trợ CUSP(X) + NSUP(X) nhỏ hơn maxsup hay không. Nếu thỏa thì X sẽ được thêm vào tập các HURI cần khai phá. Trong bước 4 áp dụng chiến lược tỉa CSUP để bỏ qua các tập hợp không thỏa yêu cầu về độ hỗ trợ. Bước 5 sẽ vận dụng phép tỉa U + RU để xem xét một tập hợp có cần tiếp tục xem xét các mở rộng của nó hay không. Nếu thảo, thuật toán sẽ kết hợp RCUL đang xét với tất cả các RCUL phía sau để tạo ra các exRCUL của các tập hợp có tiền tố là X. Từ đó thủ tục Search_HURI được goi đệ qui để tìm các HURI có tiền tố là X trong cơ sở dữ liệu D.
242 NÂNG CAO TÍNH HIỆU QUẢ TRONG VIỆC KHAI THÁC TẬP HỮU ÍCH CAO HIẾM TRÊN CƠ SỞ DỮ LIỆU LỚN Procedure: Search_HURI Input: 𝑃: tập tiền tố, tập RCULs, ngưỡng η, 𝑚𝑎𝑥𝑠𝑢𝑝𝑝 Output: 𝐻𝑈𝑅𝐼𝑠: tập hợp các tập hữu ích cao hiếm có tiền tố là tập P. 1. for each vị trí 𝑖 trong tập RCULs do 2. 𝑋 = 𝑃 ∪ 𝑅𝐶𝑈𝐿𝑠[𝑖]. 𝑖𝑡𝑒𝑚; 𝑠𝑢𝑝 = 𝑆𝑢𝑝(𝑋); 3. If (U(X) ∝ η và CUSP(X) + NSUP(X) < 𝑚𝑎𝑥𝑠𝑢𝑝𝑝) 𝐻𝑈𝑅𝐼𝑠 = 𝐻𝑈𝑅𝐼𝑠 ∪ 𝑋; 4. 𝑖𝑓(CUSP(X) ≥ 𝑚𝑎𝑥𝑠𝑢𝑝𝑝) Continue ; 5. if (𝑈(𝑋) + 𝑅𝑈(𝑋) ∝ η then 6. 𝑒𝑥𝑅𝐶𝑈𝐿𝑠 = 𝐶𝑜𝑛𝑠𝑡𝑟𝑢𝑐𝑡_𝑅𝐶𝑈𝐿(𝑅𝐶𝑈𝐿𝑠, 𝑖, η); 7. 𝑖𝑓(𝑒𝑥𝑅𝐶𝑈𝐿𝑠! = 𝑛𝑢𝑙𝑙) 𝑆𝑒𝑎𝑟𝑐ℎ_𝐻𝑈𝑅𝐼 (𝑋, 𝑒𝑥𝑅𝐶𝑈𝐿𝑠, η, 𝑚𝑎𝑥𝑠𝑢𝑝𝑝); 8. end if 9. end for Thủ tục Construct_RCUL là thủ tục có nhiệm vụ kết hợp RCUL[i] với các RCUL[j] trong RCULs để tạo ra các RCUL mới mà có tiền tố là là RCUL của ở vị trí i. Procedure: Construct_RCUL Input: 𝑅𝐶𝑈𝐿𝑠: 𝑑𝑎𝑛ℎ 𝑠á𝑐ℎ 𝑅𝐶𝑈𝐿, 𝑠𝑡: 𝑣ị 𝑡𝑟í 𝑏ắ𝑡 đầ𝑢, η: ngưỡng do người dùng xác định Output: 𝑒𝑥𝑅𝐶𝑈𝐿𝑠: danh sách các RCUL mở rộng từ RCUL[st] 1. 𝑠𝑧 = |𝑅𝐶𝑈𝐿𝑠| − 𝑠𝑡; 2. 𝑥 = 𝑅𝐶𝑈𝐿𝑠[𝑠𝑡]. 𝑖𝑡𝑒𝑚; 3. for 𝑖 từ 0 tới 𝑠𝑧 − 1 do 4. 𝑦 = 𝑅𝐶𝑈𝐿𝑠[𝑠𝑡 + 𝑖]. 𝑖𝑡𝑒𝑚; 5. if (𝐸𝑈𝐶𝑆[𝑥, 𝑦] ∝ η) then 6. Khởi tạo 𝑒𝑥𝑅𝐶𝑈𝐿𝑠[𝑖]; 7. Khởi tạo 𝐿𝐴𝑈[𝑖] và 𝐶𝑈𝑇𝐼𝐿[𝑖]; 8. end if 9. end for 10. for mỗi 𝑖𝑇𝑖𝑑𝐶𝑈𝐿 trong 𝑅𝐶𝑈𝐿𝑠[𝑣𝑡]. 𝑇𝑖𝑑𝐿𝑖𝑠𝑡 do 11. 𝑡𝑖𝑑 = 𝑖𝑇𝑖𝑑𝐶𝑈𝐿. 𝑡𝑖𝑑; 12. for 𝑗 từ 0 đến 𝑠𝑧 − 1 do 13. if (𝑅𝐶𝑈𝐿𝑠[𝑗 + 𝑣𝑡]. 𝑇𝑖𝑑𝐿𝑖𝑠𝑡 = 𝑁𝑈𝐿𝐿) then 14. Cập nhật 𝐿𝐴𝑈[𝑖]; 15. if (𝐿𝐴𝑈[𝑗] < η) then 𝑒𝑥𝑅𝐶𝑈𝐿𝑠[𝑗] = 𝑁𝑈𝐿𝐿; 16. else 17. Cập nhật 𝐶𝑈𝑇𝐼𝐿[𝑗]; 18. end if 19. //update 𝑒𝑥𝑅𝐶𝑈𝐿𝑠 20. if (tid chứa trong tất cả 𝑅𝐶𝑈𝐿𝑠 đứng sau 𝑅𝐶𝑈𝐿𝑠[𝑣𝑡]) then 21. Cập nhật 𝐶𝑃𝑈, 𝐶𝑈, 𝐶𝑅𝑈, 𝐶𝑆𝑈𝑃 trong tất cả 𝑒𝑥𝑅𝐶𝑈𝐿𝑠; 22. else 23. if (tid trung với giao dịch trước đó) then 24. Cập nhật giá trị trong 𝑖𝑇𝑖𝑑𝐶𝑈𝐿; 25. else
Vũ Văn Vinh, Lâm Thị Họa Mi, Dương Thị Mộng Thùy 243 26. Thêm mới 𝑖𝑇𝑖𝑑𝐶𝑈𝐿 vào 𝑒𝑥𝑅𝐶𝑈𝐿𝑠[𝑗] tương ứng với 𝑅𝐶𝑈𝐿𝑠[𝑗 + 𝑠𝑡] chứa tid; 27. end if 28. end if 29. end if 30. end for 31. Loại bỏ 𝑒𝑥𝑅𝐶𝑈𝐿𝑠[𝑗] nếu 𝑒𝑥𝑅𝐶𝑈𝐿𝑠[𝑗] = 𝑁𝑈𝐿𝐿 hoặc 𝐶𝑈𝑇𝐼𝐿[𝑗] < η 32. return 𝒆𝒙𝑴𝑪𝑼𝑳𝒔 Như vậy ban đầu xuất phát việc xây dựng các 1-RCUL cho cac tập hợp chỉ gồm 1 mục. Từ các cấu trúc này thuật toán dễ dàng xác định được độ hữu ích cũng như độ hỗ trợ của các itemset để xác định một tập có phải là rareHUI hay không? Thuật toán sẽ tiếp tục kết hợp các RCUL ở mức k (k-RCUL) với nhau để tạo thành các RCUL ở mức k+1 ((k+1)-RCUL) và cứ vậy cho tới khi không còn RCUL nào được sinh ra thì thuật toán dừng. IV. THỰC NGHIỆM Thuật toán được cài đặt và thực nghiệm trên môi trường có cấu hình như sau core i5, ram 8GB sử dụng hệ điều hành windows 10. Công cụ dùng để phát triển thuật toán: Eclipse, phiên bản: Mars.2 Release (4.5.2), ngôn ngữ: Java. Các cơ sở dữ liệu dùng cho thực nghiệm là các cơ sở dữ liệu chuẩn được tải từ website mã nguồn mở SPMF phát triển bởi Philippe: http://www.philippe-fournier-viger.com/spmf/index.php?link=datasets.php [16]. Kết quả thử nghiệm trên cơ sở dữ liệu BMS, Retail. Đây là 2 cơ sở dữ liệu thưa có số lượng giao dịch lần lượt là 59,601 và 88,162 với độ dài trung bình của các giao dịch là 4,8 và 10,3. Dựa vào kết quả thực nghiệm sẽ giúp chứng minh tính hiệu quả của thuật toán đề xuất so với thuật toán RareHUI ở các mức hỗ trợ khác nhau và ngưỡng minUtil khác nhau. Cụ thể với BMS, các ngưỡng thực nghiệm với độ hỗ trợ là 0,03; 0,05; 0,07 và 0,09. Đối với Retail sẽ thực nghiệm với độ hỗ trợ là 0,01, 0,02; 0,03 và 0,04. Hình 3. Thời gian thực thi trên BMS và Retail Do việc thực thi của EHURI chỉ sử dụng một giai đoạn nên thời gian thực thi vượt trội hơn hẳn so với thuật toán RareHUI. Hơn thế nữa việc áp dụng nhiều chiến lược tỉa hiệu quả giúp thu gọn đáng kể số lượng ứng viên cần phải tính toán giúp cho thời gian tiêu tốn ít hơn rất nhiều từ 2 lần tới hơn 10 lần. Hình 4. Bộ nhớ sử dụng trên BMS và Retail Tính hiệu quả của cấu trúc RCUL cũng giúp cho dữ liệu được nén lại làm cho bộ nhớ sử dụng trong quá trình thực thi cũng giảm hơn so với thuật toán RareHUI. V. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Bài báo này đã trình bày một thuật toán mới EHURI để khai thác tập hữu ích cao hiếm hiệu quả hơn các thuật toán đã có. Thuật toán đã sử dụng cấu trúc lưu trữ RCUL để lưu trữ thông tin giúp cho việc thực thi thuật toán hiệu quả hơn. Thuật toán cũng áp dụng tính chất của độ hỗ trợ đóng để tỉa bớt các ứng viên kết hợp với các chiến lược tỉa hiện đại đã làm cho thời gian thực hiện và không gian lưu trữ giảm đi rất nhiều. Kết quả thực nghiệm cho thấy EHURI hiệu quả hơn thuật toán RareHUI về thời gian thực thi, bộ nhớ lưu trữ trong các cơ sở dữ liệu thực nghiệm.
244 NÂNG CAO TÍNH HIỆU QUẢ TRONG VIỆC KHAI THÁC TẬP HỮU ÍCH CAO HIẾM TRÊN CƠ SỞ DỮ LIỆU LỚN Chúng tôi sẽ mở rộng ý tưởng được giới thiệu trong EHURI cho bài toán khai thác tập hữu ích cao hiếm trên cơ sở dữ liệu tăng trưởng và áp dụng kỹ thuật cơ sở dữ liệu chiếu để giảm bớt không giam lưu trữ. TÀI LIỆU THAM KHẢO [1] SzathmaryL, Napoli A, Valtchev P, “Towards rare itemset mining”, Tools with artificial intelligence 19th IEEE international conference, 2017. [2] Pillai J., Vyas O.P., Muyeba M, “HURI - A novel algorithm for mining high utility rare itemsets”, Advances in Intelligent Systems and Computing, vol. 177, Advances in Intelligent Systems and Computing, 2013. [3] S. Krishnamoorthy, “HMiner: Efficiently mining high utility itemsets”, Expert Systems with Applications, pp. 168-183, 2017. [4] Agrawal, R., Ramakrishnan, Srikant, O, “Fast algorithms for mining association rules”, Proc. 20th international conference very large data bases, VLDB, 1994. [5] Adda M, Wu L, White S, Feng Y , “Pattern detection with rare item-set mining. ar”, arXiv preprint. arXiv:1209.3089, 2007. [6] Y. Liu, W. Liao, A. Choudhary, “A two-phase algorithm for fast discovery of high utility itemsets”, Advances in Knowledge Discovery and Data Mining, PAKDD, 2005. [7] V. S. Tseng, C. W. Wu, B. E. Shie, P. S. Yu, “UP-Growth: an efficient algorithm for high utility itemset mining”, International Conference on Knowledge Discovery and Data Mining, KDD, 2010. [8] B. Le, H. Nguyen, B. Vo, “An efficient strategy for minings high utility itemsets”, International Journal of Intelligent Information and Database Systems, vol. 5, no. 2, pp. 164-176, 2011. [9] V. S. Tseng, B. Shie, C. Wu, P. S. Yu, “Efficient algorithms for mining high utility itemsets from transactional databases”, IEEE Transactions on Knowledge and Data Engineering, vol. 25, no. 8, pp. 1772-1786, 2013. [10] M. Liu, J. Qu, “Mining high utility itemsets without candidate generation”, CIKM, 2012. [11] P. Fournier-Viger, C. W. Wu, S. Zida, V. S. Tseng, “FHM: Faster high-utility itemset mining using estimated utility co- occurrence pruning”, Foundations of Intelligent Systems, ISMIS, 2014. [12] S. Zida, P. Fournier-Viger, J. C. Lin, C. Wu, V. S. Tseng, “EFIM: A highly efficient algorithm for high-utility itemset mining”, Knowledge and Information Systems, vol. 51, no. 2, pp. 595-625, 2017. [13] Adda M, Wu L, “Rare itemse tmining”, IEEE 6th International Conference on Machine Learning and Applications, ICMLA, 2007. [14] Koh YS, Rountree N, “Finding sporadic rules using Apriori-inverse”, Pacific-Asia Conference on Knowledge Discovery and Data Mining, Berlin, Heidelberg, 2005. [15] Goyal V., Dawar S., Sureka A, “High Utility Rare Itemset Mining over Transaction Databases”, Databases in Networked Information Systems, vol. 8999, p. 2015. [16] P. Fournier-Viger, A. Gomariz, A. Soltani, H. Lam, “An open-source data mining library [Online]”, 2014. [Online]. Available: http://www.philippe-fournier-viger.com. IMPROVE THE EFFICIENCY OF HIGH UTILITY RARE ITEMSET MINING IN LARGE DATABASES Vu Van Vinh, Lam Thi Hoa Mi, Duong Thi Mong Thuy ABSTRACT: High utility itemset mining has great significance in production and business activities. In many practical situations, rare cases are of higher concern (e.g., in medicine, rare symptoms pose challenges and provide useful insights for physicians in the disease). Rare itemset mining is a topic of interest to many scientists today. Several algorithms have been proposed to solve this problem, but it consumes much time and usages. In this paper, we will propose and apply a suitable data structure to build a rare high utility itemset mining that is more efficient than previous algorithms in both space and time.