Index
· 1: Understanding the Fundamentals
∘ 1.1: What’s Okay-Means Clustering?
∘ 1.2: How Does Okay-Means Work?
· 2: Implementing Okay-Means
∘ 2.1: The Arithmetic Behind Okay-Means
∘ 2.2: Selecting the Optimum Variety of Clusters
· 3: Okay-Means in Observe
∘ 3.1 Okay-Means From Scratch in Python
∘ 3.2 Implementing Okay-Means with Scikit-Be taught
· 4: Benefits and Challenges
∘ 4.1 Advantages of Utilizing Okay-Means
∘ 4.2 Overcoming Okay-Means Limitations
· 5: Past Fundamental Okay-Means
∘ 5.1 Variants of Okay-Means
1.1: What’s Okay-Means Clustering?
Think about you’re at a farmer’s market with a bunch of fruits and veggies that it is advisable to type out. You wish to set up them so all of the apples, oranges, and carrots are hanging out with their form. This job is rather a lot like what Okay-Means Clustering does in knowledge science.
So, what’s Okay-Means Clustering? It’s a method used to naturally group knowledge. Consider it as a solution to type unlabeled knowledge into totally different teams or clusters. Every cluster is a bunch of information factors which might be extra alike to one another than to these in different teams. The “Okay” in Okay-Means? It represents the variety of teams you suppose there must be.
1.2: How Does Okay-Means Work?
Now, remember the farmer’s market instance, and let’s attempt to dive deep a bit extra into Okay-means mechanisms.
Consider Okay-Means as organising the preliminary fruit stands (centroids) in our market. It randomly picks just a few spots (knowledge factors) to position these stands. The variety of stands you resolve to arrange is the “Okay” in Okay-Means, and this quantity relies on what number of several types of produce (teams) you suppose you have got.
Now, Okay-Means takes every fruit and veggie (knowledge level) and figures out which stand (centroid) it belongs to based mostly on how shut it’s. It’s like every apple, orange, or carrot selecting the closest stand to hang around at, forming little teams round them.
After all of the produce has discovered a stand, Okay-Means checks if the stands are in the very best spots. It does this by discovering a brand new spot for every stand based mostly on the common place of all of the produce grouped round them. It’s just like transferring the stands to the precise center of every produce group to ensure they’re actually on the coronary heart of the motion.
This technique of sorting produce and adjusting stands retains going. Fruits and veggies would possibly transfer to a unique stand in the event that they discover one nearer, and the stands would possibly shift positions to higher signify their teams. This cycle continues till the stands and their produce teams don’t change a lot anymore. That’s when Okay-Means is aware of the market is completely organized, and every bit of produce is of its form.
What you find yourself with are properly organized stands (clusters) with fruits and veggies grouped round them. Every stand represents a kind of produce, exhibiting you the way your market (knowledge) could be divided into distinct sections (classes) based mostly on similarities.
2.1: The Arithmetic Behind Okay-Means
Let’s placed on our math hats for a second and peek into the engine room of the Okay-Means algorithm to see what makes it tick. Okay-Means is all about discovering the candy spot:
the optimum placement of centroids that minimizes the space between factors in a cluster and their central level.
Right here’s how the mathematics performs out:
Step 1: Initialization
Initially, Okay-Means must resolve the place to begin, selecting okay preliminary centroids (μ1,μ2,…,μk) from the dataset. This may be finished randomly or extra strategically with strategies like Okay-Means++, which we are going to cowl later.
Whereas no particular method is used right here, the selection of preliminary centroids can considerably have an effect on the end result. However don’t fear, as a result of, within the subsequent part, we are going to information you thru the very best ideas to decide on the optimum okay.
Step 2: Task of Factors to Closest Centroid
NeXT, each knowledge level x is assigned to the closest centroid, forming okay clusters, the place the “nearest” centroid is set by the minimal distance between the purpose and all centroids.
Right here, the space d between some extent x and a centroid μi is usually calculated utilizing the Euclidean distance:
the place xj and μij are the j-th dimensions of level x and centroid μi, respectively. Now, whereas Euclidean distance is the preferred selection for Okay-Means, you could possibly discover its software with extra distances. Nonetheless, take into account that Euclidean distance is often the urged selection for optimum efficiency, whereas different variances of the algorithm are extra versatile to totally different distance strategies. Have a look at the subsection 2.1 of my earlier article about Okay-Nearest Neighbors to know extra about distance strategies:
Conserving the Euclidean distance in thoughts, let’s see how the algorithm assigns some extent x to the cluster Ci:
Right here’s what it means:
- Ci: This represents the i-th cluster, a set of factors grouped based mostly on their similarity.
- x: It is a level within the dataset that the Okay-Means algorithm is making an attempt to assign to one of many okay clusters.
- d(x,μi): This calculates the space between the purpose x and the centroid μi of cluster Ci. The centroid is actually the imply place of all of the factors at the moment in cluster Ci.
- d(x,μj): This calculates the space between the purpose x and the centroid μj of another cluster Cj.
- okay: That is the entire variety of clusters the algorithm is making an attempt to partition the information into.
The situation d(x,μi) ≤ d(x,μj) ∀ j, 1≤j≤okay specifies {that a} level x is assigned to the cluster Ci if and provided that the space from x to the centroid μi of Ci is lower than or equal to its distance from x to the centroids μj of all different clusters Cj, for each j from 1 to okay.
In less complicated phrases, the method says:
Have a look at all of the clusters and their facilities (centroids). Now, discover which centroid is closest to level x. Whichever cluster has this closest centroid, that’s the cluster x belongs to.
This step ensures that every level is assigned to the cluster with the closest centroid, minimizing within-cluster distances and making the clusters as tight and homogenous as potential.
Step 3: Updating the Centroids
In spite of everything factors have been assigned to clusters, the positions of the centroids are recalculated to be on the heart of their respective clusters.
The brand new place μi′ of centroid μi is calculated because the imply of all factors assigned to cluster Ci:
the place ∣Ci∣ is the variety of factors in cluster Ci, and the summation aggregates the positions of all factors within the cluster.
Step 4: Iteration Till Convergence
The task and replace steps (Steps 2 and three) are repeated till the centroids now not change considerably, indicating that the algorithm has converged.
Right here, convergence is usually assessed by measuring the change in centroid positions between iterations. If the change falls beneath a predetermined threshold, the algorithm stops.
Within the context of the Okay-Means algorithm, there isn’t a single, universally outlined method for convergence that applies in all circumstances. As an alternative, convergence is set based mostly on the algorithm’s habits over successive iterations, particularly whether or not the centroids of the clusters cease altering considerably.
Nonetheless, a standard solution to assess convergence is by trying on the change within the within-cluster sum of squares (WCSS) or the positions of the centroids between iterations. Right here, we set a threshold for modifications within the centroid positions or the WCSS. If the change falls beneath this threshold from one iteration to the subsequent, the algorithm could be thought of to have converged. This may be expressed as:
the place:
- μi(t) is the place of centroid i at iteration t,
- μi(t−1) is the place of centroid i at iteration t−1,
- ϵ is a small constructive worth chosen because the convergence threshold.
2.2: Selecting the Optimum Variety of Clusters
Deciding on the precise variety of clusters, okay, in Okay-Means clustering is extra artwork than science. It’s like Goldilocks looking for the mattress that’s excellent, with not too many clusters to overcomplicate issues, and never too few to oversimplify. Right here’s how yow will discover that candy spot:
The Elbow Technique
One well-liked method is the Elbow Technique. It entails working Okay-Means a number of occasions, every time with a unique variety of clusters, after which plotting the Inside-Cluster Sum of Squares (WCSS) towards the variety of clusters. WCSS measures how tight your clusters are, with decrease values indicating that factors are nearer to their respective centroids.
The method for calculating WCSS is :
Right here’s a breakdown of this method:
- okay represents the entire variety of clusters.
- Ci denotes the set of all factors belonging to cluster i.
- x is some extent inside cluster Ci.
- μi is the centroid of cluster i.
- ∥x−μi∥2 calculates the squared Euclidean distance between some extent x and the centroid μi, which quantifies how far the purpose is from the centroid.
The WCSS is actually a sum of those squared distances for all factors in every cluster, aggregated throughout all okay clusters. A decrease WCSS worth signifies that factors are on common nearer to their cluster centroids, suggesting tighter and presumably extra significant clusters.
As you enhance okay, WCSS decreases as a result of the factors are nearer to centroids. Nonetheless, there’s some extent the place including extra clusters doesn’t offer you a lot bang in your buck. This level, the place the speed of lower sharply modifications, appears to be like like an elbow on the graph. Within the graph above, the elbow level is 3, as the speed of lower slows down considerably afterward. That’s your Goldilocks okay:
Elbow level ≈ Optimum okay
The Silhouette Technique
One other strategy is the Silhouette Technique, which evaluates how comparable an object is to its cluster in comparison with different clusters. The silhouette rating ranges from -1 to 1, the place a excessive worth signifies that the article is well-matched to its cluster and poorly matched to neighboring clusters.
The method for calculating the Silhouette Rating for a single knowledge level is:
- s(i) is the silhouette rating for a single knowledge level i.
- a(i) is the common distance of information level i to the opposite factors in the identical cluster, measuring how nicely i suits into its cluster.
- b(i) is the smallest common distance of i to factors in a unique cluster, minimized over all clusters. This represents the space to the closest cluster that i will not be part of, indicating how poorly i matches its neighboring clusters.
- The rating s(i) ranges from −1−1 to 11, the place a excessive worth suggests that time i is nicely matched to its cluster and poorly matched to neighboring clusters.
Then, we take the common silhouette rating for the dataset, which is calculated by averaging the silhouette scores of all factors. In mathematical phrases:
the place N is the entire variety of factors within the dataset.
For every okay, calculate the common silhouette rating of all factors. The okay that offers you the best common silhouette rating is taken into account the optimum variety of clusters. It’s like discovering the occasion the place everybody feels they slot in greatest. Within the graph above, the best rating is given by 3 clusters.
Max common silhouette rating → Optimum okay
Okay-Means++
Means++ is an algorithm for selecting the preliminary values (or “seeds”) for the Okay-Means clustering algorithm. The usual Okay-Means algorithm begins with a random number of centroids, which may typically lead to poor convergence velocity and suboptimal clustering. Okay-Means++ addresses this by spreading out the preliminary centroids earlier than continuing with the usual Okay-Means optimization iterations.
It begins by randomly deciding on the primary centroid from the dataset. Then, for every subsequent centroid, Okay-Means++ chooses knowledge factors as new centroids with a likelihood proportional to their squared distance from the closest current centroid. This step will increase the probabilities of deciding on centroids which might be far-off from one another, lowering the probability of poor clustering. This course of is repeated till all okay centroids are chosen.
Lastly, as soon as the preliminary centroids are chosen utilizing the Okay-Means++ strategy, proceed with the usual Okay-Means algorithm to regulate the centroids and assign factors to clusters.
On this submit, I received’t delve deep into Okay-Means++ math, however count on it in a brand new submit. Within the meantime, you could possibly learn the next article for a greater understanding:
k-means++: The Benefits of Cautious Seeding
3.1 Okay-Means From Scratch in Python
As I love to do on this “Machine Studying From Scratch” sequence, let’s now recreate a less complicated model of the algorithm from scratch. Let’s first have a look at the entire code:
class KMeans:
def __init__(self, Okay, max_iters=100, tol=1e-4):
"""
Constructor for KMeans classParameters
----------
Okay : int
Variety of clusters
max_iters : int, non-obligatory
Most variety of iterations, by default 100
tol : float, non-obligatory
Tolerance to declare convergence, by default 1e-4
"""
self.Okay = Okay
self.max_iters = max_iters
self.tol = tol
self.centroids = None
self.labels = None
self.inertia_ = None
def initialize_centroids(self, X):
"""
Initialize centroids
Parameters
----------
X : array-like
Enter knowledge
Returns
-------
array-like
Preliminary centroids
"""
# Easy random initialization, take into account k-means++ for enchancment
indices = np.random.permutation(X.form[0])
centroids = X[indices[:self.K]]
return centroids
def compute_centroids(self, X, labels):
"""
Compute centroids
Parameters
----------
X : array-like
Enter knowledge
labels : array-like
Cluster labels
Returns
-------
array-like
Up to date centroids
"""
centroids = np.zeros((self.Okay, X.form[1]))
for okay in vary(self.Okay):
if np.any(labels == okay):
centroids[k] = np.imply(X[labels == k], axis=0)
else:
centroids[k] = X[np.random.choice(X.shape[0])]
return centroids
def compute_distance(self, X, centroids):
"""
Compute distances between knowledge factors and centroids
Parameters
----------
X : array-like
Enter knowledge
centroids : array-like
Centroids
Returns
-------
array-like
Distances
"""
distances = np.zeros((X.form[0], self.Okay))
for okay in vary(self.Okay):
distances[:, k] = np.linalg.norm(X - centroids[k], axis=1) ** 2
return distances
def find_closest_cluster(self, distances):
"""
Discover the closest cluster for every knowledge level
Parameters
----------
distances : array-like
Distances
Returns
-------
array-like
Cluster labels
"""
return np.argmin(distances, axis=1)
def match(self, X):
"""
Match the mannequin
Parameters
----------
X : array-like
Enter knowledge
"""
self.centroids = self.initialize_centroids(X)
for i in vary(self.max_iters):
distances = self.compute_distance(X, self.centroids)
self.labels = self.find_closest_cluster(distances)
new_centroids = self.compute_centroids(X, self.labels)
# Compute inertia (sum of squared distances)
inertia = np.sum([distances[i, label] for i, label in enumerate(self.labels)])
# Examine for convergence: if the centroids do not change a lot (inside tolerance)
if np.allclose(self.centroids, new_centroids, atol=self.tol) or inertia <= self.tol:
break
self.centroids = new_centroids
self.inertia_ = inertia
def predict(self, X):
"""
Predict the closest cluster for every knowledge level
Parameters
----------
X : array-like
Enter knowledge
Returns
-------
array-like
Cluster labels
"""
distances = self.compute_distance(X, self.centroids)
return self.find_closest_cluster(distances)
Let’s break down every a part of the category to clarify its performance:
__init__
Technique:
def __init__(self, Okay, max_iters=100, tol=1e-4):
self.Okay = Okay
self.max_iters = max_iters
self.tol = tol
self.centroids = None
self.labels = None
self.inertia_ = None
This methodology initializes a brand new occasion of the KMeans class.
Right here, the parameters are:
Okay
: The variety of clusters to type.max_iters
: The utmost variety of iterations to run the algorithm for.tol
: The convergence tolerance. If the change within the sum of squared distances of samples to their closest cluster heart (inertia) is lower than or equal to this worth, the algorithm will cease.
We additionally initialize just a few attributes to None:
self.centroids
: Shops the centroids of the clusters.self.labels
: Shops the labels of every knowledge level indicating which cluster it belongs to.self.inertia_
: Shops the sum of squared distances of samples to their closest cluster heart after becoming the mannequin.
2. initialize_centroids
and compute_centroids
Strategies:
def initialize_centroids(self, X):
# Easy random initialization, take into account k-means++ for enchancment
indices = np.random.permutation(X.form[0])
centroids = X[indices[:self.K]]
return centroidsdef compute_centroids(self, X, labels):
centroids = np.zeros((self.Okay, X.form[1]))
for okay in vary(self.Okay):
if np.any(labels == okay):
centroids[k] = np.imply(X[labels == k], axis=0)
else:
centroids[k] = X[np.random.choice(X.shape[0])]
return centroids
First, we initialize the centroids randomly from the information factors, by randomly permuting the indices of the enter knowledge and deciding on the primary Okay
because the preliminary centroids. As we talked about earlier than, a random choice is without doubt one of the potential centroid initializations, you could possibly go forward and experiment with extra strategies to see how this impacts the efficiency of the mannequin.
Then, we compute the brand new centroids because the imply of the information factors assigned to every cluster. Right here, if a cluster finally ends up with no factors, a random knowledge level from X
is chosen as the brand new centroid for that cluster.
3. compute_distance
and find_closest_cluster
Technique:
def compute_distance(self, X, centroids):
distances = np.zeros((X.form[0], self.Okay))
for okay in vary(self.Okay):
distances[:, k] = np.linalg.norm(X - centroids[k], axis=1) ** 2
return distancesdef find_closest_cluster(self, distances):
return np.argmin(distances, axis=1)
We outline the strategy to calculate the squared Euclidean distance between every knowledge level and every centroid, which returns an array the place every aspect incorporates the squared distances from an information level to all centroids.
Then, we assign every knowledge level to the closest cluster based mostly on the computed distances. The output of the operation consists of an array of labels indicating the closest cluster for every knowledge level.
4. match
and predict
Technique:
def match(self, X):
self.centroids = self.initialize_centroids(X)
for i in vary(self.max_iters):
distances = self.compute_distance(X, self.centroids)
self.labels = self.find_closest_cluster(distances)
new_centroids = self.compute_centroids(X, self.labels)
# Compute inertia (sum of squared distances)
inertia = np.sum([distances[i, label] for i, label in enumerate(self.labels)])
# Examine for convergence: if the centroids do not change a lot (inside tolerance)
if np.allclose(self.centroids, new_centroids, atol=self.tol) or inertia <= self.tol:
break
self.centroids = new_centroids
self.inertia_ = inertiadef predict(self, X):
distances = self.compute_distance(X, self.centroids)
return self.find_closest_cluster(distances)
Now we construct the core methodology of this class: the match methodology, which first initializes the centroids, and iterates as much as max_iters
occasions, the place in every iteration:
- Computes distances of all factors to the centroids.
- Assigns factors to the closest cluster.
- Computes new centroids.
- Calculates inertia (sum of squared distances to the closest centroid).
- Checks for convergence (if centroids change inside
tol
or inertia is much less or equal totol
), and stops if it has converged.
Lastly, we predict the closest cluster for every level in a brand new dataset, utilizing the predict methodology.
Yow will discover the entire code and a sensible implementation on this Jupyter Pocket book:
3.2 Implementing Okay-Means with Scikit-Be taught
Okay, now you have got a strong understanding of what the algorithm does, and you’ll recreate the algorithm from scratch. Fairly cool proper? Effectively, you received’t be utilizing that code anytime quickly, as our pal Scikit Be taught already gives a way more environment friendly implementation of Okay-Means, which solely takes just a few strains of code. Right here, we will use variations of Okay-Means solely by specifying a parameter. Let’s have a look at one implementation of it.
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs# Generate an artificial dataset
X, y_true = make_blobs(n_samples=300, facilities=3, cluster_std=0.60, random_state=0)
# Initialize and match KMeans
kmeans = KMeans(n_clusters=3, max_iter=100, tol=1e-4)
kmeans.match(X)
# Predict the cluster labels
labels = kmeans.predict(X)
# Print the cluster facilities
print("Cluster facilities:n", kmeans.cluster_centers_)
We first import KMeans from scikit-learn, and make_blobs is a perform to generate artificial datasets for clustering. We generate an artificial dataset with 300 samples, 3 facilities (clusters), and a typical deviation of 0.60 for every cluster. The random_state parameter is used to make sure that the outcomes are reproducible.
We initialize the KMeans algorithm with 3 clusters (n_clusters=3), a most of 100 iterations (max_iter=100), and a tolerance of 1e-4 (tol=1e-4). The tolerance is the brink to declare convergence — if the change within the within-cluster sum of squares (inertia) is lower than this worth, the algorithm will cease.
We match the KMeans algorithm to our knowledge utilizing the match methodology. That is the place the precise clustering occurs. We predict the cluster labels for our knowledge utilizing the predict methodology. This assigns every knowledge level to the closest cluster.
4.1 Advantages of Utilizing Okay-Means
At this level, you in all probability have an concept of why Okay-Means is so well-liked, however let’s be sure to know when to think about Okay-Means in your knowledge science journey:
Simplicity and Ease of Implementation
First off, Okay-Means is easy. It doesn’t ask for a lot, simply the information and the variety of clusters okay you’re aiming for. This simplicity makes it tremendous approachable, even for freshmen within the knowledge science discipline.
Effectivity at Scale
Okay-Means is fairly environment friendly, particularly with giant datasets. It’s bought a means of chopping via knowledge to seek out patterns while not having a supercomputer to do its factor. This effectivity makes it a sensible selection for real-world functions the place time and assets are of the essence.
Good for Pre-Processing and Simplification
The algorithm will also be an important pre-processing step. By clustering your knowledge first, you may simplify complicated issues, cut back dimensionality, and even enhance the efficiency of different algorithms that you simply would possibly run afterward.
Discovering Patterns and Insights
It may possibly assist uncover hidden buildings which may not be instantly apparent, offering worthwhile insights into the character of the information. This will inform decision-making, and technique improvement, and even result in discoveries inside the knowledge.
Simple Interpretation of Outcomes
The outcomes from Okay-Means are fairly simple to interpret. Clusters are outlined clearly, and every knowledge level is assigned to a particular group. This readability could be notably useful when explaining outcomes to stakeholders who won’t have a deep technical background.
4.2 Overcoming Okay-Means Limitations
Whereas Okay-Means clustering is a robust software for knowledge evaluation, it’s not with out its quirks and challenges. Right here’s a have a look at some frequent points and techniques for addressing them:
Sensitivity to Preliminary Centroids
One of many most important challenges with Okay-Means is that it’s fairly delicate to the preliminary placement of centroids. Random initialization can result in suboptimal clustering or totally different outcomes every time you run the algorithm.
Consider using the Okay-Means++ method for initializing centroids. It’s a better solution to begin the clustering course of, lowering the probabilities of poor outcomes by spreading out the preliminary centroids.
Mounted Variety of Clusters
Deciding on the variety of clusters okay upfront could be tough. Select unsuitable, and also you would possibly find yourself forcing your knowledge into too many or too few clusters.
As we mentioned earlier than, experimenting with strategies just like the Elbow Technique and the Silhouette Rating to discover a appropriate okay. These approaches can present extra perception into the optimum variety of clusters in your knowledge.
Issue with Non-Spherical Clusters
A spherical cluster is one the place the information factors are roughly equidistant from the cluster’s heart, leading to a form that’s, in a multidimensional area, spherical or round.
Okay-Means assumes that clusters are spherical and of comparable dimension, which isn’t all the time the case in real-world knowledge. This assumption can result in much less correct clustering when the true clusters have irregular shapes.
On this case, think about using clustering algorithms designed for complicated cluster shapes, comparable to Spectral Clustering or DBSCAN.
Sensitivity to Scale and Outliers
The efficiency of Okay-Means could be considerably affected by the dimensions of the information and the presence of outliers. Massive-scale variations between options can skew the clustering, and outliers can pull centroids away from the true cluster heart.
As traditional, make sure that to normalize the options to make sure they’re on an identical scale.
5.1 Variants of Okay-Means
The traditional Okay-Means algorithm has impressed a spread of variants designed to sort out its limitations and adapt to particular challenges or knowledge varieties. Let’s discover a few of these diversifications:
Okay-Means++
We launched it earlier than, Okay-Means++ is all about giving Okay-Means a greater start line. The principle concept right here is to decide on preliminary centroids extra strategically to enhance the probabilities of converging to an optimum answer. By spreading out the preliminary centroids, Okay-Means++ reduces the danger of poor clustering outcomes and sometimes results in sooner convergence.
k-means++: The Benefits of Cautious Seeding
Okay-Medoids or PAM (Partitioning Round Medoids)
Whereas Okay-Means focuses on minimizing the variance inside clusters, Okay-Medoids intention to reduce the sum of dissimilarities between factors labeled to be in a cluster and some extent designated as the middle of that cluster. This methodology is extra sturdy to noise and outliers as a result of medoids are precise knowledge factors, in contrast to centroids, that are the imply values of factors in a cluster.
Hyperlink to the analysis paper.
Fuzzy C-Means (FCM)
Fuzzy C-Means introduces the idea of partial membership, the place every level can belong to a number of clusters with various levels of membership. This strategy is beneficial when the boundaries between clusters should not clear-cut, permitting for a softer, extra nuanced clustering answer.
Bisecting Okay-Means
This variant adopts a “divide and conquer” technique, beginning with all factors in a single cluster and iteratively splitting clusters till the specified quantity is reached. At every step, the algorithm chooses the very best cluster to separate based mostly on a criterion, such because the one that can consequence within the largest lower within the whole sum of squared errors.
Efficiency Evaluation of Okay-Means and Bisecting Okay-Means Algorithms in Weblog Information
Regardless of its limitations, the array of methods and variants out there ensures that Okay-Means stays a flexible software in your knowledge science toolkit. Whether or not you’re tackling buyer segmentation, picture classification, or any variety of clustering duties, Okay-Means provides a place to begin that’s each accessible and highly effective.
- Jain, A. Okay., Murty, M. N., & Flynn, P. J. (1999). Information clustering: A evaluate. ACM Computing Surveys (CSUR), 31(3), 264–323.
- Arthur, D., & Vassilvitskii, S. (2007). k-means++: Some great benefits of cautious seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms (pp. 1027–1035). Society for Industrial and Utilized Arithmetic.
- MacQueen, J. (1967, June). Some strategies for classification and evaluation of multivariate observations. In Proceedings of the fifth Berkeley symposium on mathematical statistics and likelihood (Vol. 1, №14, pp. 281–297).