Содержание к диссертации
Введение
1 Предмет и научная задача исследования 16
1.1 Особенности использования баз данных в корпоративных информационных системах 16
1.1.1 Базы данных как объект исследования 19
1.2 Объект и цель исследований 22
1.3 Анализ известного научно-методического аппарата тестирования БД и необходимость его совершенствования 25
1.3.1 Целостность и достоверность 26
1.3.2 Применение интеллектуальных информационных систем в задачах тестирования 31
1.4 Классификация ошибок реляционных баз данных 32
1.4.1 Ошибки этапа проектирования БД 32
1.4.2 Ошибки этапа эксплуатации БД 33
1.5 Постановка общей научной задачи и частные задачи исследования 38
Выводы по разделу 44
2 Модели и методы обработки содержания баз данных искусственными нейронными сетями для верификации БД 45
2.1 Математическая модель БД 45
2.2 Общая модель ИНС 49
2.3 Сеть Кохонена для решения задачи кластеризации 51
2.4 Алгоритм определения оптимального количества кластеров 55
2.5 Многослойная нейронная сеть прямого распространения 62
Выводы по разделу 66
3 Применение ИНС для определения достоверности строк таблицы БД 69
3.1 Виды контроля достоверности строк при верификации таблиц 69
3.2 Требования к обучающей базе 72
3.3 Использование сети Кохонена на этапе разведочного анализа 78
3.4 Применение многослойной сети прямого распространения для оценки достоверности данных 80
3.5 Средства доступа к данным при верификации БД 83
Выводы по разделу 85
4 Оценка эффективности применения ИНС для верификации БД 87
4.1 Критерий оценки качества верификации 87
4.2 Верификация БД перевозок 91
4.3 Верификация БД при неустранённой ошибке в обучающей выборке 100
Выводы по разделу 103
Заключение 104
Список использованных источников 106
Приложение А 118
Приложение Б 121
Приложение В 123
Приложение Г. Программная реализация сети Кохонена 125
Приложение Д. Программная реализация многослойной ИНС прямого распространения 130
Приложение Е. Исходные данные и результаты верификации БД перевозок 135
- Целостность и достоверность
- Алгоритм определения оптимального количества кластеров
- Требования к обучающей базе
- Верификация БД перевозок
Введение к работе
Актуальность исследования. Важным компонентом многих современных информационных систем являются реляционные базы данных (БД). Как правило, БД, находясь на нижнем уровне в общей структуре ИС, являются источником данных для всех средств обработки информации и принятия решений, входящих в конкретную систему. Информация, хранимая в БД, служит для составления отчётов о текущей ситуации, прогнозов, основанных на данных за длительные прошедшие периоды и принятия решений на основе полученных данных, а ошибки в ней приводят к негативным последствиям. Соответственно, среди требований к данным, хранимым в БД, на первый план выходят такие как полнота, актуальность и достоверность, а задача обеспечения достоверности в процессе верификации приобретает актуальность.
Архитектура части ИС, в первую очередь территориально распределённых, предполагает наличие БД различных уровней, различающихся по функциональному назначению. БД нижнего уровня служат для хранения оперативной информации о деятельности подразделения и являются источником данных для БД верхнего уровня, которые предназначены для накопления данных о деятельности всей организации за как можно большее время. Процедура импорта/экспорта данных между БД разных уровней автоматизируется средствами системы управления базой данных (СУБД) или самой ИС и имеет жестко заданные временные рамки.
В результате, актуальным становится не просто обеспечение достоверности данных в результате верификации, но и оперативность её проведения.
Вопросам верификации БД посвящены работы ряда отечественных и зарубежных специалистов: М.Л. Глухарева, А. Аграновского, Г. Майерса, В. Зайцева, Б. Телеснина, Р. Хади, Ю. Карпова, В. Липаева, В.М. Соловьева, А.А. Вербицкого, В.Н. Гридина, В.И. Солодовникова, В.В. Кульба, В.Н. Лихачёва, J.-M. Nicolas, P. Meseguer, A. Preece. Верификация БД, также проводится с использованием специализированного программного обеспечения, разрабаты - ваемого компаниями Computer Associates, Rational Software, Logic Wokrs, Quest Software, Oracle, IBM и др.
Наиболее широкое распространение имеют методы формальной верификации БД на основе тестирования ограничений целостности и триггеров. Однако, данный подход также не позволяет полностью исключить возникновение ошибки: во-первых при увеличении количества столбцов количество соответствующих триггеров значительно возрастает, замедляя работу БД; во- вторых триггеры также не защищают от ошибки, когда данные соответствуют всем формальным требованиям, но, по-прежнему, содержат ошибку. Верификация обычно проводится вручную путём сравнения значений в каждой строке БД с реальными значениями. В связи с этим, для повышения оперативности верификации БД, актуальной является разработка методов, позволяющих автоматизировать определение достоверности данных при эксплуатации БД и на этой основе сократить время обнаружения и устранения ошибок.
Целью диссертационного исследования является повышение оперативности верификации БД.
Объектом исследований являются методы и средства верификации баз данных на этапе их эксплуатации.
Научная задача исследования — разработка метода повышения оперативности верификации БД при заданных исходных данных о количестве строк и столбцов в таблицах БД и требуемом уровне достоверности.
Для решения общей научной задачи необходимо решить следующие частные задачи:
разработка метода определения достоверности строки таблицы БД на основе интеллектуального анализа данных с применением искусственной нейронной сети;
разработка метода формирования обучающей выборки, содержащей достоверный фрагмент верифицируемой БД, применяемой при обучении искусственных нейронных сетей;
разработка метода определения принадлежности строки к какому-либо классу достоверных данных, по ограниченному числу столбцов таблицы, значимых с точки зрения верификации;
определение количества классов, являющегося оптимальным для заданной обучающей выборки;
оценка степени достижения цели.
Методы исследования. Для решения поставленных в диссертации задач использованы методы системного анализа, теории информационных систем, математической статистики, формальной логики, теории отношений, а так же теории вероятностей и математической статистики.
С целью проведения экспериментов была спроектирована и реализована библиотека классов, описывающих ИНС различных типов, с использованием объектно-ориентированной парадигмы программирования.
Наиболее существенные положения, выдвигаемые для защиты:
-
-
Существующие методы не обеспечивают проверку достоверности при эксплуатации БД, поэтому верификация выполняется неавтоматизированными методами, приводящими к существенным временным затратам, в связи с чем, задача повышения оперативности верификации БД является актуальной.
-
Повышение оперативности достижимо за счёт проверки строк, упорядоченных в порядке возрастания достоверности, начиная с минимальной.
-
Определение достоверности строки БД возможно с применением искусственных нейронных сетей (ИНС) на основе оценки степени уверенности ИНС в принадлежности строки к одному из классов заведомо достоверных данных.
-
Определение оптимального числа классов осуществимо на основе кластеризации обучающей выборки с помощью сети Кохонена.
5. С использованием разработанных методов достижимо значительное, повышение оперативности верификации БД (на примере БД, содержащей таблицу из 483 строк и 3 столбцов — до 60%).
Наиболее существенные новые научные результаты, выдвигаемые для защиты:
-
-
-
Модель БД, описывающая использование хранимой информации в качестве входных данных ИНС, основанная на реляционной модели и отличающаяся учётом свойства достоверности строки таблицы БД.
-
Метод определения оптимального числа классов, использующий сеть Кохонена и отличающийся применением в качестве критерия оптимальности средней разности между максимальным значением выхода нейронной сети и остальными выходными значениями.
-
Метод определения степени принадлежности элемента к классу достоверных данных, отличающийся от известных применением многослойных ИНС прямого распространения, и использующий значения максимального выхода нейрона выходного слоя в качестве оценки достоверности, используемой для сортировки таблицы в порядке возрастания достоверности, начиная с минимальной.
Теоретическая значимость диссертации:
-
-
-
-
Полученный метод верификации БД является дальнейшим развитием методов интеллектуального анализа данных.
-
Разработанный алгоритм определения оптимального числа нейронов выходного слоя сети Кохонена при решении задачи кластеризации является развитием методов кластеризации и может быть использован при задании конфигурации ИНС других типов.
-
Предложенный метод определения степени принадлежности элемента к классу на основе значения максимального выхода нейрона выходного слоя многослойной ИНС может быть применён для решения задач классификации не связанных с оценкой достоверности БД.
-
Работа является приложением к учебному процессу, так как предложенные решения могут быть использованы при составлении теоретической части курса «Интеллектуальные информационные системы».
Практическая значимость диссертационного исследования заключается в следующем:
-
-
-
-
-
Метод определения достоверности строки таблицы на основе степени принадлежности элемента к классу достоверных данных, в отличие от принятых способов определения достоверности БД не требует участия человека и не зависит от предметной области.
-
Программная реализация методики верификации реляционных БД с применением искусственных нейронных сетей, в отличие от известных программных средств позволяет проводить автоматизированную оценку достоверности строк в таблицах БД и ускорить процесс поиска ошибок.
-
Алгоритм, реализующий разработанный метод определения оптимального числа классов, может быть использован в качестве программного компонента в средствах интеллектуального анализа данных для проведения кластеризации при неизвестном числе кластеров.
-
Применение предложенного метода оценки достоверности строки таблицы с использованием искусственных нейронных сетей на основе степени принадлежности элемента к классу достоверных данных позволило до 60% сократить время верификации БД, содержащей таблицу из 483 строк и 3 столбцов.
Реализация работы. Основные результаты диссертации реализованы в следующих документах:
-
в отчёте о выполнении ОКР «Разработка комплекса программных средств фильтрации мультимедийных данных, поступающих из сети интернет, на основе анализа аудио и видео составляющих» (г.к. № 07.524.11.4023), выполненном ФГАНУ НИИ «Спецвузавтоматика»;
-
в отчёте о НИР на тему «Метод сбалансированной дискретизации для задач имитационного моделирования динамических процессов в распределенных объектах и методика тестирования интеллектуальной информационной технологии экспертных систем» (№ гос. рег. 7.54614.1011), выполненном на кафедре «Вычислительные системы и информационная безопасность» ДГТУ;
-
в рабочей программе дисциплины «Интеллектуальные информационные системы» кафедры «Вычислительные системы и информационная безопасность» ДГТУ (Рег. № 243 от 5.11.2010 г.).
Апробация работы. Основные результаты работы докладывались и обсуждались на XXIII международной научно-практической конференции «Математические методы в технике и технологиях» (Саратов, 2010 г.), VTII-ой Международной научно-технической конференции «Современные инструментальные системы, информационные технологии, и инновации» (Курск, 2010 г.), международной научно-практической конференции «Состояние и перспективы развития сельскохозяйственного машиностроения: материалы» (Ростов-на-Дону, 2011 г.), международном семинаре «Системный анализ, управление и обработка информации» (Ростов-на-Дону, 2011 г.), международной научно-практической конференции «Автоматизация технологических объектов и процессов. Поиск молодых» (Донецк, 2012 г.), международном семинаре «Системный анализ, управление и обработка информации» (Ростов-на-Дону, 2012 г.).
Публикации по теме диссертации. Основные материалы диссертации опубликованы в 1 3 научных изданиях, в составе которых: 4 статьи в ведущих рецензируемых научных журналах, входящих в список ВАК РФ; 7 статей в материалах всероссийских и международных конференций. Во всех работах, опубликованных в соавторстве, доля материалов, принадлежащих автору диссертации, составляет не менее 50%. 2 свидетельства об официальной регистрации программы для ЭВМ выданы Федеральным государственным бюджетным учреждением «Федеральный институт промышленной собственности».
Целостность и достоверность
Основным инструментом обеспечения правильной работы базы данных, применяемом на этапе проектирования, являются ограничения целостности. Целостность базы данных — соответствие имеющейся в базе данных информации её внутренней логике, структуре и всем явно заданным ограничивающим правилам. Каждое правило, налагающее некоторое ограничение на возможное состояние базы данных, называется ограничением целостности.
Как можно более полное выявление всех имеющихся ограничений целостности и задание их в базе данных является задачей аналитика и проектировщика базы данных.
Однако целостность БД не гарантирует достоверности содержащейся в ней информации, а лишь обеспечивает правдоподобность этой информации, отвергая заведомо невероятные, невозможные значения.
В реляционной модели данных определены два базовых требования обеспечения целостности:
— целостность сущностей,
— целостность ссылок.
Целостность сущностей означает, что объект реального мира представляется в реляционной базе данных как кортеж некоторого отношения. Требование целостности заключается в том, что каждый кортеж любого отношения должен отличатся от любого другого кортежа этого отношения (т.е. любое отношение должно обладать первичным ключом).
Вполне очевидно, что если данное требование не соблюдается (т.е. кортежи в рамках одного отношения не уникальны), то в базе данных может хранится противоречивая информация об одном и том же объекте. Поддержание целостности сущностей обеспечивается средствами системы управления базой данных (СУБД). Это осуществляется с помощью двух ограничений:
— при добавлении записей в таблицу проверяется уникальность их первичных ключей;
— не позволяется изменение значений атрибутов, входящих в первичный ключ.
Сложные объекты реального мира представляются в реляционной базе данных в виде кортежей нескольких нормализованных отношений, связанных между собой. При этом связи между данными отношениями описываются в терминах функциональных зависимостей.
Для отражения функциональных зависимостей между кортежами разных отношений используется дублирование первичного ключа одного отношения (родительского) в другое (дочернее). Атрибуты, представляющие собой копии ключей родительских отношений, называются внешними ключами.
Требование целостности по ссылкам состоит в следующем — для каждого значения внешнего ключа, появляющегося в дочернем отношении, в родительском отношении должен найтись кортеж с таким же значением первичного ключа.
Еще одним важным видом обеспечения целостности является целостность доменов. Целостность домена гарантирует, что все значения некоторого столбца принадлежат множеству допустимых значений. Минимальным набором ограничений в данном случае является задание типа данным и его длины, например количество символов в строке или количество знаков после запятой у вещественного числа, для более точного задания указывается диапазон допустимых значений. Ограничения доменной целостности не могут гарантировать, что конкретный элемент данных введен правильно, а только позволяют определить, является ли оно допустимым. Важным является то, что ограничения целостности доменов накладываются на определённый столбец, значения которого берутся из данного домена, при этом совершенно не учитываются ограничения, накладываемые на данный столбец другими столбцами, например для возраста человека можно использовать следующие ограничения: целое число в диапазоне от 0 до 100, однако, например, возраст ребёнка не может быть больше возраста родителя — учесть это с помощью ограничений целостности домена невозможно.
Целостность данных можно также контролировать с помощью триггеров — хранимых процедур особого типа, которые пользователь не вызывает непосредственно, а исполнение которых обусловлено действием по модификации данных: добавлением, удалением строки в заданной таблице, или изменением данных в определенном столбце заданной таблицы реляционной базы данных. С помощью триггеров возможно организовать более сложные проверки, в том числе учитывающие ограничения налагаемые на значения столбца значениями других столбцов. Возвращаясь к примеру с возрастом ребёнка, с помощью триггера можно при добавлении в таблицу нового человека реализовать сравнение его возраста с возрастом родителя, как и любую другую проверку. Однако, данный подход также не позволяет полностью исключить возникновение ошибки: во-первых при увеличении количества столбцов количество соответствующих триггеров значительно возрастает, замедляя работу БД; во-вторых триггеры также не защищают от ошибки, когда данные соответствуют всем формальным требованиям, но, по-прежнему, содержат ошибку, например возраст сотрудника, которому 20 лет, равный в результате ошибки ввода 30 годам.
Рассмотрим для примера таблицу «Сотрудники», являющуюся представлением соответствующего отношения (рис. 1.2). Оно включает в себя такие атрибуты как ФИО (Фамилия Имя Отчество), адрес, дата рождения, стаж, оклад и должность. Атрибут «номер» является суррогатным первичным ключом, атрибут должность — внешним ключом, ссылающимся на соответствующий первичный ключ отношения «Должности». Подобная таблица в том или ином виде присутствует в БД любой организации.
Требование ссылочной целостности обеспечивается СУБД путём запрещения операций вставки в таблицу «Сотрудники» строк ссылающихся на отсутствующие значения первичного ключа в таблице «Должности». Таким образом, исключается ошибка, состоящая в добавлении в БД сотрудника, работающего на несуществующей должности. Аналогичным образом исключается ошибка, возникающая при удалении строки из таблицы «Должности» — пока существуют внешние ключи, ссылающиеся на первичный ключ удаляемой строки, она не может быть удалена.
Требование целостности сущностей обеспечивается благодаря наличию уникального ключа «номер».
Для отношения заданы следующие ограничения целостности домена:
— ФИО — строка, длиной не больше 64 символов,
— адрес — строка, длиной не больше 64 символов,
— дата рождения — дата, не раньше 1900 и не позже текущего момента,
— стаж — вещественное число, больше 0,
— зарплата — вещественное число с 6 знаками до запятой и 3 после запятой,
— должность — целое число (ограничения соответствуют ограничениям целостности домена для первичного ключа отношения «Должности»).
Пример заполнения такой таблицы данными приведён в табл. 1.1. Из таблицы видно, что все требования целостности соблюдены, однако в строке с номером 5 содержится ошибка — неправильно указана дата рождения. Её можно определить только зная реальный возраст данного человека, однако данная строка может вызвать подозрения и при анализе приведённой таблицы, так как в ней прослеживается зависимость между возрастом, стажем, зарплатой и должностью. Ввиду сложности этих связей задать их все в явном виде не представляется возможным.
Алгоритм определения оптимального количества кластеров
Основным преимуществом обучения без учителя является отсутствие необходимости задания желаемых значений выходов для каждого входного вектора из обучающей выборки.
Однако, обязательным требованием для использования нейронных сетей, в том числе сети Кохонена, является точное задание количества нейронов во входном и выходном слоях. Так как каждый нейрон выходного слоя отвечает за принадлежность образца к определенному кластеру, то число кластеров всегда равно числу выходных нейронов. Это свойство вступает в противоречие с тем, что сеть Кохонена обучается без учителя. Для того чтобы полностью исключить пользователя из процесса кластеризации, необходима возможность автоматического определения количества кластеров, оптимального для заданного множества входных векторов [30].
Принадлежность объекта к определённому классу определяется по максимальному значению выхода нейронов последнего слоя сети. Чем больше значение выхода, тем более сеть «уверена» в принадлежности объекта, поданного на вход к соответствующему классу [24].
Применительно к сети Кохонена, значение максимального выхода нейрона тем больше, чем ближе к ядру кластера находится точка, координаты которой составляют входной вектор [31]. На рис. 2.3 показан результат обучения нейронной сети данного вида на одном и том же обучающем множестве для разных значений количества нейронов выходного слоя. Для каждой точки указано значение максимального выхода нейронов выходного слоя. Обучающее множество состоит из довольно чётко выделяющихся групп двухкомпонентных векторов, представленных точками на плоскости. В результате обучения при соответствии количества выходов нейронной сети реальному количеству кластеров, ядра устанавливаются точно в центр кластера, а при недостатке выходов ядро установилось в центр между двумя кластерами. При этом увеличивается расстояние от него до точек, принадлежащих ближайшим кластерам, соответственно для каждой из указанных точек уменьшается значение, получаемое на выходе нейронной сети.
Используя данное свойство нейронных сетей, можно определять насколько конфигурация сети соответствует задаче, в которой она применяется. Оптимальным количеством нейронов при этом будет такое количество, при котором для каждого кластера среднее значение максимального выхода нейрона выходного слоя, отвечающего за принадлежность к данному кластеру, будет максимальным [32]. Критерием оптимальности будем считать величину среднего значения максимального выхода нейрона выходного слоя. Формула расчёта средних значений:
Возможен и второй вариант, где рассчитывается средняя разница между максимальным и минимальным выходами нейронов последнего слоя:
Скорость работы современных компьютеров и скорость работы нейронной сети Кохонена, по сравнению с другими типами нейронных сетей, позволяют проводить большое количество обучений сети за короткое время, следовательно, можно воспользоваться одним из численных методов определения максимального значения функции.
В таблице 2.2 представлены результаты экспериментов по определению критерия оптимальности по приведенным выше формулам для различных сочетаний числа кластеров и количества нейронов выходного слоя сети.
Так как по достижении оптимального числа кластеров, последующие нейроны, добавляемые к сети, не будут активироваться, то они не оказывают никакого влияния на результат вычисления среднего значения. Таким образом, график зависимости среднего максимального значения от числа нейронов в выходном слое имеет вид, представленный на рисунке 2.4.
Основываясь на изложенном выше, можно сформулировать общую последовательность действий для вычисления оптимального количества нейронов выходного слоя сети Кохонена.
1. Подготовка множества входных векторов.
2. Обучение нейронной сети Кохонена с использованием входного множества.
3. Кластеризация входного множества обученной сетью.
4. Подсчёт критерия оптимальности по формуле (2.3).
5. Определение численным методом количества нейронов выходного слоя, при котором значение критерия будет максимальным.
Для проверки описанной методики была разработана программная реализация нейронной сети Кохонена, позволяющая задавать количество входных и выходных нейронов (Приложение Г).
В соответствии с методикой на начальном этапе было сформировано множество входных векторов, каждый из которых включает 3 значения. Графическое представление данного множества показано на рис. 2.5.
В качестве начального количества нейронов выходного слоя было выбрано значение 3 и по формуле (2.3) для него рассчитано значение средней разницы между максимальным выходом нейрона и средним значением выходов остальных нейронов. В результате получено значение 0,674.
Далее число нейронов было увеличено и стало равняться 4. Для данного количества так же было вычислено значение критерия оптимальности, которое составило 0,968.
На следующем шаге значение количества нейронов выходного слоя было увеличено до 5, и для данного значения так же была рассчитана величина критерия оптимальности, которая равнялась 0,76.
Следовательно, максимальное значение средней разницы между максимальным выходом нейрона и средним значением выходов остальных нейронов достигается при количестве нейронов выходного слоя равном 4. Именно такое количество является оптимальным для данного входного множества, что видно из рис. 2.5.
Можно говорить, что данный метод позволяет определять количество кластеров, оптимальных для заданного множества и для исходных значений, заданных векторами большей размерности.
Полученная методика является дальнейшим развитием методов обучения без учителя. Она позволяет избежать необходимости задания количества выходов нейронной сети Кохонена и может найти широкое применение как в решении задач интеллектуального анализа данных, так и при распознавании новых неизвестных классов и ситуаций в различных областях деятельности.
Сети Кохонена относятся к классу однослойных сетей, что определяет некоторые их свойства и ограничения, такие как, например, невозможность разделения нелинейно разделимых кластеров и вытекающая отсюда невозможность решения задачи исключающего ИЛИ. Добавление еще одного или нескольких слоев нейронов в сеть позволяет устранить указанные недостатки, а так же увеличивает возможности сети по выявлению статистических зависимостей более высокого порядка.
Требования к обучающей базе
Ключевой особенностью нейронных сетей является способность к обучению и обобщению. Поэтому особо важным этапом методики верификации БД является этап формирования обучающей выборки (или эталонной БД). Эталонная БД формируется администратором или специалистом заранее, однако данная операция должна проводиться либо один раз, либо достаточно редко.
Ошибки, допущенные на данном этапе, оказывают влияние на результаты, получаемые на всех остальных дальнейших этапах. При этом на первый план выходит необходимость обеспечения репрезентативности обучающей выборки.
Репрезентативность (в статистике) — соответствие характеристик выборки характеристикам популяции или генеральной совокупности в целом [37]. Репрезентативность определяет, насколько возможно обобщать результаты исследования с привлечением определённой выборки на всю генеральную совокупность, из которой она была собрана. Также, репрезентативность можно определить как свойство выборочной совокупности представлять параметры генеральной совокупности, значимые с точки зрения задач исследования.
В контексте аналитических технологий под репрезентативностью исходных данных следует понимать наличие достаточного количества разнообразных обучающих примеров, отражающих правила и закономерности, которые должны быть обнаружены моделью в процессе обучения. Она имеет три аспекта:
— достаточность — число обучающих примеров должно быть достаточным для обучения. Это число может быть различным для разных типов моделей. Например, для нейронной сети необходимо, чтобы число обучающих примеров было в несколько раз больше, чем число весов межнейронных связей, в противном случае модель может не приобрести способности к обобщению [38]. Кроме этого, размер выборки должен быть достаточным для формирования обучающего и тестового множеств;
— разнообразие — большое число разнообразных комбинаций вход-выход в обучающих примерах. Если число примеров достаточное, но все они одинаковые, то обобщающая способность не будет достигнута;
— равномерность представления классов — примеры различных классов должны быть представлены в обучающей выборке примерно в одинаковых пропорциях. Если один из классов будет доминировать, то это может привести к «перекосу» в процессе обучения модели [38]. Преобладающий класс будет определен моделью как наиболее вероятный для любых новых наблюдений.
Если репрезентативность исходной выборки недостаточна, то частично это можно компенсировать применением перекрестной проверки, обогащением данных [38].
Рассмотрим каждое из требований более подробно.
В соответствии с п. 2.1 число нейронов входного слоя ИНС, применяемых при решении задачи равно числу элементов п отношения гр т.е. числу столбцов в таблице, выбранных для проведения верификации. Оно хранится в метаданных БД и может быть извлечено из служебных таблиц. В пункте 2.5 указывается, что для многослойной сети число нейронов в скрытом слое должно превышать число нейронов во входном слое в 1,5 — 2 раза, таким образом, общее число нейронов во входном и скрытом слое составляет от 2,5и до Зи. Так как сеть полносвязная, т.е. каждый нейрон предыдущего слоя соединён со всеми нейронами следующего слоя, то число связей между 1-ым и 2-м слоями равно п 2п = 2п .
Общее же число связей для двухслойной сети:
Км=2хп +2хлхт = 2хих(й + га) (3-1) где п — число входных нейронов, т — число выходных нейронов. Для сети Кохонена: Кк — п х т
Однако число нейронов в выходном слое т является неизвестным, так как зависит от количества классов объектов, информация о которых хранится в данной таблице. Таким образом, число связей между нейронами скрытого и выходного слоя равное 2п т невозможно определить до окончания этапа кластеризации.
При п 1 и т 1
пхт 2хп +2хпхт
Это означает, что для обучения сети Кохонена требуется выборка значительно меньшая, чем для обучения многослойной сети, следовательно, на первом этапе анализа данных можно использовать обучающую выборку, содержащую количество элементов, значительно превышающее минимально необходимое.
Воспользуемся эмпирическим предположением, основанным на предыдущих практических результатах, и примем число классов т равным 10, тогда:
Км = 2 х п2 + 20 х п
Выберем Км строк из таблицы в качестве обучающей выборки для обучения сети Кохонена, т.е. Кк = Км, тогда тхп-2хп2+20хп т = 2хп + 20
То есть, сеть Кохонена обученная на Км примерах должна иметь возможность выделить до 2п+20 кластеров, что является достаточным для большинства задач и предметных областей, однако, в программном средстве, реализующем разработанную методику, имеется возможность задания пользователем размера обучающей выборки [39].
В случае если полученное число кластеров находится в следующем диапазоне: 10 т 2п + 20, то есть размер выборки достаточен для сети Кохонена и недостаточен для обучения многослойной сети, следует увеличить объём выборки в соответствии с формулой (3.1) на основе полученного числа кластеров.
Следующие два требования — разнообразие и равномерность возможно обеспечить только случайным выбором строк из таблицы для обучающей выборки.
Однако метод случайного выбора не может гарантировать стопроцентное выполнение указанных условий. Присутствующий элемент случайности, особенно при достаточно большом количестве классов может вносить значительные погрешности, в том числе, приводящие к нерепрезентативности обучающей выборки. В некоторой степени устранить данный недостаток можно путём формирования 2-х обучающих выборок и их последующей кластеризации. В случае если в результате кластеризации двух выборок получено одинаковое число кластеров, можно говорить об их достаточной репрезентативности.
Для получения такой выборки необходимо последовательно выполнить 2 запроса:
SELECT INTOR1 FROM R OFFSET К LIMIT N;
SELECT FROMR OFFSET К LIMIT N WHERE NOTINR1.
При выполнении запросов также необходимо учитывать, что в результирующих таблицах (см. п. 2.1, таблица 1) должны быть предусмотрены дополнительные поля для значений достоверности каждой строки и её принадлежности к кластеру (классу). Тогда запросы будут выглядеть следующим образом: SELECT , d, CI INTO Rl FROM R OFFSET К LIMIT N;
SELECT d, CI FROM R OFFSET К LIMIT N WHERE N0TINR1.
Рассмотрим результаты, полученные при использовании разработанного метода для поиска ошибок в тестовой БД, которая содержит 485 строк с информацией о деятельности некоторой транспортной компании, в 5 из которых намеренно внесены ошибки. Известно, что в таблице представлена информация о п = 3 кластерах различных объектов, тогда, в соответствии с формулой (1) т = 26 строк. Так как объем обучающей выборки должен превышать полученное значение в несколько (т.е. минимум в 2) раз и, так как в соответствии с разработанным методом, используются 2 выборки, то общее число строк равно 26 х 2 х 2 = 104.
Номера строк с ошибками заранее известны, необходимо переместить данные строки как можно ближе к началу таблицы, что позволит проверить их в первую очередь.
На графике (рис. 3.3) видно, что наилучший результат достигается при объёме обучающей выборки, составляющем 20% от всей таблицы, то есть 485 х 0.2 = 97 строк, что соответствует рассчитанному ранее объёму выборки.
Верификация БД перевозок
Рассмотрим БД, хранящую информацию транспортного предприятия. Данная БД, помимо прочих, включает в себя таблицу, содержащую сведения о перевозках. На рис. 4.2 представлена схема такой таблицы. На нём «id» — суррогатный ключ, уникально идентифицирующий каждую запись о перевозке, «Дата» — дата выполнения перевозки, «Расстояние» — длина маршрута перевозки в километрах, «Вес» — вес перевозимого груза в тоннах, «Время» — время в пути в минутах. Пример данных, содержащихся в таблице приведён в табл. 4.1.
Согласно разработанной методики верификации первым этапом является формирование обучающей выборки. Запросы, приведённые в п. 3.1 в общем виде, и предназначенные для формирования обучающей выборки, примут вид:
SELECT id, Расстояние, Вес, Время, d, CI INTO ТІ FROM Transit_part OFFSET К LIMIT 1
SELECT id, Расстояние, Вес, Время, d, CI INTO T2 FROM Transit_part OFFSET К LIMIT 1 WHERE id NOT IN (SELECT id FROM Tl)
В таблицы ТІ и Т2 добавлены поля d — для хранения полученных значений достоверности строки и С1 — для хранения принадлежности строки к кластеру.
Размер (количество строк) каждой таблицы зависит от числа, характеризующего кратность выполнения запросов и определяет размер обучающей выборки. Определение достоверности осуществляется на основе 3 значений, с чем связано число входов ИНС равное 3. Тогда по формуле (3.2) определим минимально необходимое для обучающей выборки количество строк:
Аналогичную операцию проделаем со столбцами «Вес» и «Время» таблицы ТІ, а также со столбцами «Расстояние», «Вес» и «Время» таблицы Т2. Далее, данные следует нормализовать в соответствии с формулой (2.1). Результирующие таблицы приведены в приложении Е.
После проведения всех предварительных шагов по формированию обучающей выборки необходимо провести её кластеризацию с применением сети Кохонена, предварительно определив количество кластеров. Из рис. 4.3 и 4.5 видно, что в таблице содержатся данные об объектах, принадлежащих к 3-м кластерам. В результате работы алгоритма определения оптимального числа кластеров, были получены следующие результаты (табл. 4.2), которые соответствуют наглядным данным (рис. 4.3).
Из данных, приведённых в табл. 4.2 видно, что максимальное значение критерия оптимальности достигается при количестве выходных нейронов сети Кохонена равном 3, что означает, что наилучшим вариантом является разделение исходного множества на и=3 кластера. Следовательно, для проведения кластеризации необходимо создать нейронную сеть Кохонена, содержащую 3 нейрона во входном слое и 3 нейрона в выходном.
В результате кластеризации в таблицах ТІ и Т2 (рис. 4.3) будет заполнен столбец С1, хранящий принадлежность строки к кластеру. Результаты кластеризации обучающей выборки приведены в приложении Е.
Следующим этапом верификации является задание топологии и обучение многослойной сети. Данная сеть будет иметь 3 нейрона во входном слое, 6 нейронов в скрытом и 3 нейрона в выходном. Создание программного объекта, реализующего многослойную ИНС, производится автоматически.
Рассчитаем число связей в такой сети:
Км =2хих(« + от)=2хЗх(з + 3)=36
Следовательно, объём обучающей выборки должен быть не меньше 36 элементов. Так как каждая из таблиц ТІ и Т2 содержат по 29 строк, то не требуется дополнять обучающую выборку новыми элементами.
После того как получена вся необходимая информация для обучения многослойной сети, можно проводить её обучение. График зависимости коэффициента ошибки от эпохи обучения приведён на рис. 4.5. В качестве критериев остановки выбраны следующие условия: достижения коэффициента ошибки, равного 0.001 или проведение 5000 эпох обучения. Из рис. 4.5 видно, что обучение закончилось по достижении заданного коэффициента ошибки и для этого потребовалось 1354 эпохи обучения. Время, затраченное на обучение, составляет 3 мин. 52 сек.
Данный этап является самым сложным с точки зрения вычислений. Во избежание повторения таких временных затрат, обученную сеть необходимо сохранить. В программном средстве, имеется возможность сохранения весов связей ИНС в xml-файл.
Последним этапом верификации является классификация множества строк таблицы Transit, не вошедших в обучающую выборку с помощью обученной многослойной сети.
В результате классификации каждой строке будет присвоено значение, определяющее степень её принадлежности к определённому классу. При этом не важно, к какому именно классу принадлежит строка, важным является только уверенность ИНС в её принадлежности, определяемая максимальным значением выхода сети.
Объединим полученную таблицу (назовём её «Transit_ver»), содержащую оценки достоверности с исходной таблицей («Transit») с помощью следующего запроса:
SELECT Transit. , Transit ver.d FROM Transit INNER JOIN Transit_ver ON Transit, id = Transit ver. id
Далее, проведем сортировку полученной таблицы по полю d с помощью следующего запроса:
SELECT Transit. , Transit_ver.d FROM Transit INNER JOIN Trans it_ver ON Transit.id = Transit ver.id ORDER BYdASC
В табл. 4.3 приведены первые несколько строк таблицы, полученные в результате сортировки.
Проверка первой и второй строки в данной таблице показала, наличие ошибки в расстоянии, проверка строк с 3 по 18 не выявила ошибок, проверка 19-ой строки — ошибку в столбце время. Ошибки в различных столбцах были найдены также в строках с номерами 94, 105 и 202. Проверка остальных строк не выявила других ошибок. Таким образом, таблица содержала 5 строк с ошибками, приводившими к их недостоверности. При этом в результате сортировки последняя недостоверная строка оказалась на 202 месте (из 483), тогда, оценка качества верификации с использованием критерия, основанного на позициях недостоверных строк в отсортированной таблице:
Расчёт второго показателя, характеризующего точность метода определения достоверности (формула 4.2), с использованием разработанного приложения, дал следующий результат c = 0.87f чт0 МОЖно трактовать как среднее значение достоверности, вычисленное для достоверной строки с использованием разработанного метода верификации. Близость полученного значения к 1 говорит о точности метода.
График распределения ошибочных строк в таблице для нескольких экспериментов приведён на рис. 4.6. Из него видно, что даже в худшем случае все ошибочные строки будут находиться в первой половине таблицы. Это означает, что проверка половины отсортированных строк приведёт к достоверности данных.
Похожие диссертации на Метод и средства верификации баз данных на основе нейросетевых технологий
-
-
-
-
-
-
-
-
-
-
