scikit-learn · ogrisel · Feb 20, 2020 · Aug 30, 2018 · Oct 22, 2018 · Oct 22, 2018
diff --git a/azure-pipelines.yml b/azure-pipelines.yml
@@ -39,6 +39,7 @@ jobs:
         PILLOW_VERSION: '*'
         PYTEST_VERSION: '*'
         JOBLIB_VERSION: '*'
+        THREADPOOLCTL_VERSION: '2.0.0'
         COVERAGE: 'true'
 
 - template: build_tools/azure/posix.yml
@@ -54,6 +55,7 @@ jobs:
         DISTRIB: 'ubuntu'
         PYTHON_VERSION: '3.6'
         JOBLIB_VERSION: '0.11'
+        THREADPOOLCTL_VERSION: '2.0.0'
       # Linux + Python 3.6 build with OpenBLAS and without SITE_JOBLIB
       py36_conda_openblas:
         DISTRIB: 'conda'
@@ -70,6 +72,7 @@ jobs:
         SCIKIT_IMAGE_VERSION: '*'
         # latest version of joblib available in conda for Python 3.6
         JOBLIB_VERSION: '0.13.2'
+        THREADPOOLCTL_VERSION: '2.0.0'
         COVERAGE: 'true'
       # Linux environment to test the latest available dependencies and MKL.
       # It runs tests requiring lightgbm, pandas and PyAMG.
@@ -92,6 +95,7 @@ jobs:
         DISTRIB: 'ubuntu-32'
         PYTHON_VERSION: '3.6'
         JOBLIB_VERSION: '0.13'
+        THREADPOOLCTL_VERSION: '2.0.0'
 
 - template: build_tools/azure/posix.yml
   parameters:
@@ -109,6 +113,7 @@ jobs:
         PILLOW_VERSION: '*'
         PYTEST_VERSION: '*'
         JOBLIB_VERSION: '*'
+        THREADPOOLCTL_VERSION: '2.0.0'
         COVERAGE: 'true'
       pylatest_conda_mkl_no_openmp:
         DISTRIB: 'conda'
@@ -120,6 +125,7 @@ jobs:
         PILLOW_VERSION: '*'
         PYTEST_VERSION: '*'
         JOBLIB_VERSION: '*'
+        THREADPOOLCTL_VERSION: '2.0.0'
         COVERAGE: 'true'
         SKLEARN_TEST_NO_OPENMP: 'true'
         SKLEARN_SKIP_OPENMP_TEST: 'true'

