К-медианы кластеризации - K-medians clustering

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

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

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

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

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

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

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

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

Смотрите также

Рекомендации

  1. ^ А. К. Джайн и Р. К. Дубес, Алгоритмы кластеризации данных. Прентис-Холл, 1988.
  2. ^ П. С. Брэдли, О. Л. Мангасарян и У. Н. Стрит, «Кластеризация посредством вогнутой минимизации», в «Достижения в системах обработки нейронной информации», т. 9, M. C. Mozer, M. I. Jordan, T. Petsche, Eds. Кембридж, Массачусетс: MIT Press, 1997, стр. 368–374.