Key Sequence

Notation

New Concepts

• Kernel Trick

Important Results / Claims

Questions

Interesting Factoids

Key Sequence

Notation

New Concepts

• Decision Tree

Important Results / Claims

Questions

Interesting Factoids

constituents

• dataset \(\qty {x^{(1)}, \dots, x^{(n)}}\)
• number of clusters \(k\)

requirements

Initialize cluster centroids \(\mu_{1}, …, \mu_{k}\) randomly, and repeat:

• assigning points \(x^{(i)}\) to cluster centers \(c^{(i)}\): for each \(i \in [1, \dots N]\), write \(c^{(i)} = \arg\min_{j} \norm{x^{(i)}- \mu_{j}}^{2}_{2}\)
• update centroids: for each \(j \in [1 \dots k]\), write \(\mu_{j} = \frac{\sum_{i=1}^{n} \mathbbm{1}\qty {c^{(i)}=j} x^{(i)}}{\sum_{i=1}^{n} \mathbbm{1}\qty {c^{(i)}=j}}\)

additional information

some ways to pick better centroid

• sample the data points as the initial centroids
• k-means++

k-means++

• pick uniform data point to be first centroid
• pick next centroid w.r.t. probability proportional to distance to the previous centroid squared

distortion function

Consider the following function:

OG scaling laws paper