Подтвердить что ты не робот

Оптимизация кластерных одномерных данных?

Есть ли у кого-нибудь документ, объясняющий, как работает Ckmeans.1d.dp?

Или: что является наиболее оптимальным способом k-означает кластеризацию в одномерном?

Ответ 1

Я думаю, что это бумага, которую вы ищете:

Ckmeans.1d.dp: Оптимальное k-значение Кластеризация в одном измерении с помощью динамического программирования by Haizhou Wang and Mingzhou Song.

Ответ 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).