Repository: scikit-learn/scikit-learn
Pull request: change stats.mode to collections.Counter, for better performance.
<!--
Thanks for contributing a pull request! Please ensure you have taken a look at
the contribution guidelines: https://github.com/scikit-learn/scikit-learn/blob/master/CONTRIBUTING.md#pull-request-checklist
-->

#### Reference Issues/PRs
<!--
Example: Fixes #1234. See also #3456.
Please use keywords (e.g., Fixes) to create link to the issues or pull requests
you resolved, so that they will automatically be closed when your pull request
is merged. See https://github.com/blog/1506-closing-issues-via-pull-requests
-->
Fixes #18978

#### What does this implement/fix? Explain your changes.
As suggested in the issue we replaced `scipy.stats.mode` with `collections.Counter` since it has better performance.

<!--
Please be aware that we are a loose team of volunteers so patience is
necessary; assistance handling other issues is very welcome. We value
all user contributions, no matter how minor they are. If we are slow to
review, either the pull request needs some benchmarking, tinkering,
convincing, etc. or more likely the reviewers are simply busy. In either
case, we ask for your understanding during the review process.
For more information, see our FAQ on this topic:
http://scikit-learn.org/dev/faq.html#why-is-my-pull-request-not-getting-any-attention.

Thanks for contributing!
-->


Problem statement:
SimpleImputer performance on strings 
#### Describe the bug

SimpleImputer is extremely slow on string/object categories using option "most_frequent".

#### Steps/Code to Reproduce

```python
import sys; print('python', sys.version)
import numpy as np
import pandas as pd
from sklearn.impute import SimpleImputer

si = SimpleImputer(strategy='most_frequent')

n = 1_000_000
df = pd.DataFrame(
    dict(a_string_column = np.random.choice(['a', 'b'], n),
         a_numeric_column = np.random.choice([1, 2], n))
)

print('np.unique:')
%time np.unique(df.a_string_column, return_counts=True)

print('\nsimple imputer numeric:')
%time si.fit(df[['a_numeric_column']])

print('\nsimple imputer string/object:')
%time si.fit(df[['a_string_column']])
```
#### Output
```
np.unique:
Wall time: 766 ms

simple imputer numeric:
Wall time: 43 ms

simple imputer string/object:
Wall time: 29.7 s
```

#### Versions
```
System:
    python: 3.7.9
   machine: Windows-10

Python dependencies:
          pip: 20.2.4
   setuptools: 50.3.0.post20201006
      sklearn: 0.23.2
        numpy: 1.19.4
        scipy: 1.4.1
       Cython: None
       pandas: 1.1.3
   matplotlib: 3.3.1
       joblib: 0.17.0
threadpoolctl: 2.1.0
```

Hints from issue discussion:
Yep we are using `scipy.stats.mode` which is doing a terrible job with a numpy array with object dtype (probably fall-back to iterate with a Python for loop). I think that we should default using `Counter` when we have this type of data (the same way we use `set` to get uniques).

I put some code to illustrate that `Counter` is much faster (in the order of hundred ms instead of 10 s)
(I don't give definitive benchmark because I don't have a computer which does not share resource with other application)

```python
# %%
import numpy as np

n = 1_000_000
x = np.random.choice(np.array(['a', 'b'], dtype=object), n)

# %%
from collections import Counter
from scipy import stats

# %%
%%time

mode = stats.mode(x)
mode

# %%
%%time

uniques, counts = np.unique(x, return_counts=True)
mode = (uniques[counts.argmax()], counts.max())
mode

# %%
%%time

count = Counter(x)
mode = (max(count, key=count.get), count[max(count, key=count.get)])
mode
```
@glemaitre : Excellent idea, `Counter` seems very performant. Unlike np.unique, it would also count `np.nan` (which might be desireable or not...).
@glemaitre Good idea using `Counter`!
You can get the mode even a bit simpler:
```python
count = Counter(x)
mode = count.most_common(1)
```

