Bài báo này đề xuất một cải tiến của thuật toán Two-Phase. Việc cải tiến được thực hiện thông qua chiến lược tỉa hiệu quả hơn các tập mục ứng cử, cải tiến bước sinh tập ứng viên, nhờ đó giảm bớt được thời gian thực hiện thuật toán khai phá. | TẠP CHÍ KHOA HỌC, ðại học Huế, Số 65, 2011 MỘT THUẬT TOÁN KHAI PHÁ TẬP MỤC LỢI ÍCH CAO TRONG CƠ SỞ DỮ LIỆU Nguyễn Phúc Xuân Quỳnh Trường ðại học Sư Phạm, ðại học Huế TÓM TẮT Khai phá tập mục lợi ích cao (high-utility itemset) là một mở rộng của bài toán khai phá tập mục phổ biến, ñã ñược nhiều tác giả quan tâm với mục ñích ñánh giá ý nghĩa của các tập mục trong khai phá luật kết hợp. Thuật toán hai pha (Two-Phase) là một trong các thuật toán khai phá tập mục lợi ích cao. Bài báo này ñề xuất một cải tiến của thuật toán Two-Phase. Việc cải tiến ñược thực hiện thông qua chiến lược tỉa hiệu quả hơn các tập mục ứng cử, cải tiến bước sinh tập ứng viên, nhờ ñó giảm bớt ñược thời gian thực hiện thuật toán khai phá. 1. ðặt vấn ñề Khai phá tri thức từ dữ liệu là một trong những vấn ñề nhận ñược nhiều sự quan tâm của các nhà nghiên cứu. Trong lĩnh vực này, bài toán khai phá luật kết hợp ñược nghiên cứu rộng rãi. Một hướng mở rộng bài toán là quan tâm ñến các tập mục ñem lại lợi ích cao, quan tâm ñến mức ñộ quan trọng khác nhau của các mục dữ liệu. Mô hình khai phá tập mục lợi ích cao ñã ñược Yao và cộng sự ñề xuất [7]), từ ñó ñã có một số thuật toán khai phá tập mục lợi ích cao ñược ñưa ra trong [1, 2, 5, 6]. , Liao, Choudhary, 2005 [5] ñã ñưa ra khái niệm lợi ích của giao tác và lợi ích của tập mục tính theo lợi ích của giao tác chứa nó (lợi ích twu), từ ñó ñề xuất thuật toán Two-Phase [5] khai phá tất cả các tập mục lợi ích cao, tuy nhiên mất nhiều thời gian trong việc sinh ứng viên với cơ sở dữ liệu lớn. Vấn ñề của các thuật toán khai phá tập mục lợi ích cao là giảm thiểu kích thước của tập ứng viên và ñơn giản hóa quá trình tính toán lợi ích các tập mục. Nhằm giảm số lượng ứng viên cho tập mục lợi ích cao, giảm thời gian khai phá, bài báo ñề xuất thuật toán Im-Two-Phase trên cơ sở cải tiến bước sinh tập ứng viên và tính giá trị twu. 2. Các khái niệm và ñịnh nghĩa cơ bản Phần này trình bày các ñịnh nghĩa, tính chất cơ bản về tập mục lợi ích cao từ [5, 6, 7]. ðịnh .
