Метод и средства верификации баз данных на основе нейросетевых технологий

Актуальность темы

Важным компонентом многих современных информационных систем являются реляционные базы данных (БД). Качество БД оказывает большое влияние на качество информационной системы в целом.

Как правило, БД, находясь на нижнем уровне в общей структуре корпоративной информационной системы (КИС), являются источником данных для всех средств обработки информации и принятия решений, входящих в конкретную систему. Соответственно среди требований к данным, хранимым в БД, на первый план выходят такие как полнота, актуальность и достоверность.

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

Архитектура части ИС, в первую очередь территориально распределённых, предполагает наличие БД различных уровней, различающихся по функциональному назначению. БД нижнего уровня служат для хранения оперативной информации о деятельности подразделения и являются источником данных для БД верхнего уровня, которые предназначены для накопления данных о деятельности всей организации за как можно большее время. Процедура импорта/экспорта данных между БД разных уровней автоматизируется средствами системы управления базами данных (СУБД) или самой ИС и имеет жестко заданные временные рамки.

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

Вопросам верификации БД посвящены работы ряда отечественных и зарубежных специалистов: M.JI. Глухарева, А. Аграновского, Г. Майерс, В. Зайцева, Б. Телеснина, Р. Хади, Ю. Карпова, В. В. Смирнова, В. Липаева, В. М. Соловьева, A.A. Вербицкого, В. Н. Гридина, В. И. Солодовникова, В. В. Кульба, В. Н. Лихачёва, J.-M. Nicolas, P. Meseguer, А. Ргеесе.

Верификация БД, также проводится с использованием специализированного программного обеспечения, разрабатываемого компаниями Computer Associates, Rational Software, Logic Wokrs, Quest Software, Oracle, IBM и др.

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

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

Предметом диссертационного исследования являются методы верификации БД.

Цель исследования — повышение оперативности верификации БД.

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

Научная задача: разработка метода повышения оперативности верификации БД при заданных исходных данных о количестве строк и столбцов в таблицах БД и требуемом уровне достоверности.

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

Наиболее существенные научные положения, выдвигаемые для защиты:

1. Существующие методы не обеспечивают проверку достоверности при эксплуатации БД, поэтому верификация выполняется неавтоматизированными методами, приводящими к существенным временным затратам, в связи с чем, задача повышения оперативности верификации БД является актуальной.

2. Повышение оперативности достижимо за счёт проверки строк, упорядоченных в порядке возрастания достоверности, начиная с минимальной.

3. Определение достоверности строки БД возможно с применением искусственных нейронных сетей (ИНС) на основе оценки степени уверенности ИНС в принадлежности строки к одному из классов заведомо достоверных данных.

4. Определение оптимального числа классов осуществимо на основе кластеризации обучающей выборки с помощью сети Кохонена.

5. С использованием разработанных методов достижимо значительное, повышение оперативности верификации БД (на примере БД, содержащей таблицу из 483 строк и 3 столбцов — до 60%).

Наиболее существенные научные результаты:

1. Модель БД, описывающая использование хранимой информации в качестве входных данных ИНС, основанная на реляционной модели и отличающаяся учётом свойства достоверности строки таблицы БД.

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

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

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

В первой главе рассмотрены БД как часть корпоративных информационных систем (КИС). БД, находясь на нижнем уровне в общей структуре КИС являются источником данных для всех средств обработки информации и принятия решений, входящих в конкретную систему. Соответственно среди требований к данным, хранимым в БД, на первый план выходят такие как полнота, актуальность и достоверность. Основным способом обеспечения достоверности является верификация.

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

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

Рассмотрены основные принципы применения ИНС в задачах тестирования. В результате установлено, что методы применения ИНС в задачах, связанных с тестированием, диагностикой и т. д. в основном сводятся к задачам классификации состояний системы, в частности, классификации по работоспособности — на работоспособное и неработоспособное, или классификацию состояний системы по наличию в ней ошибок.

Проведена классификация ошибок реляционных баз данных. При этом ошибки разделены на 2 группы: ошибки этапа проектирования и этапа эксплуатации.

Выявление ошибок в ходе эксплуатации БД позволяет снизить вероятность получения в результате выполнения запроса искажённых данных и способствует повышению надёжности работы базы данных.

