The R Journal: article published in 2016, volume 8:1 Optimal Clustering with Sequential Constraint by Using Dynamic Programming PDF download
Tibor Szkaliczki , The R Journal (2016) 8:1, pages 318-327.

Abstract 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.

Received: 2015-12-09; online 2016-05-01
CRAN packages: Ckmeans.1d.dp,

CC BY 4.0
This article is licensed under a Creative Commons Attribution 3.0 Unported license .

  author = {Tibor Szkaliczki},
  title = {{ Optimal Clustering with Sequential
          Constraint by Using Dynamic Programming}},
  year = {2016},
  journal = {{The R Journal}},
  doi = {10.32614/RJ-2016-022},
  url = {},
  pages = {318--327},
  volume = {8},
  number = {1}