Индексы с постоянными и переменными весами Метод анализа иерархий Средний уровень моментного ряда Модель взаимозачета долгов предприятий Выбор инвестиционных проектов Интегральный метод факторного анализа Баланс движения основных фондов Экономически активное население
Метод k-средних Показатели динамики Индекс сезонности
Аддитивная модель ряда Мультипликативная модель Цепные показатели
Общий индекс цен Группировка данных Аналитическое выравнивание

Алгоритм К-средних

Метод K-средних – это метод кластерного анализа, целью которого является разделение m наблюдений на k кластеров, при этом каждое наблюдение относится к тому кластеру, к центу (центроиду) которого оно ближе всего.

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

Инструкция. Укажите количество данных, нажмите Далее. Полученное решение сохраняется в файле Word.
Размерность матрицы разбиения x

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

  1. Выбирается число кластеров k.
  2. Из исходного множества данных случайным образом выбираются k записей, которые будут служить начальными центрами кластеров.
  3. Для каждой записи исходной выборки определяется ближайший к ней центр кластера. При этом записи, «притянутые» определенным центром, образуют начальные кластеры.
  4. Вычисляются центроиды – центры тяжести кластеров. Каждый центроид – это вектор, элементы которого представляют собой средние значения признаков, вычисленные по всем записям кластера. Затем центр кластера смещается в его центроид.
Процесс итерации прекращается, когда границы кластеров не перестанут изменяться от итерации к итерации, т.е. на каждой итерации в каждом кластере будет оставаться один и тот же набор записей.

Достоинства алгоритма k-средних:

Недостатки алгоритма k-средних:

Пример №1. По данной выше таблице провести классификацию объектов на три класса методом К-средних. Провести максимальное число итераций. Эталонные точки и порядок появления точек задать самостоятельно. Отобразить на плоскости по лученный вариант классификации.

Объекты A B C D E F
признак-X –2 –2 –3 4 3 0
признак-Y 0 –1 0 0 0 0
Сравниваем расстояние от точки E до эталонных точек.



Минимальным является расстояние d(Ee1)
Пересчитываем значения для эталонной точки e1: (3+1)/2 = 2;(0+0)/2 = 0;
Сравниваем расстояние от точки F до эталонных точек.



Минимальным является расстояние d(Fe1)
Пересчитываем значения для эталонной точки e1: (0+2)/2 = 1;(0+0)/2 = 0;
Произведём классификацию объектов:



Объект A ближе всех расположен к эталонной точке e2.



Объект B ближе всех расположен к эталонной точке e2.



Объект C ближе всех расположен к эталонной точке e3.



Объект D ближе всех расположен к эталонной точке e1.



Объект E ближе всех расположен к эталонной точке e1.



Объект F ближе всех расположен к эталонной точке e1.
e1 e2 e3
DEF AB C
Итерация №1
Сравниваем расстояние от точки A до эталонных точек.



Минимальным является расстояние d(Ae2)
Пересчитываем значения для эталонной точки e2: (-2+(-2))/2 = -2;(0+(-1))/2 = -0.5;
Сравниваем расстояние от точки B до эталонных точек.



Минимальным является расстояние d(Be2)
Пересчитываем значения для эталонной точки e2: (-2+(-2))/2 = -2;(-1+(-0.5))/2 = -0.75;
Сравниваем расстояние от точки D до эталонных точек.



Минимальным является расстояние d(De1)
Пересчитываем значения для эталонной точки e1: (4+1)/2 = 2.5;(0+0)/2 = 0;
Сравниваем расстояние от точки E до эталонных точек.



Минимальным является расстояние d(Ee1)
Пересчитываем значения для эталонной точки e1: (3+2.5)/2 = 2.75;(0+0)/2 = 0;
Сравниваем расстояние от точки F до эталонных точек.



Минимальным является расстояние d(Fe2)
Пересчитываем значения для эталонной точки e2: (0+(-2))/2 = -1;(0+(-0.75))/2 = -0.375;
Произведём классификацию объектов:



Объект A ближе всех расположен к эталонной точке e3.



Объект B ближе всех расположен к эталонной точке e2.



Объект C ближе всех расположен к эталонной точке e3.



Объект D ближе всех расположен к эталонной точке e1.



Объект E ближе всех расположен к эталонной точке e1.



