k -медиан кластеризация

В статистике - медиан k кластеризация ^[1]^[2] — алгоритм кластерного анализа . Это разновидность k кластеризации -средних , при которой вместо вычисления среднего значения для каждого кластера для определения его центроида вычисляется медиана . Это приводит к минимизации ошибки во всех кластерах по отношению к метрике расстояния 2- нормы , в отличие от метрики расстояния в квадрате 2-нормы (что делает k -means ).

Это имеет прямое отношение к k проблеме -медианы , которая представляет собой задачу нахождения k центров таких, чтобы образуемые ими кластеры были наиболее компактными по отношению к 2-норме. Формально, учитывая набор точек данных x , k центров c _i должны быть выбраны так, чтобы минимизировать сумму расстояний от каждого x до ближайшего c _i .

Сформулированная таким образом целевая функция иногда является лучшим критерием, чем критерий, используемый в k алгоритме кластеризации -средних , в котором используется сумма квадратов расстояний. Сумма расстояний широко используется в таких приложениях, как задача определения местоположения объекта .

Предложенный алгоритм использует итерацию в стиле Ллойда, которая чередует этап ожидания (E) и шаг максимизации (M), что делает его алгоритмом ожидания-максимизации . На этапе E всем объектам присваивается ближайшая медиана. На этапе M медианы пересчитываются с использованием медианы в каждом отдельном измерении.

Медианы и медоиды

Медиана вычисляется в каждом отдельном измерении в -медиан с использованием манхэттенского расстояния формулировке проблемы k , поэтому отдельные атрибуты будут взяты из набора данных (или будут средними из двух значений из набора данных). Это делает алгоритм более надежным для дискретных или даже двоичных наборов данных. Напротив, использование средних значений или медиан евклидова расстояния не обязательно приведет к получению отдельных атрибутов из набора данных. Даже при использовании формулировки манхэттенского расстояния отдельные атрибуты могут происходить из разных экземпляров набора данных; таким образом, результирующая медиана может не быть членом входного набора данных.

Этот алгоритм часто путают с алгоритмом k -medoids . Однако медоид должен быть реальным экземпляром из набора данных, в то время как для многомерной медианы Манхэттенского расстояния это справедливо только для значений одного атрибута. Таким образом, фактическая медиана может представлять собой комбинацию нескольких экземпляров. Например, для векторов (0,1), (1,0) и (2,2) медиана манхэттенского расстояния равна (1,1), которая не существует в исходных данных и, следовательно, не может быть медоид.

Программное обеспечение

ELKI включает в себя различные варианты k-средних, включая k-медианы.
ФОРТРАН кммедианы
GNU R включает k-медианы в пакет «flexclust».
Стата кммедианы

См. также

Ссылки

^ AK Jain и RC Dubes, Алгоритмы кластеризации данных . Прентис-Холл, 1988.
^ PS Брэдли, О.Л. Мангасарян и У.Н. Стрит, «Кластеризация посредством вогнутой минимизации», в «Достижениях в области нейронных систем обработки информации», том. 9, М. К. Мозер, М. И. Джордан и Т. Петше, ред. Кембридж, Массачусетс: MIT Press, 1997, стр. 368–374.

[1] AK Jain и RC Dubes, Алгоритмы кластеризации данных . Прентис-Холл, 1988.

[2] PS Брэдли, О.Л. Мангасарян и У.Н. Стрит, «Кластеризация посредством вогнутой минимизации», в «Достижениях в области нейронных систем обработки информации», том. 9, М. К. Мозер, М. И. Джордан и Т. Петше, ред. Кембридж, Массачусетс: MIT Press, 1997, стр. 368–374.

[1]

[2]