The Illumination Model for
Nearest Neighbor Classification
Michael E. HOULE
National Institute of Informatics

Why

What

The disciplines of machine learning and data mining
continue to grapple with fundamental issues in thearea of knowledge representation. Many importanttasks in data analysis, such as similarity search,classification, and clustering, depend on the interplay
between data features and similarity measures.

This presentation introduces a new model of nearest
neighbor classification that starts from the premisethat featurization should be scale invariant. Under
this premise, the influence of individual training
points on the classification can be shown to resemble
many physical phenomena, most notably the way inwhich light sources combine to illuminate objects.

Featurization
NN CLASSIFICATION
 Traditional K-NN classification: K

most similar objects influence theclassification of the test object.
 The featurization of the data and thesimilarity measure are both taken asgiven.
 Open issues:o How big should K be?
o What weighting should be given

to the influence of eachneighbor?

FEATURES & SIMILARITY Role of features: competing

influences in the valuation of objectto-object similarity.
 Distance (or similarity) functions

always implicitly determine a relative
weighting among the features.
 Feature set + distance function 

designer’s policy on relative
influence of object attributes.

 Can’t change this policy!

SIMILARITY & SCALE
 Relative weighting is important:o Ratio of contribution of featurevalues to similarity.
o Ratio of contribution of similarity
values to classification scores.
 Scaling of feature values:o Leads to proportional scaling ofthe similarity values.
o In general, no effect on relative
contributions of features tosimilarity.
o Not accounted for by modelers.

DISCRIMINABILITY d(q,x) < d(q,y) yx should have greater
influence on y in theclassification of q.

qxz d(q,y) = d(q,z) q cannot distinguish y from z.
 Scaling of feature values should notaffect the classification decision.
o Note that distributionalclassification methods areaffected by scaling of features.

Illumination ModelBASIC CRITERIA Contribution of training point toSCALE INVARIANCE
 Relative to q, sets of Due to isotropy, influence overclassification criterion: influence.

indistinguishable points form
equivalence classes:

 Influence should be isotropic andE (q, r )  x  S | d (q, x)  r

monotone:d ( x, y )  d ( a , b )  I ( x, y )  I ( a , b )d ( x, y )  d ( a , b )  I ( x, y )  I ( a , b )INFLUENCE FORMULA

members of an equivalence class isconstant.

influence to change with scaling ofdistance values (and feature values).

 Basic criteria determines the form

 Equivalence classes can be thoughtthat influence can take.

of as an indivisible entity.
G

COMBINING INFLUENCES
 Each influence carries class

information with it.
 The greater the number of influencing

objects from a given class, thestronger the total influence for thatclass.
 Influences additive by class:1m 1d( q, x )xCshould then be scale invariant: I (q, x) dx   I (q, y) dy  G
E ( q ,r )xC

 Physical analogue: illumination withtraining objects as light sources.
 Majority vote: class with largest total

influence wins. (All items participate!) Other combination strategies arepossible.

 I (q, x) dx  I (q, x)  dx
E ( q ,r )E ( q ,r ) dx

 I ( q, x )  G

E ( q ,r )E ( q ,r )

EFFECT OF DIMENSIONALITYINTRINSIC DIMENSIONALITY As m tends to infinity, the illumination

ranked in terms of distance to q:
q : x0 , x1 , x2 ,  , xi , model decision tends to that of 1-NN
classification.

 Can normalize influences by dividing

each by the influence of the 1-NN
object.
GGI (q,) :,  , m 1,m 1
d (q, x0 )d (q, xi ) d (q, x0 ) 
I 0 (q,) : 1,  ,  d (q, xi )  Farther neighbors generally havesignificant (normalized) influence only
when the dimension is small.
 In the vicinity of a given test point q,only a subset of the features can beconsidered relevant.

m 1,

 Idea: substitute m by the intrinsic

dimension in the vicinity of q, as
estimated from the training set data.

 For m > 1, the influences of farther

neighbors diminishes faster as thedimensionality increases.
 When the normalized influences are

sufficiently small, further neighbors
need not be evaluated.

 Can be estimated in many ways:o PCA.
o Generalized expansion

dimension.
o Others.

連絡先： Michael E. HOULE (フール マイケル) ／ 国立情報学研究所 客員教授
TEL : 03-4212-2538

m 1dx


(,m)
r



GG
I ( q, x )  m 1m 1 ( , m)  d (q, x) d (q, x)
 In 3-dimensional space, inverse

square law.
 Can also be applied to other spaces,

both continuous and discrete.

 Consider ordered list of objects

I ( q , C )   I ( q , x )  G  In m-dimensional Euclidean space:E ( q ,r )

 Influence over equivalence classes
 Isotropy and monotonicity force

PHYSICAL INTERPRETATION

Email : meh@nii.ac.jp

SUMMARY A NN classification variant that

automatically determines (based on
distance values and dimensionality):o an appropriate neighborhoodsize.
o a natural distance-based
weighting scheme.
 Takes effects of dimensionality into

account in a natural way.
 Derivable from principles of isotropy,

monotonicity, equivalence, and scale
invariance.