Selected clustering algorithms
implementation details

This page includes a brief description and source codes of selected clustering algorithms mostly from [Fränti2006]. The algorithms have been selected so that they represent the best ones in the class of iterative and hierarchical algorithms, or they are popular due to their simplicity of other reasons. Among GMM models, the EM algorithm has also been included.

	Documentation	Implementation	Recommended parameters
Random		C*	-c -n1
Repeated K-means	[DH73]	C*	-r10
SOM	[Nasra88]	C*	-b2 -i1000 -r10,1
PNN	[Fränti2000b]	C*   pseudocode
SPLIT	[Fränti1997a]	C*	-g0 -e6 -h2,0 -l
SM	[Kauko1998]	C*	-e6 -h2,1 -l -d -g2 -i999 -a0,(size)**
RS	[Fränti2000a]	C*   pseudocode	-t2500
GA	[Fränti2000c]	C*   pseudocode	-z10 -n0 -g2
FCM	[Dunn1974]	C++	-g200 -f10
EM (GMM)	[McLachlan2001]	C++	-r 10,10,yes

* For compiling VQ methods you need modules package.
** Use the same value as the codebook size.
*** All methods require also the codebook size as parameter (usually -s)

Random: A trivial method for modeling the data is to construct the codebook from K randomly chosen data vectors. The random codebook will be used as the initial solution for the iterative algorithms described below, but also as a reference solution for measuring the quality the clustering algorithms. A good clustering algorithm should produce significantly better codebook than the random selection.

Repeated K-means: K-means [McQueen] starts from any initial solution, which is then iteratively improved by two optimization steps as long as improvement is achieved. The method is known as LBG (Linde-Buzo-Gray) or GLA (Generalized Lloyd Algorithm) in vector quantization literature [LBG80]. Since the quality of the K-means is sensitive for the initial solution, we apply the method repeatedly each time starting from a new random initial solution [DH73]. The codebook providing the smallest MSE is retained as the final solution. We use the fast reduced-search variant of the K-means [Kauko2000].

SOM: Self-organizing map [Nasra88] is a neural network approach to the clustering problem. The neurons in the network are connected with a 1-D or 2-D structure, and they correspond to the code vectors. Each feature vector is fed to the network by finding the nearest code vector. The best matched code vector and its neighboring vectors in the network are updated by moving them towards the input vector. After processing the training set by a predefined number of times, the neighborhood size is shrunk. The entire process is repeated until the neighborhood size shrinks to zero.

PNN: Pairwise nearest neighbor [Equitz89] [Fränti2000b] generates the codebook hierarchically. It starts by initializing each feature vector as a separate code vector. Two code vectors are merged at each step of the algorithm and the process is repeated until the desired size of the codebook is obtained. The code vectors to be merged are always the ones whose merge increase the distortion least. We recommend the fast exact PNN method introduced in [Fränti2000b]. Its main benefits are the simplicity of implementation and reasonably good quality of the clustering result.

SPLIT: An opposite, top-down approach starts with a single cluster including all the feature vectors. New clusters are then created one at a time by dividing the existing clusters. The splitting process is repeated until the desired number of clusters is reached. This approach usually requires much less computation than the PNN. We use the method in [Fränti1997a] that always selects the optimal hyperplane dividing the particular cluster along its principal axis, augmented with a local repartitioning phase at each division step. This SPLIT variant gives comparable results to that of the PNN but with a much faster algorithm at the cost of significantly more complicated implementation.

SM: Split-and-Merge [Kauko1998] is an iterative method that modifies the codebook by a series of split and merge operations. At every step, the code vectors to be split and merged are chosen as the ones that provides best improvement (split), or least increase (merge) in the distortion. The method provides high quality codebooks but with a significantly more complex implementation than the other methods.

RS: Random Swap [Fränti2000a] algorithm starts with a random codebook, which is then iteratively improved. At every step, a randomly selected code vector is tentatively re-allocated to a randomly chosen training vector. The new candidate codebook is fine-tuned by two iterations of K-means, the solution is then evaluated and accepted if it improves the previous solution. The algorithm is iterated for a fixed number of iterations. This trial-and-error approach is simple to implement and surprisingly effective. The efficiency of the method has been studied in [Fränti2008].

FCM: Fuzzy C-means [Dunn1974] generalizes K-means to fuzzy clustering, in which data vectors can belong to several partitions at the same time with a given weight. Traditional K-means is then applied in the final step in order to obtain the centroids (codebook) from the fuzzy partitions.

GA: Genetic algorithm [Fränti1997b] [Fränti2000c] generates a set of solutions (called population) and evolves it using the survival of the fittest principle. PNN is used as the crossover to generate new candidates, which are further fine-tuned by k-means. The algorithm has outperformed so far every competitive clustering algorithm for more than a decade already. Slightly better results have been reported only by other (more complicated) GA variants [Kivijarvi2003] [Fränti2006]. It therefore serves as a reference point as how good one can do with cluster model.

GMM: Expectation-Maximization (EM) algorithm [Bishop96] [McLachlan2001] is used for training Gaussian Mixture Model (GMM) as described in [Reynolds95]. Initial guess is made for the model parameters, and the solution is then improved by two optimization steps similarly as in K-means. Since the EM algorithm is also sensitive for the initialization, it is recommended to start it repeatedly from a new random solution, which is first fine-tuned by K-means. The result providing the highest likelihood is retained as the final model. In the implementation, diagonal covariances is used instead of the full covariance matrices. This is more common variant in speech and speaker recognition applications because much less training data is required and it is computationally much more efficient because full covariance matrix would require inversions.

References