Итеративные методы, Алгоритм k-средних (k-means) - Кластерный анализ

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

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

Алгоритм k-средних (k-means)

Наиболее распространен среди неиерархических методов алгоритм k-средних, также называемый быстрым кластерным анализом. Полное описание алгоритма можно найти в работе Хартигана и Вонга (Hartigan and Wong, 1978). В отличие от иерархических методов, которые не требуют предварительных предположений относительно числа кластеров, для возможности использования этого метода необходимо иметь гипотезу о наиболее вероятном количестве кластеров.

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

Общая идея алгоритма: заданное фиксированное число k кластеров наблюдения сопоставляются кластерам так, что средние в кластере (для всех переменных) максимально возможно отличаются друг от друга.

Описание алгоритма

1. Первоначальное распределение объектов по кластерам. O выбор k-наблюдений для максимизации начального расстояния; O случайный выбор k-наблюдений; O выбор первых k-наблюдений.

Выбирается число k, и на первом шаге эти точки считаются "центрами" кластеров. Каждому кластеру соответствует один центр. Выбор начальных центроидов может осуществляться следующим образом: В результате каждый объект назначен определенному кластеру.

2. Итеративный процесс. O кластерные центры стабилизировались, т. е. все наблюдения принадлежат кластеру, которому принадлежали до текущей итерации; O число итераций равно максимальному числу итераций.

Вычисляются центры кластеров, которыми затем и далее считаются покоординатные средние кластеров. Объекты опять перераспределяются. Процесс вычисления центров и перераспределения объектов продолжается до тех пор, пока не выполнено одно из условий:

Выбор числа кластеров является сложным вопросом. Если нет предположений относительно этого числа, рекомендуют создать 2 кластера, затем 3, 4, 5 и т. д., сравнивая полученные результаты.

Похожие статьи

• Определение количества кластеров - Кластерный анализ

  Существует проблема определения числа кластеров. Иногда можно априорно определить это число. Однако в большинстве случаев число кластеров определяется в...

• Методы кластерного анализа, Иерархические методы кластерного анализа - Кластерный анализ

  Методы кластерного анализа можно разделить на две группы: - иерархические; - неиерархические. Каждая из групп включает множество подходов и алгоритмов....

• Методы объединения или связи - Кластерный анализ

  Когда каждый объект представляет собой отдельный кластер, расстояния между этими объектами определяются выбранной мерой. Возникает следующий вопрос - как...

• Иерархический кластерный анализ в SPSS - Кластерный анализ

  Рассмотрим процедуру иерархического кластерного анализа в пакете SPSS (SPSS). Процедура иерархического кластерного анализа в SPSS предусматривает...

• Методы Кластерного Анализа, Иерархические методы - Кластерный анализ

  Иерархические методы С понятием кластеризации мы познакомились в первом разделе курса. В этом мы опишем понятие "кластер" с математической точки зрения,...

• Сходимость итерационных алгоритмов кластер-анализа - Базовые результаты математической теории классификации

  Сначала обсудим один из широко применяемых методов кластер-анализа - с метода k-средних. Он предназначен для разбиения исходного множества элементов...

• Детерминированные экономико-математические модели и методы факторного анализа, Моделирование. Детерминизм. Требования к моделированию - Экономико-математическая детерминированная модель

  Моделирование. Детерминизм. Требования к моделированию В процессе исследования объекта часто бывает нецелесообразно или даже невозможно иметь дело...

• Алгоритм принятия решений на основе анализа иерархии целей - Формализация решения многоцелевых задач при управлении научной деятельностью

  Алгоритм использует в качестве исходных данных документы, содержащие следующие сведения: X A, k,j, i - измеряемые показатели научной работы; X A, TG,...

• Анализ работы методов - Комплексное исследование численных методов для задачи решения нелинейных уравнений

  Метод дихотомии требует менее всего итераций цикла для получения корней уравнения с заданной точностью. Если расчет ведется без помощи ЭВМ, то это...

• Введение - Применение метода Монте-Карло в эконометрическом анализе

  Метод Монте-Карло можно определить как метод моделирования случайных величин с целью вычисления характеристик их распределений. Возникновение идеи...

• Введение, Составление плана эксперимента и проведение в соответствии с этим планом исследования объекта управления - Методы регрессионного анализа и планирования эксперимента

  1. Ознакомиться с методами регрессионного анализа и планирования эксперимента; 2. Определить коэффициенты статистической характеристики объекта...

• ОПРЕДЕЛЕНИЕ МЕТОДА ФАКТОРНОГО АНАЛИЗА И ЧИСЛА ФАКТОРОВ - Многомерный статистический анализ

  Определение метода факторного анализа. Различные методы факторного анализа различаются в зависимости от подходов, которые используются для выделения...

• МЕТОДЫ СРАВНИТЕЛЬНОГО ШКАЛИРОВАНИЯ - Многомерный статистический анализ

  Шкалирование методом попарного сравнения - Это метод сравнительного шкалирования, при котором респонденту дается два объекта для выбора по определенному...

• Методы анализа взаимосвязи - Статистическое изучение взаимосвязи социально-экономических явлений

  Первым и обязательным этапом изучения взаимосвязи социально-экономических явлений является качественный анализ природы явления методами экономической...

• Заключение - Анализ методов прогнозирования

  На основании проведенного исследования можно сделать следующие выводы и предложения: 1. Под прогнозом понимается система научно обоснованных...

• Метод наименьших квадратов - Анализ методов прогнозирования

  Расчет параметров af b для конкретной функциональной зависимости осуществляется с помощью метода наименьших квадратов (МНК) и его модификаций. Суть МНК...

