31. Задача распознавания без учителя на основе метода потенциальных функций, Алгоритм решения.

32. Алгоритм распознавания, основанный на вычислении оценок – перечислить 6 этапов.

Первые алгоритмы вычисления оценок появились в 60-е годы [18]. Они хорошо зарекомендовали себя при решении практических задач, таких, как задачи геологического прогнозирования, медицинской диагно­стики и т.п. На базе этих алгоритмов были в дальнейшем [28] созданы модели алгоритмов вычисления оценок. В большом цикле работ эти моде­ли были подробно изучены, а также использованы для решения разнооб­разных прикладных задач.

Особую роль в формировании модели вычисления оценок сыграл тесто­вый алгоритм. Этот алгоритм базируется на понятии теста, введенном в 1956 г. С.В. Яблонским. Описано большое число модификаций тесто­вого алгоритма, их машинных реализаций и применений.

Определение теста по Яблонскому С.В.

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

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

Тупиковый тест – это как бы неизбыточные описания объектов, характеризуемых строками таблиц.

Тупиковых тестов может быть довольно много. Существуют оценки числа тупиковых тестов. Яблонский и Чегис впервые описали алгоритм построения тестов.

Построить пример!

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

Пусть задана обучающая последовательность объектов

x₁ , …, x_r ,x_{r +1} ,…,x_r ,…,x_{r +1} ,…,x_{r ,}

принадлежащих L непересекающимся классам К₁, К₂, …, К_L , причем пер­вые r₁ объектов - из класса К₁, следующие r₂ – r₁ объектов - из К₂ и т.д.

Пусть пространство объектов Х - n-мерно. Это означает, что любое объект х есть набор п характеристик (признаков), опи­сывающих объект.

Обозначим признаки, характеризующие объект x_j так:

x_j = (α_j , α_j ,…, α_j ).

Будем говорить, что обучающая последовательность объектов

x₁ , …, x_r ,x_{r +1} ,…,x_r ,…,x_{r +1} ,…,x_r

образует таблицу обучения T_n,r .

Каждой строке этой таблицы отвечает одно из объектов обучающей последовательности.

Поскольку все объекты на обучающей последо­вательности относятся к тому или иному классу, то можно считать, что таблица T_{n, r} разбита на L групп непересекающихся строк.

Сформулируем основную задачу. Пусть задана таблица обучения T_n,r и некоторое объект s на Х. Требуется указать класс K_j , j = 1, 2,…, L, к которому принадлежит объект s.

Перейдем теперь к описанию класса алгоритмов, решающих основную задачу. Будем называть этот класс классом алгоритмов, основанных на ВО, а каждый конкретный алгоритм - алгоритмом ВО. Класс алгоритмов, основанных на ВО, задается посредством описания шести элементов его определяющих.

1. система опорных множеств,

2. функция близости,

3. ВО по строкам фиксированного опорного множества,

4. ВО для класса по опорному множеству,

5. оценка для класса по системе опорных множеств,

6. решающее правило.

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