Алгоритмы k-means и k-medians

Алгоритм k-средних (k-means) – алгоритм кластеризации данных. Целью задачи кластеризации является разбиение множества объектов на кластеры (классы) на основе некоторой меры сходства объектов.

Дано:

Набор векторов , i = 1, …, p;

k – число кластеров, на которые нужно разбить набор .

 

Найти:

k средних векторов m_j, j = 1, …, k (центров кластеров);

отнести каждый из векторов к одному из k кластеров;

 

Алгоритм:

1. Случайным образом выбрать k средних m_j j = 1, …, k;

2. Для каждого x_i i = 1, …, p подсчитать расстояние до каждого из m_j j=1, …, k,

Отнести (приписать) x_i к кластеру j’, расстояние до центра которого m_j’ минимально;

3. Пересчитать средние (центр масс) m_j j=1, …, k по всем кластерам;

4. Повторять шаги 2, 3, пока кластеры не перестанут изменяться.

 

Пример кластеризации в 2D.

 

 

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

Алгоритм кластеризации k-medoids похож на алгоритм k-means, но в отличие от него на каждой итерации ищет центры кластеров не как среднее точек, а как медоиды точек. То есть, центр кластера должен обязательно являться одной из его точек. Медоидом для множества точек называется одна из точек множества, сумма расстояний до которой от всех точек множества минимальна.

Алгоритм k-medoids, в отличие от k-means, использует для представления центра кластера не центр масс, а представительный объект – один из объектов кластера. Как и в методе k-means, сначала произвольным образом выбирается k представительных объектов. Каждый из оставшихся объектов объединяется в кластер с ближайшим представительным объектом. Затем итеративно для каждого представительного объекта производится его замена произвольным непредставительным объектом пространства данных. Процесс замены продолжается до тех пор, пока улучшается качество результирующих кластеров. Качество кластеризации определяется суммой отклонений между каждым объектом и представительным объектом соответствующего кластера, которую метод стремится минимизировать. То есть, итерации продолжаются до тех пор, пока в каждом кластере его представительный объект не станет медоидом – наиболее близким к центру кластера объектом.

 

Задание для лабораторной работы

1. При необходимости выполнить коррекцию яркости изображения (см. лаб. работу №1).

2. Перевести цветное изображение в бинарное изображение (см. лаб. работу №1).

3. Реализовать пороговую бинаризацию изображения (см. лаб. работу №1).

4. Выделить связные области на изображении (рекурсивный алгоритм или алгоритм последовательного сканирования).

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

6. Используя алгоритм k-means, k-medians либо k-medoids, определить принадлежность объекта к одному из кластеров (классов). Реализация данного алгоритма обязательна.

 

№ варианта	Алгоритм выделения связных областей	Алгоритм кластеризации
	Рекурсивный	k-means
	Последовательного сканирования	k-medians
	Рекурсивный	k-medoids
	Последовательного сканирования	k-means
	Рекурсивный	k-medians
	Последовательного сканирования	k-medoids

 

 

Тестовые базы:

1. Преподавателем будет выдана тестовая база, в которой будут два класса изображений.

2. По желанию студент может реализовать данный алгоритм для своих изображений.

 

Рис. 2.6. Примеры тестовых изображений

 

 

Контрольные вопросы

1. Геометрические признаки при описании объектов.

2. Фотометрические признаки при описании объектов.

3. Кластерный анализ.

4. Алгоритм k-means.

5. Алгоритм k-medians.

6. Алгоритм k-medoids.

 

 

Литература

1. Яне, Б. Цифровая обработка изображений / Б. Яне. – М.: Техносфера, 2007.

2. Гонсалес, Р. Цифровая обработка изображений / Р. Гонсалес, Р. Вудс. – М.: Техносфера, 2006.

3. Дуда, Р. Распознавание образов и анализ сцен / Р. Дуда, П. Харт. – М.: Мир, 1976.

4. Павлидис, Т. Алгоритмы машинной графики и обработки изображений / Т. Павлидис. – М.: Радио и связь, 1986.

5. Прэтт, У. Цифровая обработка изображений. В 2 т. / У. Прэтт. – М.: Мир, 1982.

 

Св. план 2010, поз. 56

 

Учебное издание

 

 

Лукашевич Марина Михайловна

Садыхов Рауф Хосровович

 

 

⇐ Предыдущая123456

Поделиться:

Популярное:

1. Алгоритмы линейной структуры
2. Алгоритмы на различных языках программирования. Заполнение массивов
3. Алгоритмы обслуживания вызовов
4. АЛГОРИТМЫ ПОСТРОЕНИЯ КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ И КРАТЧАЙШЕГО ОСТОВА ГРАФА
5. Алгоритмы построения минимальных связывающих деревьев
6. АЛГОРИТМЫ ПОСТРОЕНИЯ ЭЙЛЕРОВА И ГАМИЛЬТОНОВА ЦИКЛА
7. Алгоритмы проектных расчетов гидрометаллургического оборудования
8. Алгоритмы проектных расчетов пирометаллургического оборудования
9. Алгоритмы проектных расчетов электрометаллургического оборудования.
10. Алгоритмы реализации методики КТД
11. Алгоритмы симметричного шифрования