保留正文与补采附件。源页面当前未重新核验；具体限制见交付清单。

Revisit consent button We value your privacy We use cookies to enhance your browsing experience, serve personalised ads or content, and analyse our traffic. By clicking "Accept All", you consent to our use of cookies. Customise Reject All Accept All Customise Consent Preferences We use cookies to help you navigate efficiently and perform certain functions. You will find detailed information about all cookies under each consent category below. The cookies that are categorised as "Necessary" are stored on your browser as they are essential for enabling the basic functionalities of the site. ... Show more NecessaryAlways Active Necessary cookies are required to enable the basic features of this site, such as providing secure log-in or adjusting your consent preferences. These cookies do not store any personally identifiable data.

Functional Functional cookies help perform certain functionalities like sharing the content of the website on social media platforms, collecting feedback, and other third-party features.

Analytics Analytical cookies are used to understand how visitors interact with the website. These cookies help provide information on metrics such as the number of visitors, bounce rate, traffic source, etc.

Performance Performance cookies are used to understand and analyse the key performance indexes of the website which helps in delivering a better user experience for the visitors.

Advertisement Advertisement cookies are used to provide visitors with customised advertisements based on the pages you visited previously and to analyse the effectiveness of the ad campaigns.

Uncategorised Other uncategorised cookies are those that are being analysed and have not been classified into a category as yet. No cookies to display. Reject All Save My Preferences Accept All Toggle SearchToggle Mobile Navigation Publish AI, ML & data-science insights to a global community of data professionals. Sign inSubmit an Article LatestEditor's PicksNewsletterShipAI

Write For TDS LinkedInXToggle Search Data Science

K-Means Clustering: How It Works & Finding The Optimum Number Of Clusters In The Data

Mathematical formulation, Finding the optimum number of clusters and a working example in Python. Serafeim Loukas, PhD September 9, 20208 min read

Mathematical formulation, Finding the optimum number of clusters and a working example in Python

Image created by the author Image created by the author

Learn this step by step with the interactive AI and Data Scientist and Machine Learning roadmaps.

Introduction

K-means is one of the most widely used unsupervised clustering methods. The K-means algorithm clusters the data at hand by trying to separate samples into K groups of equal variance, minimizing a criterion known as the inertia or within-cluster sum-of-squares. This algorithm requires the number of clusters to be specified. It scales well to large number of samples and has been used across a large range of application areas in many different fields. The k-means algorithm divides a set of N samples (stored in a data matrix X) into K disjoint clusters C , each described by the mean μj of the samples in the cluster. The means are commonly called the cluster "centroids". K-means algorithm falls into the family of unsupervised machine learning algorithms/methods. For this family of models, the research needs to have at hand a dataset with some observations without the need of having also the labels /classes of the observations. Unsupervised learning studies how systems can infer a function to describe a hidden structure from unlabeled data. Now let's discover the mathematical foundations of the algorithm.

Mathematical formulation

Given a set of observations (x 1, x 2, ..., x n), where each observation is a d -dimensional real vector, k -means clustering aims to partition the n observations into k (≤ n) sets S = {_S_1, _S_2, ..., Sk} so as to minimize the within-cluster sum of squares (WCSS) (i.e. variance). Formally, the objective is defined as follows: Latex image created by the author. Latex image created by the author. where μ i is the mean of points in group/cluster Si.

Another resource. Learn Data Science and ML with the help of an 🤖 AI-powered tutor. Start here https://aigents.co/learn choose a topic and he will show up where you need him. No paywall, no signups, no ads.

Understanding the algorithm behind

Example of some Voronoi diagrams source: https://scikit-learn.org/stable/auto_examples/cluster/plot_kmeans_digits.html#sphx-glr-auto-examples-cluster-plot-kmeans-digits-py. Example of some Voronoi diagrams (source: https://scikit-learn.org/stable/auto_examples/cluster/plot_kmeans_digits.html#sphx-glr-auto-examples-cluster-plot-kmeans-digits-py). The algorithm can also be understood through the concept of Voronoi diagrams. First, the Voronoi diagram of the points is calculated using the current centroids. Initially, the centroids are usually chosen randomly but this depends on the underlying package / library / software used. Each segment in the Voronoi diagram becomes a separate cluster. Secondly, the centroids are updated to the mean of each segment. The algorithm then repeats this until a stopping criterion is fulfilled. The algorithm stops when the relative decrease in the objective function between iterations is less than the given tolerance (ε) value or when centroids move (in space) less than the tolerance.

Finding the optimum number of clusters

As stated in the introduction, the K-Means algorithm requires the number of clusters to be specified beforehand. In case that there is no valid assumption about the underlying number of clusters in the data, this task can be difficult to tackle. Fortunately, there are some methods for estimating the optimum number of clusters in our data such as the Silhouette Coefficient or the Elbow method. If the ground truth labels are not known, evaluation must be performed using the model itself. In this article we will only use the Silhouette Coefficient and not the Elbow method which is much simpler. Briefly, the elbow method looks at the percentage of variance explained as a function of the number of clusters: One should choose a number of clusters so that adding another cluster doesn't give much better modeling of the data. A higher Silhouette Coefficient score relates to a model with better defined clusters. The Silhouette Coefficient is defined for each sample and is composed of two scores:

