{"action":"created","issue":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/7383","repository_url":"https://api.github.com/repos/scikit-learn/scikit-learn","labels_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/7383/labels{/name}","comments_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/7383/comments","events_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/7383/events","html_url":"https://github.com/scikit-learn/scikit-learn/pull/7383","id":176112149,"number":7383,"title":"Added flag to disable l2-dist finite check","user":{"login":"Erotemic","id":3186211,"avatar_url":"https://avatars.githubusercontent.com/u/3186211?v=3","gravatar_id":"","url":"https://api.github.com/users/Erotemic","html_url":"https://github.com/Erotemic","followers_url":"https://api.github.com/users/Erotemic/followers","following_url":"https://api.github.com/users/Erotemic/following{/other_user}","gists_url":"https://api.github.com/users/Erotemic/gists{/gist_id}","starred_url":"https://api.github.com/users/Erotemic/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Erotemic/subscriptions","organizations_url":"https://api.github.com/users/Erotemic/orgs","repos_url":"https://api.github.com/users/Erotemic/repos","events_url":"https://api.github.com/users/Erotemic/events{/privacy}","received_events_url":"https://api.github.com/users/Erotemic/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":3,"created_at":"2016-09-09T21:11:38Z","updated_at":"2016-09-13T14:09:48Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/7383","html_url":"https://github.com/scikit-learn/scikit-learn/pull/7383","diff_url":"https://github.com/scikit-learn/scikit-learn/pull/7383.diff","patch_url":"https://github.com/scikit-learn/scikit-learn/pull/7383.patch"},"body":"The following change significantly speeds up the kmeans++ initialization used\r\nin MiniBatchKmeans.\r\n\r\nThe Euclidean distance computation is the bottleneck in kmeans++. However, on\r\nevery call to Euclidean distance there is also a call to check_pairwise_arrays. \r\nIn in kmeans++, the same Y arrays are being checked every time. One of the checks \r\nin here turns out to cause a speed issue. Specifically the finite check. This patch adds a flag to disable this check.\r\n\r\nI'm not sure if this is the desired way to go about this change, but I do think something needs to be \r\ndone about this functions efficiency. \r\n\r\nHere is some data that shows the speed increase:\r\nFor these tests I'm clustering with  n_clusters=1000. The feature dimension is 128 and \r\nthe number of data points is 10*n_clusters. I then profiled different versions of the code.\r\nFirst here is the slow version where I force it to perform the finite check every time.\r\n\r\n```python\r\nTotal time: 5.67384 s\r\nFile: /home/joncrall/code/scikit-learn/sklearn/metrics/pairwise.py\r\nFunction: euclidean_distances at line 173\r\n\r\nLine #      Hits         Time  Per Hit   % Time  Line Contents\r\n==============================================================\r\n   173                                           @ut.profile\r\n   174                                           def euclidean_distances(X, Y=None, Y_norm_squared=None, squared=False,\r\n   175                                                                   X_norm_squared=None, force_all_finite=True):\r\n   237      1000      1402395   1402.4     24.7      X, Y = check_pairwise_arrays(X, Y, force_all_finite=True)\r\n   239                                           \r\n   240      1000         1000      1.0      0.0      if X_norm_squared is not None:\r\n   241                                                   XX = check_array(X_norm_squared)\r\n   242                                                   if XX.shape == (1, X.shape[0]):\r\n   243                                                       XX = XX.T\r\n   244                                                   elif XX.shape != (X.shape[0], 1):\r\n   245                                                       raise ValueError(\r\n   246                                                           \"Incompatible dimensions for X and X_norm_squared\")\r\n   247                                               else:\r\n   248      1000        36429     36.4      0.6          XX = row_norms(X, squared=True)[:, np.newaxis]\r\n   249                                           \r\n   250      1000         1251      1.3      0.0      if X is Y:  # shortcut in the common case euclidean_distances(X, X)\r\n   251                                                   YY = XX.T\r\n   252      1000          976      1.0      0.0      elif Y_norm_squared is not None:\r\n   253      1000        15173     15.2      0.3          YY = np.atleast_2d(Y_norm_squared)\r\n   254                                           \r\n   255      1000         2450      2.5      0.0          if YY.shape != (1, Y.shape[0]):\r\n   256                                                       raise ValueError(\r\n   257                                                           \"Incompatible dimensions for Y and Y_norm_squared\")\r\n   258                                               else:\r\n   259                                                   YY = row_norms(Y, squared=True)[np.newaxis, :]\r\n   260                                           \r\n   261      1000      3846672   3846.7     67.8      distances = safe_sparse_dot(X, Y.T, dense_output=True)\r\n   262      1000       108011    108.0      1.9      distances *= -2\r\n   263      1000        64575     64.6      1.1      distances += XX\r\n   264      1000        64196     64.2      1.1      distances += YY\r\n   265      1000       128121    128.1      2.3      np.maximum(distances, 0, out=distances)\r\n   266                                           \r\n   267      1000         1648      1.6      0.0      if X is Y:\r\n   268                                                   # Ensure that distances between vectors and themselves are set to 0.0.\r\n   269                                                   # This may not be the case due to floating point rounding errors.\r\n   270                                                   distances.flat[::distances.shape[0] + 1] = 0.0\r\n   271                                           \r\n   272      1000          941      0.9      0.0      return distances if squared else np.sqrt(distances, out=distances)\r\n```\r\n\r\n\r\nDigging a little deeper shows the timings int his function in this function.\r\nAs you can see most of this functions time is spent in `check_array`.\r\n\r\n```python\r\nTotal time: 1.40017 s\r\nFile: /home/joncrall/code/scikit-learn/sklearn/metrics/pairwise.py\r\nFunction: check_pairwise_arrays at line 58\r\n\r\nLine #      Hits         Time  Per Hit   % Time  Line Contents\r\n==============================================================\r\n    58                                           @ut.profile\r\n    59                                           def check_pairwise_arrays(X, Y, precomputed=False, dtype=None,\r\n    60                                                                     force_all_finite=True):\r\n   104      1000         8652      8.7      0.6      X, Y, dtype_float = _return_float_dtype(X, Y)\r\n   105                                           \r\n   106      1000          659      0.7      0.0      warn_on_dtype = dtype is not None\r\n   107      1000          460      0.5      0.0      estimator = 'check_pairwise_arrays'\r\n   108      1000          507      0.5      0.0      if dtype is None:\r\n   109      1000          524      0.5      0.0          dtype = dtype_float\r\n   110                                           \r\n   111      1000          581      0.6      0.0      if Y is X or Y is None:\r\n   112                                                   X = Y = check_array(X, accept_sparse='csr', dtype=dtype,\r\n   113                                                                       warn_on_dtype=warn_on_dtype, estimator=estimator,\r\n   114                                                                       force_all_finite=force_all_finite)\r\n   115                                               else:\r\n   116      1000          761      0.8      0.1          X = check_array(X, accept_sparse='csr', dtype=dtype,\r\n   117      1000          481      0.5      0.0                          warn_on_dtype=warn_on_dtype, estimator=estimator,\r\n   118      1000       153559    153.6     11.0                          force_all_finite=force_all_finite)\r\n   119      1000          633      0.6      0.0          Y = check_array(Y, accept_sparse='csr', dtype=dtype,\r\n   120      1000          514      0.5      0.0                          warn_on_dtype=warn_on_dtype, estimator=estimator,\r\n   121      1000      1230357   1230.4     87.9                          force_all_finite=force_all_finite)\r\n   122                                           \r\n   123      1000          559      0.6      0.0      if precomputed:\r\n   124                                                   if X.shape[1] != Y.shape[0]:\r\n   125                                                       raise ValueError(\"Precomputed metric requires shape \"\r\n   126                                                                        \"(n_queries, n_indexed). Got (%d, %d) \"\r\n   127                                                                        \"for %d indexed.\" %\r\n   128                                                                        (X.shape[0], X.shape[1], Y.shape[0]))\r\n   129      1000         1287      1.3      0.1      elif X.shape[1] != Y.shape[1]:\r\n   130                                                   raise ValueError(\"Incompatible dimension for X and Y matrices: \"\r\n   131                                                                    \"X.shape[1] == %d while Y.shape[1] == %d\" % (\r\n   132                                                                        X.shape[1], Y.shape[1]))\r\n   133                                           \r\n   134      1000          638      0.6      0.0      return X, Y\r\n```\r\n\r\n\r\nLooking at `check_array` we see the offending function call to `_assert_all_finite`\r\n\r\n```python\r\nTotal time: 1.28438 s\r\nFile: /home/joncrall/code/scikit-learn/sklearn/utils/validation.py\r\nFunction: check_array at line 271\r\n\r\nLine #      Hits         Time  Per Hit   % Time  Line Contents\r\n==============================================================\r\n   271                                           @ut.profile\r\n   272                                           def check_array(array, accept_sparse=None, dtype=\"numeric\", order=None,\r\n   273                                                           copy=False, force_all_finite=True, ensure_2d=True,\r\n   274                                                           allow_nd=False, ensure_min_samples=1, ensure_min_features=1,\r\n   275                                                           warn_on_dtype=False, estimator=None):\r\n\r\n   342      2001         2498      1.2      0.2      if isinstance(accept_sparse, str):\r\n   343      2000         2531      1.3      0.2          accept_sparse = [accept_sparse]\r\n   344                                           \r\n   345                                               # store whether originally we wanted numeric dtype\r\n   346      2001         4113      2.1      0.3      dtype_numeric = dtype == \"numeric\"\r\n   347                                           \r\n   348      2001         3419      1.7      0.3      dtype_orig = getattr(array, \"dtype\", None)\r\n   349      2001         4128      2.1      0.3      if not hasattr(dtype_orig, 'kind'):\r\n   350                                                   # not a data type (e.g. a column named dtype in a pandas DataFrame)\r\n   351                                                   dtype_orig = None\r\n   352                                           \r\n   353      2001         1811      0.9      0.1      if dtype_numeric:\r\n   354         1            1      1.0      0.0          if dtype_orig is not None and dtype_orig.kind == \"O\":\r\n   355                                                       # if input is object, convert to float.\r\n   356                                                       dtype = np.float64\r\n   357                                                   else:\r\n   358         1            1      1.0      0.0              dtype = None\r\n   359                                           \r\n   360      2001         4210      2.1      0.3      if isinstance(dtype, (list, tuple)):\r\n   361                                                   if dtype_orig is not None and dtype_orig in dtype:\r\n   362                                                       # no dtype conversion required\r\n   363                                                       dtype = None\r\n   364                                                   else:\r\n   365                                                       # dtype conversion required. Let's select the first element of the\r\n   366                                                       # list of accepted types.\r\n   367                                                       dtype = dtype[0]\r\n   368                                           \r\n   369      2001         1944      1.0      0.2      if estimator is not None:\r\n   370      2000         3129      1.6      0.2          if isinstance(estimator, six.string_types):\r\n   371      2000         1908      1.0      0.1              estimator_name = estimator\r\n   372                                                   else:\r\n   373                                                       estimator_name = estimator.__class__.__name__\r\n   374                                               else:\r\n   375         1            1      1.0      0.0          estimator_name = \"Estimator\"\r\n   376      2001         3926      2.0      0.3      context = \" by %s\" % estimator_name if estimator is not None else \"\"\r\n   377                                           \r\n   378      2001         3753      1.9      0.3      if sp.issparse(array):\r\n   379                                                   array = _ensure_sparse_format(array, accept_sparse, dtype, copy,\r\n   380                                                                                 force_all_finite)\r\n   381                                               else:\r\n   382      2001         8476      4.2      0.7          array = np.array(array, dtype=dtype, order=order, copy=copy)\r\n   383                                           \r\n   384      2001         2034      1.0      0.2          if ensure_2d:\r\n   385      2001         2534      1.3      0.2              if array.ndim == 1:\r\n   386                                                           if ensure_min_samples >= 2:\r\n   387                                                               raise ValueError(\"%s expects at least 2 samples provided \"\r\n   388                                                                                \"in a 2 dimensional array-like input\"\r\n   389                                                                                % estimator_name)\r\n   390                                                           warnings.warn(\r\n   391                                                               \"Passing 1d arrays as data is deprecated in 0.17 and will \"\r\n   392                                                               \"raise ValueError in 0.19. Reshape your data either using \"\r\n   393                                                               \"X.reshape(-1, 1) if your data has a single feature or \"\r\n   394                                                               \"X.reshape(1, -1) if it contains a single sample.\",\r\n   395                                                               DeprecationWarning)\r\n   396      2001        16453      8.2      1.3              array = np.atleast_2d(array)\r\n   397                                                       # To ensure that array flags are maintained\r\n   398      2001         3891      1.9      0.3              array = np.array(array, dtype=dtype, order=order, copy=copy)\r\n   399                                           \r\n   400                                                   # make sure we actually converted to numeric:\r\n   401      2001         2012      1.0      0.2          if dtype_numeric and array.dtype.kind == \"O\":\r\n   402                                                       array = array.astype(np.float64)\r\n   403      2001         2282      1.1      0.2          if not allow_nd and array.ndim >= 3:\r\n   404                                                       raise ValueError(\"Found array with dim %d. %s expected <= 2.\"\r\n   405                                                                        % (array.ndim, estimator_name))\r\n   406      2001         1898      0.9      0.1          if force_all_finite:\r\n   407      2001      1114783    557.1     86.8              _assert_all_finite(array)\r\n   408                                           \r\n   409      2001        61351     30.7      4.8      shape_repr = _shape_repr(array.shape)\r\n   410      2001         2295      1.1      0.2      if ensure_min_samples > 0:\r\n   411      2001        16251      8.1      1.3          n_samples = _num_samples(array)\r\n   412      2001         2250      1.1      0.2          if n_samples < ensure_min_samples:\r\n   413                                                       raise ValueError(\"Found array with %d sample(s) (shape=%s) while a\"\r\n   414                                                                        \" minimum of %d is required%s.\"\r\n   415                                                                        % (n_samples, shape_repr, ensure_min_samples,\r\n   416                                                                           context))\r\n   417                                           \r\n   418      2001         2557      1.3      0.2      if ensure_min_features > 0 and array.ndim == 2:\r\n   419      2001         2229      1.1      0.2          n_features = array.shape[1]\r\n   420      2001         1982      1.0      0.2          if n_features < ensure_min_features:\r\n   421                                                       raise ValueError(\"Found array with %d feature(s) (shape=%s) while\"\r\n   422                                                                        \" a minimum of %d is required%s.\"\r\n   423                                                                        % (n_features, shape_repr, ensure_min_features,\r\n   424                                                                           context))\r\n   425                                           \r\n   426      2001         1958      1.0      0.2      if warn_on_dtype and dtype_orig is not None and array.dtype != dtype_orig:\r\n   427                                                   msg = (\"Data with input dtype %s was converted to %s%s.\"\r\n   428                                                          % (dtype_orig, array.dtype, context))\r\n   429                                                   warnings.warn(msg, _DataConversionWarning)\r\n   430      2001         1776      0.9      0.1      return array\r\n```\r\n\r\n\r\nDisabling this check after it runs the first time gives a better profile.\r\n\r\nWe could probably even scrape a bit more performance by checking everything at\r\nthe start of kmeans++ and then disabling all subsequent checks. This should be\r\nok because the new centroids are always just previously existing ones. \r\n\r\n```\r\nTotal time: 3.82659 s\r\nFile: /home/joncrall/code/scikit-learn/sklearn/metrics/pairwise.py\r\nFunction: euclidean_distances at line 173\r\n\r\nLine #      Hits         Time  Per Hit   % Time  Line Contents\r\n==============================================================\r\n   173                                           @ut.profile\r\n   174                                           def euclidean_distances(X, Y=None, Y_norm_squared=None, squared=False,\r\n   175                                                                   X_norm_squared=None, force_all_finite=True):\r\n   238      1000       288126    288.1      7.5      X, Y = check_pairwise_arrays(X, Y, force_all_finite=force_all_finite)\r\n   239                                           \r\n   240      1000          718      0.7      0.0      if X_norm_squared is not None:\r\n   241                                                   XX = check_array(X_norm_squared)\r\n   242                                                   if XX.shape == (1, X.shape[0]):\r\n   243                                                       XX = XX.T\r\n   244                                                   elif XX.shape != (X.shape[0], 1):\r\n   245                                                       raise ValueError(\r\n   246                                                           \"Incompatible dimensions for X and X_norm_squared\")\r\n   247                                               else:\r\n   248      1000        21165     21.2      0.6          XX = row_norms(X, squared=True)[:, np.newaxis]\r\n   249                                           \r\n   250      1000          927      0.9      0.0      if X is Y:  # shortcut in the common case euclidean_distances(X, X)\r\n   251                                                   YY = XX.T\r\n   252      1000          699      0.7      0.0      elif Y_norm_squared is not None:\r\n   253      1000         8768      8.8      0.2          YY = np.atleast_2d(Y_norm_squared)\r\n   254                                           \r\n   255      1000         1956      2.0      0.1          if YY.shape != (1, Y.shape[0]):\r\n   256                                                       raise ValueError(\r\n   257                                                           \"Incompatible dimensions for Y and Y_norm_squared\")\r\n   258                                               else:\r\n   259                                                   YY = row_norms(Y, squared=True)[np.newaxis, :]\r\n   260                                           \r\n   261      1000      3174245   3174.2     83.0      distances = safe_sparse_dot(X, Y.T, dense_output=True)\r\n   262      1000        93573     93.6      2.4      distances *= -2\r\n   263      1000        69584     69.6      1.8      distances += XX\r\n   264      1000        72021     72.0      1.9      distances += YY\r\n   265      1000        92431     92.4      2.4      np.maximum(distances, 0, out=distances)\r\n   266                                           \r\n   267      1000         1575      1.6      0.0      if X is Y:\r\n   268                                                   # Ensure that distances between vectors and themselves are set to 0.0.\r\n   269                                                   # This may not be the case due to floating point rounding errors.\r\n   270                                                   distances.flat[::distances.shape[0] + 1] = 0.0\r\n   271                                           \r\n   272      1000          804      0.8      0.0      return distances if squared else np.sqrt(distances, out=distances)\r\n```\r\n\r\n\r\nDisabling the profiler and using a coarser function timer we get the following timings:\r\n\r\nWithout Checks: 3.9655s\r\nWith Checks: 4.9669s\r\n\r\nThis is a 20% decrease in the amount of time taken (1 second total).\r\n\r\n\r\nTo ensure that this speedup was not just for parameters resembling my problem I\r\ndid a gridsearch on various parameter values and looked at the percent change.\r\nFor larget datasets the change is consistently positive. There are a few\r\nnegative changes for small datasets, but this is likely because of random\r\nfluctuations. For datasets with at least a .1 second speed increase, there is a\r\n15% average improvement with the improvement increasing for larger datasets.\r\n\r\n```\r\n    n_clusters  n_features  per_cluster  new_speed  old_speed  percent_change  absolute_change\r\n0         2000         512          200  45.520926  56.996406        0.201337        11.475480\r\n1         2000         512          100  46.009816  57.047427        0.193481        11.037611\r\n2         2000         512           10  46.023527  56.965505        0.192081        10.941978\r\n3         2000         512            1  46.036122  57.028242        0.192749        10.992120\r\n4         2000         128          200  13.359815  16.861238        0.207661         3.501423\r\n5         2000         128          100  13.594423  16.169258        0.159243         2.574835\r\n6         2000         128           10  13.041987  16.357325        0.202682         3.315338\r\n7         2000         128            1  13.517229  15.883567        0.148980         2.366338\r\n8         2000          32          200   4.691806   5.384530        0.128651         0.692724\r\n9         2000          32          100   4.785984   5.434597        0.119349         0.648613\r\n10        2000          32           10   4.816490   5.309634        0.092877         0.493144\r\n11        2000          32            1   4.678081   5.419021        0.136729         0.740940\r\n12        2000           4          200   2.194186   2.311234        0.050643         0.117048\r\n13        2000           4          100   2.195776   2.310168        0.049517         0.114392\r\n14        2000           4           10   2.197284   2.313143        0.050087         0.115859\r\n15        2000           4            1   2.245128   2.298406        0.023181         0.053278\r\n16        1000         512          200  10.325005  13.263920        0.221572         2.938915\r\n17        1000         512          100  10.372535  13.245843        0.216922         2.873308\r\n18        1000         512           10  10.340922  13.195515        0.216331         2.854593\r\n19        1000         512            1  10.377185  13.245806        0.216568         2.868621\r\n20        1000         128          200   2.862865   3.559318        0.195670         0.696453\r\n21        1000         128          100   2.814686   3.682527        0.235664         0.867841\r\n22        1000         128           10   2.866434   3.692132        0.223637         0.825698\r\n23        1000         128            1   3.000796   3.592812        0.164778         0.592016\r\n24        1000          32          200   1.063762   1.172979        0.093111         0.109217\r\n25        1000          32          100   1.053794   1.172330        0.101111         0.118536\r\n26        1000          32           10   1.042551   1.164388        0.104636         0.121837\r\n27        1000          32            1   1.045254   1.165895        0.103475         0.120641\r\n28        1000           4          200   0.576731   0.612182        0.057909         0.035451\r\n29        1000           4          100   0.576767   0.609157        0.053172         0.032390\r\n30        1000           4           10   0.598036   0.607962        0.016327         0.009926\r\n31        1000           4            1   0.578046   0.610441        0.053068         0.032395\r\n32         100         512          200   0.124780   0.144742        0.137913         0.019962\r\n33         100         512          100   0.122643   0.144813        0.153094         0.022170\r\n34         100         512           10   0.123119   0.142057        0.133312         0.018938\r\n35         100         512            1   0.122787   0.144781        0.151913         0.021994\r\n36         100         128          200   0.049460   0.058768        0.158387         0.009308\r\n37         100         128          100   0.060528   0.072691        0.167326         0.012163\r\n38         100         128           10   0.049410   0.061536        0.197052         0.012126\r\n39         100         128            1   0.052959   0.061433        0.137941         0.008474\r\n40         100          32          200   0.029961   0.035051        0.145223         0.005090\r\n41         100          32          100   0.028987   0.033165        0.125970         0.004178\r\n42         100          32           10   0.030262   0.039366        0.231266         0.009104\r\n43         100          32            1   0.028978   0.033200        0.127173         0.004222\r\n44         100           4          200   0.022328   0.027136        0.177188         0.004808\r\n45         100           4          100   0.015451   0.017483        0.116230         0.002032\r\n46         100           4           10   0.014638   0.016714        0.124215         0.002076\r\n47         100           4            1   0.014893   0.018615        0.199944         0.003722\r\n48          10         512          200   0.003733   0.002868       -0.301604        -0.000865\r\n49          10         512          100   0.002347   0.002843        0.174507         0.000496\r\n50          10         512           10   0.002344   0.002907        0.193718         0.000563\r\n51          10         512            1   0.002358   0.006877        0.657086         0.004519\r\n52          10         128          200   0.001717   0.002016        0.148196         0.000299\r\n53          10         128          100   0.007036   0.002073       -2.394020        -0.004963\r\n54          10         128           10   0.001862   0.002053        0.093021         0.000191\r\n55          10         128            1   0.001747   0.002061        0.152244         0.000314\r\n56          10          32          200   0.001596   0.001831        0.128385         0.000235\r\n57          10          32          100   0.001543   0.001787        0.136606         0.000244\r\n58          10          32           10   0.001550   0.001786        0.132159         0.000236\r\n59          10          32            1   0.001551   0.001857        0.164719         0.000306\r\n60          10           4          200   0.001525   0.001715        0.110663         0.000190\r\n61          10           4          100   0.007363   0.001704       -3.320974        -0.005659\r\n62          10           4           10   0.001505   0.001696        0.112470         0.000191\r\n63          10           4            1   0.001494   0.009352        0.840255         0.007858\r\n```\r\n\r\n\r\nThe script I used to generate these numbers is:\r\n```python\r\n\"\"\"\r\npython speedup_kmeans.py --profile\r\npython speedup_kmeans.py\r\n\r\nFor 1000 clusters and 10000 datapoints:\r\n    5 seconds with checks\r\n    3 seconds without checks\r\n    3 seconds without checks and with out safe_dot\r\n\"\"\"\r\nfrom __future__ import absolute_import, division, print_function, unicode_literals\r\nimport utool as ut\r\nimport sklearn  # NOQA\r\nfrom sklearn.datasets.samples_generator import make_blobs\r\nfrom sklearn.utils.extmath import row_norms, squared_norm  # NOQA\r\nimport sklearn.cluster\r\nimport numpy as np\r\nfrom sklearn.metrics.pairwise import euclidean_distances  # NOQA\r\n(print, rrr, profile) = ut.inject2(__name__, '[tester]')\r\n\r\n\r\n#@profile\r\ndef test_kmeans_plus_plus_speed(n_clusters=1000, n_features=128, per_cluster=10, fix=True):\r\n    # Make random cluster centers on a ball\r\n    rng = np.random.RandomState(42)\r\n    centers = rng.rand(n_clusters, n_features)\r\n    centers /= np.linalg.norm(centers, axis=0)[None, :]\r\n    (centers * 512).astype(np.int) / 512\r\n    centers /= np.linalg.norm(centers, axis=0)[None, :]\r\n\r\n    n_samples = n_clusters * 10\r\n    n_clusters, n_features = centers.shape\r\n    X, true_labels = make_blobs(n_samples=n_samples, centers=centers,\r\n                                cluster_std=1., random_state=42)\r\n\r\n    x_squared_norms = row_norms(X, squared=True)\r\n\r\n    _k_init = sklearn.cluster.k_means_._k_init\r\n    random_state = rng\r\n    n_local_trials = None  # NOQA\r\n\r\n    #print('Testing kmeans init')\r\n    with ut.Timer('testing kmeans init') as t:\r\n        centers = _k_init(X, n_clusters, random_state=random_state, x_squared_norms=x_squared_norms, fix=fix)\r\n    #print('Done testing kmeans init')\r\n    return t.ellapsed\r\n\r\n\r\ndef main():\r\n    basis = {\r\n        'n_clusters': [10, 100, 1000, 2000][::-1],\r\n        'n_features': [4, 32, 128, 512][::-1],\r\n        'per_cluster': [1, 10, 100, 200][::-1],\r\n    }\r\n    vals = []\r\n    for kw in ut.ProgIter(ut.all_dict_combinations(basis), lbl='gridsearch',\r\n                          bs=False, adjust=False, freq=1):\r\n        print(kw)\r\n        new_speed = test_kmeans_plus_plus_speed(fix=True, **kw)\r\n        old_speed = test_kmeans_plus_plus_speed(fix=False, **kw)\r\n        kw['new_speed'] = new_speed\r\n        kw['old_speed'] = old_speed\r\n        vals.append(kw)\r\n\r\n    import pandas as pd\r\n    pd.options.display.max_rows = 64\r\n    pd.options.display.width = 100\r\n    pd.options.display.max_ = 64\r\n    df = pd.DataFrame.from_dict(vals)\r\n    df['percent_change'] = (df['old_speed'] - df['new_speed']) / df['old_speed']\r\n    df = df.reindex_axis(['n_clusters', 'n_features', 'per_cluster', 'new_speed', 'old_speed', 'percent_change'], axis=1)\r\n    df['absolute_change'] = (df['old_speed'] - df['new_speed'])\r\n    print(df)\r\n\r\n    print(df['percent_change'][df['absolute_change'] > .1].mean())\r\n    #print(df.loc[df['percent_change'].argsort()[::-1]])\r\n\r\n    #try:\r\n    #    profile.dump_stats('out.lprof')\r\n    #    profile.print_stats(stripzeros=True)\r\n    #except Exception:\r\n    #    pass\r\n\r\n#if __name__ == '__main__':\r\n#    main()\r\n```\r\n"},"comment":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/comments/246693463","html_url":"https://github.com/scikit-learn/scikit-learn/pull/7383#issuecomment-246693463","issue_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/7383","id":246693463,"user":{"login":"Erotemic","id":3186211,"avatar_url":"https://avatars.githubusercontent.com/u/3186211?v=3","gravatar_id":"","url":"https://api.github.com/users/Erotemic","html_url":"https://github.com/Erotemic","followers_url":"https://api.github.com/users/Erotemic/followers","following_url":"https://api.github.com/users/Erotemic/following{/other_user}","gists_url":"https://api.github.com/users/Erotemic/gists{/gist_id}","starred_url":"https://api.github.com/users/Erotemic/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Erotemic/subscriptions","organizations_url":"https://api.github.com/users/Erotemic/orgs","repos_url":"https://api.github.com/users/Erotemic/repos","events_url":"https://api.github.com/users/Erotemic/events{/privacy}","received_events_url":"https://api.github.com/users/Erotemic/received_events","type":"User","site_admin":false},"created_at":"2016-09-13T14:09:48Z","updated_at":"2016-09-13T14:09:48Z","body":"I finished these changes. Let me know if anything looks like it needs more work. "}}
{"actor":{"display_login":"Erotemic"}}