| Line 24: | Line 24: | ||
---- | ---- | ||
=='''METRICS AND NEAREST NEIGHBOR RULE'''== | =='''METRICS AND NEAREST NEIGHBOR RULE'''== | ||
| − | However, the closest distance between x' and x is determined by which metrics are used for feature space. A "metric" on a space S is a function <math>D: S\times S\rightarrow \mathbb{R}</math> | + | However, the closest distance between x' and x is determined by which metrics are used for feature space. A "metric" on a space S is a function <math>D: S\times S\rightarrow \mathbb{R}</math> which has following 4 properties: |
| − | + | ||
*Non-negativity : <math>D(\vec{x_{1}},\vec{x_{2}}) \geq 0, \forall \vec{x_{1}},\vec{x_{2}} \in S</math> | *Non-negativity : <math>D(\vec{x_{1}},\vec{x_{2}}) \geq 0, \forall \vec{x_{1}},\vec{x_{2}} \in S</math> | ||
*Symmetry : <math>D(\vec{x_{1}},\vec{x_{2}}) = D(\vec{x_{2}},\vec{x_{1}}), \forall \vec{x_{1}},\vec{x_{2}} \in S</math> | *Symmetry : <math>D(\vec{x_{1}},\vec{x_{2}}) = D(\vec{x_{2}},\vec{x_{1}}), \forall \vec{x_{1}},\vec{x_{2}} \in S</math> | ||
Revision as of 15:12, 29 April 2014
Nearest Neighbor Method (Still working on it. Please do not put any comments yet. Thank you)
A slecture by Sang Ho Yoon
Partly based on the ECE662 Spring 2014 lecture material of Prof. Mireille Boutin.
Contents
Introduction
In this slecture, basic principles of implementing nearest neighbor rule will be covered. The error related to the nearest neighbor rule will be discussed in detail including convergence, error rate, and error bound. Since the nearest neighbor rule mostly relies on a metric function between patterns, the properties of metrics will be studied in detail. Several examples will be illustrated to help understanding throughout the lecture.
Nearest Neighbor Rule
Let's consider a testing sample x. Based on labeled training sample D$ ^n $ $ = x_{1},... ,x_{n}, $ the nearest neighbor technique will find the closest point x' to x. Then we assign the class of x' to x. This is how the classification based on the nearest neighbor rule is processed. Although this rule is very simple, it is also reasonable. The label $ \theta' $ used in the nearest neighbor is random variable which means $\theta' = w_{i}$ is same as a posterior probability $ P(w_{i}|x'). $ If sample sizes are big enough, it could be assumed that x' is sufficiently close to x that $ P(w_{i}|x') = P(w_{i}|x). $
METRICS AND NEAREST NEIGHBOR RULE
However, the closest distance between x' and x is determined by which metrics are used for feature space. A "metric" on a space S is a function $ D: S\times S\rightarrow \mathbb{R} $ which has following 4 properties:
- Non-negativity : $ D(\vec{x_{1}},\vec{x_{2}}) \geq 0, \forall \vec{x_{1}},\vec{x_{2}} \in S $
- Symmetry : $ D(\vec{x_{1}},\vec{x_{2}}) = D(\vec{x_{2}},\vec{x_{1}}), \forall \vec{x_{1}},\vec{x_{2}} \in S $
- Reflexivity : $ D(\vec{x},\vec{x}) = 0, \forall \vec{x} \in S $
- Triangle Inequality : $ D(\vec{x_{1}},\vec{x_{2}}) + D(\vec{x_{2}},\vec{x_{3}}) \geq D(\vec{x_{1}},\vec{x_{3}}), \forall \vec{x_{1}},\vec{x_{2}},\vec{x_{3}} \in S $
References
Questions and comments
If you have any questions, comments, etc. please post them on this page.
