Распознавание не основе методов нечеткой логики

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 00:27, 25 мая 2017.

Интенсивные исследования по созданию систем искусственного интеллекта (СИИ) проводятся с начала 60-х годов. Основной целью являлась разработка математических и программных средств моделирования процессов человеческого мышления для автоматического решения различных прикладных и теоретических задач. К 80-м годам пришло понимание того, что эффективность систем такого рода зависит от знаний, которыми они обладают. Эти знания не только чисто эмпирические (полученные эмпирическим путем), но и эвристические - набор правил и рекомендаций, которыми следует пользоваться в той или иной ситуации, возникающей в данной предметной области. Такого рода эмпирические правила поставляются экспертами, поэтому системы и получили название экспертных систем (ЭС). В самом общем виде ЭС - это программная система, способная в данной предметной области вырабатывать решения, по эффективности, конкурирующие с решениями эксперта. Задачи, которые целесообразно решать с помощью ЭС, могут быть охарактеризованы следующими свойствами:

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

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

В случае решения задач распознавания применение ЭС, основанных на нечеткой логике (см. Приложение 7) позволяет оптимальным образом сочетать детерминированный и эвристический подходы к их решению.

Поскольку однозначные алгоритмические выводы как правило отсутствуют, то необходимо иметь возможность контроля хода логических выводов ЭС, соответствующая система называется «подсистема объяснений».

Выделяют следующие основные составляющие (подсистемы) ЭС:

  • база знаний;
  • редактор базы знаний;
  • машина (механизм) логического вывода;
  • интерфейс с пользователем, основанный на псевдоестественном языке;
  • подсистема объяснений.

Отметим, что обязательными для любой ЭС являются три первые подсистемы. В ближайшее время ожидается бурное развитие рынка ЭС и сопутствующих им компонент. Среди последних выделяют программные средства, включая языки программирования типа ПРОЛОГ и ЛИСП, инструментальные средства разработки ЭС, автоматизированные рабочие места ЭС (АРМ ЭС) и специальные ЭВМ для решения задач искусственного интеллекта (ИИ).

Функциональные характеристики примера программной реализации

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

Реляционная модель данных

Реляционная модель была попыткой упростить структуру базы данных. В ней отсутствовали явные указатели на предков и потомков, а все данные были представлены в виде простых таблиц, разбитых на строки и столбцы. На Рисунке 1 показан пример реляционной базы данных, содержащей информацию о заказах.

Рисунок 1. Пример организации реляционной базы данных.

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

Реляционная СУБД отвечает за поддержку структуры и решает следующие задачи:

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

В данном примере в качестве СУБД была выбрана MySQL. Гибкость СУБД MySQL обеспечивается поддержкой большого количества типов таблиц: пользователи могут выбрать как таблицы типа MyISAM, поддерживающие полнотекстовый поиск, так и таблицы InnoDB, поддерживающие транзакции на уровне отдельных записей. Более того, СУБД MySQL поставляется со специальным типом таблиц EXAMPLE, демонстрирующим принципы создания новых типов таблиц. Благодаря открытой архитектуре и GPL-лицензированию, в СУБД MySQL постоянно появляются новые типы таблиц.

Для программной реализации используется язык SQL как стандартный язык баз данных.

Обзор возможностей языка SQL

SQL является инструментом, предназначенным для обработки и чтения данных, содержащихся в компьютерной базе данных. SQL - это сокращенное название структурированного языка запросов (Structured Query Language). Как следует из названия, SQL является языком программирования, который применяется для организации взаимодействия пользователя с базой данных. SQL работает только с базами данных одного определенного типа, а именно реляционными БД. Язык SQL представляет пользователю интерфейс общения с базой данных, абстрагированный от внутренней архитектуры этой базы данных. Допустим, в вычислительной системе имеется база данных, в которой хранится важная информация. Если вычислительная система относится к сфере бизнеса, то в базе данных может храниться информация о материальных ценностях, выпускаемой продукции, объемах продаж и зарплате. В базе данных на персональном компьютере может храниться информация о выписанных чеках, телефонах и адресах или информация, извлеченная из более крупной вычислительной системы. Компьютерная программа, которая управляет базой данных, называется системой управления базой данных, или СУБД.

Если пользователю необходимо прочитать данные из базы данных, он запрашивает их у СУБД с помощью SQL-запроса. СУБД обрабатывает запрос, находит требуемые данные и посылает их пользователю. Процесс запрашивания данных и получения результата называется запросом к базе данных: отсюда и название - структурированный язык запросов.

