[SciPy-User] kmeans and initial centroid guesses

[Keith Goodman]

The kmeans function has two modes. In one of the modes the initial
guesses for the centroids are randomly selected from the input data.
The selection is currently done with replacement:

guess = take(obs, randint(0, No, k), 0)

That means some of the centroids in the intial guess might be the
same. Wouldn't it be better to select without replacement? Something
like

guess = take(obs, rand(No).argsort()[:k], 0)

Here's an extreme example of what can go wrong if the selection is
done with replacement:

>> obs

array([[ 1, 1],
[-1, -1],
[-1, 1],
[ 1, -1]])
>> vq.kmeans(obs, k_or_guess=4)

(array([[-1, -1],
[-1, 1],
[ 1, -1],
[ 1, 1]]), 0.0) # <--- good
>>
>> k_or_guess = obs[[1,1,1,1],:]
>> k_or_guess

array([[-1, -1],
[-1, -1],
[-1, -1],
[-1, -1]])
>> vq.kmeans(obs, k_or_guess)
(array([[0, 0]]), 1.4142135623730951) # <--- not as good

In most cases it won't make any difference. But the cost of the code
change is small.
_______________________________________________
SciPy-User mailing list
SciPy...@scipy.org
http://mail.scipy.org/mailman/listinfo/scipy-user

[David Cournapeau]

On Mon, Dec 28, 2009 at 10:37 AM, Keith Goodman <kwgo...@gmail.com> wrote:
> The kmeans function has two modes. In one of the modes the initial
> guesses for the centroids are randomly selected from the input data.
> The selection is currently done with replacement:
>
> guess = take(obs, randint(0, No, k), 0)
>
> That means some of the centroids in the intial guess might be the
> same. Wouldn't it be better to select without replacement?

I think you are right, but random sampling without replacement for
floating point values is a bit hard to use here: if two values are
different but very close, you would see the same effect, right ?

Generally, for clustering algorithms, I think you'd you want to start
with centroids as far from each other as possible, so maybe the code
could be improved taking this into account.

cheers,

David

[Keith Goodman]

On Sun, Dec 27, 2009 at 5:47 PM, David Cournapeau <cour...@gmail.com> wrote:
> On Mon, Dec 28, 2009 at 10:37 AM, Keith Goodman <kwgo...@gmail.com> wrote:
>> The kmeans function has two modes. In one of the modes the initial
>> guesses for the centroids are randomly selected from the input data.
>> The selection is currently done with replacement:
>>
>> guess = take(obs, randint(0, No, k), 0)
>>
>> That means some of the centroids in the intial guess might be the
>> same. Wouldn't it be better to select without replacement?
>
> I think you are right, but random sampling without replacement for
> floating point values is a bit hard to use here: if two values are
> different but very close, you would see the same effect, right ?
>
> Generally, for clustering algorithms, I think you'd you want to start
> with centroids as far from each other as possible, so maybe the code
> could be improved taking this into account.

That's a good point. And it sounds like an interesting problem to find
the set of k points that are farthest apart. But the time it takes to
find far apart points could be used to do more iterations of randomly
selected points. I see that kmeans2 has a few different methods for
selecting the initial points. A method like the one you suggest could
be added there. (Maybe use pdist to select the two farthest apart
points and then select the point that is furthest away from the first
two points and so on. It would get slow if a lot of points were
needed.) For kmeans I'll file a ticket to draw without replacement.

[Keith Goodman]

I opened a ticket and created a patch:

http://projects.scipy.org/scipy/ticket/1078