Національний аерокосмічний університет ім. М.Є. Жуковського
“Харківський авіаційний інститут”

ЧУХРАЙ Андрій Григорович

УДК 681.3.01:658.012.011.56

МЕТОДИ ТА ЗАСОБИ ПІДВИЩЕННЯ ЯКОСТІ ДАНИХ

В АВТОМАТИЗОВАНИХ СИСТЕМАХ ОРГАНІЗАЦІЙНОГО УПРАВЛІННЯ

05.13.06 – Автоматизовані системи управління та прогресивні інформаційні технології

Автореферат

дисертації на здобуття наукового ступеня

кандидата технічних наук

Харків 2003

Дисертацією є рукопис.

Роботу виконано в Національному аерокосмічному університеті ім. М.Є. Жуковського “Харківський авіаційний інститут” Міністерства освіти і науки України.

Науковий керівник:

доктор технічних наук, професор КУЛІК Анатолій Степанович, Національний аерокосмічний університет ім. М.Є. Жуковського “Харківський авіаційний інститут”, завідуючий кафедрою систем управління літальних апаратів.

Офіційні опоненти:

доктор технічних наук, професор ПЕТРОВ Едуард Георгійович, Харківський національний університет радіоелектроніки, завідуючий кафедрою системотехніки;

кандидат технічних наук, доцент ТАНЯНСЬКИЙ Сергій Станіславович, Національний університет внутрішніх справ, доцент кафедри інформаційних систем і технологій в діяльності органів внутрішніх справ.

Провідна установа:

Національний технічний університет “Харківський політехнічний інститут”, кафедра системного аналізу і управління, Міністерство освіти і науки України, м. Харків.

Захист відбудеться “30” січня 2004 р. о 14 годині на засіданні спеціалізованої вченої ради Д64.062.01 у Національному аерокосмічному університеті ім. М.Є. Жуковського “Харківський авіаційний інститут” за адресою: 61070, Харків-70, вул. Чкалова, 17.

З дисертацією можна ознайомитися в бібліотеці Національного аерокосмічного університету
ім. М.Є. Жуковського “Харківський авіаційний інститут” (61070, Харків-70, вул. Чкалова, 17).

Автореферат розісланий “26” грудня 2003 р.

Вчений секретар

спеціалізованої вченої ради Чумаченко І.В.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Неперервне вдосконалення та інтенсивне впровадження інформаційних технологій у повсякденну практику привело до того, що в сучасних масштабних організаціях і потужних індустріальних підприємствах стали накопичуватися та оброблятися величезні обсяги даних. Керівники багатьох організацій усвідомили необхідність комп’ютерної підтримки прийняття управлінських рішень, що, в свою чергу, зумовило залежність ефективності функціонування організацій від якості даних автоматизованих систем організаційного управління (АСОУ). Так, із-за низької якості даних в АСОУ підприємства щорічно втрачають від 10 до 25% свого прибутку. Особливо гостро проблема якості даних стоїть у тому разі, коли АСОУ включає в себе множину неоднорідних розподілених і не узгоджених між собою програмних систем, які до того ж містять значну частку надмірних даних і не завжди задовольняють висунуті вимоги. Крім того, існує протиріччя між вимогами до достовірності інформації в АСОУ (10-7 ...10-4 помилок на символ залежно від класу задач) і психофізіологічними можливостями людини як джерела інформації або оператора (до 10-3 ... 10-2 помилок на символ).

Конструктивним шляхом до підвищення якості даних в АСОУ є створення спеціалізованих методів і засобів, які базуються на можливостях прогресивних інформаційних технологій і враховують конкретну специфіку помилок людини. Перші теоретичні дослідження в галузі якості даних автоматизованих систем датуються кінцем 50-х років минулого сторіччя. До цього часу значний вклад у розв’язання проблеми якості даних в АСОУ внесли такі вчені, як В.І. Левенштейн, Ю.М. Мельников, І.С. Зінгер, О.М. Пивоваров, Ф.А. Ніколаєв, А.Г. Маміконов, А.Т. Ашеров, В.А. Литвинов, В.В. Липаєв, Д. Кнут, М. Хернандес, А. Монге, E. Рам, М. Лі, А. Маркус, А. Мотро та інші. Проте, як показує аналіз існуючих методів і засобів підвищення якості даних, більшість робіт присвячена лише окремим питанням даної проблеми, наприклад, тільки розробці методів пошуку надмірних даних або контролю достовірності даних, що не дозволяє вирішувати проблему комплексно. До того ж відкритим залишається питання вибору архітектури баз даних, що забезпечує потенційну можливість підвищення якості даних в АСОУ, а представлені методи та засоби не завжди задовольняють сучасні вимоги щодо точності та швидкодії.

