Data Mining. Concepts and Techniques, 3rd Edition

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.

---