Wikipedia says that:
VC dimension is the cardinality of the largest set of points that a algorithm can shatter.
For instance, a linear classifier has a cardinality n+1. My question is why do we care? Most datasets that you do linear classification on tend to very large and contain a lot of points.
What is the VC dimension
As mentioned by @CPerkins the VC dimension is a measure of a model's complexity. It also can be defined with regard to the ability to shatter datapoints like, as you mentioned, wikipedia does.
The basic problem
The following image (taken from here) shows some Models ($\mathcal{S_1}$ up to $\mathcal{S_k}$) of differing complexity (VC dimension), here shown on the x-axis and called $h$.
The images shows that a higher VC dimension allows for a lower empirical risk (the error a model makes on the sample data), but also introduces a higher confidence interval. This interval can be seen as the confidence in the model's ability to generalize.
Low VC dimension (high bias)
If we use a model of low complexity, we introduce some kind of assumption (bias) regarding the dataset e.g. when using a linear classifier we assume the data can be described with a linear model. If this is not the case, our given problem can not be solved by a linear model, for example because the problem is of nonlinear nature. We will end up with a bad performing model which will not be able to learn the data's structure. We should therefore try to avoid introducing a strong bias.
High VC dimension (greater confidence interval)
On the other side of the x-axis we see models of higher complexity which might be of such a great capacity that it will rather memorize the data instead of learning it's general underlying structure i.e. the model overfits. After realizing this problem it seems that we should avoid complex models.
This may seem controversial as we shall not introduce a bias i.e. have low VC dimension but should also do not have high VC dimension. This problem has deep roots in statistical learning theory and is known as the bias-variance-tradeoff. What we should do in this situation is to be as complex as necessary and as simplistic as possible, so when comparing two models which end up with the same empirical error, we should use the less complex one.
I hope I could show you that there is more behind the idea of VC dimension.
VC dimension is the number of bits of information (samples) one needs in order to find a specific object (function) among a set of $N$ objects (functions).
$VC$ dimension comes from a similar concept in the information theory. The information theory started from the Shannon's observation of the following:
If you have $N$ objects and among these $N$ objects you're looking for a specific one. How many bits of information do you need to find this object? You can split your set of objects into two halfs and ask "In what half the object that I'm looking for is located?". You receive "yes" if it is in the first half or "no", if it is in the second half. In other words, you receive 1 bit of information. After that, you ask the same question and split your set again and again, until you finally find your desired object. How many bits of information do you need (yes/no answers)? It's clearly $log_2(N)$ bits of information - similarly to binary search problem with the sorted array.
Vapnik and Chernovenkis asked a similar question in pattern recognition problem. Suppose you have a set of $N$ functions s.t. given input $x$, each function outputs yes or no (supervised binary classification problem) and among these $N$ functions you are looking for a specific function, that gives you correct results yes/no for a given dataset $D=\{(x_1,y_1), (x_2, y_2), ..., (x_l, y_l)\}$. You can ask the question: "Which functions do return no and which functions do return yes for a given $x_i$ from your dataset. Since you know what the real answer is from the training data you have, you can throw away all the functions that give you wrong answer for some $x_i$. How many bits of information do you need? Or in other words: How many training examples do you need to remove all those wrong functions?. Here it is a small difference from the Shannon's observation in information theory. You aren't splitting your set of functions to exactly half (maybe just only one function out of $N$ gives you incorrect answer for some $x_i$), and maybe, your set of functions is very big and it's sufficient for you find a function that is $\epsilon$-close to your desired function and you want to be sure that this function is $\epsilon$-close with probability $1-\delta$ ($(\epsilon, \delta)$-PAC framework), the number of bits of information (number of samples) you need will be $\frac{log_2N/\delta}{\epsilon}$.
Suppose now that among the set of $N$ functions there is no function that does not commit errors. As previously, it is enough for you to find a function that is $\epsilon$-close with probability $1-\delta$. The number of samples you would need is $\frac{log_2N/\delta}{\epsilon^2}$.
Note that results in both cases are proportional to $log_2N$ - similar to the binary search problem.
Now suppose that you have an infinite set of functions and among those functions you want to find the function that is $\epsilon$-close to the best function with probability $1-\delta$. Suppose (for simplicity of illustration) that the functions are affine continuous (SVM) and you have found a function that is $\epsilon$-close to the best function. If you would move your function a little bit s.t. it won't change the results of the classification you would have a different function that classifies with the same results as the first one. You can take all such function that give you the same classification results (classification error) and count them as a single function because they classify your data with the exact same loss (a line in the picture).
___________________Both lines (function) will classify the points with the same success___________________
How many samples do you need to find a specific function from a set of sets of such functions (recall that we had devided our functions to the sets of functions where each function gives the same classification results for a given set of points)? This is what the $VC$ dimension tells - $log_2N$ is replaced by $VC$ because you have an infinite number of continuous functions that are divided to a sets of functions with the same classification error for specific points. The number of samples you would need is $\frac{VC -log(\delta)}{\epsilon}$ if you have a function that recognizes perfectly and $\frac{VC - log(\delta)}{\epsilon^2}$ if you don't have a perfect function in your original set of functions.
That is, $VC$ dimension gives you an upper bound (that cannot be improved btw) for a number of samples you need in order to achieve $\epsilon$ error with probability $1-\delta$.
The VC dimension is a measure of the complexity of the model. For example, given the VC dimension Dvc, a good rule of thumb is that you should have n = 10xDvc data points given the complexity of your model.
You can also use it to create an upper bound on the test error.