diff --git a/build_tools/azure/install.cmd b/build_tools/azure/install.cmd
@@ -15,14 +15,16 @@ IF "%PYTHON_ARCH%"=="64" (
 
     call activate %VIRTUALENV%
 
+    pip install threadpoolctl
+
     IF "%PYTEST_VERSION%"=="*" (
         pip install pytest
     ) else (
         pip install pytest==%PYTEST_VERSION%
     )
     pip install pytest-xdist
 ) else (
-    pip install numpy scipy cython pytest wheel pillow joblib
+    pip install numpy scipy cython pytest wheel pillow joblib threadpoolctl
 )
 if "%COVERAGE%" == "true" (
     pip install coverage codecov pytest-cov

diff --git a/build_tools/azure/install.sh b/build_tools/azure/install.sh
@@ -65,6 +65,8 @@ if [[ "$DISTRIB" == "conda" ]]; then
 
 	make_conda $TO_INSTALL
 
+    pip install threadpoolctl==$THREADPOOLCTL_VERSION
+
     if [[ "$PYTEST_VERSION" == "*" ]]; then
         python -m pip install pytest
     else
@@ -81,13 +83,13 @@ elif [[ "$DISTRIB" == "ubuntu" ]]; then
     sudo apt-get install python3-scipy python3-matplotlib libatlas3-base libatlas-base-dev python3-virtualenv
     python3 -m virtualenv --system-site-packages --python=python3 $VIRTUALENV
     source $VIRTUALENV/bin/activate
-    python -m pip install pytest==$PYTEST_VERSION pytest-cov cython joblib==$JOBLIB_VERSION
+    python -m pip install pytest==$PYTEST_VERSION pytest-cov cython joblib==$JOBLIB_VERSION threadpoolctl==$THREADPOOLCTL_VERSION
 elif [[ "$DISTRIB" == "ubuntu-32" ]]; then
     apt-get update
     apt-get install -y python3-dev python3-scipy python3-matplotlib libatlas3-base libatlas-base-dev python3-virtualenv
     python3 -m virtualenv --system-site-packages --python=python3 $VIRTUALENV
     source $VIRTUALENV/bin/activate
-    python -m pip install pytest==$PYTEST_VERSION pytest-cov cython joblib==$JOBLIB_VERSION
+    python -m pip install pytest==$PYTEST_VERSION pytest-cov cython joblib==$JOBLIB_VERSION threadpoolctl==$THREADPOOLCTL_VERSION
 elif [[ "$DISTRIB" == "conda-pip-latest" ]]; then
     # Since conda main channel usually lacks behind on the latest releases,
     # we use pypi to test against the latest releases of the dependencies.

diff --git a/build_tools/azure/posix-32.yml b/build_tools/azure/posix-32.yml
@@ -36,6 +36,7 @@ jobs:
         -e JUNITXML=$JUNITXML
         -e VIRTUALENV=testvenv
         -e JOBLIB_VERSION=$JOBLIB_VERSION
+        -e THREADPOOLCTL_VERSION=$THREADPOOLCTL_VERSION
         -e PYTEST_VERSION=$PYTEST_VERSION
         -e OMP_NUM_THREADS=$OMP_NUM_THREADS
         -e OPENBLAS_NUM_THREADS=$OPENBLAS_NUM_THREADS

diff --git a/doc/modules/clustering.rst b/doc/modules/clustering.rst
@@ -205,12 +205,13 @@ computing cluster centers and values of inertia. For example, assigning a
 weight of 2 to a sample is equivalent to adding a duplicate of that sample
 to the dataset :math:`X`.
 
-A parameter can be given to allow K-means to be run in parallel, called
-``n_jobs``. Giving this parameter a positive value uses that many processors
-(default: 1). A value of -1 uses all available processors, with -2 using one
-less, and so on. Parallelization generally speeds up computation at the cost of
-memory (in this case, multiple copies of centroids need to be stored, one for
-each job).
+Low-level parallelism
+---------------------
+
+:class:`KMeans` benefits from OpenMP based parallelism through Cython. Small
+chunks of data (256 samples) are processed in parallel, which in addition
+yields a low memory footprint. For more details on how to control the number of
+threads, please refer to our :ref:`parallelism` notes.
 
 .. warning::
 

diff --git a/doc/whats_new/v0.23.rst b/doc/whats_new/v0.23.rst
@@ -64,6 +64,26 @@ Changelog
   could not have a `np.int64` type. :pr:`16484`
   by :user:`Jeremie du Boisberranger <jeremiedbb>`.
 
+- |API| The ``n_jobs`` parameter of :class:`cluster.KMeans`,
+  :class:`cluster.SpectralCoclustering` and
+  :class:`cluster.SpectralBiclustering` is deprecated. They now use OpenMP
+  based parallelism. For more details on how to control the number of threads,
+  please refer to our :ref:`parallelism` notes. :pr:`11950` by
+  :user:`Jeremie du Boisberranger <jeremiedbb>`.
+
+- |API| The ``precompute_distances`` parameter of :class:`cluster.KMeans` is
+  deprecated. It has no effect. :pr:`11950` by
+  :user:`Jeremie du Boisberranger <jeremiedbb>`.
+
+- |Efficiency| The critical parts of :class:`cluster.KMeans` have a more
+  optimized implementation. Parallelism is now over the data instead of over
+  initializations allowing better scalability. :pr:`11950` by
+  :user:`Jeremie du Boisberranger <jeremiedbb>`.
+
+- |Enhancement| :class:`cluster.KMeans` now supports sparse data when
+  `solver = "elkan"`. :pr:`11950` by
+  :user:`Jeremie du Boisberranger <jeremiedbb>`.
+
 :mod:`sklearn.compose`
 ......................
 

diff --git a/setup.py b/setup.py
@@ -56,6 +56,7 @@
     NUMPY_MIN_VERSION = '1.13.3'
 
 JOBLIB_MIN_VERSION = '0.11'
+THREADPOOLCTL_MIN_VERSION = '2.0.0'
 
 # Optional setuptools features
 # We need to import setuptools early, if we want setuptools features,
@@ -257,7 +258,8 @@ def setup_package():
                     install_requires=[
                         'numpy>={}'.format(NUMPY_MIN_VERSION),
                         'scipy>={}'.format(SCIPY_MIN_VERSION),
-                        'joblib>={}'.format(JOBLIB_MIN_VERSION)
+                        'joblib>={}'.format(JOBLIB_MIN_VERSION),
+                        'threadpoolctl>={}'.format(THREADPOOLCTL_MIN_VERSION)
                     ],
                     package_data={'': ['*.pxd']},
                     **extra_setuptools_args)

