Технологии искусственного интеллекта. Распознавание без учителя. Методы кластеризации

В задаче распознавания без учителя машинной системе предоставляется лишь совокупность образов x_i ∈ Χ, i =1, …, M. На основе этих образов система должна не только построить решающее правило ϕ: Χ → Α, но и сформировать само множество классов А ={ a ₁, …, a_d }. Поскольку решающее правило относит каждый образ обучающей выборки к одному из классов, задача, по сути, сводится к тому, чтобы объединить образы обучающей выборки в группы (на основе которых и формируются классы). Такое объединение называется группированием. Коль скоро группирование осуществлено, для построения решающего правила могут быть применены ранее рассмотренные методы распознавания с учителем. Здесь, однако, возникает вопрос: на каком основании какие-то образы следует относить к одной группе, а какие-то – к другой?

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

Кратко рассмотрим несколько эвристических алгоритмов кластеризации. Один такой алгоритм основан на вычислении k внутригрупповых средних, или кратко алгоритм k средних. Алгоритм состоит из следующих шагов (используем переменную d для обозначения числа классов):

1. Каждому из d кластеров произвольным образом назначаются их центры (или эталонные образы) x _{0 i}. Часто в качестве этих центров выступают первые (или случайно выбранные) d образов обучающей выборки x _{0 i} = x_i, i =1, …, d.

2. Каждый образ выборки относится к тому классу, расстояние до центра которого минимально:

3. Центры кластеров пересчитываются, исходя из того, какие образы к каждому из них были отнесены:

, где M_j – количество образов, попавших в класс a_j.

4. Шаги 2 и 3 повторяются, пока не будет достигнута сходимость, то есть пока классы не перестанут изменяться.

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

Одним из ограничений алгоритма k средних является необходимость задания числа классов. Чтобы решить эту проблему, можно выполнить алгоритм для различного числа классов и выбрать среди решений некоторое лучшее решение. При выборе по критерию минимальной суммы расстояний от образов до центров классов предпочтение будет отдаваться решениям с большим числом классов, поэтому требуется применять более сложные критерии.

Существуют и алгоритмы, не требующие задания числа классов. Однако во многих из них присутствует какой-либо иной параметр. Простейший такой алгоритм требует задания порога s * на размер кластера и состоит из шагов:

1. Сформировать один кластер (d = 1) из первого образа обучающей выборки и положить x ₀₁ = x ₁.

2. Выбрать следующий еще нерассмотренный вектор x_i и определить минимальное расстояние . Если это расстояние меньше порога s ′ < s *, то отнести образ к соответствующему классу, в противном случае увеличить число классов d на единицу и сформировать новый класс с центром x _{0 d} = x_d.

3. Повторить шаг 2 последовательно для всех образов обучающей выборки.

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

Хотя для работы этого алгоритма не требуется знание числа классов, ему необходим размер кластеров s *, причем этот размер одинаков для всех классов. Эти два параметра (число классов и размер кластеров) несут примерно одинаковое количество, хотя и немного разной, априорной информации. В связи с этим нельзя сказать, что этот подход предпочтительнее предыдущего. Если он применяется на практике, и порог s * неизвестен, то алгоритм желательно выполнять для различных значений порога и использовать некоторый критерий для выбора лучшего решения.

Этот алгоритм является простейшим примером инкрементного обучения. Образы в нем предъявляются последовательно, и его работу можно интерпретировать следующим образом: если новый встреченный объект не похож ни на один уже известный класс объектов, то это объект нового, ранее не встречавшегося класса. Если же объект может быть надежно классифицирован, то он пополняет информацию о выбранном классе: на его основе уточняется модель класса (в данном случае смещается вектор средних).

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

Алгоритм ISODATA (Iterative Self-Organizing Data Analysis Techniques) основывается на алгоритме k средних, но включает набор оказавшихся полезными на практике эвристик и параметры по их настройке. Одним из задаваемых априори параметров является желаемое число кластеров K. Это число выступает в качестве рекомендации: в результате работы алгоритма может быть построено как меньшее, так и большее число кластеров, но оно будет не сильно отличаться от значения K. Приведем лишь основные эвристики:

1. Ликвидируются кластеры, в состав которых входит менее чем заданное число элементов.

2. Для каждого текущего кластера определяется направление максимальной вытянутости. Наиболее вытянутый кластер может быть расщеплен на два. Решение о расщеплении принимается с учетом размера кластера в направлении вытянутости (этот размер может сравниваться с фиксированным порогом и отклонением от среднего размера всех кластеров, а также общего числа кластеров, которое должно быть мало (с учетом параметра K).

3. Попарно сливаются кластеры, расстояние между центрами которых меньше заданного порога, если число кластеров велико (с учетом параметра K).

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