Проведён анализ методов проверки БД, в результате установлено, что наибольшее внимание уделяется поиску ошибок на этапе проектирования БД, однако существует большое количество видов ошибок, возникновение которых возможно на этапе эксплуатации. Частично, предотвращение таких ошибок обеспечивается ограничениями целостности и триггерами. Однако данные средства не гарантируют достоверности информации, содержащейся в БД, а лишь обеспечивают её правдоподобность, отвергая заведомо невероятные, невозможные значения. Это приводит к необходимости ручной проверки оператором каждого значения, хранимого в БД, что связано со значительными временными затратами.

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

На основании проведённого анализа определены основные этапы и представлена концептуальная схема решения поставленной научной задачи.

Во второй главе описываются модели и методы анализа содержания баз данных искусственными нейронными сетями при решении задачи верификации. БД представляется совокупностью отношений Я. Каждый элемент отношения ., г-}, ., гт} (т > 0) является кортежем, включающим в себя элементы множеств £>ь /)2, • • А?- ,)-ый элемент отношения Я равен ., а^еВь аИ2, ., е ?)". Отношение может быть представлено в виде таблицы, в которой столбцы (поля, атрибуты) соответствуют вхождениям доменов в отношение, а строки (записи) — наборам из п значений, взятых из исходных доменов. Каждому элементу ^ ставится в соответствие параметр — достоверность данного элемента такое, что 0 < 4п)< 1.

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

Главным достоинством сетей Кохонена является обучение без учителя, также называемое самоорганизацией, основным преимуществом которого является отсутствие необходимости задания желаемых значений выходов для каждого входного вектора из обучающей выборки. Однако, обязательным требованием для использования нейронных сетей, в том числе сети Кохонена, является точное задание количества нейронов во входном и выходном слоях. Так как каждый нейрон выходного слоя отвечает за принадлежность образца к определенному кластеру, то число кластеров всегда равно числу выходных нейронов. Это свойство вступает в противоречие с тем, что сеть Кохонена обучается без учителя. Принадлежность объекта к определённому классу определяется по максимальному значению выхода нейронов последнего слоя сети. Чем больше значение выхода, тем более сеть «уверена» в принадлежности объекта, поданного на вход к соответствующему классу. Оптимальным количеством нейронов при этом будет такое количество, при котором для каждого кластера среднее значение максимального выхода нейрона выходного слоя, отвечающего за принадлежность к данному кластеру, будет максимальным. Критерием оптимальности можно считать величину среднего значения максимального выхода нейрона выходного слоя, расчёт которой предлагается проводить по формуле:

2 I>4*2 *" Х0"'*,) + £(/яох&bdquo- - —) +. + Ё (тахт -^—) о п-1 ,=о п -1 т2 т к] ~ь к’у. ~ь п где к — количество образцов, принадлежащих к 1-му кластерук&bdquo- — количество образцов, принадлежащих к и-му кластерупс — число нейронов выходного слоя (число кластеров) — тах-ц — максимальное значение выхода нейронов последнего слоя для го образца, принадлежащего к 1-му кластеруоШщ — значение выхода га-го нейрона (т Ф.

В третьей главе описываются этапы применения ИНС для верификации.

БД:

1. формирование обучающей выборки;

2. «разведочный» анализ данных;

3. «глубокий» анализ данных;

4. оценка достоверности строк таблицы;

5. принятие решения об исправлении или исключении недостоверных данных из таблицы.

Выделены 2 подхода к верификации БД: входной контроль — проверка вводимых данных на соответствие хранимым в БД, исходя из предположения, что в БД хранятся достоверные данныетекущий контроль — проверка данных, хранящихся в БД и поиск недостоверных среди них.

Сформулированы требования к обучающей БД. Основными среди них являются: достаточностьразнообразиеравномерность представления классов.

Описаны способы обеспечения перечисленных требований. Так для обеспечения достаточности предлагается выбор для обучения сети количества строк не меньшего чем количество связей многослойной ИНС. Разнообразие и равномерность возможно обеспечить случайным выбором строк из таблицы для обучающей выборки.

