# These are the libraries that you will need for this lab
import time, warnings
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split, StratifiedKFold, cross_val_score, GridSearchCV
from sklearn.preprocessing import MinMaxScaler
from sklearn.pipeline import Pipeline
from sklearn.neighbors import KNeighborsClassifier
from sklearn.tree import DecisionTreeClassifier, plot_tree
from sklearn.metrics import accuracy_score, precision_score, recall_score, f1_score, ConfusionMatrixDisplay
warnings.filterwarnings('ignore')
plt.rcParams['figure.figsize'] = (10, 3.5)
SEED = 605Lab 8: Machine Learning - kNN & Decision Trees
Course: INS-605: Data Analysis II
Lecturer: Sothea HAS, PhD
- Student name: …
- ID: …
The notebook of the lab can be downloaded from Lab8: Machine Learning - KNN and Trees.
1. Data & Preprocessing (~10 min)
Goal: prepare the data for two supervised classification models that we will build in this lab: kNN (Section 2) and Decision Tree (Section 3).
Data: Breast Cancer Wisconsin (Diagnostic): 569 tumors, each described by 30 numerical features measured from images of cell nuclei (radius, texture, area, smoothness, …). The target is whether the tumor is malignant (\(y=1\)) or benign (\(y=0\)). The data is shipped with scikit-learn, so no download is needed.
The positive class is malignant. Missing a malignant tumor (a false negative) is much more costly than a false alarm, so keep an eye on the recall as well as on the F1-score.
1.1. Data Exploration
Run the cell below to load the data.
bc = load_breast_cancer(as_frame=True)
X = bc.data
y = (bc.target == 0).astype(int) # 1 = malignant, 0 = benign
y.name = 'malignant'
print(X.shape, '| positive class = malignant')
X.iloc[:, :6].head()A. Before modeling, always check the data quality. Compute the number of missing values, the number of duplicated rows and the class proportions. (The lecture showed that duplicates can make a kNN look better than it really is!)
n_missing = None # TODO: total number of missing values in the whole table X
n_dup = None # TODO: number of fully duplicated rows in X
class_prop = None # TODO: proportion of each class in y (benign = 0, malignant = 1)
print('missing values:', n_missing, '| duplicated rows:', n_dup)
print(class_prop.round(3))B. Look at the scale of the features: build a table with the min, max and std of every feature, sorted by std. The cell then prints the 3 features with the smallest spread and the 3 with the largest spread.
scale_tab = None # TODO: summary statistics of X with one row per feature and only 3 columns (min, max, std), sorted by std from smallest to largest
pd.concat([scale_tab.head(3), scale_tab.tail(3)]).round(3)C. In a markdown cell, briefly answer: which features would dominate a Euclidean distance computed on the raw data? Do you expect scaling to matter more for kNN or for a decision tree? Why?
C. Your answer here:
…
1.2. Train / Test Split
A. Keep 20% of the data as the test set, stratified on y so that both sets have the same malignant rate. The test set is used only to report the final performance of each model, never to tune or to choose anything.
X_train, X_test, y_train, y_test = None, None, None, None # TODO: split X and y into 80% train / 20% test, stratified on y, using random_state=SEED
print(X_train.shape, X_test.shape, '| malignant rate train / test:', round(y_train.mean(), 3), '/', round(y_test.mean(), 3))B. Complete evaluate, which returns the four classification metrics of the lecture for the positive class (malignant). The folds cv (5-fold, stratified) are defined once and reused for all the tuning below, and perf will collect the test performance of every model.
cv = StratifiedKFold(n_splits=5, shuffle=True, random_state=SEED) # the same 5 folds are used for ALL tuning below
def evaluate(y_true, y_pred):
return {'Accuracy': None, # TODO: proportion of correct predictions
'Precision': None, # TODO: precision of the positive class (malignant)
'Recall': None, # TODO: recall of the positive class
'F1-score': None} # TODO: F1-score of the positive class
perf = {} # test performance of every model will be stored here2. k-Nearest Neighbors: Default vs Fine-tuned (~15 min)
Goal: build a default kNN, see why scaling is essential, then fine-tune \(k\) with cross-validation.
2.1. Default kNN (k = 5)
A. Fit the default KNeighborsClassifier (5 neighbors) twice: on the raw features and on the min-max scaled features. The scaler must be learned on the training set only and then applied to the test set.
# --- (1) default kNN on the RAW features ---
knn_raw = None # TODO: a kNN classifier with all default settings, fitted on the raw training data
pred_raw = None # TODO: its predictions for the raw test features
# --- (2) default kNN on the MIN-MAX SCALED features ---
scaler = None # TODO: a min-max scaler, learned on the training features ONLY
X_train_sc = None # TODO: the scaled training features
X_test_sc = None # TODO: the scaled test features, using the scaling learned on the training set (never learn anything from the test set!)
knn_sc = None # TODO: a default kNN classifier fitted on the scaled training data
pred_sc = None # TODO: its predictions for the scaled test features
perf['kNN (default, raw)'] = evaluate(y_test, pred_raw)
perf['kNN (default, scaled)'] = evaluate(y_test, pred_sc)
pd.DataFrame(perf).T.round(3)B. In a markdown cell, briefly answer: what does scaling change in the test performance? Explain it with your answer of Section 1.1.C. Why must the scaler not be fitted on the test set?
B. Your answer here:
…
2.2. Fine-tuning k with Cross-validation
\(k=5\) is arbitrary. The lecture showed that a small \(k\) overfits and a large \(k\) underfits, so we tune \(k\) with cross-validation on the training set.
A. Scaling must be re-learned inside each CV fold (otherwise the validation fold leaks into the scaler). We therefore chain the scaler and the kNN in a Pipeline: the hyperparameters of a pipeline are named <step name>__<parameter name>. Complete the grid search over \(k=1,\dots,30\) scored with the F1-score.
knn_pipe = Pipeline([('scaler', MinMaxScaler()), ('knn', KNeighborsClassifier())])
k_values = list(range(1, 31))
param_grid_knn = None # TODO: a dictionary describing the grid: the key is the name of the "number of neighbors" parameter of the 'knn' step (step name, two underscores, parameter name) and the value is k_values
gs_knn = None # TODO: a grid search over knn_pipe and param_grid_knn, scored with the F1-score, using the folds in `cv`, and keeping the training scores too (needed for the plot below)
# TODO: run the grid search on the training set (X_train, y_train). The test set must not be touched!
print('Best k =', gs_knn.best_params_['knn__n_neighbors'], '| best CV F1 =', round(gs_knn.best_score_, 4))B. Plot the mean training and validation F1-score as a function of \(k\). The results of the search are stored in the dictionary gs_knn.cv_results_.
cvr = gs_knn.cv_results_
val_f1 = None # TODO: mean validation F1 of every k, taken from the dictionary `cvr` (print its keys to find the right entry)
trn_f1 = None # TODO: mean training F1 of every k, also taken from `cvr`
fig, ax = plt.subplots(figsize=(10, 3.5))
ax.plot(k_values, trn_f1, 'o-', color='orange', label='train F1')
ax.plot(k_values, val_f1, 'o-', color='#345a8b', label='CV (validation) F1')
ax.axvline(gs_knn.best_params_['knn__n_neighbors'], color='red', ls='--', label='best k')
ax.set_xlabel('k (number of neighbors)'); ax.set_ylabel('F1-score'); ax.legend(); plt.show()C. The grid search has already refitted the best pipeline on the whole training set (gs_knn.best_estimator_). Evaluate it on the test set and add it to perf.
pred_knn = None # TODO: predictions for the RAW test features with the best pipeline found by the grid search (the pipeline scales the data itself)
perf['kNN (tuned)'] = evaluate(y_test, pred_knn)
pd.DataFrame(perf).T.round(3)D. In a markdown cell, briefly answer:
What happens to the training and the validation F1 when \(k=1\)? What about large \(k\)? Which one is overfitting / underfitting?
Does the fine-tuned kNN improve the default scaled kNN on the test set? Is the gain conclusive with only 114 test tumors?
D. Your answer here:
…
…
3. Decision Trees: Default vs Fine-tuned (~30 min)
Goal: build a default tree, then explore which hyperparameters impact its performance the most, and finally fine-tune it. The lecture lists the main hyperparameters of a CART:
| Hyperparameter | Meaning |
|---|---|
max_depth |
maximum depth of the tree |
min_samples_leaf |
minimum number of samples in a leaf |
min_samples_split |
minimum number of samples in a node to be split |
max_features |
number of features randomly considered at each split |
criterion |
impurity measure (gini or entropy) |
No scaling is needed for trees, so we use the raw features.
3.1. Default Tree
A. Fit a default DecisionTreeClassifier (fix random_state=SEED since ties between splits are broken randomly) and compare its training and test accuracy.
tree0 = None # TODO: a decision tree with default settings except random_state=SEED, fitted on the raw training data
pred_tr0 = None # TODO: its predictions for the training set
pred_te0 = None # TODO: its predictions for the test set
print('depth:', tree0.get_depth(), '| leaves:', tree0.get_n_leaves())
print('train accuracy:', round(accuracy_score(y_train, pred_tr0), 3), '| test accuracy:', round(accuracy_score(y_test, pred_te0), 3))
perf['Tree (default)'] = evaluate(y_test, pred_te0)
pd.DataFrame(perf).T.round(3)Run the cell below to see the first two levels of the default tree (the regions of the lecture are defined by these rules).
fig, ax = plt.subplots(figsize=(13, 5))
plot_tree(tree0, max_depth=2, feature_names=list(X.columns), class_names=['benign', 'malignant'],
filled=True, impurity=True, fontsize=9, ax=ax)
plt.show()B. In a markdown cell, briefly answer: is there a sign of overfitting? Read the first split of the tree: which feature is used and what does the gini value of a node measure?
B. Your answer here:
…
3.2. Which Hyperparameters Matter? One at a Time
Strategy: start from the default tree, change one hyperparameter at a time over a range of values (all the others stay at their default) and measure the mean CV F1-score on the training set. A hyperparameter with a large variation of the score has a large impact.
Defaults:
max_depth=None(unlimited, equivalent to 15 here),min_samples_leaf=1,min_samples_split=2,max_features=None(all 30 features),criterion='gini'.
A. Complete the loop. For each value, build the tree and compute its F1-score on the 5 folds (only on the training set).
one_at_a_time = {
'max_depth': [1, 2, 3, 4, 5, 6, 8, 10, 15],
'min_samples_leaf': [1, 2, 5, 10, 20, 40, 60],
'min_samples_split': [2, 5, 10, 20, 40, 80, 120],
'max_features': [1, 2, 3, 5, 10, 20, 30],
'criterion': ['gini', 'entropy'],
}
rows = []
for hp, values in one_at_a_time.items():
for v in values:
tree = None # TODO: a decision tree with random_state=SEED where ONLY the hyperparameter named `hp` is set to the value `v`. Hint: put {hp: v} in a dictionary and unpack it as keyword arguments
scores = None # TODO: the F1-score of this tree on each of the 5 folds `cv`, computed on the training set only (an array of 5 numbers)
rows.append({'hyperparameter': hp, 'value': v, 'CV F1': scores.mean(), 'CV std': scores.std()})
oat = pd.DataFrame(rows)
oat.head()B. Run the cell below: it plots the mean CV F1 (with \(\pm1\) std over the folds) against each hyperparameter, with the same y-axis.
fig, axes = plt.subplots(1, 5, figsize=(18, 3.3), sharey=True)
for ax, hp in zip(axes, one_at_a_time):
d = oat[oat['hyperparameter'] == hp]
ax.errorbar(range(len(d)), d['CV F1'], yerr=d['CV std'], marker='o', capsize=3, color='#345a8b')
ax.set_xticks(range(len(d))); ax.set_xticklabels(d['value'].astype(str), rotation=45)
ax.set_title(hp)
axes[0].set_ylabel('CV F1')
plt.tight_layout(); plt.show()C. Measure the sensitivity of each hyperparameter: the gap between its best and its worst mean CV F1 in oat. Compare it with the typical fold-to-fold noise (CV std).
sens = None # TODO: for each hyperparameter, the gap between its best and its worst mean CV F1 in `oat` (one number per hyperparameter), sorted from largest to smallest
print('typical CV std across folds:', round(oat['CV std'].mean(), 3))
sens.round(4)D. In a markdown cell, briefly answer:
Which hyperparameters look the most / the least influential? Describe the shape of the curves (where does the score drop? where does it plateau?).
Why is this one-at-a-time ranking only a partial picture? (think about
max_depthandmin_samples_leaf, and about the fact that all the others are fixed at their defaults).
D. Your answer here:
…
…
3.3. Which Hyperparameters Matter? Full Grid Search
A. Now explore all the hyperparameters together with GridSearchCV scored with the F1-score on the same folds cv. The grid below has \(2\times5\times4\times3\times5=600\) configurations (3000 fits, ~10-60 s). Use all CPU cores.
param_grid_tree = {
'criterion': ['gini', 'entropy'],
'max_depth': [2, 3, 4, 6, 12], # 12 >= depth of the unconstrained tree: it means "no limit"
'min_samples_leaf': [1, 5, 10, 20],
'min_samples_split': [2, 10, 30],
'max_features': [2, 5, 10, 20, 30],
}
t0 = time.time()
gs_tree = None # TODO: a grid search over a DecisionTreeClassifier (random_state=SEED) and param_grid_tree, scored with the F1-score, using the folds in `cv`, with all CPU cores
# TODO: run the grid search on the training set
print(f'{time.time() - t0:.0f}s | best params: {gs_tree.best_params_} | best CV F1: {gs_tree.best_score_:.4f}')B. The score of every configuration is in res. For each hyperparameter and each of its values, compute the marginal mean CV F1: the average of the validation score over all configurations that share this value (the other hyperparameters are averaged out). The impact of a hyperparameter is then the gap between its best and its worst marginal mean.
res = pd.DataFrame(gs_tree.cv_results_)
marg_rows = []
for hp, values in param_grid_tree.items():
col = res['param_' + hp].astype(str) # compare as text so that all types of values work in the same way
for v in values:
m = None # TODO: the mean of the validation score (column 'mean_test_score' of `res`) over the rows where `col` equals str(v)
marg_rows.append({'hyperparameter': hp, 'value': str(v), 'marginal CV F1': m})
marg = pd.DataFrame(marg_rows)
impact = None # TODO: for each hyperparameter, the gap between its best and its worst 'marginal CV F1' in `marg`, sorted from largest to smallest
impact.round(4)C. Run the cell below: for each hyperparameter, one box per value shows the distribution of the CV F1 over all the configurations sharing that value.
fig, axes = plt.subplots(1, 5, figsize=(18, 3.5), sharey=True)
for ax, (hp, values) in zip(axes, param_grid_tree.items()):
sns.boxplot(x=res['param_' + hp].astype(str), y=res['mean_test_score'], order=[str(v) for v in values], color='#9db8d9', ax=ax)
ax.set_title(hp); ax.set_xlabel(''); ax.set_ylabel('CV F1')
plt.tight_layout(); plt.show()D. Display the 10 best configurations (sorted by validation score) with their hyperparameter values, the mean score and its std over the folds.
param_cols = [c for c in res.columns if c.startswith('param_')]
top10 = None # TODO: the 10 configurations with the best validation score (use the rank column of `res`), keeping only the columns in param_cols plus 'mean_test_score' and 'std_test_score'
top10.round(4)E. In a markdown cell, briefly answer:
Rank the hyperparameters by impact. Is it the same ranking as in 3.2? Which ones can be safely ignored?
Look at the top 10 configurations: which hyperparameters are the same in all of them (the ones that must be tuned carefully) and which ones change freely?
The impact depends on the range of values in the grid. Give an example from 3.2 vs 3.3.
E. Your answer here:
…
…
…
3.4. Final Tuned Tree
A. Take the best tree of the grid search (already refitted on the whole training set), evaluate it on the test set (once!) and add it to perf. Then compute its feature importances (total impurity reduction brought by each feature), sorted from the largest to the smallest.
tree_best = None # TODO: the best tree found by the grid search (already refitted on the whole training set)
pred_best = None # TODO: its predictions for the test set
perf['Tree (tuned)'] = evaluate(y_test, pred_best)
print('depth:', tree_best.get_depth(), '| leaves:', tree_best.get_n_leaves())
imp = None # TODO: a pandas Series of the feature importances of tree_best (index = feature names) sorted from the largest to the smallest
imp.head(8).sort_values().plot.barh(color='#345a8b', figsize=(8, 3), title='Top 8 feature importances'); plt.show()
pd.DataFrame(perf).T.round(3)B. In a markdown cell, briefly answer: compare the default and the tuned tree (CV F1 of the tuned tree vs its test F1, depth, leaves). Why does the tuned tree generalize better?
B. Your answer here:
…
4. Comparison of the Models (~5 min)
A. Display the final comparison table (all the models in perf) sorted by F1-score from the largest to the smallest, then run the next cell to see the confusion matrices.
final_tab = None # TODO: the performance table of all models (one row per model), sorted by F1-score from the largest to the smallest
display(final_tab.round(3))
fig, axes = plt.subplots(1, 3, figsize=(13, 3.6))
for ax, (name, pred) in zip(axes, {'kNN (tuned)': pred_knn, 'Tree (default)': pred_te0, 'Tree (tuned)': pred_best}.items()):
ConfusionMatrixDisplay.from_predictions(y_test, pred, display_labels=['benign', 'malignant'], ax=ax, colorbar=False)
ax.set_title(name)
plt.tight_layout(); plt.show()B. In a markdown cell, briefly answer:
Which model would you report? Consider the recall (number of malignant tumors missed) and the size of the test set.
What did tuning bring for each family (kNN, tree)? For which one was it more important?
Name one advantage of kNN and one advantage of trees for this problem.
B. Your answer here:
…
…
…
5. Going Further (Homework)
The sections below are for you to complete after class.
5.1. Curse of Dimensionality: kNN vs Tree
A. The lecture said that kNN suffers in high dimension because closeness loses its meaning. Test it: add \(p\in\{0,10,50,200,500\}\) pure noise features (standard normal) to the data and compare the test F1 of the tuned kNN (best \(k\) of Section 2.2) and of the tuned tree (best hyperparameters of Section 3.3).
rng = np.random.default_rng(SEED)
best_k = gs_knn.best_params_['knn__n_neighbors']
rows = []
for p in [0, 10, 50, 200, 500]:
Xtr_p = np.column_stack([X_train.to_numpy(), rng.normal(size=(len(X_train), p))])
Xte_p = np.column_stack([X_test.to_numpy(), rng.normal(size=(len(X_test), p))])
knn_p = None # TODO: a pipeline (min-max scaler + kNN with k = best_k) fitted on Xtr_p. Hint: reuse knn_pipe and set the parameter of the 'knn' step
tree_p = None # TODO: a decision tree with random_state=SEED and the best hyperparameters of the grid search gs_tree (dictionary unpacking again), fitted on Xtr_p
rows.append({'noise features': p,
'kNN F1': f1_score(y_test, knn_p.predict(Xte_p)),
'Tree F1': f1_score(y_test, tree_p.predict(Xte_p))})
noise_tab = pd.DataFrame(rows).set_index('noise features')
noise_tab.round(3)B. In a markdown cell: which model is more robust to useless features and why? How could you protect kNN (see the summary of the lecture)?
B. Your answer here:
…
5.2. A Better Measure of Hyperparameter Importance
A. The gap best - worst only uses two values per hyperparameter. A better summary is the share of variance of the CV scores of all the configurations explained by one hyperparameter alone,
\[\eta^2(\text{hp})=\frac{\sum_{v} n_v\,(\bar s_v-\bar s)^2}{\sum_i (s_i-\bar s)^2},\]
where \(s_i\) is the mean CV F1 of configuration \(i\), \(\bar s\) their overall mean, and \(n_v\), \(\bar s_v\) the number and the mean score of the configurations having the value \(v\) for this hyperparameter. Complete the code and compare with the ranking of 3.3.
total_ss = ((res['mean_test_score'] - res['mean_test_score'].mean()) ** 2).sum()
eta2 = {}
for hp in param_grid_tree:
g = res.groupby(res['param_' + hp].astype(str))['mean_test_score']
ss_between = None # TODO: the sum over the values of the hyperparameter of (group size) x (group mean - overall mean of 'mean_test_score') squared. `g.size()` and `g.mean()` give the group sizes and means
eta2[hp] = ss_between / total_ss
pd.Series(eta2).sort_values(ascending=False).round(3)B. In a markdown cell: does this ranking agree with 3.3? What percentage of the variation of the CV score is explained by the 5 hyperparameters taken separately? What does the remaining part represent?
B. Your answer here:
…
5.3. Full Workflow on a Regression Problem: Diabetes
Apply the same workflow to a regression problem with load_diabetes(as_frame=True) (442 patients, 10 features, target = disease progression after one year). Use KNeighborsRegressor and DecisionTreeRegressor.
A. Do the following (add cells below):
- Split 80/20 (
random_state=SEED) and build the baseline that always predicts the training mean. Compute its test RMSE and \(R^2\). - Fit a default kNN (on scaled features) and a default tree. Report the train and test RMSE.
- Tune \(k\) with 5-fold CV (scoring: negative RMSE) and plot the CV curve.
- Tune the tree with
GridSearchCVovermax_depth,min_samples_leafandmax_features. Which hyperparameter has the largest impact (use the marginal means of 3.3)? - Compare the 5 models on the test set (RMSE, \(R^2\)). Does tuning help more for kNN or for the tree? Explain.
# your code hereA. Your answer here:
…
Wrap-up
In this lab you:
- Checked the data (missing values, duplicates, scale) and split it into train/test with stratification (Section 1).
- Built a default kNN, saw why scaling is essential, and fine-tuned \(k\) with cross-validation inside a pipeline (Section 2).
- Built a default tree, explored which hyperparameters matter (one-at-a-time, then jointly with a grid search) and fine-tuned it (Section 3).
- Compared the models on the test set, used once (Section 4).
- (At home) Tested the curse of dimensionality, measured the hyperparameter importance with a variance ratio, and repeated the workflow for regression (Section 5).
The core idea: kNN needs scaling and a tuned \(k\); a tree needs no scaling but needs regularization, mostly through max_features and max_depth; always tune with CV on the training set only and report the test error once.