Bài báo này đề xuất một thuật toán mới được gọi là EDMAR (an Efficient Distributed algorithm for Mining Association Rules) . Thuật toán này sử dụng thuật toán FP-Growth và cấu trúc FP-Tree để khai phá tập phổ biến cục bộ tại các điểm đã làm giảm số lần quét cơ sở dữ liệu, từ đó tăng hiệu quả khai phá tại các điểm cục bộ. | JOURNAL OF SCIENCE OF HNUE FIT. 2011 Vol. 56 pp. 29-39 MỘT PHƯƠNG PHÁP KHAI PHÁ LUẬT KẾT HỢP HIỆU QUẢ TRONG MÔI TRƯỜNG PHÂN TÁN Nguyễn Thế Bình Lương Thế Dũng Trung Tâm CNTT - Ban Cơ yếu Chính phủ Nguyễn Mạnh Hùng Học viện Kỹ thuật quân sự Email nguyenthebinh81@ Tóm tắt. Khai phá luật kết hợp trong môi trường phân tán là một hướng nghiên cứu quan trọng trong lĩnh vực khai phá dữ liệu một số thuật toán khai phá luật kết hợp phân tán đã được đề xuất. Tuy nhiên việc phát triển các thuật toán mới hiệu quả hơn vẫn đang là vấn đề dành được nhiều sự quan tâm. Bài báo này đề xuất một thuật toán mới được gọi là EDMAR an Efficient Distributed algorithm for Mining Association Rules . Thuật toán này sử dụng thuật toán FP-Growth và cấu trúc FP-Tree để khai phá tập phổ biến cục bộ tại các điểm đã làm giảm số lần quét cơ sở dữ liệu từ đó tăng hiệu quả khai phá tại các điểm cục bộ. Hơn nữa EDMAR đã giảm thiểu được số lượng các tập ứng cử toàn cục sử dụng ít hơn các bước đồng bộ do đó làm tăng hiệu quả trong quá trình khai phá. 1. Mở đầu Khai phá luật kết hợp là một nội dung quan trọng trong khai phá dữ liệu KPDL được khởi xướng từ năm 1993 1 và cho đến thời điểm này đã có rất nhiều thuật toán khai phá luật kết hợp đã được các tác giả đưa ra. Quá trình khai phá luật kết hợp được chia thành hai bài toán Tìm tất cả các tập mục phổ biến có trong cơ sở dữ liệu CSDL dựa vào ngưỡng độ hỗ trợ tối thiểu và tạo ra các luật mong muốn từ các tập mục phổ biến với điều kiện chúng thỏa mãn ngưỡng độ tin cậy tối thiểu. Trong hai bài toán này thì bài toán thứ hai là đơn giản hơn vì vậy hầu hết các nghiên cứu về luật kết hợp đều tập trung ở bài toán thứ nhất. Một trong những thuật toán khá nổi tiếng là Apriori 1 sau đó có một vài thuật toán phát triển dựa trên Apriori 2 3 . Thuật toán thực hiện các bước lặp trong mỗi bước lặp sẽ dùng tập phổ biến k-1 phần tử để tạo ra các tập ứng cử k phần tử sau đó duyệt CSDL để đối sánh mẫu và đếm số lần xuất hiện của của các 29 Nguyễn Thế Bình Lương .
