Repository: dirty-cat/dirty_cat
Pull request #339 (2022-09-11 12:19:38)

FEA Deduplication
This PR implements a basic `deduplicate` function (see discussion in #306 ).
It is based on computing n-gram tfidf distances between unique words in a column (same as for `fuzzy_join`), hierarchically clustering the distance matrix, then deduplicating by picking the most frequent exemplar in each cluster as the "correct" spelling.

Open design question: Should this be a function or a class? It clearly has a state (and could be useful when "trained" on a large set of dirty categories and then applied to new incoming data) - but saving a translation table in a class would be costly. An alternative would be to go from a clustered distance matrix to a K-means representation based on string distances (where each centroid is the most frequent cluster exemplar).

It's currently WIP because I still want to add an example/documentation.

FWIW this function was immediately useful in my work, but its usefulness depends on the structure of your data:
If there are few underlying categories, which might be corrupted by typos or alternative spellings, then it should work well out of the box.

jovan-stojanovic: Hi @mjboos, thanks for opening this PR, exciting work ahead.
Just so you know, on Wednesday during the day we plan to have a sprint during which we will take a closer look at the problem.
We may come up with some comments and answers to your questions.
mjboos: Thanks for the update @jovan-stojanovic !
I added a bare-bones example (examples/07_deduplication.py) to show a use case for this work, let me know if you have any questions/ideas for future directions.
mjboos: @jovan-stojanovic @GaelVaroquaux Initially I wanted to extend the example, but think it's better to only do that after you gave some feedback on the PR/design questions I raised above.

Seems like the test is failing due to some missing approval/workflow configuration - let me know if it's something on my end.
GaelVaroquaux: I approved running the tests.
GaelVaroquaux: Trivial comment: the file should be named "_deduplicate.py", to signal that it is private and that people should not be importing from it.
GaelVaroquaux: I had a quick look, and overall things look good. I made a bunch of minor comments, but nothing on the overall design. Let me try to think about it more. Yet, so far, so good!
mjboos: Thanks for the feedback @GaelVaroquaux I implemented the suggestions
mjboos: Thanks for the comments @jovan-stojanovic !
I implemented your suggestions, but had some additional questions (took some time to get back to it, life happens).

When I used the function in the past month, I stumbled across another use case:
Often I notice dirty categorical data in a database/data warehouse, this data is usually too large to download and put into the function itself. So I already create a table of unique values and their counts and then use this as input (instead of the raw data).
To fix typos, I create the translation table and use it to join in the database.
I'm not sure if this is a workflow you want to support in dirty cat, but I could adapt the function to accept already unique strings + their counts (instead of the raw data/list of strings).
Trade off is that we overload the parameter (can be either unique values + counts or just list of potentially duplicate strings) and I'm not sure whether dirty cat is often used with data too large to fit into memory.

jovan-stojanovic: Thanks! Interesting use case but there is something I don't understand:
> So I already create a table of unique values and their counts and then use this as input (instead of the raw data). To fix typos, I create the translation table and use it to join in the database. 

Isn't this exactly what the `deduplicate` function does? So the only difference would be that you would manually provide `unique words` and `counts` instead of doing what is in the first line `unique_words, counts = np.unique(data, return_counts=True)`
But then again, you would need to do this to get the counts and uniques, only outside of the function?
mjboos: > Thanks! Interesting use case but there is something I don't understand:
> 
> > So I already create a table of unique values and their counts and then use this as input (instead of the raw data). To fix typos, I create the translation table and use it to join in the database.
> 
> Isn't this exactly what the `deduplicate` function does? So the only difference would be that you would manually provide `unique words` and `counts` instead of doing what is in the first line `unique_words, counts = np.unique(data, return_counts=True)` But then again, you would need to do this to get the counts and uniques, only outside of the function?

Exactly, (locally) I allow `counts` as optional argument, if it is present I assume `data` already refers to unique strings.
I get the counts & uniques via a cloud database (e.g., google cloud) and download only these. For me, this is helpful because I have very large datasets in the cloud and don't want to get the full, raw data - the correction then happens in the cloud too, by uploading the `translation_table` as a literal table and joining on it.
It's quite useful for me, but I'm not sure how many `dirty_cat` users will use a similar workflow (hence trade-off of overloading the parameters vs. supporting this workflow).
jovan-stojanovic: I see, then best to do in my opinion is the following:
- finish this version of deduplication;
- add an issue mentioning this, to keep track of it and see if it affect others.
mjboos: > I see, then best to do in my opinion is the following:
> 
> * finish this version of deduplication;
> * add an issue mentioning this, to keep track of it and see if it affect others.

Sounds good @jovan-stojanovic .
I changed the function to always return the deduplicated data and adapted the example to show how to re-create the translation table - that should make it easier to use.
Lmk if that's enough.
mjboos: Thanks @jovan-stojanovic @LilianBoulard
I accepted all suggestions apart from the one where I had an additional question :)
GaelVaroquaux: > You need to make this function public (as it is used in the example).

