HAN
09-ch02-039-082-9780123814791
2011/6/1
3:15
Page 71
#33
2.4 Measuring Data Similarity and Dissimilarity
71
dissimilarity between i and j is
d
(i, j) =
r +
s
q +
r +
s +
t
.
(2.13)
For asymmetric binary attributes, the two states are not equally important, such as
the positive (1) and negative (0) outcomes of a disease test. Given two asymmetric binary
attributes, the agreement of two 1s (a positive match) is then considered more signifi-
cant than that of two 0s (a negative match). Therefore, such binary attributes are often
considered “monary” (having one state). The dissimilarity based on these attributes is
called asymmetric binary dissimilarity, where the number of negative matches, t, is
considered unimportant and is thus ignored in the following computation:
d
(i, j) =
r +
s
q +
r +
s
.
(2.14)
Complementarily, we can measure the difference between two binary attributes based
on the notion of similarity instead of dissimilarity. For example, the asymmetric binary
similarity between the objects
i and
j can be computed as
sim
(i, j) =
q
q +
r +
s
= 1 − d(i, j).
(2.15)
The coefficient sim
(
i,
j) of Eq. (2.15) is called the
Jaccard coefficient and is popularly
referenced in the literature.
When both symmetric and asymmetric binary attributes occur in the same data set,
the mixed attributes approach described in Section 2.4.6 can be applied.
Example 2.18
Dissimilarity between binary attributes. Suppose that a patient record table (
Table 2.4)
contains the attributes name, gender, fever, cough, test-1, test-2, test-3, and test-4, where
name is an object identifier,
gender is a symmetric attribute, and the remaining attributes
are asymmetric binary.
For asymmetric attribute values, let the values Y (yes) and P (positive) be set to 1,
and the value N (no or negative) be set to 0. Suppose that the distance between objects
Table 2.4
Relational Table Where Patients Are Described by Binary Attributes
name
gender
fever
cough
test-1
test-2
test-3
test-4
Jack
M
Y
N
P
N
N
N
Jim
M
Y
Y
N
N
N
N
Mary
F
Y
N
P
N
P
N
..
.
..
.
..
.
..
.
..
.
..
.
..
.
..
.
HAN
09-ch02-039-082-9780123814791
2011/6/1
3:15
Page 72
#34
72
Chapter 2 Getting to Know Your Data
(patients) is computed based only on the asymmetric attributes. According to Eq. (2.14),
the distance between each pair of the three patients—Jack, Mary, and Jim—is
d
(Jack, Jim) =
1 + 1
1 + 1 + 1
= 0.67,
d
(Jack, Mary) =
0 + 1
2 + 0 + 1
= 0.33,
d
(Jim, Mary) =
1 + 2
1 + 1 + 2
= 0.75.
These measurements suggest that Jim and Mary are unlikely to have a similar disease
because they have the highest dissimilarity value among the three pairs. Of the three
patients, Jack and Mary are the most likely to have a similar disease.
2.4.4
Dissimilarity of Numeric Data: Minkowski Distance
In this section, we describe distance measures that are commonly used for computing
the dissimilarity of objects described by numeric attributes. These measures include the
Euclidean, Manhattan, and Minkowski distances.
In some cases, the data are normalized before applying distance calculations. This
involves transforming the data to fall within a smaller or common range, such as [−1, 1]
or [0.0, 1.0]. Consider a height attribute, for example, which could be measured in either
meters or inches. In general, expressing an attribute in smaller units will lead to a larger
range for that attribute, and thus tend to give such attributes greater effect or “weight.”
Normalizing the data attempts to give all attributes an equal weight. It may or may not be
useful in a particular application. Methods for normalizing data are discussed in detail
in Chapter 3 on data preprocessing.
The most popular distance measure is Euclidean distance (i.e., straight line or
“as the crow flies”). Let i = (x
i1
, x
i2
,
..., x
ip
) and j = (x
j1
, x
j2
,
..., x
jp
) be two objects
described by p numeric attributes. The Euclidean distance between objects i and j is
defined as
d
(i, j) = (x
i1
− x
j1
)
2
+ (
x
i2
− x
j2
)
2
+ · · · + (
x
ip
− x
jp
)
2
.
(2.16)
Another well-known measure is the
Manhattan (or city block) distance, named so
because it is the distance in blocks between any two points in a city (such as 2 blocks
down and 3 blocks over for a total of 5 blocks). It is defined as
d
(i, j) = |x
i1
− x
j1
| + |x
i2
− x
j2
| + · · · + |x
ip
− x
jp
|.
(2.17)
Both the Euclidean and the Manhattan distance satisfy the following mathematical
properties:
Non-negativity: d
(i, j) ≥ 0: Distance is a non-negative number.
Identity of indiscernibles: d
(i, i) = 0: The distance of an object to itself is 0.