Lecture 3: k-Nearest Neighbours and SVM RBFs

Lecture 3: \(k\)-Nearest Neighbours and SVM RBFs#

UBC Master of Data Science program, 2023-24

Instructor: Varada Kolhatkar

If two things are similar, the thought of one will tend to trigger the thought of the other
– Aristotle

Lecture plan#

Announcements
Recap: Lecture 3 iClicker questions (~15 mins)
iClicker questions (~10 mins)
Class demo (~20 mins)
Break (~5 mins)
Worksheet section (~20 mins)
Intro to scaling (~5 mins)

Imports, announcements, and LOs#

Imports#

import sys
import os

import IPython
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
from IPython.display import HTML

sys.path.append(os.path.join(os.path.abspath("."), "code"))

import ipywidgets as widgets
import mglearn
from IPython.display import display
from ipywidgets import interact, interactive
from plotting_functions import *
from sklearn.dummy import DummyClassifier
from sklearn.model_selection import cross_validate, train_test_split
from utils import *

%matplotlib inline

pd.set_option("display.max_colwidth", 200)
import warnings

warnings.filterwarnings("ignore")

Learning outcomes#

From this lecture, you will be able to

explain the notion of similarity-based algorithms;
broadly describe how \(k\)-NNs use distances;
discuss the effect of using a small/large value of the hyperparameter \(k\) when using the \(k\)-NN algorithm;
describe the problem of curse of dimensionality;
explain the general idea of SVMs with RBF kernel;
broadly describe the relation of gamma and C hyperparameters of SVMs with the fundamental tradeoff.

Quick recap#

Why do we split the data?
What are the 4 types of data splits we discussed in the last lecture?
What are the benefits of cross-validation?
What is overfitting?
What’s the fundamental trade-off in supervised machine learning?
What is the golden rule of machine learning?

Important

If you want to run this notebook you will have to install ipywidgets. Follow the installation instructions here.

Motivation and distances [video]#

Analogy-based models#

Suppose you are given the following training examples with corresponding labels and are asked to label a given test example.

source

An intuitive way to classify the test example is by finding the most “similar” example(s) from the training set and using that label for the test example.

Analogy-based algorithms in practice#

Herta’s High-tech Facial Recognition
- Feature vectors for human faces
- \(k\)-NN to identify which face is on their watch list
Recommendation systems

General idea of \(k\)-nearest neighbours algorithm#

Consider the following toy dataset with two classes.
- blue circles \(\rightarrow\) class 0
- red triangles \(\rightarrow\) class 1
- green stars \(\rightarrow\) test examples

X, y = mglearn.datasets.make_forge()
X_test = np.array([[8.2, 3.66214339], [9.9, 3.2], [11.2, 0.5]])

plot_train_test_points(X, y, X_test)

../_images/510b8c4c01c8f52a29ddcf5a86ccca1f54e2a327a43197e6fe5445eb3612270b.png

Given a new data point, predict the class of the data point by finding the “closest” data point in the training set, i.e., by finding its “nearest neighbour” or majority vote of nearest neighbours.

import panel as pn
from panel import widgets
from panel.interact import interact
import matplotlib

pn.extension()

def f(n_neighbors):
    plt.clf()
    fig = plt.figure(figsize=(6, 4)) 
    plot_knn_clf(X, y, X_test, n_neighbors=n_neighbors)
    return fig

n_neighbors_selector = pn.widgets.IntSlider(name='n_neighbors', start=1, end=10, value=1)
# interact(f, n_neighbors=n_neighbors_selector)
interact(f, n_neighbors=n_neighbors_selector).embed(max_opts=10)

n_neighbors 1

<Figure size 640x480 with 0 Axes>

../_images/07ee105beea856ff075c421248fdbbf1b984fd1992f538d7b7e20030f8d1c635.png

n_neighbors 10

<Figure size 640x480 with 0 Axes>

../_images/d223b2d33db7e873c010050591839b68dc6f2283104983f622f2917b7e4f27a0.png

n_neighbors 9

<Figure size 640x480 with 0 Axes>

../_images/74f68a97e5db6bec6864f0972b3849a49fb8566898812f13f515a2dc37d6e6a3.png

n_neighbors

<Figure size 640x480 with 0 Axes>

../_images/46638e96b6c3d4a5a53b813315320cd4c010caf72882e922051e87f455ac7c71.png

n_neighbors 7

<Figure size 640x480 with 0 Axes>

../_images/ec1ca1204e8abf2f1191b058b5b1b95153dda4ae3bb55462809b5f609c5f1eb5.png

n_neighbors 6

<Figure size 640x480 with 0 Axes>

../_images/9eb70b29d0ba4886e3560584d7c098ead4d39d8bb225bff922f29a23b646e015.png

n_neighbors 5

<Figure size 640x480 with 0 Axes>

../_images/11580400da1359440d136f5a6ebf26267a8b907254d017a78481b5560180cec9.png

n_neighbors 4

<Figure size 640x480 with 0 Axes>

../_images/73213b9660b806eb70b66ecc79a8fe7fcc6c6e2e7ca356bdfefe23c8cf04eba9.png

