Project Title

Kmeans from A to Z

by Fan Li

Table of Contents

1. Description
2. Workflow
   1. Kmeans
   2. Kmeans ++
   3. Applications
   4. Advanced topic: RF + Kmeans
   5. Limitations
3. Dataset
4. About
5. References

Description

For this project, I implemented the Kmeans as well as the kmeans++ algorithm from scratch. I used five data sets to showcase some applications and results of those algorithms. Further, after uncovering the drawbacks of Kmeans, I implemented a ‘Spectral clustering’ using the random forest (RF) technique paired with kmeans++ to overcome the ‘discontinuity of clusters’ issue. Lastly, I addressed some limitations and possible improvements for future research reference.

Workflow:

1. Kmeans

Procedure:

1. Initialize centroids꞉ Randomly initialize k number of data points from the original X data. The number of k depends on how many clusters we want to end up with.

2. Compute distance꞉ Here I used Euclidean distance to measure the distance from each of the remaining data points to each of the centroids we initialized in step 1, assigning each of the remaining data points to the ‘closest ’ centroids.

3. Update centroids꞉ Within each cluster, compute the average distance of all the data points to that centroid FEATURE WISE. This average distance will be the new centroids’ ‘coordinate’ in that cluster. Intuitively speaking, this means we are correcting the centroids to be the ‘center’ of that cluster. This means our final centroids will most likely not be members of the dataset. The reason we picked data points from the dataset as initial centroids is simply to assign a starting point.

4. Reassign data point Finally, compute distance, reassign data points according to the new centroids we updated in step 3, update centroids. Iterate the above process until the centroids’ ‘coordinates’ don’t change any more.

ISSUES:

Each rounds’ initial centroids are different due to the mechanism of random initialization. This goes without saying, but the algorithm produces slightly different final centroids, labels, and clusters. The good news is all the final norms are 0, which means those clusters make perfect sense in each of their own round’s ‘world’.

2. Kmeans ++

Procedure:

1. Initialize centroids꞉ Randomly initialize k number of data points from the original X data. The number of k depends on how many clusters we want to end up with.

2. Compute distance꞉ Here I used Euclidean distance to measure the distance from each of the remaining data points to each of the centroids we initialized in step 1, assigning each of the remaining data points to the ‘closest ’ centroids.

3. Update centroids꞉ Within each cluster, compute the average distance of all the data points to that centroid FEATURE WISE. This average distance will be the new centroids’ ‘coordinate’ in that cluster. Intuitively speaking, this means we are correcting the centroids to be the ‘center’ of that cluster. This means our final centroids will most likely not be members of the dataset. The reason we picked data points from the dataset as initial centroids is simply to assign a starting point.

4. Reassign data point Finally, compute distance, reassign data points according to the new centroids we updated in step 3, update centroids. Iterate the above process until the centroids’ ‘coordinates’ don’t change any more.

3. Applications

• Synthetic data set

• Multi-dimension data (Circle data 500*2)

As you can see, Kmeans performs poorly on disjointed and nested structures. To rescue, I will introduce spectral clustering by using RF and Kmeans together in the Advanced topic section.

• Breast cancer

  • Without scaling X꞉

* With scaled X

• Image compression

  • Grayscale

    • Original:
    • Kmeans++ copresion:

  • Color

    • Original:
    • Kmeans++ copresion:

4. Advanced topic: RF + Kmeans

Procedure:

1. RF ‘group’ similar data points.

2. Construct frequency (similarity) matrix

3. Feed similarity matrix to SpectralClustering

Test on circle data (sklearn vs. RF+Kmeans)

5. Limitations

• Randomness in RF will sometimes result in unexpected cluster labels (accuracy is not as steady).

• Kmeans++ only considers picking the furthest point to its previous centroid. Take k=3 as an example, as a consequence, the 1st and 3rd controls can sometimes be quite close to each other. Is there a way to consider all the previous centroids and pick the furthest point from all the previous centroids? How do we even define the ‘minimum distance’ since each centroid has its own furthest points, one point can't be the furthest to multiple centroids?

Dataset

• Synthetic data set: A small synthetic data that has a shape of 16*1
• Multi-dimension data (Circle data 500*2): from sklearn.datasets.make_circles
• Breast cancer: from sklearn.datasets.load_breast_cancer
• north-africa-1940s-grey and parrt-vancouver.jpg: from Professor Terence Parr

About

• Jupyter Notebook file: workspace where I performed and tested the works.
• kmeans.py: modularized support functions

• kmeans.pdf: pdf presentation

• img: png files were used in this project.

Software used

• Jupyter Notebook
• Atom
• Python 3.9

• Numpy
• Pandas
• Matplotlib
• Seaborn
• sklearn
• statistics
• PIL
• tqdm

References

• K-Means Clustering: From A to Z
• ML | K-means++ Algorithm
• Image Segmentation using K Means Clustering
• Breiman's website