DFS-Apriori: Khai thác nhanh tập phổ biến áp dụng chiến lược tìm kiếm theo chiều sâu

Bài viết "DFS-Apriori: Khai thác nhanh tập phổ biến áp dụng chiến lược tìm kiếm theo chiều sâu" khảo sát một số thuật toán Apriori cải tiến và trình bày cách tiếp cận mới cải tiến hiệu quả thuật toán Apriori dựa theo chiến lược tìm kiếm theo chiều sâu (Depth First Search – DFS) – dễ dàng mở rộng trên môi trường tính toán phân tán. Đồng thời, thuật toán đề xuất kỹ thuật rút gọn các ứng viên, tính nhanh độ phổ biến của ứng viên và biểu diễn dữ liệu dạng bit - giúp đẩy nhanh tốc độ tính toán và giảm thiểu truy xuất dữ liệu. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
DFS-Apriori: Khai thác nhanh tập phổ biến áp dụng chiến lược tìm kiếm theo chiều sâu Hội nghị Quốc gia lần thứ 25 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2022) DFS-Apriori: Khai Thác Nhanh Tập Phổ Biến Áp Dụng Chiến Lƣợc Tìm Kiếm Theo Chiều Sâu Phan Thành Huấn1,2,4, Đặng Thanh Minh1,4, Nguyễn Nhƣ Đồng3 1 Khoa Toán – Tin học, Trƣờng Đại học Khoa học Tự nhiên, ĐHQG.HCM-VN 2 Bộ môn Tin học, Trƣờng Đại học Khoa học Xã hội và Nhân văn, ĐHQG.HCM-VN 3 Trung tâm Giáo dục Nghề nghiệp – Giáo dục Thƣờng xuyên, Tp. Thủ Đức 4 Đại học Quốc gia Tp. Hồ Chí Minh Email: huanphan@hcmussh.edu.vn; minhthanhdang1982@gmail.com; dongnhunguyen74@gmail.com Tóm tắt - Khai thác tập phổ biến là giai đoạn cốt lõi trong khai đƣợc nhiều nhà nghiên cứu cải tiến và áp dụng khai phá trên thác luật kết hợp từ dữ liệu giao dịch nhị phân. Agrawal cùng nhiều loại dữ liệu khác nhau: chuỗi [3], định lượng [4], đồ thị đồng sự đề xuất thuật toán Apriori . Đây là thuật toán cơ sở cho [5], thuộc tính có trọng số [6],… nhiều cải tiến, cũng như được sử dụng khai thác trên nhiều loại Qua khảo sát các nghiên cứu liên quan đến cải tiến thuật dữ liệu khác nhau. Ngoài ra, những năm gần đây thuật toán toán Apriori khai thác tập phổ biến trên DLGD nhị phân, gồm Apriori là thuật toán được nhiều nhà nghiên cứu lựa chọn để mở hai hướng tiếp cận chính: rộng cho khai thác tập phổ biến từ dữ liệu lớn trên môi trường  Định dạng dữ liệu theo chiều ngang: Đây là định dạng phân tán. Thuật toán Apriori dựa theo chiến lược tìm kiếm theo theo thuật toán Apriori gốc. Các thuật toán cải tiến Apriori chiều rộng (Breadth First Search – BFS) – điều này làm hạn chế trong thực hiện tính toán phân tán. Trong bài viết này, nhóm tác thƣờng sử dụng chiến lƣợc rút gọn giao dịch và rút gọn giả khảo sát một số thuật toán Apriori cải tiến và trình bày cách không gian sinh các ứng viên tiềm năng k-itemset. Tuy tiếp cận mới cải tiến hiệu quả thuật toán Apriori dựa theo chiến nhiên, vấn đề tính độ phổ biến của k-itemset vẫn chƣa thật lược tìm kiếm theo chiều sâu (Depth First Search – DFS) – dễ sự hiệu quả. dàng mở rộng trên môi trường tính toán phân tán. Đồng thời,  Định dạng dữ liệu theo chiều dọc: Năm 1995, Savasere thuật toán đề xuất kỹ thuật rút gọn các ứng viên, tính nhanh độ [7] cùng đồng sự đề xuất thuật toán Parition sử dụng định phổ biến của ứng viên và biểu diễn dữ liệu dạng bit - giúp đẩy dạng dữ liệu theo chiều dọc. Định dạng này, giúp tính độ nhanh tốc độ tính toán và giảm thiểu truy xuất dữ liệu. Thuật phổ biến dễ dàng và hạn chế đối với DLGD có mật độ cao. toán cải tiến được gọi là DFS-Apriori. Nhóm tác giả tiến hành Bảng 1. Một số công trình cải tiến thuật toán Apriori [7-16] thực nghiệm thuật toán trên bộ dữ liệu thực của UCI và dữ liệu Tác giả Định dạng Thuật toán Năm giả lập của trung tâm nghiên cứu IBM Almaden, cho thấy thuật đứng đầu dữ liệu toán cải tiến hiệu quả. A. Savasere Partition dọc 1995 J. Lei HDO-Apriori ngang 2006 Từ khóa – luật kết hợp, tập phổ biến, thuật toán DFS-Apriori. W.Yu RATT ngang 2008 Y. Guo IApriori dọc 2010 I. GIỚI THIỆU J. Singh SOT-Apriori ngang 2013 Năm 1993, Agrawal cùng đồng sự đề xuất mô hình đầu tiên H. Singh MBAT ngang 2013 của bài toán khai thác luật kết hợp – khai thác luật kết hợp trên M. A. Maolegi M-Apriori dọc 2014 dữ liệu giao dịch (DLGD) nhị phân [1]. Khai thác luật kết hợp V.Vijayalakshmi CBTRA ngang 2015 là khai phá các luật kết hợp có độ phổ biến (support) cũng nhƣ S. Aditya LOT-Apriori ngang 2017 độ tin cậy (confidence) lớn hơn hoặc bằng một ngƣỡng phổ L. Xu MD-Apriori dọc 2019 biến tối thiểu (minsup) và ngƣỡng tin cậy tối thiểu (minconf). Bảng 1, liệt kê một số thuật toán cải tiến Apriori. Các đặc Bài toán đƣợc chia thành hai pha: trƣng của thuật toán cải tiến: i) rút gọn giao dịch dựa vào số Pha 1: Tìm tất cả các kết hợp thỏa ngƣỡng phổ biến tối lƣợng items trên mỗi giao dịch – SOT-Aprioir [11], CBTRA thiểu minsup (sinh tập phổ biến FI - Frequent Itemset); [14], LOT-Apriori [15] ; ii) rút gọn tập ứng viên tiềm năng – Pha 2: Sinh luật kết hợp lần lƣợt từ các kết hợp thỏa Partition [7], HDO-Apriori [8], Iapriori [11], M-Ap ...