Data Mining: Practical Machine Learning Tools and Techniques, Second Edition

are working with binary data. Weights are unchanged if the attribute value is 0,

because then they do not participate in the decision. Otherwise, the multiplier

is aif that attribute helps to make a correct decision and 1/aif it does not.

Another difference is that the threshold in the linear function is also a user-

specified parameter. We call this threshold qand classify an instance as belong-

ing to class 1 if and only if

The multiplier aneeds to be greater than one. The wiare set to a constant at

the start.

The algorithm we have described doesn’t allow negative weights, which—

depending on the domain—can be a drawback. However, there is a version,

called Balanced Winnow,which does allow them. This version maintains two

weight vectors, one for each class. An instance is classified as belonging to class

1 if:

Figure 4.11(b) shows the balanced algorithm.

Winnow is very effective in homing in on the relevant features in a dataset—

therefore it is called an attribute-efficientlearner. That means that it may be a

good candidate algorithm if a dataset has many (binary) features and most of

them are irrelevant. Both winnow and the perceptron algorithm can be used in

an online setting in which new instances arrive continuously, because they can

incrementally update their hypotheses as new instances arrive.

4.7 Instance-based learning

In instance-based learning the training examples are stored verbatim, and a dis-

tance function is used to determine which member of the training set is closest

to an unknown test instance. Once the nearest training instance has been

located, its class is predicted for the test instance. The only remaining problem

is defining the distance function, and that is not very difficult to do, particularly

if the attributes are numeric.

The distance function

Although there are other possible choices, most instance-based learners use

Euclidean distance. The distance between an instance with attribute values a 1 (1),

a 2 (1),...,ak(1)(where kis the number of attributes) and one with values a 1 (2),

a 2 (2),...,ak(2)is defined as

aa 11 12 aa aakk

2

2

1

2

( ()- ())+-(() (^2 ))^2 ++ -... ((^12 ) ())^2.

(wwa wwa000 111+- +-- ) +-( ) ++ -... (wwakkk+-) >q

wa wa wa 00 ++++ > 11 22 ... wakk q.

128 CHAPTER 4| ALGORITHMS: THE BASIC METHODS