n_neighbors 3

<Figure size 640x480 with 0 Axes>

../_images/593d35dfc3f756bef4859ae98ef3d8b3aa4ae0b2ac8e56dcf78e81d0566a86af.png

n_neighbors 2

<Figure size 640x480 with 0 Axes>

../_images/572920704014223f3ffa4311cad60f18f45a3c1cfe71c829b913e3b7fb521d07.png

n_neighbors 1

<Figure size 640x480 with 0 Axes>

# interactive(
#     f,
#     n_neighbors=widgets.IntSlider(min=1, max=10, step=2, value=1),
# )

Geometric view of tabular data and dimensions#

To understand analogy-based algorithms it’s useful to think of data as points in a high dimensional space.
Our X represents the problem in terms of relevant features (\(d\)) with one dimension for each feature (column).
Examples are points in a \(d\)-dimensional space.

How many dimensions (features) are there in the cities data?

cities_df = pd.read_csv("data/canada_usa_cities.csv")
X_cities = cities_df[["longitude", "latitude"]]
y_cities = cities_df["country"]

mglearn.discrete_scatter(X_cities.iloc[:, 0], X_cities.iloc[:, 1], y_cities)
plt.xlabel("longitude")
plt.ylabel("latitude");

../_images/c1d301cc99fc52f06f350098c39ead9dc75810299993bed6de02483aa078ac1a.png

Recall the Spotify Song Attributes dataset from homework 1.
How many dimensions (features) we used in the homework?

spotify_df = pd.read_csv("data/spotify.csv", index_col=0)
X_spotify = spotify_df.drop(columns=["target", "song_title", "artist"])
print("The number of features in the Spotify dataset: %d" % X_spotify.shape[1])
X_spotify.head()

---------------------------------------------------------------------------
FileNotFoundError                         Traceback (most recent call last)
Cell In[9], line 1
----> 1 spotify_df = pd.read_csv("data/spotify.csv", index_col=0)
X_spotify = spotify_df.drop(columns=["target", "song_title", "artist"])
print("The number of features in the Spotify dataset: %d" % X_spotify.shape[1])

File ~/miniconda3/envs/571/lib/python3.10/site-packages/pandas/io/parsers/readers.py:948, in read_csv(filepath_or_buffer, sep, delimiter, header, names, index_col, usecols, dtype, engine, converters, true_values, false_values, skipinitialspace, skiprows, skipfooter, nrows, na_values, keep_default_na, na_filter, verbose, skip_blank_lines, parse_dates, infer_datetime_format, keep_date_col, date_parser, date_format, dayfirst, cache_dates, iterator, chunksize, compression, thousands, decimal, lineterminator, quotechar, quoting, doublequote, escapechar, comment, encoding, encoding_errors, dialect, on_bad_lines, delim_whitespace, low_memory, memory_map, float_precision, storage_options, dtype_backend)
kwds_defaults = _refine_defaults_read(
   dialect,
   delimiter,
   (...)
   dtype_backend=dtype_backend,
)
kwds.update(kwds_defaults)
--> 948 return _read(filepath_or_buffer, kwds)

File ~/miniconda3/envs/571/lib/python3.10/site-packages/pandas/io/parsers/readers.py:611, in _read(filepath_or_buffer, kwds)
_validate_names(kwds.get("names", None))
# Create the parser.
--> 611 parser = TextFileReader(filepath_or_buffer, **kwds)
if chunksize or iterator:
   return parser

File ~/miniconda3/envs/571/lib/python3.10/site-packages/pandas/io/parsers/readers.py:1448, in TextFileReader.__init__(self, f, engine, **kwds)
   self.options["has_index_names"] = kwds["has_index_names"]
self.handles: IOHandles | None = None
-> 1448 self._engine = self._make_engine(f, self.engine)

File ~/miniconda3/envs/571/lib/python3.10/site-packages/pandas/io/parsers/readers.py:1705, in TextFileReader._make_engine(self, f, engine)
   if "b" not in mode:
       mode += "b"
-> 1705 self.handles = get_handle(
   f,
   mode,
   encoding=self.options.get("encoding", None),
   compression=self.options.get("compression", None),
   memory_map=self.options.get("memory_map", False),
   is_text=is_text,
   errors=self.options.get("encoding_errors", "strict"),
   storage_options=self.options.get("storage_options", None),
)
assert self.handles is not None
f = self.handles.handle

File ~/miniconda3/envs/571/lib/python3.10/site-packages/pandas/io/common.py:863, in get_handle(path_or_buf, mode, encoding, compression, memory_map, is_text, errors, storage_options)
elif isinstance(handle, str):
   # Check whether the filename is to be opened in binary mode.
   # Binary mode does not support 'encoding' and 'newline'.
   if ioargs.encoding and "b" not in ioargs.mode:
       # Encoding
--> 863         handle = open(
           handle,
           ioargs.mode,
           encoding=ioargs.encoding,
           errors=errors,
           newline="",
       )
   else:
       # Binary mode
       handle = open(handle, ioargs.mode)

