# Upper bound to number of closed itemsets

Given a set $I$ of $n$ items, and a collection $D$ of $m<2^n$ subsets of $I$, a closed itemset is a subset $A$ of $I$ that is contained in strictly more elements of $D$ than any of its proper supersets. Closed itemsets are important in data mining because they provide a compact representation of the dataset.

I'm trying to find some non-trivial upper bound to the number of closed itemsets. It seems a natural combinatorial question and I'm surprised I can't find anything non-trivial.

Any suggestion/reference? Thank you.

• If my collection $D$ contains each possible subset of $I$ exactly once, wouldn't all possible itemsets be closed according to your definition, hence proving that no trivial upper bound is possible in general? – a3nm May 5 '14 at 20:52
• Sorry, I should specify that $D$ has some fixed size $m< 2^n$. Edited the question accordingly. – Matteo May 5 '14 at 20:54
• @Saeed: I suppose the goal is to have a bound that is a function of $n$ and $m$. – a3nm May 5 '14 at 21:42
• @a3nm, In that case m-n seems to be a (almost) tight upper bound. – Saeed May 5 '14 at 21:56
• @Saeed: No, for D = {{A, B}, {A, C}}, the closed itemsets are {A, B}, {A, C}, and {A}, so I think your bound is wrong. – a3nm May 5 '14 at 21:57

The bound is $2^{\min(n, m)}$. It is an upper bound because no two "formal concepts" (i.e., closed itemsets with their respective transaction sets) can have the same subset of items or the same subset of transactions. Considering $D$ as an $n$ by $m$ matrix of $0$ or $1$ such that each cell indicates whether item $i$ is part of the $j$-th transaction of $D$, you can reach the bound by filling the matrix to '1' and setting to '0' a "diagonal" (well, not really a diagonal since the matrix is rectangular). If you wish, you can then permute the rows and/or the columns and the number of closed itemsets obviously remains the same. Any number of '1' out of the square matrix where there is the diagonal can be turned into '0' too.