У той же час схожі задачі, пов'язані з визначенням стану технічної системи і відновленням її працездатності, успішно вирішують у сфері підвищення якості функціонування технічних систем. Зокрема, професором Куліком А.С. створено системний підхід до забезпечення необхідної якості функціонування в аварійних режимах технічних систем, в основі якого лежать принципи послідовного зняття невизначеності щодо технічного стану системи і гнучкого використання ресурсів для забезпечення якісного функціонування. В зв'язку з цим перспективним підходом до підвищення якості даних в АСОУ є створення методів та засобів для глибокого діагностування і гнучкого відновлення даних, що використовуються у процесах прийняття управлінських рішень.

Зв'язок роботи з науковими програмами, планами, темами. Робота над дисертацією проводилася автором на кафедрі систем управління літальних апаратів Національного аерокосмічного університету ім. М. Є. Жуковського “Харківський авіаційний інститут” в 1999–2003 рр. у рамках державної науково-технічної програми №7 “Перспективні інформаційні технології, прилади комплексної автоматизації, системи зв'язку” ДКНТПП України (Постанова Верховної Ради України 2705-хіі від 16.10. 92 г. “Про пріоритетні напрямки розвитку науки і техніки”) відповідно до плану науково-дослідних робіт за держбюджетними темами
Г603–53/98 “Розробка системних алгоритмів і комп'ютерних технологій аналізу і прогнозування функціонування вищих навчальних закладів у ринкових умовах” (ДР № 0198U001604, Інв. № 0200u004435) і Г301-30/00 “Теоретичні основи синтезу і математичне моделювання інтелектуальних систем управління аерокосмічними об’єктами за наявності збурень” (ДР № 0U002191, Інв. №0203U000622). Особисто автором, який був одним із співвиконавців робіт, у межах зазначених тем було проведено аналіз існуючих підходів до підвищення якості даних в АСОУ, формалізовано процес вибору архітектури баз неоднорідних і розподілених даних в АСОУ, створено підхід до підвищення якості даних в АСОУ, розроблено методи та засоби підвищення якості даних в АСОУ.

Мета і задачі дисертаційного дослідження. Дисертаційне дослідження проводилося з метою підвищення якості даних в автоматизованих системах організаційного управління за допомогою методів і засобів, розроблених на основі принципів діагностування і відновлення працездатності технічних систем. Для досягнення поставленої мети були визначені такі задачі.

1.

2.

3.

4.

5.

6.

Об'єкт дослідження – процес інтеграції неоднорідних і розподілених даних в автоматизованих системах організаційного управління.

Предмет дослідження – якість даних в автоматизованих системах організаційного управління.

Методи дослідження. У дисертаційній роботі при дослідженні процесу інтеграції неоднорідних і розподілених даних АСОУ використані методи системного аналізу, моделювання даних, теорії графів, прийняття рішень; при розробці методів підвищення якості даних – методи теорії множин і числення предикатів, теорії ймовірностей, теорії алгоритмів, теорії перешкодостійкого кодування, прийняття рішень і методи теорії сигнально-параметричного діагностування технічних систем.

Наукова новизна отриманих результатів

1.

2.

3.

4.

Практичне значення отриманих результатів. У результаті впровадження розроблених методів і засобів у складі підсистеми забезпечення якості даних автоматизованої системи управління адміністративно-фінансовою діяльністю (АСУ АФД) університету “ХАІ” достовірність даних підсистеми “Бухгалтерський облік” підвищилася на 38%, даних підсистеми “Облік кадрів” підвищилася на 8%. Доступність даних підсистеми “Бухгалтерський облік” підвищилася на 6%, даних підсистеми “Облік кадрів” підвищилася на 11%.

