Repository: dirty-cat/dirty_cat
Pull request #109 (2020-01-08 13:45:06)

[WIP] Add Fast hash
Add fast hash and the minmax hashing encoder. 


Patch:
diff --git a/CHANGES.rst b/CHANGES.rst
index 2bae756..9a8e509 100644
--- a/CHANGES.rst
+++ b/CHANGES.rst
@@ -1,17 +1,24 @@
 Release 0.0.7
 =============
+
+* **MinHashEncoder**: Added ``minhash_encoder.py`` and ``fast_hast.py`` files
+  that implement minhash encoding through the ``MinHashEncoder`` class.
+  This method allows for fast and scalable encoding of string categorical
+  variables.
+
 * **datasets.fetch_employee_salaries**: change the origin of download for employee_salaries.
+
   - The function now return a bunch with a dataframe under the field "data",
     and not the path to the csv file. 
   - The field "description" has been renamed to "DESCR".
 
-
-Release 0.0.6
-=============
 * **SimilarityEncoder**: Fixed a bug when using the Jaro-Winkler distance as a
   similarity metric. Our implementation now accurately reproduces the behaviour
   of the ``python-Levenshtein`` implementation.
 
+Release 0.0.6
+=============
+
 * **SimilarityEncoder**: Accelerate ``SimilarityEncoder.transform``, by:
 
   - computing the vocabulary count vectors in ``fit`` instead of ``transform``
diff --git a/README.rst b/README.rst
index cdd6b87..a4925ac 100644
--- a/README.rst
+++ b/README.rst
@@ -7,7 +7,8 @@ Website: https://dirty-cat.github.io/
 
 For a detailed description of the problem of encoding dirty categorical data,
 see `Similarity encoding for learning with dirty categorical variables
-<https://hal.inria.fr/hal-01806175>`_ [1]_.
+<https://hal.inria.fr/hal-01806175>`_ [1]_ and `Encoding high-cardinality string categorical variables
+<https://hal.inria.fr/hal-02171256v4>`_ [2]_.
 
 Installation
 ------------
@@ -45,3 +46,4 @@ References
 ~~~~~~~~~~
 
 .. [1] Patricio Cerda, Gaël Varoquaux, Balázs Kégl. Similarity encoding for learning with dirty categorical variables. 2018, Machine Learning journal, Springer.
+.. [2] Patricio Cerda, Gaël Varoquaux. Encoding high-cardinality string categorical variables, 2019.
diff --git a/dirty_cat/__init__.py b/dirty_cat/__init__.py
index 54fafc0..fef06a1 100644
--- a/dirty_cat/__init__.py
+++ b/dirty_cat/__init__.py
@@ -9,5 +9,6 @@ with open(version_file) as fh:
 
 from .similarity_encoder import SimilarityEncoder
 from .target_encoder import TargetEncoder
+from .minhash_encoder import MinHashEncoder
 
