(New page: **Nearest Neighbor Classification Rule** - useful when there are several labels - e.g. fingerprint-based recognition .. |X_space_d| image:: tex :alt: tex: \vec{X_1}, \vec{X_2},...) |
|||
Line 1: | Line 1: | ||
+ | [http://balthier.ecn.purdue.edu/index.php/ECE662 ECE662 Main Page] | ||
+ | |||
+ | [http://balthier.ecn.purdue.edu/index.php/ECE662#Class_Lecture_Notes Class Lecture Notes] | ||
+ | |||
**Nearest Neighbor Classification Rule** | **Nearest Neighbor Classification Rule** | ||
− | + | - useful when there are several labels | |
− | + | - e.g. fingerprint-based recognition | |
.. |X_space_d| image:: tex | .. |X_space_d| image:: tex | ||
− | + | :alt: tex: \vec{X_1}, \vec{X_2}, \ldots, \vec{X_d} | |
.. |inRn| image:: tex | .. |inRn| image:: tex | ||
− | + | :alt: tex: \in \mathbb{R}^n | |
.. |X_0| image:: tex | .. |X_0| image:: tex | ||
− | + | :alt: tex: \vec{X_0} | |
.. |X| image:: tex | .. |X| image:: tex | ||
− | + | :alt: tex: \vec{X} | |
Problem: Given the labeled training samples: |X_space_d| |inRn| (or some other feature space) and an unlabeled test point |X_0| |inRn|. | Problem: Given the labeled training samples: |X_space_d| |inRn| (or some other feature space) and an unlabeled test point |X_0| |inRn|. | ||
Line 23: | Line 27: | ||
.. |D_from_SxS_to_R| image:: tex | .. |D_from_SxS_to_R| image:: tex | ||
− | + | :alt: tex: D: S\times S\rightarrow \mathbb{R} | |
There are many meaning depending on the metric we choose for the feature space. | There are many meaning depending on the metric we choose for the feature space. | ||
Line 32: | Line 36: | ||
.. |nonnegat| image:: tex | .. |nonnegat| image:: tex | ||
− | + | :alt: tex: D(\vec{x_1},\vec{x_2})\geq 0, \forall \vec{x_1},\vec{x_2}\in S | |
.. |symmetry| image:: tex | .. |symmetry| image:: tex | ||
− | + | :alt: tex: D(\vec{x_1},\vec{x_2})=D(\vec{x_2},\vec{x_1}), \forall \vec{x_1},\vec{x_2}\in S | |
.. |reflex| image:: tex | .. |reflex| image:: tex | ||
− | + | :alt: tex: D(\vec{x},\vec{x})=0, \forall \vec{x}\in S | |
.. |tri-ineq| image:: tex | .. |tri-ineq| image:: tex | ||
− | + | :alt: tex: 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 | |
that satisfies the following 4 properties: | that satisfies the following 4 properties: | ||
− | + | - Non-negativity |nonnegat| | |
− | + | - Symmetry |symmetry| | |
− | + | - Reflexivity |reflex| | |
− | + | - Triangle Inequality |tri-ineq| | |
.. |euclid| image:: tex | .. |euclid| image:: tex | ||
− | + | :alt: tex: D(\vec{x_1},\vec{x_2})=||\vec{x_1}-\vec{x_2}||_{L_2}=\sqrt{\sum_{i=1}^n ({x_1}^i-{x_2}^i)^2} | |
.. |manhattan| image:: tex | .. |manhattan| image:: tex | ||
− | + | :alt: tex: D(\vec{x_1},\vec{x_2})=||\vec{x_1}-\vec{x_2}||_{L_1}=\sum_{i=1}^n |{x_1}^i-{x_2}^i| | |
.. |minkowski| image:: tex | .. |minkowski| image:: tex | ||
− | + | :alt: tex: D(\vec{x_1},\vec{x_2})=||\vec{x_1}-\vec{x_2}||_{L_p}=(\sum_{i=1}^n ({x_1}^i-{x_2}^i)^p)^{\frac{1}{p}} | |
.. |riemannian| image:: tex | .. |riemannian| image:: tex | ||
− | + | :alt: tex: D(\vec{x_1},\vec{x_2})=\sqrt{(\vec{x_1}-\vec{x_2})^\top \mathbb{M}(\vec{x_1}-\vec{x_2})} | |
**Examples of metrics** | **Examples of metrics** | ||
Line 75: | Line 79: | ||
.. |nxn| image:: tex | .. |nxn| image:: tex | ||
− | + | :alt: tex: n\times n | |
where M is a symmetric positive definite |nxn| matrix. Different choices for M enable associating different weights with different components. | where M is a symmetric positive definite |nxn| matrix. Different choices for M enable associating different weights with different components. | ||
.. |Rn| image:: tex | .. |Rn| image:: tex | ||
− | + | :alt: tex: \mathbb{R}^n | |
.. |Zn| image:: tex | .. |Zn| image:: tex | ||
− | + | :alt: tex: \mathbb{Z}^n | |
.. |Cn| image:: tex | .. |Cn| image:: tex | ||
− | + | :alt: tex: \mathbb{C}^n | |
In this way, we see that |Rn|, |Zn|, |Cn| have many natural metrics, but feature could be in some other set, e.g. a discrete set. | In this way, we see that |Rn|, |Zn|, |Cn| have many natural metrics, but feature could be in some other set, e.g. a discrete set. |
Revision as of 00:01, 5 March 2008
- Nearest Neighbor Classification Rule**
- useful when there are several labels - e.g. fingerprint-based recognition
.. |X_space_d| image:: tex
- alt: tex: \vec{X_1}, \vec{X_2}, \ldots, \vec{X_d}
.. |inRn| image:: tex
- alt: tex: \in \mathbb{R}^n
.. |X_0| image:: tex
- alt: tex: \vec{X_0}
.. |X| image:: tex
- alt: tex: \vec{X}
Problem: Given the labeled training samples: |X_space_d| |inRn| (or some other feature space) and an unlabeled test point |X_0| |inRn|.
Classification: Let |X| be the closest training point to |X_0|, then we assign the class of |X| to |X_0|.
- What do we mean by closest?**
.. |D_from_SxS_to_R| image:: tex
- alt: tex: D: S\times S\rightarrow \mathbb{R}
There are many meaning depending on the metric we choose for the feature space.
- Definition** A "metric" on a space S is a function
|D_from_SxS_to_R|
.. |nonnegat| image:: tex
- alt: tex: D(\vec{x_1},\vec{x_2})\geq 0, \forall \vec{x_1},\vec{x_2}\in S
.. |symmetry| image:: tex
- alt: tex: D(\vec{x_1},\vec{x_2})=D(\vec{x_2},\vec{x_1}), \forall \vec{x_1},\vec{x_2}\in S
.. |reflex| image:: tex
- alt: tex: D(\vec{x},\vec{x})=0, \forall \vec{x}\in S
.. |tri-ineq| image:: tex
- alt: tex: 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
that satisfies the following 4 properties: - Non-negativity |nonnegat| - Symmetry |symmetry| - Reflexivity |reflex| - Triangle Inequality |tri-ineq|
.. |euclid| image:: tex
- alt: tex: D(\vec{x_1},\vec{x_2})=||\vec{x_1}-\vec{x_2}||_{L_2}=\sqrt{\sum_{i=1}^n ({x_1}^i-{x_2}^i)^2}
.. |manhattan| image:: tex
- alt: tex: D(\vec{x_1},\vec{x_2})=||\vec{x_1}-\vec{x_2}||_{L_1}=\sum_{i=1}^n |{x_1}^i-{x_2}^i|
.. |minkowski| image:: tex
- alt: tex: D(\vec{x_1},\vec{x_2})=||\vec{x_1}-\vec{x_2}||_{L_p}=(\sum_{i=1}^n ({x_1}^i-{x_2}^i)^p)^{\frac{1}{p}}
.. |riemannian| image:: tex
- alt: tex: D(\vec{x_1},\vec{x_2})=\sqrt{(\vec{x_1}-\vec{x_2})^\top \mathbb{M}(\vec{x_1}-\vec{x_2})}
- Examples of metrics**
Euclidean distance: |euclid|
Manhattan distance: |manhattan|
Minkowski metric: |minkowski|
Riemannian metric: |riemannian|
.. |nxn| image:: tex
- alt: tex: n\times n
where M is a symmetric positive definite |nxn| matrix. Different choices for M enable associating different weights with different components.
.. |Rn| image:: tex
- alt: tex: \mathbb{R}^n
.. |Zn| image:: tex
- alt: tex: \mathbb{Z}^n
.. |Cn| image:: tex
- alt: tex: \mathbb{C}^n
In this way, we see that |Rn|, |Zn|, |Cn| have many natural metrics, but feature could be in some other set, e.g. a discrete set.