Greedy Algorithms with Weights for Construction of Partial Association Rules

• Autorzy: Moshkov M.Ju. , Piliszczuk M. , Zielosko B.
• Języki publikacji: EN

Abstrakty

EN

This paper is devoted to the study of approximate algorithms for minimization of the total weight of attributes occurring in partial association rules. We consider mainly greedy algorithms with weights for construction of rules. The paper contains bounds on precision of these algorithms and bounds on the minimal weight of partial association rules based on an information obtained during the greedy algorithm run.

Słowa kluczowe

EN

rough sets; information systems; weights; association rules; greedy algorithms

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 94, nr 1
• Strony: 101--120
• Opis fizyczny: Bibliogr. 24 poz., tab., wykr.

Twórcy

autor

Moshkov M.Ju.

autor

Piliszczuk M.

autor

Zielosko B.

• Division of Mathematical and Computer Sciences and Engineering, King Abdullah University of Science and Technology, P.O. Box 55455, Jeddah 21534, Saudi Arabia,

Bibliografia

• [1] Agrawal, R., Srikant, R.: Fast algorithms for mining association rules in large databases, Proc. 20th International Conference on Very Large Data Bases (J.B. Bocca, M. Jarke, C. Zaniolo, Eds.), Morgan Kaufmann, 1994.
• [2] Bazan, J.G.: Discovery of decision rules by matching new objects against data tables, Proc. Rough Sets and Current Trends in Computing (L. Polkowski, A. Skowron, Eds.), LNCS (LNAI) 1424, Springer, Heidelberg, 1998.
• [3] Chvátal, V.: A greedy heuristic for the set-covering problem, Mathematics of Operations Research, 4, 1979, 233-235.
• [4] Feige, U.: A threshold of ln n for approximating set cover (preliminary version). Proc. 28th Annual ACM Symposium on the Theory of Computing, ACM Press, New York, 1996.
• [5] Frequent Itemset Mining Implementations Repository, http://fimi.cs.helsinki.fi/
• [6] Kearns, M.J.: The Computational Complexity of Machine Learning, MIT Press, Cambridge Massachussetts, 1990.
• [7] Moshkov, M.Ju., Piliszczuk, M., Zielosko, B.: On partial covers, reducts and decision rules with weights, LNCS Transactions on Rough Sets VI (J.F. Peters, A. Skowron, I. Düntsch, J.W. Grzymała-Busse, E. Orłowska, L. Polkowski , Eds.), LNCS 4374. Springer, Heidelberg, 2007.
• [8] Moshkov, M.Ju., Piliszczuk, M., Zielosko, B.: Partial Covers, Reducts and Decision Rules in Rough Sets: Theory and Applications, Studies in Computational Intelligence, vol. 145, Springer, Heidelberg, 2009.
• [9] Moshkov,M.Ju., Piliszczuk, M., Zielosko, B.: Greedy algorithm for construction of partial association rules, Fundamenta Informaticae (to appear)
• [10] Nguyen, H.S.: Approximate Boolean reasoning: foundations and applications in data mining, LNCS Transactions on Rough Sets V (J.F. Peters, A. Skowron, Eds.), LNCS 4100. Springer, Heidelberg, 2006.
• [11] Nguyen, H.S., Ślęzak, D.: Approximate reducts and association rules - correspondence and complexity results, Proc. Rough Sets, Fuzzy Sets, Data Mining and Granular Computing (N. Zhong, A. Skowron, S. Ohsuga, Eds.), LNCS (LNAI) 1711, Springer, Heidelberg, 1999.
• [12] Pawlak, Z.: Rough Sets - Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Dordrecht, 1991.
• [13] Pawlak, Z.: Rough set elements, in: Rough Sets in Knowledge Discovery 1. Methodology and Applications (L. Polkowski, A. Skowron, Eds.), Studies in Fuzziness and Soft Computing, Physica-Verlag, Heidelberg, 1998, 10-30.
• [14] Pawlak, Z., Skowron, A.: Rudiments of rough sets, Information Sciences, 177(1), 2007, 3-27; Rough sets: Some extensions, Information Sciences, 177(1), 2007, 28-40; Rough sets and boolean reasoning, Information Sciences, 177(1), 2007, 41-73.
• [15] Quafafou,M.: α-RST: a generalization of rough set theory, Information Sciences, 124, 2000, 301-316.
• [16] Rastogi, R., Shim, K.: Mining optimized association rules with categorical and numeric attributes, Proc. 14th International Conference on Data Engineering, IEEE Computer Society,Washington, 1998.
• [17] Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proc. 29th Annual ACM Symposium on the Theory of Computing, ACM Press, New York, 1997.
• [18] Skowron, A.: Rough sets in KDD. Proc. 16th IFIPWorld Computer Congress (Z. Shi, B. Faltings,M.Musen, Eds.), Publishing House of Electronic Industry, 2000.
• [19] Slavık, P.: Approximation algorithms for set cover and related problems, Ph.D. Thesis, University of New York at Buffalo, 1998.
• [20] Ślęzak, D.: Normalized decision functions and measures for inconsistent decision tables analysis, Fundamenta Informaticae, 44, 2000, 291-319.
• [21] Ślęzak, D.: Approximate entropy reducts, Fundamenta Informaticae, 53, 2002, 365-390.
• [22] Srikant, R., Agrawal, R.: Mining quantitative association rules in large relational tables, Proc. 1996 ACM SIGMOD International Conference on Management of Data, ACM Press, New York, 1996.
• [23] Wróblewski, J.: Ensembles of classifiers based on approximate reducts, Fundamenta Informaticae, 47, 2001, 351-360.
• [24] Ziarko,W.: Analysis of uncertain information in the framework of variable precision rough sets, Foundations of Computing and Decision Sciences, 18, 1993, 381-396.