Finding duplicate places in your data

Dealing with duplicate places is a challenging task. If you look at standard ways of dealing with duplicates, they revolve around string similairty algorithms, like Levenshtein, Jaccard, Jaro-Winkler and so-on.

There’s a general task of finding duplicate records in databases. That involves dealing with things at a different scale than traditional string comparision algorithms handle. Dealing with all potential matches pair-wise is going to be extremely slow. There is a class of hashing algorithms that are good at dealing with such tasks. They are known as LSH or Locality-sensitive hashing. LSH is a powerful technique with many cool applications - this article by Uber engineering is one such.

What all these methods have in common is that they are relatively stateless. This is not needed for string comparision or data duplication detection. They do not have any idea what part of a word provides more context, and what is not really useful. This causes some issues when we are dealing with duplicate places as you shall see.

Let’s look at a few examples of why this task is challenging:

To solve this problem, the engineers at Facebook wrote an excellent paper - Deduplicating a Places Database. I’ve prototyped the algorithm outlined in a section in the paper and will walk you through some of the results I’ve seen.

To be more precise, this is the problem we are trying to solve:

Given two place names $n1$ and $n2$, and an approximate geographical location containing both of them, determine if the two names can refer to the same entity.

The solution sketch to this problem has three main components.

The first is a novel generative language model for places that identifies the core of a place name.

For example in “Emelina’s” vs “Emelina’s Peruvian Restaurant”, it identifies “Emelina’s” as the core and “Peruvian”, “Restaurant” as the background words. More on this later.

The second component is a language model that incorporates the spatial context, e.g., the presence of nearby land- marks, parks, malls, airports, major streets and the current city.

The spatial model helps us with distinguishing “Hillsdale Mall Levi’s Outlet” from “Hillsdale Mall Gap Outlet” and matching/non-matching Central Park and Central Park Cafe.

The third component of our solution is a place name similarity measure based on our language models.

I’m only going to talk about the first part. I’ll try and write follow up posts for the others.

Approach for the Simple Name Model

Let’s build some intuition by starting with an example. Consider the set of $names$ to be:

1. Philz Coffee
2. Starbucks Coffee
3. Philz

Our goal is to come up with core words for each of these words. The result should be:

1. Philz
2. Starbucks
3. Philz

This is because Coffee is a “Background” word.

Let’s define:

• $vocabulary$ - set of all tokens/words in our $names$.
• $C(w)$ - Probability that token $w \in vocabulary$ is a core word.
• $B(w)$ - Probability that token $w \in vocabulary$ is a background word.
• $z(w, n)$ - Probability that token $w \in n$ | $n \in names$, is a core word.

Algorithm

We start with $vocabulary = \{Philz, Coffee, Starbucks\}$. $C, B$ are uniform distributions. This looks like:

C[Philz] = C[Coffee] = C[Starbucks] = 1/3
B[Philz] = B[Coffee] = B[Starbucks] = 1/3

Thus, we have

• $z(Philz, n1) = z(Coffee, n1) = 0.5$
• $z(Starbucks, n2) = z(Coffee, n2) = 0.5$, and
• $z(Philz, n3) = 1$

Based on this, we will update our $C$ and $B$ values.

• $C = \{Philz ← 1/2,Starbucks ← 1/6,Coffee ← 1/3\}$ and
• $B = \{Philz ← 1/4,Starbucks ← 1/4,Coffee ← 1/4\}$

If you notice, the core probability of Philz and the background probability of Coffee increases. The algorithm converges to the following solution:

• $C = \{Philz ← 2/3, Starbucks ← 1/3,Coffee ← 0\}$
• $B = \{Philz ← 0, Starbucks ← 0, Coffee ← 1\}$

The algorithm drives down the core probability of Coffee to 0 and background probabilities of Starbucks and Philz to 0.

eps = 1e-16

# this is to get map from token_number to word
def get_inverse_vocab_map(count_vect):
    invert = dict((v, k) for k, v in count_vect.vocabulary_.items())
    return collections.OrderedDict(sorted(invert.items()))


