voronoi diagram matlab

Question

I was wondering how I show/plot a voronoi diagram in the below FCM method? Also is there a method where you can watch the programme from the figure as it places and computes each point in matlab? Almost like a running trailer.

  [centers, U, objFun] = fcm(data, 6);
  plot(data(:,1), data(:,2),'o');
  maxU = max(U);
  index1 = find(U(1, :) == maxU);
  index2 = find(U(2, :) == maxU);
  line(data(index1,1),data(index1, 2),'linestyle','none',...
 'marker','*','color','g');
  line(data(index2,1),data(index2, 2),'linestyle','none',...
 'marker', '*','color','r');

Answer 1

This should be the same for k-means and FCM, btw.

To get the Voronoi diagram, you need to compute the Delaunay triangulation, then place a side of the Voronoi diagram orthogonal on the mean of each Delaunay edge.

There are efficient algorithms for Delaunay in at least 2D and 3D. This is quite closely related to computing the convex hull. Plus, as you don't have many cluster centers, the scalability is not that hard.

However, you have one big problem: your data is 6 dimensional. This means that the sides of your Voronoi cells are in fact 5-dimensional, and they will not trivially map to a reasonable 2d projection.

Computing the Voronoi diagram in the 2D projection that you are using however will be inaccurate. You could try to compute the Voronoi cells in 6D, and map all the corners of the voronoi cells into 2D, then connect neighboring corners. But that may yield a big mess of lines, and is not particularly helpful IMHO.

Sorry, as far as I know, Voronoi cell visualization is mostly useful for understanding k-means in 2D and if you have a good 3D visualization engine in 3D.

Don't get me wrong: Voronoi cells is exactly what k-means cluster look like. They're not spheres or blobs or stars. They are Voronoi cells: the cell exactly is the area that would be assigned to a particular mean.

Have a look at this image from Wikipedia:

The black lines are the borders (which in a 2D data set are simple 1d lines) that separate the clusters. In the top center there is a blue object just right of the line. It is blue, because it is on the right of the line - it is in the Voronoi cell of the blue mean.

This is a key drawback of k-means: it does not have the notion of size as in spatial extend for a cluster. They only have a center, and the data is split on the orthogonal hyperplane inbetween of two neighboring centers. For this particular data set, k-means *does not have a chance to split the data correctly! It hasn't converged to a "bad" local minimum, but the correct solution cannot be found by k-means, because the clusters have different size (and there is not enough gap inbetween for k-means to be lucky). To properly cluster this data set, you actually need an EM-like notion of cluster size or a density based method. If k-means were able to detect that the green clusters is about twice as big as the blue ones, it would probably work much better (but then it almost were EM already anyway)