2
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – Antoine Amarilli 'a3nm'
    Commented May 5, 2014 at 20:52
  • $\begingroup$ Sorry, I should specify that $D$ has some fixed size $m< 2^n$. Edited the question accordingly. $\endgroup$
    – Matteo
    Commented May 5, 2014 at 20:54
  • $\begingroup$ @Saeed: I suppose the goal is to have a bound that is a function of $n$ and $m$. $\endgroup$
    – Antoine Amarilli 'a3nm'
    Commented May 5, 2014 at 21:42
  • $\begingroup$ @a3nm, In that case m-n seems to be a (almost) tight upper bound. $\endgroup$
    – Saeed
    Commented May 5, 2014 at 21:56
  • $\begingroup$ @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. $\endgroup$
    – Antoine Amarilli 'a3nm'
    Commented May 5, 2014 at 21:57

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.