CẢI TIẾN THUẬT TOÁN APRIORI TRÊN MÔ HÌNH MAP/REDUCE

Abstract

Tóm tắt: Tìm kiếm c{c tập mục phổ biến l| một bước rất quan trọng khai ph{ luật kết hợp,để từ đó ph{t sinh luật kết hợp. Một trong những thuật to{n khai ph{ luật kết hợp kinh điểnv| nổi tiếng l| thuật to{n Apriori. Tuy nhiên, thuật to{n Apriori có yếu điểm l| với trườnghợp cơ sở dữ liệu lớn thì thời gian tính to{n cũng sẽ rất lớn. Vì vậy, trong b|i b{o n|y chúngtôi đề xuất một cải tiến của thuật to{n Apriori trên mô hình lập trình v| tính to{n song songMap/Reduce. Cải tiến được thực hiện thông qua việc x}y dựng thuật to{n Apriori trên môhình Map/Reduce, qua đó đưa ra giải ph{p tìm tất cả tập mục phổ biến thông qua hai pha:pha thứ nhất tìm c{c tập mục phổ biến 1_itemsets; pha thứ hai tìm tất cả tập mục phổ biếnk_itemsets (k>=2). Với phương ph{p n|y việc tính to{n đã cải thiện đ{ng kể thời gian tínhto{n khi ứng dụng thuật to{n Apriori khai ph{ cơ sở dữ liệu lớn. Bước đầu thử nghiệm chothấy thuật to{n Apriori ph{t triển trên mô hình Map/Reduce cho kết quả nhanh hơn trên cơsở dữ liệu lớn so với thuật to{n Apriori gốc.

Từ khóa: Apriori, Map/Reduce