Now we need someone volunteering to work out a PR.
Hi @lorentzenchr 
Can I be assigned to this PR?
@DavidKatz-il feel free to comment below with `take` to be assigned to this PR 
take
If there is more than one value, `scipy.stats` returns the smallest, and `Counter` will return the first on (base on the original array).
```python
In [1]: from collections import Counter
   ...: from scipy import stats
   ...: arr = [3, 2, 1]
   ...: print(stats.mode(arr))
   ...: print(Counter(arr).most_common(1))
   ...:
ModeResult(mode=array([1]), count=array([1]))
[(3, 1)]
```
Should we take care of this?
If NO, we will need to make changes to the tests with those cases.
If can keep the same behaviour when breaking tie, it would be better.
I did not read the doc of `stats.mode` but there is maybe a need to sort
the keys of Counter to ge the same results

On Wed, 9 Dec 2020 at 17:50, David Katz <notifications@github.com> wrote:

> If there is more than one value, scipy.stats returns the smallest, and
> Counter will return the first on (base on the original array).
>
> In [1]: from collections import Counter
>    ...: from scipy import stats
>    ...: arr = [3, 2, 1]
>    ...: print(stats.mode(arr))
>    ...: print(Counter(arr).most_common(1))
>    ...:ModeResult(mode=array([1]), count=array([1]))
> [(3, 1)]
>
> Should we take care of this?
> If NO, we will need to make changes to the tests with those cases.
>
> —
> You are receiving this because you were mentioned.
> Reply to this email directly, view it on GitHub
> <https://github.com/scikit-learn/scikit-learn/issues/18978#issuecomment-741900669>,
> or unsubscribe
> <https://github.com/notifications/unsubscribe-auth/ABY32PYH4KZRTL3L6HVZ6ELST6THHANCNFSM4URZ4WQQ>
> .
>


-- 
Guillaume Lemaitre
Scikit-learn @ Inria Foundation
https://glemaitre.github.io/

> If can keep the same behaviour when breaking tie, it would be better. I did not read the doc of `stats.mode` but there is maybe a need to sort the keys of Counter to ge the same results

from `scipy.stats.mode`  [doc](https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.mode.html)
> If there is more than one such value, only the smallest is returned.    
   

The following code will keep the same behavior.
```python 
counter = Counter(x)
most_frequent_count = counter.most_common(1)[0][1]
most_frequent_value = min(value for value, count in counter.items() if count == most_frequent_count) 
```


I think we should also change:
```python
        if most_frequent_value < extra_value:
            return most_frequent_value
        else:
            return extra_value
```
to
```python
        return min(most_frequent_value, extra_value)
```

Commit message: add a test for testing all _most_frequent options

Patch to review:
diff --git a/sklearn/impute/_base.py b/sklearn/impute/_base.py
index dd6922ce5b9f3..644a268b66728 100644
--- a/sklearn/impute/_base.py
+++ b/sklearn/impute/_base.py
@@ -7,6 +7,7 @@
 
 import numpy as np
 import numpy.ma as ma
+from collections import Counter
 from scipy import sparse as sp
 from scipy import stats
 
