Checking Sets of Pure Evolving Association Rules

• Autorzy: Combi Carlo , Rizzi Romeo , Sala Pietro

Identyfikatory

DOI

10.3233/FI-2021-2008

• Języki publikacji: EN

Abstrakty

EN

Extracting association rules from large datasets has been widely studied in many variants in the last two decades; they allow to extract relations between values that occur more “often” in a database. With temporal association rules the concept has been declined to temporal databases. In this context the “most frequent” patterns of evolution of one or more attribute values are extracted. In the temporal setting, especially where the interference betweeen temporal patterns cannot be neglected (e.g., in medical domains), there may be the case that we are looking for a set of temporal association rules for which a “significant” portion of the original database represents a consistent model for all of them. In this work, we introduce a simple and intuitive form for temporal association rules, called pure evolving association rules (PE-ARs for short), and we study the complexity of checking a set of PE-ARs over an instance of a temporal relation under approximation (i.e., a percentage of tuples that may be deleted from the original relation). As a by-product of our study we address the complexity class for a general problem on Directed Acyclic Graphs which is theoretically interesting per se.

Słowa kluczowe

EN

data mining; association rules; data complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 178, nr 4
• Strony: 283--313
• Opis fizyczny: Bibliogr. 45 poz., rys., tab.

Twórcy

autor

Combi Carlo

• Department of Computer Science, University of Verona, Strada Le Grazie 15, 37134 Verona, Italy

autor

Rizzi Romeo

• Department of Computer Science, University of Verona, Strada Le Grazie 15, 37134 Verona, Italy

autor

Sala Pietro

• Department of Computer Science, University of Verona, Strada Le Grazie 15, 37134 Verona, Italy

Bibliografia

