The Close-by-One (CbO) algorithm is a well-known algorithm used in Formal Concept Analysis (FCA). We shed a new light on CbO: First, we propose and evaluate a novel algorithm for computation of the Duquenne-Guigues basis which combines CbO and LinClosure algorithms. This combination enables us to reuse attribute counters used in LinClosure and speed up the computation. Second, we describe LCM, an algorithm for enumeration of frequent closed itemsets in transaction databases, in terms of FCA and show that LCM is basically the CbO algorithm with multiple speed-up features for processing sparse data. Third, we show that FCA and Logical Analysis of Data (LAD) utilize the same basic building blocks, which enable us to develop an interface between the two methodologies. We provide some preliminary benefits of the interface; most notably efficient algorithms for computing spanned patterns in LAD using algorithms of FCA.
Annotation in English
The Close-by-One (CbO) algorithm is a well-known algorithm used in Formal Concept Analysis (FCA). We shed a new light on CbO: First, we propose and evaluate a novel algorithm for computation of the Duquenne-Guigues basis which combines CbO and LinClosure algorithms. This combination enables us to reuse attribute counters used in LinClosure and speed up the computation. Second, we describe LCM, an algorithm for enumeration of frequent closed itemsets in transaction databases, in terms of FCA and show that LCM is basically the CbO algorithm with multiple speed-up features for processing sparse data. Third, we show that FCA and Logical Analysis of Data (LAD) utilize the same basic building blocks, which enable us to develop an interface between the two methodologies. We provide some preliminary benefits of the interface; most notably efficient algorithms for computing spanned patterns in LAD using algorithms of FCA.
The Close-by-One (CbO) algorithm is a well-known algorithm used in Formal Concept Analysis (FCA). We shed a new light on CbO: First, we propose and evaluate a novel algorithm for computation of the Duquenne-Guigues basis which combines CbO and LinClosure algorithms. This combination enables us to reuse attribute counters used in LinClosure and speed up the computation. Second, we describe LCM, an algorithm for enumeration of frequent closed itemsets in transaction databases, in terms of FCA and show that LCM is basically the CbO algorithm with multiple speed-up features for processing sparse data. Third, we show that FCA and Logical Analysis of Data (LAD) utilize the same basic building blocks, which enable us to develop an interface between the two methodologies. We provide some preliminary benefits of the interface; most notably efficient algorithms for computing spanned patterns in LAD using algorithms of FCA.
Annotation in English
The Close-by-One (CbO) algorithm is a well-known algorithm used in Formal Concept Analysis (FCA). We shed a new light on CbO: First, we propose and evaluate a novel algorithm for computation of the Duquenne-Guigues basis which combines CbO and LinClosure algorithms. This combination enables us to reuse attribute counters used in LinClosure and speed up the computation. Second, we describe LCM, an algorithm for enumeration of frequent closed itemsets in transaction databases, in terms of FCA and show that LCM is basically the CbO algorithm with multiple speed-up features for processing sparse data. Third, we show that FCA and Logical Analysis of Data (LAD) utilize the same basic building blocks, which enable us to develop an interface between the two methodologies. We provide some preliminary benefits of the interface; most notably efficient algorithms for computing spanned patterns in LAD using algorithms of FCA.
Student nastuduje algoritmus Close-by-One a některé jeho varianty. Na základě získaných poznatků se pokusí algoritmus vylepšit, případně upravit pro použití v jiných oblastech. Dále nastuduje algoritmus LCM a popíše jej z pohledu Formální konceptuální analýzy.
Research Plan
Student nastuduje algoritmus Close-by-One a některé jeho varianty. Na základě získaných poznatků se pokusí algoritmus vylepšit, případně upravit pro použití v jiných oblastech. Dále nastuduje algoritmus LCM a popíše jej z pohledu Formální konceptuální analýzy.
Recommended resources
B. Ganter and R. Wille. Formal Concept Analysis -- Mathematical Foundations. Springer, 1999.
S. O. Kuznetsov. A fast algorithm for computing all intersections of objects from an arbitrary semilattice. Nauchno-Tekhnicheskaya Informatsiya Seriya 2-Informatsionnye (Protsessy i Sistemy
, (1):17--20, 1993.}
S. Andrews. In-Close, a fast algorithm for computing formal concepts. In International Conference on Conceptual Structures. Springer, 2009.
J. Outrata and V. Vychodil. Fast algorithm for computing fixpoints of Galois connections induced by object-attribute relational data. Information Sciences, 185(1):114--127, 2012.
T. Uno, T. Asai, Y. Uchida, and H. Arimura. An efficient algorithm for enumerating closed patterns in transaction databases. International Conference on Discovery Science, pages 16--31. Springer, 2004.
G. Alexe, S. Alexe, T. O. Bonates, and A. Kogan. Logical Analysis of Data--the vision of Peter L. Hammer. Annals of Mathematics and Artificial Intelligence, 49(1-4):265--312, 2007.
Recommended resources
B. Ganter and R. Wille. Formal Concept Analysis -- Mathematical Foundations. Springer, 1999.
S. O. Kuznetsov. A fast algorithm for computing all intersections of objects from an arbitrary semilattice. Nauchno-Tekhnicheskaya Informatsiya Seriya 2-Informatsionnye (Protsessy i Sistemy
, (1):17--20, 1993.}
S. Andrews. In-Close, a fast algorithm for computing formal concepts. In International Conference on Conceptual Structures. Springer, 2009.
J. Outrata and V. Vychodil. Fast algorithm for computing fixpoints of Galois connections induced by object-attribute relational data. Information Sciences, 185(1):114--127, 2012.
T. Uno, T. Asai, Y. Uchida, and H. Arimura. An efficient algorithm for enumerating closed patterns in transaction databases. International Conference on Discovery Science, pages 16--31. Springer, 2004.
G. Alexe, S. Alexe, T. O. Bonates, and A. Kogan. Logical Analysis of Data--the vision of Peter L. Hammer. Annals of Mathematics and Artificial Intelligence, 49(1-4):265--312, 2007.
