9/15/15
Nearest
Neighbor
Find
the
instance
that
is
closest
to
the
one
you
are
trying
to
classify;
assign
the
same
class
This
works
OK
for
data
that
tends
to
be
noise-
free
Classica-on
Using
the
Nearest
Neighbor
Big
Data
Analy-cs
Howles
Determining
nearness
Other
Methods
Some-mes
it
is
intui-ve:
Yes,
yes,
yes,
no
classica-on
of
A
No,
no,
yes,
no
classica-on
of
B
Distance
measurements
Euclidean
distance
ManhaVan
Distance
(City
Block)
Others
too,
but
well
focus
on
Euclidean
How
would
you
classify
Yes,
yes,
no
yes?
(probably
A)
Euclidean
Distance
Euclidean
Distance
If
looking
at
two
aVributes,
look
at
the
distance
between
them
This
is
the
same
calcula-on
you
have
used
to
determine
the
distance
between
2
points
on
a
2-D
plane
(a1-b1)2
+
(a2-b2)
2
+
+
(ak-bk))
2
9/15/15
Normalizing
the
data
What
is
the
distance?
Suppose
we
are
using
the
Euclidean
distance
If
we
look
at
the
dierence
between
aVributes,
some
may
be
very
skewed
Example:
Some-mes
it
may
be
obvious
Is
this
color
closest
to
black
or
white?
What
happens
if
you
have
>
1
aVribute?
Car
data;
mileage
and
age
of
the
car
Mileages
may
dier
by
thousands,
but
the
age
by
only
a
small
number
of
years
The
mileage
dierences
may
overshadow
the
age
Are
they
of
equal
importance?
Do
they
need
to
be
normalized?
Which
aVributes
are
really
important?
Weighted
Euclidean
Distance
Other
Distance
Formulas
If
the
aVributes
are
not
equally
important,
use
weights:
(
w1
(a1-b1)2
+
w2
(a2-b2)
2
+
+
wk
(ak-bk))
2
)
Indica-ng
that
we
have
determined
a
nearest
neighbor
implies
that
we
know
how
to
correctly
calculate
the
distance
between
the
two
instances
As
we
just
saw,
its
easy
to
calculate
the
distance
between
numeric
values
(assuming
the
values
themselves
have
meaning)
How
do
we
predict
distances
between
other
data
types?
10
Whats
the
dierence
between
Department
231
and
Department
240?
Calcula-ng
the
dierence
Whats
the
dierence
it
depends
Can
you
determine
a
distance
formula?
Is
department
info
embedded
in
other
data
(Do
people
in
certain
departments
earn
a
dierent
salary?)
Does
the
aVribute
really
maVer
(does
it
inuence
the
result)?
Suppose
you
have
employee
data
Assume
the
instances
include
aVributes
for
department
code
What
is
the
(numerical)
dierence
between
department
codes?
There
may
not
be
a
meaningful
way
to
determine
In
short,
you
cant
automa-cally
apply
the
Euclidean
distance
to
all
numeric
values
11
12
9/15/15
Calcula-ng
the
dierence
K-Nearest
Neighbor
Algorithm
What
if
we
are
trying
to
calculate
the
distance,
and
the
aVributes
are
not
numeric?
If
the
data
is
noisy,
K-Nearest
Neighbor
may
be
used
Classica-on
algorithm
based
on
K
closest
training
examples
An
object
is
classied
by
a
majority
vote
of
k
neighbors
How
is
nearest
neighbor
determined?
Look
for
an
instance
in
the
training
set
that
is
closest
to
the
instance
you
are
trying
to
classify
What
is
the
dierence
between
SE
and
CS?
Is
a
SE
student
closer
to
a
CS
student
or
an
EE
student?
You
may
need
to
look
for
another
meaningful
way
to
measure
the
distance
13
14
Determining
the
Op-mal
k
Missing
Values
The
more
noise,
the
greater
the
op-mal
value
of
k
For
nominal
aVributes,
assume
the
missing
value
is
maximally
dierent
from
all
others
For
numeric
values
with
both
values
missing,
assume
distance
is
1
Generally,
if
a
value
is
missing,
the
dierence
is
interpreted
to
be
as
large
as
it
can
be
You
can
run
cross
valida-on
tests
with
dierent
k
values;
choose
the
best
one
This
is
computa-onally-expensive
Monitor
your
results
if
you
see
an
instance
that
tends
to
misclassify
(its
not
representa-ve
of
a
good
neighbor),
discard
it
from
the
training
set
15
16
Compu-ng
Distances
The
ability
to
compute
distances
between
instances
comes
into
play
in
other
tools
we
will
study
later
on
If
you
use
a
tool,
be
sure
you
understand
how
distances
are
calculated
17