diff --git a/sklearn/cluster/_bicluster.py b/sklearn/cluster/_bicluster.py
@@ -3,6 +3,7 @@
 # License: BSD 3 clause
 
 from abc import ABCMeta, abstractmethod
+import warnings
 
 import numpy as np
 
@@ -88,7 +89,7 @@ class BaseSpectral(BiclusterMixin, BaseEstimator, metaclass=ABCMeta):
     @abstractmethod
     def __init__(self, n_clusters=3, svd_method="randomized",
                  n_svd_vecs=None, mini_batch=False, init="k-means++",
-                 n_init=10, n_jobs=None, random_state=None):
+                 n_init=10, n_jobs='deprecated', random_state=None):
         self.n_clusters = n_clusters
         self.svd_method = svd_method
         self.n_svd_vecs = n_svd_vecs
@@ -115,6 +116,10 @@ def fit(self, X, y=None):
         y : Ignored
 
         """
+        if self.n_jobs != 'deprecated':
+            warnings.warn("'n_jobs' was deprecated in version 0.23 and will be"
+                          " removed in 0.25.", FutureWarning)
+
         X = check_array(X, accept_sparse='csr', dtype=np.float64)
         self._check_parameters()
         self._fit(X)
@@ -233,6 +238,10 @@ class SpectralCoclustering(BaseSpectral):
         ``-1`` means using all processors. See :term:`Glossary <n_jobs>`
         for more details.
 
+        .. deprecated:: 0.23
+            ``n_jobs`` was deprecated in version 0.23 and will be removed in
+            0.25.
+
     random_state : int, RandomState instance, default=None
         Used for randomizing the singular value decomposition and the k-means
         initialization. Use an int to make the randomness deterministic.
@@ -277,7 +286,7 @@ class SpectralCoclustering(BaseSpectral):
     """
     def __init__(self, n_clusters=3, svd_method='randomized',
                  n_svd_vecs=None, mini_batch=False, init='k-means++',
-                 n_init=10, n_jobs=None, random_state=None):
+                 n_init=10, n_jobs='deprecated', random_state=None):
         super().__init__(n_clusters,
                          svd_method,
                          n_svd_vecs,
@@ -380,6 +389,10 @@ class SpectralBiclustering(BaseSpectral):
         ``-1`` means using all processors. See :term:`Glossary <n_jobs>`
         for more details.
 
+        .. deprecated:: 0.23
+            ``n_jobs`` was deprecated in version 0.23 and will be removed in
+            0.25.
+
     random_state : int, RandomState instance, default=None
         Used for randomizing the singular value decomposition and the k-means
         initialization. Use an int to make the randomness deterministic.
@@ -425,7 +438,7 @@ class SpectralBiclustering(BaseSpectral):
     def __init__(self, n_clusters=3, method='bistochastic',
                  n_components=6, n_best=3, svd_method='randomized',
                  n_svd_vecs=None, mini_batch=False, init='k-means++',
-                 n_init=10, n_jobs=None, random_state=None):
+                 n_init=10, n_jobs='deprecated', random_state=None):
         super().__init__(n_clusters,
                          svd_method,
                          n_svd_vecs,