За результатами дисертаційних досліджень видано навчальні посібники “Автоматизація адміністративно-фінансової діяльності вузу” у співавторстві з Нечипоруком М.В., Кисілем В.А., Піщухіною О.О., Яровою О.В. та “Информационно-аналитическое обеспечение управления административно-финансовой деятельностью вуза” у співавторстві з Кривцовим В.С., Куліком А.С., Нечипоруком М.В., Піщухіною О.О., Мирною О.В., що використовуються в курсовому та дипломному проектуванні.

Впровадження результатів дисертаційного дослідження в Національному аерокосмічному університеті ім. М. Є. Жуковського “Харківський авіаційний інститут” підтверджується відповідними актами.

Особистий внесок здобувача. У працях, опублікованих разом із співавторами, особисто здобувачу належать такі результати, як підхід до підвищення якості даних в АСОУ [12], модель функціонування вузу в умовах переходу до ринкових умов [1], опис пропозицій ринку АСОУ [2], вибір концепції створення АСУ АФД вузу [3,15], математичне забезпечення індексно-реквізитного діагностування і відновлення даних в АСОУ [4,14], математичне забезпечення пошуку надмірних даних в неоднорідних довідниках АСОУ [5], діагностичні моделі даних в АСОУ [6], викладення сучасних проблем АФД вузу [8], опис задач АСУ АФД вузу [9], модель вибору архітектури баз неоднорідних і розподілених даних в АСОУ [10,13], структурна модель взаємодії підсистем в АСОУ [11]. Робота [7] виконана без співавторів.

Апробація результатів дослідження. Основні положення і результати дисертації доповідалися й обговорювалися на засіданнях кафедри систем управління літальних апаратів Національного аерокосмічного університету ім. М. Є. Жуковського “Харківський авіаційний інститут”. Деякі положення і результати викладалися на науково-технічних конференціях: VII міжнародній конференції “Нові технології в машинобудуванні”, Рибаче – Харків, 1998 р.; V міжнародній науково-технічній конференції “Контроль і управління в складних системах”, м. Вінниця, 1999 р.; науково-технічній конференції молодих учених Державного аерокосмічного університету ім. М.Є. Жуковського “ХАІ” “Системи управління-2000”, м. Харків, 2000 р., міжнародних науково-технічних конференціях “Інформаційні комп'ютерні технології в машинобудуванні”, м. Харків, 2001–2002 рр., міжнародній конференції з керування “Автоматика-2002”, м. Донецьк, 2002 р., науково-технічній конференції “Сучасні засоби автоматизації і комп’ютерно-інтегровані технології”, м. Краматорськ, 2003 р.

Публікації. Результати дисертаційної роботи відображено в 15 публікаціях. Серед них: 2 статті у наукових журналах, 5 статей у збірниках наукових праць, що включені в список видань ВАК України, і 8 статей, які опубліковано за матеріалами науково-технічних конференцій.

Структура і обсяг роботи. Дисертація складається зі вступу, п’яти розділів і висновків. Загальний обсяг роботи – 173 сторінки тексту, що містять 7 таблиць, 44 рисунка на 3 сторінках, список використаної літератури з 139 джерел на 12 сторінках, 3 додатки на 19 сторінках.

ЗМІСТ РОБОТИ

У вступі обґрунтовано актуальність задачі розробки методів і засобів підвищення якості даних в АСОУ. Показано зв'язок дисертації з науковими програмами, планами, темами. Сформульовано мету і задачі роботи. Відображено об'єкт, предмет і методи досліджень. Викладено наукову новизну і практичне значення отриманих результатів. Наведено інформацію про особистий внесок здобувача, а також про апробації й публікації результатів дисертаційної роботи.

У першому розділі “Сучасний стан проблеми якості даних в автоматизованих системах організаційного управління”, який складається з чотирьох підрозділів, проаналізовано відомі способи оцінки якості даних в АСОУ. Виходячи з прикладної спрямованості дослідження, вибрано підхід, що полягає у вимірюванні двох ортогональних характеристик якості, а саме – достовірності й доступності даних. Систематизовано типові неякісні дані й методи підвищення якості даних в АСОУ. Визначено недоліки існуючих методів підвищення якості даних, що полягають у недостатній продуктивності і точності одержуваних результатів. Виявлено схожість задач підвищення якості даних і задач забезпечення потрібної якості функціонування технічних систем. На прикладі сучасного вищого навчального закладу розглянуто складну організаційну систему та її інформаційні проблеми. На основі результатів аналізу існуючих розробок в галузі підвищення якості даних в АСОУ сформульовано наукові задачі дослідження.