It implies: changing the naming, importing it in the main namespace (init) of dirty_cat and documenting it.

> Best is to move this function into datasets._fetching and rename it to something like make_deduplication

I'd rather use as a name "make_deduplication_data"

LilianBoulard: Could you also add a changelog major change entry for version 0.4.0? Thanks!
LilianBoulard: Hey @mjboos
We are looking to release a new version of dirty_cat within the next two weeks, and we're excited to have the deduplication as part of 0.4! Thus we need to merge this PR :)
Do you need any help/guidance on how to operate the previously suggested changes?
Thanks!
mjboos: Sure, I can prioritize it and get it done in the next few days :)

Am Mo., 9. Jan. 2023 um 14:50 Uhr schrieb Lilian ***@***.***>:

> Hey @mjboos <https://github.com/mjboos>
> We are looking to release a new version of dirty_cat within the next two
> weeks, and we're excited to have the deduplication as part of 0.4! Thus we
> need to merge this PR :)
> Do you need any help/guidance on how to operate the previously suggested
> changes?
> Thanks!
>
> —
> Reply to this email directly, view it on GitHub
> <https://github.com/dirty-cat/dirty_cat/pull/339#issuecomment-1375736897>,
> or unsubscribe
> <https://github.com/notifications/unsubscribe-auth/ABWLQDW27KI25AINIQRPW5LWRQQSFANCNFSM6AAAAAAQJYF6E4>
> .
> You are receiving this because you were mentioned.Message ID:
> ***@***.***>
>

jovan-stojanovic: Hey @mjboos, we are ready for a beta release, would be good to have this as well. Do you need assistance with the few changes left?
mjboos: Sure, I accepted the suggestions and made the function public. I kept the different function for testing though @jovan-stojanovic and detailed why I did above (but can change it).
Also added a change log @LilianBoulard lmk if you want to have it another way or want to add attribution to suggesters of changes as well.
mjboos: > The test_docstrings.py are failing (you should update the docstrings to meet the numpydoc standards).

Oops, fixed it.
jovan-stojanovic: It's green, merging. Thanks!

Patch:
diff --git a/CHANGES.rst b/CHANGES.rst
index 8300c48..ab91735 100644
--- a/CHANGES.rst
+++ b/CHANGES.rst
@@ -18,6 +18,9 @@ Major changes
   starting with an underscore shouldn't be imported in your code. :pr:`331` by :user:`Lilian Boulard <LilianBoulard>`
 * The :class:`MinHashEncoder` now supports a `n_jobs` parameter to parallelize
   the hashes computation. :pr:`267` by :user:`Leo Grinsztajn <LeoGrin>` and :user:`Lilian Boulard <LilianBoulard>`.
+* New experimental feature: deduplicating misspelled categories using :func:`deduplicate` by clustering string distances.
+  This function works best when there are significantly more duplicates than underlying categories.
+  :pr:`339` by :user:`Moritz Boos <mjboos>`.
 
 Minor changes
 -------------
