How to measure shape of cluster?

Question

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.

Answer 1

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?

Answer 2

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.