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

· 6: Conclusion

· Bibliography

1.1: What’s Okay-Means Clustering?

Think about you’re at a farmer’s market with a bunch of fruits and veggies that you have to type out. You wish to manage them so all of the apples, oranges, and carrots are hanging out with their sort. This job is quite a bit like what Okay-Means Clustering does in information science.

So, what’s Okay-Means Clustering? It’s a method used to naturally group information. Consider it as a solution to type unlabeled information into completely different teams or clusters. Every cluster is a bunch of knowledge factors which can 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 needs to be.

1.2: How Does Okay-Means Work?

Now, take into account the farmer’s market instance, and let’s attempt to dive deep a bit extra into Okay-means mechanisms.

Consider Okay-Means as establishing the preliminary fruit stands (centroids) in our market. It randomly picks a couple of spots (information factors) to position these stands. The variety of stands you resolve to arrange is the “Okay” in Okay-Means, and this quantity is dependent upon what number of various kinds of produce (teams) you suppose you may have.

Now, Okay-Means takes every fruit and veggie (information level) and figures out which stand (centroid) it belongs to primarily based 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 one of the best spots. It does this by discovering a brand new spot for every stand primarily based on the typical 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 verify they’re really 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 distinct stand in the event that they discover one nearer, and the stands would possibly shift positions to raised characterize 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 each piece of produce is of its sort.

What you find yourself with are properly organized stands (clusters) with fruits and veggies grouped round them. Every stand represents a kind of produce, displaying you the way your market (information) might be divided into distinct sections (classes) primarily based 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 gap 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 ok preliminary centroids (μ1​,μ2​,…,μk​) from the dataset. This may be completed randomly or extra strategically with strategies like Okay-Means++, which we’ll cowl later.

Whereas no particular components 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’ll information you thru one of the best ideas to decide on the optimum ok.

Step 2: Project of Factors to Closest Centroid
NeXT, each information level x is assigned to the closest centroid, forming ok clusters, the place the “nearest” centroid is set by the minimal distance between the purpose and all centroids.

Right here, the gap 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 can discover its software with extra distances. Nonetheless, remember that Euclidean distance is normally the steered selection for optimum efficiency, whereas different variances of the algorithm are extra versatile to completely different distance strategies. Take a look at the subsection 2.1 of my earlier article about Okay-Nearest Neighbors to know extra about distance strategies:

Preserving 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 primarily based 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 ok clusters.
• d(x,μi​): This calculates the gap between the purpose x and the centroid μi​ of cluster Ci​. The centroid is actually the imply place of all of the factors presently in cluster Ci​.
• d(x,μj​): This calculates the gap between the purpose x and the centroid μj​ of some other cluster Cj​.
• ok: That is the entire variety of clusters the algorithm is making an attempt to partition the info into.

The situation d(x,μi​) ≤ d(x,μj​) ∀ j, 1≤j≤ok specifies {that a} level x is assigned to the cluster Ci​ if and provided that the gap 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 ok.

In easier phrases, the components says:

Take 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 attainable.

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 middle 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 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 components for convergence that applies in all instances. As an alternative, convergence is set primarily based on the algorithm’s habits over successive iterations, particularly whether or not the centroids of the clusters cease altering considerably.

Nonetheless, a typical 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 adjustments within the centroid positions or the WCSS. If the change falls beneath this threshold from one iteration to the subsequent, the algorithm might 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 proper variety of clusters, ok, 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 you will discover that candy spot:

The Elbow Methodology
One in style method is the Elbow Methodology. It includes working Okay-Means a number of instances, every time with a distinct variety of clusters, after which plotting the Inside-Cluster Sum of Squares (WCSS) in opposition to the variety of clusters. WCSS measures how tight your clusters are, with decrease values indicating that factors are nearer to their respective centroids.

The components for calculating WCSS is :

Right here’s a breakdown of this components:

• ok 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 ok clusters. A decrease WCSS worth signifies that factors are on common nearer to their cluster centroids, suggesting tighter and probably extra significant clusters.

As you improve ok, WCSS decreases as a result of the factors are nearer to centroids. Nonetheless, there’s some extent the place including extra clusters doesn’t provide you with a lot bang to your buck. This level, the place the speed of lower sharply adjustments, 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 ok:

Elbow level ≈ Optimum ok

The Silhouette Methodology
One other method is the Silhouette Methodology, 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 item is well-matched to its cluster and poorly matched to neighboring clusters.

The components for calculating the Silhouette Rating for a single information level is:

