Abstract
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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, R., Srikant, R.: Fast algorithms for mining association rules in large databases. In: Bocca, J.B., Jarke, M., Zaniolo, C. (eds.) Proceedings of the 20th International Conference on Very Large Data Bases. Morgan Kaufmann, San Francisco (1994)
Bazan, J.G.: Discovery of decision rules by matching new objects against data tables. In: Polkowski, L., Skowron, A. (eds.) RSCTC 1998. LNCS (LNAI), vol. 1424, pp. 521–528. Springer, Heidelberg (1998)
Chvátal, V.: A greedy heuristic for the set-covering problem. Mathematics of Operations Research 4(3), 233–235 (1979)
Feige, U.: A threshold of ln n for approximating set cover (preliminary version). In: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, Philadelphia, US (1996)
Goethals, B.: Frequent itemset mining implementations repository, http://fimi.cs.helsinki.fi
Kearns, M.J.: The computational complexity of machine learning. Massachussetts Institute of Technology Press, Cambridge (1990)
Moshkov, M.J., Piliszczuk, M., Zielosko, B.: On partial covers, reducts and decision rules with weights. In: Peters, J.F., Skowron, A., Düntsch, I., Grzymała-Busse, J.W., Orłowska, E., Polkowski, L. (eds.) Transactions on Rough Sets VI. LNCS, vol. 4374, pp. 211–246. Springer, Heidelberg (2007)
Moshkov, M.J., Piliszczuk, M., Zielosko, B.: Partial covers, reducts and decision rules in rough sets: theory and applications. Studies in Computational Intelligence, vol. 145. Springer, Heidelberg (2008)
Nguyen, H.S.: Approximate boolean reasoning: foundations and applications in data mining. In: Peters, J.F., Skowron, A. (eds.) Transactions on Rough Sets V. LNCS, vol. 4100, pp. 334–506. Springer, Heidelberg (2006)
Nguyen, H.S., Ślęzak, D.: Approximate reducts and association rules – correspondence and complexity results. In: Zhong, N., Skowron, A., Ohsuga, S. (eds.) RSFDGrC 1999. LNCS (LNAI), vol. 1711, pp. 137–145. Springer, Heidelberg (1999)
Pawlak, Z.: Rough sets – theoretical aspects of reasoning about data. Kluwer Academic Publishers, Dordrecht (1991)
Pawlak, Z.: Rough set elements. In: Polkowski, L., Skowron, A. (eds.) Rough sets in knowledge discovery 1. Methodology and applications. Studies in Fuzziness and Soft Computing. Physica-Verlag, Heidelberg (1998)
Pawlak, Z., Skowron, A.: Rudiments of rough stes. Information Sciences 177, 3–27; Rough sets: Some extensions. Information Sciences 177, 28–40; Rough sets and boolean reasoning. Information Sciences 177, 41–73 (2007)
Quafafou, M.: α-RST: a generalization of rough set theory. Information Sciences 124(1-4), 301–316 (2000)
Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the 29th Annual ACM symposium on the theory of computing. El Paso, US (1997)
Skowron, A.: Rough sets in KDD. In: Shi, Z., Faltings, B., Musen, M. (eds.) Proceedings of the 16th IFIP World Computer Congress. Publishing House of Electronic Industry, Beijing (2000)
Slavík, P.: Approximation algorithms for set cover and related problems. Ph.D. thesis, University of New York, Buffalo, US (1998)
Ślęzak, D.: Normalized decision functions and measures for inconsistent decision tables analysis. Fundamenta Informaticae 44(3), 291–319 (2000)
Ślęzak, D.: Approximate entropy reducts. Fundamenta Informaticae 53(3-4), 365–390 (2002)
Wróblewski, J.: Ensembles of classifiers based on approximate reducts. Fundamenta Informaticae 47(3-4), 351–360 (2001)
Ziarko, W.: Analysis of uncertain information in the framework of variable precision rough sets. Foundations of Computing and Decision Sciences 18(3-4), 381–396 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Moshkov, M.J., Piliszczuk, M., Zielosko, B. (2009). On Construction of Partial Association Rules with Weights. In: Cyran, K.A., Kozielski, S., Peters, J.F., Stańczyk, U., Wakulicz-Deja, A. (eds) Man-Machine Interactions. Advances in Intelligent and Soft Computing, vol 59. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00563-3_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-00563-3_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00562-6
Online ISBN: 978-3-642-00563-3
eBook Packages: EngineeringEngineering (R0)