Informatics and Applications
2022, Volume 16, Issue 1, pp 82-87
FINDING MAXIMAL FREQUENT AND MINIMAL INFREQUENT SETS IN PARTIALLY ORDERED DATA
- N. A. Dragunov
- E. V. Djukova
Abstract
Relevant issues of time costs reducing in the logical analysis of data with elements from the Cartesian product of finite partially ordered sets are investigated. An original method based on solving a complex discrete problem called dualization over the product of partial orders is proposed for the problem of finding maximal frequent and minimal infrequent sets in the transaction database. The proposed method is a synthesis of two other known methods, one of which is quite obvious and the other uses the idea of an incremental enumeration of target sets and is, therefore, mainly of theoretical interest. An experimental study of the considered approaches in the
case of the product of finite chains is carried out and conditions for their effectiveness are revealed. The expediency
of applying asymptotically optimal dualization algorithms over the product of partial orders is shown.
[+] References (8)
- Aggarwal, C. 2014. Frequent pattern mining. Heidelberg:
Springer. 467 p.
- Agrawal, R., T Imielinski, and A. Swami. 1993. Mining
association rules between sets of items in large databases.
SIGMOD Conference (International) on Management of Data
Proceedings. New York, NY: ACM. 207-216.
- Elbassioni, K. 2014. On finding minimal infrequent elements in multidimensional data defined over partially ordered sets. arXiv.org. 30 p. Available at: https://arxiv.org/pdf/1411.2275.pdf (accessed January 25, 2022).
- Elbassioni, K. 2009. Algorithms for dualization over products of partially ordered sets. SIAM J. Discrete Math. 23(1):487-510.
- Agrawal, R., and R. Srikant. 1994. Fast algorithms for mining association rules in large databases. 20th Conference (International) on Very Large Data Bases Proceedings. San Francisco, CA: Morgan Kaufmann Publs. Inc. 487-499.
- Khachiyan, L. G. 2009. Izbrannye trudy [Selected works]. Moscow: MCCME. 520 p.
- Djukova, E. V., G. O. Maslyakov, and P. A. Prokofyev. 2017. O dualizatsii nad proizvedeniem chastichnykh poryadkov [On dualization over the product of partial orders]. Mashin - noe obuchenie i analiz dannykh [J. Machine Learning Data Analysis] 3(4):239-249.
- Djukova, E.V., and P. A. Prokofyev. 2015. Asymptotically optimal dualization algorithms. Comp. Math. Math. Phys. 55(5):891-905.
[+] About this article
Title
FINDING MAXIMAL FREQUENT AND MINIMAL INFREQUENT SETS IN PARTIALLY ORDERED DATA
Journal
Informatics and Applications
2022, Volume 16, Issue 1, pp 82-87
Cover Date
2022-03-30
DOI
10.14357/19922264220112
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
maximal frequent sets; minimal infrequent sets; dualization over the product of partial orders; asymptotically optimal dualization algorithm
Authors
N. A. Dragunov  and E. V. Djukova
Author Affiliations
Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
|