Fuzzy graph-schemes in pattern recognition © 1992 Dmitry A.Kazakov

Введение

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

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

Что касается эмпирических методов, таких как факторы уверенности экспертной системы MYCIN [Экс87, Уот89] и их развитие в системе Intersensor [Mak83], или байесовский подход оценки свидетельств (PROSPECTOR [Уот89]), то не известны границы их применимости.

С другой стороны, теория нечетких множеств, сформулированная Л.А.Заде четверть века назад, предлагает естественный аппарат для представления таких понятий теории распознавания образов, как объект и класс, «размытость» которых не обязательно должна выражаться в случайности. Классы и объекты, в конечном итоге, интуитивно определяются наблюдателем, в воображении которого они представляются скорее нечеткими нежели случайными. Альтернативой теории вероятности является теория возможностей, развиваемая с 50-х годов. В отличии от вероятностного пространства, возможностное строится из взаимно вложенных друг в друга событий, что хорошо соответствует стратегии классификации « сверху-вниз », когда каждый шаг классификации все более сужает рассматриваемую область пространства образов, предполагая иерархичность его строения.

Настоящая работа посвящена исследованию вопросов использования теории нечетких множеств и теории возможностей в задачах распознавания образов. При этом, основное внимание было уделено деревьям решений. Деревья решений это универсальное средство представления знаний, близкое к продукциям. Наиболее широко используемые до сих пор четкие и вероятностные деревья решений сужают возможности методов распознавания из-за неадекватности детерминистских и вероятностных моделей. Выше сказанное делает актуальным использование нечетких деревьев. К деревьям решений тесно примыкает понятие граф-схемы, предложенное впервые для описания алгоритмов Л.А.Калужининым в 1959 г. Как показано в работах [Орл80] граф-схемы оказались эффективным средством представления решающих правил.

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

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

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

В соответствии с указанными целями работы, в диссертации решены следующие задачи:

1. Получена формальная постановка задачи нечеткого обучения с учителем в терминах теории возможностей.

2. Разработаны алгоритмы и методы построения нечетких классификаторов на основе нечетких граф-схем.

3. Разработаны архитектура и программная реализация системы нечеткого обучения.

Методы исследования. Для решения указанных задач используется аппарат теории нечетких множеств Заде, теории возможностей, теории Демпстера-Шейфера и системы программирования языка Ada.

Научной новизной работы являются:

1. Обобщение понятия граф-схемы принятия решения на основе использования:

• пары граф-схем, одна из которых оценивает возможности, а другая - необходимости принадлежности классифицируемого объекта классам;
• нечетких множеств в качестве весов дуг;
• условных возможностей и необходимостей в качестве факторов уверенности переходов по дугам граф-схемы.

2. Разработка метода построения нечеткой граф-схемы по нечеткому обучающему множеству и его исследование.

3. Метод бинаризации признаков с упорядоченными шкалами и его использование при построении граф-схемы.

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

Практическая ценность.

1. Разработан конкретный алгоритм построения нечеткой граф-схемы.

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

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

Список обозначений

- булево множество {0,1}
C(·) - возможность
² - пространство классов
D -декартово произведение областей значений признаков
D_i - область значенийi -го признака
E -решающее правило типа « перечисления »
- пространство нечетких описаний
- пространство нечетких признаков
G - граф-схема
G_C - граф-схема возможностей
G_N - граф-схема необходимостей
Inf - точная нижняя грань
N(·) - возможность
- множество целых чисел
P(·) - вероятность
p, q - нечеткие события
p^j - класс j
- множество вещественных чисел
Sup - точная верхняя грань
x - векторный признак, составленный из отдельных признаков
x_i- признак i
Ω - множество элементарных событий
ω - элементарное событие
π - распределение возможностей
2^X - степенное множество -множество всех подмножеств X
[0,1]^X - множество всех нечетких подмножеств X
- max-композиция нечетких отношений
- min-композиция нечетких отношений
- пересечение множеств
- объединение множеств
& - булево И
V - булево ИЛИ
~ - эквивалентность обучающих множеств

to chapter one