<p>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.</p>

<p>Quite recently, Richard Émilion published in <em>Discrete Applied Mathematics</em> the average and the variance of the number of (frequent) closed itemsets in a rectangular 0/1 matrix with a Bernoulli distribution of the '1's: <a href="http://www.univ-orleans.fr/mapmo/membres/emilion/publ/sizeofgl.pdf" rel="nofollow">http://www.univ-orleans.fr/mapmo/membres/emilion/publ/sizeofgl.pdf</a></p>

<p>That is interesting because real-life datasets usually are very sparse. I am not aware of any bound of the number of (closed) itemsets w.r.t. the density. I believe the formula would not be beautiful at all!</p>

<p>I have already told that to a3nm at ICDT'14: you guys (I am not a theorist, just a data miner) want to read about the so-called "Formal Concept Analysis" (FCA): <a href="https://en.wikipedia.org/wiki/Formal_concept_analysis" rel="nofollow">https://en.wikipedia.org/wiki/Formal_concept_analysis</a></p>

CC BY-SA 3.0
2014-05-06T11:10:10.267Z
2014-05-07T00:44:03.980Z
2014-05-07T00:44:03.980Z
Magic Banana
<p>Given a set $I$ of $n$ items, and a collection $D$ of $m&lt;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. </p>

<p>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. </p>

<p>Any suggestion/reference? Thank you.</p>

CC BY-SA 3.0
2014-05-05T20:52:26.107Z
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?
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-05-05T20:54:26.820Z
Sorry, I should specify that $D$ has some fixed size $m< 2^n$. Edited the question accordingly.
Matteo
CC BY-SA 3.0
2014-05-05T21:42:03.877Z
@Saeed: I suppose the goal is to have a bound that is a function of $n$ and $m$.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-05-05T21:56:00.933Z
@a3nm, In that case m-n seems to be a (almost) tight upper bound.
Saeed
CC BY-SA 3.0
2014-05-05T21:57:27.980Z
@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.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-05-05T22:00:09.940Z
@a3nm, When we have no knowledge on B, my bound is good enough, because we can suppose m is much more larger than n, so we have something like m-n, if you have m<n or m linear to n, then just a simple case analysis works (your special case is m < n, and such special cases happens very rarely according to the problem definition with natural assumption).
Saeed
CC BY-SA 3.0
2014-05-05T22:06:17.137Z
Right now I think my bound even for big m is not good. By the way problem is not interesting (for me) at all ;) Because I cannot see how the tight upper bound can be useful, and why finding such an upperbound should naturally be interesting :)
Saeed
<co.combinatorics><upper-bounds><data-mining>
Upper bound to number of closed itemsets
Matteo
# Upper bound to number of closed itemsets

(Asked by: username_0 on 2014-05-05)

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.

**Tags:** co.combinatorics, upper-bounds, data-mining
> **Comments:**
> **username_1**: 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?  
> **username_0**: Sorry, I should specify that $D$ has some fixed size $m< 2^n$. Edited the question accordingly.  
> **username_1**: @Saeed: I suppose the goal is to have a bound that is a function of $n$ and $m$.  
> **username_2**: @a3nm, In that case m-n seems to be a (almost) tight upper bound.  
> **username_1**: @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.  
> **username_2**: @a3nm, When we have no knowledge on B, my bound is good enough, because we can suppose m is much more larger than n, so we have something like m-n, if you have m<n or m linear to n, then just a simple case analysis works (your special case is m < n, and such special cases happens very rarely according to the problem definition with natural assumption).  
> **username_2**: Right now I think my bound even for big m is not good. By the way problem is not interesting (for me) at all ;) Because I cannot see how the tight upper bound can be useful, and why finding such an upperbound should naturally be interesting :)  

---

## 1 answers

### Answer by username_3 on 2014-05-06. Score: 3

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.

Quite recently, Richard Émilion published in *Discrete Applied Mathematics* the average and the variance of the number of (frequent) closed itemsets in a rectangular 0/1 matrix with a Bernoulli distribution of the '1's: <http://www.univ-orleans.fr/mapmo/membres/emilion/publ/sizeofgl.pdf>

That is interesting because real-life datasets usually are very sparse. I am not aware of any bound of the number of (closed) itemsets w.r.t. the density. I believe the formula would not be beautiful at all!

I have already told that to a3nm at ICDT'14: you guys (I am not a theorist, just a data miner) want to read about the so-called "Formal Concept Analysis" (FCA): <https://en.wikipedia.org/wiki/Formal_concept_analysis>


---

