k-means clustering with some known centers I am working on an project where I need to add clusters (likely double but I want it to be arbitrary) to an existing kmeans clustering solution.
I am actually only interested in the centers. So is there a method where I can add more clusters with the initial ones fixed? I guess the end result will not meet the exact definition of kmeans, but something as close as possible.
I would greatly prefer a python tool. Even better if sklearn. But I am open to alternatives if I have to be.
Thanks!
 A: This is equivalent to a modified version of k-means, where some of the centroids are constrained to take given values. Below, I'll describe how to formulate this as an optimization problem, then how to solve it.
Formulating the problem
Let $X = \{x_1, \dots, x_n\}, x_i \in \mathbb{R}^d$ be a set of data points to cluster and let $\{c_1, \dots, c_k\}, c_i \in \mathbb{R}^d$ denote a set of $k$ centroids. Suppose the first $k' < k$ centroids are already known (e.g. they've been learned using an initial round of k-means clustering). $X$ may or may not include data used to learn this initial clustering.
The goal is to learn the remaining $k-k'$ centroids such that, when each point is assigned to the nearest centroid, the sum of squared point-to-centroid distances is minimized:
$$\min_{c_{k'+1}, \dots, c_k} \ \sum_{j=1}^k \sum_{x \in S_j} \| x - c_j\|^2$$
where $S_j$ is a set containing the points assigned to centroid $j$ (i.e. points for which $c_j$ is the nearest centroid using Euclidean distance). Note that the above is equivalent to the standard k-means problem, with the first $k'$ centroids constrained to take known values.
Solving the problem
The standard (unconstrained) k-means problem is typically solved using Lloyd's algorithm:


*

*Initialize cluster centroids. For example, choose them to be a random subset of data points. More clever strategies exist as well (e.g. k-means++).


Repeat until assignment of points to centroids doesn't change:


*Assign each point to the nearest centroid (using Euclidean distance).

*Update each centroid to be the mean of all points assigned to it.
A simple modification of Lloyd's algorithm can be used to solve the modified k-means problem above: In steps 1 and 3, keep the first $k'$ centroids fixed at their given values, and only initialize/update centroids $k'+1$ through $k$
Notes


*

*The solution to the modified k-means problem above will have error at least as large as standard k-means. That is, constraining the first $k'$ centroids can only reduce performance (or, at best, leave it unchanged) compared to re-solving for all $k$ centroids. Whether this is acceptable depends on the underlying problem you're trying to solve.

*This is a non-standard problem. It's unlikely that a software implementation already exists, but it should be straightforward to implement it yourself.

*Lloyd's algorithm may converge to a local minimum, so it gives only approximate solutions to the k-means problem. Finding an exact solution is NP-hard. A common strategy is to run multiple times from different initial centroids.

*Various strategies for accelerating Lloyd's algorithm (e.g. using the triangle inequality to reduce the number of distance computations) should be applicable in the constrained case as well (see references here).
A: I'm not aware of any expansion of k-means cluster analysis that allows for clusters to be fixed in location, and to be perfectly frank it doesn't seem like a good idea. That being said it shouldn't be too difficult to code something like this up yourself. 
Standard k-means (with a random partition initialization) works by the following algorithm.


*

*Assign elements to clusters at random.

*calculate new centers of each cluster. 

*assign elements to nearest cluster centroid

*repeat 2-3 until no elements change cluster.


The only amendment you would need to make for your constraints is to never update the centroids of the clusters you want to remain fixed in location in step 2.
However, if that sounds like too much work and you are willing to accept small deviations from the original centroids, scikit learn seems to support weighting your data. You could try adding the centroids you wish to keep as additional data points with a very high weight.
A: A library won't do all the work for you.
But with just 4-5 lines of code you should be able to build a k-means variant that only updates those centers that you want to move and keeps the others fixed. That will work.
