# Classification Review
The goals for this homework are as follows:
1. To provide examples of using different classification techniques
2. To demonstrate the problem of model overfitting.
Model Overfitting
To illustrate the problem of model overfitting, we consider a two-dimensional dataset
containing 1500 labeled instances, each of which is assigned to one of two classes, 0
or 1. Instances from each class are generated as follows:
1. Instances from class 1 are generated from a mixture of 3 Gaussian distributions,
centered at [6,14], [10,6], and [14 14], respectively.
2. Instances from class 0 are generated from a uniform distribution in a square
region, whose sides have a length equals to 20.
For simplicity, both classes have equal number of labeled instances. The code for
generating and plotting the data is shown below. All instances from class 1 are shown
in red while those from class 0 are shown in black.
import numpy as np
import [Link] as plt
from [Link] import random
%matplotlib inline
N = 1500
mean1 = [6, 14]
mean2 = [10, 6]
mean3 = [14, 14]
cov = [[3.5, 0], [0, 3.5]] # diagonal covariance
[Link](50)
X = [Link].multivariate_normal(mean1, cov, int(N/6))
X = [Link]((X, [Link].multivariate_normal(mean2, cov, int(N/6))))
X = [Link]((X, [Link].multivariate_normal(mean3, cov, int(N/6))))
X = [Link]((X, 20*[Link](int(N/2),2)))
Y = [Link](([Link](int(N/2)),[Link](int(N/2))))
[Link](X[:int(N/2),0],X[:int(N/2),1],'r+',X[int(N/2):,0],X[int(N/2):,1],'k.',ms=4)
## Decision tree classifier
In this example, we reserve 80% of the labeled data for training and the remaining
20% for testing. We then fit decision trees of different maximum depths (from 2 to
50) to the training set and plot their respective accuracies when applied to the
training and test sets.
#########################################
# Training and Test set creation
#########################################
from sklearn.model_selection import train_test_split
X_train, X_test, Y_train, Y_test = train_test_split(X, Y, test_size=0.8, random_state=1)
from sklearn import tree
from [Link] import accuracy_score
#########################################
# Model fitting and evaluation
#########################################
maxdepths = [2,3,4,5,6,7,8,9,10,15,20,25,30,35,40,45,50]
trainAcc = [Link](len(maxdepths))
testAcc = [Link](len(maxdepths))
index = 0
for depth in maxdepths:
clf = [Link](max_depth=depth)
clf = [Link](X_train, Y_train)
Y_predTrain = [Link](X_train)
Y_predTest = [Link](X_test)
trainAcc[index] = accuracy_score(Y_train, Y_predTrain)
testAcc[index] = accuracy_score(Y_test, Y_predTest)
index += 1
#########################################
# Plot of training and test accuracies
#########################################
[Link](maxdepths,trainAcc,'ro-',maxdepths,testAcc,'bv--')
[Link](['Training Accuracy','Test Accuracy'])
[Link]('Max depth')
[Link]('Accuracy')
##K-Nearest neighbor classifier
In this approach, the class label of a test instance is predicted based on the majority
class of its *k* closest training instances. The number of nearest neighbors, *k*, is a
hyperparameter that must be provided by the user, along with the distance metric.
By default, we can use Euclidean distance (which is equivalent to Minkowski distance
with an exponent factor equals to p=2):
\begin{equation*}
\textrm{Minkowski distance}(x,y) = \bigg[\sum_{i=1}^N |x_i-y_i|^p \bigg]^{\frac{1}
{p}}
\end{equation*}
from [Link] import KNeighborsClassifier
import [Link] as plt
%matplotlib inline
numNeighbors = [1, 5, 10, 15, 20, 25, 30]
trainAcc = []
testAcc = []
for k in numNeighbors:
clf = KNeighborsClassifier(n_neighbors=k, metric='minkowski', p=2)
[Link](X_train, Y_train)
Y_predTrain = [Link](X_train)
Y_predTest = [Link](X_test)
[Link](accuracy_score(Y_train, Y_predTrain))
[Link](accuracy_score(Y_test, Y_predTest))
[Link](numNeighbors, trainAcc, 'ro-', numNeighbors, testAcc,'bv--')
[Link](['Training Accuracy','Test Accuracy'])
[Link]('Number of neighbors')
[Link]('Accuracy')
### Linear Classifiers
Linear classifiers such as logistic regression and support vector machine (SVM)
constructs a linear separating hyperplane to distinguish instances from different
classes.
For logistic regression, the model can be described by the following equation:
\begin{equation*}
P(y=1|x) = \frac{1}{1 + \exp^{-w^Tx - b}} = \sigma(w^Tx + b)
\end{equation*}
The model parameters (w,b) are estimated by optimizing the following regularized
negative log-likelihood function:
\begin{equation*}
(w^*,b^*) = \arg\min_{w,b} - \sum_{i=1}^N y_i \log\bigg[\sigma(w^Tx_i + b)\bigg] +
(1-y_i) \log\bigg[\sigma(-w^Tx_i - b)\bigg] + \frac{1}{C} \Omega([w,b])
\end{equation*}
where $C$ is a hyperparameter that controls the inverse of model complexity
(smaller values imply stronger regularization) while $\Omega(\cdot)$ is the
regularization term, which by default, is assumed to be an $l_2$-norm in sklearn.
For support vector machine, the model parameters $(w^*,b^*)$ are estimated by
solving the following constrained optimization problem:
\begin{eqnarray*}
&&\min_{w^*,b^*,\{\xi_i\}} \frac{\|w\|^2}{2} + \frac{1}{C} \sum_i \xi_i \\
\textrm{s.t.} && \forall i: y_i\bigg[w^T \phi(x_i) + b\bigg] \ge 1 - \xi_i, \ \ \xi_i \ge 0
\end{eqnarray*}
from sklearn import linear_model
from [Link] import SVC
C = [0.01, 0.1, 0.2, 0.5, 0.8, 1, 5, 10, 20, 50]
LRtrainAcc = []
LRtestAcc = []
SVMtrainAcc = []
SVMtestAcc = []
for param in C:
clf = linear_model.LogisticRegression(C=param)
[Link](X_train, Y_train)
Y_predTrain = [Link](X_train)
Y_predTest = [Link](X_test)
[Link](accuracy_score(Y_train, Y_predTrain))
[Link](accuracy_score(Y_test, Y_predTest))
clf = SVC(C=param,kernel='linear')
[Link](X_train, Y_train)
Y_predTrain = [Link](X_train)
Y_predTest = [Link](X_test)
[Link](accuracy_score(Y_train, Y_predTrain))
[Link](accuracy_score(Y_test, Y_predTest))
fig, (ax1, ax2) = [Link](1, 2, figsize=(12,6))
[Link](C, LRtrainAcc, 'ro-', C, LRtestAcc,'bv--')
[Link](['Training Accuracy','Test Accuracy'])
ax1.set_xlabel('C')
ax1.set_xscale('log')
ax1.set_ylabel('Accuracy')
[Link](C, SVMtrainAcc, 'ro-', C, SVMtestAcc,'bv--')
[Link](['Training Accuracy','Test Accuracy'])
ax2.set_xlabel('C')
ax2.set_xscale('log')
ax2.set_ylabel('Accuracy')
##Nonlinear Support Vector Machine
The code below shows an example of using nonlinear support vector machine with a
Gaussian radial basis function kernel to fit the 2-dimensional dataset.
from [Link] import SVC
C = [0.01, 0.1, 0.2, 0.5, 0.8, 1, 5, 10, 20, 50]
SVMtrainAcc = []
SVMtestAcc = []
for param in C:
clf = SVC(C=param,kernel='rbf',gamma='auto')
[Link](X_train, Y_train)
Y_predTrain = [Link](X_train)
Y_predTest = [Link](X_test)
[Link](accuracy_score(Y_train, Y_predTrain))
[Link](accuracy_score(Y_test, Y_predTest))
[Link](C, SVMtrainAcc, 'ro-', C, SVMtestAcc,'bv--')
[Link](['Training Accuracy','Test Accuracy'])
[Link]('C')
[Link]('log')
[Link]('Accuracy')
##Ensemble Methods
An ensemble classifier constructs a set of base classifiers from the training data and
performs classification by taking a vote on the predictions made by each base
classifier. We consider 3 types of ensemble classifiers in this example: bagging,
boosting, and random forest.
In the example below, we fit 500 base classifiers to the 2-dimensional dataset using
each ensemble method. The base classifier corresponds to a decision tree with
maximum depth equals to 10.
from sklearn import ensemble
from [Link] import DecisionTreeClassifier
numBaseClassifiers = 500
maxdepth = 10
trainAcc = []
testAcc = []
clf = [Link](n_estimators=numBaseClassifiers)
[Link](X_train, Y_train)
Y_predTrain = [Link](X_train)
Y_predTest = [Link](X_test)
[Link](accuracy_score(Y_train, Y_predTrain))
[Link](accuracy_score(Y_test, Y_predTest))
clf =
[Link](DecisionTreeClassifier(max_depth=maxdepth),n_estimat
ors=numBaseClassifiers)
[Link](X_train, Y_train)
Y_predTrain = [Link](X_train)
Y_predTest = [Link](X_test)
[Link](accuracy_score(Y_train, Y_predTrain))
[Link](accuracy_score(Y_test, Y_predTest))
clf =
[Link](DecisionTreeClassifier(max_depth=maxdepth),n_estim
ators=numBaseClassifiers)
[Link](X_train, Y_train)
Y_predTrain = [Link](X_train)
Y_predTest = [Link](X_test)
[Link](accuracy_score(Y_train, Y_predTrain))
[Link](accuracy_score(Y_test, Y_predTest))
methods = ['Random Forest', 'Bagging', 'AdaBoost']
fig, (ax1, ax2) = [Link](1, 2, figsize=(12,6))
[Link]([1.5,2.5,3.5], trainAcc)
ax1.set_xticks([1.5,2.5,3.5])
ax1.set_xticklabels(methods)
[Link]([1.5,2.5,3.5], testAcc)
ax2.set_xticks([1.5,2.5,3.5])
ax2.set_xticklabels(methods)