The Silhouette Coefficient s for a single sample is then defined as: Latex image created by the author. Latex image created by the author. Finally, the Total Silhouette Coefficient for a set of samplesis given as the mean of the Silhouette Coefficient for each sample.

The best value is 1 and the worst value is -1. Values near 0 indicate overlapping clusters. Negative values generally indicate that a sample has been assigned to the wrong cluster, as a different cluster is more similar.

Python working example

For this example we will create artificial data i.e. artificial clusters. This way we will know in advance the ground through i.e. the exact number of clusters in our dataset. Let's start with importing the required python libraries: text

from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_samples, silhouette_score

import matplotlib.pyplot as plt
import matplotlib.cm as cm
import numpy as np

Next, let's create some artificial data containing 500 samples , 2 features/variables , and K=4 clusters. text

# Generating the data
# This particular setting has one distinct cluster and 3 clusters placed close together.
X, y = make_blobs(n_samples=500,
                  n_features=2,
                  centers=4,
                  cluster_std=1,
                  center_box=(-10.0, 10.0),
                  shuffle=True,
                  random_state=1)

We know that we have K=4 clusters in the data however, in order to understand how the Silhouette Score works we will fit the model using a range of different number of clusters. Each time, we will estimate the Silhouette Score and also plot the data with the final (converged) centroids. All these are done by the following code: text

range_n_clusters = [3, 4, 5]

text

for n_clusters in range_n_clusters:
    # Create a subplot with 1 row and 2 columns
    fig, (ax1, ax2) = plt.subplots(1, 2)
    fig.set_size_inches(18, 7)

    # The 1st subplot is the silhouette plot
    # The silhouette coefficient can range from -1, 1 but in this example all
    # lie within [-0.1, 1]
    ax1.set_xlim([-0.1, 1])
    # The (n_clusters+1)*10 is for inserting blank space between silhouette
    # plots of individual clusters, to demarcate them clearly.
    ax1.set_ylim([0, len(X) + (n_clusters + 1) * 10])

    # Initialize the clusterer with n_clusters value and a random generator
    # seed of 10 for reproducibility.
    clusterer = KMeans(n_clusters=n_clusters, random_state=10)
    cluster_labels = clusterer.fit_predict(X)

    # The silhouette_score gives the average value for all the samples.
    # This gives a perspective into the density and separation of the formed
    # clusters
    silhouette_avg = silhouette_score(X, cluster_labels)
    print("For n_clusters =", n_clusters,
          "The average silhouette_score is :", silhouette_avg)

    # Compute the silhouette scores for each sample
    sample_silhouette_values = silhouette_samples(X, cluster_labels)

    y_lower = 10
    for i in range(n_clusters):
        # Aggregate the silhouette scores for samples belonging to
        # cluster i, and sort them
        ith_cluster_silhouette_values = 
            sample_silhouette_values[cluster_labels == i]

        ith_cluster_silhouette_values.sort()

        size_cluster_i = ith_cluster_silhouette_values.shape[0]
        y_upper = y_lower + size_cluster_i

        color = cm.nipy_spectral(float(i) / n_clusters)
        ax1.fill_betweenx(np.arange(y_lower, y_upper),
                          0, ith_cluster_silhouette_values,
                          facecolor=color, edgecolor=color, alpha=0.7)

        # Label the silhouette plots with their cluster numbers at the middle
        ax1.text(-0.05, y_lower + 0.5 * size_cluster_i, str(i))

        # Compute the new y_lower for next plot
        y_lower = y_upper + 10  # 10 for the 0 samples

    ax1.set_title("The silhouette plot for the various clusters.")
    ax1.set_xlabel("The silhouette coefficient values")
    ax1.set_ylabel("Cluster label")

    # The vertical line for average silhouette score of all the values
    ax1.axvline(x=silhouette_avg, color="red", linestyle="--")

    ax1.set_yticks([])  # Clear the yaxis labels / ticks
    ax1.set_xticks([-0.1, 0, 0.2, 0.4, 0.6, 0.8, 1])

    # 2nd Plot showing the actual clusters formed
    colors = cm.nipy_spectral(cluster_labels.astype(float) / n_clusters)
    ax2.scatter(X[:, 0], X[:, 1], marker='.', s=30, lw=0, alpha=0.7,
                c=colors, edgecolor='k')

    # Labeling the clusters
    centers = clusterer.cluster_centers_
    # Draw white circles at cluster centers
    ax2.scatter(centers[:, 0], centers[:, 1], marker='o',
                c="white", alpha=1, s=200, edgecolor='k')

    for i, c in enumerate(centers):
        ax2.scatter(c[0], c[1], marker='$%d$' % i, alpha=1,
                    s=50, edgecolor='k')

    ax2.set_title("The visualization of the clustered data.")
    ax2.set_xlabel("Feature space for the 1st feature")
    ax2.set_ylabel("Feature space for the 2nd feature")

    plt.suptitle(("Silhouette analysis for KMeans clustering on sample data "
                  "with n_clusters = %d" % n_clusters),
                 fontsize=14, fontweight='bold')

