Lecture 02 Nearest Neighbor Methods STAT 479: Machine Learning, Fall 2018 Sebastian Raschka http://stat.wisc.edu/~sraschka/teaching/stat479-fs2018/ 1 1-Nearest Neighbor ? Sebastian Raschka STAT 479: Machine Learning ? FS 2018 !2 1-Nearest Neighbor ? Sebastian Raschka ? STAT 479: Machine Learning FS 2018 !3 Training Step [i] [i] ⟨x , y ⟩ ∈ 𝒟 Sebastian Raschka ( | 𝒟 | = n) STAT 479: Machine Learning FS 2018 !4 1-Nearest Neighbor Prediction Step closest_point := None closest_distance := for : current_distance := if current_distance < closest_distance: return closest_distance := current_distance closest_point := closest_point closest_point is the label of Sebastian Raschka STAT 479: Machine Learning FS 2018 !5 Commonly used: Euclidean Distance (L2) d(x[a], x[b]) = m ∑ j=1 Sebastian Raschka [a] [b] x − x (j j ) STAT 479: Machine Learning 2 FS 2018 !6 Nearest Neighbor Decision Boundary Sebastian Raschka STAT 479: Machine Learning FS 2018 !7 Decision Boundary Between (a) and (b) b a Sebastian Raschka a STAT 479: Machine Learning FS 2018 !8 Decision Boundary Between (a) and (c) a Sebastian Raschka c STAT 479: Machine Learning FS 2018 !9 a a Decision Boundary Between (a) and (c) d c Sebastian Raschka STAT 479: Machine Learning FS 2018 !10 Decision Boundary 1NN b a a c d c Sebastian Raschka STAT 479: Machine Learning FS 2018 !11 Decision Boundary 1-NN Sebastian Raschka STAT 479: Machine Learning FS 2018 !12 Which Point is Closest? Euclid distan a c ? b Sebastian Raschka STAT 479: Machine Learning FS 2018 !13 ? a a b ? b Depends on the Distance Measure! Euclidean distance=1 Manhattan distance=1 a c ? ? b Sebastian Raschka STAT 479: Machine Learning FS 2018 !14 Continuous Distance Measures Euclidean Manhattan m Minkowski: d(x , x ) = [∑ ( x − x [a] [b] [a] [b] j=1 )] p 1 p Mahalanobis ... Sebastian Raschka STAT 479: Machine Learning FS 2018