# Why does Clustering violate the iid assumption?

I am aware of the i.i.d assumption for data in supervised learning models, namely that data is identically and independently distributed. However I don't understand how/why Clustering violates this assumption.

• Is your question about cluster analysis or about modeling in clustered/nested populations? – ttnphns May 9 '18 at 16:47
• What is the formal version of "the IID assumption"? If you assume there are two clusters, these two clusters are assumed to have different distribution. – Has QUIT--Anony-Mousse May 9 '18 at 18:11
• @ttnphns It was indeed about cluster analysis - more specifically I was reading about k-means clustering in my introductory Machine Learning textbook. – lostAtLife May 10 '18 at 15:46

The basic premise of clustering is that there may be some relationship between the individuals in each cluster. I'm not sure that it's correct to say that the independence is automatically violated because of clustering, though. In fact, when we do hierarchical (i.e. clustered) modeling, we first check the level of clustering by calculating the intra-class correlation (ICC) and design effect (DEFF). If those aren't very large (typically over 0.05 or 2, respectively), some feel it's acceptable to ignore the clustering.

I should note that many researchers (I should have a citation here) feel that hierarchical modeling should always be used if there is any clustering in the data.

• This answer could be irrelevant if the question (which is not quite clear by now) is about cluster analysis, a unsuperviced technique – ttnphns May 9 '18 at 16:50
• Ah, good point. I'm biased based on my own recent work in hierarchical modeling! – dankernler May 9 '18 at 17:31

It is arguably easier to see why clustering violates IID assumption from the perspective of a generative model. The generative model is like a story or a blueprint that tells what process generates the observed data. If the generated data are indistinguishable from the observed data, one can be quite certain about the process and perform many inference tasks.

The story goes like this:

1. Define number of clusters $K$
2. Initialize cluster pick probabilities vector $\pi = (\pi_1, \ldots, \pi_K)$
3. Initialize cluster distributions $p(x|C)$
4. Initialize data point assignments $z_i$ (eg. randomly)
5. For each data point $x_i$
1. Sample cluster assignment $j \sim Dirichlet(\pi)$ according to the pick probabilities vector $\pi$
2. Sample data point from the selected cluster $x_i \sim p(x|C_j)$
6. Return dataset

As you can see, the process starts with generating the cluster pick followed by sampling a data point from it. Any data points generated from the same cluster violate IID - they are coming from the same distribution (eg. Gaussian).

I suggest to find a good introductory text on Gaussian Mixture Model (or Bernoulli Mixture Model) to get more details.

• I think you are missing a "not" in your explanation. – Has QUIT--Anony-Mousse May 9 '18 at 18:10

In my opinion as an undergraduate student, the i.i.d. is the assumption on the distribution of the sample data. So simply, it just wants the sample data to be random if the data is random the law of large number hold because if you collect more of the data randomly the most frequency out of all in the population will be the average(the most frequency one) and also the other less frequency will form the shape of the normal distribution as the number of samples is large. But when it is clustering, for example, you use data that collect from New York City to represent the whole population of the USA it will be wrong because that clustering will only give the most frequency one in New York City not the most frequency one in the USA and also the result that you give can be totally different.