FileNotFoundError: [Errno 2] No such file or directory: 'data/spotify.csv'

Dimensions in ML problems#

In ML, usually we deal with high dimensional problems where examples are hard to visualize.

\(d \approx 20\) is considered low dimensional
\(d \approx 1000\) is considered medium dimensional
\(d \approx 100,000\) is considered high dimensional

Feature vectors#

Feature vector: is composed of feature values associated with an example.

Some example feature vectors are shown below.

print(
    "An example feature vector from the cities dataset: %s"
    % (X_cities.iloc[0].to_numpy())
)
print(
    "An example feature vector from the Spotify dataset: \n%s"
    % (X_spotify.iloc[0].to_numpy())
)

An example feature vector from the cities dataset: [-130.0437   55.9773]
An example feature vector from the Spotify dataset: 
[ 1.02000e-02  8.33000e-01  2.04600e+05  4.34000e-01  2.19000e-02
  2.00000e+00  1.65000e-01 -8.79500e+00  1.00000e+00  4.31000e-01
  1.50062e+02  4.00000e+00  2.86000e-01]

Similarity between examples#

Let’s take 2 points (two feature vectors) from the cities dataset.

two_cities = X_cities.sample(2, random_state=120)
two_cities

	longitude	latitude
69	-104.8253	38.8340
35	-112.0741	33.4484

The two sampled points are shown as big black circles.

mglearn.discrete_scatter(
    X_cities.iloc[:, 0], X_cities.iloc[:, 1], y_cities, s=8, alpha=0.3
)
mglearn.discrete_scatter(
    two_cities.iloc[:, 0], two_cities.iloc[:, 1], markers="o", c="k", s=18
);

../_images/ffb1854d5d10ccc86d997f435035809c09bb1036f73d4a8fa6548721c729833c.png

Distance between feature vectors#

For the cities at the two big circles, what is the distance between them?
A common way to calculate the distance between vectors is calculating the Euclidean distance.
The euclidean distance between vectors \(u = <u_1, u_2, \dots, u_n>\) and \(v = <v_1, v_2, \dots, v_n>\) is defined as:

\[distance(u, v) = \sqrt{\sum_{i =1}^{n} (u_i - v_i)^2}\]

Euclidean distance#

two_cities

	longitude	latitude
69	-104.8253	38.8340
35	-112.0741	33.4484

Subtract the two cities
Square the difference
Sum them up
Take the square root

# Subtract the two cities
print("Subtract the cities: \n%s\n" % (two_cities.iloc[1] - two_cities.iloc[0]))

# Squared sum of the difference
print(
    "Sum of squares: %0.4f" % (np.sum((two_cities.iloc[1] - two_cities.iloc[0]) ** 2))
)

# Take the square root
print(
    "Euclidean distance between cities: %0.4f"
    % (np.sqrt(np.sum((two_cities.iloc[1] - two_cities.iloc[0]) ** 2)))
)

Subtract the cities: 
longitude   -7.2488
latitude    -5.3856
dtype: float64

Sum of squares: 81.5498
Euclidean distance between cities: 9.0305

two_cities

	longitude	latitude
69	-104.8253	38.8340
35	-112.0741	33.4484

# Euclidean distance using sklearn
from sklearn.metrics.pairwise import euclidean_distances

euclidean_distances(two_cities)

array([[0.        , 9.03049217],
       [9.03049217, 0.        ]])

Note: scikit-learn supports a number of other distance metrics.

Finding the nearest neighbour#

Let’s look at distances from all cities to all other cities

dists = euclidean_distances(X_cities)
np.fill_diagonal(dists, np.inf)
dists.shape

(209, 209)

pd.DataFrame(dists)

	0	1	2	3	4	5	6	7	8	9	...	199	200	201	202	203	204	205	206	207	208
