- K-medians
-
В статистике и машинном обучении, k-medians[1][2] — это вариация k-means метода кластеризации, где для определения центроида кластера вместо среднего вычисляется медиана. Это соответствует минимизации ошибки по всем кластерам в метрике с 1-нормой, вместо метрики с 2-нормой для k-means.
Соответствующая проблема k-median состоит в поиске таких k центров, что сформированные по ним кластеры будут наиболее компактными. Формально, при заданных точках данных x, k центров ci должны быть выбраны так, чтобы минимизировать сумму расстояний от каждой x до ближайшего ci.
k-medians иногда работает лучше чем k-means, где минимизируется сумма квадратов расстояний. Критерий суммы расстояний широко используется для транспортных задач[3].
Обратите внимание, что этот алгоритм часто путают с медоид, а не медиану кластера. Медоид является одной из точек данных, в то время как медианы таковыми быть не обязаны.
Ссылки
- ↑ A. K. Jain and R. C. Dubes, Algorithms for Clustering Data: Prentice-Hall, 1981.
- ↑ P. S. Bradley, O. L. Mangasarian, and W. N. Street, "Clustering via Concave Minimization, " in Advances in Neural Information Processing Systems, vol. 9, M. C. Mozer, M. I. Jordan, and T. Petsche, Eds. Cambridge, MA: MIT Press, 1997, pp. 368—374.
- ↑ http://www.aladdin.cs.cmu.edu/reu/mini_probes/papers/facilitylocation.ppt
Категории:- Алгоритмы классификации
- Статистические алгоритмы
- Кластерный анализ
- Исследование операций
- Машинное обучение
- Средние величины
Wikimedia Foundation. 2010.