• [1] Sala P, Combi C, Cuccato M, Galvani A, Sabaini A. A Framework for Mining Evolution Rules and Its Application to the Clinical Domain. In: 2015 International Conference on Healthcare Informatics, (ICHI) 2015, Dallas, TX, USA, October 21-23, 2015. 2015 pp. 293-302. doi:10.1109/ICHI.2015.42. URL http://dx.doi.org/10.1109/ICHI.2015.42.
• [2] Liu WY, Song N, Yao H. Temporal functional dependencies and temporal nodes bayesian networks. The Computer Journal, 2005. 48(1):30-41. doi:10.1093/comjnl/bxh066.
• [3] Wijsen J. Temporal FDs on Complex Objects. ACM Transactions on Database Systems (TODS), 1999. 24(1):127-176. doi:10.1145/310701.310715.
• [4] Agrawal R, Srikant R. Mining sequential patterns. In: Proceedings of the Eleventh International Conference on Data Engineering, 1995. IEEE, 1995 pp. 3-14.
• [5] Concaro S, Sacchi L, Cerra C, Fratino P, Bellazzi R. Mining Healthcare Data with Temporal Association Rules: Improvements and Assessment for a Practical Use. In: Combi C, Shahar Y, Abu-Hanna A (eds.), Artificial Intelligence in Medicine, 12th Conference on Artificial Intelligence in Medicine, AIME 2009, Verona, Italy, July 18-22, 2009. Proceedings, volume 5651 of Lecture Notes in Computer Science. 2009 pp. 16-25. doi:10.1007/978-3-642-02976-9\_3.
• [6] Zaki MJ. SPADE: An Efficient Algorithm for Mining Frequent Sequences. Machine Learning, 2001. 42(1/2):31-60. doi:10.1023/A:1007652502315.
• [7] Zhao Q, Bhowmick SS. Association rule mining: A survey. Nanyang Technological University, Singapore, 2003.
• [8] Sala P. An Algorithm for Verifying Approximate Pure Evolving Functional Dependencies. In: Felli P, Montali M (eds.), Proceedings of the 33rd Italian Conference on Computational Logic, Bolzano, Italy, September 20-22, 2018, volume 2214 of CEUR Workshop Proceedings. CEUR-WS.org, 2018 pp. 2-16. URL http://ceur-ws.org/Vol-2214/paper1.pdf.
• [9] Agrawal R, Imielinski T, Swami AN. Mining Association Rules between Sets of Items in Large Databases. In: Buneman P, Jajodia S (eds.), Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, DC, USA, May 26-28, 1993. ACM Press, 1993 pp. 207-216. doi:10.1145/170035.170072.
• [10] Singh S, Singh P, Garg R, Mishra P. Mining Association Rules in Various Computing Environments: A Survey. International Journal of Applied Engineering Research, 2016. 11(8):5629-5640. URL http://www.ripublication.com/ijaer16/ijaerv11n8_47.pdf.
• [11] Sohail MN, Jiadong R, Uba MM, Irshad M. A Comprehensive Looks at Data Mining Techniques Contributing to Medical Data Growth: A Survey of Researcher Reviews. In: Patnaik S, Jain V (eds.), Recent Developments in Intelligent Computing, Communication and Devices. Springer Singapore, Singapore, 2019 pp. 21-26. ISBN:978-981-10-8944-2. doi:10.1007/978-981-10-8944-2_3.
• [12] Zhang Y, Ren S, Liu Y, Si S. A big data analytics architecture for cleaner manufacturing and maintenance processes of complex products. Journal of Cleaner Production, 2017. 142:626-641. doi:https://doi.org/10.1016/j.jclepro.2016.07.123. Special Volume on Improving natural resource management and human health to ensure sustainable societal development based upon insights gained from working within Big Data Environments, URL http://www.sciencedirect.com/science/article/pii/S0959652616310198.
• [13] Wang F, Li W, Wang S, Johnson CR. Association rules-based multivariate analysis and visualization of spatiotemporal climate data. ISPRS International Journal of Geo-Information, 2018. 7(7):266. doi:10.3390/ijgi7070266.
• [14] Merceron A, Yacef K. Interestingness measures for association rules in educational data. In: Educational Data Mining, 2008 pp. 57-273.
• [15] Abdel-Basset M, Mohamed M, Smarandache F, Chang V. Neutrosophic association rule mining algorithm for big data analysis. Symmetry, 2018. 10(4):106. doi:10.3390/sym10040106.
• [16] Bechini A, Marcelloni F, Segatori A. A MapReduce solution for associative classification of big data. Information Sciences, 2016. 332:33-55. doi:10.1016/j.ins.2015.10.041.
• [17] Agrawal R, Srikant R, et al. Fast algorithms for mining association rules. In: Proceedings of the 20th international conference on Very Large Data Bases, VLDB, volume 1215. 1994 pp. 487-499.
• [18] Yuan X. An improved Apriori algorithm for mining association rules. In: AIP conference proceedings, volume 1820. AIP Publishing LLC, 2017 p. 080005. doi:10.1063/1.4977361.
• [19] Han J, Pei J, Yin Y. Mining frequent patterns without candidate generation. ACM Sigmod Record, 2000. 29(2):1-12. doi:10.1145/342009.335372.
• [20] Zhang M, He C. Survey on association rules mining algorithms. In: Advancing Computing, Communication, Control and Management, pp. 111-118. Springer, 2010. doi:10.1007/978-3-642-05173-9_15.
• [21] Ghafari SM, Tjortjis C. A survey on association rules mining using heuristics. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2019. 9(4):e1307. doi:10.1002/widm.1307.
• [22] Combi C, Sabaini A. Extraction, Analysis, and Visualization of Temporal Association Rules from Interval-Based Clinical Data. In: Artificial Intelligence in Medicine - 14th Conference on Artificial Intelligence in Medicine, AIME 2013, Murcia, Spain, May 29 - June 1, 2013. Proceedings. 2013 pp. 238-247. doi:10.1007/978-3-642-38326-7_35.
• [23] Silveira C, Cecatto J, Santos M, Ribeiro M. Thematic Spatiotemporal Association Rules to Track the Evolving of Visual Features and Their Meaning in Satellite Image Time Series. In: Information Technology-New Generations, pp. 317-323. Springer, 2018. doi:10.1007/978-3-319-77028-4_43.
• [24] Martn D, Martnez-Ballesteros M, Garca-Gil D, Alcal-Fdez J, Herrera F, Riquelme-Santos J. MRQAR: A generic MapReduce framework to discover quantitative association rules in big data problems. Knowledge-Based Systems, 2018. 153:176-192. doi:https://doi.org/10.1016/j.knosys.2018.04.037.
• [25] Tan PN, Kumar V, Srivastava J. Selecting the right interestingness measure for association patterns. In: Proceedings of the eighth ACM SIGKDD international conference on Knowledge Discovery and Data Mining. 2002 pp. 32-41. doi:10.1145/775047.775053.
• [26] Lenca P, Meyer P, Vaillant B, Lallich S. On selecting interestingness measures for association rules: User oriented description and multiple criteria decision aid. European Journal of Operational Research, 2008. 184(2):610-626. doi:10.1016/j.ejor.2006.10.059.
• [27] Shaikh MR, McNicholas PD, Antonie ML, Murphy TB. Standardizing interestingness measures for association rules. Statistical Analysis and Data Mining: The ASA Data Science Journal, 2018. 11(6):282-295. doi:10.1002/sam.11394.
• [28] Dasgupta D, Roy S, Roy SS, Chakraborty A. Survey and analysis of mining requirements in spatiotemporal database. Computer, Communication and Electrical Technology, CRC Press, 2017. pp. 91-95.
• [29] Wang L, Meng J, Xu P, Peng K. Mining temporal association rules with frequent itemsets tree. Applied Soft Computing, 2018. 62:817-829. doi:https://doi.org/10.1016/j.asoc.2017.09.013.
• [30] Wang L, Meng J, Xu P, Peng K. Mining temporal association rules with frequent itemsets tree. Applied Soft Computing, 2018. 62:817-829. doi:10.1016/j.asoc.2017.09.013.
• [31] Orphanou K, Dagliati A, Sacchi L, Stassopoulou A, Keravnou E, Bellazzi R. Combining naive bayes classifiers with temporal association rules for coronary heart disease diagnosis. In: 2016 IEEE International Conference on Healthcare Informatics (ICHI). IEEE, 2016 pp. 81-92. doi:10.1109/ICHI.2016.15.
• [32] Mannila H, Toivonen H, Verkamo AI. Discovery of frequent episodes in event sequences. Data Mining and Knowledge Discovery, 1997. 1(3):259-289. doi:10.1023/A:1009748302351.
• [33] Sacchi L, Larizza C, Combi C, Bellazzi R. Data mining with Temporal Abstractions: learning rules from time series. Data Mining and Knowledge Discovery, 2007. 15(2):217-247. doi:10.1007/s10618-007-0077-7.
• [34] Ale JM, Rossi GH. An Approach to Discovering Temporal Association Rules. In: Proceedings of the 2000 ACM Symposium on Applied Computing - Volume 1, SAC ’00. ACM, New York, NY, USA, 2000 pp. 294-300.
• [35] Chen X, Petrounias I. An Integrated Query and Mining System for Temporal Association Rules. In: Proceedings of the Second International Conference on Data Warehousing and Knowledge Discovery, DaWaK 2000. Springer-Verlag, London, UK, UK, 2000 pp. 327-336. doi:10.1007/3-540-44466-1_33.
• [36] Wang W, Yang J, Muntz R. TAR: temporal association rules on evolving numerical attributes. In: Data Engineering, 2001. Proceedings. 17th International Conference on. 2001 pp. 283-292. doi:10.1109/ICDE.2001.914839.
• [37] Chen L, Bhowmick S, Li J. Mining Temporal Indirect Associations. In: Ng WK, Kitsuregawa M, Li J, Chang K (eds.), Advances in Knowledge Discovery and Data Mining, volume 3918 of Lecture Notes in Computer Science, pp. 425-434. Springer Berlin Heidelberg, 2006. ISBN:978-3-540-33206-0.
• [38] Banaee H, Loutfi A. Data-Driven Rule Mining and Representation of Temporal Patterns in Physiological Sensor Data. IEEE J. Biomedical and Health Informatics, 2015. 19(5):1557-1566. doi:10.1109/JBHI.2015.2438645.
• [39] Ichise R, Numao M. First-Order Rule Mining by Using Graphs Created from Temporal Medical Data. In: Tsumoto S, Yamaguchi T, Numao M, Motoda H (eds.), Active Mining, Second International Workshop, AM 2003, Maebashi, Japan, October 28, 2003, Revised Selected Papers, volume 3430 of Lecture Notes in Computer Science. Springer. ISBN 3-540-26157-5, 2003 pp. 112-125. doi:10.1007/11423270_7.
• [40] Radhakrishna V, Kumar P, Janaki V, Cheruvu A. A dissimilarity measure for mining similar temporal association patterns. IADIS International Journal on Computer Science and Information Systems, 2017. 12(1):126-142. ID:54075371.
• [41] Huhtala Y, Kärkkäinen J, Porkka P, Toivonen H. TANE: An efficient algorithm for discovering functional and approximate dependencies. The Computer Journal, 1999. 42(2):100-111. doi:10.1093/comjnl/42.2.100.
• [42] Greenlaw R, Petreschi R. Cubic Graphs. ACM Computing Surveys, 1995. 27(4):471-495. doi:10.1145/234782.234783.
• [43] Calamoneri T. Does Cubicity Help to Solve Problems. Ph.D. thesis, Department of Computer Science University of Rome La Sapienza, Rome, Italy, 1997.
• [44] Berman P, Karpinski M. On Some Tighter Inapproximability Results (Extended Abstract). In: Wiedermann J, van Emde Boas P, Nielsen M (eds.), Automata, Languages and Programming, volume 1644 of Lecture Notes in Computer Science, pp. 200-209. Springer Berlin Heidelberg, 1999. ISBN:978-3-540-66224-2.
• [45] Yannakakis M. Node-and Edge-Deletion NP-Complete Problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC 78. Association for Computing Machinery, New York, NY, USA, 1978 p. 253264. ISBN 9781450374378. doi:10.1145/800133.804355.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).