Метод k-медиан

Метод ${\displaystyle k}$-медиан^[1][2] — применяемая в статистике и машинном обучении вариация метода ${\displaystyle k}$-средних для задач кластеризации, где для определения центроида кластера вместо среднего вычисляется медиана. Такой подход соответствует минимизации ошибки по всем кластерам в метрике с 1-нормой, вместо метрики с 2-нормой, используемой в стандартном методе ${\displaystyle k}$-средних.

Задача определения ${\displaystyle k}$-медиан состоит в поиске таких ${\displaystyle k}$ центров, что сформированные по ним кластеры будут наиболее «компактными». Формально, при заданных точках данных ${\displaystyle x_{i}}$, ${\displaystyle k}$ центров ${\displaystyle c_{j}}$ должны быть выбраны так, чтобы минимизировать сумму расстояний от каждой ${\displaystyle x_{i}}$ до ближайшего ${\displaystyle c_{j}}$.

Метод иногда работает лучше, чем метод ${\displaystyle k}$-средних, где минимизируется сумма квадратов расстояний. Критерий суммы расстояний широко используется для транспортных задач^[3].

Ещё альтернатива — метод ${\displaystyle k}$-медоидов, в котором ищут оптимальный медоид, а не медиану кластера (медоид является одной из точек данных, в то время как медианы таковыми быть не обязаны).