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

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

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

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

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