Лекция 7 (Гиренко - Лекции)

Лекция 7. Метод предельных упрощений (МПУ). Коллективы решающих правил. Методы и алгоритмы анализа структуры многомерных данных

Метод предельных упрощений (МПУ)

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

В МПУ предполагается, что разделяющая функция задается заранее в виде линейного (самого простого) полинома, а процесс обучения состоит в конструировании такого пространства минимальной размерности, в котором заранее заданная наиболее простая разделяющая функция безошибочно разделяет обучающую последовательность. МПУ назван так потому, что в нем строится самое простое решающее правило в пространстве небольшой размерности, т. е. в простом пространстве.

Пусть на некотором множестве объектов V заданы два подмножества V^*₁ и V^*₂, определяющих собой образы на обучающей последовательности V. Рассмотрим i-е свойство объектов, такое, что некоторые объекты обучающей последовательности этим свойством обладают, а другие — нет. Пусть заданным свойством обладают объекты, образующие подмножество V_1i, а объекты подмножества V_2i этим свойством не обладают (V_1i  V_2i = V). Тогда i-е свойство называют признаком первого типа относительно образа V^*₁, если выполняются соотношения

и

(ф. 1)

и признаком второго типа, если выполняются

и (ф. 2)

Если же выполняются соотношения

и (ф. 3)

то i-е свойство считается признаком первого типа относительно образа V^*₂, а если выполняются

и (ф. 4)

то это же свойство объявляется признаком второго типа относительно образа V^*₂. Если свойство не обладает ни одной из приведенных особенностей, то оно вообще не относится к признакам и не участвует в формировании пространства.

Одинаковые признаки — это два признака x_i и x_j, порождающие подмножества V_1j, V_2j, V_1i, V_2i, такие, что

V_1j= V_1i и V_2j= V_2i. (ф. 5)

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

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

(ф. 6)

либо уравнением

(ф. 7)

Каждый объект относится к одному из образов в зависимости от того, по какую сторону относительно плоскости находится соответствующий этому объекту вектор в пространстве признаков размерности n.

Коллективы решающих правил

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

Для рационального использования особенностей различных алгоритмов при решении задач распознавания возможно объединить различные по характеру алгоритмы распозна­вания в коллективы, формирующие классификационное решение на основе правил, принятых в теории коллективных решений. Пусть в некоторой ситуации Х принимается решение S. Тогда S=R(X), где R—алгоритм принятия решения в ситуации X. Предположим, что существует L различных алгоритмов решения задачи, т. е. S_l=R_l(X), l=1, 2, ... , L, где S_l—решение, получен­ное алгоритмом R_l. Будем называть множество алгоритмов {R}={R₁, R₂, ..., R_i.} коллективом алгоритмов решения задачи (кол­лективом решающих правил), если на множестве решений S_l в любой ситуации Х определено решающее правило F, т. е. S=F(S₁, S₂, ..., S_L, X). Алгоритмы R_l принято называть членами коллектива, S_l — решением l-го члена коллектива, а S — коллек­тивным решением. Функция F определяет способ обобщения ин­дивидуальных решений в решения коллектива S. Поэтому синтез функции F, или способ обобщения, является центральным момен­том в организации коллектива.

Принятие коллективного решения может быть использовано при решении различных задач. Так, в задаче управления под си­туацией понимается ситуация среды и целей управления, а под решением — самоуправление, приводящее объект в целевое состоя­ние. В задачах прогноза Х — исходное, а S — прогнозируемое состояние. В задачах распознавания ситуацией Х является опи­сание объекта X, т. е. его изображение, а решением S — номер образа, к которому принадлежит наблюдаемое изображение. Индивидуальное и коллективное решения в задаче распозна­вания состоят в отнесении некоторого изображения к одному из образов. Наиболее интересными коллективами распознающих ал­горитмов являются такие, в которых существует зависимость веса каждого решающего правила R_l от распознаваемого изображения. Например, вес решающего правила R_l может определяеться соотно­шением

(ф. 8)

где B_l — область компетентности решающего правила R_l. Веса решающих правил выбираются так, что

(ф. 9)

для всех возможных значений X. Соотношение (ф. ) означает, что решение коллектива определяется решением того решающего правила Ri, области компетентности которого принадлежит изоб­ражение объекта X. Такой подход представляет собой двухуров­невую процедуру распознавания. На первом уровне определяется принадлежность изображения той или иной области компетент­ности, а уже на втором — вступает в силу решающее правило, компетентность которого максимальна в найденной области. Решение этого правила отождествляется с решением всего кол­лектива. Основным этапом в такой организации коллективного решения является обучение распознаванию областей компетентности. Прак­тически постановкой этой задачи различаются правила органи­зации решения коллектива. Области компетентности можно ис­кать, используя вероятностные свойства правил коллектива, можно применить гипотезу компактности и считать, что одина­ковым правилам должны соответствовать компактные области, которые можно выделить алгоритмами самообучения. В про­цессе обучения сначала выделяются компактные множества и соответствующие им области, а затем в каждой из этих областей восстанавливается свое решающее правило. Решение такого пра­вила, действующего в определенной области, объявляется дикта­торским, т. е. отождествляется с решением всего коллектива.

В перцептроне каждый A-элемент может интерпретироваться как член коллектива. В процессе обучения все A-элементы при­обретают веса, в соответствии с которыми эти A-элементы участ­вуют в коллективном решении. Особенность каждого A-элемента состоит в том, что он действует в некотором подпространстве ис­ходного пространства, характер которого определяется связями между S- и A-элементами. Решение, получаемое на выходе перцептрона, можно интерпретировать как средневзвешенное реше­ние коллектива, состоящего из всех A-элементов.

Методы и алгоритмы анализа структуры многомерных данных

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

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

Критерий качества кластеризации в той или иной мере отражает следующие неформальные требования:

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

б) объекты разных групп должны быть далеки друг от друга;

в) при прочих равных условиях распределения объектов по группам должны быть равномерными.

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

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

Другой важной величиной в кластерном анализе является расстояние между целыми группами объектов. Приведем примеры наиболее распространенных расстояний и мер близости, характеризующих взаимное расположение отдельных групп объектов. Пусть w_i — i-я группа (класс, кластер) объектов, N_i — число объектов, образующих группу w_i, вектор _i — среднее арифме­тическое объектов, входящих в w_i (другими словами [_i — «центр тяжести» i-й группы), a q ( w_l, w_m ) — расстояние меж­ду группами w_l и w_m