Repository: scikit-learn/scikit-learn
Pull request: [MRG+1] Warning in KMeans if too few clusters were found
#### Reference Issues/PRs
Fixes #10059 

#### What does this implement/fix? Explain your changes.
Gives a warning if the number of distinct cluster centers found is smaller than the number of expected clusters (given by ```n_clusters```). 

Added a test, where exactly this behaviour can be seen and check whether the set of labels actually is too small and if the warning is raised properly.

#### Any other comments?
This is sort-of a minimal solution. The problem remains annoying (I understand @ilectra here, although it is expected behaviour of the algorithm). 

I could also implement something like a sanitizing routine, which also removes the duplicate center (then ```set(labels)``` and ```set(cluster_centers)``` would have at least the same size. This actually would take more effort, since the missing label could be any label and it could also be more than just one label missing. 

I marked this as WIP since I'm not confident if a warning alone is sufficient. 

Problem statement:
Duplicated input points silently create duplicated clusters in KMeans
#### Description
When there are duplicated input points to Kmeans resulting to number of unique points < number of requested clusters, there is no error thrown. Instead, clustering continues to (seemingly) produce the number of clusters requested, but some of them are exactly the same, so the cluster labels produced for the input points do not go all the way to number of requested clusters.

#### Steps/Code to Reproduce
```python
from sklearn.cluster import KMeans
import numpy as np

# some input points here are identical, so that n_total=17, n_unique=9
x2d = np.array([(1086, 348), (1087, 347), (1190, 244), (1190, 244), (1086, 348), (1185, 249), (1193, 241), (1185, 249), (1087, 347), (1188, 247), (1187, 233), (26, 111), (26, 111), (26, 110), (26, 110), (26, 110), (26, 110)])
kmeans = KMeans(n_clusters=10) # n_clusters > n_unique
c_labels = kmeans.fit_predict(x2d)
c_centers = kmeans.cluster_centers_
```
#### Expected Results
Either an error thrown, or the cluster labels produced should match the unique clusters only (i.e. no identical cluster centres)

#### Actual Results
```python
>>> c_labels  # note there's no entry for cluster 9
array([7, 2, 6, 6, 7, 5, 4, 5, 2, 1, 3, 8, 8, 0, 0, 0, 0], dtype=int32)
>>> c_centers # two of these 10 clusters have identical centers, so only 9 of them are unique
array([[   26.,   110.],
       [ 1188.,   247.],
       [ 1087.,   347.],
       [ 1187.,   233.],
       [ 1193.,   241.],
       [ 1185.,   249.],
       [ 1190.,   244.],
       [ 1086.,   348.],
       [   26.,   111.],
       [   26.,   110.]]) 
```

#### Versions
```python
Darwin-16.7.0-x86_64-i386-64bit
Python 3.6.1 |Continuum Analytics, Inc.| (default, May 11 2017, 13:04:09)
[GCC 4.2.1 Compatible Apple LLVM 6.0 (clang-600.0.57)]
NumPy 1.13.1
SciPy 0.19.1
Scikit-Learn 0.18.2
```

Hints from issue discussion:
Is this what you should expect for such a small dataset? Are there standard
ways to avoid duplicate centroids in KMeans?

Though not nice, this is actually, what MacQueen wrote in his paper and thus it _could_ be considered _expected_ behaviour.

(MacQueen, 1967, Some Methods for Classification and Analysis of Multivariate Observations, https://projecteuclid.org/download/pdf_1/euclid.bsmsp/1200512992, p283)
> The set S_i(x) contains the points in E_N nearest to x_i, with tied points being assigned
arbitrarily to the set of lower index. Note that with this convention concerning
tied points, if x_i = x_j and i < j then S_j(x) = 0.

```0``` here means the empty set. ```x``` is the complete data set and ```S_j(x)``` is the j-th cluster generated for ```x```.
@christianbraune79  If `S_j(x) = 0`, shouldn't `c_centers` reflect this fact by being resized to the valid/unique only clusters? And then of course `x_i` and `x_j` would belong to the same cluster.

In any case, a warning issued by the code, and some discussion in the documentation would help.
A patch for either of those things will be considered for inclusion...

Commit message: unnecessary comment

Patch to review:
diff --git a/doc/whats_new/v0.20.rst b/doc/whats_new/v0.20.rst
index 5af76499bcb39..73cf84a56de9a 100644
--- a/doc/whats_new/v0.20.rst
+++ b/doc/whats_new/v0.20.rst
@@ -134,6 +134,11 @@ Decomposition, manifold learning and clustering
 - Fixed a bug when setting parameters on meta-estimator, involving both a
   wrapped estimator and its parameter. :issue:`9999` by :user:`Marcus Voss
   <marcus-voss>` and `Joel Nothman`_.
+  
+- ```k_means``` now gives a warning, if the number of distinct clusters found
+  is smaller than ```n_clusters```. This may occur when the number of distinct 
+  points in the data set is actually smaller than the number of cluster one is 
+  looking for. :issue:`10059` by :user:`Christian Braune <christianbraune79>`.
 
 Metrics
 
diff --git a/sklearn/cluster/k_means_.py b/sklearn/cluster/k_means_.py
index 0da0144172703..71ed97ea33a3b 100644
--- a/sklearn/cluster/k_means_.py
+++ b/sklearn/cluster/k_means_.py
@@ -374,6 +374,10 @@ def k_means(X, n_clusters, init='k-means++', precompute_distances='auto',
             X += X_mean
         best_centers += X_mean
 
+    if len(set(best_labels)) < n_clusters:
+        warnings.warn("number of distinct clusters found smaller than n_clusters. "
+                      "Possibly due to duplicate points in X", RuntimeWarning, stacklevel=2)
+
     if return_n_iter:
         return best_centers, best_labels, best_inertia, best_n_iter
     else:
diff --git a/sklearn/cluster/tests/test_k_means.py b/sklearn/cluster/tests/test_k_means.py
index 080a31ba52f9d..2effbaea65cda 100644
--- a/sklearn/cluster/tests/test_k_means.py
+++ b/sklearn/cluster/tests/test_k_means.py
@@ -867,3 +867,16 @@ def test_sparse_validate_centers():
     msg = "The shape of the initial centers \(\(4L?, 4L?\)\) " \
           "does not match the number of clusters 3"
     assert_raises_regex(ValueError, msg, classifier.fit, X)
+
+
+def test_less_centers_than_unique_points():
+    X = np.asarray([[0, 0],
+                    [0, 1],
+                    [1, 0],
+                    [1, 0]])  # last point is duplicated
+
+    km = KMeans(n_clusters=4).fit(X)
+
+    assert_equal(set(km.labels_), set(range(3)))
+    assert_warns(RuntimeWarning, k_means, X, n_clusters=4)
+


Code review comments:
diff_hunk: @@ -374,6 +374,10 @@ def k_means(X, n_clusters, init='k-means++', precompute_distances='auto',
             X += X_mean
         best_centers += X_mean
 
+    if len(set(best_labels)) < n_clusters:
+        warnings.warn("number of distinct clusters found smaller than n_clusters. "
path: sklearn/cluster/k_means_.py
text: @user1:
Do you think a ConvergenceWarning is appropriate? 

@author:
Probably more appropriate than a FitFailedWarning...

@author:
Better than a FitFailedWarning... :)