Тема 1. Обучение без учителя: простейшие алгоритмы кластеризации.

Основное задание:

1. Изучить различные меры близости изображений(описаний объектов)

2. Изучить:

• простой эвристический алгоритм определения кластеров

• эвристический алгоритм максиминного расстояния

• алгоритм К внутригрупповых средних

3. Подробно разобрать примеры работы каждого из этих алгоритмов

4. Указать сферу применения данной группы алгоритмов

1.Меры сходства

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

1) Ранее рассматривалось евклидово расстояние между образами и :

;

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

2) Меры сходства не исчерпываются расстояниями. В качестве примера можно привести неметрическую функцию сходства

,

представляющую собой косинус угла, образованного векторами и , и достигающую максимума, когда их направления совпадают. Этой мерой сходства удобно пользоваться в тех случаях, когда кластеры обнаруживают тенденцию располагаться вдоль главных осей, как это показано на рис. Этот рисунок, в част­ности, показывает, что образ обладает большим сходством с образом х, чем образ z₂, поскольку значение функции s(x, ) больше значения s(x, z₂). Следует, однако, отметить, что исполь­зование данной меры сходства связано определенными ограни­чениями, например такими, как достаточное отстояние класте­ров друг от друга и от начала координат.

3) Нашла широ­кое распространение в информационном поиске, нозологии

(классификации болезней) и таксономии (классификации видов животных и растений), так называемая мера Тани­мато, определяемая как

2.1. Простой эвристический алгоритм определения клаcтеров

Пусть дано множество N изображений объектов и определена произвольная неотрицательная пороговая величина ; Необходимо получить представление о количестве кластеров.

Алгоритм:

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

2. Вычисляем расстояние между образом и центром кластера по формуле

.

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

Пусть условие выполнено, т.е. – центр нового кластера.

4. Вычисляем расстояния и от до центров кластеров и

5. Если оба расстояния оказываются больше порога , то учреждается новый центр кластера , в противном случае изображение объекта зачисляется в тот кластер, чей центр к нему ближе.

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

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

Хотя это алгоритм обладает рядом очевидных недостатков, он позволяет просто и быстро получить приблизительные оценки основных характеристик заданного набора данных. Кроме того, этот алгоритм привлекателен с вычислительной точки зрения, так как для выявления центров кластеров, соответствующих определенному значению порога , ему требуется только однократный просмотр выборки. Практически же, для того чтобы хорошо понять геометрию распределения образов с помощью такой процедуры, приходится проводить многочисленные эксперименты с различными значениями порога и различными исходными точками кластеризации. Поскольку изучаемые образы обычно имеют высокую размерность, визуальная интерпретация результатов исключается; поэтому необходимая информация добывается в основном при помощи сопоставления после каждого цикла просмотра данных расстояний, разделяющих центры кластеров, и количества образов, вошедших в различные кластеры. Полезными характеристиками являются также ближайшая и наиболее удаленная от центра точки кластера и различие размеров отдельных кластеров. Информацию, полученную таким образом после каждого цикла обработки данных, можно использовать для коррекции выбора нового значения порога и новой исходной точки классификации в следующем цикле. Можно рассчитывать на получение с помощью подобной процедуры полезных результатов в тех случаях, когда в данных имеются характерные «гнезда», которые достаточно хорошо разделяются при соответствующем выборе значения порога.