Другий розділ “Дослідження процесу інтеграції неоднорідних і розподілених даних в АСОУ” включає в себе чотири підрозділи.

У першому із них виділено базові підсистеми АСОУ, а саме: “Фінансове планування”, “Облік кадрів”, “Бухгалтерський облік”, розглянуто основні функції підсистем і зв'язки між ними, показано, що у випадку неоднорідності й незалежності названих підсистем дані про співробітників організації будуть триразово дублюватися. Викладено необхідність інтеграції даних про співробітників для отримання цілісної й достовірної картини щодо кадрового складу організації.

В другому підрозділі на прикладі АСУ АФД вузу побудовано ER-моделі даних базових підсистем. Аналіз побудованих моделей даних дав можливість визначити конкретні сутності, що є у всіх трьох підсистемах.

У третьому підрозділі формалізовано процес вибору архітектури баз даних (БД) АСОУ, яка забезпечує інтеграцію та підвищення якості неоднорідних і розподілених даних. Для цього запропоновано її стратифіковане представлення виходячи з трьох рівнів абстрагування: фізичного, логічного та прикладного. Стратифікований опис архітектури БД АСОУ істотно спрощує задачу вибору, оскільки страти практично не залежать один від одного. У зв'язку з неоднорідністю і розподіленістю базових підсистем АСОУ найбільш важливим стає питання вибору архітектурного рішення на фізичній страті – способу інтеграції існуючих даних. Існує ряд альтернатив інтеграції розподілених даних. Серед них: 1) стандартизоване програмне забезпечення проміжного рівня; 2) об’єктно-орієнтовані розподілені технології; 3) шлюзи БД; 4) сховища даних. Як критерії вибору були використані: 1) можливість практичної реалізації архітектури БД; 2) рівень інтеграції розподілених даних і можливість застосування адекватних моделей даних для різних компонентів АСОУ; 3) відповідність стандартам відкритих систем; 4) можливість підвищення якості даних; 5) швидкість доступу до даних. За кожним критерієм проведено обґрунтоване вимірювання якості альтернатив. Для багатокритеріального вибору було використано метод зваженої суми, що найчастіше застосовується при вирішенні практичних задач. У результаті найбільшу сумарну корисність одержали сховища даних.

У четвертому підрозділі розглянуто місце засобів підвищення якості даних у процесі інтеграції неоднорідних і розподілених даних АСОУ в сховище даних. Оскільки сховище даних являє собою джерело незмінних даних для систем підтримки прийняття рішень, отже, дані повинні відновлюватися до надходження в сховище даних у спеціальному буфері. Далі викладено підхід до підвищення якості даних. Його основними принципами стали принципи системного підходу до забезпечення необхідної якості функціонування технічних систем:

1.

2.

3.

4.

Відповідно до принципу послідовного зняття невизначеності про стан даних треба було провести топологічне упорядкування реляційної моделі буфера сховища даних. Для цього її розглянуто як орієнтований граф G=(E,Г), що має порядкову функцію. За допомогою методу Демукрона, було одержано упорядкований граф. На першому етапі необхідно було за рахунок інформаційної надмірності підвищити якість довідників і незалежної сутності “Співробітник”. Далі потрібно було пов'язати еталонні дані з даними про вакансії, наукові ступені та звання співробітника. Третій етап передбачав підвищення якості даних про призначення, і, нарешті, на четвертому етапі необхідно було пов'язати відновлені дані про призначення співробітників з нарахуваннями й утриманнями за призначеннями.

Третій розділ “Розробка методів пошуку надмірних даних в АСОУ” включає в себе два підрозділи. У першому з них представлено метод пошуку схожих реквізитів у неоднорідних довідниках.

Відповідно до принципу діагностування даних щодо заданої множини найбільш поширених видів помилок: однократних транскрипцій, додавань символу, пропусків символу, транспозицій суміжних символів, дворазових транскрипцій як критерій схожості реквізитів було вибрано мінімум відстані Левенштейна між ними, тобто

d(sm1, sm2) , (1)

