Unsupervised Learning: Cheat Sheet

Assembled from the matching per-unit cheat-sheet slices. The whole topic compressed for the night before the exam.

Clustering foundations

Unsupervised = no target variable; the job is to find structure.
Clustering: minimize intra-cluster distance, maximize inter-cluster distance.
Four types: Hierarchical, Partitional, Density-based, Grid-based.

Bottom-up: merge the closest clusters until one remains; visualize as a dendrogram and cut it to get K clusters. No need to pre-specify K.
Linkage: MIN (single), MAX (complete), Group Average, Centroid, Ward's (squared error).
Example C1 = {a,b}, C2 = {c,d,e} with features 1, 2, 4, 5, 6: single = 2, complete = 5, average = 3.5.
Space O(N²), Time O(N³) (reducible to O(N² log N)). Merges are irreversible.

Partitional; pick K; iterate assign → update until the centroids stop moving. Minimize $\text{SSE} = \sum_i \sum_{x \in C_i} \text{dist}^2(m_i, x)$ .
Medicine example A(1,1) B(2,1) C(4,3) D(5,4) with K=2 converges to {A,B}, {C,D}.
Complexity O(n · K · I · d). Cons: local minima, sensitivity to random initialization, non-globular shapes.
Bisecting K-Means: repeatedly split the largest-SSE cluster with K=2 (a divisive + K-means hybrid); better for large K and gives similar-sized clusters. P(good init) = $K!/K^K$ (K=10 gives 0.00036).

$\text{Support}(X \rightarrow Y) = \sigma(X \cup Y)/|T|$ ; $\text{Confidence}(X \rightarrow Y) = \sigma(X \cup Y)/\sigma(X)$ . Co-occurrence is not causality.
Two steps: frequent-itemset generation (expensive) then rule generation. There are $2^d$ candidate itemsets.
Apriori principle: frequent ⇒ all subsets frequent; infrequent ⇒ all supersets infrequent (support is anti-monotone). Speed-ups: reduce M, reduce N, reduce NM (hash tree).
Example on {1,3,4}, {2,3,5}, {1,2,3,5}, {2,5} at minsup 50% gives L3 = {2,3,5}.
Maximal: no immediate superset is frequent. Closed: no immediate superset has the same support. Maximal ⊆ Closed ⊆ Frequent.
Rule generation: $|L| = k$ gives $2^k - 2$ rules; confidence is anti-monotone with respect to RHS size: $c(ABC \rightarrow D) \geq c(AB \rightarrow CD) \geq c(A \rightarrow BCD)$ .

No candidate generation. Build the FP-tree in 2 passes: count and order descending to get the header, then insert the sorted transactions sharing prefixes, with node links.
Mine with conditional FP-trees, one per suffix; the recursion bottoms out when the tree is a single path.
More efficient than Apriori, which needs multiple database scans.

$A = U \Sigma V^{T}$ . U = orthonormal eigenvectors of AAᵀ; V = of AᵀA; Σ = diagonal of singular values = √eigenvalues, in descending order.
AAᵀ and AᵀA are symmetric, square, share the same positive eigenvalues, and have the same rank r. Orthogonal means dot product 0, so a 90° angle.
Uses: dimensionality reduction, recommendation systems, image compression, noise reduction.
Keep the top singular values for a low-rank approximation - the "Tiger" still reads as a tiger with 20% of the dimensions.

Everything above covers every slide topic in the Unit 4 folder (Module 4, L1-L8 plus SVD).
The FP-Growth and SVD decks were largely image and equation slides that do not extract as text. Those derivations are reconstructed from standard material and follow the slide flow; FP-Growth's worked example comes from L8, which extracted cleanly.
The lecture numbering in the source folder jumps L3 to L5 - there is no L4 file, and nothing is missing because of it.
All the worked examples here - hierarchical linkage, the K-means medicines, Apriori, the rule confidences and the FP-Growth itemsets - were independently recomputed and verified.