# Distance calculation on variables that cannot be represented in the Euclidean space

Given a variable such as number of events attended together, which is more of a multi-dimensional data how can you calculate a sort of distance between people (i.e. a similarity score)?

Context:

For simplicity, lets say there are two types of data available

1. Customer_id and their purchases across brands (a.k.a. Buying Patterns)
2. Customer_id and the events attended (a.k.a. Socializing Patterns), where a customer may attend multiple events

The idea is to process the data and get a weighted (Based on business priorities) average similarity score that can identify customers who are similar to each other.

1. Buying Patterns: Here because it is continuous data that can be rolled up at customer_id level we can simply take a distance measure.
2. Socializing Patterns: If we roll up the data to a customer_id level with the number of events attended we lose information about which customer attended the same event as the other. This is valuable info lost as they might have met each other, may have mutual friends attending the event or simply means that they have similar tastes.

I was thinking of simply taking the number of events attended together itself as a distance between them after reversing the values (i.e. Maximum value - value), assuming that people who have attended more number of events together are similar to each other.

Is there a better approach to this? A better way to handle a variable that is more of a network variable (if that is the right word)

Note: there are 100s of events, and when I mean the distance cannot be represented in the Euclidean space I mean you cannot simply calculate the distance on the events data.

For example given an input with customer_id, event_id how can you measure the similarities between customers? You can't simply count the number of events attended and then calculate the distance because of the problem I've mentioned above.

One idea is to try out Gower's measure but I'm still trying to understand what that does exactly.

• How about an indicator variable for each event? Customers get a 1 on the variable if they attended the event, a 0 if they did not. You can then use a mixed similarty measure (since you will have both continuous and binary variables) like Gower. – Alvaro Fuentes Jun 1 '18 at 11:53
• You mean a 1/0 flag for each and every event right?. Well that's an idea, but to be honest with 100s of events I'm not a big fan of that – Raunak Thomas Jun 1 '18 at 11:57
• Can you just show how your data look like? What do you mean by "roll up"? Do you want a (dis)similarity measure on both your types of data at once or only on events data? What are "similar" individuals for you in your case, intuitively? – ttnphns Jun 6 '18 at 7:32
• ...and why do you think the variables cannot be represented in Euclidean space? Just your question is not enough clear, I think. – ttnphns Jun 6 '18 at 7:40
• When I say rolled up I mean aggregated. For example data at customer, date item level can be aggregated to the customer level by summing up all the items bought. I actually want it on both types of data, but lets say I just want it for the events data. In my case intuitively people who have attended the same event are similar because they have similar preferences. – Raunak Thomas Jun 6 '18 at 7:40

I assume you store your customers in any form similar to this:

(customer_1, {event_1, event_5, event_7, event_8})
(customer_2, {event_2, event_3, event_5, event_8, event_13})
...

Then you can measure how similar a given pair of customers are to each other, by measuring a similarity score for the respective sets of attended events.

Measuring similarity of sets with a notion of overlap can be done with Jaccard coefficient or Dice coefficient (among others). These are related, and can be derived from each other. You should check which one works best for your data, empirically.

Let A, B be the sets of events attended by customer 1, and customer 2, respectively.

Jaccard measures the number of commonly attended events, normalized by the number of events attended by either person: $$J(A,B) = {{|A \cap B|}\over{|A \cup B|}} = {{|A \cap B|}\over{|A| + |B| - |A \cap B|}}$$

Dice measures the number of commonly attended events (times 2), normalized by the number of events attended by either person with repetition: $$D(A,B) = \frac{2 |A \cap B|}{|A|+ |B|}$$

In the above example, the coefficients are: $J(A,B)=2/7$ and $D(A,B)=4/9$

Implementations are widely available (e.g., scikitlearn, Java Apache commons for Jaccard), but can also be done very easily on your own for any general programming language.

