3.5. DISTANCE MEASURES
101
Non-Euclidean Spaces
Notice that several of the distance measures introduced in this section are
not Euclidean spaces. A property of Euclidean spaces that we shall ﬁnd
important when we take up clustering in Chapter 7 is that the average
of points in a Euclidean space always exists and is a point in the space.
However, consider the space of sets for which we deﬁned the Jaccard dis-
tance. The notion of the “average” of two sets makes no sense. Likewise,
the space of strings, where we can use the edit distance, does not let us
take the “average” of strings.
Vector spaces, for which we suggested the cosine distance, may or may
not be Euclidean. If the components of the vectors can be any real num-
bers, then the space is Euclidean. However, if we restrict components to
be integers, then the space is not Euclidean. Notice that, for instance, we
cannot ﬁnd an average of the vectors [1, 2] and [3, 1] in the space of vectors
with two integer components, although if we treated them as members of
the two-dimensional Euclidean space, then we could say that their average
was [2.0, 1.5].
3.5.6
Hamming Distance
Given a space of vectors, we deﬁne the Hamming distance between two vectors
to be the number of components in which they diﬀer. It should be obvious
that Hamming distance is a distance measure. Clearly the Hamming distance
cannot be negative, and if it is zero, then the vectors are identical. The dis-
tance does not depend on which of two vectors we consider ﬁrst. The triangle
inequality should also be evident. If x and z diﬀer in m components, and z
and y diﬀer in n components, then x and y cannot diﬀer in more than m + n
components. Most commonly, Hamming distance is used when the vectors are
Boolean; they consist of 0’s and 1’s only. However, in principle, the vectors can
have components from any set.
Example 3.17 : The Hamming distance between the vectors 10101 and 11110
is 3. That is, these vectors diﬀer in the second, fourth, and ﬁfth components,
while they agree in the ﬁrst and third components.
✷
3.5.7
Exercises for Section 3.5
! Exercise 3.5.1: On the space of nonnegative integers, which of the following
functions are distance measures? If so, prove it; if not, prove that it fails to
satisfy one or more of the axioms.
(a) max(x, y) = the larger of x and y.
