EE559 Homework 2-the one vs. one method for multiclass classification Solved

Description

1. In this 3-class problem, you will use the one vs. one method for multiclass classification. Let the discriminant functions be:

g₁₂(x)=−x₁−x₂+5 g₁₃(x)=−x₁+3 g₂₃(x)=−x₁+x₂−1

and g_ji(x)=−g_ij(x).

The decision rule is:

x ∈S_k iff g_kj(x) > 0 forall j ≠ k.

Draw the decision boundaries and label decision regions Γ_i and any indeterminate regions.

Classify the points   x = (4,1,   1), (1,5,  3), and (0,0,  1) .  If there is an indeterminate region prove it by

finding a point that doesn’t get classified according to the above rule.  If there is no indeterminate region, so state.

2. For the wine dataset, code up a nearest-means classifier with the following multiclass approach: one vs. rest.  Use the original unnormalized data.  Note that the class means should always be defined by the training data.  Run the one vs. rest classifier using only the following two features:  1 and 2.

Note that the same guidelines as HW1 apply on coding the classifier(s) yourself vs. using available packages or routines , with one possible exception*.

Give the following:

• Classification accuracy on training set and on testing set.
• Plots showing each resulting 2-class decision boundary and regions ( S_k′ vs. S_k′ ) (c) A plot showing the final decision boundaries and regions ( Γ₁, Γ₂, Γ₃, indeterminate).

Hint 1: For (b) and (c), you can use PlotDecBoundaries().  Modify it if necessary.

Hint 2: *If using Python, you may optionally use scipy.spatial.distance.cdist in calculating Euclidean distance between matrix elements.  HW2 continues on next page…

1. 1 of 2

3. (a) Derive an expression for the discriminant function 𝑔(𝑥)for a 2-class nearestmeans classifier, based on Euclidean distance, for class means ^µ1 and ^µ₂ .  Is the classifier linear?
   • Continuing from part (a), for the following class means:

µ₁=⎢⎡⎣ −⁰₂ ⎥⎦⎤, µ₂ =^⎡⎢⎣ ⁰₁ ⎥⎦⎤

Plot the decision boundaries and label the decision regions.

• Repeat part (a) except for a 3-class classifier, using the maximal value method (MVM):

find the three discriminant functions g₁(x), g₂(x), g₃(x) , given three class means µ1, µ2, and µ3.  Express in simplest form. Is the classifier linear?

• Continuing from part (c) using MVM, for the following class means:

⎡⎣ 2 ⎦⎤ 2 ⎢⎣⎡ 1 ⎥⎦, µ3=⎣⎢ 02 ⎥⎤⎦ µ1=⎢ −0 ⎥, µ = 0 ⎤ ⎡

Plot the decision boundaries and label the decision regions.

Hint:  Refer to Lecture 5 and (upcoming) Lecture 6 if you have trouble with this.

4. Extra credit. DHS Problem 5.9.  (Note that DHS has a set of “Problems”, and a set of

“Computer Exercises”, both at the end of each chapter.  This is “Problem” 9 of Chapter 5.)

The problem statement starts “The convex hull of a set of vectors…”.  Some versions of the DHS text may have a slightly different numbering of problems, so it’s best to check every time that you are going to solve an assigned problem.

Additional hint:  Classify the point  x twice, once based on  x in the convex hull of  S₁ data points, and a second time based on  x in the convex hull of  S₂ data points.