The general clustering algorithms do not guarantee optimality because of the hardness of the problem. Polynomial-time methods can find the clustering corresponding to the exact optimum only in special cases. For example, the dynamic programming algorithm can solve the one-dimensional clustering problem, i.e., when the items to be clustered can be characterised by only one scalar number. Optimal one-dimensional clustering is provided by package Ckmeans.1d.dp in R. The paper shows a possible generalisation of the method implemented in this package to multidimensional data: the dynamic programming method can be applied to find the optimum clustering of vectors when only subsequent items may form a cluster. Sequential data are common in various fields including telecommunication, bioinformatics, marketing, transportation etc. The proposed algorithm can determine the optima for a range of cluster numbers in order to support the case when the number of clusters is not known in advance.
Text and figures are licensed under Creative Commons Attribution CC BY 4.0. The figures that have been reused from other sources don't fall under this license and can be recognized by a note in their caption: "Figure from ...".
For attribution, please cite this work as
Szkaliczki, "clustering.sc.dp: Optimal Clustering with Sequential Constraint by Using Dynamic Programming", The R Journal, 2016
BibTeX citation
@article{RJ-2016-022,
author = {Szkaliczki, Tibor},
title = {clustering.sc.dp: Optimal Clustering with Sequential Constraint by Using Dynamic Programming},
journal = {The R Journal},
year = {2016},
note = {https://doi.org/10.32614/RJ-2016-022},
doi = {10.32614/RJ-2016-022},
volume = {8},
issue = {1},
issn = {2073-4859},
pages = {318-327}
}