# k-means and perceptron generalization ability

I've implemented simple Widrow-Hopf perceptron and k-means clustering and compare results against MNIST data set. I didn't expect great results because of linear nature of these algorithms. WH perceptron ended up with ~70% accuracy and k-means with ~50% (I have unit tests and compare with pure random chance 1/10 I suppose they do work somehow correct).

Also I gave "a hint" to k-means by set up initial centroids around different digits, so it can converge faster.

I suppose that k-means showed this result because digits are pretty much similar (6 is like 8 and 8 is like 9). Then I assumed that generalizations ability of WH perceptron is better than k-means. Did anyone see any article/book about this topic? I want to understand results from a rigor mathematical perspective.

Comparing K-means and perceptrons doesn't make sense, they are different types of algorithms.

K-means doesn't have a generalization ability at all, since it is an unsupervised algorithm, and generalization is a property of supervised learning algorithms.

If you are changing it to behave like a supervised algorithm, than it will have poor generalization ability compared to the perceptron, because K-means will have a tendency to overfit the data since it is forced to assign a cluster to each of its data points.

If you want to compare perceptron's performance to other algorithms, you should compare it to k-NN (K nearest neighbors), Random Forests, or Support Vector Machines.

• Do you mean that from a geometrical perspective, WH poshes hyperplane off the points, but k-means tends to be more central? I would love to see article/book about this? I assume that well separated data (where data clusters placed far from each other) WH and k-means will perform equally. Or Im wrong ? Commented Sep 19, 2016 at 2:19
• I don't understand what you mean when you say they would perform equally: how are you measuring generalization at all with K-means? With K-means the clusters would get recalculated each time you added new data - there is no separate training and testing phase - unlike a perceptron which would fix the hyperplanes after the training is done. Can you clarify how exactly you are measuring the performance of K-means for your task? I don't see how K-means can perform generalization, since it would recalculate the boundaries each times? Commented Sep 19, 2016 at 6:26
• Hm, one give a hint by point to a proper init guess (for example every initial centroid points to one of samples from it's cluster). Then one recalculate centroids until they converge to some centers (calculate norm, normalize, update centroids). Then you use these centroids to identify samples from a new dataset which has the same structure as one which one used to calculate centroids. I calculate hits and misses/ Commented Sep 19, 2016 at 6:41
• My idea was, that centroids are vectors in the same space as samples, but they are on center of each cluster. So any vector that needs to be classified will be closer to a corresponding centroid btw I do understand that k-means is not super appropriate thing for that, SVM, DNN, WH would work better. Im just curious about results and way how they can be explained, even if they sound a bit (or a lot) ridiculous. Commented Sep 19, 2016 at 6:50
• I found the answer, thanks for pointing me in the right direction stats.stackexchange.com/questions/79741/… Commented Sep 19, 2016 at 22:46