Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Thuật toán hiệu quả để khai thác các tập hợp mục trung bình có giá trị cao trong cơ sở dữ liệu giao dịch gia tăng
Tóm tắt
Trong bài báo này, chúng tôi trình bày một thuật toán mới để khai thác hiệu quả các tập hợp mục có giá trị trung bình cao (HAUIs) từ các cơ sở dữ liệu gia tăng, trong đó thể tích của chúng có thể được mở rộng một cách động. Các thuật toán trước đây có điểm kém hiệu quả là chúng phải quét một cơ sở dữ liệu nhất định nhiều lần để tạo ra các tập hợp mục ứng cử viên và xác định các tập hợp mục hợp lệ theo từng cấp. Lý do là chúng tuân theo khung cơ bản của một phương pháp tương tự Apriori. Nhược điểm này có thể gây ra các vấn đề nghiêm trọng trong việc xử lý các cơ sở dữ liệu gia tăng vì việc quét một cơ sở dữ liệu trở thành một nhiệm vụ khó khăn hơn khi kích thước cơ sở dữ liệu tăng lên. Ngược lại, thuật toán được đề xuất trong bài báo này xây dựng một cấu trúc cây gọn gàng, duy trì tất cả thông tin cần thiết nhằm tránh việc quét cơ sở dữ liệu quá mức trong quá trình khai thác của nó. Các thuật toán trước đây chịu khó khăn từ việc sản sinh ra một lượng lớn các tập hợp mục ứng cử viên không cần thiết ở mỗi cấp, đi kèm với cách phát sinh ứng cử viên kết hợp naiv trên cơ sở một phương pháp tương tự Apriori, mà tạo ra các tập hợp mục ứng cử viên có chiều dài (k+1) bằng cách đơn giản là kết hợp các tập hợp mục có chiều dài k. Mặt khác, thuật toán của chúng tôi sử dụng cách tiếp cận phát triển mẫu, cho phép thuật toán tạo ra một tập hợp chỉ chứa các tập hợp mục ứng cử viên cần thiết. Để thuật toán của chúng tôi liên tục duy trì tính gọn gàng của cấu trúc cây của nó trong suốt quá trình khai thác gia tăng, một kỹ thuật tái cấu trúc được sử dụng. Trong việc đánh giá hiệu suất, chúng tôi cho thấy thuật toán của chúng tôi nhanh hơn và tiêu tốn ít không gian bộ nhớ hơn so với các đối thủ.
Từ khóa
#khai thác dữ liệu #tập hợp mục #cơ sở dữ liệu gia tăng #thuật toán Apriori #tối ưu hóa bộ nhớTài liệu tham khảo
Agrawal R, Srikant R (1994) Fast algorithms for mining association rules in large databases. In: 20th international conference on very large data bases, pp 487–499
Ahmed CF, Tanbeer SK, Jeong B, Lee Y (2009) Efficient tree structures for high utility pattern mining in incremental databases. IEEE Trans Knowl Data Eng 21(12):1708–1721
Bennett KP, Mangasarian OL (1992) Robust linear programming discrimination of two linearly inseparable sets. Optim Methods Software 1:23–34
Cheung DW, Han J, Ng VT, Wong CY (1996) Maintenance of discovered association rules in large databases: an incremental updating approach. In: The 12th IEEE international conference on data engineering, pp 106–114
Duong Q, Liao B, Fournier-Viger P, Dam T (2016) An efficient algorithm for mining the top-k high utility itemsets, using novel threshold raising and pruning strategies. Knowl-Based Syst 104:106–122
Fournier-Viger P, Wu C, Zida S, Tseng V (2014) FHM: faster high-utility itemset mining using estimated utility co-occurrence pruning. In: ISMIS, pp 83–92
Fan Y, Ye Y, Chen L (2016) Malicious sequential pattern mining for automatic malware detection. Expert Syst Appl 52:16–25
Han J, Pei J, Yin Y (2000) Mining frequent patterns without candidate generation. In: Proceedings of the 2000 ACM SIGMOD international conference on management of data, pp 1–12
Hong T, Lee C, Wang S (2011) Effective utility mining with the measure of average utility. Expert Syst Appl 38(7):8259–8265
Hong T, Lee C, Wang S (2009) An incremental mining algorithm for high average-utility itemsets. In: ISPAN 2009, pp 421–425
Koh J, Shieh S (2003) An efficient approach for maintaining association rules based on adjusting FP-tree structures. In: DASFAA, pp 417–424
Krishnamoorthy S (2015) Pruning strategies for mining high utility itemsets. Expert Syst Appl 42(5):2371–2381
Kim D, Yun U (2016) Efficient mining of high utility pattern with considering of rarity and length. Appl Intell 45(1):152–173
Kim D, Yun U (2016) Mining high utility itemsets based on the time decaying model. Intell Data Anal 20 (5):1157–1180
Lan G, Hong T, Tseng V (2012) A projection-based approach for discovering high average-utility itemsets. J Inf Sci Eng 28:193–209
Lan G, Hong T, Tseng V (2012) Efficiently mining high average-utility itemsets with an improved upper-bound strategy. Int J Inf Technol Decis Making 11(5):1009–1030
Le T, Vo B (2015) An N-list-based algorithm for mining frequent closed patterns. Expert Syst Appl 42 (19):6648–6657
Lee G, Yun U, Ryu K (2014) Sliding window based weighted maximal frequent pattern mining over data streamss. Expert Syst Appl 41(2):694–708
Lee G, Yun U, Ryang H (2015) An uncertainty-based approach: frequent itemset mining from uncertain data with different item importance. Knowl-Based Syst 90:239–256
Lee G, Yun U, Ryang H, Kim D (2016) Approximate maximal frequent pattern mining with weight conditions and error tolerance. Int J Pattern Recognit Artif Intell 30(6):1–42
Lee G, Yun U, Ryang H, Kim D (2016) Erasable itemset mining over incremental databases with weight conditions. Eng Appl Artif Intell 52:213–234
Lin J, Gan W, Hong T, Tseng V (2015) Efficient algorithms for mining up-to-date high utility patterns. Adv Eng Inform 29(3):648–661
Lin J, Gan W, Fournier-Viger P, Hong T, Tseng V (2016) Efficient algorithms for mining high-utility itemsets in uncertain databases. Knowl-Based Syst 96:171–187
Liu Y, Liao W, Choudhary A (2005) A two-phase algorithm for fast discovery of high utility itemsets. In: Advances in knowledge discovery and data mining, pp 689–695
Liu M, Qu J (2012) Mining high utility itemsets without candidate generation. In: Proceedings of the 21st ACM international conference on Information and knowledge management, pp 55–64
Lu T, Vo B, Nguyen HT, Hong T (2014) A new method for mining high average utility itemsets. In: Computer Information Systems and Industrial Management, pp 33–42
Pisharath J, Liu Y, Ozisikyilmaz B, Narayanan R, Liao WK, Choudhary A Memik G NU-MineBench version 2.0 dataset and technical report, http://cucis.ece.northwestern.edu/projects/DMS/
Ryang H, Yun U (2015) Top-K high utility pattern mining with effective threshold raising strategies. Knowl-Based Syst 76:109–126
Ryang H, Yun U, Ryu K (2016) Fast algorithm for high utility pattern mining with sum of item quantities. Intell Data Anal 20(2):395–415
Tseng V, Shie BE, Wu CW, Yu PS (2013) Efficient algorithms for mining high utility itemsets from transactional databases. IEEE Trans Knowl Data Eng 25(8):1772–1786
Tseng V, Wu C, Fournier-Viger P, Yu PS (2016) Efficient algorithms for mining top-K high utility itemsets. IEEE Trans Knowl Data Eng 28(1):54–67
Tanbeer SK, Ahmed CF, Jeong B, Lee Y (2009) Efficient single-pass frequent pattern mining using a prefix-tree. Inf Sci 179(5):559–583
Tsai C, Lai B (2015) A location-item-time sequential pattern mining algorithm for route recommendation. Knowl-Based Syst 73:97–110
Yun U, Ryang H (2015) Incremental high utility pattern mining with static and dynamic databases. Appl Intell 42(2):323–352
Yun U, Ryang H, Ryu K (2014) High utility itemset mining with techniques for reducing overestimated utilities and pruning candidates. Expert Syst Appl 41(8):3861–3878
Yun U, Kim D, Ryang H, Lee G, Lee K (2016) Mining recent high average utility patterns based on sliding window from stream data. J Intell Fuzzy Syst 30(6):3605–3617
Yun U, Lee G (2016) Incremental mining of weighted maximal frequent itemsets from dynamic databases. Expert Syst Appl 54:304–327
Yun U, Lee G (2016) Sliding window based weighted erasable stream pattern mining for stream data applications. Futur Gener Comput Syst 59:1–20
Yun U, Lee G, Kim C (2016) The smallest valid extension-based efficient, rare graph pattern mining, considering length-decreasing support constraints and symmetry characteristics of graphs. Symmetry 8(5):1–26
Yun U, Pyun G, Yoon E (2015) Efficient mining of robust closed weighted sequential patterns without information loss. Int J Artif Intell Tools 24(1):1–28
Yun U, Lee G, Lee K (2016) Efficient representative pattern mining based on weight and maximality conditions. Expert Syst 33(5):439–462
Zhang J, Wang Y, Yang D (2015) CCSpan: mining closed contiguous sequential patterns. Knowl-Based Syst 89:1–13
Zhang X, Deng Z (2015) Mining summarization of high utility itemsets. Knowl-Based Syst 84:67–77