<!--
Abstract:

CS 461
Introduction to Deep Learning
Lecture 05
-->

# CS 461 - Lecture 05

## Machine Learning Principles

Bernhard Firner

2025-09-22

---

## Reading

* K-Nearest Neighbors
* Recommended reading
  * Machine Learning: A Probabilistic Perspective by Murphy
    * Section 1.4.1 - 1.4.4 for parametric vs. non-parametric discussion
    * Section 14.7.2 - 14.7.3 for another perspective on KNN
    * Section 25.1.2 for evaluation of cluster methods
  * Machine Learning: The Art and Science of Algorithms that Make Sense of Data by Flach
    * Chapter 8 (distance-based models)

---

## Review: Penguins

---

## Review: Penguins

---

---

## Decision Trees

---

## Printing the tree

```python
def print_decision_tree(root, feature_names, name=1):
    """Print the current root and all of its children.
    Returns the numbers of nodes printed.
    """
    if root.lchild is not None:
        # Get the split information to print
        feature_name = feature_names[root.feature_index]
        isfloat = True
        try:
            # Numerical value
            number = float(root.boundary)
        except ValueError:
            isfloat = False
        if isfloat:
            comp_str_l = "<"
            comp_str_r = ">="
        else:
            comp_str_l = "=="
            comp_str_r = "!="
        lname = name + 1
        print(f'{name} -> {lname} [label="{feature_name} {comp_str_l} {root.boundary}"];')
        found_children = print_decision_tree(root.lchild, feature_names, lname)
        rname = name + found_children + 1
        print(f'{name} -> {rname} [label="{feature_name} {comp_str_r} {root.boundary}"];')
        found_children = found_children + print_decision_tree(root.rchild, feature_names, rname)
        # Don't give this node a name in the graph
        print(f'{name} [label = ""]')
        return found_children + 1
    else:
        # This is a leaf node.
        # Print out the population information.
        print(f'{name} [label = {root.class_name}];')
        return 1
```

-v-

<pre>
digraph {
1 -> 2 [label="bill_length_mm < 40.9"];
2 [label = Adelie];
1 -> 3 [label="bill_length_mm >= 40.9"];
3 -> 4 [label="bill_depth_mm < 16.4"];
4 [label = Gentoo];
3 -> 5 [label="bill_depth_mm >= 16.4"];
5 -> 6 [label="island == Dream"];
6 -> 7 [label="bill_length_mm < 45.2"];
7 -> 8 [label="sex == female"];
8 -> 9 [label="bill_depth_mm < 18.5"];
9 [label = Chinstrap];
8 -> 10 [label="bill_depth_mm >= 18.5"];
10 [label = Adelie];
8 [label = ""]
7 -> 11 [label="sex != female"];
11 [label = Adelie];
7 [label = ""]
6 -> 12 [label="bill_length_mm >= 45.2"];
12 [label = Chinstrap];
6 [label = ""]
5 -> 13 [label="island != Dream"];
13 -> 14 [label="flipper_length_mm < 219.0"];
14 [label = Adelie];
13 -> 15 [label="flipper_length_mm >= 219.0"];
15 [label = Gentoo];
13 [label = ""]
5 [label = ""]
3 [label = ""]
1 [label = ""]
}
</pre>

-v-

## Visualize with dot