Результаты данного этапа используются для принятия решения о дальнейших действиях. Здесь возможны 2 варианта дальнейших действий, приводящих к повышению достоверности отдельных таблиц БД, и как следствие, БД в целом. Это: исключение из таблиц строк с достоверностью ниже определённого проверка строк в порядке увеличения оценки их достоверности, начиная с самой низкой.

В четвёртой главе проводится оценка разработанной методики верификации. Для этого определены следующие критерии:

Расположение недостоверных строк в отсортированной по критерию достоверности таблице:

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

2Х 0 т где для достоверных строк 1 — di, для недостоверных строк т — количество строк в таблице.

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

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

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

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

Реализация работы. Основные результаты диссертации реализованы в следующих документах: в отчёте о выполнении ОКР «Разработка комплекса программных средств фильтрации мультимедийных данных, поступающих из сети интернет, на основе анализа аудио и видео составляющих» (г.к. № 07.524.11.4023), выполненном ФГАНУ НИИ «Спецвузавтоматика" — в отчёте о НИР на тему «Метод сбалансированной дискретизации для задач имитационного моделирования динамических процессов в распределенных объектах и методика тестирования интеллектуальной информационной технологии экспертных систем» (№ гос. per. 7.54 614.1011), выполненном на кафедре «Вычислительные системы и информационная безопасность» ДГТУв рабочей программе дисциплины «Интеллектуальные информационные системы» кафедры «Вычислительные системы и информационная безопасность» ДГТУ (per. № 243 от 5.11.2010 г.).

Апробация работы. Основные результаты работы докладывались и обсуждались на XXIII международной научно-практической конференции «Математические методы в технике и технологиях» (Саратов, 2010 г.), VIII-ой Международной научно-технической конференции «Современные инструментальные системы, информационные технологии, и инновации» (Курск, 2010 г.), международной научно-практической конференции «Состояние и перспективы развития сельскохозяйственного машиностроения: материалы» (Ростов-на-Дону, 2011 г.), международном семинаре «Системный анализ, управление и обработка информации» (Ростов-на-Дону, 2011 г.), международной научно-практической конференции «Автоматизация технологических объектов и процессов. Поиск молодых» (Донецк, 2012 г.), международном семинаре «Системный анализ, управление и обработка информации» (Ростов-на-Дону, 2012 г.).

Публикации. Основные материалы диссертации опубликованы в 13 научных изданиях, в составе которых: 4 статьи в ведущих рецензируемых научных журналах, входящих в список ВАК РФ- 7 статей в материалах всероссийских и международных конференций. Во всех работах, опубликованных в соавторстве, доля материалов, принадлежащих автору диссертации, составляет не менее 50%. 2 свидетельства об официальной регистрации программы для ЭВМ выданы Федеральным государственным бюджетным учреждением «Федеральный институт промышленной собственности».

Выводы по разделу.

1. Определены этапы верификации БД с применением ИНС, основанные на методах интеллектуального анализа данных.

2. Выделены два варианта проведения верификации — входной и текущий контроль. Входной контроль применяется для проверки добавляемых в БД строк. Исходными данными для обучения ИНС при этом являются уже содержащиеся в БД данные.

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

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

Обоснован выбор размера обучающей выборки, т. е. достаточность. Рассмотрены методы обеспечения разнообразия и равномерности.

4. Представлена разработанная методика использования многослойных нейронных сетей для определения достоверности данных. Она предполагает использование сети Кохонена для кластеризации на этапе разведочного анализа и определения принадлежности каждой строки таблицы обучающей выборки к кластеру или классу. На этапе глубокого анализа данных предлагается использование многослойной сети прямого распространения для классификации строк таблицы. Обосновывается возможность использование значения максимального выхода ИНС в качестве значения достоверности.

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

4 ОЦЕНКА ЭФФЕКТИВНОСТИ ПРИМЕНЕНИЯ ИНС ДЛЯ.

ВЕРИФИКАЦИИ БД 4.1 Критерий оценки качества верификации.

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