• s(i) is the silhouette rating for a single information level i.
• a(i) is the typical distance of knowledge level i to the opposite factors in the identical cluster, measuring how properly i matches into its cluster.
• b(i) is the smallest common distance of i to factors in a distinct cluster, minimized over all clusters. This represents the gap to the closest cluster that i just isn’t 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 properly matched to its cluster and poorly matched to neighboring clusters.

Then, we take the typical 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 ok, calculate the typical silhouette rating of all factors. The ok that offers you the very best common silhouette rating is taken into account the optimum variety of clusters. It’s like discovering the get together the place everybody feels they slot in greatest. Within the graph above, the very best rating is given by 3 clusters.

Max common silhouette rating → Optimum ok

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 end in poor convergence pace 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 information factors as new centroids with a likelihood proportional to their squared distance from the closest present centroid. This step will increase the possibilities of deciding on centroids which can be distant from one another, decreasing the chance of poor clustering. This course of is repeated till all ok centroids are chosen.

Lastly, as soon as the preliminary centroids are chosen utilizing the Okay-Means++ method, proceed with the usual Okay-Means algorithm to regulate the centroids and assign factors to clusters.

On this publish, I gained’t delve deep into Okay-Means++ math, however count on it in a brand new publish. Within the meantime, you can 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 an easier model of the algorithm from scratch. Let’s first take a look at the entire code:

class KMeans:
def __init__(self, Okay, max_iters=100, tol=1e-4):
"""
Constructor for KMeans class
Parameters
----------
Okay : int
Variety of clusters
max_iters : int, elective
Most variety of iterations, by default 100
tol : float, elective
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 information
Returns
-------
array-like
Preliminary centroids
"""
# Easy random initialization, contemplate 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 information
labels : array-like
Cluster labels
Returns
-------
array-like
Up to date centroids
"""
centroids = np.zeros((self.Okay, X.form[1]))
for ok in vary(self.Okay):
if np.any(labels == ok):
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 information factors and centroids
Parameters
----------
X : array-like
Enter information
centroids : array-like
Centroids
Returns
-------
array-like
Distances
"""
distances = np.zeros((X.form[0], self.Okay))
for ok 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 information 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 information
"""
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 information level
Parameters
----------
X : array-like
Enter information
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:

1. __init__ Methodology:

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 technique initializes a brand new occasion of the KMeans class.

Right here, the parameters are:

• Okay: The variety of clusters to kind.
• 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 middle (inertia) is lower than or equal to this worth, the algorithm will cease.

We additionally initialize a couple of attributes to None:

• self.centroids: Shops the centroids of the clusters.
• self.labels: Shops the labels of every information level indicating which cluster it belongs to.
• self.inertia_: Shops the sum of squared distances of samples to their closest cluster middle after becoming the mannequin.

2. initialize_centroids and compute_centroids Strategies:

def initialize_centroids(self, X):
# Easy random initialization, contemplate k-means++ for enchancment
indices = np.random.permutation(X.form[0])
centroids = X[indices[:self.K]]
return centroids
def compute_centroids(self, X, labels):
centroids = np.zeros((self.Okay, X.form[1]))
for ok in vary(self.Okay):
if np.any(labels == ok):
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 info factors, by randomly permuting the indices of the enter information and deciding on the primary Okay because the preliminary centroids. As we talked about earlier than, a random choice is likely one of the attainable centroid initializations, you can go forward and experiment with extra methods to see how this impacts the efficiency of the mannequin.

Then, we compute the brand new centroids because the imply of the info factors assigned to every cluster. Right here, if a cluster finally ends up with no factors, a random information level from X is chosen as the brand new centroid for that cluster.

3. compute_distance and find_closest_clusterMethodology:

def compute_distance(self, X, centroids):
distances = np.zeros((X.form[0], self.Okay))
for ok in vary(self.Okay):
distances[:, k] = np.linalg.norm(X - centroids[k], axis=1) ** 2
return distances
def find_closest_cluster(self, distances):
return np.argmin(distances, axis=1)

We outline the tactic to calculate the squared Euclidean distance between every information level and every centroid, which returns an array the place every component incorporates the squared distances from a knowledge level to all centroids.

Then, we assign every information level to the closest cluster primarily based on the computed distances. The output of the operation consists of an array of labels indicating the closest cluster for every information level.

4. match and predict Methodology:

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_ = inertia
def predict(self, X):
distances = self.compute_distance(X, self.centroids)
return self.find_closest_cluster(distances)

Now we construct the core technique of this class: the match technique, which first initializes the centroids, and iterates as much as max_iters instances, 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 to tol), and stops if it has converged.

Lastly, we predict the closest cluster for every level in a brand new dataset, utilizing the predict technique.

You 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 may have a strong understanding of what the algorithm does, and you’ll recreate the algorithm from scratch. Fairly cool proper? Nicely, you gained’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 a couple of strains of code. Right here, we will use variations of Okay-Means solely by specifying a parameter. Let’s take 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 normal 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 information utilizing the match technique. That is the place the precise clustering occurs. We predict the cluster labels for our information utilizing the predict technique. This assigns every information level to the closest cluster.

4.1 Advantages of Utilizing Okay-Means

At this level, you in all probability have an thought of why Okay-Means is so in style, however let’s be sure to know when to think about Okay-Means to your information science journey:

Simplicity and Ease of Implementation
First off, Okay-Means is easy. It doesn’t ask for a lot, simply the info and the variety of clusters ok you’re aiming for. This simplicity makes it tremendous approachable, even for rookies within the information science area.

Effectivity at Scale
Okay-Means is fairly environment friendly, particularly with massive datasets. It’s obtained a method of chopping by way of information to seek out patterns without having a supercomputer to do its factor. This effectivity makes it a sensible selection for real-world functions the place time and sources are of the essence.

Good for Pre-Processing and Simplification
The algorithm can be an ideal pre-processing step. By clustering your information 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 could assist uncover hidden constructions which may not be instantly apparent, offering helpful insights into the character of the info. This could inform decision-making, and technique growth, and even result in discoveries throughout the information.

Simple Interpretation of Outcomes
The outcomes from Okay-Means are fairly simple to interpret. Clusters are outlined clearly, and every information level is assigned to a particular group. This readability might be notably helpful when explaining outcomes to stakeholders who may not have a deep technical background.

4.2 Overcoming Okay-Means Limitations

Whereas Okay-Means clustering is a robust device for information evaluation, it’s not with out its quirks and challenges. Right here’s a take a look at some frequent points and techniques for addressing them:

Sensitivity to Preliminary Centroids
One of many foremost challenges with Okay-Means is that it’s fairly delicate to the preliminary placement of centroids. Random initialization can result in suboptimal clustering or completely different outcomes every time you run the algorithm.

Consider using the Okay-Means++ method for initializing centroids. It’s a wiser solution to begin the clustering course of, decreasing the possibilities of poor outcomes by spreading out the preliminary centroids.

Fastened Variety of Clusters
Deciding on the variety of clusters ok prematurely might be tough. Select fallacious, and also you would possibly find yourself forcing your information into too many or too few clusters.

As we mentioned earlier than, experimenting with strategies just like the Elbow Methodology and the Silhouette Rating to discover a appropriate ok. These approaches can present extra perception into the optimum variety of clusters to your information.

Issue with Non-Spherical Clusters

A spherical cluster is one the place the info factors are roughly equidistant from the cluster’s middle, leading to a form that’s, in a multidimensional house, spherical or round.

Okay-Means assumes that clusters are spherical and of comparable measurement, which isn’t all the time the case in real-world information. 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, equivalent to Spectral Clustering or DBSCAN.

Sensitivity to Scale and Outliers
The efficiency of Okay-Means might be considerably affected by the dimensions of the info and the presence of outliers. Giant-scale variations between options can skew the clustering, and outliers can pull centroids away from the true cluster middle.

As regular, ensure that to normalize the options to make sure they’re on an analogous scale.

5.1 Variants of Okay-Means

The traditional Okay-Means algorithm has impressed a variety of variants designed to sort out its limitations and adapt to particular challenges or information varieties. Let’s discover a few of these variations:

Okay-Means++
We launched it earlier than, Okay-Means++ is all about giving Okay-Means a greater start line. The principle thought right here is to decide on preliminary centroids extra strategically to enhance the possibilities 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 attenuate the sum of dissimilarities between factors labeled to be in a cluster and some extent designated as the middle of that cluster. This technique is extra sturdy to noise and outliers as a result of medoids are precise information 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 method is helpful when the boundaries between clusters usually are 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 one of the best cluster to separate primarily based on a criterion, such because the one that can outcome within the largest lower within the complete 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 device in your information science toolkit. Whether or not you’re tackling buyer segmentation, picture classification, or any variety of clustering duties, Okay-Means affords a place to begin that’s each accessible and highly effective.

1. Jain, A. Okay., Murty, M. N., & Flynn, P. J. (1999). Information clustering: A evaluate. ACM Computing Surveys (CSUR), 31(3), 264–323.
2. 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.
3. 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).