9
$\begingroup$

Apparently, for K-means clustering, the decision boundary for whether a data point lies in cluster $A$ or cluster $A'$ is linear.

I don't quite understand this statement. Why is it linear? Every iteration of K-means clustering, I reassign data points to clusters to minimize square error. Then, I reassign the prototypes (centers of the clusters) to minimize error again.

How do these processes create a "linear decision boundary"?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
12
$\begingroup$

There are linear and non-linear classification problems. In a linear problem, you can draw lines, planes or hyperplanes (depending on the number of dimensions in your problem) in order to classify all your data points correctly. In a non-linear problem, you can't do that. As you know, lines, planes or hyperplanes are called decision boundaries.

K-means clustering produces a Voronoi diagram which consists of linear decision boundaries. For example, this presentation depicts the clusters, the decision boundaries (slide 34) and describes briefly the Voronoi diagrams, so you can see the similarities. On the other hand, neural networks depending on the number of hidden layers are able to deal with problems with non-linear decision boundaries. Finally, support vector machines in principle are capable of dealing with linear problems since they depend on finding hyperplanes. However, using the kernel trick, support vector machines can transform a non-linear problem into a linear problem (in a higher dimensional space)

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ and you have linear decision boundaries as a consequence of using the Euclidean distance $\endgroup$
    – jpmuc
    Commented Mar 26, 2013 at 8:55
  • 2
    $\begingroup$ @juampa technically, it's the squared euclidean distance: it's the sum of squares is minimized by k-means. The square root just happens to be a monotone function, so coincidentially, Euclidean distance is also minimized. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Mar 26, 2013 at 13:46
  • $\begingroup$ The boundary is created from multiple hyperplanes, creating convex hulls around the classes, but this doesn't make the boundary itself linear. $\endgroup$
    – Bert Kellerman
    Commented Jan 20, 2018 at 23:20
  • $\begingroup$ One could say that the decision boundary is "piecewise linear" if we have multiple classes. $\endgroup$
    – usεr11852
    Commented Feb 7, 2023 at 23:35
2
$\begingroup$

points on decision boundary will be equidistant from both the centers C1 and C2. So you have enter image description here

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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