I am in the final year of my undergraduate program and I am doing my capstone project related to k-means clustering. I am trying to get good results on my dataset by optimizing the k-means algorithm using the Newton-Rapshon method in R. The Newton-Raphson algorithm is a root solving function which takes an equation as an argument and gives out the approximate root. I can't understand how to integrate that with the k-means algorithm for optimization purposes. Can anyone help me out with this, it would be much appreciated.

  • $\begingroup$ I am in agreement with Dougal's answer. N-R + k-means wouldn't be a great combination. If you're really settled on trying to look at k-means, I suggest reading through this post first stats.stackexchange.com/questions/133656/… It should give you appropriate context about the limitations of k-means, then maybe you can think of a project where you try to "optimize" k-means. $\endgroup$ – Jon Feb 1 '17 at 17:40

The k-means algorithm is a specific algorithm that doesn't really have a spot to plug in Newton-Raphson.

You could consider using Newton-Raphson to optimize the k-means problem: finding assignments of points to sets to minimize the total squared distance from their means. The objective function is$\DeclareMathOperator*{\argmin}{\mathrm{arg\,min}}$ $$ \argmin_{S_1, \dots, S_k} \sum_{i=1}^k \sum_{x \in S_i} \left\lVert x - \frac{1}{\lvert S_i \rvert} \sum_{x' \in S_i} x' \right\rVert^2 .$$ Unfortunately, since the sets $S_i$ are discrete objects, it's going to be hard to phrase the problem in a way that Newton-Raphson can work on, since it's for functions on continuous input spaces.

I'm not sure why you decided to use Newton-Raphson – it's not a very natural fit. If you're just trying to analyze some data, use an existing k-means package. But if you're really dedicated to doing this idea, you could try a relaxation to soft assignments, like in a Gaussian mixture model. The standard thing to do there would be expectation maximization, but Newton-Raphson would also work.


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.