• What do mean saying Jaccard and Dice are "related and can be derived from each other"? So, knowing value of one you could get the value of the other without knowing their formula terms? This will make either one of the two theoretically redundant. Actually, that is not so, and both are usable. Dice coef. is most often applied for binary data representing nominal attributes stats.stackexchange.com/a/61910/3277 – ttnphns Jun 7 '18 at 9:25
• Yes, knowing one will give you the other, as explained here: link. In that sense, they are redundant. However, dependent on how you use them downstream, one might be favourable over the other. To the binarization of nominal attributes: Would that same mapping to dummy binary variables (mentioned in your link) be possible, if you want to apply Jaccard afterwards? – Lutz Büch Jun 7 '18 at 14:12
• Oops, you are completely right. I've entirely forgotten about that they are curvilinearly related (I myself had an answer observing the relationships of some binary measures with Dice). So, I take my comment remark back. +1 for your answer. – ttnphns Jun 7 '18 at 15:41
• Thank you for the answer I learnt quite a bit from these two answers. But in the end I guess I will go for a Gowers measure as there are a few continuous variables as well. – Raunak Thomas Jun 7 '18 at 17:55
• Can you also elaborate on what you should look for in your data to choose one method over the other – Raunak Thomas Jun 7 '18 at 20:17

I would suggest using the sample Mahalanobis distance for the vectors of indicator variables for the events. Suppose that you have $n$ customers and $m$ social events, so that you can represent event attendance in an $n \times m$ matrix:

$$\mathbf{M} = \begin{bmatrix} \boldsymbol{m}_1^\text{T} \\ \boldsymbol{m}_2^\text{T} \\ \vdots \\ \boldsymbol{m}_n^\text{T} \end{bmatrix} = \begin{bmatrix} m_{1,1} & m_{1,2} & \cdots & m_{1,m} \\ m_{2,1} & m_{2,2} & \cdots & m_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ m_{n,1} & m_{n,2} & \cdots & m_{n,m} \\ \end{bmatrix}.$$

The elements of this matrix would be indicator variables, but this is not actually necessary for the proceeding calculation of the distances. The matrix of squared Mahalanobis distances between the customeres is an $n \times n$ matrix given by:

$$\mathbf{D}^2 = \frac{\mathbf{c} \mathbf{M} (\mathbf{M}^\text{T} \mathbf{c} \mathbf{M})^{-1} \mathbf{M}^\text{T} \mathbf{c}}{n-1} \quad \quad \quad \mathbf{c} = \mathbf{I}_n - \tfrac{1}{n} \mathbf{1}_{n \times n}.$$

(Note that the matrix $\mathbf{c}$ is the centering matrix.) The square roots of the values in this matrix give the distances between the customers in terms of their event attendance.

Implementation in R: The above squared-distance matrix $\mathbf{D}^2$ can be calculated in R using the mahalanobis function in the stats package. This is done as follows (this code assumes that you have already entered the data as an $n \times m$ matrix of indicators assigned as M):

library(stats);
D2 <- mahalanobis(M, colMeans(M), cov(M));

• Thanks for the reply, so effectively what you are saying is that factors should be created (aka dummy code the variables) based on which the distance can be calculated but isn't that a problem for high dimentionality (~4k customers and ~1k events). The distance calculation might not have much meaning in such a case as far as I have read stats.stackexchange.com/a/122118/164939 – Raunak Thomas Jun 3 '18 at 10:55
• Not sure if that level of computation will present a problem. I would think it that would still be within the scope of what could be computed, so I wouldn't anticipate a problem. There is no reason it would not be meaningful - customers with more events in common will have closer distance than those with less, taking account of the number they attended. – Reinstate Monica Jun 3 '18 at 12:03
• Why are you suggesting Mahalanobis distance (and not, for example, euclidean or Manhattan)? In particular, what are resons to compute it on binary variables? – ttnphns Jun 6 '18 at 7:28