Analysis of monotonicity properties of some rule interestingness measures

• Autorzy: Greco S. , Słowiński R. , Szczęch I.
• Języki publikacji: EN

Abstrakty

EN

One of the crucial problems in the field of knowledge discovery is development of good interestingness measures for evaluation of the discovered patterns. In this paper, we consider quantitative, objective interestingness measures for "if..., then... " association rules. We focus on three popular interestingness measures, namely rule interest function of Piatetsky-Shapiro, gain measure of Fukuda et al., and dependency factor used by Pawlak. We verify whether they satisfy the valuable property M of monotonic dependency on the number of objects satisfying or not the premise or the conclusion of a rule, and property of hypothesis symmetry (HS). Moreover, analytically and through experiments we show an interesting relationship between those measures and two other commonly used measures of rule support and anti-support.

Słowa kluczowe

EN

association rules; Piatetsky-Shapiro's rule interest function; gain measure; dependency factor; anti-support; Pareto-optimal border

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2009
• Tom: Vol. 38, no 1
• Strony: 9--25
• Opis fizyczny: Bibliogr. 25 poz., wykr.

Twórcy

autor

Greco S.

autor

Słowiński R.

autor

Szczęch I.

• Faculty of Economics, University of Catania, Corso Italia, 55, 95129 Catania, Italy,

Bibliografia

• AGRAWAL, R., IMIELINSKI, T. and SWAMI, A. (1993) Mining Associations Between Sets of Items in Massive Databases. In: P. Buneman and S. Jajodia, eds., Proceedings of the 1993 ACM-SIGMOD Int’l Conf. on Management of Data, Washington, B.C., USA. ACM Press, 207-216.
• BAYARDO, R.J. and AGRAWAL, R. (1999) Mining the Most Interesting Rules. Proceedings of Fifth ACM-SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining, San Diego, CA, USA. ACM Press, New York, NY, 145-154.
• BRAMER, M. (2007) Principles of Data Mining. Springer-Verlag, New York.
• BRIN, S., MOTWANI, R., ULLMAN, J. and TSUR, S. (1997) Dynamicitemset counting and implication rules for market basket data. Proceedings of the 1997 ACM-SIGMOD Int’l Conf. on the Management of Data. ACM Press, New York, NY, 255-264.
• BRZEZIŃSKA. I., GRECO, S. and SŁOWIŃSKI, R. (2007) Mining Pareto-optimal rules with respect to support and anti-support. Engineering Applications of Artificial Intelligence, 20 (5), 587-600.
• CARNAP, R. (1962) Logical Foundations of Probability, 2nd ed. University of Chicago Press, Chicago.
• CLARK, P. and BOSWELL, P. (1991) Rule Induction with CN2: Some Recent Improvements. Proceedings of the European Working Session on Machine Learning. LNCS 482, Springer, London, 151-163.
• DHAR, V. and TUZHILIN, A. (1993) Abstract-driven pattern discovery in databases. IEEE Transactions on Knowledge and Data Engineering 5 (6), 926-938.
• EARMAN, J. (1992) Bayes or Bust: A Critical Examination of Bayesian Confirmation Theory. MIT Press, Cambridge, MA.
• EELLS, E and FITELSON, B. (2002) Symmetries and assymmetries in evidential support. Philosophical Studies, 107 (2), 129-142.
• FITELSON, B. (2001) Studies in Bayesian confirmation theory. Ph.D. Thesis, University of Wisconsin, Madison.
• FUKUDA, T., MORIMOTO, Y., MORISHITA, S. and TOKUYAMA, T. (1996) Data Mining using Two-Dimensional Optimized Association Rules: Schemes, Algorithms, and Visualization. Proceedings of the 1996 ACM SIGMOD Int’l Conference on Management of Data. Montreal, Canada. ACM Press, New York, 13-23.
• GRECO, S., PAWLAK, Z. and SŁOWIŃSKI, R. (2004) Can Bayesian confirmation measures be useful for rough set decision rules? Engineering Applications of Artificial Intelligence 17, 345-361.
• HEMPEL, C.G. (1945) Studies in the logic of confirmation (I). Mind 54, 1-26.
• HILDERMAN, R. and HAMILTON, H. (2001) Knowledge Discovery and Measures of Interest. Kluwer Academic Publishers, Boston.
• INTERNATIONAL BUSINESS MACHINES (1996) IBM Intelligent Miner User’s Guide Version 1, Release 1.
• MORZY, T. and ZAKRZEWICZ, M. (2003) Data mining. In: J. Błażewicz, W. Kubiak, T. Morzy, M.E. Rusinkiewicz, eds., Handbook on Data Management in Information Systems. Springer-Verlag, 487-565.
• PAWLAK, Z. (2004) Some issues on Rough Sets. Transactions on Rough Sets I. LNCS 3100, 1-58.
• PIATETSKY-SHAPIRO, G. (1991) Discovery, analysis and presentation of strong rules. Knowledge Discovery in Databases. AAAI/MIT Press, 2, 29-248.
• POPPER, K.R. (1959) The Logic of Scientific Discovery. Hutchinson, London.
• SILBERSCHATZ, A. and TUZHILIN, A. (1996) What Makes Patterns Interesting in Knowledge Discovery Systems. IEEE Transactions on Knowledge and Data Engineering 8 (6), 970-974.
• SŁOWIŃSKI, R., BRZEZIŃSKA, I. and GRECO, S. (2006) Application of Bayesian confirmation measures for mining rules from support-confidence Pareto-optimal set. Invited paper in: L. Rutkowski, R. Tadeusiewicz, L.A. Zadeh, J. Żurada, eds., Artificial Intelligence and Soft Computing. LNAI 4029, Springer-Verlag, Berlin, 1018-1026.
• SŁOWIŃSKI, R., SZCZĘCH, I., URBANOWICZ, M. and GRECO, S. (2007) Mining association rules with respect to support and anti-support - experimental results. In: M. Kryszkiewicz, J.F. Peters, H. Rybiński, A. Skowron, eds., Rough Sets and Intelligent Systems Paradigms. LNAI 4585, Springer-Verlag, Berlin, 534-542.
• TAN, P-N., STEINBACH, M. and KUMAR, V. (2006) Introduction to Data Mining. Pearson Education, Inc., USA.
• WEBB, G.I. (1995) OPUS: An efficient admissible algorithm for unordered search. Journal of Artificial Intelligence Research, 3, 431-465.