Initialization

A clustering algorithm usually requires initialization before it could be started.

Seeding

Seeding is a type of clustering initialization, which provides a few seeds – points from a data set that would serve as the initial cluster centers (one for each cluster).

Each seeding algorithm implemented by Clustering.jl is a subtype of SeedingAlgorithm:

Clustering.SeedingAlgorithm — Type.

Base type for all seeding algorithms.

Each seeding algorithm should implement the two functions: initseeds! and initseeds_by_costs!.

source

Clustering.initseeds! — Function.

initseeds!(iseeds::AbstractVector{Int}, alg::SeedingAlgorithm,
           X::AbstractMatrix)

Initialize iseeds with the indices of cluster seeds for the X data matrix using the alg seeding algorithm.

Returns iseeds.

source

Clustering.initseeds_by_costs! — Function.

initseeds_by_costs!(iseeds::AbstractVector{Int}, alg::SeedingAlgorithm,
                    costs::AbstractMatrix)

Initialize iseeds with the indices of cluster seeds for the costs matrix using the alg seeding algorithm.

Here, $\mathrm{costs}_{ij}$ is the cost of assigning points $i$ and $j$ to the same cluster. One may, for example, use the squared Euclidean distance between the points as the cost.

Returns iseeds.

source

There are several seeding methods described in the literature. Clustering.jl implements three popular ones:

Clustering.KmppAlg — Type.

Kmeans++ seeding (:kmpp).

Chooses the seeds sequentially. The probability of a point to be chosen is proportional to the minimum cost of assigning it to the existing seeds.

D. Arthur and S. Vassilvitskii (2007). k-means++: the advantages of careful seeding. 18th Annual ACM-SIAM symposium on Discrete algorithms, 2007.

source

Clustering.KmCentralityAlg — Type.

K-medoids initialization based on centrality (:kmcen).

Choose the $k$ points with the highest centrality as seeds.

Hae-Sang Park and Chi-Hyuck Jun. A simple and fast algorithm for K-medoids clustering. doi:10.1016/j.eswa.2008.01.039

source

Clustering.RandSeedAlg — Type.

Random seeding (:rand).

Chooses an arbitrary subset of $k$ data points as cluster seeds.

source

For convenience, the package also defines the two wrapper methods that take the name of the seeding algorithm and the number of clusters and take care of allocating iseeds and applying the proper SeedingAlgorithm instance:

Clustering.initseeds — Function.

initseeds(alg::Union{SeedingAlgorithm, Symbol},
          X::AbstractMatrix, k::Integer)

Select k seeds from a $d×n$ data matrix X using the alg algorithm.

alg could be either an instance of SeedingAlgorithm or a symbolic name of the algorithm.

Returns an integer vector of length k that contains the indices of chosen seeds.

source

Clustering.initseeds_by_costs — Function.

initseeds_by_costs(alg::Union{SeedingAlgorithm, Symbol},
                   costs::AbstractMatrix, k::Integer)

Select k seeds from the $n×n$ costs matrix using algorithm alg.

Here, $\mathrm{costs}_{ij}$ is the cost of assigning points $i$ and $j$ to the same cluster. One may, for example, use the squared Euclidean distance between the points as the cost.

Returns an integer vector of length k that contains the indices of chosen seeds.

source

In practice, we found that Kmeans++ is the most effective seeding method. To simplify its usage we provide:

Clustering.kmpp — Function.

kmpp(X, k)

Use Kmeans++ to choose k seeds from the $d×n$ data matrix X.

source

Clustering.kmpp_by_costs — Function.

kmpp_by_costs(C, k)

Use Kmeans++ to choose k seeds based on the $n×n$ cost matrix C.

source