0	inf	4.955113	9.869531	10.106452	10.449666	19.381676	28.366626	33.283857	33.572105	36.180388	...	9.834455	58.807684	16.925593	56.951696	59.384127	58.289799	64.183423	52.426410	58.033459	51.498562
1	4.955113	inf	14.677579	14.935802	15.305346	24.308448	33.200978	38.082949	38.359992	40.957919	...	14.668787	63.533498	21.656349	61.691640	64.045304	63.032656	68.887343	57.253724	62.771969	56.252160
2	9.869531	14.677579	inf	0.334411	0.808958	11.115406	20.528403	25.525757	25.873103	28.479109	...	0.277381	51.076798	10.783789	49.169693	51.934205	50.483751	56.512897	44.235152	50.249720	43.699224
3	10.106452	14.935802	0.334411	inf	0.474552	10.781004	20.194002	25.191396	25.538702	28.144750	...	0.275352	50.743133	10.480249	48.836189	51.599860	50.150395	56.179123	43.904226	49.916254	43.365623
4	10.449666	15.305346	0.808958	0.474552	inf	10.306500	19.719500	24.716985	25.064200	27.670344	...	0.675814	50.269880	10.051472	48.363192	51.125476	49.677629	55.705696	43.435186	49.443317	42.892477
...	...	...	...	...	...	...	...	...	...	...	...	...	...	...	...	...	...	...	...	...	...
204	58.289799	63.032656	50.483751	50.150395	49.677629	39.405415	30.043890	25.057003	24.746328	22.127878	...	50.333340	0.873356	41.380643	1.345136	3.373031	inf	6.102435	6.957987	0.316363	6.800190
205	64.183423	68.887343	56.512897	56.179123	55.705696	45.418031	36.031385	31.032874	30.709185	28.088948	...	56.358333	5.442806	47.259286	7.369875	5.108681	6.102435	inf	12.950733	6.303916	12.819584
206	52.426410	57.253724	44.235152	43.904226	43.435186	33.258427	24.059863	19.187663	18.932124	16.380495	...	44.100248	7.767852	35.637982	5.930561	9.731583	6.957987	12.950733	inf	6.837848	3.322755
207	58.033459	62.771969	50.249720	49.916254	49.443317	39.167214	29.799983	24.810368	24.497386	21.878183	...	50.098326	0.930123	41.121628	1.082749	3.286821	0.316363	6.303916	6.837848	inf	6.555740
208	51.498562	56.252160	43.699224	43.365623	42.892477	32.612755	23.244592	18.256813	17.946783	15.328953	...	43.546610	7.378764	34.596810	5.473691	8.568009	6.800190	12.819584	3.322755	6.555740	inf

209 rows × 209 columns

Let’s look at the distances between City 0 and some other cities.

print("Feature vector for city 0: \n%s\n" % (X_cities.iloc[0]))
print("Distances from city 0 to the first 5 cities: %s" % (dists[0][:5]))
# We can find the closest city with `np.argmin`:
print(
    "The closest city from city 0 is: %d \n\nwith feature vector: \n%s"
    % (np.argmin(dists[0]), X_cities.iloc[np.argmin(dists[0])])
)

Feature vector for city 0: 
longitude   -130.0437
latitude      55.9773
Name: 0, dtype: float64

Distances from city 0 to the first 5 cities: [        inf  4.95511263  9.869531   10.10645223 10.44966612]
The closest city from city 0 is: 81 

with feature vector: 
longitude   -129.9912
latitude      55.9383
Name: 81, dtype: float64

Ok, so the closest city to City 0 is City 81.

Question#

Why did we set the diagonal entries to infinity before finding the closest city?

Finding the distances to a query point#

We can also find the distances to a new “test” or “query” city:

# Let's find a city that's closest to the a query city
query_point = [[-80, 25]]

dists = euclidean_distances(X_cities, query_point)
dists[0:10]

array([[58.85545875],
       [63.80062924],
       [49.30530902],
       [49.01473536],
       [48.60495488],
       [39.96834506],
       [32.92852376],
       [29.53520104],
       [29.52881619],
       [27.84679073]])

# The query point is closest to
print(
    "The query point %s is closest to the city with index %d and the distance between them is: %0.4f"
    % (query_point, np.argmin(dists), dists[np.argmin(dists)])
)

The query point [[-80, 25]] is closest to the city with index 72 and the distance between them is: 0.7982

\(k\)-Nearest Neighbours (\(k\)-NNs) [video]#

small_cities = cities_df.sample(30, random_state=90)
one_city = small_cities.sample(1, random_state=44)
small_train_df = pd.concat([small_cities, one_city]).drop_duplicates(keep=False)

X_small_cities = small_train_df.drop(columns=["country"]).to_numpy()
y_small_cities = small_train_df["country"].to_numpy()
test_point = one_city[["longitude", "latitude"]].to_numpy()

plot_train_test_points(
    X_small_cities,
    y_small_cities,
    test_point,
    class_names=["Canada", "USA"],
    test_format="circle",
)

../_images/985c22f6704857061aaa1b1108a1440e0e7da4e44f448b009baaab88b3640953.png

Given a new data point, predict the class of the data point by finding the “closest” data point in the training set, i.e., by finding its “nearest neighbour” or majority vote of nearest neighbours.

Suppose we want to predict the class of the black point.

An intuitive way to do this is predict the same label as the “closest” point (\(k = 1\)) (1-nearest neighbour)
We would predict a target of USA in this case.

plot_knn_clf(
    X_small_cities,
    y_small_cities,
    test_point,
    n_neighbors=1,
    class_names=["Canada", "USA"],
    test_format="circle",
)

n_neighbors 1

../_images/252e319e4328134537af378ff4f1a865659167e52c15517ffd4464ebdca349ff.png

How about using \(k > 1\) to get a more robust estimate?

For example, we could also use the 3 closest points (k = 3) and let them vote on the correct class.
The Canada class would win in this case.

plot_knn_clf(
    X_small_cities,
    y_small_cities,
    test_point,
    n_neighbors=3,
    class_names=["Canada", "USA"],
    test_format="circle",
)

n_neighbors 3

../_images/f8540bb8a6c31fec5cb2f21bc21bc74cc54ad3750cc1d1d70ec2500f653f8f23.png

from sklearn.neighbors import KNeighborsClassifier

