Let's say I have the data set $x_i,y_i,z_i$, where $z_i=y_i-x_i$ or $z_i=f(x_i,y_i)$.

Can I run clustering algorithms on this data set? I wanted to add non-linear or linear combinations of variables because they may have information that is useful for clustering. I'm not sure the clustering algorithms can detect these relationships themselves.

As an extreme case, I want to consider a perfect collinearity. If these algos can be applied to perfectly collinear data, then they surely can be applied to nonlinear relationships.

There's a similar question on k-means clustering, but it's not satisfactory for two reasons. It's about k-means specifically, and my question is more general clustering. Second, it doesn't have an accepted answer, because the answers are not complete.

  • 1
    $\begingroup$ possible duplicate of Do I need to drop variables that are collinear before running kmeans? $\endgroup$ – le_andrew Apr 20 '15 at 19:56
  • $\begingroup$ There's no answer there even for k-means, and my question is more general clustering. $\endgroup$ – Aksakal Apr 20 '15 at 19:58
  • $\begingroup$ Thanks for elaborating. We are a little beyond my clustering expertise now, but working through some examples using perfect collinearity, the center for your $z$ variable, using your linear combination, will always be equal to the center for your $x$ variable minus the center for your $y$ variable. Similarly, if you have 2 variable, and $x=y$ the values for $x$ and $y$ of your centers will be the same. When they are not perfectly collinear, the results are similar, but with error. So, the clustering "detects" the relationship, in a way. $\endgroup$ – le_andrew Apr 20 '15 at 20:06

You can always apply the algorithms to any data sets. You can also always pre-whiten (or drop the columns that cause collinearity) from your data matrix. The question, IMO, is therefore not whether these algorithms can be computed on (nearly) collinear data matrices $\pmb X$ but whether the estimates you obtain from these clustering algorithms are affected by the covariance structure of the data.

(The argument below can be slightly modified to also account for soft clustering algorithms, but that would make the explanation more complex because it will require the introduction of a weight function, so for simplicity's sake I will stick to hard clustering algorithms.)

Given $\pmb X$ an $n$ by $p$ dataset with rows $\{\pmb x_i\}_{i=1}^n$, a hard clustering algorithm realizes a partition of $\{1:n\}$ into $J>1$ non overlapping subsets $\{C_j\}_{j=1}^J$.

Consider the results of such a partition. The argument below could be made of other estimates derived from the partitions $\{C_j\}_{j=1}^J$ (see paper linked below) but for simplicity's sake I will keep the focus on the estimated cluster centres $\{\pmb t(\pmb X,C_j)\}_{j=1}^J$: each $\pmb t(\pmb X,C_j)$ is a $p$-vector and gives a location estimate for the corresponding cluster. For example, $\pmb t(\pmb X,C_j)$ could be the intra cluster mean:

$$\pmb t(\pmb X,C_j)=\mbox{ave}_{i\in C_j} \pmb x_i$$

A location estimator $\pmb t(\pmb X,C_j)$ for which it holds that:

$$(1)\quad \pmb t(\pmb A\pmb X,C_j)=\pmb A \pmb t(\pmb X,C_j)$$ for any non singular $p$ by $p$ matrix $\pmb A$ is said to be affine equivariant.

From a statistical point of view, affine equivariant location estimates are not affected by the covariance structure of the data matrix $\pmb X$. This is because when a non singular transformation is applied to the data, these estimates transforms like the data. Therefore, they yield statistically equivalent estimates whether they are ran on $\pmb X$ or on a whitened copy of $\pmb X$. This definition can be extended to also hold even if some columns of $\pmb X$ are nearly collinear (a related but stronger property called exact fit insures that the location estimates also transform like the data when $\pmb X$ contains exactly collinear columns or when $\pmb A$ is singular).

My understanding is that the OP is essentially asking (at the minimum) for clustering methods that yield affine equivariant estimates (from a statistical point of view, such estimates would not be affected by the covariance structure of the data). At the maximum, the OP is asking for clustering methods that yield estimates having the exact fit property.

A well known result [0] (ungated copy) is that $(1)$ (and the exact fit property) holds only if $\#\{C_j\}/n>1/2$. This condition excludes all clustering methods as defined in the intro to this answer.

  • (0) H. P. Lopuhaa and P. J. Rousseeuw (1991). Breakdown Points of Affine Equivariant Estimators of Multivariate Location and Covariance Matrices. Ann. Statist. Volume 19, Number 1, 229-248.

If you can define a good distance function, then distance based algorithms will work just fine on the transformed data.

If your preprocessing was not good, then the results are likely to suffer even more.

Plus, you will be bitten by the curse of dimensionality earlier. The more features you add, the more even the relative distances get - everything is similar/disssimilar the same way.

  • $\begingroup$ What if I don't have a good distance measure? If I had distance I wouldn't need clustering $\endgroup$ – Aksakal Apr 21 '15 at 0:32
  • $\begingroup$ Then clustering will not help you. It's not capable of doing magic. It needs your help more than any other method, or the results will be useless. $\endgroup$ – Anony-Mousse Apr 21 '15 at 4:29

The following is not an attempt to comprehensively answer your interesting (+1) question, but rather conveniently store and share with you and others some relevant, in my opinion, papers:


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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