# Can I use Manhattan distance on binary data for hierarchical clustering?

I understand that classically Jaccard and Hamming work best with binary data, but is there anything specifically wrong with using a Manhattan distance instead with the complete linkage function?

• Do the math. Hamming on binary = Manhattan. It's just faster to compute Hamming properly using bit operations like POPCNT. – Anony-Mousse Mar 8 '18 at 8:00

No, there's nothing inherently incorrect about doing that. In fact, for binary data, the Manhattan distance and Hamming distance are equivalent. For each variable the distance contribution is either 0 or 1; these contributions are summed over all variables. The Hamming distance explicitly sets these contributions to 0 or 1 as match/mismatch. The Manhattan distance works out to be the same because the underlying data is binary and so the only possible Manhattan distances between two values are 0 and 1.

Hamming and Manhattan distance for binary data are equivalent. I will show this graphically for a simple case:

Let's consider we have a dataset with two people and two variables:

Now for this case a contingency matrix of agreement/disagreement between two people is very simple:

We can see that with variable $var_1$ and $var_2$ the same pattern is repeated twice where $n_1=0$ and $n_2=1$.

We know from theory that Hamming distance from contingency table is calculated as $b+c=2+0=2$. Furthermore the definition of Hamming distance is as follows:

Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.

So in our case we have two strings $0 0$ and $1 1$. We can see that in both positions the symbols between two strings are different so the Hamming distance is $2$.

Now this is a geometric representation of our data:

$n_1$ has a value of $0$ on both variables and $n_2$ has a value of $1$ on both variables. You can see that manhattan distance between these two points equals the length of a dashed green line $1+1=2$.

EDIT: this can also be shown graphically with three variables. Then the graphical representation would be a cube defined in three dimensions by three variables. I suggest you look up a post about Hamming distance on Wikipedia to get an idea: Hamming distance

So to answer your question directly. There is no difference between using Hammond or Manhattan distance but there is a difference if you use Jaccard distance which is defined as $\frac{a}{a+b+c}$. There is no direct correspondence between Jaccard and Manhattan distance.

• @user3324491 did the post answer your question? – Vivaldi Aug 7 '18 at 13:22

With binary data Hamming and Manhattan are equivalent, so it's a question of "Hamming/Jaccard" vs. "Hamming/Complete Linkage".

Complete linkage takes the cluster distance as the distance between the farthest two points that are in different clusters and for binary Jaccard will be similar, except Jaccard does not consider absence of a feature as a sign of similarity, while complete linkage does.