def compute_core_and_background(names, verbose=False):
    count_vect = CountVectorizer(stop_words='english', analyzer='word')
    word_vec = count_vect.fit_transform(names).toarray()

    invert = get_inverse_vocab_map(count_vect)
    w_T = word_vec.T

    n_words = len(count_vect.vocabulary_)
    n_names = len(names)

    C = np.full(n_words, 1.0 / n_words)
    B = np.full(n_words, 1.0 / n_words)

    Z = np.zeros((n_words, n_names))
    _round = 1

    while _round <= max(n_names, 100):
        _round += 1

        min_bg = np.min(B)
        # until convergence do us part
        if min_bg < eps:
            break

        amplified_coreness = C / B
        K = (w_T.T * amplified_coreness).T
        Z = K / np.sum(K, axis=0)
        C = np.sum(Z, axis=1) / np.sum(Z)
        Z_prime = w_T - Z
        B = np.sum(Z_prime, axis=1) / np.sum(Z_prime)

    # avoid division by zero
    B += eps

    if verbose:
        res = []
        for k, v in invert.items():
            k = (v, "core:", C[k], ", bg:", B[k])
            res.append(k)
        res.sort(key=lambda x: -(x[2] / x[-1]))
        for i in res:
            print(i)
    return count_vect, C, B

Let’s run this on our example:

_ = compute_core_and_background(
    ['Philz', 'Starbucks Coffee', 'Philz Coffee'], True)

('philz', 'core:', 0.6666666666666666, ', bg:', 1e-16)
('starbucks', 'core:', 0.3333333333333333, ', bg:', 1e-16)
('coffee', 'core:', 1.0087745832662039e-17, ', bg:', 1.0)

Analyzing the points of interest in Palo Alto

For this exploration. I’m using the sample dataset of places in Palo Alto, filtered to Zip Code: 94301.

Note: I’ve added some noise and duplicates to this dataset to make this effort more interesting.

palo_alto = pd.read_csv('https://gist.githubusercontent.com/iskakaushik/8a1c7580dd8f5ba2841bb009c28dbe76/raw/7d8aab8731e717bdbc388b1faa04af072ecb9798/palo-alto-places.csv')
names = palo_alto.name.tolist()

count_vect, C, B = compute_core_and_background(palo_alto.name.tolist())
palo_alto.head(3)

invert = get_inverse_vocab_map(count_vect)
core_word_identified = []

for name in names:
    one_hot_name = count_vect.transform([name]).toarray()[0]
    coreness_vector = one_hot_name * (C / B)
    hottest_i = np.argmax(coreness_vector)
    hotness_score = np.max(coreness_vector)
    core = invert[hottest_i]
    core_word_identified.append((core, name, hotness_score))

core_words_df = pd.DataFrame(core_word_identified, columns = ['core_word', 'name', 'score'])
core_words_df.head(3)

Score Distributions

Left is unscaled scores. Right ranks scores, to make the plot tighter.

Finding duplicates:

We identify the words that share the same core_word. We can tune the $score$ threshold to pick one that we are confident will result in strong matches. We can then deal with the duplicates by picking one or merging. We can use the score distribution to arrive at reasonable thresholds.

As you can see, we’ve identificed $22$ high condent matches.

THRESHOLD = 5.0

duplicates = core_words_df.groupby('core_word').filter(lambda x: len(x) >= 2).copy()
duplicates['rank'] = duplicates['score'].rank(method='min')
ranked_duplicates = duplicates.sort_values(by=['rank', 'core_word'], ascending=False)

high_score_ranked_dups = ranked_duplicates[ranked_duplicates.score > THRESHOLD]

print("%s high confident matches." % len(high_score_ranked_dups))

high_score_ranked_dups

22 high confident matches.

Let’s take a look at some of the duplicates we have identified.

Not all duplicates are good

Here are some examples of matches on core words that had a low confidence score. Compare $0.6$ to $5$. Art also lies in data exploration and picking the right thresholds.

Hope you had fun reading the post.

Thanks,

Kaushik Iska