-__all__ = ['SimilarityEncoder', 'TargetEncoder']
+__all__ = ['SimilarityEncoder', 'TargetEncoder', 'MinHashEncoder']
diff --git a/dirty_cat/fast_hash.py b/dirty_cat/fast_hash.py
new file mode 100644
index 0000000..5bd56fd
--- /dev/null
+++ b/dirty_cat/fast_hash.py
@@ -0,0 +1,97 @@
+"""
+n-gram hashing by simple dot products
+
+The principle is as follows:
+  1. A string is viewed as a succession of numbers (the ASCII or UTF8
+     representation of its elements).
+  2. Each n-gram is then an n-dimensional vector of integers "g". A simple
+     hash function is then computed by taking the dot product with a
+     given random vector "atom", modulo max-int (integers larger than
+     max-int overflow). The corresponding operation defines a random
+     order in the interval [-maxint, maxint]
+  3. Computing this dot product over a sliding window (to compute it for
+     every n-gram is a convolution
+  4. We can then take the min (or the max) of the resulting sliding
+  window
+
+"""
+import functools
+import numpy as np
+
+# Precompute to avoid the cost and
+# cast to int32 to speedup the min 
+MININT32 = np.int32(-2 ** (32 - 1))
+MAXINT32 = np.int32(2 ** (32 - 1) - 1)
+
+@functools.lru_cache(maxsize=1024)
+def gen_atom(atom_len, seed=0):
+    """ Generate a random integer array (atom).
+
+    Parameters
+    ----------
+    atom_len : int
+        The length of the atom.
+    seed : int, default=0
+        The seed of the random_number generator.
+
+    Returns
+    -------
+    array, shape (atom_len, )
+        An array of random integers of length atom_len and dtype int32
+        (assuming dtype_size=32).
+    """
+    rng = np.random.RandomState(seed)
+    atom = rng.randint(-MAXINT32, MAXINT32, size=atom_len,
+                       dtype=np.dtype('int32'))
+    return atom
+
+
+def ngram_min_hash(string, ngram_range=(2, 4), seed=0, return_minmax=False):
+    """ Compute the min/max hash of the ngrams of the string.
+
+    Parameters
+    ----------
+    string : str
+        String to encode.
+    ngram_range : tuple (min_n, max_n), default=(2, 4)
+        The lower and upper boundary of the range of n-values 
+        for different n-grams to be extracted.
+    seed : int, default=0
+        Integer used to seed the hashing function.
+    return_minmax : bool, default=False
+        If True, returns both the minhash and maxhash of the string.
+        Else, only returns the minhash. 
+    Returns
+    -------
+    int or tuple 
+        The min_hash or (min_hash, max_hash) of the n-grams of the string.
+
+    """
+    # Create a numerical 1D array from the string
+    array = np.frombuffer(string.encode(), dtype='int8', count=len(string))
+
+    max_hash = MININT32
+    min_hash = MAXINT32
+    for atom_len in range(ngram_range[0], ngram_range[1]):
+        atom = gen_atom(atom_len, seed=seed)
+        # np.correlate is faster than np.convolve
+        # the convolution gives a hash for each ngram
+        hashes = np.correlate(array, atom)
+        min_hash = min(min_hash, hashes.min())
+        if return_minmax:
+            max_hash = max(max_hash, hashes.max())
+
+    # We should check that longer windows do not have different
+    # statistics from shorter ones
+    if return_minmax:
+        return min_hash, max_hash
+    return min_hash
+
+
+if __name__ == '__main__':
+    # Download demo text
+    from sklearn import datasets
+    data = datasets.fetch_20newsgroups()
+    a = data.data[0]
+
+    h = ngram_min_hash(a)
diff --git a/dirty_cat/minhash_encoder.py b/dirty_cat/minhash_encoder.py
new file mode 100644
index 0000000..cc1ccdd
--- /dev/null
+++ b/dirty_cat/minhash_encoder.py
@@ -0,0 +1,197 @@
+"""
+Minhash encoding of string arrays.
+The principle is as follows:
+  1. A string is viewed as a succession of numbers (the ASCII or UTF8
+     representation of its elements).
+  2. The string is then decomposed into a set of n-grams, i.e.
+     n-dimensional vectors of integers.
+  3. A hashing function is used to assign an integer to each n-gram.
+     The minimum of the hashes over all n-grams is used in the encoding.
+  4. This process is repeated with N hashing functions are used to 
+     form N-dimensional encodings.
+Maxhash encodings can be computed similarly by taking the hashes maximum
+instead.
+With this procedure, strings that share many n-grams have greater
+probability of having same encoding values. These encodings thus capture
+morphological similarities between strings.
+"""
+import warnings
+
+import numpy as np
+from joblib import Parallel, delayed
+from scipy import sparse
+from sklearn.cluster import KMeans
+from sklearn.feature_extraction.text import CountVectorizer, HashingVectorizer
+from sklearn.neighbors import NearestNeighbors
+from sklearn.base import BaseEstimator, TransformerMixin
+from sklearn.utils import check_random_state, murmurhash3_32 
+
+from .fast_hash import ngram_min_hash
+from .utils import LRUDict
+
+class MinHashEncoder(BaseEstimator, TransformerMixin):
+    """
+    Encode string categorical features as a numeric array, minhash method
+    applied to ngram decomposition of strings based on ngram decomposition
+    of the string.
+
+    Parameters
+    ----------
+    n_components : int
+        The number of dimension of encoded strings.
+    ngram_range : tuple (min_n, max_n), default=(2, 4)
+        The lower and upper boundary of the range of n-values for different
+        n-grams to be extracted. All values of n such that min_n <= n <= max_n.
+        will be used.
+    hashing : str {'fast', 'murmur'}, default=fast
+        Hashing function. fast is faster but
+        might have some concern with its entropy.
+    minmax_hash : bool, default=False
+        if True, return min hash and max hash concatenated.
+    References
+    ----------
+    For a detailed description of the method, see
+    `Encoding high-cardinality string categorical variables
+    <https://hal.inria.fr/hal-02171256v4>`_ by Cerda, Varoquaux (2019).
+    
+    """
+
+    def __init__(self, n_components, ngram_range=(2, 4),
+                 hashing='fast', minmax_hash=False):
+        self.ngram_range = ngram_range
+        self.n_components = n_components
+        self.hashing = hashing
+        self.minmax_hash = minmax_hash
+        self.count = 0
+
+    def get_unique_ngrams(self, string, ngram_range):
+        """ Return the set of unique n-grams of a string.
+        Parameters
+        ----------
+        string : str
+            The string to split in n-grams.
+        ngram_range : tuple (min_n, max_n)
+        The lower and upper boundary of the range of n-values for different
+        n-grams to be extracted. All values of n such that min_n <= n <= max_n.
+        Returns
+        -------
+        set
+            The set of unique n-grams of the string.
+        """
+        spaces = ' '  # * (n // 2 + n % 2)
+        string = spaces + " ".join(string.lower().split()) + spaces
+        ngram_set = set()
+        for n in range(ngram_range[0], ngram_range[1] + 1):
+            string_list = [string[i:] for i in range(n)]
+            ngram_set |= set(zip(*string_list))
+        return ngram_set
+
+    def minhash(self, string, n_components, ngram_range):
+        """ Encode a string using murmur hashing function.
+        Parameters
+        ----------
+        string : str
+            The string to encode.
+        n_components : int
+            The number of dimension of encoded string.
+        ngram_range : tuple (min_n, max_n)
+        The lower and upper boundary of the range of n-values for different
+        n-grams to be extracted. All values of n such that min_n <= n <= max_n.
+        Returns
+        -------
+        array, shape (n_components, )
+            The encoded string.
+        """
+        min_hashes = np.ones(n_components) * np.infty
+        grams = self.get_unique_ngrams(string, self.ngram_range)
+        if len(grams) == 0:
+            grams = self.get_unique_ngrams(' Na ', self.ngram_range)
+        for gram in grams:
+            hash_array = np.array([
+                murmurhash3_32(''.join(gram), seed=d, positive=True)
+                for d in range(n_components)])
+            min_hashes = np.minimum(min_hashes, hash_array)
+        return min_hashes/(2**32-1)
+
+    def get_hash(self, string):
+        """
+        Encode a string with murmur or fast hashing function.
+        fast hashing supports both min_hash and minmax_hash encoding,
+        whereas murmur only supports min_hash encoding.
+        Parameters
+        ----------
+        string : str
+            The string to encode.
+        Returns
+        -------
+        array, shape (n_components, )
+            The encoded string, using specified encoding scheme.
+        """
+        if self.hashing == 'fast':
+            if self.minmax_hash:
+                assert self.n_components % 2 == 0,\
+                       "n_components should be even when minmax_hash=True"
+                return np.concatenate([ngram_min_hash(string, self.ngram_range,
+                                                      seed, return_minmax=True)
+                                      for seed in range(self.n_components//2)])
+            else:
+                return np.array([ngram_min_hash(string, self.ngram_range, seed)
+                                for seed in range(self.n_components)])
+
+        elif self.hashing == 'murmur':
+            assert not(self.minmax_hash),\
+                   "minmax_hash not implemented with murmur"
+            return self.minhash(
+                    string, n_components=self.n_components,
+                    ngram_range=self.ngram_range)
+        else:
+            raise ValueError("hashing function must be 'fast' or"
+                             "'murmur', got '{}'"
+                             "".format(self.hashing))
+
+    def fit(self, X, y=None):
+        """
+        Fit the MinHashEncoder to X. In practice, just initializes a dictionary
+        to store encodings to speed up computation.
+        Parameters
+        ----------
+        X : array-like, shape (n_samples, ) or (n_samples, 1)
+            The string data to encode.
+        
+        Returns
+        -------
+        self
+            The fitted MinHashEncoder instance. 
+        """
+        self.hash_dict = LRUDict(capacity=2**10)
+        return self
+
+    def transform(self, X):
+        """ Transform X using specified encoding scheme.
+        Parameters
+        ----------
+        X : array-like, shape (n_samples, ) or (n_samples, 1)
+            The string data to encode.
+        Returns
+        -------
+        array, shape (n_samples, n_components)
+            Transformed input.
+        """
+        X = np.asarray(X)
+        assert X.ndim == 1 or (X.ndim == 2 and X.shape[1] == 1), f"ERROR:\
+        shape {X.shape} of input array is not supported."
+        if X.ndim == 2:
+            X = X[:, 0]
+        # Check if first item has str or np.str_ type
+        assert isinstance(X[0], str), "ERROR: Input data is not string."
+        X_out = np.zeros((len(X), self.n_components))
+
+        # TODO Parallel run here
+        for i, x in enumerate(X):
+            if x not in self.hash_dict:
+                self.hash_dict[x] = self.get_hash(x)
+
+        for i, x in enumerate(X):
+            X_out[i, :] = self.hash_dict[x]
+            
+        return X_out
diff --git a/dirty_cat/utils.py b/dirty_cat/utils.py
new file mode 100644
index 0000000..c9808b1
--- /dev/null
+++ b/dirty_cat/utils.py
@@ -0,0 +1,29 @@
+import collections
+
+
+class LRUDict:
+    """ dict with limited capacity
+
+    Using LRU eviction, this avoid to memorizz a full dataset"""
+    def __init__(self, capacity):
+        self.capacity = capacity
+        self.cache = collections.OrderedDict()
+
+    def __getitem__(self, key):
+        try:
+            value = self.cache.pop(key)
+            self.cache[key] = value
+            return value
+        except KeyError:
+            return -1
+
+    def __setitem__(self, key, value):
+        try:
+            self.cache.pop(key)
+        except KeyError:
+            if len(self.cache) >= self.capacity:
+                self.cache.popitem(last=False)
+        self.cache[key] = value
+
+    def __contains__(self, key):
+        return key in self.cache
diff --git a/doc/index.rst b/doc/index.rst
index 79aa407..e2e3c49 100644
--- a/doc/index.rst
+++ b/doc/index.rst
@@ -14,10 +14,13 @@ robust to morphological variants**, such as typos, in the category strings.
 The :class:`SimilarityEncoder` is a drop-in replacement for
 `scikit-learn <https://scikit-learn.org>`_'s
 :class:`~sklearn.preprocessing.OneHotEncoder`.
+If speed and scalability are an issue, the :class:`MinHashEncoder` provides
+a fast encoding method.
 
 For a detailed description of the problem of encoding dirty categorical data,
 see `Similarity encoding for learning with dirty categorical variables
-<https://hal.inria.fr/hal-01806175>`_ [1]_.
+<https://hal.inria.fr/hal-01806175>`_ [1]_ and `Encoding high-cardinality
+string categorical variables <https://hal.inria.fr/hal-02171256v4>`_ [2]_.
 
 :Installing: `$ pip install --user dirty_cat`
 
@@ -44,6 +47,7 @@ Encoders
    :template: class.rst
    :nosignatures:
 
+   MinHashEncoder
    SimilarityEncoder
    TargetEncoder
 
@@ -85,4 +89,5 @@ contributions in the scope of dirty categories.
    https://github.com/rakutentech/spark-dirty-cat
 
 .. [1] Patricio Cerda, Gaël Varoquaux, Balázs Kégl. Similarity encoding for learning with dirty categorical variables. 2018. Machine Learning journal, Springer.
+.. [2] Patricio Cerda, Gaël Varoquaux. Encoding high-cardinality string categorical variables, 2019.
 
diff --git a/examples/02_fit_predict_plot_employee_salaries.py b/examples/02_fit_predict_plot_employee_salaries.py
index 4db37ad..67bf7d9 100644
--- a/examples/02_fit_predict_plot_employee_salaries.py
+++ b/examples/02_fit_predict_plot_employee_salaries.py
@@ -55,7 +55,7 @@ clean_columns = {
 # We then choose the categorical encoding methods we want to benchmark
 # and the dirty categorical variable:
 
-encoding_methods = ['one-hot', 'target', 'similarity']
+encoding_methods = ['one-hot', 'target', 'similarity', 'minhash']
 dirty_column = 'employee_position_title'
 #########################################################################
 
@@ -67,12 +67,14 @@ dirty_column = 'employee_position_title'
 
 from sklearn.preprocessing import FunctionTransformer
 from sklearn.preprocessing import OneHotEncoder
-from dirty_cat import SimilarityEncoder, TargetEncoder
+from dirty_cat import SimilarityEncoder, TargetEncoder, MinHashEncoder
 
 encoders_dict = {
     'one-hot': OneHotEncoder(handle_unknown='ignore', sparse=False),
     'similarity': SimilarityEncoder(similarity='ngram'),
     'target': TargetEncoder(handle_unknown='ignore'),
+    'minhash': MinHashEncoder(n_components=10, ngram_range=(2, 4),
+                              hashing='fast', minmax_hash=False),
     'numerical': FunctionTransformer(None)}
 
 # We then create a function that takes one key of our ``encoders_dict``,
@@ -128,6 +130,12 @@ for method in encoding_methods:
 # Plotting the results
 # --------------------
 # Finally, we plot the scores on a boxplot:
+# We notice that the MinHashEncoder performs poorly compared to other encoding
+# methods. There are two reasons for that: the MinHashEncoder performs better
+# with tree-based models than linear models (see example 03), and the
+# low-dimensionality of encodings (increasing n_components improves
+# performances.
+
 import seaborn
 import matplotlib.pyplot as plt
 plt.figure(figsize=(4, 3))
diff --git a/examples/03_fit_predict_plot_midwest_survey.py b/examples/03_fit_predict_plot_midwest_survey.py
index c18ac2a..06e3c7a 100644
--- a/examples/03_fit_predict_plot_midwest_survey.py
+++ b/examples/03_fit_predict_plot_midwest_survey.py
@@ -64,11 +64,13 @@ y = df[target_column].values.ravel()
 # -------------------------------------------
 # We first import the right encoders to transform our clean/dirty data:
 from sklearn.preprocessing import FunctionTransformer, OneHotEncoder
-from dirty_cat import SimilarityEncoder
+from dirty_cat import SimilarityEncoder, MinHashEncoder
 
 encoder_dict = {
     'one-hot': OneHotEncoder(handle_unknown='ignore', sparse=False),
     'similarity': SimilarityEncoder(similarity='ngram'),
+    'minhash': MinHashEncoder(n_components=10, ngram_range=(2, 4),
+                              hashing='fast', minmax_hash=False),
     'num': FunctionTransformer(None)
 }
 ##############################################################################
@@ -110,7 +112,7 @@ from sklearn.model_selection import StratifiedKFold
 
 cv = StratifiedKFold(n_splits=3, random_state=12, shuffle=True)
 all_scores = {}
-for method in ['one-hot', 'similarity']:
+for method in ['one-hot', 'similarity', 'minhash']:
     pipeline = make_pipeline(method)
     # Now predict the census region of each participant
     scores = cross_val_score(pipeline, df, y, cv=cv)
diff --git a/examples/04_dimension_reduction_and_performance.py b/examples/04_dimension_reduction_and_performance.py
index 4abf142..2ce8898 100644
--- a/examples/04_dimension_reduction_and_performance.py
+++ b/examples/04_dimension_reduction_and_performance.py
@@ -62,14 +62,14 @@ df = df.dropna(axis=0)
 df = df.reset_index()
 ################################################################################
 # We will use SimilarityEncoder on the 'description' column. One
-# difficulty is that it many different entries
+# difficulty is that it has many different entries.
 print(df['Description'].nunique())
 
 ################################################################################
 print(df['Description'].value_counts()[:20])
 
 ################################################################################
-# As we will see,SimilarityEncoder takes a while on such data
+# As we will see, SimilarityEncoder takes a while on such data.
 
 
 ################################################################################


Test patch:
diff --git a/dirty_cat/test/test_fast_hash.py b/dirty_cat/test/test_fast_hash.py
new file mode 100644
index 0000000..01cf0a0
--- /dev/null
+++ b/dirty_cat/test/test_fast_hash.py
@@ -0,0 +1,22 @@
+from dirty_cat.fast_hash import ngram_min_hash
+
+
+def test_fast_hash():
+
+    from sklearn import datasets
+    data = datasets.fetch_20newsgroups()
+    a = data.data[0]
+
+    min_hash = ngram_min_hash(a, seed=0)
+    min_hash2 = ngram_min_hash(a, seed=0)
+    assert min_hash == min_hash2
+
+    list_min_hash = [ngram_min_hash(a, seed=seed) for seed in range(50)]
+    assert len(set(list_min_hash)) > 45, 'Too many hash collisions'
+
+    min_hash4 = ngram_min_hash(a, seed=0, return_minmax=True)
+    assert len(min_hash4) == 2
+
+
+if __name__ == '__main__':
+    test_fast_hash()
diff --git a/dirty_cat/test/test_minhash_encoder.py b/dirty_cat/test/test_minhash_encoder.py
new file mode 100644
index 0000000..4ae6f9a
--- /dev/null
+++ b/dirty_cat/test/test_minhash_encoder.py
@@ -0,0 +1,93 @@
+import numpy as np
+import time
+
+from sklearn.datasets import fetch_20newsgroups
+from dirty_cat import MinHashEncoder
+
+def test_MinHashEncoder(n_sample=70, minmax_hash=False):
+    X_txt = fetch_20newsgroups(subset='train')['data']
+    X = X_txt[:n_sample]
+
+    for minmax_hash in [True, False]:
+        for hashing in ['fast', 'murmur']:
+
+            if minmax_hash and hashing == 'murmur':
+                pass # not implemented
+
+            # Test output shape
+            encoder = MinHashEncoder(n_components=50, hashing=hashing)
+            encoder.fit(X)
+            y = encoder.transform(X)
+            assert y.shape == (n_sample, 50), str(y.shape)
+            assert len(set(y[0])) == 50
+
+            # Test same seed return the same output
+            encoder = MinHashEncoder(50, hashing=hashing)
+            encoder.fit(X)
+            y2 = encoder.transform(X)
+            np.testing.assert_array_equal(y, y2)
+
+            # Test min property
+            if not minmax_hash:
+                X_substring = [x[:x.find(' ')] for x in X]
+                encoder = MinHashEncoder(50, hashing=hashing)
+                encoder.fit(X_substring)
+                y_substring = encoder.transform(X_substring)
+                np.testing.assert_array_less(y - y_substring, 0.0001)
+
+def test_input_type():
+    # Numpy array
+    X = np.array(['alice', 'bob'])
+    enc = MinHashEncoder(n_components=2)
+    enc.fit_transform(X)
+    # List
+    X = ['alice', 'bob']
+    enc = MinHashEncoder(n_components=2)
+    enc.fit_transform(X)
+
+def test_get_unique_ngrams():
+    string = 'test'
+    true_ngrams = {
+        (' ','t'), ('t','e'), ('e','s'), ('s', 't'),
+        ('t',' '), (' ','t','e'), ('t','e','s'),
+        ('e','s','t'), ('s','t',' '), (' ','t','e','s'),
+        ('t','e','s','t'), ('e','s','t',' ')}
+    ngram_range = (2,4)
+    enc = MinHashEncoder(n_components=2)
+    ngrams = enc.get_unique_ngrams(string, ngram_range)
+    assert ngrams == true_ngrams
+        
+def profile_encoder(Encoder, hashing='fast', minmax_hash=False):
+    # not an unit test
+    
+    from dirty_cat import datasets
+    import pandas as pd
+    employee_salaries = datasets.fetch_employee_salaries()
+    data = pd.read_csv(employee_salaries['path'])
+    X = data['Employee Position Title'].tolist()
+    X = X * 10
+    t0 = time.time()
+    encoder = Encoder(n_components=50, hashing=hashing, minmax_hash=minmax_hash)
+    encoder.fit(X)
+    y = encoder.transform(X)
+    assert y.shape == (len(X), 50)
+    eta = time.time() - t0
+    return eta
+
+
+if __name__ == '__main__':
+    print('start test')
+    test_MinHashEncoder()
+    print('test passed')
+
+    for _ in range(3):
+        print('time profile_encoder(MinHashEncoder, hashing=fast)')
+        print("{:.4} seconds".format(profile_encoder(MinHashEncoder, hashing='fast')))
+    for _ in range(3):
+        print('time profile_encoder(MinHashEncoder, hashing=fast) with minmax')
+        print("{:.4} seconds".format(profile_encoder(MinHashEncoder,
+                         hashing='fast', minmax_hash=True)))
+    print('time profile_encoder(MinHashEncoder, hashing=murmur)')
+    print("{:.4} seconds".format(profile_encoder(MinHashEncoder, hashing='murmur')))
+
+    print('Done')
diff --git a/dirty_cat/test/test_utils.py b/dirty_cat/test/test_utils.py
new file mode 100644
index 0000000..70caf4a
--- /dev/null
+++ b/dirty_cat/test/test_utils.py
@@ -0,0 +1,15 @@
+from dirty_cat.utils import LRUDict
+
+
+def test_lrudict():
+    dict_ = LRUDict(10)
+
+    for x in range(15):
+        dict_[x] = 'filled'+str(x)
+
+    for x in range(5, 15):
+        assert x in dict_
+        assert dict_[x] == 'filled'+str(x)
+
+    for x in range(5):
+        assert (x not in dict_)