Details

Given the set of

n

p

-dimensional feature vectors and a positive integer

k

, the problem is to find a set of

k

p

-dimensional vectors that minimize the objective function (overall error)

where is the distance from to the closest center in

C

, such as the Euclidean distance. The vectors are called centroids. To start computations, the algorithm requires initial values of centroids.

Choice of first
k
feature vectors from the data set
X
.
Random choice of
k
feature vectors from the data set using the following simple random sampling draw-by-draw algorithm. The algorithm does the following:
Chooses one of the feature vectors from
X
with equal probability.
Excludes from
X
and adds it to the current set of centers.
Resumes from step 1 until the set of centers reaches the desired size
k
.
K-Means++ algorithm [Arthur2007], which selects centers with the probability proportional to their contribution to the overall error according to the following scheme:
Chooses one of the feature vectors from
X
with equal probability.
Excludes from
X
and adds it to the current set of centers
C
.
For each feature vector in
X
calculates its minimal distance from the current set of centers
C
.
Chooses one of the feature vectors from
X
with the probability .
Resumes from step 2 until the set of centers
C
reaches the desired size
k
.
Parallel K-Means++ algorithm [Bahmani2012] that does the following:
Chooses one of the feature vectors from
X
with equal probability.
Excludes from
X
and adds it to the current set of centers
C
.
Repeats
nRounds
times:
For each feature vector from
X
calculates its minimal distance from the current set of centers
C
.
Chooses feature vectors from
X
with the probability .
Excludes vectors chosen in the previous step from
X
and adds them to the current set of centers
C
.
For sets to the ratings, the number of points in
X
closer to than to any other point in
C
.
Applies K-Means++ algorithm with weights to the points in
C
, which means that the following probability is used in step:

The algorithm parameters define the number of candidates
L
selected in each round and number of rounds:
Choose
oversamplingFactor
to make .
Choose nRounds as , where is the estimation of the goal function when the first center is chosen. [Bahmani2012] recommends to set
nRounds
to a constant value not greater than
8
.

Computation of the goal function includes computation of the Euclidean distance between vectors . The algorithm uses the following modification of the Euclidean distance between feature vectors

a

and

b

: , where is computed for continuous features as

and is computed for binary categorical features as

In these equations, γ weighs the impact of binary categorical features on the clustering, is the number of continuous features, and is the number of binary categorical features. Note that the algorithm does not support non-binary categorical features.

The K-Means clustering algorithm computes centroids using Lloyd’s method [Lloyd82]. For each feature vector , you can also compute the index of the cluster that contains the feature vector.

Feature vectors, most distant from their assigned centroids, are selected as the new cluster centers. Information about these vectors is gathered automatically during the algorithm execution.
In the distributed processing mode, most distant vectors from the local nodes are computed (Step 1), stored in
PartialResult
, and collected on the master node (Step 2). For more details, see the
PartialResult
description at Step 1 [Tan2005].

Initialization

Batch Processing
Distributed Processing

Computation

Batch Processing
Distributed Processing

Examples

kmeans_init_dense.cpp
kmeans_lloyd_dense_batch.cpp

kmeans_lloyd_dense_batch.cpp
kmeans_init_dense.cpp

kmeans_dense_batch.cpp
kmeans_csr_batch.cpp

kmeans_dense_distr.cpp
kmeans_csr_distr.cpp

KMeansDenseBatch.java
KMeansCSRBatch.java

KMeansDenseDistr.java
KMeansCSRDistr.java

kmeans_batch.py

kmeans_batch.py

kmeans_spmd.py

Performance Considerations

If input data is homogeneous, provide the input data and store results in homogeneous numeric tables of the same type as specified in the algorithmFPType class template parameter.
If input data is non-homogeneous, use AOS layout rather than SOA layout.
For the output assignments table, use a homogeneous numeric table of the int type.