де sm1, sm2 – рядкові значення двох реквізитів; d(sm1, sm2)– мінімальна кількість операцій редагування, необхідних для перетворення реквізиту sm1 на реквізит sm2; - деякий заданий поріг, N, причому якщо нерівність (1) виконується, тоді зазначені реквізити схожі. Вибір цього критерію зумовлено тим, що для інших відомих критеріїв схожості реквізитів, таких, як лексикографічна близькість рядків в упорядкованому наборі, рівність q-грам, рівність відображень “SOUNDEX”, не всі з перерахованих видів помилок можуть бути виявлені.

Постановка задачі пошуку схожих реквізитів має такий вигляд: нехай існує набір реквізитів SM = (sm1,..., smn0,..., smn) і задано натуральне число . Необхідно поставити у відповідність множину , таку, що .

Використовуючи “наївний” підхід, ми повинні для кожного реквізиту і для кожного реквізиту перевірити, чи виконується умова d(smi, smj) . При цьому кількість таких перевірок складе n0(n – n0). Оскільки в реальному випадку (n – n0) n0, то при досить великому n0 “наївний” підхід до виявлення потрібних пар стає неефективним.

Вирішення, що пропонується складається з двох етапів. Спочатку з набору випадково вибираються k реквізитів o1, o2, ...,ok, (k<n), що надалі будуть асоціюватися з осями k- мірного евклідова простору Ek. Потім кожному smiSM ставиться у відповідність точка цього гіперпростору P(smi), координати якої дорівнюють відстаням Левенштейна до осей, тобто . На другому етапі відстані Левенштейна розраховуються тільки для тих реквізитів, для яких виконуються викладені нижче необхідні умови схожості.

Твердження 1. Якщо smi, smj – реквізити, відстань Левенштейна між якими не більше деякого порога , тоді: а) точка P(smj) розміщується в Ek у межах гіперкуба з центром у точці P(smi) і стороною 2; б) абсолютне значення різниці відстаней від точок P(smi) і P(smj) до початку координат у Ek не перевищує ; в) абсолютне значення різниці довжин реквізитів smi, smj не перевищує .

Швидкодія запропонованого методу залежить від кількості реквізитів, які складають набір SN, вибраної кількості осей, а також порога . При невеликому часова складність методу не перевищує O(kn).

Другий підрозділ присвячено розробці методу пошуку надмірних кортежів у реляційному відношенні. Постановка задачі має такий вигляд: нехай R – відношення арності h, що включає в себе n- кортежів:

, (2)

де pkiN - первинний ключ, що унікально ідентифікує кортеж mi у відношенні R;
smi1,...,smih – рядкові значення реквізитів кортежу mi. Тоді необхідно розбити R на z непересічних кластера (непорожні множини) так, щоб у кожному кластері всі кортежі були попарно схожі.

Ця задача може бути декомпозована на дві: пошук усіх пар схожих кортежів і об'єднання отриманих пар у кластери. Тоді рішенням першої задачі буде множина пар схожих кортежів (mi,mj), pki>pkj. Очевидно, що задача пошуку схожих кортежів може бути зведена до задачі пошуку схожих реквізитів шляхом конкатенації всіх реквізитів кожного кортежу в рядок. Проте у випадку використання найбільш простого алгоритму Вагнера-Фішера для розрахунку відстані Левенштейна між двома рядками ефективність пошуку буде невисокою в силу того, що справедливе таке твердження.

Твердження 2. Часова складність обчислення відстані Левенштейна за допомогою алгоритму Вагнера-Фішера для двох рядків і , таких, що , , де – оператор конкатенації, перевищує часову складність h- обчислень відстаней Левенштейна для відповідних реквізитів кортежів mi і mj.

Виходячи з цього як критерій схожості кортежів і було вибрано .

Запропоноване вирішення задачі пошуку пар схожих кортежів базується на вирішенні попередньої задачі і також складається з двох аналогічних етапів. Теоретичною основою для цього стали доведені необхідні умови схожості кортежів, аналогічні необхідним умовам схожості реквізитів.

Для об'єднання отриманих пар кортежів у кластери було використано відому структуру даних – систему непересічних множин.

Часова складність розробленого методу при невеликому також складає O(kn).

Четвертий розділ “Розробка методу індексно-реквізитного діагностування і відновлення даних в АСОУ” включає в себе три підрозділи. Перший із них містить постановку задачі.

Після визначення кластерів схожих кортежів потрібно для кожного кластера сформувати еталонний кортеж, що згодом буде занесений у сховище даних АСОУ. Крім того, помилкові кортежі слід повернути у відповідні підсистеми з указівкою місця помилки, тобто конкретного помилкового реквізиту. Нехай R1 – розглянутий кластер, тобто множина, що включає в себе q-кортежів виду (2), qN. Для кожного -го атрибуту, (), сформуємо відповідну мультимножину M =(sm1,sm2,..., smq). Тоді, ґрунтуючись на мажоритарному принципі, можна сформулювати визначення ступенів коректності мультимножини M.

Мультимножина M, ( ) є такою, що коректується, якщо більше половини, але не всі з її елементів попарно однакові. Формально

,

де CORRECTED(M) – предикат, що набуває значення “ІСТИНА”, якщо M –мультимножина, що коректується; – підмультимножина . Елемент smip M – еталонний, якщо . Елемент smip M – помилковий, якщо .

Очевидне вирішення щодо діагностування мультимножини M полягає в попарному порівнянні всіх її елементів smip і smjp, (ij). Разом з тим максимальний час виконання цієї процедури може бути оцінений як Tзаг.поп.пор((q2 – q)/2*L+q)*tпор, де tпор – час виконання команди порівняння двох символів.