Объект F ближе всех расположен к эталонной точке e2.
e1 e2 e3
DE BF AC
Границы кластеров изменились, продолжаем процесс разбиения.
Итерация №2
Сравниваем расстояние от точки A до эталонных точек.



Минимальным является расстояние d(Ae3)
Пересчитываем значения для эталонной точки e3: (-2+(-3))/2 = -2.5;(0+0)/2 = 0;
Сравниваем расстояние от точки B до эталонных точек.



Минимальным является расстояние d(Be3)
Пересчитываем значения для эталонной точки e3: (-2+(-2.5))/2 = -2.25;(-1+0)/2 = -0.5;
Сравниваем расстояние от точки C до эталонных точек.



Минимальным является расстояние d(Ce3)
Пересчитываем значения для эталонной точки e3: (-3+(-2.25))/2 = -2.625;(0+(-0.5))/2 = -0.25;
Сравниваем расстояние от точки D до эталонных точек.



Минимальным является расстояние d(De1)
Пересчитываем значения для эталонной точки e1: (4+2.75)/2 = 3.375;(0+0)/2 = 0;
Сравниваем расстояние от точки E до эталонных точек.



Минимальным является расстояние d(Ee1)
Пересчитываем значения для эталонной точки e1: (3+3.375)/2 = 3.1875;(0+0)/2 = 0;
Сравниваем расстояние от точки F до эталонных точек.



Минимальным является расстояние d(Fe2)
Пересчитываем значения для эталонной точки e2: (0+(-1))/2 = -0.5;(0+(-0.375))/2 = -0.1875;
Произведём классификацию объектов:



Объект A ближе всех расположен к эталонной точке e3.



Объект B ближе всех расположен к эталонной точке e3.



Объект C ближе всех расположен к эталонной точке e3.



Объект D ближе всех расположен к эталонной точке e1.



Объект E ближе всех расположен к эталонной точке e1.



Объект F ближе всех расположен к эталонной точке e2.
e1 e2 e3
DE F ABC
Границы кластеров изменились, продолжаем процесс разбиения.
Итерация №3
Сравниваем расстояние от точки A до эталонных точек.



Минимальным является расстояние d(Ae3)
Пересчитываем значения для эталонной точки e3: (-2+(-2.625))/2 = -2.3125;(0+(-0.25))/2 = -0.125;
Сравниваем расстояние от точки B до эталонных точек.



Минимальным является расстояние d(Be3)
Пересчитываем значения для эталонной точки e3: (-2+(-2.3125))/2 = -2.15625;(-1+(-0.125))/2 = -0.5625;
Сравниваем расстояние от точки C до эталонных точек.



Минимальным является расстояние d(Ce3)
Пересчитываем значения для эталонной точки e3: (-3+(-2.15625))/2 = -2.578125;(0+(-0.5625))/2 = -0.28125;
Сравниваем расстояние от точки D до эталонных точек.



Минимальным является расстояние d(De1)
Пересчитываем значения для эталонной точки e1: (4+3.1875)/2 = 3.59375;(0+0)/2 = 0;
Сравниваем расстояние от точки E до эталонных точек.



Минимальным является расстояние d(Ee1)
Пересчитываем значения для эталонной точки e1: (3+3.59375)/2 = 3.296875;(0+0)/2 = 0;
Сравниваем расстояние от точки F до эталонных точек.



Минимальным является расстояние d(Fe2)
Пересчитываем значения для эталонной точки e2: (0+(-0.5))/2 = -0.25;(0+(-0.1875))/2 = -0.09375;
Произведём классификацию объектов:



Объект A ближе всех расположен к эталонной точке e3.



Объект B ближе всех расположен к эталонной точке e3.



Объект C ближе всех расположен к эталонной точке e3.



Объект D ближе всех расположен к эталонной точке e1.



Объект E ближе всех расположен к эталонной точке e1.



Объект F ближе всех расположен к эталонной точке e2.
e1 e2 e3
DE F ABC
Границы кластеров не изменились, т.е. в каждом кластере будет остается один и тот же набор записей. Останавливаем процесс кластеризации.

Пример №2. Даны четыре объекта, каждый определяется двумя признаками. Разбить объекты на три кластера методом k-средних. Первоначально первые три объекта образуют начальные кластеры, метрика – квадрат евклидова расстояния: X1(2;3), Х2(3;2), Х3(7;3), Х4 (5;-3).

Дипломные работы
Консультации и помощь
Сроки от 3 дней

Подробнее