Repository: dirty-cat/dirty_cat (python)

Issue:
fuzzy_join is slow with big number of categories
When I tried to join my table with the [embeddings table](https://soda-inria.github.io/ken_embeddings/) that contain 2.5 million entities, I realised that the [fuzzy_join](https://dirty-cat.github.io/dev/generated/dirty_cat.fuzzy_join.html#dirty_cat.fuzzy_join) is getting increasingly slow with a big number of categories to join.

When I inspected more closely, the most expensive operation is encoding the categories with the [Count Vectorizer](https://scikit-learn.org/stable/modules/generated/sklearn.feature_extraction.text.CountVectorizer.html). To be more precise, it's the [_count_vocab](https://github.com/scikit-learn/scikit-learn/blob/f3f51f9b6/sklearn/feature_extraction/text.py#L1192) that takes too long.

An alternative may be to use the [HashingVectorizer](https://scikit-learn.org/stable/modules/generated/sklearn.feature_extraction.text.HashingVectorizer.html) when the number of categories is bigger than a certain threshold. Similar to what is done in the [SuperVectorizer](https://dirty-cat.github.io/stable/generated/dirty_cat.SuperVectorizer.html#dirty_cat.SuperVectorizer) with the encoders.

Pull request:
Added HashingVectorizer to fuzzy_join.
Fix #418 

Patch:
diff --git a/dirty_cat/_fuzzy_join.py b/dirty_cat/_fuzzy_join.py
index 6db6a41..9a3313a 100644
--- a/dirty_cat/_fuzzy_join.py
+++ b/dirty_cat/_fuzzy_join.py
@@ -1,8 +1,8 @@
 """
 Fuzzy joining tables using string columns.
 The principle is as follows:
-  1. We embed and transform the key string columns using CountVectorizer
-  and TfifdTransformer.
+  1. We embed and transform the key string columns using
+  HashingVectorizer and TfifdTransformer.
   2. For each category, we use the nearest neighbor method to find its closest
   neighbor and establish a match.
   3. We match the tables using the previous information.
@@ -17,7 +17,11 @@ from typing import Literal, Tuple, Union
 import numpy as np
 import pandas as pd
 from scipy.sparse import vstack
-from sklearn.feature_extraction.text import CountVectorizer, TfidfTransformer
+from sklearn.feature_extraction.text import (
+    HashingVectorizer,
+    TfidfTransformer,
+    _VectorizerMixin,
+)
 from sklearn.neighbors import NearestNeighbors
 
 
@@ -28,6 +32,7 @@ def fuzzy_join(
     left_on: Union[str, None] = None,
     right_on: Union[str, None] = None,
     on: Union[str, None] = None,
+    encoder: Union[Literal["hashing"], _VectorizerMixin] = None,
     analyzer: Literal["word", "char", "char_wb"] = "char_wb",
     ngram_range: Tuple[int, int] = (2, 4),
     return_score: bool = False,
@@ -60,9 +65,14 @@ def fuzzy_join(
         Name of common left and right table join key columns.
         Must be found in both DataFrames. Use only if `left_on`
         and `right_on` parameters are not specified.
+    encoder: Union[Literal["hashing"], _VectorizerMixin], default=None,
+        Encoder parameter for the Vectorizer.
+        Options: {None, `_VectorizerMixin`}. If None, the
+        encoder will use the `HashingVectorizer`. It is possible to pass a
+        `_VectorizerMixin` custom object to tweak the parameters of the encoder.
     analyzer : {"word", "char", "char_wb"}, optional, default=`char_wb`
-        Analyzer parameter for the CountVectorizer used for the string
-        similarities.
+        Analyzer parameter for the HashingVectorizer passed to
+        the encoder and used for the string similarities.
         Options: {`word`, `char`, `char_wb`}, describing whether the matrix V
         to factorize should be made of word counts or character n-gram counts.
         Option `char_wb` creates character n-grams only from text inside word
@@ -162,6 +172,10 @@ def fuzzy_join(
             f"analyzer should be either 'char', 'word' or 'char_wb', got {analyzer!r}",
         )
 
+    if encoder is not None:
+        if not issubclass(encoder.__class__, _VectorizerMixin):
+            raise ValueError(f"encoder should be a vectorizer object, got {encoder!r}")
+
     if how not in ["left", "right"]:
         raise ValueError(
             f"how should be either 'left' or 'right', got {how!r}",
@@ -206,10 +220,13 @@ def fuzzy_join(
     main_col_clean = main_table[main_col].astype(str)
     aux_col_clean = aux_table[aux_col].astype(str)
 
-    enc = CountVectorizer(analyzer=analyzer, ngram_range=ngram_range)
-
     all_cats = pd.concat([main_col_clean, aux_col_clean], axis=0).unique()
 
+    if encoder is None:
+        enc = HashingVectorizer(analyzer=analyzer, ngram_range=ngram_range)
+    else:
+        enc = encoder
+
     enc_cv = enc.fit(all_cats)
     main_enc = enc_cv.transform(main_col_clean)
     aux_enc = enc_cv.transform(aux_col_clean)
diff --git a/dirty_cat/_target_encoder.py b/dirty_cat/_target_encoder.py
index 14017a0..e87e411 100644
--- a/dirty_cat/_target_encoder.py
+++ b/dirty_cat/_target_encoder.py
@@ -44,8 +44,8 @@ class TargetEncoder(BaseEstimator, TransformerMixin):
         Whether to raise an error or ignore if a unknown categorical feature is
         present during transform (default is to raise). When this parameter
         is set to 'ignore' and an unknown category is encountered during
-        transform, the resulting one-hot encoded columns for this feature
-        will be all zeros.
+        transform, the encoded columns for this feature
+        will be assigned the prior mean of the target variable.
     handle_missing : typing.Literal["error", ""], default=""
         Whether to raise an error or impute with blank string '' if missing
         values (NaN) are present during fit (default is to impute).
@@ -81,16 +81,19 @@ class TargetEncoder(BaseEstimator, TransformerMixin):
     >>> enc.categories_
     [array(['Female', 'Male', 'male'], dtype='<U6')]
 
-    We look at the encoded categories :
+    We will encode the following categories, of which the first two are unknown :
+
+    >>> X2 = [['MALE'], ['FEMALE'], ['Female'], ['male'], ['Female']]
 
-    >>> enc.transform(X)
-    array([[3.44444444],
-        [2.11111111],
-        [3.61538462],
-        [3.44444444],
-        [3.61538462]])
+    >>> enc.transform(X2)
+    array([[3.        ],
+        [3.        ],
+        [3.54545455],
+        [2.72727273],
+        [3.54545455]])
 
     As expected, they were encoded according to their influence on y.
+    The unknown categories were assigned the mean of the target variable.
 
     """
 


Test patch:
diff --git a/dirty_cat/tests/test_fuzzy_join.py b/dirty_cat/tests/test_fuzzy_join.py
index d90a132..11ea7cc 100644
--- a/dirty_cat/tests/test_fuzzy_join.py
+++ b/dirty_cat/tests/test_fuzzy_join.py
@@ -1,6 +1,7 @@
 import numpy as np
 import pandas as pd
 import pytest
+from sklearn.feature_extraction.text import HashingVectorizer
 
 from dirty_cat import fuzzy_join
 
@@ -201,3 +202,42 @@ def test_fuzzy_join_pandas_comparison():
     result_s_fj.rename(columns={"key_x": "key"}, inplace=True)
 
     pd.testing.assert_frame_equal(result_s, result_s_fj)
+
+
+def test_correct_encoder():
+    """Test that the encoder error checking is working as intended."""
+
+    class TestVectorizer(HashingVectorizer):
+        """Implements a custom vectorizer to check if the `encoder`
+        parameter uses the passed instance as expected.
+        Raises an error when `fit` is called.
+        """
+
+        def fit(self, X):
+            raise AssertionError("Custom vectorizer was called as intended.")
+
+    left = pd.DataFrame(
+        {
+            "key": ["K0", "K1", "K2", "K3"],
+            "A": ["A0", "A1", "A2", "A3"],
+            "B": ["B0", "B1", "B2", "B3"],
+        }
+    )
+
+    right = pd.DataFrame(
+        {
+            "key": ["K0", "K1", "K2", "K3"],
+            "C": ["C0", "C1", "C2", "C3"],
+            "D": ["D0", "D1", "D2", "D3"],
+        }
+    )
+
+    enc = TestVectorizer()
+
+    with pytest.raises(
+        AssertionError, match=r"Custom vectorizer was called as intended."
+    ):
+        fuzzy_join(left, right, on="key", how="left", encoder=enc)
+
+    with pytest.raises(ValueError, match=r"encoder should be a vectorizer object"):
+        fuzzy_join(left, right, on="key", how="left", encoder="awrongencoder")
diff --git a/dirty_cat/tests/utils.py b/dirty_cat/tests/utils.py
index baf55bd..c6c3756 100644
--- a/dirty_cat/tests/utils.py
+++ b/dirty_cat/tests/utils.py
@@ -8,6 +8,7 @@ def generate_data(
     n_samples,
     as_list=False,
     random_state: Optional[Union[int, float, str, bytes, bytearray]] = None,
+    sample_length: int = 100,
 ) -> np.ndarray:
     if random_state is not None:
         random.seed(random_state)
@@ -15,7 +16,7 @@ def generate_data(
     str_list = []
     for i in range(n_samples):
         random_string = "category "
-        for _ in range(100):
+        for _ in range(sample_length):
             random_integer = random.randint(1, MAX_LIMIT)
             random_string += chr(random_integer)
             if random_integer < 50: