Clustering Algorithm Demonstration

Algorithm:

First of all, let us explain to you visually what the K-means clustering algorithm looks like.

1. Given a set of points, x1,........,xn and an integer value, k, representing the number of cluster we are trying to make
2. We first pick k points out of x1,........,xn to use as our first centroids
3. Then we will clusterize all the points into the k sets by finding the nearest centeroid for each point.
4. We find the new centroids using the cluster we now have (Centroid is just the mean of the cluster).
5. We check if any of the point needs to be reassigned to a different cluster based on the new centroid
6. If no reassignment happens, we are now done. Otherwise, we go through steps 4 and 5 until no reassignment happens, aka convergence.

Example:

Place mouse over a particular step to see the corresponding visualization on the right

Real Life Application:

This can be useful in the following fields:

1. Marketing

   • Goal: Subdivide a market into distinct subsets of customers, such that each subset is conceivably a submarket which can be reached with a customized marketing mix.

   • Approach: Collect different attributes of customers based on their geographical and lifestyle related information. Find clusters of similar customers. Measure the clustering quality by observing buying patterns of customers in same cluster vs. those from different clusters.

2. Document clustering

   • Goal: Find groups of documents that are similar to each other based on the important terms appearing in them. Information retrieval can utilize the clusters to relate a new document or search term to clustered documents.

   • Approach: Identify frequently occurring terms in each document. Form a similarity measure based on the frequencies of different terms. Use it to cluster.

3. Biology: Taxonomy of living things: kingdom, phylum, class, order, family, genus and species
4. Social networks: Recognize communities within people

Why does it converge?

In order to prove the convergence, we can specify a clustering quality objective function and show that the algorithm converges to a (local) minimum of that function. The objective function K-means is optimizing is the sum of squared distances from any data point to its assigned centroid.

Formally, the K-Means objective is :
$L(z,\mu,;D) = \sum_n \parallel x_n - \mu_{z_n} \parallel^2 = \sum_k \sum_{n:z_n=k} \parallel x_n -\mu_k \parallel^2$ where $z$ are assignments, $\mu$ are the centroids, and $D$ is the dataset.

There are only two points in which the K-means algorithm changes the values of $\mu$ or $z$ :
1. When we assign data points to centroids.
2. When we recalculate centroids.

We will show that both of these operations can never increase the value of $L$ .
After the first iteration, there are only finitely many possible assignments to $z$ and $\mu$ , because $z$ is discrete and because $\mu$ can only take on a finite number of values: means of some subset of the data. Besides, $L$ is lower-bounded by zero (square can’t be less than 0). Together, this means that $L$ cannot decrease more than a finite number of times. Thus, it must stop decreasing at some point, where the algorithm has converged.

For the first operation, when looking at a data point $n$ , suppose that the previous value of $z_n$ is $a$ and the new value is $b$ . It must be the case that $\parallel x_n - \mu_b \parallel \leq \parallel x_n - \mu_b \parallel$ . Thus, changing from $a$ to $b$ can only decrease $L$ .
For the second operation, consider the second form of $L$ The second operation computes $\mu_k$ as the mean of the data points for which $z_n = k$ , which is precisely the point that minimizes squared distances. Thus, this update to $\mu_k$ can only decrease $L$ .

How sensitive it is to initialization?

There are several aspects of K-means that are unfortunate. One of those is that the convergence is only to a local optimum of $L$ depending on the initializations. So how should we initialize the centroids? One way of doing it is to pick some data points from the data set as centroids. This does not work well, because it’s very likely that data points that are picked as centroids will end up in the same cluster.

A better approach is called the furthest first, which initialize the first centroid randomly, but then intialize the second centroid to be the data point that is furthest away from the first centroids. With this approach, we can assure that the centroids to be well distributed.

An even better approach is called K-means++. It works like the furthest first approach, but instead of choosing the next centroid to be the point that are furthest away from all assigned centroids, it selects a point with probability proportional to the square of its distance to the nearest preceding centroid. By doing so, we add some randomness to the algorithm and make it more likely to get one neaer the center of the true cluster.

In practice, you should run it couple times with different initializations and pick the one with minimal resulting $L$ .

What should K be (Hyperparameter tuning)?

If someone just gives you a dataset and ask you to cluster it, how many clusters should you produce? As you might have realized that if we keep increasing K, the objective function $L$ decreases as well (until K > N), and so simply using $L$ as a notion of goodness is insufficient (like overfitting in a supervised learning). We can “regularize” K so that the model can’t grow to be too complicated (imagine you practice too much on the practice exams but fail to generalize the concepts).

The two most popular procedures are the Bayes Information Criteria (BIC) and the Akaike Information Criteria (AIC), defined below in the context of K-means:
- BIC : $argmin_K L_K + K logD$
- AIC : $argmin_K L_K + 2KD$

The idea behind these criteria is that increasing K will make $L$ go down. However, if it doesn’t go down “by enough” then it’s not worth doing.

Add your own points by and run the k-means algorithm with it
This will find two clusters among the entered points
Please limit the range for both x and y between 0 and 30, inclusive
Make sure you enter at least two points
Notice: Clearing should be used prior to clicking on “Find K-Means”, in order to redo the interaction, please reload the page!

Algorithm Analysis

• Time Complexity:
  • O(tkn), where n is number of objects, k is number of clusters, and t is number of iterations. Normally, k, t << n.
• Limitaions:
  • Need to specify k, the number of clusters
  • Sensitive to initial centroids, noisy data and outliers