Một thuật toán tìm tập thường xuyên trên cơ sở dữ liệu giao tác có trọng số

Bài viết Một thuật toán tìm tập thường xuyên trên cơ sở dữ liệu giao tác có trọng số đề xuất thuật toán CABOWD, nhằm rút ngắn thời gian tìm các tập thường xuyên theo hướng phân nhỏ và rút gọn kích thước dữ liệu.
Nội dung trích xuất từ tài liệu:
Một thuật toán tìm tập thường xuyên trên cơ sở dữ liệu giao tác có trọng số Nguyễn Hữu Trọng, Lê Đức An, Trần Xuân Việt, Nguyễn Anh Hào MỘT THUẬT TOÁN TÌM TẬP THƯỜNG XUYÊN TRÊN CƠ SỞ DỮ LIỆU GIAO TÁC CÓ TRỌNG SỐ A NEW METHOD TO MINE FREQUENT ITEMSETS ON TRANSACTION DATA WEIGHTED Nguyễn Hữu Trọng1 , Lê Đức An2 , Trần Xuân Việt2 , Nguyễn Anh Hào2 1 Trường Đại học Nha Trang; Email: trongnhntu@gmail.com 2 Trường Đại học Quy Nhơn; Email: an.leduc@gmail.com, cntranxuanviet@yahoo.com, Hao.nguyenvan1979@gmail.com Tóm tắt – Tìm tất cả các tập mục dữ liệu thường xuyên là công việc Abstract – Find all of the frequent itemsets are basic work in data cơ bản trong khai phá dữ liệu. Trong hơn 20 năm từ ngày Agrawal mining. For more than 20 years from the date of Agrawal and và các cộng sự đưa ra thuật toán AIS, các nhà nghiên cứu đã đề colleagues provide AIS algorithm, the researchers have proposed xuất nhiều thuật toán cải tiến về tốc độ để phát hiện nhanh những many improved algorithms for detecting fast pace of the frequent tập mục dữ liệu thường xuyên. Những thuật toán này, một hướng itemsets. These algorithms, an improved focus on navigating the tập trung vào cải tiến cách duyệt qua tập dữ liệu và cách tính độ hỗ data sets and how to calculate the support of each candidate item trợ của từng tập mục dữ liệu ứng viên, một hướng khác, tập trung set, a different direction, focusing on the reduced size and split vào việc rút gọn kích thước và phân nhỏ cơ sở dữ liệu được xử lý. the data into several clusters. In this paper, we propose algorithms Trong báo cáo này, chúng tôi đề xuất thuật toán CABOWD, nhằm CABOWD (clustering algorithm based on weighted data), in order to rút ngắn thời gian tìm các tập thường xuyên theo hướng phân nhỏ shorten the time by the way to split the data and reduce data size. và rút gọn kích thước dữ liệu. Từ khóa – cơ sở dữ liệu giao tác, luật kết hợp; tập thường xuyên; Key words – database transactions; association rules; frequent phân cụm; trọng số. practice; clustering; weight. 1. Đặt vấn đề AIS, năm 1994 Agrawal và Srikant đưa ra thuật toán Apriori Cho I = {x1 , x2 , . . . , xn } là tập hợp các mục dữ liệu. [3], thuật toán đặt nền móng cho việc tìm tất cả các tập Một tập con t={xi1 , xi2 , . . . , xik } ⊆ I gọi là một giao tác thường xuyên và luật kết hợp. Hạn chế lớn nhất của thuật trên I. Một tập hợp gồm m giao tác T = {t1 , t2 , . . . , tm } gọi toán Aprori là duyệt qua cơ sở dữ liệu quá nhiều lần, đặc biệt là một cơ sở dữ liệu (CSDL) giao tác trên I. Mỗi tập hợp X với dữ liệu lớn, lưu trữ ở bộ nhớ ngoài thì thời gian duyệt ⊆ I gọi là tập mục dữ liệu (itemset), mỗi tập con S ⊆ T gọi quá lớn, việc tìm tất cả tập thường xuyên không khả thi. là một giao tác. Độ hỗ trợ (support) của một tập mục dữ liệu Thuật toán FP_Growth do nhóm nghiên cứu của Jiawei X, ký hiệu Supp(X) là số các giao tác trong T chứa X. Để Han trường đại học Illinois Hoa Kỳ đề xướng năm 2000 [4] đơn giản, quy ước dùng Supp(xi ) thay cho Supp({xi }) khi và trình bày đầy đủ trong [5]. Hạn chế của các thuật toán tập chỉ có một mục dữ liệu. Cho S0 là một số nguyên, ta nói FP_Growth là với dữ liệu lớn, việc đệ quy để tìm tất cả các X là tập mục dữ liệu thường xuyên (frequent itemset) theo tập thường xuyên của FP_Growth tốn một thời gian khá lớn. ngưỡng S0 nếu Supp(X) ≥ S0 . Một biểu thức X1 → X2 , Khi dữ liệu lớn, việc đệ quy có thể tràn bộ nhớ, không thể với X1 , X2 ⊆ I và X1 ∩ X2 = φ được gọi là một luật kết thực hiện được. Nhiều cải tiến FP_Growth đã được tổng hợp hợp (Association rule) trên T. Độ hỗ trợ của luật kết hợp trong [9]. X1 → X2 , ký hiệu Supp(X1 → X2 ) = Supp(X1 ∪ X2 ) = Supp(X1 X2 ). Luật kết hợp f:X1 → X2 trên T là luật thường 3. Phân cụm dữ liệu xuyên theo ngưỡng S0 nếu Supp(X1 → X2 ) ≥ S0 . Độ Phân cụm (Data clustering) hay gom cụm là quá trình tin cậy (Confidence) của luật X1 → X2 , là tỷ số: p = phân chia các đối tượng trong CSDL T vào các cụm sao cho Conf(X1 → X2 ) = Supp(X1 → X2 )/Supp(X1 ), ký hiệu các đối tượng có độ tương tự giống nhau được gom vào một Conf(X1 → X2 ). Với C0 ∈ (0, 1] ta nói f:X1 → X2 là luật cụm. Như vậy, mỗi đối tượng trong T thuộc về một và chỉ tin cậy (Confident rule) theo ngưỡng S0 và C0 nếu f là luật một cụm. Việc xử lý thay vì làm trên toàn cơ sở dữ liệu có thường xuyên theo ngưỡng S0 và Conf(X1 → X2 ) ≥ C0 . thể thu lại trên từng cụm. Các kết quả tiêu biểu của kỹ thuật Bài toán tìm luật kết hợp trên một CSDL được chia phân cụm và nén dữ liệu được trình bày trong [6][7][8] và thành hai bài toán nhỏ. Bài toán thứ nhất là tìm tất cả các [11][12][13][14]. tập mục dữ liệu thường xuyên theo ngưỡng tối thiểu cho trước. Bài toán thứ hai là tìm ra những luật kết hợp từ những Thời gian tìm tập ứng viên trong thuật toán Apriori tập mục dữ liệu thường xuyên thỏa độ tin cậy tối thiểu cho là không đáng kể khi ta có một giải thuật tốt. Trong báo trước. Bài toán thứ hai là đơn giản, hầu hết các nghiên cứu cáo này, chúng tôi đề xuất thuật toán CABOWD ...