Сегодня SQL представляет собой нечто гораздо большее, чем простой инструмент создания запросов, хотя именно для этого он и был первоначально предназначен. Несмотря на то, что чтение данных по-прежнему остается одной из наиболее важных функций SQL, сейчас этот язык используется для реализации всех функциональных возможностей, которые СУБД предоставляет пользователю, а именно:

  1. Организация данных. SQL дает пользователю возможность изменять структуру представления данных, а также устанавливать отношения между элементами базы данных.
  2. Чтение данных. SQL дает пользователю или приложению возможность читать из базы данных, содержащиеся в ней данные и пользоваться ими.
  3. Обработка данных. SQL дает пользователю или приложению возможность изменять базу данных, т.е. добавлять в нее новые данные, а также удалять или обновлять уже имеющиеся в ней данные.
  4. Управление доступом. С помощью SQL можно ограничить возможности пользователя по чтению и изменению данных и защитить их от несанкционированного доступа.
  5. Совместное использование данных. SQL координирует совместное использование данных пользователями, работающими параллельно, чтобы они не мешали друг другу.
  6. Целостность данных. SQL позволяет обеспечить целостность базы данных, защищая ее от разрушения из-за несогласованных изменений или отказа системы.

Таким образом, SQL является достаточно мощным языком для взаимодействия с СУБД.

Сам по себе SQL не является ни системой управления базами данных, ни отдельным программным продуктом. Нельзя пойти в компьютерный магазин и «купить SQL». SQL - это неотъемлемая часть СУБД, инструмент, с помощью которого осуществляется связь пользователя с ней.

Ядро базы данных является сердцевиной СУБД; оно отвечает за физическое структурирование и запись данных на диск, а также за физическое чтение данных с диска. Кроме того, оно принимает SQL-запросы от других компонентов СУБД (таких как генератор форм, генератор отчетов или модуль формирования интерактивных запросов), от пользовательских приложений и даже от других вычислительных систем.

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

Базовая конфигурация системы нечеткой логики с фаззификатором и дефаззификатором представлена на Рисунке 2.

Рисунок 2. Система нечеткой логики с фаззификатором и дефаззификатором.

Фаззификатор отображает «четкую» точку (или значение переменной ) из Х в нечеткие множества из Х. Дефаззификатор отображает нечеткие множества из Y в четкое значение выхода. Базис нечетких правил и механизм нечеткого вывода остаются такими же, как в простых системах нечеткой логики.

Системы нечеткой логики с фаззификатором и дефаззификатором имеют несколько привлекательных черт:

  1. они пригодны для использования в технических системах, так как их входные и выходные переменные принимают реальные значения;
  2. они предоставляют возможность естественного перехода от заключений эксперта к нечетким IF-THEN-правилам;
  3. они предоставляют большую свободу в выборе фаззификатора, механизма нечеткого вывода и дефаззификатора, т.е. можно подобрать систему нечеткой логики, наиболее подходящую для решения конкретной задачи;
  4. могут быть разработаны различные алгоритмы настройки таких систем нечеткой логики, что позволяет эффективно объединять численную и лингвистическую информацию.

Базис нечетких правил. Базис нечетких правил состоит из набора нечетких IF-THEN-правил вида (1). Без потери общности можно рассматривать многовходовую систему нечеткой логики с одним выходом (МISO-систему), т.к. система со многими выходами (MIMO - система) может быть представлена как композиция группы систем, имеющих один выход. Базис нечетких правил является основной частью системы нечеткой логики в том смысле, что остальные ее компоненты используются для интерпретации этих правил и их применения при решении конкретных задач. Практика показывает, что нечеткие IF-THEN-правила в форме (1) предоставляют удобный механизм человеку-эксперту для выражения своих знаний.

Рисунок 3. Пример системы вывода Мамдани-Заде.

Преимущества нечетких систем

Коротко перечислим преимущества fuzzy-систем по сравнению с другими:

  1. возможность оперировать нечеткими входными данными: например, непрерывно изменяющиеся во времени значения (динамические задачи), значения, которые невозможно задать однозначно (результаты статистических опросов, рекламные компании и т.д.);
  2. возможность нечеткой формализации критериев оценки и сравнения: оперирование критериями "большинство", "возможно", преимущественно" и т.д.;
  3. возможность проведения качественных оценок как входных данных, так и выходных результатов: вы оперируете не только значениями данных, но и их степенью достоверности и ее распределением;
  4. возможность проведения быстрого моделирования сложных динамических систем и их сравнительный анализ с заданной степенью точности: оперируя принципами поведения системы, описанными fuzzy-методами, вы во-первых, не тратите много времени на выяснение точных значений переменных и составление описывающих уравнений, во-вторых, можете оценить разные варианты выходных значений.

Структура нечеткого поиска

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

Для параметра цвет используется следующее распределение:

---- brown violet red orange yellow green white grey blue ----
0 1 2 3 4 5 6 7 8 9 10

Для параметра форма используется следующее распределение:

----- rectangular p-shaped L-shaped semicircular round other -----
0 1 2 3 4 5 6 7