* *dot* is part of [graphviz](https://graphviz.org)
* Very useful plotting tools

<pre>
dot -Tpng example_decision_tree.dot -o example_decision_tree.png
</pre>

---

## Scoring function

```python
import numpy as np

def gini_impurity(classlist):
    # We can't test with 0 instances
    if len(classlist) == 0:
        return 0.

# Get the unique classes and the counts for each class
    classes, counts = np.unique(classlist, return_counts=True)
    p_hats = counts/len(classlist)
    gini = 1.0 - np.sum(p_hats**2)
    # Using the square root of gini impurity
    return np.sqrt(gini)
```

---

## Splitting

* Start with a dataset, $D$
  * It could be a subset of the full data
  * Has $n$ columns/features, $x_1$ ... $x_n$
* Loop over all categories, $x_i$
  * Loop over each row in $x_i$
    * $x_{ij}$
  * Remember if $x_{ij}$ is the best place to split so far

---

## Parametric Vs Non-Parametric

* Why did we jump from regression to trees?
  * And now we're going to something called K-nearest neighbors!
* The regression-style solutions are `parametric`
  * Meaning that they come with a set of parameters that we provided
* The decision tree (and today's techniques) determine their parameters from the data

---

## Nearest Neighbors

* The conceptually simplest version of a `non-parametric` model is this:
  * For any test input, find the nearest sample in our dataset with a class
  * Assign that class label to the test input
* What are the parameters?
  * The entire dataset

---

## Exemplar Techniques

* The nearest neighbor solution is an `exemplar` technique
  * Meaning that our dataset examples stick around in the model
* Opposite of regression models, where only the statistics stuck around

---

## Let's pause

* You may know that a trained neural network can be examined to deduce its training data
  * Large generative models have a tendency to reproduce some training data
    * Both text or images
* Why does this happen?
* And what does it say about exemplar models?

---

## Information Retention

* An exemplar model is, in some ways, greedy
  * Attempts to hold on to all training data
* A parametric model let's it go, trusting in the statistics
* Deep neural networks are huge
  * Plenty of capacity to "memorize" some inputs
  * One could argue that makes them a hybrid approach
    * Good? Bad? Or both?

---

## Why non-parametric?

* Back to trees and nearest neighbors
* Non-parametric models are useful when describing our data is difficult
* Makes sense; if $x_3$ is more similar to $x_1$ than to $x_2$, then it is likely the same thing as $x_1$

---

## Why not non-parametric?

* Very biased by the sampling of the dataset
  * e.g. if class A is undersampled, items will be under-assigned to it
* Untrustworthy near decision boundaries

</div>
<div class="col">
<img style="width: 95%" class="r-stretch" src="./figures/all_real_penguins_flipper_length_vs_body_mass.png" />

</div>
</div>

---

## Distances

* Using multiple distances is better
* But how do they mix?

---

## Euclidean Distance

* Clearly works well for continuous data
  * First need to normalize all inputs
  * This is like measuring each exemplar and unknown instance by their differences from the mean
* Not so good for labels
  * For example, islands, sex of a penguin
* Let's test it out on the continuous inputs first

---

## K-Nearest Neighbors

* Use bill_length_mm, bill_depth_mm, flipper_length_mm, body_mass_g
* Predict class
* Going to reserve 10% of penguins for testing
  * There are 333 filtered penguins, so 33 are reserved

---

## Build a Dataset

<pre>
$ head -n 1 filtered_penguins.csv > train_penguins.csv
$ head -n 1 filtered_penguins.csv > test_penguins.csv
$ tail -n +2 filtered_penguins.csv | shuf > temp_penguins.csv
$ head -n 33 temp_penguins.csv >> test_penguins.csv 
$ tail -n +34 temp_penguins.csv >> train_penguins.csv 
$ wc test_penguins.csv 
  34   34 1545 test_penguins.csv
$ wc train_penguins.csv 
  301   301 13330 train_penguins.csv
$ rm temp_penguins.csv
</pre>

---

## Code

```python
import sys
import numpy
import tree_funcs
train_records, column_names = tree_funcs.read_csv("train_penguins.csv")
test_records, column_names = tree_funcs.read_csv("test_penguins.csv")
#species,island,bill_length_mm,bill_depth_mm,flipper_length_mm,body_mass_g,sex,year
y = train_records[0]
X = numpy.array(train_records[2:6])

y_test = test_records[0]
X_test = numpy.array(test_records[2:6])

# Normalize with sample estimates from X
x_mean = numpy.mean(X)
x_variance = numpy.mean((X - x_mean)**2)
X = X - x_mean
X = X / x_variance

# Must normalize the test set using the training estimate
X_test = X_test - x_mean
X_test = X_test / x_variance

num_neighbors = int(sys.argv[1])

def euclideandistance(x, sample):
    return numpy.sqrt(numpy.sum((x - sample)**2))

def get_k_nearest(X, sample, k):
    distances = [euclideandistance(X[:,row], sample) for row in range(X.shape[1])]
    return numpy.argsort(distances)[:k]

def knn_classify(X, y, sample, k):
    k_nearest_idx = get_k_nearest(X, sample, k)

nearest_labels = [y[idx] for idx in k_nearest_idx]
    labels, counts = numpy.unique(nearest_labels, return_counts=True)
    best = labels[numpy.argmax(counts)]
    return best

# Let's get the statistics
classes, class_counts = numpy.unique(y, return_counts=True)

# Remember which indices belong to which class
class_idxs = [[], [], []]
for c_idx, c_name in enumerate(classes):
    for idx, y_name in enumerate(y_test):
        if c_name == y_name:
            class_idxs[c_idx].append(idx)

y_hat = [knn_classify(X, y, X_test[:,row], num_neighbors) for row in range(len(y_test))]

def class_match(a, b):
    return [i for i in range(len(a)) if a[i] == b[i]]

def class_match_mag(a, b):
    return len(class_match(a, b))

accuracy = class_match_mag(y_test, y_hat)/len(y_test)
print(f"Accuracy is {accuracy}")

print(f"Gini impurity is {tree_funcs.gini_impurity(y_hat)}")

confusion = []
# The columns of the confusion matrix is reality
for real_class in classes:
    # The row of the confusion matrix is the prediction
    for predicted_class in classes:
        total = 0
        for i in range(len(y_hat)):
            if y_hat[i] == predicted_class and y_test[i] == real_class:
                total += 1
        confusion.append(total)

true_positives = confusion[0] + confusion[4] + confusion[8]
false_positives = sum(confusion[1:4]) + sum(confusion[5:8])
precision = true_positives / (true_positives + false_positives)

# Print the confusion matrix
print("Raw confusion")
print(f"{len(y_test)}\t\t{classes[0]}\t{classes[1]}\t{classes[2]}")
print(f"{classes[0]}\t\t{confusion[0]}\t{confusion[1]}\t\t{confusion[2]}")
print(f"{classes[1]}\t{confusion[3]}\t{confusion[4]}\t\t{confusion[5]}")
print(f"{classes[2]}\t\t{confusion[6]}\t{confusion[7]}\t\t{confusion[8]}")
print("Percentage confusion")
print(f"{len(y_test)}\t\t{classes[0]}\t{classes[1]}\t{classes[2]}")
print(f"{classes[0]}\t\t{confusion[0]/len(y_test):.3f}\t{confusion[1]/len(y_test):.3f}\t\t{confusion[2]/len(y_test):.3f}")
print(f"{classes[1]}\t{confusion[3]/len(y_test):.3f}\t{confusion[4]/len(y_test):.3f}\t\t{confusion[5]/len(y_test):.3f}")
print(f"{classes[2]}\t\t{confusion[6]/len(y_test):.3f}\t{confusion[7]/len(y_test):.3f}\t\t{confusion[8]/len(y_test):.3f}")
print("The diagonal over the sum of each row is the recall")
print("The diagonal over the sum of each colum is the precision")
```

---

## Metrics

* We didn't talk about metrics for the decision tree because it was too good
* KNN is going to have some problems, so let's talk about them

---

## Rand Index

* $R = \frac{TP+TN}{TP+FP+FN+TN}$

---

## Impurity

* The decision tree metric

---

## Recall and Precision

* KNN is around 80% accurate
  * But is it better with some penguins than others?
* We need to start using recall and precision
* Recall: true positives / total class
* Precision: true positives / (true positives + false positives)

---

## Confusion Matrix at n=3

<table>
<tr><td>33</td><td>Adelie</td><td>Chinstrap</td><td>Gentoo</td></tr>
<tr><td>Adelie</td><td>15</td><td>0</td><td>1</td></tr>
<tr><td>Chinstrap</td><td>2</td><td>4</td><td>0</td></tr>
<tr><td>Gentoo</td><td>0</td><td>0</td><td>11</td></tr>
</table>

---

## With fractions

<table>
<tr><td>33</td><td>Adelie</td><td>Chinstrap</td><td>Gentoo</td></tr>
<tr><td>Adelie</td><td>0.455</td><td>0</td><td>0.03</td></tr>
<tr><td>Chinstrap</td><td>0.061</td><td>0.121</td><td>0</td></tr>
<tr><td>Gentoo</td><td>0</td><td>0</td><td>0.333</td></tr>
</table>

---

## Interpretation

* Precise with Chinstraps, but poor recall
* Perfect recall for Gentoo, very high precision
* Adelie good recall, precision is high

---

## KNN Comments

* This is an incredibly simple algorithm
  * We didn't even use the categorical data
  * Let's add those in!

---

## Categorical data

* Add in island and sex
* Set distance to 0 if they match, 1 otherwise
* Notice that this is equivalent to making a new column for each individual category
  * e.g. three columns for island:
    * Biscoe, Dream, and Torgersen
* Called a "one-hot" encoding

---

## With Categories

---

## The Curse of Dimensionality

* We obviously need enough samples to fill an area
  * Since we require neighbors
* However, with each feature we add a new dimension
  * Volume grows exponentially with the number of dimensions
  * Neighbors thus get farther away
    * Require an ever-increasing number of data points with increasing dimensions

---

## KNN Wrapup

* There are better ways to classify points
  * Trees, for example
* Also some variants
  * Instead of choosing a fixed number of neighbors, we could grow a bubble around a point
  * This is the balloon kernel density estimator
* We could also define a new distance metric based upon our labelled data points
  * This is large margin nearest neighbors

---

## Clustering on Unknown data

* But sometimes we get data that has no class information
* KNN and similar approaches require classes for the distance metric
* Clusters appear obvious to a human looking at a graph
  * Can an algorithm do the same?

---

## Unsupervised Clustering

* Problems where we want to group our data, but there is no training set
  * Meaning no labels, or $y$
* Unsupervised tasks are difficult because there is no obvious error metric
* However, there is more unlabelled data than labelled data in the world

---

## A Tree Approach

* Since we just worked on decision trees, is there a similar unsupervised idea?
* We know that leaf nodes should contain similar data
  * Let's group the closest data points into the same node
* Now we have one less node; repeat long enough, and all points will be in the tree

---

## Hierarchical agglomerative clustering

* Or `HAC`
* Start with all data points, $X$ in their own cluster
* Compute the closest pair of points and merge them
* Repeat until there is a single cluster
* Choose a cut height. These subtrees are the classes

---

## HAC Performance

* $O(N^2)$ time to compare all pairs of points
* $O(N)$ steps
  * but we can stay below $O(N^3)$ by storing previous comparisons in a priority queue
    * Only works for some distance metrics
* $O(N^3)$ if we use the average distances from cluster points
  * This is slow

---

## HAC Code

```python
import sys
import numpy
import tree_funcs

# One hot penguins has converted the categorical labels as follows::
# Biscoe    0 0 1
# Dream     0 1 0
# Torgersen 1 0 0
# Female    0 1
# Male      1 0
y = numpy.genfromtxt("one_hot_penguins.csv", dtype=str, skip_header=1, delimiter=',', usecols=(0,))
X = numpy.loadtxt("one_hot_penguins.csv", skiprows=1, delimiter=',', usecols=list(range(1, 10)))
#y = numpy.genfromtxt("tmp.csv", dtype=str, skip_header=1, delimiter=',', usecols=(0,))
#X = numpy.loadtxt("tmp.csv", skiprows=1, delimiter=',', usecols=list(range(1, 10)))

# Normalizing the categorical labels makes little sense, so we will live with the distances as they are

class Cluster:
    def __init__(self, left, right=None, indices=None):
        # Check if the input is a single number or a cluster
        # This supports Cluster initialization with lone numbers.
        if right is None:
            self.X = left
            # The height is 0
            self.height = 0
            self.indices = indices
        else:
            self.indices = left.indices + right.indices
            self.X = numpy.vstack((left.X, right.X))
            # The height is the average distance of the two sub-clusters
            self.height = left.averageDistance(right)
        self.lchild = left
        self.rchild = right

def len(self):
        return len(self.X)

def averageDistance(self, other):
        norm = (1/(self.len() + other.len()))
        dist_sum = 0
        for i in range(self.len()):
            for j in range(other.len()):
                dist_sum += numpy.sqrt(numpy.sum((self.X[i] - other.X[j])**2))
        return dist_sum * norm

clusters = [Cluster(x, None, [idx]) for idx, x in enumerate(X)]
print(f"Starting with {len(clusters)} leaf nodes.")

while len(clusters) > 1:
    min_dist = float('inf')
    min_pair = None
    for i in range(len(clusters)-1):
        for j in range(i+1, len(clusters)):
            dist = clusters[i].averageDistance(clusters[j])
            if dist < min_dist:
                min_dist = dist
                min_pair = (i, j)

# Remove the right cluster and replace the left cluster with the combined cluster
    left = clusters[min_pair[0]]
    right = clusters.pop(min_pair[1])
    clusters[min_pair[0]] = Cluster(left, right)
    print(f"There are now {len(clusters)} clusters")

# Let's get the statistics
classes, class_counts = numpy.unique(y, return_counts=True)

# Remember which indices belong to which class
class_idxs = [numpy.where(y == classes[idx]) for idx in range(3)]

# Check metrics for how much of each class was assigned to the same cluster
# Find the largest three clusters by breaking the largest of the root's two child nodes in half
if clusters[0].lchild.height > clusters[0].rchild.height:
    largest_three = [clusters[0].rchild, clusters[0].lchild.lchild, clusters[0].lchild.rchild]
else:
    largest_three = [clusters[0].lchild, clusters[0].rchild.lchild, clusters[0].lchild.rchild]

y_hat = ['none' for _ in range(len(y))]
for c_idx in range(3):
    cluster_indices = largest_three[c_idx].indices
    cluster_classes, cluster_counts = numpy.unique(y[cluster_indices], return_counts=True)
    majority_index = numpy.argmax(cluster_counts)

for idx in cluster_indices:
        y_hat[idx] = classes[majority_index]

accuracy = len(numpy.where(numpy.array(y_hat) == y)[0]) / len(y)
print(f"Accuracy is {accuracy}")
```

---

## Problems

* Very slow
* Now based on solid math
  * e.g. no model, non-parametric
  * Makes it harder to evaluate in an unsupervised setting

---

## Latent Variables

* Imagine if all of the features of a sample arise from a hidden variable
  * In this case, the life history of a penguin
* Those unknown variables are `latent variables`
  * The ones we see are `visible variables`
* Models that fit unseen variables are `latent variable models`

---

## Mixture Models

* If we use a mixture of distributions to represent our latent variables, we have a `mixture model`
* This is where we'll continue next class, introducing K-Means clustering

---

## K-Means Clustering

* Popular standard for unsupervised clustering
* What if we optimized for the compactness of the cluster?
  * This is K-means
  * Equivalent to maximizing the spread of cluster centroids
    * Intuitive, since clusters should be separated and compact

---

## K-Means Cost function

* We'll be minimizing the `distortion`, $J$
* $J(M,Z) = \sum_{n=1}{N}\lVert x_n - \mu_{z_n} \rVert^2 = \lVert X - ZM^T \rVert_{F}^2$
  * $X$ is the vector of points
  * $M$ holds the cluster centroids
  * $Z$ indicates which centroid a point belongs to
* We'll be back to our optimization tricks with the next topics