• Адсорбционные методы исследования поверхности - Анализ удельной поверхности активированного угля, основанный на использовании метода тепловой десорбции газа-адсорбата (азота) с поверхности в динамических условиях с помощью специального адсорбера, прибора для текстурных измерений "Термосорб" серии М

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

• Вычисление интегралов методом Монте-Карло, Алгоритмы метода Монте-Карло для решения интегральных уравнений второго рода - Применение метода Монте-Карло в эконометрическом анализе

  Алгоритмы метода Монте-Карло для решения интегральных уравнений второго рода Пусть необходимо вычислить линейный функционал , Где, причем для...

• Алгоритм расчета неизвестных коэффициентов уравнения регрессии, Статистический анализ полученных результатов - Методы регрессионного анализа и планирования эксперимента

  Составляется матрица численных значений базисных функций, соответствующая расширенной матрице спектра плана Вычисляется информационная матрица...

• Моделирование как метод научного познания. - Моделирование перспективного развития экономики

  Моделирование в научных исследованиях стало применяться еще в глубокой древности и постепенно захватывало все новые области научных знаний: техническое...

• Метод Монте-Карло, Общая схема метода Монте-Карло, Оценка погрешности метода Монте-Карло - Применение метода Монте-Карло в эконометрическом анализе

  Общая схема метода Монте-Карло Сущность метода Монте-Карло состоит в следующем: требуется найти значение а некоторой изучаемой величины. Для этого...

• Введение - Анализ методов прогнозирования

  Процесс прогнозирования достаточно актуален в настоящее время. Широка сфера его применения. Прогнозирование широко используется в экономике, а именно в...

• Меры сходства - Кластерный анализ

  Для вычисления расстояния между объектами используются различные меры сходства (меры подобия), называемые также метриками или функциями расстояний. В...

• Значение и методы анализа финансовых результатов - Контрольная работа по теории экономического анализа

  Анализ - метод научного исследования явлений и процессов, в основе которого лежит изучение составных частей, элементов изучаемой системы. На современном...

• Элементы матричного анализа - Методы решения системы линейных уравнений

  Вектором, как на плоскости, так и в пространстве, называется направленный Отрезок , то есть такой Отрезок , один из концов которого выделен и называется...

• КЛАССИФИКАЦИЯ ХРОМАТОГРАФИЧЕСКИХ МЕТОДОВ АНАЛИЗА, АДСОРБЦИОННАЯ ХРОМАТОГРАФИЯ. ТОНКОСЛОЙНАЯ ХРОМАТОГРАФИЯ - Хроматография как метод исследования

  В основу классификаций хроматографических методов положены принципы, учитывающие следующие различные особенности процесса разделения: * различия в...

• Качественные методы анализа - Разработка технологической схемы получения анизола и крезола

  Рециркуляционных реакционно-ректификационных процессов. При анализе сложных ХТС, характеризующихся большим числом параметров и переменных необходимо...

• Задачи регрессионного анализа, Метод наименьших квадратов - Выполнение регрессионного и дисперсионного анализа

  Регрессия -- зависимость среднего значения какой-либо величины от некоторой другой величины или от нескольких величин. Задача регрессионного анализа...

• Метод анализа многомерных иерархий

  Метод анализа многомерных иерархий Современная бизнес-аналитика требует, во-первых, выявления предполагаемых взаимосвязей и взаимовлияющих факторов в...

• Заключение, Список литературы - Применение метода Монте-Карло в эконометрическом анализе

  Метод Монте-Карло используется очень часто, порой некритично и неэффективным образом. Он имеет некоторые очевидные преимущества: А) Он не требует никаких...

• Способ, основанный на истолковании интеграла как площади - Применение метода Монте-Карло в эконометрическом анализе

  Пусть подынтегральная функция неотрицательна и ограничена: , а двумерная случайная величина распределена равномерно в прямоугольнике D с основанием и...

• Способ существенной выборки, использующий "вспомогательную плотность распределения" - Применение метода Монте-Карло в эконометрическом анализе

  Монте карло погрешность распределение интеграл В качестве оценки интеграла принимают , Где n - число испытаний; F(x) - плотность распределения...

• Задачи и методы количественного анализа - Основы аналитической химии

  Количественный анализ - это совокупность химических, физико-химических и физических методов определения количественного соотношения компонентов, входящих...

• Кластерный анализ - Кластерный анализ

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

• Алгоритмы поиска квази-клики в графе. - Использование квази-клик для анализа графа рынка России

  Как и для поиска клик существуют алгоритмы поиска квази-клик в графе. Далее мы рассмотрим некоторые из них. Как было сказано ранее, задача поиска...

• Предварительная обработка исходной информации в задачах прогнозной экстраполяции - Анализ методов прогнозирования

  Предварительная обработка исходного числового ряда направлена на решение следующих задач (всех или части из них): снизить влияние случайной составляющей...

• Методы экстраполяции - Анализ методов прогнозирования

  Методы экстраполяции тенденций являются, пожалуй, самыми распространенными и наиболее разработанными среди всей совокупности методов прогнозирования....

• Основные теоретические сведения - Метод статистических группировок и его применение в анализе прибыли и ее зависимости от формирующих факторов

  В результате первой стадии статистического исследования (статистического наблюдения) получают статистическую информацию, представляющую собой большое...

• Формализованные методы прогнозирования: корреляционно-регрессионный, методы экстраполяции, метод наименьших квадратов, Корреляционно-регрессионный метод - Анализ методов прогнозирования

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

• Задачи и методы качественного анализа - Основы аналитической химии

  Обнаружение или, как иногда говорят, "открытие" отдельных элементов или ионов, входящих в состав веществ - это задачи качественного анализа. Качественный...

Итеративные методы, Алгоритм k-средних (k-means) - Кластерный анализ

Предыдущая | Следующая