plt.show()

Code output in the console image created by the author Code output in the console (image created by the author)

We observe that the average/mean Silhouette Score is the highest in the case of K=4 clusters. This verifies that the Silhouette Score is a good measure of K-means fitting goodness. We also produced these Figures: Silhouette score the data with the final converged centroids image created by the author Silhouette score & the data with the final (converged) centroids (image created by the author) Silhouette score the data with the final converged centroids image created by the author Silhouette score & the data with the final (converged) centroids (image created by the author) Silhouette score the data with the final converged centroids image created by the author Silhouette score & the data with the final (converged) centroids (image created by the author) The vertical line is the average silhouette score of all the values. Again, we can also visually verify that the Silhouette Score is a good measure of K-means fitting goodness for the specific example.

Conclusions

K-means is one of the most widely used unsupervised clustering methods. The algorithm clusters the data at hand by trying to separate samples into K groups of equal variance, minimizing a criterion known as the inertia or within-cluster sum-of-squares. This algorithm requires the number of clusters to be specified. However, if the ground truth labels are not known, the evaluation must be performed using the model itself. In this article we used the Silhouette Coefficient. From the working example, we can verify that the Silhouette Score is a good measure of K-means fitting goodness.

That's all! Hope you liked this new article - more to come soon!

References

[1] Peter J. Rousseeuw (1987). "Silhouettes: a Graphical Aid to the Interpretation and Validation of Cluster Analysis". Computational and Applied Mathematics 20: 53–65. doi:10.1016/0377–0427(87)90125–7. [2] https://en.wikipedia.org/wiki/Silhouette_(clustering)

You may also like:

LSTM Time-Series Forecasting: Predicting Stock Prices Using An LSTM Model Time-Series Forecasting: Predicting Stock Prices Using An ARIMA Model

Stay tuned & support this effort

If you liked and found this article useful, follow me to be able to see all my new posts. Questions? Post them as a comment and I will reply as soon as possible.

Latest posts

The Best FREE Data Science Resources: FREE Books & Online Courses ROC Curve Explained using a COVID-19 hypothetical example: Binary & Multi-Class Classification... Support Vector Machines (SVM) clearly explained: A python tutorial for classification problems... PCA clearly explained - How, when, why to use it and feature importance: A guide in Python Everything you need to know about Min-Max normalization in Python How Scikit-Learn's StandardScaler works

Get in touch with me

Register Now to Continue Reading

Unlock Towards Data Science with a Free Account

All articles on Towards Data Science are available to registered users. Create a free account today to access this article and thousands more. Register for freeSign in to your account

Written By

Serafeim Loukas, PhD

See all from Serafeim Loukas, PhD ClusteringData ScienceK MeansMachine LearningUnsupervised Learning Share This Article

Towards Data Science is a community publication. Submit your insights to reach our global audience and earn through the TDS Author Payment Program. Write for TDS

Related Articles

How to Implement Randomization with the Python Random Module

Programming Let's generate randomness in our code’s outputs Mahnoor Javed November 24, 20256 min read

Multi-head Attention is a Fancy Addition Machine

Machine Learning "Attention is All you Need" showed attention as a sequence of multiplicative and concat operations but... what if I told you they have addition too? Kunj Mehta July 24, 20258 min read

On-Device Machine Learning in Spatial Computing

Machine Learning Tracking real-world objects In augmented reality Prithiv Dev Devendran February 17, 202516 min read

Why I Don’t Trust LLMs to Decide When the Weather Changed

Large Language Models A physicist's approach to building production-grade agents Fernando Arizmendi May 6, 20266 min read

Apache Spark for Data Science - Word Count With Spark and NLTK

Data Science Learn to count words of a book and address the common stop word issue - implemented in PySpark Dario Radečić April 16, 20226 min read

The Simple Yet Practical Data Cleaning Codes

Programming To solve the common scenarios of messy data Admond Lee January 11, 20195 min read

When the dataset is small, features are your friends

Artificial Intelligence Feature engineering can compensate for the lack of data. Krzysztof Pałczyński April 3, 20236 min read

India - Air Pollution Data Analysis

Machine Learning A report by Health Effects Institute on air pollution in India (2018) reports that air pollution was responsible for 1.1 million deaths in... Shubhankar Rawat June 1, 201918 min read

Machine-learned model serving at scale

Machine Learning Most ML libraries and platforms use all available CPU resources for single model inference. This breaks down for concurrent evaluations. Lester Solbakken January 4, 20228 min read

Your home for data science and AI. The world's leading publication for data science, data analytics, data engineering, machine learning, and artificial intelligence professionals. Subscribe to Our NewsletterWrite For TDS•About•Advertise•Privacy Policy•Terms of Use © Insight Media Group, LLC 2026•The New Stack•roadmap.sh•Creator Network

Recommended Articles

Close