Repository: scipy/scipy
Pull request: BUG: Fixed `_kpp` initialization on `scipy.cluster.vq`, closing #11463
The function `_kpp` used the wrong dimension to sample the data.

<!-- 
Thanks for contributing a pull request! Please ensure that
your PR satisfies the checklist before submitting:
http://scipy.github.io/devdocs/dev/contributor/development_workflow.html#checklist-before-submitting-a-pr

Also, please name and describe your PR as you would write a
commit message:
https://docs.scipy.org/doc/numpy/dev/development_workflow.html#writing-the-commit-message

Note that we are a team of volunteers; we appreciate your
patience during the review process.

Again, thanks for contributing!
-->

#### Reference issue
Closes #11462 

#### What does this implement/fix?
This corrects the dimension used, the feature dimension was being used in place of the sample dimension. This resulted in a non-uniform sampling over the data and sometimes crash when the feature dimension was larger than the sample size.

#### Note
I will be closing the PR #11463 because I accidentally deleted the branch, so I wasn't able to add the requested changes.

Problem statement:
Bug on "++" initialization on "kmeans2"
<!-- 
Thank you for taking the time to file a bug report. 
Please fill in the fields below, deleting the sections that 
don't apply to your issue. You can view the final output
by clicking the preview button above.
Note: This is a comment, and won't appear in the output.
-->

My issue is about a bug on the `++` initialization on the `kmeans2` function from the `scipy.cluster.vq` module, this only happens when the data dimension is greater than the number of samples.

Code to reproduce it:
```python
 import numpy as np
 from scipy.cluster.vq import kmeans2
 
 x = np.random.normal(size=(5 * 1000))
 x = x.reshape(5, 1000)
 
 centers, labels = kmeans2(x, k=2, minit='++')
```

Resulting error:
```python
Traceback (most recent call last):
  File "scipy-bug.py", line 7, in <module>
    centers, labels = kmeans2(x, k=2, minit='++')
  File "/usr/local/Caskroom/miniconda/base/envs/selfstudy/lib/python3.7/site-packages/scipy/cluster/vq.py", line 700, in kmeans2
    code_book = init_meth(data, k)
  File "/usr/local/Caskroom/miniconda/base/envs/selfstudy/lib/python3.7/site-packages/scipy/cluster/vq.py", line 560, in _kpp
    init[i, :] = data[np.random.randint(dims)]
```

Python version
```python
import sys, scipy, numpy; print(scipy.__version__, numpy.__version__, sys.version_info)                                                                                                                              
# 1.3.1 1.17.4 sys.version_info(major=3, minor=7, micro=5, releaselevel='final', serial=0)
```

Hints from issue discussion:

Commit message: Added new line to end of file

Patch to review:
diff --git a/scipy/cluster/tests/test_vq.py b/scipy/cluster/tests/test_vq.py
index a8ffcd0a6a16..246556e24c63 100644
--- a/scipy/cluster/tests/test_vq.py
+++ b/scipy/cluster/tests/test_vq.py
@@ -289,3 +289,25 @@ def test_kmeans_large_thres(self):
         res = kmeans(x, 1, thresh=1e16)
         assert_allclose(res[0], np.array([4.]))
         assert_allclose(res[1], 2.3999999999999999)
+        
+    def test_kmeans2_kpp_low_dim(self):
+        # Regression test for gh-11462
+        prev_res = np.array([[-1.95266667,  0.898],
+                             [-3.153375  ,  3.3945]])
+        np.random.seed(42)
+        res, _ = kmeans2(TESTDATA_2D, 2, minit='++')
+        assert_allclose(res, prev_res)
+
+    def test_kmeans2_kpp_high_dim(self):
+        # Regression test for gh-11462
+        n_dim = 100
+        size = 10
+        centers = np.vstack([ 5 * np.ones(n_dim),
+                             -5 * np.ones(n_dim)])
+        data = np.vstack([np.random.multivariate_normal(centers[0], np.eye(n_dim), size=size),
+                          np.random.multivariate_normal(centers[1], np.eye(n_dim), size=size)])
+        # 20x100 dataset
+        np.random.seed(42)
+        res, _ = kmeans2(data, 2, minit='++')
+        assert_array_almost_equal(res, centers, decimal=0)
+        
\ No newline at end of file
diff --git a/scipy/cluster/vq.py b/scipy/cluster/vq.py
index edb60c442507..58c5502ec4b1 100644
--- a/scipy/cluster/vq.py
+++ b/scipy/cluster/vq.py
@@ -556,7 +556,7 @@ def _kpp(data, k):
 
     for i in range(k):
         if i == 0:
-            init[i, :] = data[np.random.randint(dims)]
+            init[i, :] = data[np.random.randint(data.shape[0])]
 
         else:
             D2 = np.array([min(


Code review comments:
diff_hunk: @@ -289,3 +289,25 @@ def test_kmeans_large_thres(self):
         res = kmeans(x, 1, thresh=1e16)
         assert_allclose(res[0], np.array([4.]))
         assert_allclose(res[1], 2.3999999999999999)
+        
+    def test_kmeans2_kpp_low_dim(self):
+        # Regression test for gh-11462
+        prev_res = np.array([[-1.95266667,  0.898],
+                             [-3.153375  ,  3.3945]])
+        np.random.seed(42)
+        res, _ = kmeans2(TESTDATA_2D, 2, minit='++')
+        assert_allclose(res, prev_res)
+
+    def test_kmeans2_kpp_high_dim(self):
+        # Regression test for gh-11462
+        n_dim = 100
+        size = 10
+        centers = np.vstack([ 5 * np.ones(n_dim),
+                             -5 * np.ones(n_dim)])
+        data = np.vstack([np.random.multivariate_normal(centers[0], np.eye(n_dim), size=size),
+                          np.random.multivariate_normal(centers[1], np.eye(n_dim), size=size)])
+        # 20x100 dataset
+        np.random.seed(42)
path: scipy/cluster/tests/test_vq.py
text: @user1:
just want to double-check--does it matter that this seeding happens after the random calls above?

@author:
Thanks.

I fixed the styling.

The seed was mainly to fix the centers order because the k-means centers will almost surely be close to gaussian distribute mean. But it is better to be safe than sorry, I moved the seed position as recommended.