<p dir="auto"><em>Original ticket <a href="http://projects.scipy.org/scipy/ticket/1078" rel="nofollow">http://projects.scipy.org/scipy/ticket/1078</a> on 2009-12-28 by <a class="user-mention notranslate" data-hovercard-type="user" data-hovercard-url="/users/kwgoodman/hovercard" data-octo-click="hovercard-link-click" data-octo-dimensions="link_type:self" href="https://github.com/kwgoodman">@kwgoodman</a>, assigned to unknown.</em></p>
<p dir="auto">The kmeans function has two modes. In one of the modes the initial<br>
guesses for the centroids are randomly selected from the input data.<br>
The selection is currently done with replacement:</p>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="guess = take(obs, randint(0, No, k), 0)"><pre class="notranslate"><code class="notranslate">guess = take(obs, randint(0, No, k), 0)
</code></pre></div>
<p dir="auto">That means some of the centroids in the intial guess might be the<br>
same. I think it would be better to select without replacement:</p>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="guess = take(obs, rand(No).argsort()[:k], 0)"><pre class="notranslate"><code class="notranslate">guess = take(obs, rand(No).argsort()[:k], 0)
</code></pre></div>
<p dir="auto">Here's an extreme example of what can go wrong if the selection is<br>
done with replacement:</p>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="&gt;&gt; obs

array([[ 1,  1],
      [-1, -1],
      [-1,  1],
      [ 1, -1]])
&gt;&gt; vq.kmeans(obs, k_or_guess=4)

(array([[-1, -1],
      [-1,  1],
      [ 1, -1],
      [ 1,  1]]), 0.0) # &lt;--- good
&gt;&gt;
&gt;&gt; k_or_guess = obs[[1,1,1,1],:]
&gt;&gt; k_or_guess

array([[-1, -1],
      [-1, -1],
      [-1, -1],
      [-1, -1]])
&gt;&gt; vq.kmeans(obs, k_or_guess)
  (array([[0, 0]]), 1.4142135623730951) # &lt;--- not as good"><pre class="notranslate"><code class="notranslate">&gt;&gt; obs

array([[ 1,  1],
      [-1, -1],
      [-1,  1],
      [ 1, -1]])
&gt;&gt; vq.kmeans(obs, k_or_guess=4)

(array([[-1, -1],
      [-1,  1],
      [ 1, -1],
      [ 1,  1]]), 0.0) # &lt;--- good
&gt;&gt;
&gt;&gt; k_or_guess = obs[[1,1,1,1],:]
&gt;&gt; k_or_guess

array([[-1, -1],
      [-1, -1],
      [-1, -1],
      [-1, -1]])
&gt;&gt; vq.kmeans(obs, k_or_guess)
  (array([[0, 0]]), 1.4142135623730951) # &lt;--- not as good
</code></pre></div>
<p dir="auto">In most cases it won't make any difference. But the cost of the code<br>
change is small.</p>
<p dir="auto">In scipy.cluster.vq.kmeans, the initial guess for the code book uses numpy.random.randint to select observations from the input data. However, randint may return the same index more than once, which produces undesirable results. kmeans2 appears to avoid this by using np.random.permutation.</p>