<p>A range space is just a pair $(X,\mathcal{R})$ where $X$ is a finite or infinite set and a  $\mathcal{R}$ is a finite or infinite collection of subsets of $X$ (the elements of $\mathcal{R}$ are called "ranges").</p>

<p>Note that a range space is not used to "represent" the VC-dimension (whatever meaning of "represent" you are using). Rather, the VC-dimension is a property of the range space.</p>

CC BY-SA 3.0
2018-03-14T14:38:36.177Z
2018-03-15T13:33:56.770Z
2018-03-15T13:33:56.770Z
Matteo
<p>Can someone please explain to me (with normal language) - how is VC dimension related to data mining (frequent itemset mining - PAC learning). (incl. how we define range space as it's written in Matteo Riondate and Eli Upfal (Brown University) as it's really hard for me to understand what they mean)</p>

<p>More precisely I'm interested in the definition of range space and how it used to represent the VC dimension (you could say I'm looking for a conceptual presentation of what they are using to define it in that context)</p>

<p>Here's how it is defined:</p>

<pre><code>Definition 11. Let D be a dataset of transactions that are subsets of a ground set I. We
define S = (X, R) to be a range space associated with D such that:
1. X = D is the set of transactions in the dataset.
2. R = {TD(W) | W ⊆ I} is a family of sets of transactions such that for each
itemset W ⊆ I, the set TD(W) = {τ ∈ D | W ⊆ τ} of all transactions containing
W is an element of R.
</code></pre>

CC BY-SA 3.0
2018-03-14T11:28:12.933Z
As much as I wish I could answer a question on my own paper, this looks like homework to me.
Matteo
CC BY-SA 3.0
2018-03-14T13:46:12.000Z
@Matteo thank you for your reply. No it’s not for my homework. My homework is to understand your paper, and I currently cannot understand the definition of range space intuitively
Christo S. Christov
CC BY-SA 3.0
2018-03-14T14:28:25.027Z
A range space is just a collection of sets. I don't understand what additional intuition one can give about what "a collection of sets" is. Maybe there is a more specific question, for example about how the define the range space associated with a dataset in their frequent itemset mining paper?
Sasho Nikolov
CC BY-SA 3.0
2018-03-14T16:16:17.420Z
@SashoNikolov of course, in the context of frequent itemset mining(as it's explained as: (X,R) where X is the universe of items(conceptually) and R is a family of subsets, X is quite clear, but R is not so much in that context
Christo S. Christov
CC BY-SA 3.0
2018-03-14T17:17:37.363Z
$X$ is not the universe of items. As clearly written in the definition that you cite, $X$ is the set of transactions in the dataset.
Matteo
CC BY-SA 3.0
2018-03-14T21:40:22.687Z
@Matteo ah yes this is what I meant, apologies.
Christo S. Christov
<vc-dimension><data-mining>
VC dimension in data mining
Christo S. Christov
# VC dimension in data mining

(Asked by: username_0 on 2018-03-13)

Can someone please explain to me (with normal language) - how is VC dimension related to data mining (frequent itemset mining - PAC learning). (incl. how we define range space as it's written in Matteo Riondate and Eli Upfal (Brown University) as it's really hard for me to understand what they mean)
More precisely I'm interested in the definition of range space and how it used to represent the VC dimension (you could say I'm looking for a conceptual presentation of what they are using to define it in that context)
Here's how it is defined:
Definition 11. Let D be a dataset of transactions that are subsets of a ground set I. We
define S = (X, R) to be a range space associated with D such that:
1. X = D is the set of transactions in the dataset.
2. R = {TD(W) | W ⊆ I} is a family of sets of transactions such that for each
itemset W ⊆ I, the set TD(W) = {τ ∈ D | W ⊆ τ} of all transactions containing
W is an element of R.

**Tags:** vc-dimension, data-mining
> **Comments:**
> **username_1**: As much as I wish I could answer a question on my own paper, this looks like homework to me.  
> **username_0**: @Matteo thank you for your reply. No it’s not for my homework. My homework is to understand your paper, and I currently cannot understand the definition of range space intuitively  
> **username_2**: A range space is just a collection of sets. I don't understand what additional intuition one can give about what "a collection of sets" is. Maybe there is a more specific question, for example about how the define the range space associated with a dataset in their frequent itemset mining paper?  
> **username_0**: @SashoNikolov of course, in the context of frequent itemset mining(as it's explained as: (X,R) where X is the universe of items(conceptually) and R is a family of subsets, X is quite clear, but R is not so much in that context  
> **username_1**: $X$ is not the universe of items. As clearly written in the definition that you cite, $X$ is the set of transactions in the dataset.  
> **username_0**: @Matteo ah yes this is what I meant, apologies.  

---

## 1 answers

### Answer by username_1 on 2018-03-14. Score: 1

A range space is just a pair $(X,\mathcal{R})$ where $X$ is a finite or infinite set and a $\mathcal{R}$ is a finite or infinite collection of subsets of $X$ (the elements of $\mathcal{R}$ are called "ranges").

Note that a range space is not used to "represent" the VC-dimension (whatever meaning of "represent" you are using). Rather, the VC-dimension is a property of the range space.


---

