LCM from FCA point of view: a CbO-style algorithm with speed-up features. (English) Zbl 07478938
Summary: LCM is an algorithm for enumeration of frequent closed itemsets in transaction databases. It is well known that when we ignore the required frequency, the closed itemsets are exactly intents of formal concepts in Formal Concept Analysis (FCA). We describe LCM in terms of FCA and show that LCM is basically the Close-by-One algorithm with multiple speed-up features for processing sparse data. We analyze the speed-up features and compare them with those of similar FCA algorithms, like FCbO and algorithms from the In-Close family.
MSC:
| 68T30 | Knowledge representation |
References:
| [1] | Agrawal, Rakesh; Mannila, Heikki; Srikant, Ramakrishnan; Toivonen, Hannu; Inkeri Verkamo, A., Fast discovery of association rules, Adv. Knowl. Discov. Data Min., 12, 1, 307-328 (1996) |
| [2] | Alexe, Gabriela; Alexe, Sorin; Bonates, Tibérius O.; Kogan, Alexander, Logical analysis of data-the vision of Peter L. Hammer, Ann. Math. Artif. Intell., 49, 1-4, 265-312 (2007) · Zbl 1126.68064 |
| [3] | Alexe, Gabriela; Hammer, Peter L., Spanned patterns for the logical analysis of data, Discrete Appl. Math., 154, 7, 1039-1049 (2006) · Zbl 1090.68094 |
| [4] | Andrews, Simon, In-Close2, a high performance formal concept miner, (Proceedings of the 19th International Conference on Conceptual Structures for Discovering Knowledge, ICCS’11 (2011), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 50-62 |
| [5] | Andrews, Simon, A ‘Best-of-Breed’ approach for designing a fast algorithm for computing fixpoints of Galois connections, Inf. Sci., 295, 633-649 (2015) · Zbl 1360.68797 |
| [6] | Andrews, Simon, Making use of empty intersections to improve the performance of CbO-type algorithms, (International Conference on Formal Concept Analysis (2017), Springer), 56-71 · Zbl 1489.68265 |
| [7] | Andrews, Simon, A new method for inheriting canonicity test failures in Close-by-One type algorithms, (CLA, vol. 2123 (2018)), 255-266 |
| [8] | Bayardo, Roberto J., Efficiently Mining Long Patterns from Databases, ACM Sigmod Record, vol. 27, 85-93 (1998), ACM |
| [9] | Han, Jiawei; Pei, Jian; Yin, Yiwen, Mining frequent patterns without candidate generation, ACM Sigmod Rec., 29, 2, 1-12 (2000) |
| [10] | Janostik, Radek; Konecny, Jan; Krajča, Petr, LCM is well implemented CbO: study of LCM from FCA point of view, (CLA 2020, CEUR Workshop Proceedings, vol. 2668 (2020)), 47-58 · Zbl 1441.68246 |
| [11] | Krajca, Petr; Outrata, Jan; Vychodil, Vilem, Advances in algorithms based on CbO, (CLA, vol. 672 (2010)), 325-337 |
| [12] | Krajca, Petr; Vychodil, Vilem, Comparison of data structures for computing formal concepts, (International Conference on Modeling Decisions for Artificial Intelligence (2009), Springer), 114-125 · Zbl 1273.68379 |
| [13] | Kuznetsov, Sergei O., A Fast Algorithm for Computing All Intersections of Objects from an Arbitrary Semilattice, Nauchno-Tekh. Inf. Ser. 2-Inform. Protses. Sist., 1, 17-20 (1993) |
| [14] | Kuznetsov, Sergei O.; Obiedkov, Sergei, Comparing performance of algorithms for generating concept lattices, J. Exp. Theor. Artif. Intell., 14, 189-216 (2002) · Zbl 1024.68020 |
| [15] | Mannila, Heikki; Toivonen, Hannu, Multiple uses of frequent sets and condensed representations, (KDD, vol. 96 (1996)), 189-194 |
| [16] | Outrata, Jan; Vychodil, Vilem, Fast algorithm for computing fixpoints of Galois connections induced by object-attribute relational data, Inf. Sci., 185, 1, 114-127 (2012) · Zbl 1239.68070 |
| [17] | Uno, Takeaki; Asai, Tatsuya; Uchida, Yuzo; Arimura, Hiroki, LCM: An Efficient Algorithm for Enumerating Frequent Closed Item Sets, FIMI, vol. 90 (2003), Citeseer · Zbl 1110.68472 |
| [18] | Uno, Takeaki; Asai, Tatsuya; Uchida, Yuzo; Arimura, Hiroki, An efficient algorithm for enumerating closed patterns in transaction databases, (International Conference on Discovery Science (2004), Springer), 16-31 · Zbl 1110.68472 |
| [19] | Uno, Takeaki; Kiyomi, Masashi; Arimura, Hiroki, LCM ver. 2: efficient mining algorithms for frequent/closed/maximal itemsets, (FIMI, vol. 126 (2004)) |
| [20] | Uno, Takeaki; Kiyomi, Masashi; Arimura, Hiroki, LCM ver. 3: collaboration of array, bitmap and prefix tree for frequent itemset mining, (Proceedings of the 1st International Workshop on Open Source Data Mining: Frequent Pattern Mining Implementations (2005), ACM), 77-86 |
| [21] | Zaki, Mohammed J.; Gouda, Karam, Fast vertical mining using diffsets, (Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2003), ACM), 326-335 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