@@ -34,15 +35,17 @@ def _most_frequent(array, extra_value, n_repeat):
        of the array."""
     # Compute the most frequent value in array only
     if array.size > 0:
-        with warnings.catch_warnings():
-            # stats.mode raises a warning when input array contains objects due
-            # to incapacity to detect NaNs. Irrelevant here since input array
-            # has already been NaN-masked.
-            warnings.simplefilter("ignore", RuntimeWarning)
+        if array.dtype == object:
+            counter = Counter(array)
+            most_frequent_count = counter.most_common(1)[0][1]
+            most_frequent_value = min(
+                value for value, count in counter.items()
+                if count == most_frequent_count
+            )
+        else:
             mode = stats.mode(array)
-
-        most_frequent_value = mode[0][0]
-        most_frequent_count = mode[1][0]
+            most_frequent_value = mode[0][0]
+            most_frequent_count = mode[1][0]
     else:
         most_frequent_value = 0
         most_frequent_count = 0
@@ -55,11 +58,7 @@ def _most_frequent(array, extra_value, n_repeat):
     elif most_frequent_count > n_repeat:
         return most_frequent_value
     elif most_frequent_count == n_repeat:
-        # Ties the breaks. Copy the behaviour of scipy.stats.mode
-        if most_frequent_value < extra_value:
-            return most_frequent_value
-        else:
-            return extra_value
+        return min(most_frequent_value, extra_value)
 
 
 class _BaseImputer(TransformerMixin, BaseEstimator):
diff --git a/sklearn/impute/tests/test_impute.py b/sklearn/impute/tests/test_impute.py
index 4c0918b9a3230..27479a9d4c043 100644
--- a/sklearn/impute/tests/test_impute.py
+++ b/sklearn/impute/tests/test_impute.py
@@ -27,6 +27,7 @@
 from sklearn import tree
 from sklearn.random_projection import _sparse_random_matrix
 from sklearn.exceptions import ConvergenceWarning
+from .._base import _most_frequent
 
 
 def _check_statistics(X, X_true,
@@ -1474,3 +1475,29 @@ def test_simple_imputation_inverse_transform_exceptions(missing_value):
     with pytest.raises(ValueError,
                        match=f"Got 'add_indicator={imputer.add_indicator}'"):
         imputer.inverse_transform(X_1_trans)
+
+
+def test_most_frequent():
+    # collections.Counter
+    assert np.isnan(_most_frequent(np.array([]), 'extra_value', 0))
+    assert 'extra_value' == _most_frequent(
+        np.array(['a', 'b', 'c'], dtype=object), 'extra_value', 2
+    )
+    assert 'most_frequent_value' == _most_frequent(
+        np.array(
+            ['most_frequent_value', 'most_frequent_value', 'value'],
+            dtype=object), 'extra_value', 1
+    )
+    assert 'a' == _most_frequent(np.array(
+        ['min_value', 'min_value' 'value'], dtype=object), 'a', 2
+    )
+    assert 'min_value' == _most_frequent(
+        np.array(['min_value', 'min_value', 'value'], dtype=object), 'z', 2
+    )
+
+    # scipy.stats.mode
+    assert np.isnan(_most_frequent(np.array([]), 10, 0))
+    assert 10 == _most_frequent(np.array([1, 2, 3]), 10, 2)
+    assert 1 == _most_frequent(np.array([1, 1, 2]), 10, 1)
+    assert 10 == _most_frequent(np.array([20, 20, 1]), 10, 2)
+    assert 1 == _most_frequent(np.array([1, 1, 20], dtype=object), 10, 2)


Code review comments:
diff_hunk: @@ -34,15 +35,17 @@ def _most_frequent(array, extra_value, n_repeat):
        of the array."""
     # Compute the most frequent value in array only
     if array.size > 0:
-        with warnings.catch_warnings():
-            # stats.mode raises a warning when input array contains objects due
-            # to incapacity to detect NaNs. Irrelevant here since input array
-            # has already been NaN-masked.
-            warnings.simplefilter("ignore", RuntimeWarning)
+        if array.dtype == object:
+            counter = Counter(array)
path: sklearn/impute/_base.py
text: @user1:
```suggestion
            # scipy.stats.mode is slow with object dtype array.
            # Python Counter is more efficient
            counter = Counter(array)
```

diff_hunk: @@ -27,6 +27,7 @@
 from sklearn import tree
 from sklearn.random_projection import _sparse_random_matrix
 from sklearn.exceptions import ConvergenceWarning
+from .._base import _most_frequent
path: sklearn/impute/tests/test_impute.py
text: @user1:
```suggestion
from sklearn.impute._base import _most_frequent
```