Classes 20–23 · 25 · Test 4 · Final Q11–Q13

Classification
& Clustering

K-means clustering finds centroids unsupervised. Those centroids define a separating hyperplane. Confusion matrices, ROC curves, and logistic probability evaluate and refine the classifier.

K-Means Clustering

K-Means Algorithm

Method 1 (initialize partitions): 1. Randomly initialize k partitions 2. While not converged: a. For each partition i: compute centroid ⃗gᵢ (observation nearest to mean) b. For each observation: assign to nearest centroid Method 2 (initialize centroids): 1. Randomly select k centroids ⃗gᵢ from data 2. While not converged: a. For each observation: assign to nearest centroid b. For each cluster: compute new centroid

Both methods converge to the same fixed point. The centroid is the member of the cluster nearest to the cluster mean (not the mean itself, since the mean may not be a data point).

Separating Hyperplane from Centroids

Hyperplane Between Two Centroids

Given: centroids ⃗g₁ (class +1) and ⃗g₂ (class −1) Direction vector: ⃗m = ⃗g₁ − ⃗g₂ Midpoint: ⃗h = (⃗g₁ + ⃗g₂)/2 Bias scalar: b = −⃗hᵀ⃗m (so that ⃗m·⃗h + b = 0) General hyperplane H: ⃗mᵀ⃗x + b ≥ 0 → class +1 ⃗mᵀ⃗x + b < 0 → class −1

Any point equidistant from both centroids lies on the hyperplane. This is derived by expanding $\|\vec{t}-\vec{g}_1\|^2 = \|\vec{t}-\vec{g}_2\|^2$.

Unit Normal Form

$$\vec{n} = \frac{\vec{m}}{\|\vec{m}\|} \qquad c = \frac{b}{\|\vec{m}\|}$$ Unit hyperplane H: ⃗nᵀ⃗x + c = 0 Signed distance of ⃗a to H: d = ⃗nᵀ⃗a + c

The unit normal form uses a vector of magnitude 1. The signed distance $d = \vec{n}^T\vec{a} + c$ is the perpendicular distance from the hyperplane: positive on the +1 side, negative on the $-1$ side.

Logistic Probability

Logistic (Sigmoid) Function

$$p(\vec{a}) = \frac{1}{1+e^{-(\vec{n}^T\vec{a}+c)}} = \frac{1}{1+e^{-d}}$$

Maps the signed distance $d$ to a probability in $(0,1)$. When $d = 0$ (on the hyperplane): $p = 0.5$. When $d \to +\infty$: $p \to 1$. When $d \to -\infty$: $p \to 0$.

To use with general hyperplane (⃗m, b): first convert to unit form ⃗n = ⃗m/‖⃗m‖, c = b/‖⃗m‖, then compute d = ⃗n·⃗a + c, then p = 1/(1+e⁻ᵈ).

Odds and Probability

$$s = \frac{p}{1-p} \qquad p = \frac{s}{1+s}$$

Odds $s$ is the ratio of the probability of the event to the probability of the non-event.

Confusion Matrix

Confusion Matrix Structure

| Classified +1 | Classified −1 | Label +1 | TP | FN | P = TP+FN Label −1 | FP | TN | N = FP+TN TPR (sensitivity) = TP/P TNR (specificity) = TN/N FPR (Type I rate) = FP/N FNR (Type II rate) = FN/P ACC = TP + TN (total correct count)

For threshold $\theta$: classify as $+1$ if score $z_i \geq \theta$, else $-1$. Work through each observation: compare label vs. classification to find TP/FP/TN/FN.

ROC Curve and AUC

ROC Vector

$$\vec{v} = \begin{bmatrix}\text{FPR} \\ \text{TPR}\end{bmatrix} = \begin{bmatrix}1 - \text{TNR} \\ \text{TPR}\end{bmatrix}$$

One ROC point per threshold $\theta$. Plot TPR vs. FPR as $\theta$ varies. Ideal classifier: top-left corner (FPR=0, TPR=1). Random classifier: diagonal line. AUC = area under the ROC curve $\in [0,1]$.

Practice Problems

W26 Test 4 · Q1 $\vec{n}_1 = [-0.667, 0.333, 0.667]^T$, $c_1 = -1$. Classify $\vec{a}_1=[5,0,1]$ and $\vec{a}_2=[1,2,5]$. +
Worked Answer
$d = \vec{n}^T\vec{a} + c$:
$\vec{a}_1$: $5(-0.667)+0(0.333)+1(0.667)-1 = -3.335+0.667-1 = -3.668 < 0$ → negative
$\vec{a}_2$: $1(-0.667)+2(0.333)+5(0.667)-1 = -0.667+0.666+3.335-1 = 2.334 > 0$ → positive
W26 Test 4 · Q2 Scores $z_i$ and labels $y_i$ given below. With $\theta=2$, find the confusion matrix. Scores: $-3,-2.5,-2,-1,0.5,1,2.5,3,3.5,5,5.5,6$. Labels: $-1,+1,-1,-1,-1,+1,+1,+1,-1,+1,+1,+1$. +
Worked Answer
Classified $+1$ ($z \geq 2$): $2.5,3,3.5,5,5.5,6$ with labels $+1,+1,-1,+1,+1,+1$ → TP=5, FP=1
Classified $-1$ ($z < 2$): $-3,-2.5,-2,-1,0.5,1$ with labels $-1,+1,-1,-1,-1,+1$ → FN=2, TN=4

$C_2 = \begin{bmatrix}5&2\\1&4\end{bmatrix}$
W26 Test 4 · Q6 $\vec{m}_6 = [-4,3]^T$, $b_6 = 7$, $\vec{a}_6 = [2,1]$. Find $p(\vec{a}_6)$. +
Worked Answer
$\|\vec{m}\| = \sqrt{16+9} = 5$. Unit form: $\vec{n} = [-0.8, 0.6]^T$, $c = 7/5 = 1.4$.
$d = 2(-0.8)+1(0.6)+1.4 = -1.6+0.6+1.4 = 0.4$
$p = 1/(1+e^{-0.4}) \approx 1/1.670 \approx \mathbf{0.60}$
2025 Final · Q11 Centroids $\vec{g}_1=[2,3,2]^T$, $\vec{g}_2=[4,2,4]^T$. Find bias scalar $c_{11}$ for the unit-normal hyperplane. +
Worked Answer
$\vec{m} = \vec{g}_1-\vec{g}_2 = [-2,1,-2]^T$, $\|\vec{m}\| = \sqrt{4+1+4} = 3$
$\vec{h} = (\vec{g}_1+\vec{g}_2)/2 = [3, 2.5, 3]^T$
$b = -\vec{h}^T\vec{m} = -(3(-2)+2.5(1)+3(-2)) = -(-6+2.5-6) = 9.5$
$c = b/\|\vec{m}\| = 9.5/3 \approx \mathbf{3.167}$ (Answer: c)
2025 Final · Q12 $\vec{m}_{12}=[4,-3]^T$, $b_{12}=-5$, $\vec{x}_{12}=[2,2]^T$. Find $p(\vec{x}_{12})$. +
Worked Answer
$\|\vec{m}\| = 5$, $\vec{n} = [0.8,-0.6]^T$, $c = -5/5 = -1$
$d = 2(0.8)+2(-0.6)-1 = 1.6-1.2-1 = -0.6$
$p = 1/(1+e^{0.6}) \approx 1/2.822 \approx \mathbf{0.35}$ (Answer: c)