# What is the best way to use a 2-class classifier for a multi-category case?

I have a 3 class sample labeled data set, which I have divided into 2 parts. I am using the first part to train the two-class perceptron classifier.

One approach is to train $\binom{3}{2}$ two-class classifiers on training data for two classes at a time, and then use voting to classify the test samples for a multi-category case. The obvious problem with the above approach is the presence of ambiguous regions like the ones shown in the image below:

Pattern classification by Duda, Hart, Stork suggests training $c$ different linear discriminant functions, where $c$ is the number of unique classes, such that

$$g_{i}(x) = W_{i}^tX + w_{i0} \quad \quad \quad i = 1,..., c$$

and assigning $X$ to $\omega_{i}$ if $g_{i}(X) > g_{j}(X)$. The resulting classifier is called in the text book as a linear machine.

Following is an illustration from the book showing decision boundary produced by a linear machine for 3-class problem.

My doubt is how is the training process of the $c$ linear discriminant functions $g_{i}(X)$ different from training of $\binom{c}{2}$ 2-class classifiers?

UPDATE: The one vs rest approach mentioned in DavidDLewis's answer is not the one I am referring to. With the one vs rest approach, there are infact even more ambiguous regions. I am referring to linear machine classifier using which there are no ambiguous regions. See illustration of 1 vs rest approach below:

• I believe the 'linear machine' is a 'one vs. rest' approach, but the resultant classifiers are used differently than in your diagram. – shabbychef Sep 2 '11 at 20:11
• It would be really helpful, if you could please elaborate on the usage differences you mentioned in your comment. – stressed_geek Sep 4 '11 at 9:54
• imagine $k$ 1-v-rest classifiers as each describing regions where the $i$th class dominates the rest, _i.e._ $\left\{x|g_i(x) \le c_i\right\}$. This can result in the ambiguous region in your bottom figure. The linear machine approach trains the classifiers in the same way, but then defines the region where the $i$th class dominates as $\left\{x|g_i(x) \le g_j(x),\,\forall j\right\}$. – shabbychef Sep 4 '11 at 23:29