Для параметра материал используется следующее распределение:

----- brick block panel monolithic wooden other -----
0 1 2 3 4 5 6 7

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

Для параметра размеры за “0” принимается наименьшее значение, найденное в базе данных (a). За крайнее правое принимается наибольшее значение, найденное в базе данных (b).В общем случае функция принадлежности выглядит следующим образом:

Nech log4.png

Соответственно за параметр выбирается параметр, введенный в поле, а диапазон значений определяется исходя из выбранных значений степени желаемости (0 – все значения от до ; 1 – только искомое значение (с)).

Соответственно при поиске материала , со значением степени желаемости , функция принадлежности примет вид:

Nech log5.png

И, следовательно, поиск будет осуществляться по объектам, имеющим в поле “material” значения “block”, “panel”, “monolithic”.

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

Вторая модификация сужать интервал поиска по введенным значениям желаемости.

Nech log6.png

Структура базы данных

База данных (buildings) состоит из пяти таблиц:

  • buildings, в которой содержатся данные о зданиях (цвет, размеры, форма, материал, координаты);
  • images, в которой содержатся данные о принадлежности объектов к картинкам.
  • colours, materials, shapes – таблицы, в которых содержаться названия.

Запрос к таблице buildings осуществлен с помощью оператора выбора Select, который возвращает одно или множество значений из заданных полей таблицы (colour, dimension, shape, material + для выделения на картинке объекта координаты (x, y)) и удовлетворяющих указанному условию. Запрос состоит из двух частей:

  • статической
SELECT colours.colour_name, buildings.dimension, shapes.shape_name, materials.material_name, images.image_name,
    buildings.coord_x, buildings.coord_y
FROM buildings, images, shapes, materials, colours
WHERE buildings.colour_id= colours.colour_id AND buildings.shape_id=shapes.shape_id
   AND buildings.material_id=materials.material_id AND buildings.images_image_id=images.image_id AND
  • динамической (изменяющейся в зависимости от типа запроса, вида поиска, выбранных отрицаний параметров и упорядочения параметров)

Интерфейс программы.

Программа состоит из одного главного окна имеет 2 режима:

Режимы работы программы: простой поиск (слева) и нечёткий поиск

В режиме простого поиска пользователю доступны следующие функции:

  • Выбор типа поиска (строгий, нестрогий);
Nech log8.png
  • Возможность вывода результатов в упорядоченном виде, выбрав необходимый параметр, по которому будет произведено упорядочение;
Nech log9.png
  • Выбор параметров для поиска по 4 полям (цвет, размеры, форма, материал), выбор производится путем выбора необходимого параметра из выпадающего окна (все значения являются актуальными, т.к. берутся из базы данных);
    Nech log10.png
    поле размеры поддерживает выбор из выпадающей строки, непосредственный ввод желаемого размера, ввод желаемого диапазона поиска (по умолчанию поиск от минимального до максимального из значений, находящихся в базе данных)
Ввод диапазона поиска
  • Возможность отрицания выбранного параметра
    Nech log12.png
    в данном случае будет выполнен поиск (при выборе нестрого типа поиска) всех домов, имеющих любой цвет, кроме оранжевого;

Поиск осуществляется только после нажатия кнопки «Поиск», следовательно, необходимо сначала выбрать все необходимые параметры, и лишь потом осуществить поиск.

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

Nech log13.png

Если найден хотя бы один объект, то становится доступной кнопка «Показать изображение», при нажатии которой появится картинка с подсвеченным объектом:

Nech log14.png

А если найдено 2 и более объекта, то становится доступной панель:

Nech log15.png

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

Режим нечеткого поиска

Режим нечеткого поиска осуществляется путем выбора в главном окне соответствующей функции:

Nech log16.png

В режиме нечеткого поиска доступны все те же поля что и при простом поиске, за исключением поля отрицания выбранного параметра, так как при нечетком поиске данная функция не имеет смысла.

Добавлены поля ввода для выбора желаемого результата по каждому из четырех параметров (цвет, размеры, форма, материал):

Nech log17.png

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

Соответственно так же как и при простом поиске, поиск осуществляется после выбора всех необходимых параметров и нажатия кнопки «Нечёткий поиск».

В правом верхнем углу главного окна находится окно “Сообщения”, отметив которое по каждому из 4-х полей будет выводиться список параметров, задействованных в поиске:

Nech log18.png
Nech log19.png

Также как и при простом поиске, если найден 1 и более объект, становится доступной кнопка «Показать изображения», при нажатии который появляется картинка с подсвеченным объектом, а если найдено более одного объекта, просматривать таблицу удобно используя кнопки навигации, предварительно нажав кнопку «Показать изображение».

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

  1. Сужение диапазона поиска по количеству итераций;
  2. Автоматическое редактирование краевых значений функции принадлежности.

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

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

См. также