k_values = [1, 3]

for k in k_values:
    neigh = KNeighborsClassifier(n_neighbors=k)
    neigh.fit(X_small_cities, y_small_cities)
    print(
        "Prediction of the black dot with %d neighbours: %s"
        % (k, neigh.predict(test_point))
    )

Prediction of the black dot with 1 neighbours: ['USA']
Prediction of the black dot with 3 neighbours: ['Canada']

Choosing `n_neighbors`#

The primary hyperparameter of the model is n_neighbors (\(k\)) which decides how many neighbours should vote during prediction?
What happens when we play around with n_neighbors?
Are we more likely to overfit with a low n_neighbors or a high n_neighbors?
Let’s examine the effect of the hyperparameter on our cities data.

X = cities_df.drop(columns=["country"])
y = cities_df["country"]

# split into train and test sets
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.1, random_state=123
)

k = 1
knn1 = KNeighborsClassifier(n_neighbors=k)
scores = cross_validate(knn1, X_train, y_train, return_train_score=True)
pd.DataFrame(scores)

	fit_time	score_time	test_score	train_score
0	0.001642	0.003307	0.710526	1.0
1	0.001039	0.001988	0.684211	1.0
2	0.000949	0.001893	0.842105	1.0
3	0.000971	0.001885	0.702703	1.0
4	0.000897	0.001851	0.837838	1.0

k = 100
knn100 = KNeighborsClassifier(n_neighbors=k)
scores = cross_validate(knn100, X_train, y_train, return_train_score=True)
pd.DataFrame(scores)

	fit_time	score_time	test_score	train_score
0	0.000994	0.054542	0.605263	0.600000
1	0.001111	0.002233	0.605263	0.600000
2	0.000808	0.002116	0.605263	0.600000
3	0.000854	0.002164	0.594595	0.602649
4	0.000793	0.002085	0.594595	0.602649

def f(n_neighbors=1):
    results = {}
    knn = KNeighborsClassifier(n_neighbors=n_neighbors)
    scores = cross_validate(knn, X_train, y_train, return_train_score=True)
    results["n_neighbours"] = [n_neighbors]
    results["mean_train_score"] = [round(scores["train_score"].mean(), 3)]
    results["mean_valid_score"] = [round(scores["test_score"].mean(), 3)]
    return(pd.DataFrame(results))

n_neighbors_selector = pn.widgets.IntSlider(name='n_neighbors', start=1, end=10, value=1)
interact(f, n_neighbors=n_neighbors_selector).embed(max_opts=20)

# interactive(
#     f,
#     n_neighbors=widgets.IntSlider(min=1, max=101, step=5, value=1),
# )

plot_knn_decision_boundaries(X_train, y_train, k_values=[1, 11, 100])

../_images/d59e08190b8f7e2c9a4c1ef11d021d0ec1c90ac7366bc8c19973227b01aaa9c0.png

How to choose `n_neighbors`?#

n_neighbors is a hyperparameter
We can use hyperparameter optimization to choose n_neighbors.

results_dict = {
    "n_neighbors": [],
    "mean_train_score": [],
    "mean_cv_score": [],
    "std_cv_score": [],
    "std_train_score": [],
}
param_grid = {"n_neighbors": np.arange(1, 50, 5)}

for k in param_grid["n_neighbors"]:
    knn = KNeighborsClassifier(n_neighbors=k)
    scores = cross_validate(knn, X_train, y_train, return_train_score=True)
    results_dict["n_neighbors"].append(k)

    results_dict["mean_cv_score"].append(np.mean(scores["test_score"]))
    results_dict["mean_train_score"].append(np.mean(scores["train_score"]))
    results_dict["std_cv_score"].append(scores["test_score"].std())
    results_dict["std_train_score"].append(scores["train_score"].std())

results_df = pd.DataFrame(results_dict)

results_df = results_df.set_index("n_neighbors")
results_df

	mean_train_score	mean_cv_score	std_cv_score	std_train_score
n_neighbors
1	1.000000	0.755477	0.069530	0.000000
6	0.831135	0.792603	0.046020	0.013433
11	0.819152	0.802987	0.041129	0.011336
16	0.801863	0.782219	0.074141	0.008735
21	0.777934	0.766430	0.062792	0.016944
26	0.755364	0.723613	0.061937	0.025910
31	0.743391	0.707681	0.057646	0.030408
36	0.728777	0.707681	0.064452	0.021305
41	0.706128	0.681223	0.061241	0.018310
46	0.694155	0.660171	0.093390	0.018178

results_df[["mean_train_score", "mean_cv_score"]].plot();

../_images/d70cae87fba7c3b4eff2d6f8b91678468d8204ca43b234128c3086aafa2ab18a.png

best_n_neighbours = results_df.idxmax()["mean_cv_score"]
best_n_neighbours

Let’s try our best model on test data.

knn = KNeighborsClassifier(n_neighbors=best_n_neighbours)
knn.fit(X_train, y_train)
print("Test accuracy: %0.3f" % (knn.score(X_test, y_test)))

