
K
最近邻算法
|
31
曼哈顿距离可以用于诸如图的遍历和离散优化这些有边沿约束的问题。还是以房子为
例,很可能你想知道的是通过开车(而不是坐飞机)能到达的房子的价格。否则,你
可能会在找房子时囊括需要跨越湖泊或者山脉的房子!
Levenshtein
距离
在自然语言处理中常用的另一种距离是
Levenshtein
距离。
Levenshtein
距离的工作原
理,类似于通过改变一个邻居来制作另一个邻居的精确副本。这个改变需要的步骤数
就是
Levenshtein
距离。通常它应用于字符串,用来确定字符串之间需要多少次删除、
添加或替换操作才能相等。
这个性质非常有用,就像计算字符串的近似度一样,它可以计算邻居之间的近似度。
算法公式有点复杂,因为它是一个递归函数,所以我们不看数学表达,而是通过
Python
代码来说明:
Manhattan distance
This gets us into what is called the Taxicab distance or Manhattan distance.
Equation 3-2. Manhattan distance
∑
i =0
n
x
i
− y
i
Note that there is no ability to travel out of bounds. So imagine that your metric space
is a grid of graphing paper and you are only allowed to draw along the boxes. ...