Lecture :Nearest neighbor methods

Pr. Fatima Ezzahraa BEN BOUAZZA

[email protected]
Outline

1 General idea

2 Nearest neighbor and kernel-based

methods Properties of the NN method
Refinements of the NN method

3 Summary

2 / 14
Batch-mode Supervised Learning (Notations)

Objects (or observations):

Attribute vector: ∀i = 1, . . . , N.

Outputs: y i = y(oi) ∀i = 1, . . . , N.

LS Table

3 / 14
Nearest neighbor methods
Intuition: similar objects should have similar output values.
Ø NB: all inputs are numerical scalars
Ø Define distance measure in the input space:

Ø Nearest neighbor:

Ø Extrapolate output from nearest neighbor:

4 / 14
Nearest neighbor methods: illustration

Qu (Mvars)
3000 learning states
1000.
Zoom around state 4984

° °°° ••
° °°°°°°° ° °° °°° ° ° ° ° ° ° ° ° ••
°° °° °°°°°°°°°°°°° ° °° ° °°°°°°°°°°° °°°°°°°°° °°°°°° ° °°°°° °°° °°°°°° °°°°° ° °°°°°° °°°°°°° ° °°° • •
°°° ° ° °°° ° °° °°°° °°°°°°°°°°°°°°° °°°° °°°°°°°° °°°° ° ° ° °° °°° °° ° °°° ° °°°°°° ° °°° °°
°°° °°°°°° ° ° ° ° °° °°°°° ° °°° °°°°° °°° °°°° °° ° °°° ° °°°° °°°° °° ° °° °°° °° °° °°° •••
° °°°°°°°°°°° °°°°° °°° ° °° ° °°°°°° °°° °°°° ° °°° °°°° °°° °°°°° ° °°°°°° °° °° ° ° •• •••
750. ° ° °°°° °°°°°° °°°° °° °° °°° °°° ° °°°°° °° °° °°°°° ° °° ° °°° °°°°°° °°°° °°°° ° °°°°° °°° ° • •••• ••
°°° ° °°°°°°° ° °°° °° °° ° °°°°°° °°°°°°°°°°° °°°°° ° ° °°°°°°°°°° °°°° °° °°° °°° °°°°°° ° °° °° ••• ••
° °° ° °° ° °° °° ° ° ° ° °
° °° °°° ° ° °° °° °° °° ° ° °°° ° ° ° °°°°° °°°° °°° °°° °°°°°°° °°°° °° °°°° °°° • • •• ••
° °°°° °°°° °° °°° °°°°°°°° ° °°°°° °° °°°°
°°°° °° °°°°°° ° °°° °°•••••••
• ••• • •• •

° ° °°+° ••
° °° °°°° ° °° ° ° °° ° °° °° ° ° ° ° • •• •
° °° °° ° ° °° °° ° °°° ° ° °°°°°° °° ° °°°°°° °°°°° °° °°° °°°° °°°°° ° °°°°°° °° °° •• • ••••••••• •
500. ° °°° °° ° °°° °° ° ° °°° ° °°° ° °°° °° ° ° °°°° ° ° ° °° • • • • •••••
° °°
° °°° °°°° °°
°°°° ° ° °
° °° °° °°° °°°°°°°
° ° ° °° °°°° ° ° °°° ° ••••• •••• •
°°°° ° °° °°° °°°°°°°° °°°° °° °°° ° ° ° °° ° °°°°°
°°°°°°°°°° °°°°°°°°°°°°°°°°°°° ° °°°° °° °° ° °° °°°••
° °°°°°°° °°°° ° °°°°°°° °•• •••• • • ••••
° °°°°°°° °° °°°°°°°° °°° °° ° ° ° ° °°°°°°° °°°°°°°°°°° ° °
°° ° °°°°
°
°° °°
°°° °°°°°° °° °°°°°°°° °°°°°°° °° •••••••• •••• ••• • •• •
•
° °° ° °° ° ° ° ° °°°° ° ° °°°°° °°° ° °° °° °°°° •• ••••• •• •
° °°°° °° ° ° °°°°°° °°° °°°°° °° °°° °°°°°°°°°°°°°°° °°°°° ° °°°° °°°°°° ° °°°°°°°°°°°°°°°°°°•° •••••• •••• •• •• •••••••••

° ° °°• •
250. °°°°°
°°°°° °°°°° °°°° °° °° °°°° °°° °° ° ° ° °°°°°°°°°°° °°° °° ° °°°°°°°°°°°•° •••• •••• ••••••• •••
°° ° °°° °°°°°°°°°°°°°°°° ° °° ° °° ° ° °°°°° ° ° °° °
°°°°° °°° °°°° °° ° °°° ° °•• •• • ••
°° • •••• •• • •• •• •
° °°°°°
° ° °°°° °°°°° °°°°°°° °°°° °°°°°°°°°°
° ° ° °° ° ° ° °°°°° ° °° °°°°°° °° °° ° •• ••• •••••••••••
••••••• •
°°°°° °° ° °°°°°° ° ° ° ° ° ° °°°°° °° °°° °°° ° °° ° ° °° °°° °° °•••••• •• •• ••• •••••
°°°°° ° ° ° ° °°°° °° °°°°° °°° °° °° ° ° °° °° ••• ••• ••• • • •••• ••
°°° ° °°° ° °°°° °°° °° ° °° °°°° °° ° °° °°°°°°°° °°°°°°°°° °° °°°°° • •••• •••••• ••• • •••••
Qu=-20Mvar 0.0 ° ° °°°°°
°°° °° °°°° °°°°°°
°
°°° °° °° °°° °
° ° ° °° °° ° °° °°°°°°°
° °°°° ° °° °°° ° ° ° °°°°
°° ° °°° °°°°°°°° °° °°
°°°° ° ° ° °°°°° °° ° °°
°°°°°° °
°° °°°°°°
° ° °° ° °°
°°° ° °°°°°+°••• •••
°°
•••
••
••
° °° °°° ° ° °° °°°• °°• • •• •••••••• •••
•••
••
• • • •
• •
•
• •••• ••••
•
• •• •• •• •• •• ••

