K-Means Clustering Notes

Today's focus is on clustering, specifically K-means and its advanced versions.
We will address how to evaluate the quality of clustering, a crucial step after applying various clustering methods.

Many clustering algorithms can be directly implemented using libraries like scikit-learn (sklearn) in Python.
Some algorithms, like hierarchical clustering, are simple enough to implement from scratch.
K-means is only slightly more complex but still relatively straightforward to implement.

Deterministic Method: Yields the same results upon repeated executions.
Based on identifying the minimum distance in the distance matrix.
Flexibility in Cluster Numbers: The dendrogram can be cut at different levels to vary the number of clusters.
Linkage Criteria: Options include simple linkage (merging clusters with close points) and complete linkage (merging based on the furthest points still being close).
Disadvantages:
- Slow: Requires traversing the distance matrix (n x n) approximately n times, leading to a complexity of $O(n^3)$ . Some linkage criteria may achieve $O(n^2)$ , but it remains slow.
- For a million data points, this could involve a trillion comparisons, making it impractical.
- Excessive Information: Generates all levels of clustering, which may be unnecessary.

Motivation: To address the limitations of hierarchical clustering by reducing comparisons and information overload.
Concept: Divides the space into non-nested partitions, where any point in a specific area belongs to a defined cluster.
Efficiency: Reduces comparisons by relating new data points only to partitions or lines, not all data points.
Assignment of new data points is more efficient, avoiding $n^2$ calculations.

Comparisons: Every point is compared to k partitions (k being the number of clusters).
For example, with three partitions and a million data points, it involves 3 million comparisons, significantly less than hierarchical clustering.
K-means serves as a foundational algorithm for other partitional clustering methods.

Initialization:
- Start with n data points (e.g., 12 points).
- Choose the number of clusters, k, as a hyperparameter. With k equals two, split the data into two clusters.
- Select k random data points as initial cluster centroids. A refinement is to pick data points rather than random locations.
- Assign each data point to its closest centroid, forming initial clusters.
Iteration:
- Recalculate the centroid of each cluster based on the data points assigned to it.
- Reassign each data point to the closest centroid based on the newly calculated centroids.
- Repeat the centroid recalculation and reassignment steps until convergence.

Convergence is achieved when there are minimal changes in cluster assignments.
The algorithm works as long as points exist in a space and the desired number of clusters is defined.
Convergence Criteria:
- Maximum Iterations: Set a limit (e.g., 10,000 iterations) to prevent infinite loops if convergence is not reached.
- Centroid Position: Monitor the centroid positions and stop if changes are below a threshold.
- Relabeling: Stop when the number of points being relabeled decreases below a threshold.
- Overall Distance: Monitor the overall distance of points to their centroids.
  - Calculate the sum of squared distances between each point $x$ and the centroid $m$ of its cluster.
  - $\sum(x-m)^2$
  - This approximates the area of the cluster and is minimized during K-means.

K-means tends to create blob-like clusters due to its centroid-based approach.
These are generic stopping criteria applicable to other algorithms.
The algorithm aims to minimize the distance between points and their cluster centroids.
Partitioning occurs by assigning points to the nearest centroid without needing pairwise distance calculations.
With 'n' points and 'k' centroids, each step involves $n * k$ calculations.

First guess is often poor due to the initial random placement of centroids.
Centroids move in each step as they are assigned and reassigned.
Partitions are represented by lines separating clusters (points closer to a centroid belong to that cluster).
Convergence is achieved when it becomes difficult to discern changes between iterations.
The algorithm minimizes the distance between a point and its cluster's centroid.

K-means aims to find centroids that are central to the cluster.
Partitions become equivalent to straight lines in the space that that data is in.
The place where the straight liens meet represents an equidistant point to three centroids
Leads to a lot of reassignments as data points move the points are close to the dividing lines in the space.