how to calculate Manhattan distance (or L1/ cityblock) for two 2D array?

Question

For 1D vector/array it's easier. For example:

array1 = [1, 2, 3] 
array2 = [1, 1, 1]

manhattan distance will be: (0+1+2) which is 3

import numpy as np
def cityblock_distance(A, B):
    result = np.sum([abs(a - b) for (a, b) in zip(A, B)])
    return result

The output for 2 points will be: 3 But what about a 2D array/vector. For example, what will be the manhattan(or L1 or cityblock) for two 2D vector like these (below):

arr1 = [[29, 30, 36, 30, 18],[37, 37, 49, 54, 23]]
arr2 = [[31, 33, 37, 34, 22],[37, 38, 50, 58, 26]]

if I use the code I mentioned above, it is giving 3 as output for 1 D vector. For the 2D vector the output it's showing as 2281. In my sense the logical manhattan distance should be like this :

difference of the first item between two arrays: 2,3,1,4,4 which sums to 14

difference of the second item between two array:0,1,1,4,3 which is 9.

The total sum will be 23 as so manhattan distance between those two 2D array will be 23.

Is my calculation going wrong or is there any problem with my concept of L1 distance?

Answer 1

If arr1 and arr2 are numpy arrays you can use:

# skip if already numpy arrays:
arr1 = np.array(arr1)
arr2 = np.array(arr2)

x = np.sum(np.abs(arr1 - arr2))
print(x)

Prints:

23

Answer 2

You can modify your code to calculate the desired result by comparing each list in the 2d array in turn (using your code for the 1D case) and then summing the result:

def cityblock_distance(A, B):
    result = np.sum([np.sum([abs(a - b) for (a, b) in zip(C, D)]) for C, D in zip(A, B)])
    return result
cityblock_distance(arr1,arr2)

Output:

23

Answer 3

Your code as written won't work, even after fixing the indentation:

In [177]: 
     ...: def cityblock_distance(A, B):
     ...:     result = np.sum([abs(a - b) for (a, b) in zip(A, B)])
     ...:     return result
     ...: 

In [178]: arr1=[[29, 30, 36, 30, 18],[37, 37, 49, 54, 23]]; arr2=[[31, 3
     ...: 3, 37, 34, 22],[37, 38, 50, 58, 26]]

In [179]: cityblock_distance(arr1, arr2)
------------------------------------------------------------------------
TypeError                              Traceback (most recent call last)
<ipython-input-179-d1b44e49141d> in <module>
----> 1 cityblock_distance(arr1, arr2)

<ipython-input-177-907001cbfc9b> in cityblock_distance(A, B)
      1 def cityblock_distance(A, B):
----> 2     result = np.sum([abs(a - b) for (a, b) in zip(A, B)])
      3     return result

<ipython-input-177-907001cbfc9b> in <listcomp>(.0)
      1 def cityblock_distance(A, B):
----> 2     result = np.sum([abs(a - b) for (a, b) in zip(A, B)])
      3     return result

TypeError: unsupported operand type(s) for -: 'list' and 'list'

If you convert to arrays you'll get the L1 norm you wanted:

In [180]: cityblock_distance(np.array(arr1), np.array(arr2))
Out[180]: 23

but, because by default numpy.sum sums all the elements in the array, you can omit the list comprehension altogether:

In [181]: np.sum(abs(np.array(arr1)-np.array(arr2)))
Out[181]: 23

Wikipedia calls your norm the "entry-wise 1,1-norm". You can compute the matrix 1-norm ("maximum absolute row sum") with numpy.linalg.norm:

In [193]: np.linalg.norm(np.array(arr1)-np.array(arr2), 1)
Out[193]: 8.0

Answer 4

Use neulab to calculate it:

First, install it:

pip install neulab

And the use it:

from neulab.Algorithms import ManhattanMetric
arr1 = [[29, 30, 36, 30, 18],[37, 37, 49, 54, 23]]
arr2 = [[31, 33, 37, 34, 22],[37, 38, 50, 58, 26]]
dist = ManhattanMetric(vector1=arr1, vector2=arr2)

Output: 23.0

You also can use another metrics in neulab. Read the documentation https://pypi.org/project/neulab