Test accuracy: 0.905

Seems like we got lucky with the test set here.

❓❓ Questions for you#

(iClicker) Exercise 3.1#

iClicker cloud join link: https://join.iclicker.com/DAZZ

Select all of the following statements which are TRUE.

(A) Analogy-based models find examples from the test set that are most similar to the query example we are predicting.
(B) Euclidean distance will always have a non-negative value.
(C) With \(k\)-NN, setting the hyperparameter \(k\) to larger values typically reduces training error.
(D) Similar to decision trees, \(k\)-NNs finds a small set of good features.
(E) In \(k\)-NN, with \(k > 1\), the classification of the closest neighbour to the test example always contributes the most to the prediction.

V’s Solutions!

B

Break (5 min)#

More on \(k\)-NNs [video]#

Other useful arguments of `KNeighborsClassifier`#

weights \(\rightarrow\) When predicting label, you can assign higher weight to the examples which are closer to the query example.
Exercise for you: Play around with this argument. Do you get a better validation score?

Regression with \(k\)-nearest neighbours (\(k\)-NNs)#

Can we solve regression problems with \(k\)-nearest neighbours algorithm?
In \(k\)-NN regression we take the average of the \(k\)-nearest neighbours.
We can also have weighted regression.

See an example of regression in the lecture notes.

mglearn.plots.plot_knn_regression(n_neighbors=1)

../_images/5b5168cdea3915e8cb4b49d944db75b060ebac38228e935a5d55c5a58bdb452d.png

mglearn.plots.plot_knn_regression(n_neighbors=3)

../_images/d7e720d45f381e2b90c7ad8b5abfb8bfc04fc48d04ca5728aa34ee21ee76d1a1.png

Pros of \(k\)-NNs for supervised learning#

Easy to understand, interpret.
Simple hyperparameter \(k\) (n_neighbors) controlling the fundamental tradeoff.
Can learn very complex functions given enough data.
Lazy learning: Takes no time to fit

Cons of \(k\)-NNs for supervised learning#

Can be potentially be VERY slow during prediction time, especially when the training set is very large.
Often not that great test accuracy compared to the modern approaches.
It does not work well on datasets with many features or where most feature values are 0 most of the time (sparse datasets).

Attention

For regular \(k\)-NN for supervised learning (not with sparse matrices), you should scale your features. We’ll be looking into it soon.

(Optional) Parametric vs non parametric#

You might see a lot of definitions of these terms.
A simple way to think about this is:
- do you need to store at least \(O(n)\) worth of stuff to make predictions? If so, it’s non-parametric.
Non-parametric example: \(k\)-NN is a classic example of non-parametric models.
Parametric example: decision stump
If you want to know more about this, find some reading material here, here, and here.
By the way, the terms “parametric” and “non-paramteric” are often used differently by statisticians, see here for more…

Note

\(\mathcal{O}(n)\) is referred to as big \(\mathcal{O}\) notation. It tells you how fast an algorithm is or how much storage space it requires. For example, in simple terms, if you have \(n\) examples and you need to store them all you can say that the algorithm requires \(\mathcal{O}(n)\) worth of stuff.

Curse of dimensionality#

Affects all learners but especially bad for nearest-neighbour.
\(k\)-NN usually works well when the number of dimensions \(d\) is small but things fall apart quickly as \(d\) goes up.
If there are many irrelevant attributes, \(k\)-NN is hopelessly confused because all of them contribute to finding similarity between examples.
With enough irrelevant attributes the accidental similarity swamps out meaningful similarity and \(k\)-NN is no better than random guessing.

from sklearn.datasets import make_classification

nfeats_accuracy = {"nfeats": [], "dummy_valid_accuracy": [], "KNN_valid_accuracy": []}
for n_feats in range(4, 2000, 100):
    X, y = make_classification(n_samples=2000, n_features=n_feats, n_classes=2)
    X_train, X_test, y_train, y_test = train_test_split(
        X, y, test_size=0.2, random_state=123
    )
    dummy = DummyClassifier(strategy="most_frequent")
    dummy_scores = cross_validate(dummy, X_train, y_train, return_train_score=True)

    knn = KNeighborsClassifier()
    scores = cross_validate(knn, X_train, y_train, return_train_score=True)
    nfeats_accuracy["nfeats"].append(n_feats)
    nfeats_accuracy["KNN_valid_accuracy"].append(np.mean(scores["test_score"]))
    nfeats_accuracy["dummy_valid_accuracy"].append(np.mean(dummy_scores["test_score"]))

pd.DataFrame(nfeats_accuracy)

	nfeats	dummy_valid_accuracy	KNN_valid_accuracy
0	4	0.508125	0.893750
1	104	0.503125	0.775000
2	204	0.510625	0.745000
3	304	0.508125	0.630625
4	404	0.499375	0.673750
5	504	0.500625	0.649375
6	604	0.502500	0.656875
7	704	0.511875	0.588125
8	804	0.506250	0.591250
9	904	0.502500	0.587500
10	1004	0.503750	0.615000
11	1104	0.507500	0.611875
12	1204	0.499375	0.612500
13	1304	0.501250	0.593750
14	1404	0.500000	0.550000
15	1504	0.501875	0.565000
16	1604	0.511250	0.612500
17	1704	0.511875	0.586875
18	1804	0.508125	0.603125
19	1904	0.503750	0.611250

