ACBC-Adequate Association and Decision Rules Versus Key Generators and Rough Sets Approximations

• Autorzy: Kryszkiewicz M.

Identyfikatory

DOI

10.3233/FI-2016-1423

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

Abstrakty

EN

In this paper, we propose an ACBC-evaluation formula, which delivers a flexible way of formulating different kinds of criteria for association and decision rules. We prove that rules with minimal antecedents that fulfill ACBC-evaluation formulae are key generators, which are patterns of a special type. We also show that a number of types of rough set approximations of decision classes can be expressed based on ACBC-evaluation formulae. We prove that decision rules preserving respective approximations of decision classes are rules that satisfy an ACBC-evaluation formula and that antecedents of such optimal decision rules are key generators, too. A number of properties related to particular measures of association rules and key generators are derived.

Słowa kluczowe

EN

rough sets; approximation theory; mathematical formulas; mathematical proofs; pattern recognition system

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 148, nr 1/2
• Strony: 65--85
• Opis fizyczny: Bibliogr. 34 poz., tab.

Twórcy

autor

Kryszkiewicz M.

• Institute of Computer Science, Warsaw University of Technology, Nowowiejska 15/19, 00-665 Warsaw, Poland

Bibliografia

• [1] Agrawal R, Imielinski T, Swami AN. Mining association rules between sets of items in large databases. Proc. ACM SIGMOD Int. Conf. on Management of Data, ACM 1993, p. 207–216. doi:10.1145/170035.170072.
• [2] Bailey J, Manoukian T, Ramamohanarao K. Classification using constrained emerging patterns. Proc. WAIM 2003, Springer 2003, p. 226–237. doi:10.1007/978-3-540-45160-0_22.
• [3] Bastide Y, Taouil R, Pasquier N, Stumme G, Lakhal L. Mining Frequent Patterns with Counting Inference. ACM SIGKDD Explorations 2000;2(2):66–75. doi:10.1145/380995.381017.
• [4] Brin S, Motwani R, Ullman JD, Tsur S. Dynamic item set counting and implication rules for market basket data. ACM SIGMOD Int. Conf. on Management of Data, ACM 1997, p. 255–264. doi:10.1145/253260.253325.
• [5] Dong G, Zhang X, Wong L, Li J. CAEP: Classification by Aggregating Emerging Patterns. Discovery Science 13, 1999, p. 30–42. Available from: http://dl.acm.org/citation.cfm?id=647856.738224.
• [6] Greco S, Matarazzo B, Slowinski R. Parameterized rough set model using rough membership and Bayesian confirmation measures. Int. J. Approx. Reasoning (IJAR) 2008;49(2):285–300. doi:10.1016/j.ijar.2007.05.018.
• [7] Hamrouni T, Yahia SB, Nguifo EM. Succinct Minimal Generators: Theoretical Foundations and Applications. Int. J. Found. Comput. Sci. 2008;19(2):271–296. Available from: http://dx.doi.org/10.1142/S0129054108005681
• [8] Han J, Kamber M, Pei J. Data Mining: Concept and Techniques. The Morgan Kaufmann Series in Data Management Systems (2011)
• [9] Hilderman RJ, Hamilton HJ. Evaluation of interestingness measures for ranking discovered knowledge. in: Proc. 5th Pacific-Asia Conf., PAKDD 2001, vol. 2035 in LNCS, 2001 p. 247–259. doi:10.1007/3-540-45357-1_28.
• [10] Kryszkiewicz M. Closed Set Based Discovery of Representative Association Rules. in: Proc. 4th Int. Conf. IDA 2001, Lisbon, vol. 2189 of LNCS, 2001 p. 350–359. doi:10.1007/3-540-44816-0_35.
• [11] Kryszkiewicz M. Concise Representation of Frequent Patterns based on Disjunction-free Generators. in: Proc. ICDM 2001, San Jose, IEEE Computer Society 2001 p. 305–312. doi: 10.1109/ICDM.2001.989533.
• [12] Kryszkiewicz M. Concise Representations of Association Rules. Pattern Detection and Discovery, in: Proc. ESF 2002, London, vol 2447 of LNAI, Springer-Verlag 2002 p. 92–109. Available from: http://dl.acm.org/citation.cfm?id=647915.738875.
• [13] Kryszkiewicz M. Concise Representations of Frequent Patterns and Association Rules. Prace Naukowe Politechniki Warszawskiej. Elektronika 142. Publishing House of the Warsaw University of Technology 2002.
• [14] Kryszkiewicz M, Pielasa P. Odkrywanie reprezentacji generatorowej wzorców częstych z wykorzystaniem struktur listowych (Discovery of Generators’ Representation of Frequent Patterns by Means of List Structures). ICS Research Report 14, Institute of Computer Science, WUT 2004.
• [15] Kryszkiewicz M. Using Generators for Discovering Certain and Generalized Decision Rules. in: Proc. HIS 2005, Rio de Janeiro 2005 p. 181–186. doi:10.1109/ICHIS.2005.105.
• [16] Kryszkiewicz M. Dependence Factor for Association Rules. in: Proc. ACIIDS 2015, Bali, vol. 9012 of LNAI, Springer 2015 p. 135–145. doi:10.1007/978-3-319-15705-4_14.
• [17] Kryszkiewicz, M. Dependence Factor as a Rule Evaluation Measure. Challenges in Computational Statistics and Data Mining vol 605, 2016 p. 205–223. doi:10.1007/978-3-319-18781-5_12.
• [18] Kryszkiewicz M. A Lossless Representation for Association Rules Satisfying Multiple Evaluation Criteria. in: Proc. ACIIDS 2016, vol. 9622 of LNAI, Springer 2016 p. 147–158. doi:10.1007/978-3-662-49390-8_14.
• [19] Lallich S, Teytaud O, Prudhomme E. Association rule interestingness: measure and statistical validation. Quality Measures in Data Mining 2007;(43):251–275. doi:10.1007/978-3-540-44918-8_11.
• [20] Lavrac N, Flach P, Zupan B. Rule Evaluation Measures: A Unifying View. in: Proc. ILP 1999, vol. 1634 of LNAI, Springer 1999 p. 174–185.
• [21] 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. Available from: http://dx.doi.org/10.1016/j.ejor.2006.10.059.
• [22] Ohsaki M Hidenao A, Tsumoto S, Yokoi H, Yamaguchi T. Evaluation of rule interestingness measures in medical knowledge discovery in databases. Artificial Intelligence in Medicine 2007;41(3):177–196 Available from: http://dx.doi.org/10.1016/j.artmed.2007.07.005.
• [23] Pawlak Z, Skowron A. A Rough Set Approach to Decision Rules Generation. ICS Research Report 23, Institute of Computer Science, WUT 1993.
• [24] Piatetsky-Shapiro G. Discovery, Analysis, and Presentation of Strong Rules. Knowledge Discovery in Databases, AAAI/MIT Press 1991 p. 229–248.
• [25] Sheikh LM, Tanveer B, Hamdani SMA. Interesting Measures for Mining Association Rules. in: Proc. INMIC 2004, IEEE 2004. doi:10.1109/INMIC.2004.1492964.
• [26] Shortliffe E, Buchanan B. A model of inexact reasoning in medicine. Mathematical Biosciences 1975;23(3-4):351–379. doi:10.1016/0025-5564(75)90047-4.
• [27] Silberschatz A, Tuzhilin A. On Subjective Measures of Interestingness in Knowledge Discovery. in: Proc. KDD 1995 p. 275–281.
• [28] Yao Y. Three-way decisions with probabilistic rough sets. Inf. Sci. 2010;180(3):341–353. Available from: http://dx.doi.org/10.1016/j.ins.2009.09.021.
• [29] Slezak D, Ziarko W. The investigation of the Bayesian rough set model. Int. J. Approx. Reasoning 2005;40(1-2):81–91. doi:10.1016/j.ijar.2004.11.004.
• [30] Stumme G, Taouil R, Bastide Y, Pasquier N, Lakhal L. Fast Computation of Concept Lattices Using Data Mining Techniques. in: Proc. KRDB 2000, Berlin 2000 p. 129–139. Available from: https://hal.inria.fr/inria-00099288.
• [31] Stumme G, Taouil R, Bastide Y, Pasquier N, Lakhal L. Intelligent Structuring and Reducing of Association Rules with Formal Concept Analysis. KI/ÖGAI vol. 2174 of LNCS, Springer 2001 p. 335–350. doi:10.1007/3-540-45422-5_24.
• [32] Suzuki E. Pitfalls for Categorizations of Objective Interestingness Measures for Rule Discovery. vol. 127 of Statistical Implicative Analysis: Theory and Applications, Springer-Verlag 2008 p. 383–395. doi:10.1007/978-3-540-78983-3_17.
• [33] Suzuki E. Interestingness Measures - Limits, Desiderata, and Recent Results. QIMIE/PAKDD 2009.
• [34] Ziarko W. Probabilistic approach to rough sets. Int. J. Approx. Reasoning 2008;49(2):272–284. doi:10.1016/j.ijar.2007.06.014.

Uwagi

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