Practically, it means finding the optimal solution is hard. More theoretically, it means when you increase the problem size, the time it takes to find the solution increases exponentially. In some sense, it means we cannot really solve the k-means problem optimally with large dataset size, even if we had a super-computer.
K means
In lecture 10B, it was mentioned that K means clustering is NP-hard. Can you please explain what does NP-hard means?
Simply put: we don't know of a general solution to that problem that could be solved with the computers we have today (https://en.wikipedia.org/wiki/NP-hardness).
Practically, it means finding the optimal solution is hard. More theoretically, it means when you increase the problem size, the time it takes to find the solution increases exponentially. In some sense, it means we cannot really solve the k-means problem optimally with large dataset size, even if we had a super-computer.
Add comment