Khai thác tập hữu ích cao tương quan với ràng buộc chiều dài

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

Thêm vào BST

Báo xấu

18
lượt xem 3
download

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

Vấn đề khai thác tập hữu ích cao tương quan (Correlated Hight Utility Itemset - CoHUI) trong cơ sở dữ liệu giao dịch đã có nhiều nghiên cứu được đề xuất nhằm trích xuất tri thức từ hành vi mua hàng của người dùng. Bài viết đề xuất thuật toán CHL (Correlated High Utility Itemset with Length constraint) để khai thác tập hữu ích cao tương quan trên cơ sở dữ liệu giao dịch với ràng buộc chiều dài.

Chủ đề:

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

Lưu

Nội dung Text: Khai thác tập hữu ích cao tương quan với ràng buộc chiều dài

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.0079 KHAI THÁC TẬP HỮU ÍCH CAO TƯƠNG QUAN VỚI RÀNG BUỘC CHIỀU DÀI Nguyễn Văn Lễ1, Trần Văn Thọ1, Phạm Tuấn Khiêm1, Nguyễn Văn Hoàng2 1 Trường Đại học Công nghiệp thực phẩm TP. Hồ Chí Minh 2 Trường Đại học Văn Lang lenv@hufi.edu.vn, thotv@hufi.edu.vn, khiempt@hufi.edu.vn, hoang.nv@vlu.edu.vn TÓM TẮT: Vấn đề khai thác tập hữu ích cao tương quan (Correlated Hight Utility Itemset - CoHUI) trong cơ sở dữ liệu giao dịch đã có nhiều nghiên cứu được đề xuất nhằm trích xuất tri thức từ hành vi mua hàng của người dùng. Tuy nhiên, kết quả khai thác được có nhiều tập với số lượng mặt hàng lớn sẽ gây khó khăn cho việc phân tích và quyết định trong kinh doanh thay vì xem xét trên các tập kết quả với số lượng mặt hàng ít hơn. Do đó ràng buộc chiều dài được bổ sung trong quá trình khai thác, nhưng mới chỉ dừng lại trong việc khai thác tập hữu ích cao mà chưa xem xét cho việc khai thác tập hữu ích cao có tương quan. Trong bài báo này, chúng tôi đề xuất thuật toán CHL (Correlated High Utility Itemset with Length constraint) để khai thác tập hữu ích cao tương quan trên cơ sở dữ liệu giao dịch với ràng buộc chiều dài. Kết quả thử nghiệm trên các cơ sở dữ liệu Chess, Mushroom, Accident, Kosarak, Retail, Chainstore cho thấy thuật toán CHL có hiệu suất thực thi hiệu quả hơn so với thuật toán so sánh CoUPM về thời gian thực thi và bộ nhớ sử dụng, đặc biệt là các cơ sở dữ liệu thưa. Từ khóa: Tập hữu ích cao, tính tương quan, ràng buộc chiều dài, tập hữu ích cao có tương quan, khai thác dữ liệu. I. GIỚI THIỆU Khai thác các tập hữu ích cao (High Utility Itemsets - HUI) trên cơ sở dữ liệu giao dịch là bài toán phổ biến và có nhiều ứng dụng trong thực tế. Các thuật toán khai thác tập hữu ích cao đề cập đến việc khám phá các tập mặt hàng có độ hữu ích cao so với ngưỡng độ hữu ích cho trước. Một số thuật toán điển hình về khai thác tập hữu ích cao như: UP-Grown [1], Two-Phase [2], HUI-Miner [3], FHM [4], EFIM [5], HMiner [6]. Năm 2016, Fournier-Viger và cộng sự [7] đề xuất thuật toán FHM+ bổ sung thêm ràng buộc chiều dài để tối ưu tập kết quả. Một hạn chế quan trọng của các thuật toán khai thác tập hữu ích cao là chỉ sử dụng độ đo lợi nhuận để đánh giá mức độ hữu ích của các tập mặt hàng. Điều này dẫn đến kết quả khai thác có nhiều tập mặt hàng mang lại lợi nhuận cao nhưng giữa các mặt hàng trong tập lại có mối tương quan yếu. Những tập mặt hàng này kém ý nghĩa trong vấn đề phân tích kinh doanh. Từ đó, bài toán mới đặt ra là cần tìm ra các tập mặt hàng vừa có độ hữu ích cao và vừa có tính tương quan giữa các phần tử trong tập. Có nhiều nghiên cứu được đề xuất để giải quyết vấn đề này như thuật toán FCHM được đề xuất bởi Fournier-Viger và cộng sự [8]. Cùng giải quyết vấn đề này, J. C. W. Lin và cộng sự đã đề xuất thuật toán FDHUP [9] để khai thác HUI có ràng buộc tần suất cao. Sau đó, vào năm 2017, W. Gan và cộng sự đề xuất thuật toán CoHUIM [10] xem xét cả tính tương quan và lợi nhuận giữa các mặt hàng trong giao dịch. Tuy nhiên, thuật toán này sinh ra số lượng lớn các ứng viên và việc quét lại cơ sở dữ liệu gốc nhiều lần làm tăng đáng kể thời gian thực thi và bộ nhớ sử dụng. Tiếp sau đó, vào năm 2019, W. Gan và cộng sự đề xuất thuật toán CoUPM [11] có hiệu suất thực thi tốt hơn thuật toán CoHUIM. Trong bài báo này, chúng tôi đề xuất thuật toán CHL để khai thác tập hữu ích cao tương quan với ràng buộc chiều dài của tập mục. Việc bổ sung thêm ngưỡng chiều dài tập mục vào khai thác giúp cho thuật toán CHL đạt hiệu quả cao. Những đóng góp chính của bài báo: 1) Đề xuất thuật toán CHL sử dụng ràng buộc chiều dài tập mục trong việc khai thác tập hữu ích cao tương quan trên cơ sở dữ liệu giao dịch. 2) Áp dụng các chiến lược tỉa hiệu quả như U-Prune, LA-Prune, EUCS-Prune và Kulc-Prune làm tăng hiệu suất thực thi của thuật toán. 3) Thực nghiệm trên các nhóm cơ sở dữ liệu dày và thưa cho thấy thuật toán CHL có hiệu suất thực thi cao hơn thuật toán CoUPM ở thời gian thực thi và bộ nhớ sử dụng. Cấu trúc bài báo được chia làm 6 phần: Phần I trình bày giới thiệu; Phần II trình bày các công trình liên quan; Phần III trình bày các định nghĩa và ký hiệu; Phần IV trình bày thuật toán đề xuất CHL; Phần V trình bày kết quả thực nghiệm và đánh giá; Phần VI trình bày kết luận và hướng phát triển. II. CÁC CÔNG TRÌNH LIÊN QUAN Gần đây, bài toán khai thác tập hữu ích cao (High Utility Itemset - HUI) đã được nghiên cứu và ứng dụng rộng rãi, đặc biệt là trong lĩnh vực kinh doanh. Vào năm 2005, Liu và cộng sự đề xuất thuật toán Two-phase [2] nhằm khai thác tập hữu ích cao trên cơ sở dữ liệu giao dịch. Thuật toán thực hiện trên 2 pha, pha đầu tìm kiếm các ứng viên tiềm năng, pha 2 thực hiện quét lại cơ sở dữ liệu nhiều lần để xác định ứng viên nào thực sự là tập hữu ích cao. Dựa trên cách tiếp cận này, một số thuật toán khác được đề xuất để nâng cao hiệu quả khai thác HUI như: CTU-Mine [12], UP- Grown [1],UP-Grown+ [13]. Phương pháp 2 pha tuy giải quyết được bài toán khai thác tập hữu ích cao nhưng tỏ ra kém hiệu quả khi thực hiện trên 2 giai đoạn độc lập dẫn đến tốn nhiều thời gian và bộ nhớ. Để giải quyết vấn đề này,
374 KHAI THÁC TẬP HỮU ÍCH CAO TƯƠNG QUAN VỚI RÀNG BUỘC CHIỀU DÀI năm 2012, Liu và cộng sự đề xuất cấu trúc dữ liệu mới là danh sách Utility-List với thuật toán HUI-Miner [3]. Thuật toán được thiết kế để thực hiện trên 1 pha thực thi nên đã tăng hiệu suất thực thi đáng kể so với cách tiếp cận trước đó. Năm 2014, Fournier và cộng sự đề xuất chiến lược tỉa EUCP [4] kết hợp với cấu trúc dữ liệu Utility-List đã cắt giảm đáng kể không gian tìm kiếm và nâng cao hiệu suất thực thi, đặc biệt trên các cơ sở dữ liệu thưa. Năm 2017, Zida và cộng sự [5] sử dụng cơ chế chiếu và gộp trên cơ sở dữ liệu với đề xuất thuật toán EFIM để làm giảm kích thước cơ sở dữ liệu trong quá trình khai thác. Năm 2018, Krishnamoorthy [6] đề xuất cấu trúc dữ liệu CUL với thuật toán HMiner và nhiều chiến lược tỉa hiệu quả đã cho kết quả khai thác vượt trội so với các thuật toán trước đó. Tuy nhiên, trong kết quả khai thác tập hữu ích cao có chứa nhiều tập có số lượng lớn các phần tử nhưng chỉ một vài phần tử có ý nghĩa nên dẫn đến khó khăn trong quá trình phân tích đánh giá. Để giải quyết vấn đề này, Philippe Fournier-Viger đề xuất thuật toán FHM+ [7] được cải tiến từ thuật toán FHM bằng cách bổ sung ràng buộc chiều dài tập mục trong quá trình khai thác đã loại bỏ được những tập hữu ích cao kém ý nghĩa trong thực tế. Năm 2019, Singh và cộng sự [14] sử dụng kỹ thuật gộp và chiếu kết hợp với ràng buộc chiều dài để khai thác HUI trên cơ sở dữ liệu giao dịch. Một vấn đề khác của tập hữu ích cao là tính tương quan giữa các phần tử trong tập mục chưa được đề cập. Do đó kết quả khai thác tập hữu ích cao của các thuật toán trình bày ở trên vẫn chưa được tối ưu vì còn chứa nhiều tập mục có độ hữu ích cao nhưng tính tương quan giữa các phần tử lại rất thấp. Những tập mục có tính tương quan thấp là không có ý nghĩa về độ phổ biến trong phân tích kinh doanh. Năm 2018, Fournier-Viger và cộng sự [8] đề xuất thuật toán FCHM khai thác tập CHIs với 3 độ đo là any-confidence, all-confidence và bond để đánh giá độ tương quan giữa các phần tử trong tập mục. Bên cạnh đó, Lin và cộng sự đề xuất độ đo Kulc cùng với thuật toán CoHUIM [10] để khai thác tập hữu ích cao có tương quan CoHUI. Năm 2019, Gan và cộng sự [11] sử dụng cấu trúc dữ liệu Utility-List để nâng cao hiệu suất khai thác CoHUI và đề xuất thuật toán CoUPM, kết quả thực nghiệm so sánh với thuật toán CoHUIM cho thấy thuật toán CoUPM có hiệu suất thực thi tốt hơn cả về thời gian thực thi và bộ nhớ sử dụng. III. CÁC ĐỊNH NGHĨA VÀ KÝ HIỆU Cho cơ sở dữ liệu giao dịch 𝐷 = {𝑇1 , 𝑇2 , . . . , 𝑇𝑛 } và tập mục 𝐼 = {𝑖1 , 𝑖2 , . . . , 𝑖𝑚 } gồm m mục phân biệt. ∀ 𝑇𝑗 ∈ 𝐷, 𝑇𝑗 = {𝑥𝑙 |𝑙 = 1, 2, … , 𝑁𝑗 , 𝑥𝑙 ∈ 𝐼}, với 𝑁𝑗 là số các mục trong giao dịch 𝑇𝑗 . Mỗi mục 𝑖 ∈ 𝐼 có một giá trị lợi nhuận xác định là 𝑃(𝑥𝑖 ) và có một số lượng mua 𝑄�𝑥𝑖 , 𝑇𝑗 �. Ví dụ về cơ sở dữ liệu giao dịch sử dụng trong bài báo này trình bày ở Bảng 1 và Bảng 2. Bảng 1. Cơ sở dữ liệu giao dịch TID Giao dịch (𝑻) Số lượng (𝑸) 𝑇1 𝑎, 𝑏, 𝑐, 𝑑 3, 1, 4, 2 𝑇2 𝑎, 𝑏, 𝑐 3, 3, 2 𝑇3 𝑎, 𝑐, 𝑑, 𝑒, 𝑓 4, 1, 2, 2, 1 𝑇4 𝑏, 𝑐, 𝑒 2, 5, 4 𝑇5 𝑏, 𝑐, 𝑑, 𝑒 6, 5, 4, 6 𝑇6 𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓 2, 5, 1, 3, 1, 1 𝑇7 𝑎, 𝑐, 𝑒, 𝑔 2, 6, 2, 5 𝑇8 𝑎, 𝑏, 𝑒, 𝑔 2, 3, 3, 2 Bảng 2. Lợi nhuận của các mục Các mục (Items) a b c d e f g Lợi nhuận (P) 3 2 4 2 3 7 1 Độ hữu ích của mục 𝑥𝑖 trong giao dịch 𝑇𝑗 ký hiệu là 𝑈(𝑥𝑖 , 𝑇𝑗 ) với 𝑈�𝑥𝑖 , 𝑇𝑗 � = 𝑃(𝑥𝑖 ) ∗ 𝑄(𝑥𝑖 , 𝑇𝑗 ). Độ hữu ích của một tập mục 𝑋 = {𝑥1 , 𝑥2 , … , 𝑥𝑘 } ⊆ 𝑇𝑗 định nghĩa là 𝑈�𝑋, 𝑇𝑗 � = ∑𝑥𝑖 ∈𝑋 𝑈(𝑥𝑖 , 𝑇𝑗 ). Tập mục X được gọi là tập hữu ích cao nếu độ hữu ích của nó không nhỏ hơn ngưỡng độ hữu ích nhỏ nhất (minUtil) được cho bởi người dùng. Ví dụ, độ hữu ích của mục d trong giao dịch T3 là 𝑈(𝑑, 𝑇3 ) = 2 ∗ 2 = 4. Độ hữu ích của tập mục {d,e} trong 𝑇3 là U({d,e},𝑇3 ) = U(d, 𝑇3 ) + U(e, 𝑇3 ) = 2*2 + 2*3 = 10. Độ hữu ích của tập mục {d,e} là U(de)= 𝑈(𝑑𝑒, 𝑇3 ) + 𝑈(𝑑𝑒, 𝑇5 ) + 𝑈(𝑑𝑒, 𝑇6 ) = 10 + 26 + 9 = 45. Độ hỗ trợ của tập mục 𝑋, ký hiệu là 𝑆𝑈𝑃(𝑋), là số lượng giao dịch trong 𝐷 chứa 𝑋. 𝑆𝑈𝑃(𝑋) = |{𝑇|𝑇 ⊆ 𝐷 𝑣à 𝑋 ⊆ 𝑇}|. Ví dụ 𝑆𝑈𝑃(𝑎𝑏) = 4 vì có 4 giao dịch chứa {a, b} là 𝑇1 , 𝑇2 , 𝑇6 và 𝑇8 . Độ hỗ trợ của mỗi mục trong cơ sở dữ liệu 𝐷 thể hiện ở Bảng 3. Xét 2 mục 𝑥 và 𝑦 trong cơ sở dữ liệu 𝐷, nếu 𝑆𝑈𝑃(𝑥) < 𝑆𝑈𝑃(𝑦) thì thứ tự giữa 2 mục ký hiệu là 𝑥 ≺ y. Trường hợp 𝑆𝑈𝑃(𝑥) = 𝑆𝑈𝑃(𝑦) thì thứ tự dựa vào thứ tự Alphabet của 𝑥 và 𝑦. Thứ tự toàn phần của các mục trong 𝐷 được sắp xếp tăng dần theo độ hỗ trợ. Với cơ sở dữ liệu 𝐷 cho trong Bảng 1 và độ hỗ trợ của các mục được tính như Bảng 3, thì thứ tự toàn phần được xác định là f ≺ g ≺ d ≺ a ≺ b ≺ e ≺ c. 1 𝑆𝑈𝑃(𝑋) Định nghĩa 1. Xét tập mục 𝑋 = {𝑥1 , 𝑥2 , … , 𝑥𝑘 } trong cơ sở dữ liệu 𝐷. Giá trị 𝑘𝑢𝑙𝑐(𝑋) = �∑𝑥𝑖 ∈𝑋 �, 𝑘 𝑆𝑈𝑃(𝑥𝑖 ) 𝑣ớ𝑖 0∞ 𝑘𝑢𝑙𝑐(𝑋)∞ 1 [10] được định nghĩa là sự tương quan giữa các phần tử trong tập mục 𝑋. Tính tương quan giữa các mục trong 𝑋 càng cao khi giá trị 𝑘𝑢𝑙𝑐(𝑋) càng gần 1 và tính tương quan giữa các mục trong X càng thấp khi giá trị 𝑘𝑢𝑙𝑐(𝑋) càng gần 0. 1 SUP(𝑎𝑏) SUP(𝑎𝑏) 1 4 4 Ví dụ: 𝑘𝑢𝑙𝑐(𝑎𝑏) = � + � = � + � = 0.667 2 SUP(𝑎) SUP(𝑏) 2 6 6
Nguyễn Văn Lễ, Trần Văn Thọ, Phạm Tuấn Khiêm, Nguyễn Văn Hoàng 375 Xét thứ tự toàn phần 𝑥1 ≺ 𝑥1 ≺ ⋯ ≺ 𝑥𝑘 ≺ 𝑥𝑘+1 của các mục trong cơ sở dữ liệu 𝐷, khi đó, giá trị 𝑘𝑢𝑙𝑐 thỏa tính chất Downward closure là 𝑘𝑢𝑙𝑐(𝑥1 , … , 𝑥𝑘+1 ) ≤ 𝑘𝑢𝑙𝑐(𝑥1 , … , 𝑥𝑘 ). Định nghĩa 2. Gọi 𝑚𝑖𝑛𝑈𝑡𝑖𝑙, 𝑚𝑖𝑛𝐶𝑜𝑟, 𝑚𝑖𝑛𝐿𝑒𝑛𝑔𝑡ℎ, 𝑚𝑎𝑥𝐿𝑒𝑛𝑔𝑡ℎ lần lượt là ngưỡng độ hữu ích nhỏ nhất, giá trị tương quan tối thiểu, chiều dài nhỏ nhất, chiều dài lớn nhất của tập mục được cho bởi người dùng. Tập mục 𝑋 trong cơ sở dữ liệu 𝐷 được định nghĩa là tập hữu ích cao tương quan với ràng buộc chiều dài (ký hiệu là 𝐶𝐻𝑈𝐿) nếu thỏa các điều kiện: 𝑘𝑢𝑙𝑐(𝑋) ≥ 𝑚𝑖𝑛𝐶𝑜𝑟, 𝑈(𝑋) ≥ 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 và |𝑋| ∈ [𝑚𝑖𝑛𝐿𝑒𝑛𝑔𝑡ℎ, 𝑚𝑎𝑥𝐿𝑒𝑛𝑔𝑡ℎ]. 𝐶𝐻𝑈𝐿𝑠 = {𝑋 ⊆ 𝐼 | 𝑈(𝑋) ≥ 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 ∧ 𝑘𝑢𝑙𝑐(𝑋) ≥ 𝑚𝑖𝑛𝐶𝑜𝑟 ∧ |X| ∈ [𝑚𝑖𝑛𝐿𝑒𝑛𝑔𝑡ℎ, 𝑚𝑎𝑥𝐿𝑒𝑛𝑔𝑡ℎ]} Định nghĩa 3. Xét giao dịch 𝑇𝑗 = {𝑖1 , 𝑖2 , . . . , 𝑖𝑘 }, ràng buộc chiều dài 𝑙 = 𝑚𝑎𝑥𝐿𝑒𝑛𝑔𝑡ℎ. 𝑙 giá trị lớn nhất trong tập độ hữu ích �𝑢�𝑖1 , 𝑇𝑗 �, 𝑢�𝑖2 , 𝑇𝑗 �, … , 𝑢�𝑖𝑘 , 𝑇𝑗 �� ký hiệu là 𝐿(𝑇𝑗 ). Độ hữu ích của giao dịch 𝑇𝑗 với ràng buộc chiều dài 𝑙 được định nghĩa là 𝐿𝑇𝑈(𝑇𝑗 ) = ∑ 𝐿(𝑇𝑗 ) [7]. Ví dụ: Xét cơ sở dữ liệu trong Bảng 1, với 𝑚𝑎𝑥𝑙𝑒𝑛𝑔𝑡ℎ = 3, 𝐿(𝑇1 ) = {16, 9, 4}. 𝐿𝑇𝑈(𝑇1 ) = 16 + 9 + 4 = 29. Định nghĩa 4. Xét giao dịch 𝑇𝑗 = {𝑖1 , 𝑖2 , . . . , 𝑖𝑘 }. Trọng số hữu ích giao dịch của tập mục 𝑋 là tổng của tất cả các 𝐿𝑇𝑈 trong các giao dịch chứa 𝑋, ký hiệu 𝐿𝑇𝑊𝑈(𝑋) = ∑ 𝐿𝑇𝑈(𝑇𝑗 ) [7]. Ví dụ: với dữ liệu trong Bảng 1, cho 𝑚𝑎𝑥𝐿𝑒𝑛𝑔𝑡ℎ = 3, 𝐿𝑇𝑊𝑈(𝑎) = 𝐿𝑇𝑈(𝑇1 ) + 𝐿𝑇𝑈(𝑇2 ) + 𝐿𝑇𝑈(𝑇3 ) + 𝐿𝑇𝑈(𝑇6 ) + 𝐿𝑇𝑈(𝑇7 ) + 𝐿𝑇𝑈(𝑇8 ) = 29 + 23 + 25 + 23 + 36 + 21 = 157. Tính chất: Xét tập mục 𝑋, nếu 𝐿𝑇𝑊𝑈(𝑋) < 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 thì tập mục X và mọi tập mở rộng từ X không phải là tập mục hữu ích cao tương quan với ràng buộc chiều dài. Với giá trị 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 = 70, mục 𝑓 𝑣à 𝑔 bị loại bỏ khỏi cơ sở dữ liệu 𝐷 và toàn bộ cơ sở dữ liệu 𝐷 được sắp xếp lại theo thứ tự toàn phần được trình bày trong Bảng 4. Bảng 3. Độ hỗ trợ và LTWU của các mục sắp xếp tăng theo SUP Mục f g d a b e c SUP 2 2 4 6 6 6 7 LTWU 69 64 158 187 207 227 258 Bảng 4. Cơ sở dữ liệu giao dịch sau khi loại bỏ f, g và sắp xếp theo thứ tự toàn phần TID Giao dịch (𝑻) Số lượng (𝑸) Độ hữu ích (𝑼) 𝑇1 𝑑, 𝑎, 𝑏, 𝑐 2, 3, 1, 4 4, 9, 2, 16 𝑇2 𝑎, 𝑏, 𝑐 3, 3, 2 9, 6, 18 𝑇3 𝑑, 𝑎, 𝑒, 𝑐 2, 4, 2, 1 4, 12, 6, 4 𝑇4 𝑏, 𝑒, 𝑐 2, 4, 5 4, 12, 20 𝑇5 𝑑, 𝑏, 𝑒, 𝑐 4, 6, 6, 5 8, 12, 18, 20 𝑇6 𝑑, 𝑎, 𝑏, 𝑒, 𝑐 3, 2, 5, 1,1 6, 6, 10, 3, 4 𝑇7 𝑎, 𝑒, 𝑐 2, 2, 6 6, 6, 24 𝑇8 𝑎, 𝑏, 𝑒 2, 3, 3 6, 6, 9 Định nghĩa 5. Xét tập mục 𝑋∠ 𝑇𝑗 . Gọi 𝑉(𝑇𝑗 , 𝑋) là tập mục sau 𝑋 trong 𝑇𝑗 , 𝑉(𝑇𝑗 , 𝑋) = { 𝑣 ∈ 𝑇𝑗 |∀𝑥 ∈ 𝑋, 𝑥 ≺ 𝑣}. Gọi 𝑚𝑎𝑥𝐸𝑥𝑡𝑒𝑛𝑑(𝑋) = 𝑚𝑎𝑥𝐿𝑒𝑛𝑔𝑡ℎ − |𝑋| là số mục tối đa trong tập 𝑉(𝑇𝑗 , 𝑋) thỏa ràng buộc chiều dài 𝑚𝑎𝑥𝐿𝑒𝑛𝑔𝑡ℎ. Tập độ hữu ích lớn nhất sau tập mục 𝑋, ký hiệu L(𝑇𝑗 ,X), là tập các giá trị lớn nhất trong tập {𝑢(𝑣1 , 𝑇𝑗 ), 𝑢(𝑣2 , 𝑇𝑗 ), … , 𝑢(𝑣𝑘 , 𝑇𝑗 )} với ràng buộc chiều dài 𝑚𝑎𝑥𝐸𝑥𝑡𝑒𝑛𝑑(𝑋) [7]. Ví dụ: với dữ liệu trong Bảng 4, cho 𝑚𝑎𝑥𝐿𝑒𝑛𝑔𝑡ℎ = 3, xét giao dịch 𝑇1 và tập mục {𝑑}. Ta có 𝑚𝑎𝑥𝐸𝑥𝑡𝑒𝑛𝑑(𝑑) = 3 – 1 = 2. 𝐿(𝑇1 , 𝑑) = {16, 9}. Định nghĩa 6. Độ hữu ích còn lại của tập mục 𝑋 trong giao dịch 𝑇𝑗 , ký hiệu 𝑅𝑈(𝑋, 𝑇𝑗 ), là tổng của các phần tử trong L(𝑇𝑗 ,X). Độ hữu ích còn lại của tập mục 𝑋 trong cơ sở dữ liệu 𝐷 được định nghĩa là 𝑅𝑈(𝑋) = ∑ 𝑅𝑈(𝑋, 𝑇𝑗 ). Ta có 𝑅𝑈(𝑋, 𝑇𝑗 ) = ∑ 𝐿(𝑇𝑗 , 𝑋). Ví dụ: 𝑅𝑈({𝑑}, 𝑇1 ) = 𝑆𝑈𝑀�𝐿(𝑇1 , 𝑑)� = 16 + 9 = 25. IV. THUẬT TOÁN CHL A. Cấu trúc dữ liệu UList Danh sách UList được tạo sau khi loại bỏ các mục 𝑥 có 𝐿𝑇𝑊𝑈(𝑥) < 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 khỏi cơ sở dữ liệu đồng thời sắp xếp cơ sở dữ liệu theo thứ tự toàn phần (Bảng 4). Mỗi 𝑈𝐿𝑖𝑠𝑡 𝑋 gồm tập các bộ có cấu trúc: < 𝑇𝑖𝑑, 𝑢, 𝑟𝑢 >. Trong đó, 𝑇𝑖𝑑: dùng để định danh một bộ có trong UList, 𝑢: độ hữu ích của tập mục 𝑋 tại giao dịch 𝑇𝑖𝑑, 𝑟𝑢: độ hữu ích còn lại của tập 𝑋 trong giao dịch 𝑇𝑖𝑑. Dựa vào cơ sở dữ liệu ở Bảng 4, với 𝑚𝑖𝑛𝐿𝑒𝑛𝑔𝑡ℎ = 1 và 𝑚𝑎𝑥𝐿𝑒𝑛𝑔𝑡ℎ = 3 thì danh sách UList một phần tử được trình bày trong Hình 1. Xét UList một phần tử {𝑑} gồm 4 bộ tương ứng với các giao dịch 𝑇1 , 𝑇3 , 𝑇5 , 𝑇6 . Bộ 𝑇1 có độ hữu ích 𝑑. 𝑇1 . 𝑢 = 4, 𝑑. 𝑇1 . 𝑟𝑢 = 𝑆𝑈𝑀(9,16) = 25 vì sau d trong 𝑇1 gồm các mục 𝑎, 𝑏, 𝑐 có các độ hữu ích tương ứng là 9, 2, 16, tuy nhiên vì 𝑚𝑎𝑥𝐿𝑒𝑛𝑔𝑡ℎ = 3 nên 𝑚𝑎𝑥𝐸𝑥𝑡𝑒𝑛𝑑 = 𝑚𝑎𝑥𝐿𝑒𝑛𝑔𝑡ℎ − |𝑑| = 2 nghĩa là giá trị 𝑟𝑢 được tính bằng tổng 2 giá trị độ hữu ích lớn nhất là 9 và 16. Tương tự cho các bộ còn lại. Các UList còn lại cũng được thực hiện tương tự.
376 KHAI THÁC TẬP HỮU ÍCH CAO TƯƠNG QUAN VỚI RÀNG BUỘC CHIỀU DÀI Hình 1. Danh sách UList một phần tử B. Các chiến lược tỉa Các chiến lược tỉa cùng với cấu trúc dữ liệu sử dụng có ảnh hưởng lớn đến hiệu suất thực thi của thuật toán. Trong bài báo này chúng tôi áp dụng các chiến lược tỉa hiệu quả để cắt giảm không gian tìm kiếm gồm U-Prune [3], EUCS-Prune [4], LA-Prune [9] và Kulc-Prune [10]. Chiến lược 1 (U-Prune): Nếu tổng độ hữu ích của tập mục 𝑋 và độ hữu ích của các mục sau 𝑋 với ràng buộc chiều dài 𝑚𝑎𝑥𝐿𝑒𝑛𝑔𝑡ℎ nhỏ hơn 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 thì mọi tập mở rộng từ 𝑋 đều không phải là 𝐶𝐻𝑈𝐿. Nghĩa là nếu 𝑈(𝑋) + 𝑅𝑈(𝑋) < 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 thì %𝑋𝑦 mở rộng từ 𝑋 thì 𝑋𝑦∇ 𝐶𝐻𝑈𝐿 nên ngừng mở rộng với tập mục có tiền tố 𝑋. Chiến lược 2 (EUCS-Prune): Xét 𝑋, 𝑌 là hai tập mục 1 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à 𝐶𝐻𝑈𝐿. Khi đó dừng tổ hợp hai tập mục 𝑋 và 𝑌. Chiến lược 3 (LA-Prune): Xét 2 tập 𝑋 và 𝑌, 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à 𝐶𝐻𝑈𝐿. Khi đó dừng kết hợp hai tập mục 𝑋 và 𝑌. Chiến lược 4 (Kulc-Prune): Xét tập mục 𝑋, Nếu 𝑘𝑢𝑙𝑐(𝑋) < 𝑚𝑖𝑛𝐶𝑜𝑟 thì mọi tập mở rộng từ 𝑋 không phải là một 𝐶𝐻𝑈𝐿. Giả sử rằng 𝑦 là phần tử mở rộng từ tập 𝑋 để có tập 𝑋𝑦, theo tính chất 2, ta có 𝑘𝑢𝑙𝑐(𝑋𝑦) < 𝑘𝑢𝑙𝑐(𝑋) < 𝑚𝑖𝑛𝐶𝑜𝑟. Do đó mọi tập mở rộng từ 𝑋 không phải là 𝐶𝐻𝑈𝐿. C. Thuật toán CHL Ý tưởng: Quét cơ sở dữ liệu giao dịch 𝐷 lần 1 để tạo ra tập 𝐼 ∗ chứa các mục thỏa ngưỡng minUtil cho trước, đồng thời loại bỏ các mục không thỏa ra khỏi 𝐷. Sắp xếp các mục trong 𝐼 ∗ tăng theo giá trị 𝑆𝑈𝑃 và các mục trong 𝐷 theo thứ tự của 𝐼 ∗ . Quét cơ sở dữ liệu 𝐷 lần 2 để tạo danh sách 𝑈𝐿𝑖𝑠𝑡 cho mỗi mục 𝑖 ∉ 𝐼∗ . Duyệt qua danh sách UList 1 phần tử này và kiểm tra nếu thỏa các ngưỡng 𝑚𝑖𝑛𝑈𝑡𝑖𝑙, 𝑚𝑖𝑛𝐶𝑜𝑟, 𝑚𝑖𝑛𝐿𝑒𝑛𝑔𝑡ℎ 𝑣à 𝑚𝑎𝑥𝐿𝑒𝑛𝑔𝑡ℎ thì thêm vào tập CHUIs. Quá trình mở rộng tập mục khai thác bằng cách kết hợp các UList 𝑘 phần tử thành các UList 𝑘 + 1 phần tử cho đến khi kết thúc không gian tìm kiếm. Thuật toán chính (Correlated High utility itemsets with Length constraint - CHL) với dữ liệu đầu vào là cơ sở dữ liệu giao dịch 𝐷, ngưỡng độ hữu ích tối hiểu minUtil, ngưỡng độ tương quan minCor, ngưỡng ràng buộc chiều dài minLength và maxLength. Đầu tiên, tại dòng 1, thuật toán quét cơ sở dữ liệu để tính giá trị 𝑅𝑇𝑈 cho mỗi giao dịch và tính 𝑆𝑈𝑃(𝑖), 𝑅𝑇𝑊𝑈(𝑖), 𝑈(𝑖) cho mỗi mục 𝑖 có trong giao dịch. Nếu 𝑅𝑇𝑊𝑈(𝑖) ∝ 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 thì đưa i vào tập 𝐼 ∗ và loại bỏ các mục 𝑖 ∉ 𝐼 ∗ khỏi cơ sở dữ liệu 𝐷 trình bày ở dòng 2. Dòng 3 sắp xếp các mục trong 𝐼 ∗ tăng theo giá trị 𝑆𝑈𝑃 đồng thời sắp xếp các mục trong cơ sở dữ liệu 𝐷 theo thứ tự của 𝐼 ∗ . Dòng 4 khởi tạo cấu trúc EUCS. Tại dòng 5 quét cơ sở dữ liệu 𝐷 để tạo danh sách 𝑈𝐿𝑖𝑠𝑡 có tên 𝑈𝐿𝑠 cho mỗi phần tử 𝑖 ∉ 𝐼 ∗ . Từ dòng 6 đến dòng 12, kiểm tra các 𝑈𝐿𝑖𝑠𝑡 1 phần tử có phải là tập 𝐶𝐻𝑈𝐿 hay không. Từ dòng 13 đến 15, gọi đệ quy thủ tục Mining để khai thác các tập CHULs từ 2 phần tử trở lên. Thuật toán 1: (Thuật toán chính - CHL) Vào: 𝐷: Cơ sở dữ liệu giao dịch, 𝑚𝑖𝑛𝑈𝑡𝑖𝑙: Ngưỡng độ hữu ích tối thiểu, 𝑚𝑖𝑛𝐶𝑜𝑟: Ngưỡng tương quan tối thiểu, minLength: Chiều dài tối thiểu của tập mục, maxLength: Chiều dài tối đa của tập mục. Ra: Danh sách tập mục độ hữu ích cao tương quan (𝐶𝐻𝑈𝐿𝑠) thỏa ngưỡng ràng buộc chiều dài. 1. Quét cơ sở dữ liệu 𝐷 để tính 𝑅𝑇𝑈 cho mỗi giao dịch và tính 𝑆𝑈𝑃(𝑖), 𝑅𝑇𝑊𝑈(𝑖), 𝑈(𝑖) cho mỗi mục 𝑖 có trong 𝐼. 2. Tính 𝐼∗ = {𝑖∠ 𝐼 | 𝑅𝑇𝑊𝑈(𝑖) ∝ 𝑚𝑖𝑛𝑈𝑡𝑖𝑙} và loại bỏ các mục 𝑖 ∉ 𝐼 ∗ khỏi cơ sở dữ liệu 𝐷. 3. Sắp xếp 𝐼 ∗ tăng theo 𝑆𝑈𝑃, sắp xếp các mục trong 𝐷 theo thứ tự của 𝐼 ∗ . 4. Khởi tạo cấu trúc 𝐸𝑈𝐶𝑆 5. Quét cơ sở dữ liệu 𝐷 để tạo danh sách UList cho mỗi phần tử 𝑖 ∉ 𝐼∗ là 𝑈𝐿𝑠 6. if 𝑚𝑖𝑛𝐿𝑒𝑛𝑔𝑡ℎ ≤ 1 then 7. for 𝑋∠ 𝑈𝐿𝑠 do 8. if 𝑈(𝑋) ∝ 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 then 9. 𝐶𝐻𝑈𝐿𝑠 → 𝑋 10. end if 11. end for 12.end if
Nguyễn Văn Lễ, Trần Văn Thọ, Phạm Tuấn Khiêm, Nguyễn Văn Hoàng 377 13. if 𝑚𝑎𝑥𝐿𝑒𝑛𝑔𝑡ℎ > 1 then 14. 𝑀𝑖𝑛𝑖𝑛𝑔(∪ , 𝑈𝐿𝑠, 𝑚𝑖𝑛𝑈𝑡𝑖𝑙, 𝑚𝑖𝑛𝐶𝑜𝑟, 𝑚𝑖𝑛𝐿𝑒𝑛𝑔𝑡ℎ, 𝑚𝑎𝑥𝐿𝑒𝑛𝑔𝑡ℎ, 𝐸𝑈𝐶𝑆) 15. end if Thuật toán 2 (Mining) thực hiện đệ quy nhằm mở rộng không gian tìm kiếm để xác định một tập mục có phải là 𝐶𝐻𝑈𝐿𝑠 hay không. Dữ liệu đầu vào của thuật toán gồm: một 𝑈𝐿𝑖𝑠𝑡 tiền tố 𝑃, 𝑈𝐿𝑠: danh sách các 𝑈𝐿𝑖𝑠𝑡 có tiền tố là 𝑃, ngưỡng độ hữu ích tối thiểu 𝑚𝑖𝑛𝑈𝑡𝑖𝑙, ngưỡng tương quan tối thiểu 𝑚𝑖𝑛𝐶𝑜𝑟, cấu trúc 𝐸𝑈𝐶𝑆, ngưỡng ràng buộc chiều dài 𝑚𝑖𝑛𝐿𝑒𝑛𝑔𝑡ℎ và 𝑚𝑎𝑥𝐿𝑒𝑛𝑔𝑡ℎ. Dữ liệu đầu ra là các tập mục độ hữu ích cao tương quan thỏa ràng buộc chiều dài. Từ dòng 1 đến dòng 3, duyệt qua các 𝑈𝐿𝑖𝑠𝑡 𝑋 trong danh sách 𝑈𝐿𝑠 và kiểm tra nếu 𝑈(𝑋) + 𝑅𝑈(𝑋)∝ 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 (áp dụng chiến lược tỉa U-Prune) và 𝑘𝑢𝑙𝑐(𝑋)∝ 𝑚𝑖𝑛𝐶𝑜𝑟 (áp dụng chiến lược tỉa Kulc-Prune) thì tập mục 𝑋 được mở rộng, khi đó khởi tạo danh sách 𝑈𝐿𝑖𝑠𝑡 mở rộng 𝑒𝑥𝑈𝐿𝑠. Từ dòng 4 đến dòng 7, duyệt qua các 𝑈𝐿𝑖𝑠𝑡 𝑌 sau 𝑋 trong danh sách 𝑈𝐿𝑠 và kiểm tra nếu 𝐸𝑈𝐶𝑆(𝑋, 𝑌)∝ 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 (áp dụng chiến lược tỉa EUCS) thì gọi Thuật toán 3 là 𝐶𝑜𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑈𝐿(𝑃, 𝑋, 𝑌) để kết hợp hai 𝑈𝐿𝑖𝑠𝑡 𝑋, 𝑌 thành một 𝑈𝐿𝑖𝑠𝑡 𝑃𝑥𝑦, đưa 𝑃𝑥𝑦 vào danh sách mở rộng 𝑒𝑥𝑈𝐿𝑠. Tại dòng 8 và 9, kiểm tra nếu 𝑃𝑥𝑦 thỏa các điều kiện U(𝑃𝑥𝑦)∝ 𝑚𝑖𝑛𝑈𝑡𝑖𝑙, 𝑘𝑢𝑙𝑐(𝑃𝑥𝑦)∝ 𝑚𝑖𝑛𝐶𝑜𝑟 và 𝑚𝑖𝑛𝐿𝑒𝑛𝑔𝑡ℎ ≤ |𝑃𝑥𝑦| ≤ 𝑚𝑎𝑥𝐿𝑒𝑛𝑔𝑡ℎ thì 𝑃𝑥𝑦 là một tập 𝐶𝐻𝑈𝐿. Từ dòng 13 đến dòng 15 kiểm tra điều kiện để gọi đệ quy mở rộng không gian tìm kiếm. Thuật toán 2: (Mining) Vào: 𝑃: UList tiền tố; 𝑈𝐿𝑠: Danh sách các UList có tiền tố là 𝑃, 𝑚𝑖𝑛𝑈𝑡𝑖𝑙: Ngưỡng độ hữu ích tối thiểu, 𝑚𝑖𝑛𝐶𝑜𝑟: Ngưỡng tương quan tối thiểu, minLength: Chiều dài tối thiểu của tập mục, maxLength: Chiều dài tối đa của tập mục, 𝐸𝑈𝐶𝑆: Cấu trúc EUCS Ra: Các tập mục độ hữu ích cao tương quan thỏa ràng buộc chiều dài (𝐶𝐻𝑈𝐿𝑠). 1. for 𝑋∠ 𝑈𝐿𝑠 do 2. if 𝑈(𝑋) + 𝑅𝑈(𝑋)∝ 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 ⇔𝑘𝑢𝑙𝑐(𝑋)∝ 𝑚𝑖𝑛𝐶𝑜𝑟 then 3. 𝑒𝑥𝑈𝐿𝑠 = ∪ //Khởi tạo danh sách UList mở rộng từ X 4. for each 𝑌 after 𝑋 in 𝑈𝐿𝑠 do 5. if 𝐸𝑈𝐶𝑆(𝑋, 𝑌)∝ 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 then //Áp dụng chiến lược tỉa EUCP 6. 𝑃𝑥𝑦 = ConstructUL(𝑃, 𝑋, 𝑌); 7. exULs→Pxy 8. if 𝑈(𝑃𝑥𝑦)∝ 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 ⇔𝑘𝑢𝑙𝑐(𝑃𝑥𝑦)∝ 𝑚𝑖𝑛𝐶𝑜𝑟 ⇔𝑚𝑖𝑛𝐿𝑒𝑛𝑔𝑡ℎ ≤ |𝑃𝑥𝑦| ≤ 𝑚𝑎𝑥𝐿𝑒𝑛𝑔𝑡ℎ then 9. 𝐶𝐻𝑈𝐼𝑠 → 𝑃𝑥𝑦 10. end if 11. end if 12. end for 13. if |𝑃𝑥𝑦| − 1 < 𝑚𝑎𝑥𝐿𝑒𝑛𝑔𝑡ℎ then 14. 𝑀𝑖𝑛𝑖𝑛𝑔(𝑋, 𝑒𝑥𝑈𝐿𝑠, 𝑚𝑖𝑛𝑈𝑡𝑖𝑙, 𝑚𝑖𝑛𝐶𝑜𝑟, 𝑚𝑖𝑛𝐿𝑒𝑛𝑔𝑡ℎ, 𝑚𝑎𝑥𝐿𝑒𝑛𝑔𝑡ℎ, 𝐸𝑈𝐶𝑆) 15. end if 16. end if 17.end for Thuật toán 3 (ConstructUL) thực hiện kết hợp hai 𝑈𝐿𝑖𝑠𝑡 𝑃𝑥, 𝑃𝑦 thành một 𝑈𝐿𝑖𝑠𝑡 mở rộng 𝑃𝑥𝑦. Thuật toán có dữ liệu đầu vào là 𝑈𝐿𝑖𝑠𝑡 tiền tố 𝑃, hai 𝑈𝐿𝑖𝑠𝑡 cần kết hợp là 𝑃𝑥 và 𝑃𝑦. Dữ liệu đầu ra là 𝑈𝐿𝑖𝑠𝑡 sau khi kết hợp 𝑃𝑥𝑦. Tại dòng 1, đặt giá trị ban đầu cho 𝑈𝐿𝐴 = 𝑈(𝑃) + 𝑅𝑈(𝑃) để chuẩn bị cho việc áp dụng chiến lược tỉa 𝐿𝐴 − 𝑃𝑟𝑢𝑛𝑒. Dòng 2 duyệt qua từng bộ 𝑒𝑥∠ 𝑃𝑥 và kiểm tra nếu có bộ 𝑒𝑦 ∠ 𝑃𝑦 mà 𝑒𝑥. 𝑡𝑖𝑑 = 𝑒𝑦. 𝑡𝑖𝑑 (dòng 3) thì tạo một bộ mở rộng 𝑒𝑥𝑦 bởi một trong hai trường hợp: trường hợp nếu 𝑈𝐿𝑖𝑠𝑡 tiền tố 𝑃 ≈ ∪ (dòng 4) nghĩa là 𝑃𝑥, 𝑃𝑦 là các 𝑈𝐿𝑖𝑠𝑡 có từ 2 phần tử trở lên. Khi đó thực hiện tìm bộ 𝑒 ∠ 𝑃 sao cho 𝑒. 𝑡𝑖𝑑 = 𝑒𝑥. 𝑡𝑖𝑑 và tạo giá trị bộ 𝑒𝑥𝑦 =< 𝑒𝑥. 𝑡𝑖𝑑, 𝑒𝑥. 𝑢 + 𝑒𝑦. 𝑢 − 𝑒. 𝑢, 𝑒𝑦. 𝑟𝑢 > (dòng 5,6). Trường hợp ngược lại (𝑃 = ∪) nghĩa là 𝑃𝑥, 𝑃𝑦 là các 𝑈𝐿𝑖𝑠𝑡 một phần tử không có 𝑈𝐿𝑖𝑠𝑡 tiền tố, khi đó thực hiện tạo giá trị bộ 𝑒𝑥𝑦 =< 𝑒𝑥. 𝑡𝑖𝑑, 𝑒𝑥. 𝑢 + 𝑒𝑦. 𝑢, 𝑒𝑦. 𝑟𝑢 > (dòng 8). Tại dòng 11, trường hợp ngược lại điều kiện dòng 3, nghĩa là không tồn tại bất kỳ bộ 𝑒𝑦 nào thuộc 𝑃𝑦 thì giảm 𝑈𝐿𝐴 một lượng 𝑒𝑥. 𝑢 + 𝑒𝑥. 𝑟𝑢 (áp dụng chiến lược tỉa 𝐿𝐴 − 𝑃𝑟𝑢𝑛𝑒). Dòng 18 trả về kết quả là 𝑈𝐿𝑖𝑠𝑡 𝑃𝑥𝑦 được kết hợp từ hai 𝑈𝐿𝑖𝑠𝑡 𝑃𝑥 và 𝑃𝑦. Thuật toán 3: (ConstructUL) Vào: 𝑃: UList là tiền tố; 𝑃𝑥, 𝑃𝑦: Hai UList cần kết hợp; 𝑚𝑖𝑛𝑈𝑡𝑖𝑙: Ngưỡng độ hữu ích tối thiểu. Ra: 𝑃𝑥𝑦: UList sau khi kết hợp 𝑃𝑥 và 𝑃𝑦. 1. Đặt 𝑈𝐿𝐴 = 𝑈(𝑃) + 𝑅𝑈(𝑃); 2. for bộ 𝑒𝑥∠ 𝑃𝑥 then 3. if ∋ 𝑒𝑦 ∠ 𝑃𝑦 ⇔𝑒𝑥. 𝑡𝑖𝑑 = 𝑒𝑦. 𝑡𝑖𝑑 then 4. if 𝑃 ≈ ∪ then 5. Tìm 𝑒 ∠ 𝑃 sao cho 𝑒. 𝑡𝑖𝑑 = 𝑒𝑥. 𝑡𝑖𝑑; 6. 𝑒𝑥𝑦 =< 𝑒𝑥. 𝑡𝑖𝑑, 𝑒𝑥. 𝑢 + 𝑒𝑦. 𝑢 − 𝑒. 𝑢, 𝑒𝑦. 𝑟𝑢 >; 7. else 8. 𝑒𝑥𝑦 =< 𝑒𝑥. 𝑡𝑖𝑑, 𝑒𝑥. 𝑢 + 𝑒𝑦. 𝑢, 𝑒𝑦. 𝑟𝑢 >; 9. end if 10. 𝑃𝑥𝑦 → 𝑒𝑥𝑦; 11. else 12. 𝑈𝐿𝐴 = 𝑈𝐿𝐴 − (𝑒𝑥. 𝑢 + 𝑒𝑥. 𝑟𝑢);
378 KHAI THÁC TẬP HỮU ÍCH CAO TƯƠNG QUAN VỚI RÀNG BUỘC CHIỀU DÀI 13. if 𝑈𝐿𝐴 < 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 then // áp dụng chiến lược tỉa LA-Prune 14. return null; 15. end if 16. end if 17. end for 18. return 𝑃𝑥𝑦; V. THỰC NGHIỆM Thuật toán CHL được cài đặt bằng ngôn ngữ lập trình Java, chạy thử nghiệm trên máy tính Dell Precision, Intel Core i3-2310 CPU @2.1GHz, bộ nhớ RAM 4 GB trên hệ điều hành Windows 10. Các cơ sở dữ liệu thử nghiệm được tải từ thư viện SPMF [15] gồm: Chess, Mushroom, Accident, Kosarak, Retail và Chainstore. Chi tiết các cơ sở dữ liệu được trình bày trong Bảng 5. Thực nghiệm của thuật toán CHL được so sánh với thuật toán mới nhất cùng khai thác tập CHUI là CoUPM [11]. Kết quả thực nghiệm được đánh giá dựa trên thời gian thực thi và dung lượng bộ nhớ sử dụng. Bảng 5. Đặc điểm các cơ sở dữ liệu thực nghiệm Số lượng Số lượng Độ dài trung Độ dày Cơ sở dữ liệu giao dịch item (I) bình (A) (A/I) % Chess 3.196 75 37 49,3333 Mushroom 8.124 119 23 19,3277 Accident 340.183 468 33,8 7,2222 Retail 88.162 16.470 10,3 0,0625 Kosarak 990.002 41.270 8,1 0,0196 Chainstore 1.112.949 46.086 7,3 0,0158 Hình 2, 3, 4 và 5 trình bày kết quả thực nghiệm so sánh giữa thuật toán CHL với thuật toán CoUPM về thời gian thực thi và bộ nhớ sử dụng. Kết quả thực nghiệm cho thấy thuật toán CHL có thời gian thực thi hiệu quả hơn thuật toán CoUPM trên tất cả các cơ sở dữ liệu từ rất dày như Chess đến rất thưa như Chainstore. Bộ nhớ sử dụng của thuật toán CHL cũng hiệu quả hơn thuật toán CoUPM ở các cơ sở dữ liệu Chess, Accident, Retail và Chainstore trên tất cả các ngưỡng minUtil, maxLength và các ngưỡng tương quan minCor lớn. Hình 2. So sánh thời gian thực thi trên các cơ sở dữ liệu dày Hình 3. So sánh thời gian thực thi trên các cơ sở dữ liệu thưa Hình 2, 3 trình bày kết quả thực nghiệm về thời gian thực thi của hai thuật toán CHL và CoUPM trên cơ sở dữ liệu rất dày như Chess, dày trung bình Mushroom, dày vừa Accident và các cơ sở dữ liệu thưa trung bình Kosarak, thưa vừa Retail và rất thưa Chainstore. Việc thực nghiệm so sánh hai thuật toán sử dụng cùng các ngưỡng minUtil, minCor và ba ngưỡng maxLength lần lượt bằng 4, 5 và 6. Cụ thể ở Hình 2 thì thời gian thực hiện của thuật toán CHL so với thuật toán CoUPM như sau: Với cơ sở dữ liệu dày Chess thì thuật toán CHL nhanh hơn thuật toán CoUPM từ 2 đến 128 lần, trong đó với minUtil=500 và maxLength=4 thì thời gian thực hiện của CHL chỉ là 0,057giây trong khi
Nguyễn Văn Lễ, Trần Văn Thọ, Phạm Tuấn Khiêm, Nguyễn Văn Hoàng 379 CoUPM thực hiện đến 20,192 giây. Với cơ sở dữ liệu dày trung bình Mushroom thì thuật toán CHL nhanh hơn thuật toán CoUPM từ 2 đến 5 lần tương ứng mới các ngưỡng minUtil bằng 50.000 và 250.000. Với co sở dữ liệu dày vừa Accident thì thuật toán CHL nhanh hơn thuật toán CoUPM với các ngưỡng minUtil lớn và trung bình và sẽ giảm dần khi ngưỡng minUtil càng nhỏ, thuật toán CHL nhanh hơn CoUPM từ 2 đến 49 lần. Ở Hình 3: với cơ sở dữ liệu thưa trung bình Kosarak thì thuật toán CHL chỉ nhanh hơn CoUPM từ 1 đến 2 lần; với cơ sở dữ liệu thưa vừa Retail thì thuật toán CHL nhanh hơn CoUPM tăng lên đáng kể từ 19 đến 47 lần tương ứng với các ngưỡng minUtil bằng 300.000 và 500.000, đặc biệt với cơ sở dữ liệu rất thưa Chainstore thì thuật toán CHL càng vượt trội so với thuật toán CoUPM. Thật vây, với ngưỡng minUtil=1.900.000 và maxLength=6 thì thuật toán CHL thực hiện chỉ với 11,663 giây so với 474,051 giây của thuật toán CoUPM. Mức độ nhanh hơn nhiều nhất thể hiện với ngưỡng minUtil=1.300.000 và maxLength=5 thì thuật toán CHL chỉ thực hiện trong 7,462 giây trong khi thời gian thực thi của thuật toán CoUPM lên đến 899,311 giây. Tại 2 ngưỡng minUtil=1.000.000 và 700.000 thì thuật toán CHL cho kết quả từ 7 đến 18 giây, trong khi thuật toán CoUPM có thời gian thực thi lâu vượt ngoài vùng dữ liệu biểu đồ. Kết quả này chứng tỏ rằng các chiến lược tỉa và cấu trúc dữ liệu sử dụng trong thuật toán CHL với ràng buộc minLength, maxLength đã cắt giảm đáng kể không gian tìm kiếm, từ đó làm tăng hiệu suất thực thi của thuật toán CHL. Hình 4. So sánh bộ nhớ sử dụng trên cơ sở dữ liệu dày Hình 5. So sánh bộ nhớ sử dụng trên cơ sở dữ liệu thưa Hình 4, 5 trình bày kết quả thực nghiệm về bộ nhớ sử dụng của hai thuật toán CHL và CoUPM trên các cơ sở dữ liệu rất dày như Chess, dày trung bình Mushroom, dày vừa Accident và các CSDL thưa trung bình Kosarak, thưa vừa Retail và rất thưa Chainstore. Việc thực nghiệm so sánh hai thuật toán sử dụng cùng các ngưỡng minUtil, minCor và ba ngưỡng maxLength lần lượt bằng 4, 5 và 6. Cụ thể ở Hình 4, với cơ sở dữ liệu Chess thì thuật toán CHL sử dụng bộ nhớ thấp hơn thuật toán CoUPM từ 1.15 đến 3.27 lần, chẳng hạn với minUtil=600,000, maxLength=4 thì thuật toán CoUPM sử dụng bộ nhớ là 134 MB trong khi thuật toán CHL chỉ sử dụng 41 MB. Với cơ sở dữ liệu Mushroom thì mức độ sử dụng bộ nhớ của 2 thuật toán CHL và CoUPM không chênh lệch nhiều. Thực nghiệm trên cơ sở dữ liệu Accident thì thuật toán CHL sử dụng bộ nhớ thấp hơn CoUPM với tất cả các ngưỡng minUtil và maxLength, chẳng hạn tại ngưỡng minUtil=2.800.000, maxLength=4, thuật toán CHL sử dụng 570 MB trong khi thuật toán CoUPM sử dụng lên đến 1,265 MB. Ở Hình 5: với cơ sở dữ liệu thưa trung bình Kosarak thì thuật toán CHL sử dụng bộ nhớ nhiều hơn thuật toán CoUPM ở tất cả các ngưỡng minUtil và maxLength. Với cơ sở dữ liệu Retail, thuật toán CHL sử dụng bộ nhớ thấp hơn thuật toán CoUPM từ 1,04 đến 1,79 lần tương ứng với các ngưỡng minUtil=500.000 và 300.000. Với cơ sở dữ liệu rất thưa Chainstore thì thuật toán CHL cũng sử dụng bộ nhớ thấp hơn CoUPM, chẳng hạn với các ngưỡng minUtil=1.300.000 tại maxLength=4 thì thuật toán CoUPM sử dụng 835 MB trong khi CHL sử dụng 655 MB. Kết quả này cho thấy thuật toán CHL có dung lượng bộ nhớ sử dụng thấp hơn thuật toán CoUPM ở hầu hết các cơ sở dữ liệu thực nghiệm. Điều này chứng tỏ rằng việc sử dụng các chiến lược tỉa và cấu trúc dữ liệu lưu trữ cũng có ảnh hưởng đến bộ nhớ sử dụng của các thuật toán. Thuật toán CHL chỉ sử dụng bộ nhớ nhiều hơn thuật toán CoUPM ở 2 trong số 6 CSDL thực nghiệm, nhưng sự chênh lệch đó là không đáng kể.
380 KHAI THÁC TẬP HỮU ÍCH CAO TƯƠNG QUAN VỚI RÀNG BUỘC CHIỀU DÀI VI. KẾT LUẬN Khai thác tập hữu ích cao tương quan với ràng buộc chiều dài là một mở rộng của bài toán khai phá tập hữu ích cao tương quan (CHUIs) trên cơ sở dữ liệu giao dịch mà các nghiên cứu trước đây chưa đề cập đến. Trong bài báo này chúng tôi đề xuất thuật toán CHL khai thác tập hữu ích cao tương quan với ràng buộc chiều dài để khai thác tập CoHUI thật sự có ý nghĩa trong phân tích kinh doanh. Thuật toán CHL sử dụng cấu trúc dữ liệu Utility List kết hợp với nhiều chiến lược tỉa hiệu quả như U-Prune, LA-Prune, EUCS-Prune và Kulc-Prune. Kết quả thực nghiệm trên 2 nhóm cơ sở dữ liệu dày và thưa đã chứng tỏ được thuật toán CHL có hiệu suất thực thi tốt hơn so với thuật toán CoUPM cả về thời gian thực thi và bộ nhớ sử dụng. Hướng phát triển tiếp theo là cải tiến cấu trúc dữ liệu lưu trữ và chiến lược tỉa để tăng hiệu suất thực thi của thuật toán trên các cơ sở dữ liệu dày, khai thác CHUIs trên các dạng cơ sở dữ liệu khác như cơ sở dữ liệu động và tăng trưởng. TÀI LIỆU THAM KHẢO [1] V. S. Tseng, C. W. Wu, B. E. Shie, and P. S. Yu, “Up-Growth: An efficient algorithm for high utility itemset mining”, Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 253-262, 2010. [2] Y. Liu, W. K. Liao, and A. Choudhary, “A two-phase algorithm for fast discovery of high utility itemsets”, Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 689-695, 2005. [3] M. Liu and J. Qu, “Mining high utility itemsets without candidate generation”, Proceedings of the 21st ACM International Conference on Information and Knowledge Management, pp. 55-64, 2012. [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] 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. [6] S. Krishnamoorthy, “HMiner: Efficiently mining high utility itemsets”, Expert Systems with Applications, vol. 90, pp. 168-183, 2017. [7] 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”, Engineering and Other Applications of Applied Intelligent Systems, pp. 115-127, 2016. [8] P. Fournier-Viger, Y. Zhang, J. C. W. Lin, D. T. Dinh, and H. B. Le, “Mining correlated high-utility itemsets using various measures”, Logic Journal of the IGPL, vol. 28, No. 1, pp. 19-32, 2020. [9] J. C. W. Lin, W. Gan, P. Fournier-Viger, T. P. Hong, and H. C. Chao, “FDHUP: Fast algorithm for mining discriminative high utility patterns”, Knowledge and Information Systems, vol. 51, pp. 873-909, 2017. [10] 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. [11] 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. [12] A. Erwin, R. P. Gopalan, and N. R. Achuthan, “CTU-Mine: An efficient high utility itemset mining algorithm using the pattern growth approach”, IEEE International Conference on Computer and Information Technology, pp. 71-76, 2007. [13] V. S. Tseng, B. E. Shie, C. W. Wu, and S. Y. Philip, “Efficient algorithms for mining high utility itemsets from transactional databases”, IEEE transactions on knowledge and data engineering, vol. 25, pp. 1772-1786, 2012. [14] K. Singh and B. Biswas, “Efficient algorithm for mining high utility pattern considering length constraints”, International Journal of Data Warehousing and Mining, vol. 15, No. 3, pp. 1-27, 2019. [15] P. Fournier-Viger, A. Gomariz, A. Soltani, and H. Lam. An Open-Source Data Mining Library. http://www.philippe-fournier- viger.com, 2014. MINING CORRELATED HIGH UTILITY ITEMSETS WITH LENGTH CONSTRAINTS Nguyen Van Le, Tran Van Tho, Pham Tuan Khiem, Nguyen Van Hoang ABSTRACT: The problem of mining the Correlated High Utility Itemset (CoHUI) in transactional databases have been proposed by many studies to extract knowledge from users' purchasing behavior. However, the mining results have many sets with a large number of items will make it difficult to analyze and decide in business instead of considering the result itemsets with a smaller number of items. Therefore, the length constraint is added in the mining process but only considered in mining high utility itemset without considering for mining highly correlated utility itemset. In this paper, we propose the CHL algorithm (Correlated High utility itemset with Length constraint) to exploit the correlated high utility itemsets on the transaction database with the length constraint. The experiment results on Chess, Mushroom, Accident, Kosarak, Retail, Chainstore datasets show that the CHL algorithm has effective execution performance, especially in sparse datasets.