Thuật toán khai phá tập mục thường xuyên trong cơ sở dữ liệu lớn thông qua mẫu đại diện

Bài viết "Thuật toán khai phá tập mục thường xuyên trong cơ sở dữ liệu lớn thông qua mẫu đại diện" đề xuất thuật toán RSFPGrowth khai phá tập mục thường xuyên trong cơ sở dữ liệu lớn thông qua mẫu đại diện. Thuật toán RSFPGrowth cho phép thay vì tìm tập tất cả các tập mục thường xuyên trong cơ sở dữ liệu lớn bằng cách tìm tập chứa hầu hết các tập tập mục thường xuyên từ tập mẫu đại diện các giao tác. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Thuật toán khai phá tập mục thường xuyên trong cơ sở dữ liệu lớn thông qua mẫu đại diện THUẬT TOÁN KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN TRONG CƠ SỞ DỮ LIỆU LỚN THÔNG QUA MẪU ĐẠI DIỆN Nguyễn Hưng Long Khoa Hệ thống thông tin kinh tế và Thương mại điện tử, Đại học Thương mại Nguyễn Minh Hoàng Khoa Toán - Cơ - Tin học, Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội Tóm tắt Bài viết đề xuất thuật toán RSFPGrowth khai phá tập mục thường xuyên trong cơ sở dữ liệu lớn thông qua mẫu đại diện. Thuật toán RSFPGrowth cho phép thay vì tìm tập tất cả các tập mục thường xuyên trong cơ sở dữ liệu lớn bằng cách tìm tập chứa hầu hết các tập tập mục thường xuyên từ tập mẫu đại diện các giao tác. Bởi vì khi cỡ mẫu n cần lấy cho tập mẫu sẽ tăng chậm so với cỡ tổng thể nên độ hiệu quả của việc khai phá tập tập mục thường xuyên thông qua lấy mẫu đại diện các giao tác sẽ càng cao khi kích thước của cơ sở dữ liệu ban đầu càng lớn. Từ khóa: Khai phá dữ liệu, tập mục thường xuyên, cơ sở dữ liệu, mẫu đại diện, FP- Growth 1. Mở đầu Trong những năm gần đây, khai phá dữ liệu (KPDL) đã trở thành đề tài thu hút sự quan tâm của nhiều nhà nghiên cứu và đã được ứng dụng thành công trong mọi mặt của đời sống - xã hội. Khai phá dữ liệu được định nghĩa là quá trình trích lọc không tầm thường những thông tin hữu ích chưa biết từ các cơ sở dữ liệu (CSDL) lớn (có chứa đến hàng vạn, triệu các giao tác). Khai phá tập mục thường xuyên (TMTX) được biết đến như là bài toán con của bài toán khai phá dữ liệu và đã được giới thiệu lần đầu tiên vào năm 1993 bởi Agrawal R. và Srikant R. [5, 6], thuộc Trung tâm nghiên cứu Almaden của IBM (Mỹ), nhằm phân tích CSDL bán hàng tại siêu thị. Qua quá trình phân tích sẽ giúp cho nhà phân tích lựa chọn các phương án tốt nhất trong hoạt động kinh doanh của siêu thị. Để giải quyết bài toán này, các tác giả đề xuất thuật toán Apriori. Tại hội nghị quốc tế về khai phá dữ liệu vào tháng 12 năm 2006 đã đánh giá thuật toán Apriori đứng trong top 10 thuật toán khai phá dữ liệu [9]. Hiện đã có nhiều nghiên cứu, xây dựng các thuật toán khai phá TMTX được dựa trên thuật toán Apriori (gọi là các thuật toán kiểu Apriori). Thuật toán Apriori và các thuật toán kiểu Apriori có hai nhược điểm lớn: Phải sinh ra khối lượng khổng lồ các tập ứng viên và duyệt CSDL giao tác nhiều lần. TMTX là công cụ hiệu quả để khai phá các luật kết hợp (association rule), tập mục đóng (closed itemset), tập mục tuần tự (sequential itemset), các phụ thuộc hàm (functional dependencies), ... Để khắc phục hạn chế của thuật toán Apriori, Han J. và cộng sự [7, 8] tại Trường Đại học Simon Fraser (Canada) đã đề xuất thuật toán FP-growth. Thuật toán FP-growth khai phá TMTX được xây dựng dựa trên những kĩ thuật cơ bản sau: (1) Nén toàn bộ CSDL giao tác lên một cấu trúc cây, gọi là cây FP-tree, nhờ đó giảm chi phí cho số lần duyệt CSDL giao tác trong quá trình khai phá. (2) Dùng phương pháp chia để trị (devide- 285 and-conquer), bằng cách trong quá trình xây dựng và khai phá dữ liệu được chia làm thành các bài toán nhỏ hơn, theo nghĩa xây dựng các cây FP-tree có điều kiện và khai phá các TMTX trên các cây FP-tree có điều kiện đã được tạo ra. Do vậy, quá trình khai phá cây được phát triển dần các mẫu mà không sinh ra nhiều các tập mục ứng viên và nó sẽ làm giảm khối lượng thời gian tính toán. Quá trình khai phá TMTX được thực hiện theo hai pha: Pha xây dựng cây FP-tree và pha khai phá cây FP-tree bằng thuật toán FP-growth. Mặc dù thuật toán FP-growth có những ưu điểm (về tổ chức dữ liệu, bộ nhớ, thời gian tính toán) hơn thuật toán Apriori nhưng đối với CSDL giao tác lớn cần khai phá sẽ không hiệu quả. Để có thể áp dụng thuật toán FP-growth trên các CSDL kích thước lớn, trong bài viết này chúng tôi trình bày một phương pháp tiếp cận xấp xỉ. Thay vì tìm tập TMTX trong CSDL cần khai phá, ta sẽ tìm tập chứa hầu hết các tập mục từ CSDL mẫu đại diện. Độ hiệu quả của việc khai phá thông qua lấy mẫu sẽ càng cao khi kích thước của CSDL ban đầu càng lớn, bởi vì cỡ mẫu n cần lấy tăng chậm so với cỡ tổng thể. Nội dung tiếp theo của bài viết là như sau: Mục 2 giới thiệu về mô hình bài toán và thuật toán FP-Growth khai phá TMTX trong CSDL giao tác; Mục 3 trình bày phương pháp tiếp cận xấp xỉ: khai phá TMTX thông qua khai phá mẫu đại diện và cuối cùng là kết luận. 2. Khai phá tập mục thường xuyên trong csdl giao tác và thuật toán fp-growth 2.1. Bài toán khai phá tập mục thường xuyên trong CSDL giao tác [5, 6] Định nghĩa 1. Cho I= {i , i , … , i } là tập các phần tử. Mỗi phần tử trong I được gọi là một mục (item). Một tập con X ⊆ Iđược gọi là một tập mục (itemset). Số phần tử trong X kí hiệu là Card(X). Nếu Card(X) = k, (k ∈ Z) thì X được gọi là k-tập mục. Nếu Card(X)=1 thì X là 1-tập mục hay còn được gọi là mục đơn. Để đơn giản, thay vì viết k-tập mục {i , i , … , i } đôi khi ta viết i i … i . Chẳng hạn, tập mục {a, b, c} được viết ngắn gọn là abc. Định nghĩa 2. Một giao tác (transaction) là một bộ T = 〈TID , X〉, với TID là định danh giao tác (transaction identifier) duy nhất và X ⊆ Ilà một tập mục. Giao tác T gọi là chứa tập mục Y nếu Y ⊆ T. Định nghĩa 3. CSDL giao tác (transaction database) là một tập các giao tác TDB = {T , T , … , T }. Biểu diễn CSDL giao tác ngang : CSDL là một tập các giao tác. Trong đó, mỗi giao tác bao gồm một định danh (thứ tự) TID và một danh sách các mục. Ví dụ. Trong Bảng 1 dưới đây là biểu diễn ngang của CSDL giao tác. Bảng 1. Biểu diễn ngang của CSDL giao tác TID Tập các mục T1 abcdef T2 bcefh T3 acdefgh ...