14
$\begingroup$

I know that this question is not well defined, but some clusters tend to be elliptical or lie in lower dimensional space whilst the other have nonlinear shapes (in 2D or 3D examples).

Is there any measure of nonlinearity (or "shape") of clusters?

Note that in 2D and 3D space, it is not a problem to see the shape of any cluster, but in higher dimensional spaces it is problem to say something about shape. In particular, are there any measures of how convex cluster is?

I was inspired for this question by many other clustering questions where people talk about clusters but nobody is able to see them (in higher dimensional spaces). Moreover, I know that there are some measures of nonlinearity for 2D curves.

$\endgroup$
4
$\begingroup$

I like Gaussian Mixture models (GMM's).

One of their features is that, in probit domain, they act like piecewise interpolators. One implication of this is that they can act like a replacement basis, a universal approximator. This means that for non-gaussian distributions, like lognormal, weibull, or crazier non-analytic ones, as long as some criteria are met - the GMM can approximate the distribution.

So if you know the parameters of the AICc or BIC optimal approximation using GMM then you can project that to smaller dimensions. You can rotate it, and look at the principal axes of the components of the approximating GMM.

The consequence would be an informative and visually accessible way to look at the most important parts of higher dimensional data using our 3d-viewing visual perception.

EDIT: (sure thing, whuber)

There are several ways to look at the shape.

  • You can look at trends in the means. A lognormal is approximated by a series of Gaussians whos means get progressively closer and whose weights get smaller along the progression. The sum approximates the heavier tail. In n-dimensions, a sequence of such components would make a lobe. You can track distances between means (convert to high dimension) and direction cosines between as well. This would convert to much more accessible dimensions.
  • You can make a 3d system whose axes are the weight, the magnitude of the mean, and the magnitude of the variance/covariance. If you have a very high cluster-count, this is a way to view them in comparison with each other. It is a valuable way to convert 50k parts with 2k measures each into a few clouds in a 3d space. I can execute process control in that space, if I choose. I like the recursion of using gaussian mixture model based control on components of gaussian mixture model fits to part parameters.
  • In terms of de-cluttering you can throw away by very small weight, or by weight per covariance, or such.
  • You can plot the GMM cloud in terms of BIC, $ R^2$, Mahalanobis distance to components or overall, probability of membership or overall.
  • You could look at it like bubbles intersecting. The location of equal probability (zero Kullback-Leibler divergence) exists between each pair of GMM clusters. If you track that position, you can filter by probability of membership at that location. It will give you points of classification boundaries. This will help you isolate "loners". You can count the number of such boundaries above the threshold per member and get a list of "connectedness" per component. You can also look at angles and distances between locations.
  • You can resample the space using random numbers given the Gaussian PDFs, and then perform principle component analysis on it, and look at the eigen-shapes, and eigenvalues associated with them.

EDIT:

What does shape mean? They say specificity is the soul of all good communication. What do you mean about "measure"?

Ideas about what it can mean:

  • Eyeball norm sense/feels of general form. (extremely qualitative, visual accessibility)
  • measure of GD&T shape (coplanarity, concentricity, etc) (extremely quantitative)
  • something numeric (eigenvalues, covariances, etc...)
  • a useful reduced dimension coordinate (like GMM parameters becoming dimensions)
  • a reduced noise system (smoothed in some way, then presented)

Most of the "several ways" are some variation on these.

$\endgroup$
3
$\begingroup$

This might be rather simplistic, but you might get some insight by doing an eigenvalue analysis on each of your clusters.

What I would try is to take all points assigned to a cluster and fit them with a multivariate Gaussian. Then you can compute the eigenvalues of the fitted covariance matrix and plot them. There are many ways to do this ; perhaps the most well-known and widely used is called principal component analysis or PCA.

Once you have the eigenvalues (also called a spectrum), you can examine their relative sizes to determine how "stretched out" the cluster is in certain dimensions. The less uniform the spectrum, the more "cigar-shaped" the cluster is, and the more uniform the spectrum, the more spherical the cluster is. You could even define some sort of metric for indicating how non-uniform the eigenvalues are (spectral entropy ?) ; see http://en.wikipedia.org/wiki/Spectral_flatness.

As a side benefit, you can examine the principal components (the eigenvectors associated with large eigenvalues) to see "where" the "cigar-shaped" clusters are pointing in your data space.

Naturally this is a crude approximation for an arbitrary cluster, as it only models the points in the cluster as a single ellipsoid. But, like I said, it might give you some insight.

$\endgroup$
  • $\begingroup$ +1 Simplistic, maybe; but this looks effective and practical. There does not seem to be any advantage to the multivariate Gaussian fitting: just use the SVD of the centered within-cluster data (which is essentially PCA on the cluster). $\endgroup$ – whuber Aug 29 '13 at 17:13
  • $\begingroup$ @whuber yes, I think of those as doing the same thing ! The fitting is more what the theory says is happening behind the scenes, while PCA is a concrete implementation of that process. I'll edit my answer to make this more clear. $\endgroup$ – lmjohns3 Aug 29 '13 at 17:24
2
$\begingroup$

Correlation clustering algorithms such as 4C, ERiC or LMCLUS usually consider clusters to be linear manifolds. I.e. k-dimensional hyperplanes in a d-dimensional space. Well, for 4C and ERiC only locally linear, so they can in fact be non-convex. But they still try to detect clusters of a reduced local dimensionality.

Finding arbitrary shaped clusters in high dimensional data is a quite tough problem. In particular, because of the curse of dimensionality which lets the search space explode and at the same time also requires that you have a much larger input data if you still want significant results. Way too many algorithms don't pay attention to whether what they find is still significant or could as well be random.

So in fact I believe there are other problems to solve before thinking about the convexity of non-convexity of complex clusters in high-dimensional space.

Also have a look at the complexity of computing the convex hull in higher dimensions...

Also, do you have a true use case for that beyond curiosity?

$\endgroup$
2
$\begingroup$

If your dimensionality is not much higher than 2 or 3, then it might be possible to project the cluster of interest into 2D space multiple times and visualize the results or use your 2D measurement of nonlinearity. I thought of this because of the method Random Projections http://users.ics.aalto.fi/ella/publications/randproj_kdd.pdf.

Random projections can be used to reduce the dimensionality in order to build an index. The theory is that if two points are close in D dimensions and you take a random projection into d dimensions with d

For concreteness, you can think of projecting a globe onto a flat surface. No matter how you project it New York and New Jersey are going to be together, but only rarely will you push New York and London together.

I don't know if this can help you rigorously but it might be a quick way to visualize the clusters.

$\endgroup$

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.