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

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

Задача визначення $k$-медіан полягає в пошуку таких $k$ центрів, що сформовані за ними кластери будуть «найкомпактнішими». Формально, для заданих точок даних $x_i$, $k$ центри $c_j$ слід вибрати так, щоб мінімізувати суму відстаней від кожної $x_i$ до найближчого $c_j$.

Метод іноді працює краще, ніж метод $k$-середніх, де мінімізується сума квадратів відстаней. Критерій суми відстаней широко використовується для транспортної задачі.

Ще альтернатива — метод Шаблон:Нп, у якому шукають оптимальний медоїд, а не медіану кластера (медоїд є однією з точок даних, тоді як медіани такими бути не мусять).

Див. також

• Задача про 1-центр
• Силует