Істотним поліпшенням даного методу є використання перетворення ключів (гешування), що дозволить відобразити реквізити в індекси масиву (адреси пам'яті), тобто H: smip aip, де H – відображення, aip – індекс масиву, що відповідає smip елементу M.

Основні труднощі, пов'язані з перетворенням ключів, полягають у підборі такого відображення , яке дозволило б: 1) за наявності різних індексів однозначно встановлювати розходження в реквізитах; 2) виявляти найбільш розповсюджені помилки людини у реквізитах шляхом зіставлення індексів; 3) для випадкових реквізитів з якою завгодно малою ймовірністю отримувати збіжні індекси; 4) при рівності індексів установлювати з високою ймовірністю, що реквізити однакові.

У наступному підрозділі зроблено вибір відображення . Для цього поставлену задачу було зведено до задачі теорії перешкодостійкого кодування. Але на відміну від передачі по каналу зв'язку, при якій під впливом перешкод можуть змінюватися як інформаційні розряди, так і перевірні, тут ушкодженням піддаються тільки інформаційні розряди.

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

, (3)

де - поліном від фіктивної змінної , який відповідає інформаційним розрядам , – число інформаційних розрядів, – довжина кодових комбінацій, “”– оператор, що позначає

залишок від ділення поліномів, – твірний поліном.

Доведено, що перша вимога задовольняється, якщо , де – степінь твірного полінома .

При розгляді другої вимоги було доведено, що в тому разі, коли для представлення одного символу реквізиту використовується 8 бітів, відрізняється від будь-якою однократною транскрипцією чи транспозицією або дворазовою транскрипцією суміжних символів і , де , то .

Пошук умов, які задовольняють третю вимогу, привів до припущення, що всі реквізити рівноймовірні і рівномірно відображає їх на весь діапазон можливих адрес . Тоді у випадку незалежного введення трьох реквізитів, і ймовірність пропуску помилок – , що при складає приблизно .

Виходячи з припущень про рівноймовірність усіх реквізитів і рівномірності їхнього відображення на відповідні діапазони індексів при розгляді четвертої вимоги за формулою Байєса були обчислені апостеріорні ймовірності ідентичності реквізитів за умови рівності індексів. Наприклад, ймовірність того, що при збігаються реквізити , при складає приблизно .

Розглянуто стандартні поліноми CRC-CCITT – і CRC-16 – , які хоча й не відносяться до циклічних кодів, але успадковують усі їх здатності щодо виявлення помилок. Обидва поліноми задовольняють висунуті вимоги.

Для вибору конкретного полінома було проведено серію експериментів на основі даних про прізвища співробітників університету “ХАІ”. У кожне з 2175 різних прізвищ спеціально вводилися різні найбільш розповсюджені помилки людини. Крім цього, досліджувалися інші методи розрахунку 8– і 16–бітних контрольних сум, таких, як контрольні суми по модулях 256 і 65536; знакозмінні контрольні суми по модулях 256 і 65536; контрольні суми по модулях 256 і 65536 з ваговими коефіцієнтами від 1 до 25.

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

Вибір найкращої альтернативи було здійснено з використанням методу зваженої суми. При цьому вагові коефіцієнти були сформовані з відповідно до питомих ваг класів помилок. У результаті вибрано поліном .

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

Нехай – мультимножина індексів, розрахованих для реквізитів виходячи з (3), причому і нехай – вектор-рядок розмірністю , такий що , де . Тоді рівняння, що характеризує відсутність помилкових реквізитів у матиме вигляд . Якщо ж у існують помилкові реквізити, то . Діагностична модель для виявлення помилкових даних у визначається формулою

,

де – непряма ознака наявності помилкових даних в Якщо , то – безпомилкове, інакше містить помилкові реквізити.

У тому разі, коли розрахунок індексів відповідно до (3) відбувається до початку процесу підвищення якості даних, максимальний час виконання індексно-реквізитної діагностичної процедури складає .

Таким чином, продуктивність індексно-реквізитного діагностування в раз вище, ніж продуктивність діагностування, основаного на попарному порівнянні реквізитів. Наприклад, при і .

Останній підрозділ присвячено відновленню даних. Якщо в результаті індексно-реквізитного діагностування знайдено еталонні та помилкові дані, то відновлення даних у буфері сховища даних здійснюється автоматично. В тому разі, коли еталон не існує, рішення має прийняти адміністратор підсистеми забезпечення якості даних.

П’ятий розділ “Підсистема забезпечення якості даних в АСОУ” містить чотири підрозділи. В першому із них описано структуру і функції підсистеми. Її складовими частинами є засіб підвищення якості даних у довідниках, а також засіб підвищення якості даних у таблицях (рис. 1).

Рис. 1. Структурна модель підсистеми забезпечення якості даних в АСОУ

Наведено моделі метаданих і сценарії багаторазового використання підсистеми, що дозволяють проводити економічне відносно використовуваної пам’яті підвищення якості даних.

У другому підрозділі описано алгоритмічне забезпечення підсистеми у вигляді блок-схем, а також програмне забезпечення, реалізоване в середовищі Delphi 6.

Викладені в третьому підрозділі експериментальні дослідження розроблених засобів були проведені на основі реальних даних університету “ХАІ”. Так, шляхом злиття даних про посади співробітників університету отримано єдиний довідник посад, що складався з 566 найменувань, з яких перші 262 посади були еталонними. Всі експерименти проводилися на персональному комп'ютері з процесором CELERON 566 МГц і 196 Мб ОПЗ, операційною системою – Windows NT 4 Server, причому засобу підвищення якості даних в довідниках знадобилося 2924 Кб ОПЗ. Як поріг було вибрано величину 2. У результаті пошуку було виявлено 162 пари схожих реквізитів. Ідентичні результати знайдено і для “наївного” підходу. Виявлено такі схожі найменування, як “зав. відділу”, “ зав. відділом”, d=2; “прибиральниця”, “прибаральниця”, d=1; “асистент”,
“а систент ”, d=1 і т.ін. Результати експериментальних досліджень засобу підвищення якості довідників проілюстровано на рис. 2.

а б

Рис. 2. Результати експериментальних досліджень розробленого засобу: а – залежність часу пошуку схожих реквізитів від кількості осей; б – залежність часу пошуку схожих реквізитів від кількості реквізитів

Крім порівняння з простим, але неефективним за швидкодією “наївним” підходом проведено порівняння із засобом, реалізованим на основі методу лексикографічного упорядкування реквізитів (таблиця). Показники точності й помилковості рішень відповідають відомим показникам Recall і False-Positive Error. Як видно з таблиці, при невеликому розмірі вікна, засобу, основаному на лексикографічному упорядкуванні, потрібно менше часу, ніж запропонованому. Проте для того, щоб підвищити точність рішення, необхідно збільшувати розмір вікна, що, в свою чергу, призводить до збільшення часу пошуку.

Результати порівняння з підходом на основі лексикографічного упорядкування реквізитів

Показники ефективності | Запропо-нований

підхід | Лексикографічне упорядкування

Розмір вікна, w

2 | 3 | 4 | 7 | 16

Точність | 1 | 0,96815 | 0,98089 | 0,98726 | 0,98726 | 0,99363

Помилковість | 0,03086 | 0,02469 | 0,02469 | 0,03086 | 0,03086 | 0,03086

Час, мс | 296 | 101 | 130 | 170 | 261 | 531

Для експериментальних досліджень засобу підвищення якості даних кортежів вибрано записи про співробітників університету “ХАІ”, отримані з неоднорідних баз даних підсистем “Облік кадрів” і “Бухгалтерський облік”. Загальна кількість записів склала 1773. У результаті пошуку при виявлено 1040 дублікатів і 272 схожих записи, які були об'єднані в 631 кластер. При і запропонований засіб дає перевагу в швидкодії приблизно в 37 разів і використовує 6388 Кб ОПЗ. Було проведено порівняння з підходом на основі лексикографічного упорядкування кортежів. При невеликому розмірі вікна цей метод виконується швидше, ніж запропонований. Проте для того, щоб отримати максимальну точність результатів, необхідно збільшити розмір вікна до 18, що дає перевагу в швидкодії запропонованому методу в 1.6 раза.

Проведені експерименти з діагностування і відновлення даних показали, що з 631 кластера схожих кортежів для 468 сума відстаней Левенштейна між коренем і кожним листом дорівнювала нулю, для 7 кластерів еталонний кортеж було визначено за мажоритарним принципом, для 81 кластера еталонні кортежі було отримано за допомогою індексно-реквізитного підходу, а для 75 кластерів були знайдені не всі еталонні реквізити.

В останньому підрозділі для оцінки результатів застосування розроблених засобів підвищення якості даних у процесі інтеграції неоднорідних і розподілених даних АСУ АФД університету “ХАІ” використано показники достовірності і доступності даних, викладені в роботах А. Мотро. Встановлено, що достовірність даних підсистеми “Бухгалтерський облік” підвищилася на 38%, достовірність даних підсистеми “Облік кадрів” підвищилася на 8%. Доступність даних підсистем підвищилася на 6 і 11% відповідно.

Основні результати і висновки

Широке впровадження АСОУ в сучасних організаціях привело до підвищення актуальності задач забезпечення якості комп'ютерних даних. Низька якість даних в АСОУ, як правило, зумовлена двома основними факторами, а саме: існуючим протиріччям між вимогами до достовірності інформації та психофізіологічними можливостями людини, а також використанням у складі АСОУ неоднорідного і розподіленого програмного забезпечення та множини надмірних даних.

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

У дисертації викладено новий підхід до підвищення якості даних, корені якого лежать у системному підході до забезпечення необхідної якості функціонування технічних систем в аварійних режимах. Перспективність застосування принципів діагностування і відновлення працездатності технічних систем при розробці методів і засобів підвищення якості даних зумовлена схожістю задач, що вирішуються у цих областях. Як інформаційний простір для розв’язання задач підвищення якості даних АСОУ вибрано сховище даних, яке найкраще задовольняє вимоги практичної реалізації архітектури БД, інтеграції розподілених даних, підвищення якості даних на основі надмірності і швидкості доступу до даних.

Розроблений метод пошуку схожих реквізитів у неоднорідних довідниках АСОУ складається з проектування реквізитів у точки евклідова гіперпростору і швидкого пошуку реквізитів, що відповідають строго доведеним необхідним умовам схожості. Це дає переваги над відомими методами у швидкодії й точності рішення.

Метод пошуку схожих кортежів у реляційному відношенні являє собою модифікацію методу пошуку схожих реквізитів. Теоретично обґрунтовано введення нового критерію схожості. Строгий доказ необхідних умов схожості кортежів дозволив одержати переваги у швидкодії і точності над відомими методами, а також у швидкодії над попереднім методом, застосованим до задачі пошуку схожих кортежів шляхом конкатенації всіх реквізитів кортежу в один реквізит.

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

Ефективність використання розроблених засобів у складі підсистеми забезпечення якості даних АСУ АФД університету “ХАІ” характеризується підвищенням на 38% достовірності і на 6% доступності даних підсистеми “Бухгалтерський облік”, а також на 8% достовірності і на 11% доступності даних підсистеми “Облік кадрів”. Отримані результати свідчать про досягнення основної мети дисертаційного дослідження – підвищення якості даних АСОУ.

Список опублікованих праць

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

АНОТАЦІЯ

Чухрай А.Г. Методи та засоби підвищення якості даних в автоматизованих системах організаційного управління.

Дисертацією є рукопис, поданий на здобуття наукового ступеня кандидата технічних наук