Key Terms

Three Features

• Income — annual income in thousands (₱)
• Age — years old
• Spending — monthly spending score (0-100)

Look at the table. Before any algorithm, can you spot which customers are similar? That's exactly what clustering will automate.

\begin{algorithm}
\caption{K-Means Clustering}
\begin{algorithmic}
\REQUIRE Dataset $X = \{x_1, \ldots, x_n\}$, number of clusters $K$
\STATE Initialize centroids $\mu_1, \ldots, \mu_K$ randomly from $X$
\REPEAT
    \FOR{each $x_i \in X$}
        \STATE $c_i \leftarrow \arg\min_j \|x_i - \mu_j\|^2$
    \ENDFOR
    \FOR{$j = 1$ \TO $K$}
        \STATE $\mu_j \leftarrow \frac{1}{|C_j|} \sum_{x_i \in C_j} x_i$
    \ENDFOR
\UNTIL{centroids do not change}
\end{algorithmic}
\end{algorithm}
                        

Objective Function

Minimize Within-Cluster Sum of Squares (WCSS):
J = Σ_k Σ_{i ∈ Ck} ||x_i − μ_k||²

• x_i = a data point
• μ_k = centroid of cluster k
• C_k = set of points in cluster k
• ||·||² = squared Euclidean distance

Steps

1. Scale all features to mean=0, std=1
2. Run KMeans(n_clusters=K) on scaled data
3. Each point gets a cluster label

Key Parameters

• n_clusters — number of clusters (K)
• n_init=10 — runs with different random starts
• random_state — seed for reproducibility

What is Inertia?

Sum of squared distances from each point to its assigned centroid. Think of it as "total cluster tightness" — lower = tighter, but it always decreases with more K (at K=8 every customer is its own cluster, inertia=0).

Pseudocode

1. For K = 1, 2, 3, …, 10:
2.    Run K-Means, record its inertia
3. Plot K vs inertia → find the "bend"

Step-by-Step: Calculate % Improvement

From K=3 to K=4, improvement drops from 44% to just 5%. That's the elbow → choose K=3.

What If There's No Clear Elbow?

Real data often has a smooth curve instead of a sharp bend. When this happens:

1. Don't rely on the elbow alone — use Silhouette Score (next slide) as a second opinion
2. Try the % improvement rule: stop when the drop is <10% of the previous drop
3. Consider domain knowledge — does K=4 make sense for your business? (e.g., 4 customer tiers)

Common Mistakes

• Picking K=1: Inertia is always highest at K=1 — that's just "no clustering"
• Picking K=N: Inertia is 0 when K = number of points (each point is its own cluster) — useless
• Ignoring the context: K=15 may have slightly better inertia than K=4, but can you actually explain 15 customer segments to a stakeholder?

Always combine Elbow + Silhouette + Business sense. No single metric gives you the "correct" K — clustering is exploratory, not a test with one right answer.

Pseudocode

1. For each K from 2 to 10: run K-Means
2. For each point: compute a (avg dist to own cluster) and b (avg dist to nearest other cluster)
3. Silhouette = average of all points' scores
4. Pick K with the highest silhouette

• a(i) — mean distance to points in your own cluster
• b(i) — mean distance to the nearest other cluster
• Range: −1 to +1 (higher = better)

If a=2 (avg distance within cluster) and b=5 (avg distance to nearest other cluster):
s = (5−2) / max(2,5) = 3/5 = 0.6 → reasonable structure.

Pseudocode

1. Group the DataFrame by cluster label
2. Compute mean of each feature per group
3. Look at the averages → name each group
4. Ask: "Can I explain this to a non-technical person?"

If you can't name it, the clustering may not be meaningful.

Why PCA?

PCA finds the directions along which your data spreads out the most (has the most variance). Think of choosing the best camera angle to photograph a 3D object in 2D — you lose some depth, but keep the most informative view.

• Variance = how much the data spreads along a direction
• PC1 captures the biggest spread, PC2 the second-biggest
• explained_variance_ratio_ tells how much info each component captures (e.g., 72% + 18% = 90% retained)

\begin{algorithm}
\caption{Agglomerative Clustering}
\begin{algorithmic}
\REQUIRE Dataset $X = \{x_1, \ldots, x_n\}$, linkage function $d$
\STATE Initialize each $x_i$ as its own cluster $C_i$
\WHILE{number of clusters $> 1$}
    \STATE $(C_a, C_b) \leftarrow \arg\min_{i \neq j} \, d(C_i, C_j)$
    \STATE Merge $C_a$ and $C_b$ into a single cluster
    \STATE Record merge distance (for dendrogram)
