3.4. Алгоритмы кластеризации. Обучение и самообучение распознающих систем
Проблема выявления кластеров. Выявление кластеров – это скорее искусство, чем строгая наука, притом «искусство» весьма эмпирическое. Притом, что качество работы алгоритма классификации существенным образом зависит от того, как были выделены кластеры.
Для кластеризации образов вначале следует вести меру сходства (подобия) образов. Ранее мы для этого рассматривали евклидово расстояние
Di (x, z) = || x z ||
чем меньше расстояние между образами в пространстве признаков – тем больше сходство. Однако евклидовой метрикой все не исчерпывается.
Еще один способ рассчитать меру близости дает метрика
S(x,
z)=
Она определяет косинус угла между векторами x и z и достигает максимума, когда их направления совпадают:
На рисунке 3 образ z1 обладает большим сходством с образом x, чем образ z2 . Использование этой меры, однако, влечет некоторые ограничения. В частности – кластеры должны на достаточное расстояние отстоять друг от друга и от начала координат.
Когда рассматриваются качественные признаки со значениями из множества {0,1}, этой мере можно дать интересную интерпретацию. Если xi = 1, считается, что двоичный образ обладает i-м признаком. В таком случае числитель x`z показывает общее число совпадающих признаков, а знаменатель
||x||
||z|| =
среднее геометрическое числа признаков, которыми обладают образы x и z. Тогда функция S(x, z) есть мера наличия общих признаков у образа образы x и образа z.
Двоичным вариантом этой же формулы служит мера Танимото:
S(x,
z)=
Все перечисленные меры – не единственно возможные. Можно «придумать» и другие. Однако указанные довольно типичны и находят широкое применение в проблеме распознавания образов.
Проблема кластеризации не ограничивается выбором меры сходства образов. В принципе, критерий кластеризации может или воспроизводить некоторые эвристические соображения, или основываться на минимизации (максимизации) какого либо показателя качества.
Подход к кластеризации, предусматривающий использование показателя качества, связан с разработкой процедур, которые обеспечат экстремум выбранного показателя качества. Одним из таких показателей (причем довольно популярным) является сумма квадратов ошибки:
J =
,
где Nc – число кластеров, Sj – множество образов, относящихся к j-му кластеру, а
mj
=
вектор выборочных средних значений для множества Sj; Nj характеризует количество образов, входящих во множество Sj. Данный показатель качества характеризует общую сумму квадратов отклонений характеристик всех образов, входящих в некоторый кластер, от соответствующих средних значений по кластеру.
Алгоритмы кластеризации. Пороговый алгоритм.Пусть имеется N образов {x1, x2, … xN }.
Шаг 1. Объявим произвольный образ, например x1 центром кластера 1
Шаг 2. Введем порог кластеризации T.
Шаг 3. Возьмем образ x2. Если он отстоит от x1 менее, чем на T, включим его в кластер 1, иначе – считаем его центром нового кластера 2.
Шаг 4. Возьмем образ x3. Если он отстоит от x1 менее, чем на T, включим его в кластер 1, иначе – сравниваем с кластером 2. Если он отстоит от кластера 2 менее, чем на порог – включаем его в кластер 2, иначе – объявляем кластер 3.
И так далее…
Алгоритм максиминного расстояния. Аналогичен предыдущему, только вначале выявляет самые удаленные образы.
Шаг 1. Объявим произвольный образ, например x1 центром кластера 1
Шаг 2. Отыскиваем самый удаленный образ и назначаем его центром кластера 2.
Шаг 3. Вычисляем расстояние между центрами кластеров 1 и 2 и остальными образами и выделяем в каждой паре (образ x центры z1 и z2) минимальное.
Шаг 4. Выделяем максимальное из этих минимальных расстояний. Если оно сопоставимо с расстоянием между z1 и z2 (например, не менее половины) объявляем новый кластер 3, иначе СТОП.
Шаг 5. Вычисляем расстояние между центрами кластеров 1, 2, 3 и остальными образами и выделяем в каждой тройке минимальное.
Шаг 6. Выделяем максимальное из этих минимальных расстояний. Если оно сопоставимо с расстоянием между zi и zj , где i,j = 1,2,3 объявляем новый кластер 4, иначе СТОП.
И т.д.
Оставшиеся образы – не центры классов группируем по минимуму расстояния между установленными центрами