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

Ме́тод ${\displaystyle k}$-медіа́н — застосовувана в статистиці і машинному навчанні варіація методу ${\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}$-середніх, де мінімізується сума квадратів відстаней. Критерій суми відстаней широко використовується для транспортної задачі.

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

Див. також

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

Посилання

1. A. K. Jain and R. C. Dubes, Algorithms for Clustering Data: Prentice-Hall, 1981.
2. 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.
3. . Архів оригіналу за 3 квітня 2022. Процитовано 14 березня 2022.{{}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title ()