Data complexity: An FCA-based approach

International Journal of Approximate Reasoning. 2024. Vol. 165. Article 109084.

Buzmakov A. V., Dudyrev E., Kuznetsov S., Makhalova T., Napoli A.

In this paper we propose different indices for measuring the complexity of a dataset in terms of Formal Concept Analysis (FCA). We extend the lines of the research about the “closure structure” and the “closure index” based on minimum generators of intents (aka closed itemsets). We would try to capture statistical properties of a dataset, not just extremal characteristics, such as the size of a passkey. For doing so we introduce an alternative approach where we measure the complexity of a dataset w.r.t. five significant elements that can be computed in a concept lattice, namely intents (closed sets of attributes), pseudo-intents, proper premises, keys (minimal generators), and passkeys (minimum generators). Then we define several original indices allowing us to estimate the complexity of a dataset. Moreover we study the distribution of all these different elements and indices in various real-world and synthetic datasets. Finally, we investigate the relations existing between these significant elements and indices, and as well the relations with implications and association rules.

Keywords: Formal concept analysis, Data complexity, Closed set and generator, Distributivity index, Linearity index, Real-world and synthetic dataset