°°° °°° °° °°° °° °°°°° ° °°°°°°°°°° ° °° °°°°°° °°°° °°°° ° ° • • • • • • •• • •

°° °° ° ° ° °° ° °° ° ° °°° °° °° °°
°°° ° ° °°° •• •• • •• •• • •••• •
° ° ° ° ° ° °° • •••••••••••••••••••••• ••• ••••••••• ••

° •
° •• ••

°••
° ° ° ° ° ° °° ° ° ° • • • •• ••••••• ••• • •• ••• • • ••
-250. ° °°° °°°°°° °°°°°°° °° °°°°° °° °°°° °° °°°°°°°° °°°°° ° °°°°°° °°° • •••• •••••••• • •••• • •• •••
°°° ° ° ° °° ° °° °°° ° °°°°° ° °°°° °°° °° ° °°°° °••• ••••• ••
° °°°° ° ° °°°°°°° ° ° °°° °° ° °°°°°°°°°°°° °°°° °°° °°°°° ° ° ••• •• ••••••• •••••••• ••• ••••••••••••••••••••• ••
° °° ° ° ° °° ° °° °° ° ° ° °°°°° °°°°°•• •• •••• • • •• ••• • • ••• ••• • •
°°°°°°°° °° °°°° °° °° °°°° °°° ° ° ° °°°°°°° °°° °°° ° ••
• •• ••••• •• ••• ••• •• • • •• •• ••••••• • • •
••
°°° ° ° °° °° °°° °°°°°°°° ° °°° ° °°°°°°° °° ••• •••••• • • •• • •
-500. °° ° ° ° °°° °° ° ° °°° ° °°°°° ° ° • ••••• ••••• •• • •• • ••• •• •• • ••••••• ••
°° °° ° °° °°°°° °°°°° °° °°° °° °°°°°° °°°°°° °°••°••••• •••• •• • • • •• • ••••• •• •• ••• •• ••
°°°° °°°
° °°°°° ° °°°°° ° ° ° °° • •• •• •• ••••••••• • •• • •• ••• • •• •• ••• •
°° ° °° °°°°° °°° °°°°
° °°°° °° °°°° •••• ••• ••••••••• • • ••••• •• •• •••••• •••••••• • • •••• •
°° °°°° ••• • •• • • • • •••••• •
°°°° ° °°°°°° ° °° °° °°°°°°° °°°°°°° ° °° ° °°• • ••• •• • •• •• •• •• • •••••••• ••••••••• •••••••• ••••• ••••••
° °° ° °°
Pu (MW)
700. 800. 900. 1000. 1100. 1200. 1300.

Pu=1090MW Nearest neighbor (state 2276)

5 / 14
 1-Nearest Neighbor (1-NN)
(prototype based method, instance based learning, non-parametric
method)
Ø One of the simplest learning algorithm:
ü outputs as a prediction the output associated to the sample
which is the closest to the test object
M1 M2 Y
1 0.32 0.81 Healthy
2 0.15 0.38 Disease
3 0.39 0.34 Healthy
4 0.62 0.11 Disease
? 5 0.92 0.43 ?

üclosest=usually of minimal Euclidian

distance 6
 Obvious extension: k-NN

Ø Find the k nearest neighbors (instead of only the first one)

with respect to Euclidian distance
Ø Output the most frequent class (classification) or the
average outputs (regression) among the k neighbors.

7
 Effect of k on the error

Error

Under-fitting Over-fitting

CV error

LS error

Optimal k k
8
Properties of the NN method

Computational
> Training: storage of the LS (n × N )
> Testing: N distance computations ⇒ N × n
computations
Accuracy
> Asymptotically (N → ∞): suboptimal
(except if problem is deterministic)
> Strong dependence on choice of attributes
⇒ weighting of attributes

or attribute selection...

9 / 14
 Refinements of the NN method
1. The k-NN method:
Ø Instead of using only the nearest neighbor, one uses
the k (a number to be determined) nearest neighbors:

Ø Extrapolate from k nearest neighbors, e.g. for regression

and majority class for classification.

Ø k allows to control overfitting (like pruning of trees).

Ø Asymptotically (N → ∞): k(N) → ∞ and k(N ) → 0 ⇒ optimal

N
method (minimum error)
10 / 14
Refinements of the NN method

2. Condensing and editing of the LS:

Ø Condensing: remove ‘useless’ objects LS

Ø Editing: remove ‘outliers’ from LS
Ø Apply first editing then condensing (see notes)

3. Automatic tuning of the weight vector w...

4. Parzen windows and/or kernel methods:

where is a measure of similarity

11 / 14
Nearest neighbor, editing and condensing

Initial LS Edited LS Condensed LS

12 / 14
 k-NN

ü Advantages:
§ very simple
§ can be adapted to any data type by changing the distance
measure
ü Drawbacks:
§ choosing a good distance measure is a hard problem
§ very sensitive to the presence of noisy variables
§ slow for testing

13
Frequently asked questions

Ø How to choose a value for k ?

Ø Asymptotic (N → ∞) properties of 1-NN vs k-NN
ü Under which conditions is 1-NN asymptotically consistent?
ü Explain why: k(N ) → ∞ and k(N ) → 0 ⇒ optimal method
(minimum error) N

Ø Discuss computational complexity and interpretability

14 / 14