Probabilistic Record Matching for Linking User Devices

Our customers access our site using multiple devices and even multiple browsers on the same device. They don’t need to login to use our site so linking user sessions together is challenging. We analysed patterns of user behaviour to see if we could use this to link sessions together.

Example

Imagine a customer who makes their commute home more enjoyable by searching for fun holiday ideas. They start searching and quickly find loveholidays.com and open the page in their preferred browser. They find something they like and send the link to their partner who is still at work who opens the link on a mobile device which is connected to the office Wifi. Having decided to book a holiday they use a laptop on their home Wifi to book the holiday for their family.

Note that the mobile search client will set cookie values separate from those created by the regular browser implementation. Other apps, such as facebook, will also have their own browser implementations.

In this scenario we will end up with four different session IDs associated with this user journey. Is it possible to link these up?

A large proportion of our traffic, and advertising spend, is from mobile devices but we commonly see people dropping out of the purchase funnel when they get to the passenger details and payment details pages because this is easier to do on a laptop or tablet. We risk under-valuing our spend on acquiring mobile traffic if we can’t link this to the final booking event. People spend a lot of time considering their holiday options and will confer with other family members and friends before making a final decision in a way that you wouldn’t if you were buying a simple item like a pair of socks. This makes the user journey complex and hard to trace back to its start point.

Sources of Data

We receive a lot of data about customer actions. We can see their IP address, device type, search criteria and many other parameters that are assigned to any URLs that get passed around. Holidays have many options to choose from that create combinations of features that quickly become rare enough that they are unlikely to recur often purely through chance.

There are many thousands of options to choose from. Some of these combinations will be much more common than others. For example, a large hotel in Palma for a family of four during the summer holiday departing from Gatwick will be much more common than a small hotel in Tirana for six people in October departing from Luton airport. Similarly with IP addresses, some might be the IP address of a large organisation, a mobile phone mast at a busy train station or a home Wifi router.

Volume of Data

Whereas many applications of this type of classification approach could be limited to features that were reasonably commonly occurring, we want to take exactly the opposite approach and only consider features that are sufficiently rare to be distinctive. For example, a customer visiting the home page is not even worth considering as a feature because so many customers do this, that it offers no significant differentiation between customers. The rarer the feature the better, so long as it links at least two distinct session IDs. We cope with this volume of data by creating a Spark batch process using a cluster of 17 machines.

Covariance of Features

A common problem when using features to infer the likelihood of some event is that many features are not statistically independent. For example, the occurrence of flights to Palma, Mallorca will co-occur with the names or IDs of hotels in Mallorca. We countered this problem by building complexes of features that commonly co-occur. We account of pairs, triples and so on up to ten features. For speed of processing we generate composite features and assign a delta probability value for these that negates the overestimation that would occur from treating the features as statistically independent. This gets complicated with large complexes of features because of the factorial increase in the constituent occurrences.

Note that AB occurs twice at two levels removed from ABCD and would occur six times at three levels removed. At four levels removed there would be 24.

We also use the negative of the base 2 logarithm of the probability to do our calculations. This has several advantages:

• The estimation of the final probability requires the multiplication of probabilities but there is no standard product aggregation function in Apache Spark. Summing logarithms is equivalent to multiplying the original numbers so we can can use the standard summation function.
• The order of the probabilities is more important than the precise value. It doesn’t make that much difference if an event has a probability of 0.0001 or 0.00012 but it is very significant if it is hundreds or thousands of times more or less likely. A logarithmic value represents this better than a standard probability.

Just a Coincidence?

We are now in a position to calculate the probability of two distinct sessions sharing a feature or cluster of features. Can we use this to estimate the probability that this was purely by chance or as a result of a real world connection between the sessions? When does a pattern of user behaviour become sufficiently distinctive?

A Crooked Game

Let’s imagine we are betting on the toss of a coin with the person who gets the most heads being the winner. Let’s say there are 100 players but we suspect that one of them has a trick coin that has a head on both sides. Tossing one head is not suspicious but tossing 10 in a row starts to look very suspect. How can we represent this probabilistically?

Get David’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Let’s say:

• “p” is the probability of getting a head with a normal coin (i.e. 1/2)
• “q” is the probability of getting a head with the trick coin (i.e. 1)
• “c” is the probability than any given player is the cheat (i.e. 1/100)
• “n” is the number of tosses done so far

Assuming the current player has got all heads so far in the game we can say that the probability of this happen is:

• q^n if they are cheating
• p^n if they are using a regular coin

If we assume that just one player in 100 is using the trick coin we can say that the chance of the current player being the cheat is:

Note that before any tosses have been made (i.e. n = 0) the probability will be c, which is the a priori probability of each player being the cheat. We can see how this would play out:

This intuitively makes sense because getting a few heads in a row is not that unusual, but once we pass 7 heads things start to look very suspicious. We can never be 100% sure that someone is cheating but can get close enough that it’s only a rounding error away.

User Session Matching

We’ve seen how this approach could be applied to detect cheating in a simple game but how can we apply it to a user’s cross-device activity? Instead of one simple event we have events with many features, but we can still apply the same approach.

We can say that if the probability of a session having a particular feature is “p” then the probability of two sessions both having it is p². The probability of one session having the feature on the other not is p . (1 — p).

If “p” is the probability of matching features and “q” is the probability of the features one sessions has and the other doesn’t then the chance of them sharing the set of features that they do is:

What would the probability be if the sessions are actually related? Let’s suppose that there is a probability “t” of a feature that is on one session being “transmitted” to another session belonging to the same customer on a different device. We would expect this probability to be higher than the chance of this feature appearing on a completely unrelated sessions:

We can combine these two formulas to estimate the probability that two sessions are connected to the same customer, where “s” is the a priori probability that any two sessions are connected to the same customer.

This all supposes we can estimate the a priori probability of two sessions being connected. We relied our previous source of cross devicing data to estimate this.

Clustering

We used a simple clustering approach:

• Filter the pairs of sessions IDs for those that exceed a probability threshold (we used 80%)
• Sort the pairs of sessions ID by descending probability
• Add pairs to clusters with a maximum allowed cluster size (we used a max size of 20 session IDs)

Conclusions

This approach was a significant improvement over our previous approach:

• It doesn’t rely upon a third party supplier of cross devicing data
• The probabilistic approach means we can defend against bad values (for example when a link with a supposedly unique ID is shared on a public website and then clicked on by many completely unrelated users)
• Previous approaches relied upon values that could be assumed to be unique but we are able to utilise combinations of features that are sufficiently rare but not individually guaranteed to be unique