Dynamic Programming Approach for Construction of Association Rule Systems

• Autorzy: Alsolami F. , Amin T. , Chikalov I. , Moshkov M. , Zielosko B.

Identyfikatory

DOI

10.3233/FI-2016-1402

• Konferencja: International Workshop on CONCURRENCY, SPECIFICATION, and PROGRAMMING (CS&P 2015), (24; 28-30.09.2015, Rzeszów, Poland).
• Języki publikacji: EN

Abstrakty

EN

In the paper, an application of dynamic programming approach for optimization of association rules from the point of view of knowledge representation is considered. The association rule set is optimized in two stages, first for minimum cardinality and then for minimum length of rules. Experimental results present cardinality of the set of association rules constructed for information system and lower bound on minimum possible cardinality of rule set based on the information obtained during algorithm work as well as obtained results for length.

Słowa kluczowe

EN

association rules; decision rules; dynamic programming; set cover problem; rough sets

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 147, nr 2/3
• Strony: 159--171
• Opis fizyczny: Bibliogr. 26 poz., rys., tab.

Twórcy

autor

Alsolami F.

• Computer, Electrical and Mathematical Sciences and Engineering Division, King Abdullah University of Science and Technology, Thuwal 23955-6900, Saudi Arabia

autor

Amin T.

• Computer, Electrical and Mathematical Sciences and Engineering Division, King Abdullah University of Science and Technology, Thuwal 23955-6900, Saudi Arabia

autor

Chikalov I.

• Computer, Electrical and Mathematical Sciences and Engineering Division, King Abdullah University of Science and Technology, Thuwal 23955-6900, Saudi Arabia

autor

Moshkov M.

• Computer, Electrical and Mathematical Sciences and Engineering Division, King Abdullah University of Science and Technology, Thuwal 23955-6900, Saudi Arabia

autor

Zielosko B.

• Institute of Computer Science, University of Silesia, 39, Będzińska St., 41-200 Sosnowiec, Poland

Bibliografia

