Nearest Neighbor Method

(Pattern Recognition)Pattern Recognition#machine Learning

• Identifies the class of the closest data (“dictionary pattern”) to the input.
• Very simple.
• Things to consider:
  • What features to use.
    • It is desirable for the features to be significantly different when the classes are different.
    • It is desirable for the features to remain relatively unchanged when the classes are the same.
    • If the dimensionality is too high, the performance may degrade (the ”Curse of Dimensionality”).
    • (The above two points often conflict with each other.)
  • How to measure distance.
    • Euclidean distance, Manhattan distance (generalized as $L_p$ distance).
    • Applying weights to specific directions of the vectors (e.g., doubling the vertical direction of a two-dimensional vector).
    • Is isotropic distance sufficient?
    • In extreme terms, pattern recognition is the study of distances between patterns.
      • There are almost infinite definitions for distance.
  • How to prepare the “dictionary patterns”.
    • Only the centroids of each class?
    • Only the points on the boundaries?
    • Use all the data? (Efficiency issues)
• Subtypes:
  • k-nearest neighbor method