\ENDWHILE
\RETURN Dendrogram; cut at desired height for $K$ clusters
\end{algorithmic}
\end{algorithm}
                        

The dendrogram lets you visually choose K after fitting by cutting at a chosen height.

X-axis

Each leaf at the bottom is a data point (or sample). The order doesn't matter much — it's rearranged to avoid crossing lines.

Y-axis (Height)

The height where two branches merge = how dissimilar those clusters were. Higher merge = less similar. The tallest vertical line represents the biggest "jump" in dissimilarity.

Choosing K

Draw a horizontal cut line. The number of vertical lines it crosses = K. Tip: Cut where vertical lines are longest (biggest gap = most natural groupings).

Example from Previous Slide

Cut at height 4 → crosses 3 lines → K=3. Cut at height 2 → 5 clusters. Cut at height 7 → everything merges into 1.

Steps

1. Compute linkage matrix (merge history)
2. Plot dendrogram → visually pick K
3. Fit AgglomerativeClustering with chosen K

Two Libraries

• scipy — linkage + dendrogram
• sklearn — AgglomerativeClustering

RFM Features

• Recency — days since last transaction
• Frequency — number of transactions
• Monetary — total amount transacted

Two Parameters

• eps (ε) — radius of neighborhood
• min_samples — minimum points to form a dense region

\begin{algorithm}
\caption{DBSCAN}
\begin{algorithmic}
\REQUIRE Dataset $X$, radius $\varepsilon$, minimum points $m$
\FOR{each unvisited point $x_i \in X$}
    \STATE Mark $x_i$ as visited
    \STATE $N_i \leftarrow$ neighbors of $x_i$ within $\varepsilon$
    \IF{$|N_i| \geq m$}
        \STATE Create new cluster $C$; add $x_i$
        \STATE Expand $C$: recursively add all density-reachable points
    \ELSE
        \STATE Label $x_i$ as \textbf{noise}
    \ENDIF
\ENDFOR
\end{algorithmic}
\end{algorithm}
                        

Steps

1. Pick eps (radius) and min_samples
2. Points with ≥ min_samples neighbors → core
3. Expand clusters from core points; leftovers = noise (−1)

Choosing Parameters

• eps too small → everything is noise
• eps too large → one giant cluster
• min_samples ≈ 2 × n_features

Pseudocode

1. Run a clustering algorithm on your data
2. Points that are far from everyone = anomalies
3. Flag the top 5% most isolated points
4. Investigate manually — fraud? data error? rare event?

Three Approaches

1. DBSCAN noise points: Points labeled −1 are anomalies
2. Distance from centroid: Points far from their K-Means centroid are suspicious
3. Isolation Forest: Isolates points via random partitions — anomalies need fewer splits because they have unusual values. Set contamination to the expected anomaly proportion (e.g., 0.05 = 5%)

Real-World Applications

• "Customers who bought X also bought Y"
• Optimize shelf placement in grocery stores
• Design cross-selling promotions
• Bundle pricing strategies

Steps

1. Convert transactions to a boolean table
2. Find itemsets with support ≥ min_support
3. Generate rules (A → B) with lift > 1

pip install mlxtend

Illustrative Rules (Hypothetical Data)

• Instant noodles → Eggs (Lift: 2.3)
• Rice → Cooking oil (Lift: 1.9)
• Coffee sachets → Bread (Lift: 2.1)
• Shampoo sachets → Soap (Lift: 1.7)

Place eggs next to instant noodles, and bundle coffee + bread for "breakfast packs."

Steps

1. Compute R (days since last buy), F (total orders), M (total spent)
2. Divide each into 5 quintiles scored 1–5
3. Concatenate → "555" = Champion, "111" = Lost

Invert R: fewer days = higher score (labels=[5,4,3,2,1]).

Manual RFM uses arbitrary thresholds. Clustering finds the actual boundaries in your data — often more meaningful and data-driven.

Monetary values are often heavily right-skewed. Apply np.log1p() before scaling to prevent a few high-spenders from dominating the clusters. Without log: [100, 500, 50000] has huge range. After log1p: [4.6, 6.2, 10.8] — much more evenly spaced.

Inductive

Has a .predict() method. Learn once, apply to new data forever.

K-Means, Mini Batch K-Means, GMM, BIRCH

Transductive

Only has .fit_predict(). Must re-fit if new data arrives.

DBSCAN, HDBSCAN, OPTICS, Hierarchical, Spectral