Солодовников владимир Игоревич Использование методов принятия решения при проектировании нейросетевых структур обработки данных
Download 215.66 Kb. Pdf ko'rish
|
autoref-ispolzovanie-metodov-prinyatiya-resheniya-pri-proektirovanii-neirosetevykh-struktur-obrabotk
|
Вторая глава посвящена вопросам использования деревьев решения в качестве
инструментария при проектировании нейросетевых структур «интеллектуальной» обработки данных. В ней рассмотрены различные варианты деревьев решения, определены модифицированные деревья и операции над ними. Проведен анализ используемых нейросетевых парадигм, направленный на формулировку правил построения наиболее оптимальных сетей, сформированы критерии их применимости для решения конкретных задач, тем самым, осуществлено построение модифицированных деревьев решений. Рассмотрены вопросы предобработки, кодирования и визуализации исходных данных, а также проверки их на непротиворечивость. Определен способ ускорения процесса принятия решений и придания дополнительных возможностей в конструировании механизмов вывода с помощью семантических сетей. Деревья, использующиеся в теории принятия решений, оперируют такими понятиями, как распределения условных вероятностей различных состояний, исходов, последствий, при этом лицо, принимающее решение (ЛПР), должно руководствоваться принципом максимизации ожидаемой полезности при выборе той или иной альтернативы. Это требует от пользователя информации, которая может - 8 - быть ему неизвестна или недоступна в силу его квалификации, т.е. в таком виде данный подход при проектировании нейросетевых структур обработки данных хоть и применим, но слишком сильно усложняет задачу. В искусственном интеллекте используются упрощенные деревья решений, которые представляют собой способ представления правил в иерархической, последовательной структуре и основаны на алгебре высказываний. Но такая конструкция является упрощенной и не способна полностью описать весь процесс принятия решений при проектировании архитектуры и вычислении параметров нейросети для решения поставленной задачи на имеющихся данных. Данное обстоятельство потребовало разработки модифицированных деревьев решения, способных использовать логику предикатов первого порядка, обеспечивающих необходимую гибкость при принятии решений и позволяющих: - производить вычисления, как в узлах дерева, так и на его ребрах и на основе полученных результатов принимать решение, - использовать операции разбиения для выделения фрагментов из общего дерева для подробного рассмотрения отдельных подзадач, - в случае необходимости осуществлять уточнение полученного решения с помощью дальнейшего раскрытия вершин вывода, - создавать многоуровневую модель принятия решений, как для опытного, так и для неподготовленного пользователя, путем подстановки большинства значений по умолчанию и минимального уточнения полученных решений. Область определения и значений модифицированного дерева решений включает в себя следующие переменные: - переменные вывода переменная, определенная на домене (множестве значений) - переменные решений переменная, определенная на домене Дерево решений состоит из вершин двух типов, представленных на рисунке 1, 1) Вершина "решение" 2) Вершина "вывод" i где - отношение, определенное на домене переменной решений - отношение, определенное на домене переменной вывода отношение, определенное на множестве значений, удовлетворяющих отношению П, На множестве таких вершин была введена операция раскрытия вершины, которая предполагает пару родительская-дочерняя и зависит от их типа. Существуют следующие ситуации: -9- 1. Родительской является вершина "решение", а дочерней вершина "вывод". Родитель: вершина "решение". Потомок: вершина "вывод". Формальной записью такой операции является: и может быть трактована как: «Если 2. Как родительской, так и дочерней являются вершины "решение". Родитель: вершина "решение". Потомок: вершина "решение". Формально эта ситуация может быть записана как: Трактовкой является выражение: которое определяет пару условий, причем второе условие обусловлено выбором дуги второй вершины. 3. Как родительской, так и дочерней являются вершины "вывод". Родитель: вершина "вывод". Потомок: вершина "вывод". Формально можно записать: Трактовкой служит выражение: которое определяет уточнение вывода. 4. Родительской является вершина "вывод", а дочерней вершина "решение". Родитель: вершина "вывод". Потомок: вершина "решение". Формальной записью операции является: что может трактоваться как: Данная операция определяет формальное дерево решений. Таким образом, имеющиеся вершины и введенные на них операции раскрытия позволяют построить дерево. Процедура принятия решения происходи 1 сверху вниз от корня к листьям. Результаты работы дерева решений формулируются в виде фактов. Могут быть выделены три вида фактов. 1. Общий факт - пути от корня до вершин вывода, листьев дерева решения, в которых значения переменной вывода совпадают. Формальной записью общего факта является выражение вида: 2. Факт - экземпляр общего факта, т.е. для каждого отношения выбрано конкретное значение, удовлетворяющее отношению. 3. Частичный факт - путь до вершины "вывод", не являющийся листом. Над пространством деревьев решений были определены операции разбиения и объединения. Операция разбиения направлена на выделение частных деревьев из полного дерева решений, что аналогично разбиению глобальной задачи на подзадачи с определенными ограничениями. В свою очередь, разбиение подразделяется на две составляющие. -10- 1. Вертикальное разбиение. - Выделение поддерева, в котором все вершины листья, содержат одну и ту же переменную вывода, т.е. поддерево для определения различных значений определенной переменной вывода. - Выделение поддерева, в котором все вершины листья содержат одинаковые ограничения (отношения) для переменной вывода. - Выделение поддеревьев, в которых вершины листья содержат одинаковые значения переменной вывода, что соответствует нахождению общих фактов для данной переменной вывода и ее значений. 2. Горизонтальное разбиение, соответствующее разбиению от корня до ближайших вершин "вывод" и от каждой промежуточной вершины "вывод" (как корня) до следующих. Операция объединение является обратной разбиению и осуществляет формирование общего дерева решений из его фрагментов (поддеревьев). Могут быть выделены такие виды объединений как: 1. Объединение дополнение 2. Объединение уточнение. Объединение дополнение заключается в увеличении количества альтернатив выбора исходов из вершины "решение" с дальнейшим их выводом (прикрепление соответствующего поддерева к дереву по определенному значению параметра). Данное действие соответствует дополнительному разбиению множества возможных значений X на подмножества. Объединение уточнение сопоставляет вершине "вывод" некоторого дерева решений другое дерево, корень которого соответствует выбранной вершине "вывод". Таким образом, происходит дальнейшее раскрытие вершины "вывод", н она из факта трансформируется в частичный факт. Определенные таким образом деревья, в частности, позволяют решать задачи выбора и проектирования нейросетевых структур. Упрощается процесс определения значений параметров нейросетей, в связи с возможностью разбиения общего дерева решений на фрагменты, что позволяет осуществлять решение отдельных подзадач в рамках глобальной задачи. Построение деревьев решения осуществляется на основе правил, характеризующих объекты предметной области. Для этого был проведен анализ ряда нейросетевых парадигм, направленный на формулировку правил построения в некотором смысле оптимальных сетей, сформированы критерии их применимости для решения конкретных задач. Проанализированы зависимости архитектуры сети (количество слоев и нейронов в каждом слое) от входных данных. Для каждого этапа проектирования строились частные деревья решения. Первым этапом нейросетевой обработки информации, вне зависимости от решаемой задачи и используемой архитектуры, является подготовка имеющихся данных. Общий принцип предобработки, состоит в таком кодировании и нормировке непротиворечивых данных, чтобы добиться максимизации энтропии входов и выходов. Следующий этап включает в себя выбор структуры и параметров нейросети в зависимости от задач, ставящихся пользователем и уже предобработанных данных. Причем от уловия задачи главным образом зависит выбор нейросетевой парадигмы, тогда как выборка данных, определяющая общее число примеров и размерность пространства входных признаков, влияет на число нейронов в слоях. -11- Для решения задач классификации, прогнозирования, аппроксимации функциональных зависимостей применимы сети прямого распространения. Главным представителем сетей такого класса является многослойный персептрон. Этот вид нейросетей получил широкое распространение для решения задач распознавания образов, фильтрации шумов, предсказания временных рядов, идентификации, адаптивного или нелинейного управления. Причина популярности персептронов обусловлена широким кругом доступных им задач, для которых они являются: во- первых, универсальными, а во-вторых - эффективными устройствами. Круг задач решаемых RBF-сетью близок к многослойному персептрону, но основным ее отличием является другой способ представления пространства входных признаков, т.е. ей соответствует групповое представление, тогда как многослойному персептрону - плоскостное. В следствии чего, RBF-сеть не умеет экстраполировать свои выводы за область известных данных, а значит способна отслеживать аномалии. Также стоит отметить и лучшую скорость обучения и возможность быстрого дообучения в режиме реального времени (on-line) по сравнению с многослойным персептроном. Но перед использованием RBF-сети желательно выделение классов в имеющихся данных, т.е. решение задачи кластеризации. В наиболее общей форме задача кластеризации может быть сформулирована следующим образом: Пусть Е - пространство векторов данных - пространство ядер и каждому классу соответствует некоторое ядро Для каждых определяется мера близости Требуется найти набор и з я д е р и разбиение н а к л а с с о в минимизирующее Другими словами, необходимо найти оптимальное разбиение имеющейся выборки данных на некоторое, необязательно изначально определенное, количество классов, при этом классом будет являться группа векторов, расстояние между которыми внутри этой группы меньше, чем расстояние до соседних групп. Для решения задач кластеризации в работе используются сеть динамических ядер и самоорганизующиеся карты Кохонена. Отличительной особенностью таких сетей является способность к самообучению, т.е. они обучаются понимать саму структуру данных, самостоятельно выделяют во входном множестве группы (классы) схожих объектов и выявляют признаки, характеризующие ту или иную группу. Так сеть динамических ядер обладает тем свойством, что наряду с настройкой весовых коэффициентов, позволяет корректировать число нейронов кластерного слоя, осуществлять проверку классов на слияние, выявлять новые и удалять не удовлетворяющие некоторым критериям классы. В свою очередь, особенность структуры кластерного слоя самоорганизующихся карт Кохонена позволяет использовать их для визуального представления данных. Визуализация данных предполагает получение тем или иным способом отображения совокупности объектов на числовую ось, на плоскость или трехмерный объем, максимально отражающего особенности распределения этих объектов в многомерном пространстве в рамках поставленной задачи. В работе рассматривается отображение n-мерного пространства входных признаков на двумерное пространство карты Кохонена с последующей ее раскраской. Таким образом, введенная структура деревьев решений ориентирована на модели нейронных сетей с частью характеристик, известных заранее, некоторые значения параметров могут формироваться автоматически, осуществляя запросы к базе -12- данных, другие вводятся в процессе взаимодействия с пользователем, причем это взаимодействие зависит от вида сети. Стоит отметить, что процесс принятия решения достаточно нагляден, так как отображается в виде естественной цепочки рассуждений. Однако, это справедливо лишь для небольших по объему деревьев решений. Чем больше дерево, чем сложнее его структура, тем сложнее отследить логику проводимых рассуждений. Поэтому возникает задача выделения поддеревьев (частных деревьев решений), которые отображают отдельные аспекты вывода решений. При этом возникает ряд проблем: - как разбить исходное дерево на поддеревья; - какое из поддеревьев наиболее информативно для пользователя с точки зрения обоснования принимаемого решения и т.д. Также бывает неудобно каждый раз проходить всю цепочку рассуждений по дереву решений. Это особенно актуально в случае, когда решение для аналогичных условий уже было получено, и новый вывод по дереву будет характеризоваться запросами к базе данных, количество которых зависит от глубины дерева, и вычислениями уже выполненными ранее, что замедляет процесс принятия решений и напрасно использует вычислительные ресурсы. Для избежания дублирования действий и упрощения решения целого ряда задач в работе используются семантические сети. Простая семантическая сеть, называемая иногда вычислительной семантической сетью, представляет собой фактически двудольный граф. Пусть задано конечное множество называемых атрибутами, и конечное множество отношений. Схемой или интенсионалом отношения называют набор пар: - имя отношения, - домен т.е. множество значений атрибута отношения Ri Объединение всех доменов называется базовым множеством модели или множеством объектов, на которых задаются отношения R. Экстенсионалом отношения называют множество где - факт отношения Факт задается совокупностью пар атрибут - значение, называемых атрибутивными парами. Под факгом понимается конкретизация определенного отношения между указанными объектами. В графической • интерпретации факт - это подграф семантической сети, имеющий звездообразную структуру. Корень подграфа - вершина предикатного типа, помеченная уникальной меткой, включающей имя соответствующего отношения. Из вершины факта выходят ребра, помеченные именами атрибутов данного факта, ведущие в вершины базового множества, которые являются значениями этих атрибутов. Таким образом, представляется целесообразным сочетать в единой системе представление в виде деревьев решений и класса семантических сетей, что дает возможность наглядного отображения процесса принятия решений и дополнительные возможности в конструировании механизмов вывода. Стоит отметить, что уже построенные деревья решений могут быть изменены или дополнены, тем самым, определяя необходимую гибкость в использовании уже имеющихся нейросетевых структур, а также, обеспечивая возможность добавления новых. Причем такой же порядок описания может быть использован и при формировании правил для других технологий Data Mining. -13- В третьей главе приведены результаты исследований и разработки методов принятия решений, а также структуры фрагмента БД для автоматизированного проектирования нейросетевых структур обработки данных. Определена структура подсистемы проектирования и принципы взаимодействия между ее основными блоками. Разработаны информационная и объектно-ориентированная модели нейронных сетей, а также структура фрагмента БД для хранения используемых шаблонов и уже построенных сетей. Разработаны алгоритмы формирования правил, прямого и обратного вывода для модифицированных деревьев решения, а также алгоритм представления деревьев решения в виде фактов семантической сети. Подсистема принятия решений для проектирования нейросетевых структур обработки данных состоит из следующих блоков. 1. Исходное хранилище данных. 2. Блок запросов. 3. Блок принятия решений и проектирования. 4. База данных подсистемы. 5. Блок исполнения. Схематично структура подсистемы представлена на рисунке 6. Блок запросов обеспечивает формирования запросов к хранилищу исходных данных, результаты выполнения которых после последующей предобработки и кодирования сохраняются в таблицах базы подсистемы. Блок принятия решений и проектирования отвечает за ввод и формирование пользователем деревьев решений, позволяет производить прямую и обратную цепочки рассуждений, имеет возможность преобразования уже сформированных деревьев решений в семантические сети в виде двудольного графа. В нем так же осуществляется процесс принятия решений, целью которого является определение структуры, значений параметров и автоматизированное проектирование необходимых нейросетевых структур. Исходными данными для функционирования блока принятия решений и проектирования являются выходные данные блока запросов (сохраненные в базе данных) и данные, полученные от пользователя. -14- База данных подсистемы разделена на две составляющие. Первая из них служит для хранения предобработанных данных (выходные данные блока запросов). Во второй хранится следующая информация: 1) Деревья решений и семантические сети. 2) Шаблоны используемых нейросетей. 3) Построенные нейронные сети. Блок исполнения обеспечивает проведение экспериментов с построенными нейросетевыми структурами. Такая архитектура позволила упростить весь процесс создания нейронных сетей, избавив пользователя от написания кода. Требуется только сформировать описание в ходе диалога. Она так же дает возможность осуществлять анализ сети и результатов ее работы средствами, предоставляемыми базой данных. Таким образом, создание, модификация и анализ нейронной сети осуществляется в режиме взаимодействия с базой данных, а испытания сети осуществляются в режиме эксперимента. Предложенная структура подсистемы потребовала разработки информационной модели нейронной сети для ее хранения в базе данных и объектно-ориентированной модели для ее программной реализации. С точки зрения объектно-ориентированного подхода нейросеть представляет собой иерархию классов: сеть, слой, нейрон и т.д. Фактически, именно, описание этой иерархии и хранится в базе данных. Класс NeuroNet представляет собой общее описание сети, включающее идентификатор, вид сети, назначение и область применения, а также другие наиболее общие характеристики. Класс NeuroStruct задает архитектуру сети: количество входов, слоев и выходов, определяет связи (в общем случае выделяется в отдельный класс) и т.д. Класс NeuroEducate предназначен для описания характеристик обучения и содержит такие атрибуты как: вид алгоритма обучения, объем обучающей и тестовой последовательности, источник данных. Класс NeuroStratum является описанием слоев нейронной сети и содержит информацию о количестве нейронов в слое и др. -15- Класс NeuroResult используется для описания получаемых результатов и определяет вид получаемых результатов, критерии их обработки и т.д. Класс Neuron задает основные характеристики нейрона. Класс Activation определяет вид функции активации. Класс InAct задает правила вычисления входа функции активации. Класс Weights задает весовые коэффициенты. В рамках данной модели, разработаны принципы формирования нейросетей, заключающиеся в поэтапном движении сверху вниз по иерархии классов. Таким образом, сначала создаются объекты классов определяющих наиболее общие характеристики сети. Затем определяются все более мелкие, характерные фрагменты строящейся модели, т.е. построение происходит от общего к частному. Разработана структура базы данных для хранения используемых нейросетей, которая, в свою очередь, может быть разбита на две составляющие. Первая предназначается для хранения шаблонов, из которых происходит проектирование моделей. Вторая предназначена для хранения уже спроектированных и построенных нейронных сетей. Она во многом схожа с составляющей для хранения шаблонов, но в ней содержатся и дополнительная информация, характеризующая конкретную сеть. Разработанная структура базы данных позволяет осуществлять хранение, добавление новых и изменение существующих, как шаблонов, так и уже спроектированных и построенных нейросетей, а также их весовых коэффициентов. Формирование деревьев решения осуществляется в два этапа. На первом этапе задаются используемые переменные решения и вывода, а также события, определяющие все возможные состояния этих переменных, а именно их значения, ограничения и т.д. Тем самым, задается область определения и значений дерева решений и набор возможных действий. На втором, происходит создание вершин и объединение их в необходимую структуру. Для хранения сформированных деревьев решений, а точнее их экстенсионалов, используются соответствующие таблицы разработанной БД. Использование модифицированных деревьев решений в качестве инструментария подсистемы принятия решений основано на разработанных алгоритмах прямого и обратного вывода, а также формирования правил. Прямой вывод по такому дереву направлен на определение нейросетевой архитектуры, ее параметров, алгоритма обучения в зависимости от поставленной задачи, имеющихся данных, представлений и предпочтений пользователя, априорной информации, что соответствует нахождению последствий по известным условиям. Также возможно осуществление обратного вывода. Обратная цепочка рассуждений используется для того, чтобы по известному результату найти причины его вызвавшие. При этом каждый шаг по дереву решений записывается в таблицу вывода. В соответствии с этими записями и значениями переменных вывода и решения можно проследить весь пройденный путь по дереву и проанализировать полученный результат. Чтобы избежать прохождения каждый раз всей цепочки вывода, целесообразно преобразование уже сформированных деревьев решений в семантические сети в виде двудольного графа, что обеспечивает представление дерева решений в виде таблицы фактов, где для каждого значения переменной вывода присутствует своя запись значений атрибутов факта. Поскольку существует отображение одного представления в другое, эти представления с формальной точки зрения тождественны. Это позволяет осуществлять быстрый поиск решения по известным атрибутам фактов, но в тоже время, существует возможность проследить всю цепочку рассуждений, -16- воспользовавшись таблицей деревьев решений. Для этого был разработан алгоритм преобразования деревьев решений в семантическую сеть. Хранение полученных семантических сетей, а точнее их экстенсионалов, осуществляется в соответствующих таблицах разработанной БД подсистемы. Четвертая глава посвящена вопросам реализации приложения, позволяющего осуществлять автоматизированное проектирование нейронных сетей с помощью модифицированных деревьев решения, с учетом имеющихся исходных данных и требовании, предъявляемых пользователем. Разработаны алгоритмы функционирования приложения и выполнена их программная реализация. Обоснован выбор использованного программного обеспечения и системы управления базами данных. Рассмотрен принцип поэтапного построения нейронных сетей с точки зрения объектно-ориентированного подхода с описанием основных компонентных данных и методов разработанной системы классов. Представлены интерфейсы пользователя для ввода и формирования деревьев решения, предобработки данных и проектирования нейросетей. Процесс формирования деревьев решения происходит в интерактивном режиме и состоит из несколько этапов. На первом, задаются используемые переменные решения и вывода. Далее определяются все возможные события, характеризующие поведение заданных переменных. После этого формируются вершины дерева решений и вводятся отношения между ними, путем указания вершины родителя и условий на дуге между родительской и текущей, что позволяет связать вершины в древовидную структуру. Построенные деревья решений сохраняются в таблицах БД приложения. Рассмотрены варианты представления отчетов о результатах вывода по дереву решения и полученных правилах. Создание отчета происходит в несколько этапов. Сначала отчет формируется в таблицах БД и уже затем, приводится к форме доступной пользователю. Один из способов представления отчетов приближен к табличной форме хранения результатов. В нем приводится название и идентификатор дерева решений, для которого осуществлялся вывод, номера решений (вариантов вывода) и правила, принадлежащие этим решениям. Второй способ является следствием обработки табличной формы хранения результатов и представления правил в виде продукций «если... то...». Разработанная структура базы данных была приведена к нормальной форме Бойса-Кодда (НФБК), которая наряду с исключением частичных или транзитивных зависимостей от первичного ключа, также учитывает функциональные зависимости, в которых участвуют все потенциальные ключи отношения, что позволило устранить избыточность данных и исключить аномалии обновления. Для реализации приложения был использован язык программирования Visual Basic, а в качестве СУБД блока базы данных подсистемы - MS Access 2000, что обусловлено их широким распространением и доступностью. Так Visual Basic представляет собой основной подход компании Microsoft к разработке приложений баз данных для конечного пользователя. Он играет основную роль в стратегии доступа к данным, как для больших, так и для малых организаций, причем в большинстве систем используются соединения с реляционными базами данных (РСУБД) Jet (Access) и Microsoft SQL Server. Использование указанных программных средств позволило осуществить отладку алгоритмов и оценить удобство работы пользователя. |
