Data Mining. Concepts and Techniques, 3rd Edition

HAN

09-ch02-039-082-9780123814791

2011/6/1

3:15

Page 69

#31

2.4 Measuring Data Similarity and Dissimilarity

69

“How is dissimilarity computed between objects described by nominal attributes?”

The dissimilarity between two objects i and j can be computed based on the ratio of

mismatches:

d

(i, j) =

p − m

p

,

(2.11)

where m is the number of matches (i.e., the number of attributes for which i and j are in

the same state), and p is the total number of attributes describing the objects. Weights

can be assigned to increase the effect of m or to assign greater weight to the matches in

attributes having a larger number of states.

Example 2.17

Dissimilarity between nominal attributes. Suppose that we have the sample data of

Table 2.2, except that only the object-identifier and the attribute test-1 are available,

where test-1 is nominal. (We will use test-2 and test-3 in later examples.) Let’s compute

the dissimilarity matrix (Eq. 2.9), that is,











0

d

(2, 1)

0

d

(3, 1) d(3, 2)

0

d

(4, 1) d(4, 2) d(4, 3) 0











.

Since here we have one nominal attribute, test-1, we set p = 1 in Eq. (2.11) so that d(i, j)

evaluates to 0 if objects i and j match, and 1 if the objects differ. Thus, we get











0

1

0

1

1

0

0

1

1

0











.

From this, we see that all objects are dissimilar except objects 1 and 4 (i.e., d

(4,1) = 0).

Table 2.2

A Sample Data Table Containing Attributes

of Mixed Type

Object

test-1

test-2

test-3

Identifier

(nominal)

(ordinal)

(numeric)

1

code A

excellent

45

2

code B

fair

22

3

code C

good

64

4

code A

excellent

28

---

HAN

09-ch02-039-082-9780123814791

2011/6/1

3:15

Page 70

#32

70

Chapter 2 Getting to Know Your Data

Alternatively, similarity can be computed as

sim

(i, j) = 1 − d(i, j) =

m

p

.

(2.12)

Proximity between objects described by nominal attributes can be computed using

an alternative encoding scheme. Nominal attributes can be encoded using asymmetric

binary attributes by creating a new binary attribute for each of the M states. For an

object with a given state value, the binary attribute representing that state is set to 1,

while the remaining binary attributes are set to 0. For example, to encode the nominal

attribute map color, a binary attribute can be created for each of the five colors previ-

ously listed. For an object having the color yellow, the yellow attribute is set to 1, while

the remaining four attributes are set to 0. Proximity measures for this form of encoding

can be calculated using the methods discussed in the next subsection.

2.4.3

Proximity Measures for Binary Attributes

Let’s look at dissimilarity and similarity measures for objects described by either

symmetric or asymmetric binary attributes.

Recall that a binary attribute has only one of two states: 0 and 1, where 0 means that

the attribute is absent, and 1 means that it is present (Section 2.1.3). Given the attribute

smoker describing a patient, for instance, 1 indicates that the patient smokes, while 0

indicates that the patient does not. Treating binary attributes as if they are numeric can

be misleading. Therefore, methods specific to binary data are necessary for computing

dissimilarity.

“So, how can we compute the dissimilarity between two binary attributes?” One

approach involves computing a dissimilarity matrix from the given binary data. If all

binary attributes are thought of as having the same weight, we have the 2 × 2 contin-

gency table of Table 2.3, where q is the number of attributes that equal 1 for both objects

i and j, r is the number of attributes that equal 1 for object i but equal 0 for object j, s is

the number of attributes that equal 0 for object i but equal 1 for object j, and t is the

number of attributes that equal 0 for both objects i and j. The total number of attributes

is p, where p = q + r + s + t.

Recall that for symmetric binary attributes, each state is equally valuable. Dis-

similarity that is based on symmetric binary attributes is called symmetric binary

dissimilarity. If objects i and j are described by symmetric binary attributes, then the

Table 2.3

Contingency Table for Binary Attributes

Object

j

1

0

sum

1

q

r

q + r

Object

i

0

s

t

s + t

sum

q + s

r + t

p

---