Support Vector Machines (SVMs) with RBF kernel [video]#

Very high-level overview
Our goals here are
- Use scikit-learn’s SVM model.
- Broadly explain the notion of support vectors.
- Broadly explain the similarities and differences between \(k\)-NNs and SVM RBFs.
- Explain how C and gamma hyperparameters control the fundamental tradeoff.

(Optional) RBF stands for radial basis functions. We won’t go into what it means in this video. Refer to this video if you want to know more.

Overview#

Another popular similarity-based algorithm is Support Vector Machines with RBF Kernel (SVM RBFs)
Superficially, SVM RBFs are more like weighted \(k\)-NNs.
- The decision boundary is defined by a set of positive and negative examples and their weights together with their similarity measure.
- A test example is labeled positive if on average it looks more like positive examples than the negative examples.

The primary difference between \(k\)-NNs and SVM RBFs is that
- Unlike \(k\)-NNs, SVM RBFs only remember the key examples (support vectors).
- SVMs use a different similarity metric which is called a “kernel”. A popular kernel is Radial Basis Functions (RBFs)
- They usually perform better than \(k\)-NNs!

Let’s explore SVM RBFs#

Let’s try SVMs on the cities dataset.

mglearn.discrete_scatter(X_cities.iloc[:, 0], X_cities.iloc[:, 1], y_cities)
plt.xlabel("longitude")
plt.ylabel("latitude")
plt.legend(loc=1);

../_images/c5e2a25b2961fe48aca3d5e043caee4a9b71f3cb4231176b2ea72e3e544ee678.png

X_train, X_test, y_train, y_test = train_test_split(
    X_cities, y_cities, test_size=0.2, random_state=123
)

knn = KNeighborsClassifier(n_neighbors=best_n_neighbours)
scores = cross_validate(knn, X_train, y_train, return_train_score=True)
print("Mean validation score %0.3f" % (np.mean(scores["test_score"])))
pd.DataFrame(scores)

Mean validation score 0.803

	fit_time	score_time	test_score	train_score
0	0.002949	0.004925	0.794118	0.819549
1	0.000957	0.001959	0.764706	0.819549
2	0.000978	0.001963	0.727273	0.850746
3	0.000903	0.001909	0.787879	0.828358
4	0.000822	0.001737	0.939394	0.783582

from sklearn.svm import SVC

svm = SVC(gamma=0.01)  # Ignore gamma for now
scores = cross_validate(svm, X_train, y_train, return_train_score=True)
print("Mean validation score %0.3f" % (np.mean(scores["test_score"])))
pd.DataFrame(scores)

Mean validation score 0.820

	fit_time	score_time	test_score	train_score
0	0.003523	0.001714	0.823529	0.842105
1	0.001296	0.000831	0.823529	0.842105
2	0.001290	0.000809	0.727273	0.858209
3	0.001253	0.000785	0.787879	0.843284
4	0.001286	0.000872	0.939394	0.805970

Decision boundary of SVMs#

We can think of SVM with RBF kernel as “smooth KNN”.

fig, axes = plt.subplots(1, 2, figsize=(16, 5))

for clf, ax in zip([knn, svm], axes):
    clf.fit(X_train, y_train)
    mglearn.plots.plot_2d_separator(
        clf, X_train.to_numpy(), fill=True, eps=0.5, ax=ax, alpha=0.4
    )
    mglearn.discrete_scatter(X_train.iloc[:, 0], X_train.iloc[:, 1], y_train, ax=ax)
    ax.set_title(clf)
    ax.set_xlabel("longitude")
    ax.set_ylabel("latitude")

../_images/80914916627a953716e7695f0d113e2969192b233b312e5d4b3f681defcb9a3c.png

Support vectors#

Each training example either is or isn’t a “support vector”.
- This gets decided during fit.
Main insight: the decision boundary only depends on the support vectors.
Let’s look at the support vectors.

from sklearn.datasets import make_blobs

n = 20
n_classes = 2
X_toy, y_toy = make_blobs(
    n_samples=n, centers=n_classes, random_state=300
)  # Let's generate some fake data

mglearn.discrete_scatter(X_toy[:, 0], X_toy[:, 1], y_toy)
plt.xlabel("Feature 0")
plt.ylabel("Feature 1")
svm = SVC(kernel="rbf", C=10, gamma=0.1).fit(X_toy, y_toy)
mglearn.plots.plot_2d_separator(svm, X_toy, fill=True, eps=0.5, alpha=0.4)

../_images/3bd95d39e5437372c5ad23aa003bd3ea7f72abb4575fad0dede4f55fba13bf22.png

svm.support_

array([ 3,  8,  9, 14, 19,  1,  4,  6, 17], dtype=int32)

plot_support_vectors(svm, X_toy, y_toy)

