Luận văn ThS: Nghiên cứu phương án tỉa ứng viên trong khai thác tập hữu ích cao

(8)
174 lượt xem
Share

Luận văn Nghiên cứu phương án tỉa ứng viên trong khai thác tập hữu ích cao nghiên cứu các thuật toán về khai thác tập hữu ích cao, tập trung tìm hiểu các phương pháp thực nghiệm từ các bài báo tham khảo; tìm hiểu và đánh giá các thuật toán khai thác tập hữu ích cao từ đó phát triển thuật toán mới hiệu quả hơn.

Mục lục nội dung

Luận văn ThS: Nghiên cứu phương án tỉa ứng viên trong khai thác tập hữu ích cao

1. Mở đầu

1.1 Lí do chọn đề tài

Đối với khai thác tập phổ biến, các thuật toán sinh ứng viên áp dụng tính chất bao đóng giảm (downward closure property), tăng khả năng tỉa các tập ứng viên thừa. Cụ thể, nếu có một tập không phổ biến m thì thuật toán không xét các tập ứng viên chứa tập m, giả sử bộ dữ liệu chứa n phần tử và tập không phổ biến m chứa k phần tử, thuật toán sẽ không xét 2(n-k) - 2 tập có chứa m.

1.2 Mục tiêu nghiên cứu

Từ khi bài toán được Yao và các đổng sự phát biểu vào năm 2004 [4] đến nay, đã có nhiều thuật toán khai thác tập hữu ích cao được phát triển nhằm nâng cao hiệu quả khai thác: UMining (2004), UMining-H (2006), Two-Phase (2005), IHUP (2009), TWU-Mining (2009), UP-Growth (2010), DTWU-Mining (2011), EFIM (2015), ... và một số hướng phát triển khác của tập hữu ích cao, điển hình như khai thác tập đóng có CHUD (2011), AprioriCH, AprioriHC-D (2015); khai thác Top-k HUI có TKU (2012), TKO (2016); khai thác HUI trên luồng dữ liệu có THUI-Mine (2008), GUIDE (2012), hay khai thác HUI trên dữ liệu không chắc chắn.

2. Nội dung

2.1 Cơ sở lí thuyết

Giới thiệu bài toán khai thác tập mục hữu ích cao

  • Định nghĩa bài toán
  • Phát biểu bài toán

Các nghiên cứu liên quan

Các thuật toán khai thác tập hữu ích cao

  • Thuật toán Two - Phase
  • Thuật toán khai thác tập mục hữu ích cao TWU - Mining
  • Thuật toán EFIM

Kết luận

2.2 Thuật toán EFIM cải tiến (iEFIM)

Thuật toán iEFIM

Ví dụ minh họa thuật toán iEFIM

Hiệu quả P-set của iEFIM

Kết luận

2.3 Kết quả thực nghiệm

Môi trường và dữ liệu thực nghiệm

So sánh về số lượng giao dịch

So sánh về thời gian

3. Kết luận

Trên cơ sở hiệu quả thuật toán TWU - Mining với Two - Phase và EFIM, luận văn đã đề xuất giải pháp chiếu ngược P - set và thuật toán cải tiến gọi là iEFIM (improved EFIM) thông qua giải pháp P - set đã giảm được đáng kể số lượng giao dịch tham gia quá trình khai thác tập hữu ích cao nhờ đó giảm bớt được thời gian thực hiện thuật toán khai thác, đặc biệt là trên các cơ sở dữ liệu thưa. Thuật toán cải tiến đã được cài đặt và thử nghiệm thành công trên một số cơ sở dữ liệu chuẩn lớn được cộng đồng nghiên cứu về HUI sử dụng, như cơ sở dữ liệu Accidents, BMS - POS, Chess, Foodmart, Kosarak, Retail, T10I4D100K, T40I10D100K. Tương ứng với mỗi cơ sở dữ liệu là sự so sánh số giao dịch tham gia thuật toán và thời gian thực hiện của thuật toán gốc EFIM và iEFIM.

4. Tài liệu tham khảo

R. Agrawal, T. Imielinski and A. N. Swami , "Mining association rules between sets of items in large databases," in Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington D.C., pp. 207 – 216, 1993

R. Agrawal and R. Srikant, "Fast algorithms for mining association rules in large databases," in Proc. Int’l Conf. Very Large Data Bases, pp. 487-499, 1994

M. Liu and J. Qu, "High utility itemsets without candidate generation," in 21st ACM International Conference on Information and Knowledge Management, pp. 55-64, 2012

H. Yao, H. J. Hamilton and C. J. Butz, "A foundational approach to mining itemset utilities from databases," in In Proc. SIAM Int’l Conf. Data Mining, 2004....

--- Nhấn nút TẢI VỀ hoặc XEM ONLINE để tham khảo đầy đủ nội dung Luận văn trên ---

(8)
174 lượt xem
Share
Ngày:05/09/2020 Chia sẻ bởi:Minh Ngoan
TẢI VỀ XEM ONLINE

CÓ THỂ BẠN QUAN TÂM