Nearest centroid classifier: Difference between revisions

Revision as of 12:14, 28 March 2012

Latest revision as of 03:09, 17 April 2025

(19 intermediate revisions by 11 users not shown)

Line 1:

{{Short description|A classification model in machine learning based on centroids}}

In [[machine learning]], a '''nearest centroid''' or '''nearest prototype classifier''' is a [[statistical classification|classification model]] that assigns to observations the label of the class of training samples whose [[mean]] ([[centroid]]) is closest to the observation.

[[Image:Rocchioclassgraph.jpg|thumb|right|250px|Rocchio Classification]]

In [[machine learning]], a '''nearest centroid classifier''' or '''nearest prototype classifier''' is a [[statistical classification|classification model]] that assigns to observations the label of the class of training samples whose [[mean]] ([[centroid]]) is closest to the observation. When applied to [[text classification]] using [[vector space model|word vectors]] containing [[tf*idf]] vectorsweights to represent documents, the nearest centroid classifier is known as the '''Rocchio classifier''' because of its similarity to the [[Rocchio algorithm]] for [[relevance feedback]].<ref>{{cite book

| last1 = Manning

| first1 = Christopher

Line 9 ⟶ 10:

| last3 = Schütze

| title = Introduction to Information Retrieval

| chapter = 14Vector space classification

| publisher = Cambridge University Press

| year = 2008

| url = http://nlp.stanford.edu/IR-book/html/htmledition/rocchio-classification-1.html

}}</ref>

Line 16 ⟶ 19:

| last1 = Tibshirani

| first1 = Robert

| authorlink1 = Robert Tibshirani

| last2 = Hastie

| first2 = Trevor

| authorlink2 = Trevor Hastie

| last3 = Narasimhan

| first3 = Balasubramanian

| last4 = Chu

| first4 = Gilbert

| title = Diagnosis of multiple cancer types by shrunken centroids of gene expression

| journal = Proceedings of the National Academy of Sciences

| volume = 99

| number = 10

| year = 2002

| doi = 10.1073/pnas.082099299

| pages=6567–6572

| pmid=12011421

| pmc=124443

| doi-access = free

| bibcode = 2002PNAS...99.6567T

}}</ref>

== Algorithm ==

===Training===

* Training procedure: givenGiven labeled training samples <math>\textstyle\{(\vec{x}_1, y_1), \dots, (\vec{x}_n, y_n)\}</math> with class labels <math>y_i \in \mathbf{Y}</math>, compute the per-class centroids <math>\textstyle\vec{\mu_lmu}_\ell = \frac{1}{|C_lC_\ell|}\sum_underset{i \in C_lC_\ell}{\sum} \vec{x}_i</math> where <math>C_lC_\ell</math> is the set of indices of samples belonging to class <math>l\ell \in \mathbf{Y}</math>.

* Prediction function: the class assigned to an observation <math>\vec{x}</math> is <math>\hat{y} = {\arg\min}_{l \in \mathbf{Y}} \|\vec{\mu}_l - \vec{x}\|</math>

===Prediction===

* Prediction function: theThe class assigned to an observation <math>\vec{x}</math> is <math>\hat{y} = {\arg\min}_{l\ell \in \mathbf{Y}} \|\vec{\mu}_l_\ell - \vec{x}\|</math>.

== See also ==

* [[Cluster hypothesis]]

* [[K-means clustering|''k''-means clustering]]

* [[K-nearest neighborneighbors algorithm|''k''-nearest neighbor algorithm]]

* [[Linear discriminant analysis]]

== References ==