5
$\begingroup$

The question is in the title. But I would also like to know, if it is different, what is the essence of the difference?

$\endgroup$
  • $\begingroup$ Uhm, they clearly have not much in common? Why do you think they are the same? $\endgroup$ – Has QUIT--Anony-Mousse May 20 '16 at 17:35
4
$\begingroup$

The algorithms are completely different. The only common thing between them is that they both are clustering algorithms.

K-means searches for K centers, and attachment of points to them, such that:

  • each point is attached to the closest center
  • each center is the average (center of gravity) of all points attached to it

It is done iteratively. We start from random centers, attach each point to the closest center, move each center to the average of points attached to it, reattach each point to the closest center, move each center the average of points attached to it now, and so on until the iterations converge.

At the end we have K centers, each one "owns" all points which are closer to it than to any other center.

The hidden assumption is that there are K "real" clusters, each one is normally distributed around its center, and all normal distributions are spherical and have the same radius.


Support vector clustering has the following idea: let us transform the points from their space to a higher dimensionality feature space. Find a minimal enclosing sphere in this feature space. In the original space, the sphere becomes a set of disjoing regions. Each region becomes a cluster. (There are also important details like how we choose the feature space, and how we do the transformation, and how we define disjoint regions.)

These disjoint regions are completely different from the regions around K centers in the K-means algorithm. For example, in 2 dimensions, the K-means regions are polygons. The regions of SVC are amoeba-like areas.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

They are different.

The high level difference is that k-means doesn't use a kernel, and so has black and white boundaries between clusters, where SVC uses a Gaussian kernel. The significance of the kernel is that it allows for a smooth transition at the boundary rather than a hard change.

The paper introducing Support Vector Clustering is by Horn, Ben-Hur, Siegelman and Vapnick (2001) and available here - http://www.jmlr.org/papers/volume2/horn01a/rev1/horn01ar1.pdf.

However, to understand how the decision boundary in a support vector works, it might be more useful to start with something like the wikipedia page on Support Vector Machines or this earlier CV answer: Help me understand Support Vector Machines

I see that in an answer to another question you asked, it was suggested to read the Elements of Statistical Learning by Hastie, et al. The explanation of the decision boundaries in k-means and support vector machines is especially good in this text.

| cite | improve this answer | |
$\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.