Application of Dynamic Programming Approach to Optimization of Association Rules Relative to Coverage and Length

• Autorzy: Zielosko B.

Identyfikatory

DOI

10.3233/FI-2016-1424

• Konferencja: Rough Set Theory Workshop (RST’2015); (6; 29-06-2015; University of Warsaw )
• Języki publikacji: EN

Abstrakty

EN

In the paper, an application of dynamic programming approach to global optimization of approximate association rules relative to coverage and length is presented. It is an extension of the dynamic programming approach to optimization of decision rules to inconsistent tables. Experimental results with data sets from UCI Machine Learning Repository are included.

Słowa kluczowe

EN

rough sets; association rules; decision rules; length; coverage; dynamic programming

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 148, nr 1/2
• Strony: 87--105
• Opis fizyczny: Bibliogr. 33 poz., rys., tab.

Twórcy

autor

Zielosko B.

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

Bibliografia

• [1] Hájek P, Hávranek T. Mechanizing Hypothesis Formation - Mathematical Foundations for a General Theory. Springer-Verlag Berlin Heidelberg; 1978. ISBN:978-3-540-08738-0. doi:10.1007/978-3-642-66943-9.
• [2] Agrawal R, Mannila H, Srikant R, Toivonen H, Verkamo AI. Advances in Knowledge Discovery and Data Mining. American Association for Artificial Intelligence; 1996. p. 307–328. doi:10.1007/978-3-319-31750-2.
• [3] Hájek P, Holeňa M, Rauch J. The GUHA method and its meaning for data mining. Journal of Computer and System Sciences. 2010;76(1):34–48. doi:10.1016/j.jcss.2009.05.004.
• [4] Rauch J. Observational Calculi and Association Rules. vol. 469 of Studies in Computational Intelligence. Springer Berlin Heidelberg; 2013. ISBN:978-3-642-11736-7. doi:10.1007/978-3-642-11737-4.
• [5] Agrawal R, Imieliński T, Swami A. Mining Association Rules Between Sets of Items in Large Databases. In: SIGMOD ’93. ACM; 1993. p. 207–216. doi:10.1145/170035.170072.
• [6] Park JS, Chen MS, Yu PS. An Effective Hash Based Algorithm for Mining Association Rules. In: Carey MJ, Schneider DA, editors. SIGMOD Conference. ACM Press; 1995. p. 175–186. doi:10.1145/223784.223813.
• [7] Han J, Fu Y. Discovery of Multiple-Level Association Rules from Large Databases. In: Dayal U, Gray PMD, Nishio S, editors. VLDB. Morgan Kaufmann; 1995. p. 420–431. ISBN:1-55860-379-4. Available from: http://dl.acm.org/citation.cfm?id=645921.673134.
• [8] Herawan T, Deris MM. A soft set approach for association rules mining. Knowledge-Based Systems. 2011;24(1):186–195. doi:10.1016/j.knosys.2010.08.005.
• [9] Nguyen HS, Nguyen SH. Rough Sets and Association Rule Generation. Fundam Inform. 1999;40(4):383–405. Available from: http://dl.acm.org/citation.cfm?id=2379004.2379007.
• [10] Wieczorek A, Słowiński R. Generating a set of association and decision rules with statistically representative support and anti-support. Inf Sci. 2014;277:56–70. doi:10.1016/j.ins.2014.02.003.
• [11] Han J, Pei J, Yin Y, Mao R. Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach. Data Min Knowl Discov. 2004;8(1):53–87. doi:10.1023/B:DAMI.0000005258.31418.83.
• [12] Borgelt C. Simple Algorithms for Frequent Item Set Mining. In: Koronacki J, Raś ZW, Wierzchoń ST, Kacprzyk J, editors. 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.
• [13] Han J, Kamber M. Data Mining: Concepts and Techniques. Morgan Kaufmann; 2000. ISBN:1-55860-489-8.
• [14] Lee AJT, Hong RW, Ko WM, Tsao WK, Lin HH. Mining spatial association rules in image databases. Inf Sci. 2007;177(7):1593–1608.
• [15] 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. doi:10.1016/j.ins.2006.09.018
• [16] 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.
• [17] Zaki MJ, Parthasarathy S, Ogihara M, Li W. New Algorithms for Fast Discovery of Association Rules. Rochester, NY, USA; 1997. Available from: http://www.ncstrl.org:8900/ncstrl/servlet/search?formname=detail\&id=oai\%3Ancstrlh\%3Arochester_cs\%3Ancstrl.rochester_cs\%2F\%2FTR651
• [18] Rissanen J. Modeling by shortest data description. Automatica. 1978;14(5):465–471. doi:10.1016/0005-1098(78)90005-5.
• [19] Bonates TO, Hammer PL, Kogan A. Maximum patterns in datasets. Discrete Applied Mathematics. 2008; 156(6):846–861. doi:10.1016/j.dam.2007.06.004.
• [20] Moshkov MJ, Piliszczuk M, Zielosko B. Greedy Algorithm for Construction of Partial Association Rules. Fundam Inform. 2009;92(3):259–277. Available from: http://dl.acm.org/citation.cfm?id=1551885.1551888.
• [21] Nguyen HS, Ślęzak D. Approximate Reducts and Association Rules - Correspondence and Complexity Results. In: Zhong N, Skowron A, Ohsuga S, editors. RSFDGrC. vol. 1711 of LNCS. Springer; 1999. p.137–145. Available from: http://dl.acm.org/citation.cfm?id=646590.697625.
• [22] Pawlak Z, Skowron A. Rudiments of rough sets. Information Sciences 2007;177(1):3–27. doi:10.1016/j.ins.2006.06.003.
• [23] Moshkov MJ, Piliszczuk M, Zielosko B. On Construction of Partial Association Rules. In: Wen P, Li Y, Polkowski L, Yao Y, Tsumoto S, Wang G, editors. RSKT. vol. 5589 of LNCS. Springer; 2009. p. 176–183. doi:10.1007/978-3-642-02962-2_22.
• [24] 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.366.
• [25] Zielosko B. Global Optimization of Exact Association Rules Relative to Coverage. In: Kryszkiewicz M, Bandyopadhyay S, Rybiński H, Pal SK, editors. PReMI 2015. vol. 9124 of LNCS. Springer; 2015. p. 428–437. doi:10.1007/978-3-319-19941-2_41.
• [26] Zielosko B. Global Optimization of Exact Association Rules Relative to Length. In: Suraj Z, Czaja L, editors. Proceedings of 24th International Workshop, CS&P 2015. vol. 2. University of Rzeszów; 2015. p. 237–247. Available from: http://ceur-ws.org/Vol-1492/Paper_49.pdf.
• [27] Amin T, Chikalov I, Moshkov M, Zielosko B. Dynamic programming approach to optimization of approximate decision rules. Inf Sci. 2013;221(1):403–418. Available from: http://dx.doi.org/10.1016/j.ins.2012.09.018.
• [28] Skowron A. Rough Sets in KDD - plenary talk. In: Shi Z, Faltings B, Musen M, editors. Proc. 16th IFIP. World Computer Congress. Publishing House of Electronic Industry; 2000. p. 1–14.
• [29] Moshkov M, Chikalov I. On algorithm for constructing of decision trees with minimal depth. Fundam Inform. 2000;41(3):295–299. Available from: http://dl.acm.org/citation.cfm?id=343097.343100.
• [30] Moshkov MJ. On the class of restricted linear information systems. Discrete Mathematics. 2007;307(22): 2837–2844. doi:10.1016/j.disc.2007.03.002.
• [31] Asuncion A, Newman DJ. UCI Machine Learning Repository. University of California, Irvine, School of Information and Computer Sciences; 2007. Available from: http://www.ics.uci.edu/~mlearn/.
• [32] Zielosko B. Optimization of Decision Rules Relative to Coverage - Comparative Study. In: Kryszkiewicz M, Cornelis C, Ciucci D, Medina-Moreno J, Motoda H, Raś ZW, editors. JRS 2014. vol. 8537 of LNCS. Springer; 2014. p. 237–247. doi:10.1007/978-3-319-08729-0_23.
• [33] 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.

Uwagi

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