diff --git a/dirty_cat/__init__.py b/dirty_cat/__init__.py
index dc13251..b6bf6d3 100644
--- a/dirty_cat/__init__.py
+++ b/dirty_cat/__init__.py
@@ -15,6 +15,7 @@ except ModuleNotFoundError:
     )
 
 from ._datetime_encoder import DatetimeEncoder
+from ._deduplicate import compute_ngram_distance, deduplicate
 from ._fuzzy_join import fuzzy_join
 from ._gap_encoder import GapEncoder
 from ._minhash_encoder import MinHashEncoder
@@ -34,4 +35,6 @@ __all__ = [
     "DatetimeEncoder",
     "SuperVectorizer",
     "fuzzy_join",
+    "deduplicate",
+    "compute_ngram_distance",
 ]
diff --git a/dirty_cat/_deduplicate.py b/dirty_cat/_deduplicate.py
new file mode 100644
index 0000000..fda228f
--- /dev/null
+++ b/dirty_cat/_deduplicate.py
@@ -0,0 +1,182 @@
+"""
+Implements deduplication based on clustering string distance matrices.
+This works best if there is a number of underlying categories that
+sometimes appear in the data with small variations and/or misspellings.
+"""
+from typing import List, Literal, Optional, Sequence, Tuple, Union
+
+import numpy as np
+import pandas as pd
+from scipy.cluster.hierarchy import fcluster, linkage
+from scipy.spatial.distance import pdist, squareform
+from sklearn.feature_extraction.text import TfidfVectorizer
+from sklearn.metrics import silhouette_score
+
+
+def compute_ngram_distance(
+    unique_words: Union[Sequence[str], np.ndarray],
+    ngram_range: Tuple[int, int] = (2, 4),
+    analyzer: str = "char_wb",
+) -> np.ndarray:
+    """Compute the condensed pair-wise n-gram distance between `unique_words`.
+
+    Parameters
+    ----------
+    unique_words : Union[Sequence[str], np.ndarray]
+        Sequence or array of unique words from the original data.
+    ngram_range : Tuple[int, int], optional, default=(2,4)
+        The n-gram range to compute the distance in.
+    analyzer : str, optional, default=`char_wb`
+        Analyzer to extract n-grams.
+
+    Returns
+    -------
+    np.ndarray
+        An n-times-(n-1)/2 array of n-gram tf-idf distances between `unique_words`.
+
+    Notes
+    -----
+    Extracts n-grams of all elements in `unique_words`, calculates the
+    term frequency-inverse document frequency (tf-idf) for each n-gram, then
+    computes the pair-wise euclidean distance between elements based on their n-gram
+    tf-idf representation.
+    """
+    encoded = TfidfVectorizer(ngram_range=ngram_range, analyzer=analyzer).fit_transform(
+        unique_words
+    )
+
+    distance_mat = pdist(encoded.todense(), metric="euclidean")
+    return distance_mat
+
+
+def _guess_clusters(Z: np.ndarray, distance_mat: np.ndarray) -> int:
+    """Finds the number of clusters that maximize the silhouette score
+    when clustering `distance_mat`.
+
+    Parameters
+    ----------
+    Z : np.ndarray
+        hierarchical linkage matrix, specifies which clusters to merge.
+    distance_mat : np.ndarray
+        distance matrix either in square or condensed form.
+
+    Returns
+    -------
+    int
+        number of clusters that maximize the silhouette score.
+    """
+    max_clusters = distance_mat.shape[0]
+    n_clusters = np.arange(2, max_clusters)
+    # silhouette score needs a redundant distance matrix
+    redundant_dist = squareform(distance_mat)
+    silhouette_scores = []
+    for n_clust in n_clusters:
+        labels = fcluster(Z, n_clust, criterion="maxclust")
+        silhouette_avg = silhouette_score(redundant_dist, labels, metric="precomputed")
+        silhouette_scores.append(silhouette_avg)
+    return n_clusters[np.argmax(silhouette_scores)]
+
+
+def _create_spelling_correction(
+    unique_words: Union[Sequence[str], np.ndarray],
+    counts: Union[Sequence[int], np.ndarray],
+    clusters: Sequence[int],
+) -> pd.Series:
+    """Creates a pandas Series that map each cluster member to the most
+    frequent cluster member. The assumption is that the most common spelling
+    is the correct one.
+
+    Parameters
+    ----------
+    unique_words : Union[Sequence[str], np.ndarray]
+        A sequence or array of unique words in the original data.
+    counts : Union[Sequence[int], np.ndarray]
+        A sequence or array of counts of how often each unique word appears in
+        the original data.
+    clusters : Sequence[int]
+        A sequence of ints, indicating cluster membership of each unique word
+        in `count_series`.
+
+    Returns
+    -------
+    pd.Series
+        Series with unique (original) words as indices and (estimated)
+        corrected spelling of each word as values.
+    """
+    count_series = pd.Series(counts, index=unique_words)
+    original_spelling: List[str] = []
+    corrected_spelling: List[str] = []
+    for cluster in np.unique(clusters):
+        sorted_spellings = (
+            count_series.loc[clusters == cluster]
+            .sort_values(ascending=False)
+            .index.tolist()
+        )
+        original_spelling.extend(sorted_spellings)
+        # assumes spelling that occurs most frequently in cluster is correct
+        corrected_spelling.extend(sorted_spellings[:1] * len(sorted_spellings))
+    pd_spell_correct = pd.Series(corrected_spelling, index=original_spelling)
+    return pd_spell_correct
+
+
+def deduplicate(
+    data: Sequence[str],
+    n_clusters: Optional[int] = None,
+    ngram_range: Tuple[int, int] = (2, 4),
+    analyzer: Literal["word", "char", "char_wb"] = "char_wb",
+    method: Literal[
+        "single", "complete", "average", "centroid", "median", "ward"
+    ] = "average",
+) -> List[str]:
+    """Deduplicate data by hierarchically clustering similar strings.
+
+    Parameters
+    ----------
+    data : Sequence[str]
+        The data to be deduplicated.
+    n_clusters : Optional[int], optional, default=None
+        Number of clusters to use for hierarchical clustering, if None use the
+        number of clusters that lead to the lowest silhouette score.
+    ngram_range : Tuple[int, int], optional, default=(2, 4)
+        Range to use for computing n-gram distance.
+    analyzer : typing.Literal["word", "char", "char_wb"], optional, default=`char_wb`
+        Analyzer parameter for the CountVectorizer 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
+        boundaries; n-grams at the edges of words are padded with space.
+    method : str, optional, default=`average`
+        Linkage method parameter to use for merging clusters via scipy's
+        `linkage` method.
+        Options: {`single`, `complete`, `average`, `centroid`, `median`, `ward`},
+        describing different methods to calculate the distance between two clusters.
+        Option `average` calculates the distance between two clusters as the average
+        distance between data points in the first and second cluster.
+
+    Returns
+    -------
+    List[str]
+       The deduplicated data.
+
+    Notes
+    -----
+    Deduplication is done by first computing the n-gram distance between unique
+    categories in data, then performing hierarchical clustering on this distance
+    matrix, and choosing the most frequent element in each cluster as the
+    'correct' spelling. This method works best if the true number of
+    categories is significantly smaller than the number of observed spellings.
+    """
+    unique_words, counts = np.unique(data, return_counts=True)
+    distance_mat = compute_ngram_distance(
+        unique_words, ngram_range=ngram_range, analyzer=analyzer
+    )
+
+    Z = linkage(distance_mat, method=method, optimal_ordering=True)
+    if n_clusters is None:
+        n_clusters = _guess_clusters(Z, distance_mat)
+    clusters = fcluster(Z, n_clusters, criterion="maxclust")
+
+    translation_table = _create_spelling_correction(unique_words, counts, clusters)
+    unrolled_corrections = translation_table[data]
+    return unrolled_corrections
diff --git a/dirty_cat/datasets/__init__.py b/dirty_cat/datasets/__init__.py
index ff8ccc4..92f3ace 100644
--- a/dirty_cat/datasets/__init__.py
+++ b/dirty_cat/datasets/__init__.py
@@ -10,6 +10,7 @@ from ._fetching import (
     fetch_traffic_violations,
     fetch_world_bank_indicator,
     get_data_dir,
+    make_deduplication_data,
 )
 
 __all__ = [
@@ -24,4 +25,5 @@ __all__ = [
     "fetch_traffic_violations",
     "fetch_world_bank_indicator",
     "get_data_dir",
+    "make_deduplication_data",
 ]
diff --git a/dirty_cat/datasets/_fetching.py b/dirty_cat/datasets/_fetching.py
index eeba1a8..41c61ca 100644
--- a/dirty_cat/datasets/_fetching.py
+++ b/dirty_cat/datasets/_fetching.py
@@ -818,3 +818,49 @@ def fetch_world_bank_indicator(
         load_dataframe=load_dataframe,
         data_directory=directory,
     )
+
+
+def make_deduplication_data(
+    examples: List[str], entries_per_example: List[int], prob_mistake_per_letter: float
+) -> List[str]:
+    """Duplicates examples with spelling mistakes.
+    Characters are misspelled with probability `prob_mistake_per_letter`.
+
+    Parameters
+    ----------
+    examples : List[str]
+        examples to duplicate
+    entries_per_example : List[int]
+        number of duplications per example
+    prob_mistake_per_letter : float in [0, 1]
+        probability of misspelling a character in duplications
+
+    Returns
+    -------
+    List[str]
+        list of duplicated examples with spelling mistakes
+    """
+
+    import string
+
+    import numpy as np
+
+    data = []
+    for example, n_ex in zip(examples, entries_per_example):
+        len_ex = len(example)
+        # generate a 2D array of chars of size (n_ex, len_ex)
+        str_as_list = np.array([list(example)] * n_ex)
+        # randomly choose which characters are misspelled
+        idxes = np.where(
+            np.random.random(len(example[0]) * n_ex) < prob_mistake_per_letter
+        )[0]
+        # and randomly pick with which character to replace
+        replacements = [
+            string.ascii_lowercase[i]
+            for i in np.random.choice(np.arange(26), len(idxes)).astype(int)
+        ]
+        # introduce spelling mistakes at right examples and char locations per example
+        str_as_list[idxes // len_ex, idxes % len_ex] = replacements
+        # go back to 1d array of strings
+        data.append(np.ascontiguousarray(str_as_list).view(f"U{len_ex}").ravel())
+    return np.concatenate(data).tolist()
diff --git a/examples/06_deduplication.py b/examples/06_deduplication.py
new file mode 100644
index 0000000..95b8677
--- /dev/null
+++ b/examples/06_deduplication.py
@@ -0,0 +1,161 @@
+"""
+Deduplicating misspelled categories with deduplicate
+====================================================
+
+A common step in data analyses is grouping or analyzing data conditional on a
+categorical variable. In real world datasets, there often will be slight
+misspellings in the category names: This happens when, for example, data input
+*should* use a drop down menu, but users are forced to input the category name
+by hand. Misspellings happen and analyzing the resulting data using a simple
+`GROUP BY` is not possible anymore.
+
+This problem is however the perfect use case of *unsupervised learning*, a
+category of various statical methods that find structure in data without
+providing explicit labels/categories of the data a-priori. Specifically
+clustering of the distance between strings can be used to find clusters
+of strings that are similar to each other (e.g. differ only by a misspelling)
+and hence gives us an easy tool to flag potentially misspelled category names
+in an unsupervised manner.
+"""
+
+###############################################################################
+# An example
+# ----------
+#
+# Imagine the following example:
+# As a data scientist, our job is to analyze the data from a hospital ward.
+# We notice that most of the cases involve the prescription of one of three different medications:
+#  "Contrivan", "Genericon", or "Zipholan".
+# However, data entry is manual and - either because the prescribing doctor's handwriting
+# was hard to decipher, or due to mistakes during data input - there are multiple
+# spelling mistakes for these three medications.
+#
+# Let's generate some example data that demonstrate this.
+
+
+import numpy as np
+import pandas as pd
+import matplotlib.pyplot as plt
+from dirty_cat.datasets import make_deduplication_data
+
+# set seed for reproducibility
+np.random.seed(123)
+
+# our three medication names
+medications = ["Contrivan", "Genericon", "Zipholan"]
+entries_per_medications = [500, 100, 1500]
+
+# 5% probability of a typo per letter
+prob_mistake_per_letter = 0.05
+
+data = make_deduplication_data(
+    medications, entries_per_medications, prob_mistake_per_letter
+)
+# we extract the unique medication names in the data & how often they appear
+unique_examples, counts = np.unique(data, return_counts=True)
+# and build a series out of them
+ex_series = pd.Series(counts, index=unique_examples)
+
+###############################################################################
+# Visualize the data
+# ------------------
+
+ex_series.plot.barh(figsize=(10, 15))
+plt.xlabel("Medication name")
+plt.ylabel("Counts")
+
+###############################################################################
+# We can now see clearly the structure of the data: The three original medications
+# are the most common ones, however there are many spelling mistakes and hence
+# many slight variations of the names of the original medications.
+#
+# The idea is to use the fact that the string-distance of each misspelled medication
+# name will be closest to either the correctly or incorrectly spelled orginal
+# medication name - and therefore form clusters.
+
+
+from dirty_cat import deduplicate
+from dirty_cat._deduplicate import compute_ngram_distance
+from scipy.spatial.distance import squareform
+
+ngram_distances = compute_ngram_distance(unique_examples)
+square_distances = squareform(ngram_distances)
+
+###############################################################################
+# We can visualize the pair-wise distance between all medication names
+# --------------------------------------------------------------------
+#
+# Below we use a heatmap to visualize the pairwise-distance between medication names.
+# A darker color means that two medication names are closer together (i.e. more similar),
+# a lighter color means a larger distance. We can see that we are dealing with three
+# clusters - the original medication names and their misspellings that cluster around them.
+
+import seaborn as sns
+
+fig, axes = plt.subplots(1, 1, figsize=(12, 12))
+sns.heatmap(
+    square_distances, yticklabels=ex_series.index, xticklabels=ex_series.index, ax=axes
+)
+
+###############################################################################
+# Clustering to suggest corrections of misspelled names
+# -----------------------------------------------------
+#
+# The number of clusters will need some adjustment depending on the data you have.
+# If no fixed number of clusters is given, `deduplicate` tries to set it automatically
+# via the `silhouette score <https://scikit-learn.org/stable/modules/clustering.html#silhouette-coefficient>`_.
+
+
+deduplicated_data = deduplicate(data)
+
+###############################################################################
+# We can visualize the distribution of categories in the deduplicated data:
+
+deduplicated_unique_examples, deduplicated_counts = np.unique(
+    deduplicated_data, return_counts=True
+)
+deduplicated_series = pd.Series(deduplicated_counts, index=deduplicated_unique_examples)
+
+deduplicated_series.plot.barh(figsize=(10, 15))
+plt.xlabel("Medication name")
+plt.ylabel("Counts")
+
+###############################################################################
+# In this example we can correct all spelling mistakes by using the ideal number
+# of clusters as determined by the silhouette score.
+#
+# However, often the translation/deduplication won't be perfect and will require some tweaks.
+# In this case, we can construct and update a translation table based on the data
+# returned by `deduplicate`.
+# It consists of the (potentially) misspelled category names as indices and the
+# (potentially) correct categories as values.
+
+# create a table that maps original -> corrected categories
+translation_table = pd.Series(deduplicated_data, index=data)
+
+# remove duplicates in the original data
+translation_table = translation_table[~translation_table.index.duplicated(keep="first")]
+
+###############################################################################
+# Since the number of correct spellings will likely be much smaller than the
+# number of original categories, we can print the estimated cluster and their
+# most common exemplars (the guessed correct spelling):
+
+
+def print_corrections(spell_correct):
+    correct = np.unique(spell_correct.values)
+    for c in correct:
+        print(
+            f"Guessed correct spelling: {c!r} for "
+            f"{spell_correct[spell_correct==c].index.values}"
+        )
+
+
+print_corrections(translation_table)
+
+###############################################################################
+# In case we want to adapt the translation table post-hoc we can easily do so:
+
+translation_table["Gszericon"] = "Completely new category"
+new_deduplicated_data = translation_table[data]
+assert (new_deduplicated_data == "Completely new category").sum() > 0


Test patch:
diff --git a/dirty_cat/datasets/tests/test_fetching.py b/dirty_cat/datasets/tests/test_fetching.py
index 2c8605d..721c29c 100644
--- a/dirty_cat/datasets/tests/test_fetching.py
+++ b/dirty_cat/datasets/tests/test_fetching.py
@@ -29,6 +29,7 @@ from dirty_cat.datasets._fetching import (
 from dirty_cat.datasets._fetching import (
     fetch_world_bank_indicator as fetch_world_bank_indicator,
 )
+from dirty_cat.datasets._fetching import make_deduplication_data
 from dirty_cat.datasets._utils import get_data_dir as _get_data_dir
 
 
@@ -453,3 +454,25 @@ def test_fetch_world_bank_indicator():
 
     finally:
         shutil.rmtree(path=str(test_data_dir), ignore_errors=True)
+
+
+def test_make_deduplication_data():
+    import numpy as np
+
+    np.random.seed(123)
+    assert make_deduplication_data(["abc", "cba", "test1"], [3, 2, 1], 0.3) == [
+        "agr",
+        "abc",
+        "abc",
+        "cba",
+        "cba",
+        "test1",
+    ]
+    assert make_deduplication_data(["abc", "cba", "test1"], [1, 2, 3], 0.8) == [
+        "pbc",
+        "pza",
+        "cba",
+        "erxt1",
+        "test1",
+        "test1",
+    ]
diff --git a/dirty_cat/tests/test_deduplicate.py b/dirty_cat/tests/test_deduplicate.py
new file mode 100644
index 0000000..572996a
--- /dev/null
+++ b/dirty_cat/tests/test_deduplicate.py
@@ -0,0 +1,124 @@
+import string
+from typing import List
+
+import numpy as np
+import pandas as pd
+import pytest
+from scipy.cluster.hierarchy import linkage
+from scipy.spatial.distance import squareform
+
+from dirty_cat._deduplicate import (
+    _create_spelling_correction,
+    _guess_clusters,
+    compute_ngram_distance,
+    deduplicate,
+)
+
+
+def generate_example_data(examples, entries_per_example, prob_mistake_per_letter, rng):
+    """Helper function to generate data consisting of multiple entries per example.
+    Characters are misspelled with probability `prob_mistake_per_letter`"""
+
+    data = []
+    for example, n_ex in zip(examples, entries_per_example):
+        len_ex = len(example)
+        # generate a 2D array of chars of size (n_ex, len_ex)
+        str_as_list = np.array([list(example)] * n_ex)
+        # randomly choose which characters are misspelled
+        idxes = np.where(
+            rng.random_sample(len(example[0]) * n_ex) < prob_mistake_per_letter
+        )[0]
+        # and randomly pick with which character to replace
+        replacements = [
+            string.ascii_lowercase[i]
+            for i in rng.choice(np.arange(26), len(idxes)).astype(int)
+        ]
+        # introduce spelling mistakes at right examples and char locations per example
+        str_as_list[idxes // len_ex, idxes % len_ex] = replacements
+        # go back to 1d array of strings
+        data.append(np.ascontiguousarray(str_as_list).view(f"U{len_ex}").ravel())
+    return np.concatenate(data)
+
+
+@pytest.mark.parametrize(
+    "entries_per_category, prob_mistake_per_letter",
+    [[[500, 100, 1500], 0.05], [[100, 100], 0.02], [[200, 50, 30, 200, 800], 0.01]],
+)
+def test_deduplicate(
+    entries_per_category: List[int],
+    prob_mistake_per_letter: float,
+    seed: int = 123,
+) -> None:
+    rng = np.random.RandomState(seed)
+
+    # hard coded to fix ground truth string similarities
+    clean_categories = [
+        "Example Category",
+        "Generic",
+        "Random Word",
+        "Pretty similar category",
+        "Final cluster",
+    ]
+    n_clusters = len(entries_per_category)
+    clean_categories = clean_categories[:n_clusters]
+    data = generate_example_data(
+        clean_categories, entries_per_category, prob_mistake_per_letter, rng
+    )
+    deduplicated_data = np.array(deduplicate(data, n_clusters=None))
+    assert deduplicated_data.shape[0] == data.shape[0]
+    recovered_categories = np.unique(deduplicated_data)
+    assert recovered_categories.shape[0] == n_clusters
+    assert np.isin(clean_categories, recovered_categories).all()
+    deduplicated_data = deduplicate(data, n_clusters=n_clusters)
+    translation_table = pd.Series(deduplicated_data, index=data)
+    translation_table = translation_table[
+        ~translation_table.index.duplicated(keep="first")
+    ]
+    assert np.isin(np.unique(deduplicated_data), recovered_categories).all()
+    assert np.alltrue(translation_table[data] == np.array(deduplicated_data))
+    deduplicated_other_analyzer = np.array(
+        deduplicate(data, n_clusters=n_clusters, analyzer="char")
+    )
+    unique_other_analyzer = np.unique(deduplicated_other_analyzer)
+    assert np.isin(unique_other_analyzer, recovered_categories).all()
+
+
+def test_compute_ngram_distance() -> None:
+    words = np.array(["aac", "aaa", "aaab", "aaa", "aaab", "aaa", "aaab", "aaa"])
+    distance = compute_ngram_distance(words)
+    distance = squareform(distance)
+    assert distance.shape[0] == words.shape[0]
+    assert np.allclose(np.diag(distance), 0)
+    for un_word in np.unique(words):
+        assert np.allclose(distance[words == un_word][:, words == un_word], 0)
+
+
+def test__guess_clusters() -> None:
+    words = np.array(["aac", "aaa", "aaab", "aaa", "aaab", "aaa", "aaab", "aaa"])
+    distance = compute_ngram_distance(words)
+    Z = linkage(distance, method="average")
+    n_clusters = _guess_clusters(Z, distance)
+    assert n_clusters == len(np.unique(words))
+
+
+def test__create_spelling_correction(seed: int = 123) -> None:
+    rng = np.random.RandomState(seed)
+    n_clusters = 3
+    samples_per_cluster = 10
+    counts = np.concatenate(
+        [rng.randint(0, 100, samples_per_cluster) for _ in range(n_clusters)]
+    )
+    clusters = (
+        np.repeat(np.arange(n_clusters), samples_per_cluster).astype("int").tolist()
+    )
+    spelling_correction = _create_spelling_correction(
+        counts.astype("str"),
+        counts,
+        clusters,
+    )
+    # check that the most common sample per cluster is chosen as the 'correct' spelling
+    for n in np.arange(n_clusters):
+        assert (
+            spelling_correction.values[clusters == n].astype("int")
+            == counts[clusters == n].max()
+        ).all()