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

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ộ.
Nội dung trích xuất từ tài liệu:
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 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@yahoo.com 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 Thế Dũng, Nguyễn Mạnh Hùng ứng cử viên. Từ đó tìm ra tập phổ biến k phần tử. Quá trình lặp kết thúc khi không có tập phổ biến nào được tạo ra. Hạn chế của thuật toán Apriori và các thuật toán dựa vào Apriori là việc phải tạo ra một lượng rất lớn các tập ứng cử viên và phải duyệt CSDL nhiều lần, nếu số phần tử của tập phổ biến có độ dài dài nhất là n thì thuật toán phải quét CSDL (n+1 ) lần. Điều này dẫn đến thuật toán hoạt động kém hiệu quả. Các thuật toán phát triển dựa trên Apriori mặc dù đã có rất nhiều cải tiến nhưng vẫn chưa giải quyết được tốt các vấn đề trên. Gần đây, thuật toán khai phá tập phổ biến FP-Growth [4] sử dụng cấu trúc FP-Tree được phát triển bởi JIA WEI HAN có hiệu quả khá tốt nếu so sánh với thuật toán Apriori. Ý tưởng của thuật toán là dùng đệ quy để gia tăng độ dài của mẫu phổ biến dựa trên cây FP-Tree và các mẫu được phân hoạch. Ưu điểm của thuật toán này là không tạo ra các tập ứng cử và chỉ phải quét CSDL hai lần, lần quét thứ nhất là để tìm tập phổ biến một phần tử và lần quét thứ hai là để xây dựng cây FP-Tree. Nói chung đến thời điểm hiện tại thì thuật toán FP-Growth vẫn được đánh giá là một thuật toán hoạt động hiệu quả. Ngày nay với sự phát triển mạnh mẽ của công nghệ tính toán và công nghệ mạng đã dẫn đến việc phân tán nguồn dữ liệu. Khi dữ liệu được lưu trữ trên một CSDL phân tán, thì một thuật toán khai phá dữ liệu phân tán lại là cần thiết để khai phá các luật kết hợp. Khai phá các luật kết hợp trong môi trường phân tán là một vấn đề phải được giải quyết bằng việc sử dụng một thuật toán phân tán mà không cần phải trao đổi dữ liệu thô giữa các bên tham gia. Đến nay cũng đã có nhiều thuật toán khai phá luật kết hợp trong môi trường phân tán được đề xuất, ví dụ các thuật toán phổ biến như CD [9], FDM [7], PMFI [6] và DMAR [8]. Nhìn chung trong các thuật toán trên thường sử dụng một thủ tục (Ví dụ: Apriori_gen) để sinh tập ứng cử phổ biến toàn cục từ các dữ liệu cục bộ. Sau đó, sử dụng các kỹ thuật như: Cắt tỉa cục bộ tập ứng cử, cắt tỉa toàn cục tập ứng cử nên số lượng tập ứng cử đã giảm từ đó số lượng truyền thông cần trao đổi giữa các điểm cũng giảm. Mặc dù một số thuật toán được đánh giá là hiệu quả, nhưng số lượng truyền thông vẫn lớn do số lần đồng bộ nhiều. Do đó, vấn đề triển khai các thuật toán này cho các ứng dụng thực tế đặc biệt là các ứng dụng mà có các tập dữ liệu rất lớn còn gặp nhiều hạn chế, việc phát triển các phương pháp hiệu quả hơn vẫn đang là vấn đề được rất nhiều người quan tâm. Vấn đề được đặt ra khi xây dựng một thuật toán khai phá phân tán là làm thế nào để giảm thiểu được xử lý ở các điểm, giảm số lần quét CSDL, giảm thiểu khối lượng truyền thông giữa các điểm hoặc giữa các điểm với điểm chính và giảm thiểu số lần đồng bộ. Bài báo này chúng tôi đề xuất một thuật toán hiệu quả cho việc khai phá luật kết hợp trong môi trường phân tán EDMAR. Ý tưởng chính của EDMAR là sử dụng thuật toán FP-Growth để khai phá tập phổ biến tại các điểm, do đó tại mỗi 30 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 điểm chỉ cần hai lần quét CSDL. Trong quá trình xây dựng cây FP-treei tại mỗi điểm Si , thuật toán sẽ sử dụng danh sách tập phổ biến toàn cục 1-phần tử F’, điều này làm giảm đáng kể thời gian xử lý tại mỗi điểm. Thuật toán này sử dụng số lần đồng bộ tương đối ít (năm lần) và giảm thiểu chi phí truyền thông bằng cách sử dụng các kỹ thuật ở điểm chính để tạo ra các tập phổ biến toàn cục từ đó giảm bớt đi số lượng các tập mục ứng cử toàn ...