• [1] Agrawal R, Imieliński T, Swami A. Mining Association Rules Between Sets of Items in Large Databases. In: SIGMOD ’93. ACM; 1993;22(2):207–216. doi:10.1145/170035.170072.
• [2] Agrawal R, Srikant R. Fast Algorithms for Mining Association Rules in Large Databases. In: Bocca JB, Jarke M, Zaniolo C, editors. VLDB. Morgan Kaufmann; 1994. p. 487–499. ISBN: 1-55860-153-8. Available from: http://dl.acm.org/citation.cfm?id=645920.672836.
• [3] Toivonen H. Sampling Large Databases for Association Rules. In: Vijayaraman TM, Buchmann AP, Mohan C, Sarda NL, editors. VLDB. Morgan Kaufmann; 1996. p. 134–145. ISBN: 1-55860-382-4. Available from: http://dl.acm.org/citation.cfm?id=645922.673325.
• [4] Borgelt C. Simple Algorithms for Frequent Item Set Mining. In: Advances in Machine Learning II. vol. 263 of Studies in Computational Intelligence. Springer, Berlin Heidelberg; 2010. p. 351–369. doi:10.1007/978-3-642-05179-1_16.
• [5] Han J, Kamber M. Data Mining: Concepts and Techniques. Morgan Kaufmann Publishers Inc. 2000. ISBN: 1-55860-489-8.
• [6] Glass DH. Confirmation Measures of Association Rule Interestingness. Knowledge-Based Systems. 2013;44(0):65–77. Available from: http://dx.doi.org/10.1016/j.knosys.2013.01.021, doi:10.1016/j.knosys.2013.01.021.
• [7] Borgelt C, Kruse R. Induction of Association Rules: Apriori Implementation. In: 15th Conference on Computational Statistics (Compstat 2002, Berlin, Germany). Physica Verlag, Heidelberg; 2002. p. 395–400. doi:10.1007/978-3-642-57489-4_59.
• [8] Bonates TO, Hammer PL, Kogan A. Maximum Patterns in Datasets. Discrete Applied Mathematics. 2008;156(6):846–861. Available from: http://dx.doi.org/10.1016/j.dam.2007.06.004, doi:10.1016/j.dam.2007.06.004.
• [9] Moshkov M, Zielosko B. Combinatorial Machine Learning - A Rough Set Approach. Studies in Computational Intelligence 360, Springer 2011. Available from: http://dx.doi.org/10.1007/978-3-642-20995-6, doi:10.1007/978-3-642-20995-6.
• [10] Stefanowski J, Vanderpooten D. Induction of Decision Rules in Classification and Discovery-oriented Perspectives. Int J Intell Syst. 2001;16(1):13–27.
• [11] Moshkov M, Piliszczuk M, Zielosko B. Partial Covers, Reducts and Decision Rules in Rough Sets – Theory and Applications. Studies in Computational Intelligence 145. Heidelberg: Springer; 2008. Available from: http://dx.doi.org/10.1007/978-3-540-69029-0, doi:10.1007/978-3-540-69029-0.
• [12] Pawlak Z, Skowron A. Rudiments of Rough Sets. Information Sciences. 2007;177(1):3–27. doi:10.1016/j.ins.2006.06.003.
• [13] Nguyen HS, Ślęzak D. Approximate Reducts and Association Rules - Correspondence and Complexity Results. In: Proceedings of the 7th International Workshop on New Directions in Rough Sets, Data Mining, and Granular-Soft Computing, RSFDGrC ’99. LNCS 1711. Springer, 1999. p. 137–145. Available from: http://dl.acm.org/citation.cfm?id=646590.697625.
• [14] Wieczorek A, Słowiński R. Generating a Set of Association and Decision Rules with Statistically Representative Support and Anti-Support. Information Sciences. 2014;277: 56–70. doi:10.1016/j.ins.2014.02.003.
• [15] Agrawal R, Mannila H, Srikant R, Toivonen H, Verkamo AI. Fast Discovery of Association Rules. In: Fayyad UM, Piatetsky-Shapiro G, Smyth P, Uthurusamy R, editors. Advances in Knowledge Discovery and Data Mining. American Association for Artificial Intelligence; 1996. p. 307–328. Available from: http://dl.acm.org/citation.cfm?id=257938.257975.
• [16] Zaki MJ, Parthasarathy S, Ogihara M, Li W. New Algorithms for Fast Discovery of Association Rules. Rochester, NY, USA; 1997.
• [17] Moshkov MJ, Piliszczuk M, Zielosko B. Greedy Algorithm for Construction of Partial Association Rules. Fundamenta Informaticae. 2009;92(3):259–277. Available from: http://dx.doi.org/10.3233/FI-2009-0074, doi:10.3233/FI-2009-0074.
• [18] Moshkov MJ, Piliszczuk M, Zielosko B. On Construction of Partial Association Rules. In: Rough Sets and Knowledge Technology, 4th International Conference, RSKT 2009, Gold Coast, Australia, July 14-16, 2009. Proceedings. LNCS 5589 Springer; 2009 p. 176–183. Available from: http://dx.doi.org/10.1007/978-3-642-02962-2_22, doi:10.1007/978-3-642-02962-2_22.
• [19] Zielosko B. Greedy algorithm for construction of partial association rules. Studia Informatica. 2010; 31(2A):225–236. (in Polish). Available from: http://dx.doi.org/10.5072/si2010_v31.n2A.
• [20] Zielosko B. Global Optimization of Exact Association Rules Relative to Coverage. Pattern Recognition and Machine Intelligence - 6th International Conference, PReMI 2015, Warsaw, Poland, June 30 - July 3, 2015, Proceedings. LNCS. 9124 Springer; 2015. p. 428–437. Available from: http://dx.doi.org/10.1007/978-3-319-19941-2_41, doi:10.1007/978-3-319-19941-2_41.
• [21] Zielosko B. Global Optimization of Exact Association Rules Relative to Length. In: Proceedings of the 24th International Workshop on Concurrency, Specification and Programming, Rzeszow, Poland, September 28-30, 2015. CEUR 1492, 2015. p. 237–247. Available from: http://ceur-ws.org/Vol-1492/Paper_49.pdf.
• [22] Alsolami F, Amin T, Chikalov I, Moshkov M. Optimization of Decision Rules for Knowledge Discovery and Representation. Information Sciences. 2015;(submitted). doi:10.1007/978-3-319-18422-7_24.
• [23] Alsolami F, Amin T, Chikalov I, Moshkov M, Zielosko B. Dynamic Programming Approach for Construction of Association Rule Systems. In: Proceedings of the 24th International Workshop on Concurrency, Specification and Programming, Rzeszow, Poland, September 28-30, 2015. CEUR 1492, 2015. p. 12–21. Available from: http://ceur-ws.org/Vol-1492/Paper_01.pdf.
• [24] Asuncion A, Newman DJ. UCI Machine Learning Repository; Available from: http://www.ics.uci.edu/~mlearn/, accessed Feb. 2016.
• [25] Alkhalid A, Amin T, Chikalov I, Hussain S, Moshkov M, Zielosko B. Dagger: A Tool for Analysis and Optimization of Decision Trees and Rules. In: Computational Informatics, Social Factors and New Information Technologies: Hypermedia Perspectives and Avant-Garde Experiences in the Era of Communicability Expansion. Blue Herons; 2011. p. 29–39. http://fi.mimuw.edu.pl/index.php/FIhttp://content.iospress.com/journals/fundamenta-informaticae/145/2.
• [26] Zielosko B. Optimization of Approximate Decision Rules Relative to Coverage. In: Beyond Databases, Architectures, and Structures - 10th International Conference, BDAS 2014, Ustron, Poland, May 27-30, 2014. Proceedings. LNCS 8537 Springer; 2014 p. 170–179. Available from: http://dx.doi.org/10.1007/978-3-319-06932-6_17, doi: 10.1007/978-3-319-06932-6_17.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).