Алгоритм К-средних
Метод K-средних – это метод кластерного анализа, целью которого является разделение m наблюдений на k кластеров, при этом каждое наблюдение относится к тому кластеру, к центу (центроиду) которого оно ближе всего.Назначение. С помощью онлайн-калькулятора можно проводить классификацию объектов методом К-средних с построением дендрограммы (например, для построения типологической группировки).
Алгоритм разделительной кластеризации, основан на разбиении множества элементов векторного пространства на заранее определенное число кластеров k. Метод относится к неирархическим алгоритмам кластеризации. Алгоритм представляет собой итерационную процедуру:
- Выбирается число кластеров k.
- Из исходного множества данных случайным образом выбираются k записей, которые будут служить начальными центрами кластеров.
- Для каждой записи исходной выборки определяется ближайший к ней центр кластера. При этом записи, «притянутые» определенным центром, образуют начальные кластеры.
- Вычисляются центроиды – центры тяжести кластеров. Каждый центроид – это вектор, элементы которого представляют собой средние значения признаков, вычисленные по всем записям кластера. Затем центр кластера смещается в его центроид.
Достоинства алгоритма k-средних:
- простота реализации;
- интуитивная понятность и прозрачность алгоритма;
Недостатки алгоритма k-средних:
- число кластеров надо знать заранее;
- зависимость результата от инициализации центров кластеров;
- вычислительная сложность;
Пример №1. По данной выше таблице провести классификацию объектов на три класса методом К-средних. Провести максимальное число итераций. Эталонные точки и порядок появления точек задать самостоятельно. Отобразить на плоскости по лученный вариант классификации.
Объекты | A | B | C | D | E | F |
признак-X | –2 | –2 | –3 | 4 | 3 | 0 |
признак-Y | 0 | –1 | 0 | 0 | 0 | 0 |
![](images/k-means4.png)
![](images/k-means5.png)
![](images/k-means6.png)
Минимальным является расстояние d(Ee1)
Пересчитываем значения для эталонной точки e1: (3+1)/2 = 2;(0+0)/2 = 0;
Сравниваем расстояние от точки F до эталонных точек.
![](images/k-means7.png)
![](images/k-means8.png)
![](images/k-means9.png)
Минимальным является расстояние d(Fe1)
Пересчитываем значения для эталонной точки e1: (0+2)/2 = 1;(0+0)/2 = 0;
Произведём классификацию объектов:
![](images/k-means10.png)
![](images/k-means11.png)
![](images/k-means12.png)
Объект A ближе всех расположен к эталонной точке e2.
![](images/k-means13.png)
![](images/k-means14.png)
![](images/k-means15.png)
Объект B ближе всех расположен к эталонной точке e2.
![](images/k-means16.png)
![](images/k-means17.png)
![](images/k-means18.png)
Объект C ближе всех расположен к эталонной точке e3.
![](images/k-means19.png)
![](images/k-means20.png)
![](images/k-means21.png)
Объект D ближе всех расположен к эталонной точке e1.
![](images/k-means22.png)
![](images/k-means23.png)
![](images/k-means24.png)
Объект E ближе всех расположен к эталонной точке e1.
![](images/k-means25.png)
![](images/k-means26.png)
![](images/k-means27.png)
Объект F ближе всех расположен к эталонной точке e1.
e1 | e2 | e3 |
DEF | AB | C |
Сравниваем расстояние от точки A до эталонных точек.
![](images/k-means28.png)
![](images/k-means29.png)
![](images/k-means30.png)
Минимальным является расстояние d(Ae2)
Пересчитываем значения для эталонной точки e2: (-2+(-2))/2 = -2;(0+(-1))/2 = -0.5;
Сравниваем расстояние от точки B до эталонных точек.
![](images/k-means31.png)
![](images/k-means32.png)
![](images/k-means33.png)
Минимальным является расстояние d(Be2)
Пересчитываем значения для эталонной точки e2: (-2+(-2))/2 = -2;(-1+(-0.5))/2 = -0.75;
Сравниваем расстояние от точки D до эталонных точек.
![](images/k-means34.png)
![](images/k-means35.png)
![](images/k-means36.png)
Минимальным является расстояние d(De1)
Пересчитываем значения для эталонной точки e1: (4+1)/2 = 2.5;(0+0)/2 = 0;
Сравниваем расстояние от точки E до эталонных точек.
![](images/k-means37.png)
![](images/k-means38.png)
![](images/k-means39.png)
Минимальным является расстояние d(Ee1)
Пересчитываем значения для эталонной точки e1: (3+2.5)/2 = 2.75;(0+0)/2 = 0;
Сравниваем расстояние от точки F до эталонных точек.
![](images/k-means40.png)
![](images/k-means41.png)
![](images/k-means42.png)
Минимальным является расстояние d(Fe2)
Пересчитываем значения для эталонной точки e2: (0+(-2))/2 = -1;(0+(-0.75))/2 = -0.375;
Произведём классификацию объектов:
![](images/k-means43.png)
![](images/k-means44.png)
![](images/k-means45.png)
Объект A ближе всех расположен к эталонной точке e3.
![](images/k-means46.png)
![](images/k-means47.png)
![](images/k-means48.png)
Объект B ближе всех расположен к эталонной точке e2.
![](images/k-means49.png)
![](images/k-means50.png)
![](images/k-means51.png)
Объект C ближе всех расположен к эталонной точке e3.
![](images/k-means52.png)
![](images/k-means53.png)
![](images/k-means54.png)
Объект D ближе всех расположен к эталонной точке e1.
![](images/k-means55.png)
![](images/k-means56.png)
![](images/k-means57.png)
Объект E ближе всех расположен к эталонной точке e1.
![](images/k-means58.png)
![](images/k-means59.png)
![](images/k-means60.png)
Объект F ближе всех расположен к эталонной точке e2.
e1 | e2 | e3 |
DE | BF | AC |
Итерация №2
Сравниваем расстояние от точки A до эталонных точек.
![](images/k-means61.png)
![](images/k-means62.png)
![](images/k-means63.png)
Минимальным является расстояние d(Ae3)
Пересчитываем значения для эталонной точки e3: (-2+(-3))/2 = -2.5;(0+0)/2 = 0;
Сравниваем расстояние от точки B до эталонных точек.
![](images/k-means64.png)
![](images/k-means65.png)
![](images/k-means66.png)
Минимальным является расстояние d(Be3)
Пересчитываем значения для эталонной точки e3: (-2+(-2.5))/2 = -2.25;(-1+0)/2 = -0.5;
Сравниваем расстояние от точки C до эталонных точек.
![](images/k-means67.png)
![](images/k-means68.png)
![](images/k-means69.png)
Минимальным является расстояние d(Ce3)
Пересчитываем значения для эталонной точки e3: (-3+(-2.25))/2 = -2.625;(0+(-0.5))/2 = -0.25;
Сравниваем расстояние от точки D до эталонных точек.
![](images/k-means70.png)
![](images/k-means71.png)
![](images/k-means72.png)
Минимальным является расстояние d(De1)
Пересчитываем значения для эталонной точки e1: (4+2.75)/2 = 3.375;(0+0)/2 = 0;
Сравниваем расстояние от точки E до эталонных точек.
![](images/k-means73.png)
![](images/k-means74.png)
![](images/k-means75.png)
Минимальным является расстояние d(Ee1)
Пересчитываем значения для эталонной точки e1: (3+3.375)/2 = 3.1875;(0+0)/2 = 0;
Сравниваем расстояние от точки F до эталонных точек.
![](images/k-means76.png)
![](images/k-means77.png)
![](images/k-means78.png)
Минимальным является расстояние d(Fe2)
Пересчитываем значения для эталонной точки e2: (0+(-1))/2 = -0.5;(0+(-0.375))/2 = -0.1875;
Произведём классификацию объектов:
![](images/k-means79.png)
![](images/k-means80.png)
![](images/k-means81.png)
Объект A ближе всех расположен к эталонной точке e3.
![](images/k-means82.png)
![](images/k-means83.png)
![](images/k-means84.png)
Объект B ближе всех расположен к эталонной точке e3.
![](images/k-means85.png)
![](images/k-means86.png)
![](images/k-means87.png)
Объект C ближе всех расположен к эталонной точке e3.
![](images/k-means88.png)
![](images/k-means89.png)
![](images/k-means90.png)
Объект D ближе всех расположен к эталонной точке e1.
![](images/k-means91.png)
![](images/k-means92.png)
![](images/k-means93.png)
Объект E ближе всех расположен к эталонной точке e1.
![](images/k-means94.png)
![](images/k-means95.png)
![](images/k-means96.png)
Объект F ближе всех расположен к эталонной точке e2.
e1 | e2 | e3 |
DE | F | ABC |
Итерация №3
Сравниваем расстояние от точки A до эталонных точек.
![](images/k-means97.png)
![](images/k-means98.png)
![](images/k-means99.png)
Минимальным является расстояние d(Ae3)
Пересчитываем значения для эталонной точки e3: (-2+(-2.625))/2 = -2.3125;(0+(-0.25))/2 = -0.125;
Сравниваем расстояние от точки B до эталонных точек.
![](images/k-means100.png)
![](images/k-means101.png)
![](images/k-means102.png)
Минимальным является расстояние d(Be3)
Пересчитываем значения для эталонной точки e3: (-2+(-2.3125))/2 = -2.15625;(-1+(-0.125))/2 = -0.5625;
Сравниваем расстояние от точки C до эталонных точек.
![](images/k-means103.png)
![](images/k-means104.png)
![](images/k-means105.png)
Минимальным является расстояние d(Ce3)
Пересчитываем значения для эталонной точки e3: (-3+(-2.15625))/2 = -2.578125;(0+(-0.5625))/2 = -0.28125;
Сравниваем расстояние от точки D до эталонных точек.
![](images/k-means106.png)
![](images/k-means107.png)
![](images/k-means108.png)
Минимальным является расстояние d(De1)
Пересчитываем значения для эталонной точки e1: (4+3.1875)/2 = 3.59375;(0+0)/2 = 0;
Сравниваем расстояние от точки E до эталонных точек.
![](images/k-means109.png)
![](images/k-means110.png)
![](images/k-means111.png)
Минимальным является расстояние d(Ee1)
Пересчитываем значения для эталонной точки e1: (3+3.59375)/2 = 3.296875;(0+0)/2 = 0;
Сравниваем расстояние от точки F до эталонных точек.
![](images/k-means112.png)
![](images/k-means113.png)
![](images/k-means114.png)
Минимальным является расстояние d(Fe2)
Пересчитываем значения для эталонной точки e2: (0+(-0.5))/2 = -0.25;(0+(-0.1875))/2 = -0.09375;
Произведём классификацию объектов:
![](images/k-means115.png)
![](images/k-means116.png)
![](images/k-means117.png)
Объект A ближе всех расположен к эталонной точке e3.
![](images/k-means118.png)
![](images/k-means119.png)
![](images/k-means120.png)
Объект B ближе всех расположен к эталонной точке e3.
![](images/k-means121.png)
![](images/k-means122.png)
![](images/k-means123.png)
Объект C ближе всех расположен к эталонной точке e3.
![](images/k-means124.png)
![](images/k-means125.png)
![](images/k-means126.png)
Объект D ближе всех расположен к эталонной точке e1.
![](images/k-means127.png)
![](images/k-means128.png)
![](images/k-means129.png)
Объект E ближе всех расположен к эталонной точке e1.
![](images/k-means130.png)
![](images/k-means131.png)
![](images/k-means132.png)
Объект F ближе всех расположен к эталонной точке e2.
e1 | e2 | e3 |
DE | F | ABC |
Пример №2. Даны четыре объекта, каждый определяется двумя признаками. Разбить объекты на три кластера методом k-средних. Первоначально первые три объекта образуют начальные кластеры, метрика – квадрат евклидова расстояния: X1(2;3), Х2(3;2), Х3(7;3), Х4 (5;-3).