Greedy Algorithm for Construction of Partial Association Rules

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

Abstrakty

EN

Partial association rules can be used for representation of knowledge, for inference in expert systems, for construction of classifiers, and for filling missing values of attributes. This paper is devoted to the study of approximate algorithms for minimization of partial association rule length. It is shown that under some natural assumptions on the class NP, a greedy algorithm is close to the best polynomial approximate algorithms for solving of this NP-hard problem. The paper contains various bounds on precision of the greedy algorithm, bounds on minimal length of rules based on an information obtained during the greedy algorithm work, and results of theoretical and experimental study of association rules for the most part of binary information systems.

Słowa kluczowe

EN

rough sets; information systems; association rules; greedy algorithm

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 92, nr 3
• Strony: 259--277
• Opis fizyczny: Bibliogr. 26 poz., tab.

Twórcy

autor

Moshkov M.Ju.

autor

Piliszczuk M.

• Division of Mathematical and Computer Science 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] Cheriyan, J., Ravi, R.: Lecture Notes on Approximation Algorithms for Network Problems, 1998, http://www.math.uwaterloo.ca/∼jcheriya/lecnotes.html
• [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] Moshkov,M.Ju.: On greedy algorithmfor partial cover construction, Proc. Design and Complexity of Control Systems (O.B. Lupanov, Ed.), Moscow University, Moscow, 2003 (in Russian).
• [7] Moshkov, M.Ju., Piliszczuk, M., Zielosko, B.: On partial covers, reducts and decision rules. LNCS Transactions on Rough Sets VIII (J.F. Peters, A. Skowron, Eds.) LNCS 5084. Springer, Heidelberg, 2008.
• [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., Skowron, A., Suraj, Z.: On minimal rule sets for almost all binary information systems, Fundamenta Informaticae, 80(1-3), 2007, 247-258.
• [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] Rissanen, J.: Modeling by shortest data description, Automatica, 14, 1978, 465-471.
• [19] Skowron, A.: Rough sets in KDD. Proc. 16th IFIP World Computer Congress (Z. Shi, B. Faltings,M.Musen, Eds.), Publishing House of Electronic Industry, 2000.
• [20] Slavık, P.: A tight analysis of the greedy algorithm for set cover (extended abstract), Proc. 28th Annual ACM Symposium on the Theory of Computing, ACM Press, New York, 1996.
• [21] Slavık, P.: Approximation algorithms for set cover and related problems, Ph.D. Thesis, University of New York at Buffalo, 1998.
• [22] Ślęzak, D.: Normalized decision functions and measures for inconsistent decision tables analysis, Fundamenta Informaticae, 44, 2000, 291-319.
• [23] Ślęzak, D.: Approximate entropy reducts, Fundamenta Informaticae, 53, 2002, 365-390.
• [24] 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.
• [25] Wr´oblewski, J.: Ensembles of classifiers based on approximate reducts, Fundamenta Informaticae, 47, 2001, 351-360.
• [26] Ziarko,W.: Analysis of uncertain information in the framework of variable precision rough sets, Foundations of Computing and Decision Sciences, 18, 1993, 381-396.