On pattern setups and pattern multistructures

Abstract

Order and lattice theory provides convenient mathematical tools for pattern mining, in particular for condensed irredundant representations of pattern spaces and their efficient generation. Formal Concept Analysis (FCA) offers a generic framework, called pattern structures, to formalize many types of patterns, such as itemsets, intervals, graphs, and sequence sets. Moreover, FCA provides generic algorithms to generate irredundantly all closed patterns, the only condition being that the pattern space is a meet-semilattice. This does not always hold, e.g. for sequential and graph patterns. Here, we discuss pattern setups consisting of descriptions making just a partial order. Such a framework can be too broad, causing several problems, so we propose a new model, dubbed pattern multistructures, lying between pattern setups and pattern structures, which relies on multilattices. Finally, we consider some techniques, namely completions, transforming pattern setups to pattern structures using sets/antichains of patterns.

Keywords:

• Formal Concept Analysis
• order theory
• multilattices
• pattern setups
• pattern structures
• pattern multistructures

Acknowledgements

The work of Sergei O. Kuznetsov was implemented within the framework of the Basic Research Program at the National Research University Higher School of Economics (HSE) and supported within the framework of a subsidy by the Russian Academic Excellence Project “5–100”. We would like to thank also Mikhail Benado for the introduction of the concept of multilattices and we wish him a happy centenary.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 Sequence and graph patterns will be discussed in the next section, since they do not induce pattern structures directly, but the sets of incomparable patterns do.

2 $\mathcal{C}\left(E\right)$ is the set of convex subsets of E. The set $\mathcal{C}\left(\mathbb{R}\right)$ is the set of all possible intervals of $\mathbb{R}$, $\mathcal{C}(\mathbb{R}{)}^m$ is then the set of all axis-parallel m-dimensional hyper-rectangles.

3 We are grateful to Jozef Pócs for attracting my attention to Zorn's Lemma.

4 Note that ≦ does not induce an order in $\mathrm{\wp }\left(P\right)$, but just a pre-order, since the anti-symmetry does not hold (see Crampton and Loizou 2001). Indeed, consider poset $\left(\right\{a,b\},\le )$ where $a\le b$. Since $\downarrow \{a,b\}=\downarrow \left\{b\right\}=\{a,b\}$, we have $\{a,b\}\leqq \left\{b\right\}$ and $\left\{b\right\}\leqq \{a,b\}$. Yet, $\{a,b\}\ne \left\{b\right\}$. Therefore, ≦ does not induce an antisymmetric relation on $\left(\mathrm{\wp }\right(\{a,b\}),\leqq )$ but it is still reflexive and transitive (i.e., ≦ induces a preorder on $\mathrm{\wp }\left(\right\{a,b\left\}\right)$).

Additional information

Notes on contributors

Aimene Belfodil

Aimene Belfodil is a Doctor in Computer Science since 2019. He is currently working at Munic Car Data (https://www.munic.io/), a French company that is an international leader in vehicle telematics. His research interests are about ordered sets in pattern mining and data analysis. He has already published a series of papers in high-level venues, as well as participated in some of their program committees. He is also involved in the field of Formal Concept Analysis on which this article is about.

Sergei O. Kuznetsov

Sergei O. Kuznetsov is a Professor, Head of Department of Data Analysis and Artificial Intelligence at the National Research University Higher School of Economics (NRU HSE), Moscow, Russia. His interests are algorithmic complexity and algorithms in machine learning, formal concept analysis, mining complex data, and knowledge discovery. He is involved in the CLA, ICCS and ICFCA community among others and he chaired nine international conferences and numerous international workshops on FCA and Artificial Intelligence.

Mehdi Kaytoue

Mehdi Kaytoue is an Associate Professor at the “Institut National des Sciences Appliquées” since 2012 (INSA Lyon, France) and a member of the LIRIS Laboratory in Lyon (CNRS UMR 5205). He is currently working at Infologic (https://www.infologic-copilote.fr/), a company that edits and integrates software ERP solutions for the food industry. He has a large experience in data mining and applications, has already published a series of papers in high level venues, as well as participated in several of their program committees. He is also strongly involved in the field of Formal Concept Analysis on which this article is about.