Tổng luận về khai thác song song tập phổ biến từ dữ liệu giao dịch trên bộ xử lý đa nhân

Bài viết trình bày khảo sát và tổng luận về một số thuật toán khai thác song song tập phổ biến (bước quan trọng của khai thác luật kết hợp) trên bộ xử lý đa nhân. Điều này giúp các nhà nghiên cứu có sự lựa chọn giải pháp kỹ thuật phù hợp khi cần nâng cao hiệu năng trong khai thác dữ liệu lớn.
Nội dung trích xuất từ tài liệu:
Tổng luận về khai thác song song tập phổ biến từ dữ liệu giao dịch trên bộ xử lý đa nhân Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020) Tổng Luận về Khai Thác Song Song Tập Phổ Biến từ Dữ Liệu Giao Dịch trên Bộ Xử Lý Đa Nhân Phan Thành Huấn1,2 , Lê Hoài Bắc3 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 Khoa Công nghệ Thông tin, Trƣờng Đại học Khoa học Tự nhiên, ĐHQG.HCM-VN Email: huanphan@hcmussh.edu.vn, lhbac@fithcmus.edu.vn Tóm tắt - Trong gần ba mươi năm qua, khai thác luật kết hợp gian trong khai thác tập phổ biến, nhiều nhà nghiên cứu đã đề luôn được nhiều nhà nghiên cứu quan tâm và đề xuất nhiều thuật xuất thuật toán khai thác hiệu quả tập phổ biến dựa vào các toán hiệu quả cho bài toán tìm kiếm các mối tương quan tiềm ẩn cấu trúc lƣu trữ rút gọn không gian tìm kiếm nhƣ SE-Tree, giữa các item trong dữ liệu. Cùng với sự bùng nổ của dữ liệu lớn Prefix-Tree, IT-Tree, FP-Tree,… Tuy nhiên, trong thực tế việc và phát triển vượt bậc của kỹ thuật phần cứng, một số nhà phát sinh tập phổ biến tốn nhiều thời gian và có số lƣợng nghiên cứu đã nâng cao hiệu năng khai thác luật kết hợp bằng itemset rất lớn. Vì vậy, một số nhà nghiên cứu đã đề xuất khai cách sử dụng môi trường tính toán song song trên các bộ xử lý đa thác tập phổ biến đóng CFI (Closed Frequent Itemset) có số nhân – giúp giảm thiểu thời gian khai thác đáng kể. Trong bài lƣợng ít hơn tập phổ biến nhƣ thuật toán A-Close [4], Charm viết này, chúng tôi khảo sát và tổng luận về một số thuật toán khai thác song song tập phổ biến (bước quan trọng của khai thác [5], ... Song song đó, một số nhà khoa học khác cũng đề xuất luật kết hợp) trên bộ xử lý đa nhân. Điều này giúp các nhà khai thác tập phổ biến tối đại MFI (Maximal Frequent nghiên cứu có sự lựa chọn giải pháp kỹ thuật phù hợp khi cần Itemset) nhƣ thuật toán Pincer-Search [6], Mafia [7], … nâng cao hiệu năng trong khai thác dữ liệu lớn. Sau cùng, chúng Ở một số ứng dụng thực tế, việc sử dụng các tập FI, CFI tôi đưa ra khuyến nghị và định hướng nghiên cứu của nhóm và MFI tốn rất nhiều chi phí tính toán cũng nhƣ s ố lƣợng trong sự gia tăng như vũ bão của dữ liệu thu thập. itemset phổ biến rất lớn. Bayardo đề xuất khai thác tập phổ biến có chiều dài tối đa LFI (Maximu m Length Frequent Từ khóa – bộ xử lý đa nhân, khai thác song song, luật kết hợp, Itemset) đây là tập con của tập phổ biến FI và chỉ chứa các tập phổ biến. itemset phổ biến có chiều dài tối đa nhƣ thuật toán Max-Miner [8], DepthProject [9], ... I. GIỚI THIỆU Năm 1995, Park đã phát triển thuật toán PDM [10] tựa Apriori chạy trên hệ thống tính toán phân tán (HT3PT) để Khai thác luật kết hợp là một kỹ thuật quan trọng trong lĩnh nâng cao hiệu năng khai thác dữ liệu. Những năm sau: Zaki, vực khai thác dữ liệu. Mục tiêu khai thác là phát hiện những Agrawal và Han cũng lần lƣợt đề xuất các thuật toán CCPD mố i tƣơng quan giữa các item trong tập dữ liệu. Năm 1993, [11], AprioriHybrid [12] và IDD [13] theo hƣớng tiếp cận tựa Agrawal và đồng sự đề xuất mô hình đầu tiên của bài toán khai Apriori. Năm 1997, Zaki đã đề xuất thuật toán Par-Eclat [14] thác luật kết hợp là mô hình nhị phân hay còn gọi là mô hình khai thác luật kết hợp trên HT3PT theo hƣớng tiếp cận trên cơ bản, phân tích dữ liệu giao dịch, phát hiện các mối tƣơng cấu trúc dàn (lattice). Đến năm 2003, Chung dựa trên thuật quan giữa các mặt hàng đã bán tại các siêu thị. Từ đó có kế toán Max-Miner [8] của Bayardo và hiệu chỉnh thực hiện trên hoạch bố trí, sắp xếp, kinh doanh hợp lý, đồng thời tổ chức sắp HT3PT gọi là thuật toán Par-MaxMiner. Tuy nhiên, các xếp các quầy gần nhau nhƣ thế nào để có doanh thu trong các HT3PT tồn tại hạn chế lớn là phụ thuộc vào đƣờng truyền trao phiên giao dịch là lớn nhất. Ngoài ra, có thể áp dụng tri thức đổi thông tin giữa các máy tính. Năm 2004, Javed đề xuất này để dự đoán số lƣợng các mặt hàng đƣợc bán chạy nhất thuật toán PFP [16] dựa trên cấu trúc FP-Tree để khai thác trong thời gian sắp tới. Tổng hợp các tri thức này để lên kế song song tập phổ biến trên máy tính có nhiều Bộ xử lý hoạch cho hoạt động, sản xuất, kinh doanh một cách thuận tiện (BXL), các thuật toán này cũng tồn tại hạn chế về độ trễ cao hơn nhằm giảm bớt thời gian thống kê, tìm hiểu thị trƣờng,... khi các BXL cần giao tiếp. Năm 2005, Intel đã cho ra đời thế Các thuật toán tuần tự đƣợc đề xuất cho khai thác luật kết hệ BXL chứa nhiều nhân xử lý (BXLĐN), kéo theo nhiều hợp chia thành 2 pha [1-9]: công trình khai thác hiệu quả tập phổ biến trên BXLĐN nhƣ FP-array [17], PLCM [20],… cho đến nay. Pha 1: Tìm tất cả các kết hợp thỏa ngƣỡng phổ biến tối Phần 2, bài báo trình bày các khái niệm cơ bản về khai thác thiểu minsup - ph ...