RFC: add support for fast univariate clustering using dynamic programming (CKMean.1d.dp)

[loretoparisi]

Checklist

Please ensure the following tasks are completed before submitting a feature request.

• Read and understood the Code of Conduct.
• Searched for existing issues and pull requests.
• The issue name begins with RFC:.

Description

Description of the feature request.

Add an implementation for fast univariate clustering using dynamic programming and guaranteed optimality.

Related Issues

Does this feature request have any related issues?

No.

Questions

Any questions for reviewers?

No.

Other

Any other information relevant to this feature request? This may include screenshots, references, sample output, and/or implementation notes.

• https://journal.r-project.org/archive/2011-2/RJournal_2011-2_Wang+Song.pdf
• https://cran.r-project.org/web/packages/Ckmeans.1d.dp/Ckmeans.1d.dp.pdf
• https://github.com/schnerd/ckmeans

[kgryte]

@loretoparisi So we have a bit more background and motivation, what is your use case for this algorithm?

[kgryte]

One issue with this algorithm is that we can only reference the research paper and not the implementation, as the implementation is licensed under GPL. We would also need to confirm the license terms of algorithms included in the research paper.

[loretoparisi]

@kgryte well I'm using in a machine learning context when it's better to use 1d k-means basically or in combination with multi-variate k-means.

[kgryte]

You have an example dataset you have in mind?

[kgryte]

What I am after is getting a sense of general applicability and broader need. Meaning, should a univariate clustering algorithm be bumped up in our priority list, given our other ongoing efforts.

[loretoparisi]

@kgryte I understand. Well there is a wide range of applications like Time Series, Feature Selections, etc. In my case I'm using this something like this

• Feature Selections with Univariate Clustering - https://pdfs.semanticscholar.org/f116/7e2e1fa07cdf432c10beb373e07efd6a5e58.pdf