К-средних

К-средних

k-means (иногда называемый k-средних) - наиболее популярный метод кластеризации. Алгоритм представляет собой модификацию EM-алгоритма для разделения смеси гауссиан. Он разбивает множество элементов векторного пространства на заранее известное число кластеров k. Действие алгоритма таково, что он стремится минимизировать среднеквадратичное отклонение на точках каждого кластера:

V = \sum_{i=1}^{k} \sum_{x_j \in S_i} (x_j - \mu_i)^2

где k - число кластеров, Si - полученные кластеры, i = 1, 2, \dots, k и μi - центры масс векторов x_j \in S_i.

Основная идея заключается в том, что на каждой итерации перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем векторы разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе по выбраной метрике. Алгоритм завершается, когда на какой-то итерации не происходит изменения кластеров.

Как показали Д.Артур и С.Вассилвицкий, на некоторых классах множеств сложность алгоритма по времени, нужному для сходимости, равна 2^{\Omega(\sqrt{n})}.[1]

Содержание

Демонстрация алгоритма

Действие алгоритма в двумерном случае. Начальные точки выбраны случайно.

Исходные точки и случайно выбранные начальные точки.
Точки, отнесённые к начальным центрам.
Вычисление новых центров кластеров.
Предыдущие шаги повторяются, пока алгоритм не сойдётся.

Проблемы k-means

  • непонятно, как выбирать исходные центры кластеров
  • число кластеров надо знать заранее

Расширения и вариации

Ссылки

  1. David Arthur & Sergei Vassilvitskii (2006). "How Slow is the k-means Method?". Proceedings of the 2006 Symposium on Computational Geometry (SoCG). 



Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Полезное


Смотреть что такое "К-средних" в других словарях:

  • средних лет — См …   Словарь синонимов

  • СРЕДНИХ АРИФМЕТИЧЕСКИХ МЕТОД СУММИРОВАНИЯ — один из методов суммирования рядов и последовательностей. Ряд суммируем методом средних арифметических к сумме s, если где В этом случае говорят также, что последовательность {sn} суммируема методом средних арифметических к пределу s. С. а. м. с …   Математическая энциклопедия

  • Средних размеров редьку натереть на мелкой терке, добавить — Тип блюда: Категория: Продукты: Рецепт приготовления: В текущей категории (Сладости): | | | | | | | | | | | …   Энциклопедия кулинарных рецептов

  • средних лет — о не очень молодом и не очень старом Ср. Entre deux âges n avoir point d âges …   Большой толково-фразеологический словарь Михельсона

  • Средних лет — Среднихъ лѣтъ о не очень молодомъ и не очень старомъ. Ср. Entre deux âges n’avoir point d’âges …   Большой толково-фразеологический словарь Михельсона (оригинальная орфография)

  • Кафедра истории Беларуси древнего мира и средних веков БГУ — Начало деятельности кафедры восходит к 1934 г., когда в числе первых на историческом факультете были созданы кафедры истории древнего мира и истории средних веков. Особое внимание к преподаванию и исследованию древности и средневековья в БГУ… …   Википедия

  • Неравенство о средних — Среднее степени d (или просто среднее степенное) набора положительных вещественных чисел определяется как При этом по непрерывности доопределяются следующие величины …   Википедия

  • Комбинации скользящих средних — совмещение двух или более графиков скользящих средних. В общем случае графики представляют собой кратко , средне и долгосрочные периоды вычисления скользящего среднего. Обычно используются порядки 5,13,21. Комбинации скользящих средних позволяют… …   Финансовый словарь

  • История пенитенциарных учреждений со средних веков до начала XX века — При написании этой статьи использовался материал из Энциклопедического словаря Брокгауза и Ефрона (1890 1907). История пенитенциарных учреждений со средних веков до начала XX века. Эта статья о тюрьмах, каторжных заведениях и прочих местах… …   Википедия

  • КРИВАЯ СРЕДНИХ ИЗДЕРЖЕК, U-ОБРАЗНАЯ — (U shaped average cost curve) Форма, которую, как предполагается, принимает кривая средних издержек. Аргументы таковы: в любом производственном процессе имеются накладные или фиксированные издержки, благодаря которым при низких уровнях выпуска… …   Экономический словарь

  • Демография Средних веков — Связать? Демография Средних веков  в статье освещается демография человечества в Европе в Средних веках, включая тенденции и перемещения. Демографические изменения помогают очертить и определить Средние века. Грубо демографические тенденции… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»