How to optimize the result of K means

Question

I am analyzing the data of abalone. My goal is to classify the data into three categories(premium, medium premium, and classic). Since it's an unlabeled dataset, so I utilized K means clustering to do it. My problem is, is there any way the optimize the result? I feel like the only analysis that I can do in the k means algorithm in R is km = kmeans(data,centers=3,nstart=25). Is there any parameter that I can tune in this algorithm. Please give me some suggestion?

Answer 1

If you use ?kmeans in your R console you can identify different parameters that you can optimize in k-means algorithm. The best parameter is the starting values for the centroids. If you know any of the data point to be of specific class and they are far apart you can use those as your starting centroids so that kmeans does not converge to a suboptimal solution. Otherwise, you could sample them at random and use nstart to test multiple starting points. Additionally, you could use different algorithms defined within kmeans such as Lloyd, Forgy, MacQueen.

Answer 2

If you're not entirely convinced by the results of a k-means approach, you can try the following:

1. Use a variant of k-means, such as k-medoids. This is almost the same, except k-means uses the euclidian distance ($L^2$ norm), where k-medoids uses the $L^1$ norm. The k-medoids clustering is known to be more robust towards outliers. Actually, you can create your variant by simply choosing whatever distance function suits your data.

   In R, I believe you can do this through the flexclust package (or your own code, the algorithm is not so complicated).

2. Perform data transformation using the kernel trick. Sometimes the feature space does not allow a proper clustering. For instance, if you have two clusters: one very small and dense, the other one rather wide and sparse; k-means will come up with clusters about the same size, which is not what you intended. Another situation is when the points are not linearly separable.

   In such cases, you could perform spectral clustering, an approach based on the kernel trick and graph theory (it is easier than it sounds!). This not only performs data transformation, but also provides a quite easy way to determine how many clusters you may have (which is not always trivial).