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

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

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

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

2. Изучить:

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

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

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

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

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

5.

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

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

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

;

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

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

,

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

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

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