Зачастую процедура верификации проводится пользователем вручную, при этом он последовательно проверяет каждую строку из таблицы БД с целью установить достоверность содержащихся в ней данных. При таком способе проверка достоверной строки не оказывает влияния на общую достоверность как таблицы, так и БД в целом. Таким образом, большая часть времени затрачивается впустую. Однако, зная оценку достоверности для каждой строки в таблицах верифицируемой БД, можно начинать проверку со строк с наименьшей вычисленной достоверностью, т. е. проверять в начале именно те строки, в которых наиболее вероятно наличие ошибки. Такой подход позволяет при минимальных временных затратах добиться значительного повышения достоверности БД (рис. 4.1). Необходимым условием для этого является сортировка таблицы по полю, содержащему оценки достоверности («d»), выполняемое простым запросом:

SELECT * FROMR ORDER BY dASC.

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

Тогда, чем ближе значение V к 1, тем меньшее количество строк необходимо проверить для обеспечения достоверности БД.

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

С другой стороны, если 9 недостоверных строк, окажутся в начале таблицы, и 1 на 100-ом месте, то.

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

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

V = — = 1. 10 у =-= 0.

100 т.

С = 0 т.

4.2) где для достоверных строк 1 — й?(для недостоверных строк.

Рисунок 4.1 — График зависимости достоверности таблицы от числа проверок.

На практике при верификации БД возможны 2 случая:

Имеется определённое значение достоверности, которое необходимо достичь за как можно более короткое время.

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

Так как основной задачей ОЬАР-систем является получение статистических данных путём обработки большого количества исходных данных из различных источников, то незначительные отклонения значения, хранимого в БД, от реального не вносят существенных искажений в получаемую статистику. Таким образом, в некоторых случаях достаточно достижения определённого значения достоверности. Из графика видно, что для достижения заданного значения достоверности с1* при проверке упорядоченных строк требуется время, а при проверке неупорядоченных — время ?2 > ЬИ хотя метод, предлагаемый в данной работе, является нечувствительным к такого рода ошибкам, что обусловлено свойствами нейронных сетей, точности получаемого результата достаточно для выявления ошибок, способных оказывать значительное влияние на результаты вычисления статистических показателей.

В данном случае значение с1* является критерием остановки процесса верификации. Его задание возможно как вручную, исходя из требований конкретной системы и предметной области, так и автоматически, на основе данных, полученных при обучении многослойной ИНС, в частности, отличия выходных сигналов ИНС от эталонных на обучающем множестве (2.6).

Для всей обучающей выборки: где т — объём обучающей выборки, п — количество классов.

Получение на выходе значения, большего и равного гср говорит об очень высокой степени уверенности ИНС в принадлежности поданного на вход элемента к определённому классу, обусловленной его минимальными отличиями от элементов обучающей выборки, которые являются достоверными. Следовательно, исключение таких элементов из процесса верификации не окажет существенного влияния на полученную достоверность БД. Тогда с1* = -гср, то есть критерием остановки служит достижение достоверности таблицы в той степени, в которой ИНС обучилась классифицировать объекты обучающей выборки.

2-ой вариант встречается на практике гораздо чаще и связан с необходимостью периодического экспорта данных в хранилище или БД более п т.

ЕОШ, — С.

I ' ' 7=0 -=о т высокого уровня. Концепция хранилища данных не предполагает возможности удаления или изменения находящихся в нём данных, что определяет необходимость их проверки до поступления в хранилище. В связи с этим возникает необходимость верификации как можно большей части БД до определённого времени. Из графика видно, что при последовательной проверке неупорядоченных строк за время ТА будет достигнута достоверность с1, а при проверке упорядоченных строк с12 > с!, что означает достижение большей достоверности БД за одинаковое время.

4.2 Верификация БД перевозок.

Рассмотрим БД, хранящую информацию транспортного предприятия. Данная БД, помимо прочих, включает в себя таблицу, содержащую сведения о перевозках. На рис. 4.2 представлена схема такой таблицы. На нём «1с1» — суррогатный ключ, уникально идентифицирующий каждую запись о перевозке, «Дата» — дата выполнения перевозки, «Расстояние» — длина маршрута перевозки в километрах, «Вес» — вес перевозимого груза в тоннах, «Время» — время в пути в минутах. Пример данных, содержащихся в таблице приведён в табл. 4.1.

Перевозки ?(3: целое Дата: дата.

Расстояние: вещественное Вес: вещественное Время: вещественное.

Рисунок 4.2 — Структура таблицы «Перевозки».