Ответ 1
Я думаю, что это бумага, которую вы ищете:
Оптимизация кластерных одномерных данных?
Есть ли у кого-нибудь документ, объясняющий, как работает Ckmeans.1d.dp?
Или: что является наиболее оптимальным способом k-означает кластеризацию в одномерном?
Ответы
Ответ 2
Это очень старая техника от Беллмана: Замечание о кластерном анализе и динамическом программировании http://www.sciencedirect.com/science/article/pii/0025556473900072
www.informationgeometry.org
Ответ 3
Одномерная кластеризация k-значений может быть решена в O (kn) времени (на уже отсортированном входе) на основе теоретических результатов по матрицам Монжа, но этот подход не был популярным, скорее всего, из-за численной нестабильности, а также, возможно, для задач кодирования.
Лучшим вариантом является метод O (knlgn), который теперь реализован в Ckmeans.1d.dp версии 3.4.6. Эта реализация выполняется так же быстро, как эвристическое k-средство, но обеспечивает гарантированную оптимальность, на порядок лучше эвристического k-средства, особенно для больших k.
Общее решение динамического программирования Ричардом Беллманом (Richard Bellman, 1973) не затрагивает специфику проблемы k-средних, а подразумеваемая среда выполнения O (kn ^ 3).