Introduction

DBSCAN can work well for string deduplication or fuzzy grouping when you already have a distance measure such as Levenshtein edit distance. The main trick is that DBSCAN does not compute Levenshtein for you, so you usually build a pairwise distance matrix first and then run DBSCAN with metric="precomputed".

Why DBSCAN Fits String Clustering

DBSCAN is useful when you do not know the number of clusters in advance and when some strings should remain unclustered as noise. That matches many real tasks such as grouping misspelled company names, product labels, or user-entered city names.

Levenshtein distance is a good metric when similarity is defined by insertions, deletions, and substitutions. Small edit distance means the strings are close.

Build A Distance Matrix

Scikit-learn cannot feed raw strings directly into DBSCAN with Levenshtein distance unless the metric function handles pairwise calls exactly as expected. In practice, a precomputed matrix is simpler and more explicit.

1import numpy as np
2from rapidfuzz.distance import Levenshtein
3from sklearn.cluster import DBSCAN
4
5strings = [
6    "apple",
7    "appl",
8    "appel",
9    "banana",
10    "bananna",
11    "orange",
12]
13
14n = len(strings)
15dist = np.zeros((n, n), dtype=float)
16
17for i in range(n):
18    for j in range(i + 1, n):
19        d = Levenshtein.distance(strings[i], strings[j])
20        dist[i, j] = d
21        dist[j, i] = d
22
23model = DBSCAN(eps=2, min_samples=2, metric="precomputed")
24labels = model.fit_predict(dist)
25
26for s, label in zip(strings, labels):
27    print(label, s)

Here, strings within edit distance 2 can become neighbors. Strings that do not have enough nearby examples receive label -1, meaning noise.

Interpret eps Carefully

The eps parameter is the maximum allowed distance between neighboring points. With edit distance, the right value depends on string length and data quality.

A fixed eps=2 might work for short names, but it can be too strict for longer strings. For example, a difference of two characters in a five-letter word is much larger proportionally than two characters in a twenty-letter identifier.

That is why some workflows normalize distance by string length instead of using raw edit distance.

Example With Normalized Distance

1import numpy as np
2from rapidfuzz.distance import Levenshtein
3
4
5def normalized_distance(a, b):
6    if not a and not b:
7        return 0.0
8    return Levenshtein.distance(a, b) / max(len(a), len(b))
9
10strings = ["cat", "cats", "cut", "dog", "dogs"]
11n = len(strings)
12dist = np.zeros((n, n), dtype=float)
13
14for i in range(n):
15    for j in range(i + 1, n):
16        d = normalized_distance(strings[i], strings[j])
17        dist[i, j] = d
18        dist[j, i] = d
19
20labels = DBSCAN(eps=0.34, min_samples=2, metric="precomputed").fit_predict(dist)
21print(labels)

Normalized distance makes the eps value more comparable across mixed string lengths.

Performance Limits

The expensive part is not DBSCAN itself but computing the full pairwise distance matrix. For n strings, that matrix has n * n entries, so memory and runtime can become expensive quickly.

For larger datasets, common strategies include:

• pre-grouping by prefix, length, or token signature
• using approximate nearest-neighbor candidates before exact edit distance
• switching to vector embeddings if semantic similarity matters more than typo similarity

DBSCAN with full Levenshtein distance is best for moderate dataset sizes where edit-based similarity is genuinely the right definition.

Common Pitfalls

The most common mistake is trying to pass raw strings directly into DBSCAN without precomputing distances or without a compatible custom metric. That usually leads to shape or metric issues.

Another mistake is choosing eps by guesswork and never inspecting the clusters. String clustering is sensitive to threshold choice, especially when data mixes short and long strings.

A third issue is ignoring the quadratic cost of pairwise edit distance. The approach is clean, but it does not scale indefinitely.

Summary

• Use DBSCAN with a precomputed Levenshtein distance matrix for fuzzy string clustering.
• 'metric="precomputed" is the practical scikit-learn setup.'
• Tune eps based on actual edit distances in your dataset, not by intuition alone.
• Normalize distance when string lengths vary widely.
• Expect O(n^2) cost for the distance matrix and plan accordingly.