Một khảo sát về khai thác tập hữu ích cao có tính tương quan

Chia sẻ: Tưởng Trì Hoài | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

7
lượt xem 2
download

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

Bài báo "Một khảo sát về khai thác tập hữu ích cao có tính tương quan" trình bày về khảo sát tổng quan một số nghiên cứu gần đây về khai thác tập hữu ích cao có tương quan trên cơ sở dữ liệu giao dịch và đưa ra một số gợi mở cho các nghiên cứu tiếp theo. 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: Một khảo sát về khai thác tập hữu ích cao có tính tương quan

Kỷ yếu Hội thảo khoa học Khoa Công nghệ thông tin, năm 2024 MỘT KHẢO SÁT VỀ KHAI THÁC TẬP HỮU ÍCH CAO CÓ TÍNH TƯƠNG QUAN Nguyễn Văn Lễ1, * Trường Đại học Công Thương Thành phố Hồ Chí Minh 1 * Email: lenv@huit.edu.vn Ngày nhận bài: 07/04/2024 ; Ngày chấp nhận đăng: 20/05/2024 TÓM TẮT Bài toán khai thác tập hữu ích cao đã có nhiều nghiên cứu và ứng dụng trên thực tế, đặc biệt là trong lĩnh vực kinh doanh. Trong đó, tri thức được khai phá dựa trên việc tìm ra các tập mặt hàng mua cùng nhau có tổng lợi nhuận cao hơn ngưỡng độ hữu ích tối thiểu cho trước. Kết quả khai thác sẽ hỗ trợ cho người quản lý đưa ra các quyết định tốt nhất nhằm tăng lợi nhuận trong kinh doanh. Tuy nhiên với một số mặt hàng có mức lợi nhuận cao bất thường thì sự kết hợp của mặt hàng đó với bất kỳ mặt hàng nào khác có trong giao dịch cũng đều là tập hữu ích cao dẫn đến sự không hợp lý trong các tập kết quả khai thác. Để giải quyết vấn đề này, độ đo về tương quan được đưa vào trong khai thác tập hữu ích cao với nhiều đề xuất từ các thuật toán khác nhau. Các thuật toán này có sự khác nhau về cấu trúc dữ liệu, cách thức áp dụng chiến lược tỉa cũng như hiệu suất thực thi được so sánh trên hai tiêu chí là thời gian chạy và bộ nhớ sử dụng. Bài báo này trình bày về khảo sát tổng quan một số nghiên cứu gần đây về khai thác tập hữu ích cao có tương quan trên cơ sở dữ liệu giao dịch và đưa ra một số gợi mở cho các nghiên cứu tiếp theo. Từ khóa: Tập hữu ích cao, tính tương quan, cơ sở dữ liệu giao dịch, khai thác dữ liệu, chiến lược tỉa. 1. GIỚI THIỆU Trong kinh doanh, dữ liệu luôn là tài sản vô giá. Trong đó ẩn chứa những quy luật, tri thức mà nếu khai thác được sẽ giúp ích rất nhiều cho người quản lý trong việc điều hành và đưa ra những chiến lược, định hướng phù hợp. Vì vậy đã có nhiều nghiên cứu trong lĩnh vực khai thác dữ liệu đặc biệt là khai thác tập hữu ích cao nhằm tìm ra những tập mặt hàng được mua cùng nhau sao cho tổng lợi nhuận cao hơn một ngưỡng cho trước. Dựa vào kết quả khai thác được có thể giúp người quản lý điều chỉnh nguồn hàng, thiết kế gợi ý sản phẩm, tạo gói khuyến mãi…để đạt mục tiêu kinh doanh là tăng lợi nhuận. Một số thuật toán được đề xuất từ rất sớm để khai thác tập hữu ích cao (High Utility Itemsets - HUIs) trong hai pha điển hình như thuật toán Two Phase [1], UP-Growth [2]. Đến năm 2012, Liu và cộng sự đề xuất cấu trúc Utility-List để khai thác HUIs trên một pha bằng thuật toán HUI-Miner [3]. Năm 2014, Fournier-Viger [4] đề xuất cấu trúc EUCS và thuật toán FHM khai thác HUIs hiệu suất cao với các cơ sở dữ liệu thưa, sau đó nhóm tác giả Fournier-Viger cải tiến thuật toán bằng cách bổ sung ràng buộc chiều dài vào bài toán khai thác HUIs với thuật toán FHM+ [5]. Năm 2016, Liu và cộng sự đề xuất thuật toán FHN [6] để khai thác HUIs với lợi nhuận âm. Ngoài ra, một số thuật toán khai thác tập hữu ích cao hiệu quả khác như EFIM được đề xuất bởi Zida và cộng sự [7], Hminer được đề xuất bởi Krishnamoorthy [8] với cấu trúc CUL và nhiều chiến lược tỉa cho hiệu suất thực thi vượt trội. 115
Nguyễn Văn Lễ Mặc dù các nghiên cứu khai thác tập HUIs đã có nhiều cải tiến, tuy nhiên kết quả khai thác có thể thu được tập HUIs rất lớn hoặc còn nhiều tập kết quả trong đó tính tương quan giữa các mặt hàng còn thấp. Những tập này không có ý nghĩa trong phân tích kinh doanh. Để giải quyết vấn đề này, tính tương quan giữa các phần tử trong tập mặt hàng được đưa vào trong bài toán khai thác HUIs và được gọi là bài toán khai thác tập CoHUIs (Correlated High Utility Itemset). Năm 2017, Gan và cộng sự đề xuất thuật toán CoHUIM với độ đo kulc và phương pháp chiếu trên cơ sở dữ liệu trong quá trình khai thác [9]. Sau đó nhóm tác giả này cải tiến thuật toán bằng cách sử dụng cấu trúc dữ liệu Utility-List trong quá trình khai thác CoHUIs với thuật toán CoUPM [10]. Năm 2020, nhóm tác giả Vo và cộng sự [11] trình bày hướng tiếp cận cơ sở dữ liệu chiếu với đề xuất cách tính giá trị prefix-utility trên giao dịch chiếu để tính trực tiếp độ hữu ích của tập mục. Ngoài ra, hướng nghiên cứu khai thác tập CoHUIs còn được mở rộng với bài toán lợi nhuận âm [12], khai thác CoHUIs với ràng buộc chiều dài [13], khai thác trên cơ sở dữ liệu tăng trưởng [14], khai thác top-k tập hữu ích cao tương quan [15] và khai thác tập hữu ích trung bình cao có tính tương quan [16, 17]. 2. CÁC PHƯƠNG PHÁP KHAI THÁC TẬP HỮU ÍCH CAO 2.1 Khai thác tập hữu ích cao Khai thác tập hữu ích cao (HUIs) là việc rút trích ra tập các mặt hàng có tổng độ hữu ích cao hơn ngưỡng độ hữu ích tối thiểu (MinUtil) cho trước. Xét cơ sở dữ liệu có 𝑛 giao dịch 𝐷 = {𝑇1 , 𝑇2 , . . . , 𝑇 𝑛 } và tập m mục 𝐼 = {𝑖1 , 𝑖2 , . . . , 𝑖 𝑚 }. Trong đó, mỗi giao dịch có cấu trúc 𝑇𝑗 = {𝑥1 , 𝑥2 , … , 𝑥 𝑡 , | 𝑥 𝑡 ∈ 𝐼}. Mỗi mặt hàng 𝑥 𝑡 ∈ 𝐼 có giá trị lợi nhuận xác định 𝐴(𝑥 𝑡 ) và số lượng mua trong một giao dịch cụ thể 𝐵(𝑥 𝑡 , 𝑇𝑗 ). Độ hữu ích của mặt hàng 𝑥 𝑡 trong giao dịch 𝑇𝑗 ký hiệu là 𝑈(𝑥 𝑡 , 𝑇𝑗 ) = 𝐴(𝑥 𝑡 ) ∗ 𝐵(𝑥 𝑡 , 𝑇𝑗 ). Xét tập mặt hàng X={𝑥1 , 𝑥2 , … , 𝑥 𝑘 } ⊆ 𝑇𝑗 . Độ hữu ích của X trong 𝑇𝑗 ký hiệu là 𝑈(𝑋, 𝑇𝑗 ) = ∑ 𝑥 𝑖∈𝑋 𝑈(𝑥 𝑖 , 𝑇𝑗 ). Độ hữu ích của 𝑋 trong toàn bộ cơ sở dữ liệu 𝐷 ký hiệu là 𝑈(𝑋) = ∑ 𝑇 𝑗∈𝐷 𝑈(𝑋 , 𝑇𝑗 ). Ví dụ: Xét cơ sở dữ liệu giao dịch như trong Bảng 1, với 𝑋 = {𝑎, 𝑏} thì 𝑈(𝑋) = 𝑈(𝑎𝑏) = 𝑈(𝑎𝑏, 𝑇1 ) + 𝑈(𝑎𝑏, 𝑇4 ) + 𝑈(𝑎𝑏, 𝑇8 ) = 15 + 9 + 20 = 44. Bảng 1. Cơ sở dữ liệu giao dịch 𝐷 Độ hữu ích TID Giao dịch giao dịch 1 (a,4) (b,3) (c,4) (e,2) 59 2 (a,1) (d,4) (e,6) 47 3 (c,1) (d,6) (f,4) 48 4 (a,2) (b,3) (c,1) (e,2) 29 5 (c,6) (e,3) 66 6 (c,5) (d,2) (f,7) 93 7 (a,2) (c,1) (d,2) (e,6) (f,4) 82 8 (a,6) (b,2) (c,4) (d,1) (e,6) 90 Bảng 2. Các giá trị lợi nhuận, twu và support Mục a b c d e f Lợi nhuận 3 1 8 2 6 7 TWU 307 178 467 360 373 223 SUP 5 3 7 5 6 3 Định nghĩa 1. Tập mục 𝑋 trong cơ sở dữ liệu 𝐷 là tập hữu ích cao nếu 𝑈(𝑋) >= 𝑚𝑖𝑛𝑈𝑡𝑖𝑙. Trong đó 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 là ngưỡng độ hữu ích tối thiểu. Ví dụ nếu 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 = 200 thì 𝑈(𝑎𝑏) = 44 < 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 nên {𝑎, 𝑏} không là tập hữu ích cao. 116
Định nghĩa 2. Trọng lượng giao dịch (Transaction Weight Utility – 𝑇𝑊𝑈) của tập mục 𝑋 được tính bằng tổng độ hữu ích của các giao dịch chứa 𝑋. Ta có 𝑇𝑊𝑈(𝑋) = ∑ 𝑋⊆𝑇 𝑗∈𝐷 𝑇𝑈( 𝑇𝑗 ). Ví dụ: 𝑇𝑊𝑈(𝑏) = 𝑇𝑈(𝑇1 ) + 𝑇𝑈(𝑇4 ) + 𝑇𝑈(𝑇8 ) = 59 + 29 + 90 = 178 Bảng 3. Cơ sở dữ liệu giao dịch 𝐷 sau khi loại bỏ mục b và sắp xếp tăng theo support (xét 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 = 200) Độ hữu ích TID Giao dịch giao dịch 1 (a,4) (e,2) (c,4) 56 2 (a,1) (d,4) (e,6) 47 3 (f,4) (d,6) (c,1) 48 4 (a,2) (e,2) (c,1) 26 5 (e,3) (c,6) 66 6 (f,7) (d,2) (c,5) 93 7 (f,4) (a,2) (d,2) (e,6) (c,1) 82 8 (a,6) (d,1) (e,6) (c,4) 88 Bảng 4. Các giá trị sau khi loại bỏ mục b và sắp tăng dần theo support Mục f a d e c Lợi nhuận 7 3 2 6 8 TWU 223 307 360 373 467 SUP 3 5 5 6 7 2.2. Khai thác tập hữu ích cao tương quan Khai thác tập hữu ích cao có tương quan là việc sử dụng thêm ràng buộc tương quan giữa các mặt hàng trong tập mục được khai thác. Ràng buộc về tính tương quan sẽ khắc phục được một vấn đề tồn tại trong bài toán khai thác tập hữu ích cao là loại bỏ những tập mặt hàng có mối tương quan giữa các phần tử nhỏ hơn ngưỡng 𝑚𝑖𝑛𝐶𝑜𝑟 cho trước. Ví dụ một mặt hàng A có trị giá lợi nhuận khá lớn và chỉ xuất hiện trong một giao dịch 𝑇𝑗 duy nhất. Khi đó A sẽ là tập hữu ích cao và mọi mặt hàng khác trong giao dịch 𝑇𝑗 kết hợp với mặt hàng A đều là tập hữu ích cao. Những tập này không có ý nghĩa trong phân tích kinh doanh vì mặt hàng A được mua cùng với các mặt hàng khác có một lần trong giao dịch 𝑇𝑗 . Định nghĩa 3. Độ hỗ trợ (support) của tập mục 𝑋 trong cơ sở dữ liệu giao dịch 𝐷 là số lần xuất hiện của 𝑋 trong 𝐷. Ký hiệu 𝑆𝑈𝑃(𝑋). Giá trị độ hỗ trợ của từng mục được trình bày như trong Bảng 2. Ví dụ: Xét cơ sở dữ liệu trong Bảng 1, mục b xuất hiện trong 3 giao dịch 𝑇1 , 𝑇4 , 𝑇8 nên 𝑆𝑈𝑃(𝑏) = 3. Định nghĩa 4. Tập mục 𝑋 trong cơ sở dữ liệu 𝐷 được gọi là tập hữu ích cao có tương quan nếu 𝑈(𝑋) > 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 và 𝐾𝑢𝑙𝑐(𝑋) > 𝑚𝑖𝑛𝐶𝑜𝑟. Trong đó 𝑚𝑖𝑛𝐶𝑜𝑟 là ngưỡng độ tương quan tối thiểu và 𝐾𝑢𝑙𝑐(𝑋) là giá trị tương quan giữa các phần tử trong tập 𝑋. 1 𝑆𝑢𝑝(𝑋) 𝑘𝑢𝑙𝑐(𝑋) = (∑ 𝑥 𝑖∈𝑋 ). Với 0 𝑘𝑢𝑙𝑐(𝑋) 1 và 𝑋 = {𝑥1 , 𝑥2 , … , 𝑥 𝑘 } [9] 𝑘 sup(𝑥 𝑖 ) Ví dụ: Với cơ sở dữ liệu D ở Bảng 3, ta có 𝑈(𝑎𝑑) = 𝑈(𝑎𝑑, 𝑇2 ) + 𝑈(𝑎𝑑, 𝑇7 ) + 1 3 3 𝑈(𝑎𝑑, 𝑇8 ) =41. kulc(ad)= 2 (5 + 5) = 0.3 Tính chất: Cả 2 giá trị 𝑇𝑊𝑈 và 𝐾𝑢𝑙𝑐 đều thoả tính chất anti-monotonicity nghĩa là nếu 𝑋 𝑌 thì 𝑇𝑊𝑈(𝑋) ≥ 𝑇𝑊𝑈(𝑌) [3] và 𝐾𝑢𝑙𝑐(𝑋) ≥ 𝐾𝑢𝑙𝑐(𝑌) [9]. Đây là tính chất quan trọng 117
Nguyễn Văn Lễ góp phần giảm không gian tìm kiếm trong quá trình khai thác tập hữu ích cao có tương quan (CoHUIs). Định nghĩa 5. Thứ tự các mục trong cơ sở dữ liệu 𝐷 được sắp xếp lại theo trật tự tăng dần của độ hỗ trợ gọi là thứ tự toàn phần. Bảng 2 trình bày giá trị độ hỗ trợ (SUP) của từng mục chưa sắp xếp. Bảng 4 trình bày thứ tự các mục đã sắp xếp tăng theo độ hỗ trợ. Ví dụ: thứ tự toàn phần của các mục trong cở sở dữ liệu 𝐷 ở Bảng 4 là 𝑓, 𝑎, 𝑑, 𝑒, 𝑐 2.3. Một số vấn đề còn tồn tại Trong bài toán khai thác tập hữu ích cao và tập hữu ích cao có tương quan, vấn đề đặt ra là việc xác định ngưỡng 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 như thế nào cho hợp lý là điều không dễ dàng. Giá trị của ngưỡng này bao nhiêu là tuỳ thuộc vào mong muốn của từng doanh nghiệp kinh doanh và cũng phụ thuộc vào quyết định của người quản lý mà chưa có cơ sở khoa học cho việc chọn ngưỡng một cách hợp lý. Do đó, đa số các thuật toán khai thác 𝐻𝑈𝐼𝑠 và 𝐶𝑜𝐻𝑈𝐼𝑠 không đưa ra lý giải rõ ràng về việc chọn ngưỡng và cũng ko chứng minh ngưỡng nào là phù hợp với từng cơ sở dữ liệu cụ thể. Trong khi đó, một số thuật toán tính ngưỡng 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 theo phần trăm của kích thước toàn bộ cơ sở dữ liệu. Điều này có thể hợp lý, tuy nhiên trường hợp cơ sở dữ liệu có một số mặt hàng có lợi nhuận cao hơn nhiều so với đa số các mặt hàng khác trong cơ sở dữ liệu thì giá trị 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 có được sẽ bị lệch ra khỏi vùng giá trị chung của các mặt hàng. Khi đó kết quả khai thác có thể gồm những tập xoay quanh các mặt hàng có giá trị cao, và tập kết quả sẽ kém ý nghĩa cho việc phân tích trong kinh doanh. Vấn đề thứ hai là cơ sở dữ liệu sử dụng để khai thác là cố định, không được cập nhật thời gian thực nên mỗi khi có sự biến động trong cơ sở dữ liệu, nếu muốn sử dụng tập dữ liệu mới nhất thì phải thực thi lại thuật toán. Vấn đề này cũng đã có nhiều nghiên cứu và đề xuất khai thác 𝐻𝑈𝐼𝑠 và 𝐶𝑜𝐻𝑈𝐼𝑠 trên cơ sở dữ liệu tăng trưởng (Incremental database) để tận dụng được kết quả đã khai thác trước đó, tuy nhiên việc tận dụng kết quả đã khai thác vẫn chưa có hiệu quả cao. Vì khi thêm một số giao dịch mới vào cơ sở dữ liệu thì tất cả các giá trị liên quan đến những mặt hàng trong giao dịch mới này cũng sẽ bị thay đổi. Chẳng hạn như 𝑇𝑊𝑈, 𝑇𝑈, 𝑈. Do đó tất cả các giá trị này cần phải tính toán lại. Vấn đề thứ ba là việc khai thác tập hữu ích cao và tập hữu ích cao có tương quan dựa trên giả định rằng lợi nhuận của mỗi mặt hàng là một giá trị cố định như Bảng 2. Tuy nhiên trên thực tế thì lợi nhuận của một mặt hàng có thể biến động tuỳ vào thời điểm. Ví dụ một số mặt hàng có lượng mua ít trong thời gian dài, khi đó cửa hàng có thể giảm giá để kích cầu người mua. Điều này đồng nghĩa với việc cửa hàng chấp nhận mức lợi nhuận thấp hơn. Theo đó, giá trị lợi nhuận của cùng mặt hàng sẽ khác nhau theo thời gian. Chính vì vậy việc áp dụng phương pháp khai thác 𝐻𝑈𝐼𝑠 và 𝐶𝑜𝐻𝑈𝐼𝑠 hiện tại với mức lợi nhuận cố định vào dữ liệu thực tế là chưa phù hợp. 3. CÁC THUẬT TOÁN KHAI THÁC TÂP HỮU ÍCH CAO TƯƠNG QUAN Các thuật toán khai thác tập hữu ích cao có tương quan dựa trên độ đo Kulc có kết quả đầu vào và đầu ra là giống nhau như CoHUIM [9], CoUPM [10], CoHUI-Miner [11]. Các thuật toán này khác nhau chủ yếu về cấu trúc dữ liệu và các chiến lược tỉa được áp dụng. Trong đó, thuật toán CoHUIM và CoHUI-Miner sử dụng cấu trúc dữ liệu dựa trên phương pháp chiếu trên cơ sở dữ liệu (Projected database) còn thuật toán CoUPM sử dụng cấu trúc dữ liệu Utility- List. Bên cạnh đó, một số thuật toán bổ sung thêm ràng buộc vào bài toán khai thác CoHUIs như thuật toán CHN [12], CHL [13] cũng dựa trên cấu trúc dữ liệu Utility-List nhưng cách tổ chức dữ liệu khác nhau. Bảng 7: So sánh cấu trúc dữ liệu và chiến lược tỉa các thuật toán STT Thuật toán Cấu trúc dữ liệu Chiến lược tỉa 118
1 CoHUIM Projected database TWU, Kulc 2 CoUPM Utility-List TWU, Kulc, U, LA 3 CoHUI-Miner Projected database TWU, Kulc, U, LA 4 CHN Utility-List TWU, Kulc, U, EUCS, LA TWU, Kulc, U, EUCS, LA, 5 CHL Utility-List Length constraints 3.1. Các chiến lược tỉa Chiến lược tỉa dựa vào TWU: Nếu 𝑇𝑊𝑈(𝑋) < 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 thì 𝑋 và mọi tập mở rộng từ 𝑋 sẽ bị loại bỏ khỏi không gian tìm kiếm vì những tập này đều không là CoHUI. Với tính chất Downward-closuare của TWU, ta có nếu 𝑋  𝑌 thì 𝑇𝑊𝑈(𝑋) >= 𝑇𝑊𝑈(𝑌). Do đó nếu 𝑇𝑊𝑈(𝑋) < 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 thì 𝑇𝑊𝑈(𝑌) < 𝑚𝑖𝑛𝑈𝑡𝑖𝑙. Ví dụ: Với cơ sở dữ liệu 𝐷 trong Bảng 1, nếu 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 = 200 thì mục 𝑏 bị tỉa khỏi không gian tìm kiếm vì 𝑇𝑊𝑈(𝑏) = 178 < 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 = 200. Chiến lược tỉa dựa vào độ hữu ích U: Nếu tổng độ hữu ích của tập mục 𝑋 và tổng độ hữu ích của các mục sau 𝑋 nhỏ hơn 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 thì mọi tập mở rộng từ 𝑋 đều không phải là 𝐶𝑜𝐻𝑈𝐼. Nghĩa là nếu 𝑈(𝑋) + 𝑅𝑈(𝑋) < 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 thì  𝑌  𝑋, 𝑌 𝐶𝑜𝐻𝑈𝐼. Ví dụ: xét tập mục {𝑎, 𝑑}, 𝑈(𝑎𝑑) + 𝑅𝑈 (𝑎𝑑) = 41 + 148 = 189 < 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 = 200 nên tập mục {𝑎, 𝑑} cũng như mọi tập mở rộng từ {𝑎, 𝑑} bị loại bỏ khỏi không gian tìm kiếm. Chiến lược tỉa LA: Xét 2 tập 𝑋, 𝑌, nếu 𝑈(𝑋) + 𝑅𝑈(𝑋) − ∑ 𝑋⊆𝑇 𝑗∈ 𝐷 𝑌 𝑇 𝑗 𝑈(𝑋 , 𝑇𝑗 ) + 𝑅𝑈(𝑋, 𝑇𝑗 ) < 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 thì tập mục 𝑋𝑌 không phải là 𝐶𝑜𝐻𝑈𝐼 và mọi tập mở rộng từ 𝑋𝑌 cũng không phải là 𝐶𝑜𝐻𝑈𝐼. Chiến lược tỉa này được sử dụng trong quá trình kết hợp hai 𝑈𝑡𝑖𝑙𝑖𝑡𝑦 𝐿𝑖𝑠𝑡 lại với nhau với giả định rằng giá trị ban đầu là 𝑈(𝑋) + 𝑅𝑈(𝑋). Giá trị này sẽ giảm dần trong quá trình xét từng giao dịch khi mục 𝑌 không thuộc giao dịch. Chiến lược tỉa EUCS: Xét các tập mục một phần tử 𝑋, 𝑌, nếu 𝑇𝑊𝑈(𝑋, 𝑌) < 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 thì tập mục 𝑋𝑌 không phải là 𝐶𝑜𝐻𝑈𝐼 và mọi tập mở rộng từ 𝑋𝑌 cũng không phải là 𝐶𝑜𝐻𝑈𝐼 [4]. Khi đó loại bỏ tập 𝑋𝑌 khỏi không gian tìm kiếm. Xét cơ sở dữ liệu ở Bảng 4, cấu trúc EUCS được khởi tạo gồm các giá trị là một ma trận tam giác trên với 𝐸𝑈𝐶𝑆(𝑋, 𝑌) = 𝑇𝑊𝑈(𝑋𝑌). Vi dụ: 𝐸𝑈𝐶𝑆(𝑓, 𝑎) = 82, < 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 = 200 nên tập {𝑓, 𝑒} không phải là 𝐶𝑜𝐻𝑈𝐼 nên loại tập {𝑓, 𝑒} ra khỏi không gian tìm kiếm và dừng mở rộng với tập {𝑓, 𝑒}. Bảng 5. Cấu trúc EUCS f a d e c f 0 82 223 82 223 a 0 0 217 299 252 d 0 0 0 217 311 e 0 0 0 0 318 c 0 0 0 0 0 Chiến lược tiả kulc: Nếu 𝑘𝑢𝑙𝑐(𝑋) < 𝑚𝑖𝑛𝐶𝑜𝑟 thì mọi tập mở rộng từ 𝑋 không phải lài một 𝐶𝑜𝐻𝑈𝐼. Theo tính chất tương quan [9] thì 𝑘𝑢𝑙𝑐(𝑋𝑦) < 𝑘𝑢𝑙𝑐(𝑋) < 𝑚𝑖𝑛𝐶𝑜𝑟. Trong đó 𝑦 là phần mở rộng từ 𝑋. Khi đó mọi tập mở rộng từ 𝑋 không phải là 𝐶𝑜𝐻𝑈𝐼. 3.2. Cấu trúc dữ liệu 3.2.1. Phép chiếu cơ sở dữ liệu 119
Nguyễn Văn Lễ Phép chiếu trên cơ sở dữ liệu được sử dụng trong thuật toán CoHUIM [9] và CoHUI- Miner [11]. Ngoài các chiến lược tỉa thì phép chiếu cũng giúp giảm không gian tìm kiếm. Cơ sở dữ liệu chiếu trong các bước sau sẽ nhỏ dần giúp cho việc khai thác tập CoHUI nhanh hơn. Định nghĩa 6. Mục 𝑥i được gọi là sau tập mục 𝑋 trong giao dịch 𝑇𝑗 nếu 𝑥i sau tất cả các phần tử trong tập mục 𝑋. Ký hiệu 𝑋 ≺ 𝑥 𝑖 . Trong đó, thứ tự trước sau dựa trên thứ tự toàn phần được trình bày trong Định nghĩa 5. Ví dụ: Xét giao dịch 𝑇7 ở Bảng 3, {𝑓, 𝑑} ≺ 𝑒 và {𝑓, 𝑑} ≺ 𝑐 Định nghĩa 7. Phép chiếu giao dịch 𝑇𝑗 trên tập 𝑋 là tập các mục sau 𝑋 trong 𝑇𝑗 . Ký hiệu 𝑇𝑗 \𝑋 = {𝑥 𝑖 ∈ 𝑇|𝑋 ≺ 𝑥 𝑖 }. Phép chiếu cơ sở dữ liệu 𝐷 trên tập 𝑋 là tập hợp các phép chiếu 𝑇𝑗 trên 𝑋. Ký hiệu 𝐷\𝑋 = {𝑇𝑗 \𝑋 | 𝑇𝑗 ∈ D}. Ví dụ: Xét cơ sở dữ liệu 𝐷 trong Bảng 3, với 𝑋 = {𝑓, 𝑑}, 𝑇3 \𝑋 = {𝑐}, 𝑇6 \𝑋 = {𝑐}, 𝑇7 \𝑋 = {𝑒, 𝑐}. Bảng 6. Cơ sở dữ liệu chiếu trên {𝑓, 𝑑} TID Giao dịch 1 c 2 c 3 e, c 3.2.2. Utility-List Cấu trúc Utility-List được Liu và cộng sự [3] đề xuất để khai thác tập hữu ích cao HUI trên cơ sở dữ liệu giao dịch. Cấu trúc này được cải tiến để sử dụng cho các bài toán khai thác tập hữu ích cao có tương quan. Các thuật toán sử dụng cấu trúc Utility-List được trình bày trong bài báo này gồm: CoUPM [10], CHN [12], CHL [13]. Quá trình khai thác được thực hiện qua hai bước. Bước 1 đọc cơ sở dữ liệu giao dịch từ tập tin văn bản vào bộ nhớ, thực hiện loại bỏ những mục 𝑥 𝑖 có 𝑇𝑊𝑈(𝑥 𝑖 ) < 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 và sắp xếp lại cơ sở dữ liệu tăng dần theo thứ tự toàn phần. Sau đó chuyển cơ sở dữ liệu thành cấu trúc Utility-List một phần tử. Bước 2 dựa vào tập Utility-List một phần tử thực hiện mở rộng vùng tìm kiếm bằng cách kết hợp các Utility-List một phần tử thành các Utility-List 𝑘 phần tử theo phương pháp tìm kiếm theo chiều sâu (Depth-first-search). Trong quá trình kết hợp có sử dụng các chiến lược tỉa (Mục 3.1) để cắt giảm không gian tìm kiếm. Hình 1. Các bước khai thác CoHUI với cấu trúc Utility-List Hình 2. Utility-List một phần tử sử dụng trong thuật toán CoUPM và thuật toán CHL với minCor=0.6, minLength=1, maxLength=4 120
Trong thuật toán CHL, khi thay đổi giá trị 𝑚𝑖𝑛𝐿𝑒𝑛𝑔𝑡ℎ và 𝑚𝑎𝑥𝐿𝑒𝑛𝑔𝑡ℎ thì dữ liệu của các Utility-List sẽ bị thay đổi theo. Hai giá trị ngưỡng này giúp giới hạn số phần tử có trong tập kết quả CoHUI và do người dùng chọn trước khi thực hiện thuật toán. Hình 3. Utility-List một phần tử sử dụng trong thuật toán CHN Thuật toán CHN khai thác tập CoHUI trên cơ sở dữ liệu giao dịch có lợi nhuận âm nên giá trị Utility trong cấu trúc Utility-List được tách thành hai phần: PU (Positive Utility) chứa độ hữu ích dương và NU (Negative Utility) chứa độ hữu ích âm. Trong cơ sở dữ liệu ví dụ ở Bảng 3 và Bảng 4, độ hữu ích của các mục đều có giá trị dương nên giá trị NU bằng 0 trên các Utility-List. Trường hợp có độ hữu ích âm thì giá trị NU sẽ được biểu diễn bằng các số âm. 4. KẾT LUẬN Bài báo này đã trình bày khảo sát tổng quan về các phương pháp khai thác tập hữu ích cao và tập hữu ích cao có tương quan trên cơ sở dữ liệu giao dịch trong thời gian gần đây. Bên cạnh đó, tác giả đã trình bày một số vấn đề còn tồn tại trong bài toán từ đó gợi mở ra các vấn đề cần nghiên cứu tiếp theo. Với bài toán khai thác tập hữu ích cao có tương quan, tác giả đã trình bày cấu trúc dữ liệu mà các thuật toán đã sử dụng chủ yếu gồm hai dạng là phương pháp chiếu trên cơ sở dữ liệu và cấu trúc Utility-List. Mỗi thuật toán khi sử dụng cấu trúc dữ liệu thường có sự cải tiến để phù hợp với bài toán đặt ra. Cuối cùng là các chiến lược tỉa áp dụng trên các thuật toán được khảo sát là có sự tương đồng, trong đó các chiến lược tỉa dựa trên cấu trúc 𝑇𝑊𝑈, 𝐾𝑢𝑙𝑐, 𝑈, 𝐿𝐴 được sử dụng nhiều nhất trong bài toán khai thác tập hữu ích cao có tương quan. TÀI LIỆU THAM KHẢO 1. Y. Liu, W. K. Liao and A. Choudhary, "A two-phase algorithm for fast discovery of high utility itemsets," In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 689-695, 2005. 2. V. S. Tseng, C. W. Wu, B. E. Shie and P. S. Yu, "UP-Growth: an efficient algorithm for high utility itemset mining," In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 253-262, 2010. 3. M. Liu and J. Qu, "Mining high utility itemsets without candidate generation," In Proceedings of the 21st ACM International Conference on Information and Knowledge Management, pp. 55-64, 2012. 121
Nguyễn Văn Lễ 4. P. Fournier-Viger, C. W. Wu, S. Zida and V. S. Tseng, "FHM: Faster high-utility itemset mining using estimated utility co-occurrence pruning," International Symposium on Methodologies for Intelligent Systems, vol. 8502, pp. 83-92, 2014. 5. P. Fournier-Viger, J. C. W. Lin, Q. H. Duong and T. L. Dam, "FHM+: Faster High- Utility Itemset Mining Using Length Upper-Bound Reduction," in Engineering and Other Applications of Applied Intelligent Systems, 2016. 6. J. C. W. Lin, P. Fournier-Viger and W. Gan, "FHN: An efficient algorithm for mining high-utility itemsets with negative unit profits," Knowledge-Based Systems, vol. 111, pp. 283-298, 2016. 7. S. Zida, P. Fournier-Viger, J. C. W. Lin, C. W. Wu and V. S. Tseng, "EFIM: a fast and memory efficient algorithm for high-utility itemset mining," Knowledge and Information Systems, vol. 51, no. 2, pp. 595-625, 2017. 8. S. Krishnamoorthy, "HMiner: Efficiently mining high utility itemsets," Expert Systems with Applications, vol. 90, pp. 168-183, 2017. 9. W. Gan, J. C. W. Lin, P. Fournier-Viger, H. C. Chao and H. Fujita, "Extracting non- redundant correlated purchase behaviors by utility measure," Knowledge-Based Systems, vol. 143, pp. 30-41, 2018. 10. W. Gan, J. C. W. Lin, H. C. Chao, H. Fujita and S. Y. Philip, "Correlated utility- based pattern mining," Information Sciences, vol. 504, pp. 470-486, 2019. 11. B. Vo, L. Nguyen, V. Vu, M. Lam, T. Duong, L. Manh and T. Hong, "Mining correlated high utility itemsets in one phase," IEEE Access, vol. 8, pp. 465-477, 2020. 12. V. Nguyen, T. Nguyen and T. Manh, "Mining Correlated High Utility Itemset on transaction database with negative profits," Journal of Science and Technology on Information and Communications, vol. 3, pp. 94-102, 2020. 13. V. Nguyễn, T. Pham, V. Tran and V. Nguyen, "Mining correlated High Utility Itemsets with length constraints," in Fundamental And Applied IT Research, Ho Chi Minh, 2021. 14. V. Nguyen, T. Nguyen and T. Manh, "Mining correlated High Utility Itemsets on Incremental database," in Fundamental And Applied IT Research, Ho Chi Minh, 2021. 15. T. Manh, T. Nguyen and V. Nguyen, "Mining top-k correlated high utility itemsets on transaction database," in Tạp chí khoa học đại học Công Thương TPHCM, Ho Chi Minh, 2023. 16. T. Pham and V. Nguyen, "An effective algorithm for mining high average utility itemsets," Journal of Science and Technology on Information and Communications, vol. 3, pp. 72-82, 2021. 17. K. K. R. D. Sethi, "Correlated high average-utility itemset mining," Computational Intelligence: Frontiers in Intelligent Computing: Theory and Applications, vol. 1, pp. 485-497, 2020. 122
ABSTRACT A SURVEY OF CORRELATED HIGH UTILITY ITEMSET MINING Nguyen Van Le1,* Ho Chi Minh City University of Industry and Trace Email: lenv@huit.edu.vn The problem of high utility itemsets mining has many studies and applications in the fact, especially in the business field. In which, knowledge is discovered based on finding sets of items purchased together that have a total profit higher than a given minimum utility threshold. The mining results will support managers in making the best decisions to increase business profits. However, for some items with unusually high profits, the combination of that item with any other item in the same transaction is also a high utility itemset, leading to irrationality in the results. To address this problem, the correlation measure is proposed in the high utility itemset mining with many proposals from different algorithms. These algorithms have different data structures, how to apply pruning strategy as well as execution performance compared to two factors: running time and memory usage. This article presents an overview of some recent studies on mining correlated high utility itemsets on transactional databases and offers some suggestions for future research. Keywords: High utility itemsets, correlated, transaction database, data mining, strategy. Tôi xin cam kết bài báo này chưa được đăng và gửi đăng ở bất kỳ tạp chí nào khác. Tác giả: Họ và tên: Nguyễn Văn Lễ Số điện thoại liên hệ: 0378890133 123