../_images/98c512ed64d4c5e3ac2015f8b5fafb4d2f9b2621913a901f2d3e31b920001f40.png

The support vectors are the bigger points in the plot above.

Hyperparameters of SVM#

Key hyperparameters of rbf SVM are
- gamma
- C
We are not equipped to understand the meaning of these parameters at this point but you are expected to describe their relation to the fundamental tradeoff.

See scikit-learn’s explanation of RBF SVM parameters.

Relation of `gamma` and the fundamental trade-off#

gamma controls the complexity (fundamental trade-off), just like other hyperparameters we’ve seen.
- larger gamma \(\rightarrow\) more complex
- smaller gamma \(\rightarrow\) less complex

gamma = [0.001, 0.01, 0.1, 1.0, 10.0]
plot_svc_gamma(
    gamma,
    X_train.to_numpy(),
    y_train.to_numpy(),
    x_label="longitude",
    y_label="latitude",
)

../_images/1cc2389701fd77688eff7a9f7f09a4882427fcdd94634d7d8cce5bfafdfc8302.png

Relation of `C` and the fundamental trade-off#

C also affects the fundamental tradeoff
- larger C \(\rightarrow\) more complex
- smaller C \(\rightarrow\) less complex

C = [0.1, 1.0, 100.0, 1000.0, 100000.0]
plot_svc_C(
    C, X_train.to_numpy(), y_train.to_numpy(), x_label="longitude", y_label="latitude"
)

../_images/4ac0c6666ded29abdf4cc8cf3a3dfbeca17d6b3541a89a319434192c604a4d8d.png

Search over multiple hyperparameters#

So far you have seen how to carry out search over a hyperparameter
In the above case the best training error is achieved by the most complex model (large gamma, large C).
Best validation error requires a hyperparameter search to balance the fundamental tradeoff.
- In general we can’t search them one at a time.
- More on this next week. But if you cannot wait till then, you may look up the following:
  - sklearn.model_selection.GridSearchCV
  - sklearn.model_selection.RandomizedSearchCV

SVM Regressor#

Similar to KNNs, you can use SVMs for regression problems as well.
See sklearn.svm.SVR for more details.

❓❓ Questions for you#

(iClicker) Exercise 3.2#

iClicker cloud join link: https://join.iclicker.com/DAZZ

Select all of the following statements which are TRUE.

(A) \(k\)-NN may perform poorly in high-dimensional space (say, d > 1000).
(B) In sklearn’s SVC classifier, large values of gamma tend to result in higher training score but probably lower validation score.
(C) If we increase both gamma and C, we can’t be certain if the model becomes more complex or less complex.

V’s Solutions!

A, B

Summary#

We have KNNs and SVMs as new supervised learning techniques in our toolbox.
These are analogy-based learners and the idea is to assign nearby points the same label.
Unlike decision trees, all features are equally important.
Both can be used for classification or regression (much like the other methods we’ve seen).

Coming up:#

Lingering questions:

Are we ready to do machine learning on real-world datasets?
What would happen if we use \(k\)-NNs or SVM RBFs on the spotify dataset from hw1?
What happens if we have missing values in our data?
What do we do if we have features with categories or string values?

Lecture 3: k-Nearest Neighbours and SVM RBFs

Contents

Lecture 3: \(k\)-Nearest Neighbours and SVM RBFs#

Lecture plan#

Imports, announcements, and LOs#

Imports#

Learning outcomes#

Quick recap#

Motivation and distances [video]#

Analogy-based models#

Analogy-based algorithms in practice#

General idea of \(k\)-nearest neighbours algorithm#

Geometric view of tabular data and dimensions#

Dimensions in ML problems#

Feature vectors#

Similarity between examples#

Distance between feature vectors#

Euclidean distance#

Finding the nearest neighbour#

Question#

Finding the distances to a query point#

\(k\)-Nearest Neighbours (\(k\)-NNs) [video]#

Choosing n_neighbors#

How to choose n_neighbors?#

❓❓ Questions for you#

(iClicker) Exercise 3.1#

Break (5 min)#

More on \(k\)-NNs [video]#

Other useful arguments of KNeighborsClassifier#

Regression with \(k\)-nearest neighbours (\(k\)-NNs)#

Pros of \(k\)-NNs for supervised learning#

Cons of \(k\)-NNs for supervised learning#

(Optional) Parametric vs non parametric#

Curse of dimensionality#

Support Vector Machines (SVMs) with RBF kernel [video]#

Overview#

Let’s explore SVM RBFs#

Decision boundary of SVMs#

Support vectors#

Hyperparameters of SVM#

Relation of gamma and the fundamental trade-off#

Relation of C and the fundamental trade-off#

Search over multiple hyperparameters#

SVM Regressor#

❓❓ Questions for you#

(iClicker) Exercise 3.2#

More practice questions#

Summary#

Coming up:#

Choosing `n_neighbors`#

How to choose `n_neighbors`?#

Other useful arguments of `KNeighborsClassifier`#

Relation of `gamma` and the fundamental trade-off#

Relation of `C` and the fundamental trade-off#