Размещено на http://www.allbest.ru/

Міністерство освіти і науки України

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

УДК 004.65:681.3.01

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

Актуальність теми. Безперервне зростання вимог до функціональності автоматизованих систем управління (АСУ), використання програмних продуктів, які були створені неодночасно та різними колективами розробників, призвели до того, що сучасну АСУ можна охарактеризувати як сукупність неоднорідних і розподілених підсистем. Разом із тим подальший розвиток, зокрема впровадження систем підтримки прийняття рішень, потребує інтеграції таких підсистем у єдиний інформаційний простір. Необхідною умовою успішного вирішення цієї задачі є створення засобів, які б дозволили отримувати користувачам АСУ достовірні й повні дані. Але сучасні засоби інтеграції найчастіше нездатні виконати цю умову. Так, через наявність недостовірних і неповних даних в АСУ виконання 33% інтеграційних проектів прийшлось зупинити, більше того, організації щорічно втрачають від 8 до 60% свого прибутку. Аналіз практики використання АСУ дозволяє також визначити головну причину появи недостовірних та неповних даних - помилки оператора, зумовлені обмеженістю його психофізіологічних можливостей.

Значний внесок у пошук шляхів розв'язання зазначених проблем зробили такі вчені, як Л. Інгліш, Т. Редман, В. Кім, В.А. Литвинов, В.В. Крамаренко, Е. Рам, Х.Б. Ньюкомб, Д. Кнут, А. Монге, В.І. Левенштейн, А.С. Кулік, М. Хернандес, А. Маркус, Дж. Малетик, Дж. Хіпп, Р. Агравал та інші. Так, аналізуючи роботи різних авторів, можна зазначити, що відомі методи інтеграції баз даних дозволяють підвищувати достовірність і повноту лише даних, наведених у декількох джерелах інформації. Разом із тим такого обмеження позбавлені методи, в яких використано природну інформаційну надмірність даних, тобто знання про конкретні особливості даних та їх сполучення. Відзначаючи безумовну корисність упровадження згаданих методів, слід зауважити, що постійне зростання обсягів даних, що обробляються, зумовлює потребу в створенні більш ефективних за швидкодією методів.

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

Зв'язок роботи з науковими програмами, планами, темами. Робота над дисертацією проводилася автором на кафедрі систем управління літальних апаратів Національного аерокосмічного університету ім. М. Є. Жуковського “Харківський авіаційний інститут” у 2000-2007 рр. відповідно до плану науково-дослідних робіт за держбюджетними темами Д301-30/00 “Теоретичні основи синтезу і математичне моделювання інтелектуальних систем управління аерокосмічними об'єктами за наявності збурень” (ДР № 0100U002191), Д301-6/03 «Розробка науково обґрунтованих методів та інструментальних засобів автоматизації прийняття рішень при управлінні адміністративно-господарчою діяльністю сучасного вищого навчального закладу» (ДР № 0103U004079) та за грантом Президента України “Розробка комп'ютерної системи інтелектуальної підтримки прийняття рішень при управлінні адміністративно-господарчою діяльністю сучасного вузу” (ДР № 0105U006872). Особисто автором, який був одним із співвиконавців робіт, у межах зазначених тем було проведено аналіз результатів, що було досягнуто при інтеграції даних, запропоновано новий метод злиття записів, створено модель даних про персонал університету для буфера сховища даних.

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

1. Провести аналіз існуючих методів підвищення достовірності й повноти баз даних.

2. Розробити метод інтеграції баз даних, що враховує достовірність і повноту даних.

3. Удосконалити метод діагностування даних на основі природної інформаційної надмірності.

4. Створити модель схожості рядків та удосконалити метод злиття записів.

5. Удосконалити метод пошуку природної інформаційної надмірності.

6. Створити інформаційну технологію для підвищення достовірності й повноти інтегрованих баз даних.

7. Впровадити створену інформаційну технологію у реальні АСУ і оцінити ефективність її використання.

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

Предмет дослідження - методи підвищення достовірності й повноти інтегрованих баз даних.

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

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

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

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

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

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

Практичне значення отриманих результатів. У результаті впровадження розроблених методів і засобів у складі підсистеми підвищення достовірності й повноти даних автоматизованої системи управління персоналом університету «ХАІ» (АСУ ПУ «ХАІ») достовірність і повнота даних системи підвищилися на 8 і 5% відповідно. Для забезпечення показників достовірності й повноти на рівні 99,35 та 98,08% було розроблено рекомендації, що передбачають додаткове введення семи (16,3% від загальної кількості) атрибутів, у той час як організація подвійного введення усіх атрибутів АСУ ПУ «ХАІ» без застосування запропонованих методів дозволила б забезпечити достовірність і повноту даних на рівні 98,73 та 98,06% відповідно. Впровадження цієї ж системи для підвищення достовірності й повноти даних автоматизованої системи документообігу, що супроводжує збут готової продукції НВП «Хартрон-Плант» (АСУ ЗГП «Плант»), дало можливість підвищити відповідні показники на 9,2 та 1,5%. Для подальшого підвищення показників розроблено рекомендації, згідно з якими потрібно організувати додаткове введення дев'яти атрибутів (12%), що дозволить підвищити відповідні показники в АСУ ЗГП «Плант» на 10,3 та 5,9%.

Теоретичні результати дисертаційної роботи у вигляді методів пошуку знань і діагностування даних упроваджено в навчальний процес університету «ХАІ» на кафедрі систем управління літальними апаратами.

Результати наведених вище впроваджень засвідчено відповідними актами.

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

Апробація результатів дослідження. Основні положення і результати дисертації доповідалися і обговорювалися на засіданнях кафедри систем управління літальних апаратів Національного аерокосмічного університету ім. М. Є. Жуковського “Харківський авіаційний інститут”. Деякі положення та результати викладалися на науково-технічних конференціях: “Автоматика-2002”, Донецьк, 2002 р.; “Інформаційні комп'ютерні технології в машинобудуванні”, Харків, 2002, 2004, 2005 рр.; “Інформаційні технології в системі керування вищою освітою України”, Херсон, 2004 р.; “Автоматизація, технологія та якість в машинобудуванні”, Донецьк, 2004 р.; “Дні науки `2005”, Дніпропетровськ, 2005 р.; «East-West Fuzzy Colloquium», Ціттау, Німеччина, 2005-2006 рр.; «Гарантоздатні (надійні та безпечні) системи, сервіси та технології», Полтава, 2006 р.

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

Структура і обсяг роботи. Дисертаційна робота має у своєму складі вступ, чотири розділи, висновки і три додатки, викладена на 176 сторінках, у тому числі 32 рисунки по тексту, 1 рисунок на окремій сторінці, 5 таблиць по тексту, список літературних джерел із 135 найменувань на 13 сторінках, 3 додатки на 31 сторінці.

основний Зміст роботи

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

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

Основний зміст розділу опубліковано у роботах [1,2,4-6, 9,10,13].

Другий розділ присвячено розробці методу інтеграції даних в АСУ та розбито на чотири підрозділи.

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

, , (1)

де джерело Sch визначається як сукупність реляційних відношень Sch={R₁,R₂,…,R_q}; S_Sch, C_Sch -показники достовірності й повноти джерела Sch; q - кількість відношень у Sch; , - показники достовірності й повноти і-го відношення з Sch. Згідно зі згаданими вище роботами, кожен доданок з (1) обчислюється за допомогою процедури, суттю якої є порівняння реального відношення з еталонним. Оскільки одержання еталону не завжди є можливим, була запропонована процедура обчислення достовірності й повноти даних відношення, яка базується на ймовірностях виникнення неякісних даних і може бути визначена за допомогою таких рівнянь:

,, (2)

(3)

(4)

де R_i - i-те відношення Sch із заголовком {A₀:T₀, A₁:T₁, …, A_h:T_h}, A_j - ім'я атрибута, T_j - домен, на якому визначено атрибут; A₀ - ключовий атрибут; jR - відношення, отримане як проекція відношення R_i за ключовим та j-м атрибутами; (h+1) - кількість атрибутів у R_i; p_im - ймовірність того, що кортеж з ідеального відношення буде пропущено при введенні даних; p_id - ймовірність того, що кортеж з ідеального відношення буде продубльовано в реальному відношенні; p_jRi - ймовірність того, що після усунення кортежів, що дублюються, j-й атрибут випадково вибраного кортежу буде помилковим.

Таким чином, отримавши експериментально або за допомогою експерта оцінки p_im, p_id, p_jRi для кожного відношення джерела та використавши залежності (1)-(4), можна отримати показники достовірності й повноти даних у кожному джерелі.

У другому підрозділі проаналізовано результати, яких можна досягти за допомогою впровадження традиційного процесу інтеграції даних. Використання нових методів злиття записів, в яких враховано специфіку введення даних людиною-оператором, дозволить отримати такі результати. По-перше, в усіх відношеннях буфера сховища даних Sch_buf ={R_{buf_1},R_{buf_2},…,R_{buf_l}} виявляються і, отже, усуваються кортежі, що дублюються, тобто . По-друге, кортеж може бути пропущено тільки тоді, коли цей кортеж пропущено в кожному з джерел, отже, , де u - кількість джерел, в яких наведено і-те відношення; - ймовірність того, що кортеж з ідеального і-го відношення буде пропущено в g-му джерелі. По-трете, для того, щоб в атрибутах, що дублюються в різних джерелах, не було виявлено помилку, потрібно, щоб у кожному атрибуті було припущено однакову помилку, тому , де u - кількість джерел, в яких наведено j-й атрибут і-го відношення; - ймовірність того, що j-й атрибут i-го відношення буде помилковим у g-му джерелі.

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

Рис. 1 Схема процесу інтеграції неоднорідних даних у сховище даних

Результат, що отримується після застосування методу злиття записів у деякий момент часу, можна уявити як деяке універсальне відношення зі структурою, що визначається предмет-ною областю. Для спрощення математичних міркувань у дисертації на бінарному домені T₀₁={0,1} визначено відношення , яке отримується з по аналогії з роботами щодо аналізу даних.

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

Інформаційним ресурсом, що дозволяє розв'язувати такі задачі, є знання про конкретні специфічні властивості даних та їх сполучень. У роботі знання щодо даних подано як сукупність правил F={f₁, f₂, …, f_n}. Кожне правило уявляється у вигляді трійки f=(i,H,C), де i - номер правила в базі знань; H, С - множини атрибутів ( та ), що описують посилку та висновок правила відповідно. Відображаючи залежності між атрибутами, кожне правило дозволяє сформувати двозначний предикат, що відображає, чи суперечать атрибути кортежу r даному правилу: , де f_i(r)=0 - атрибути r суперечать правилу f_i, а f_i(r)=1 - атрибути r відповідають правилу f_i або не суперечать йому, оскільки не виконується умова в посилці правила; h₁, h₂, …, h_Hcnt, c₁, c₂, …, c_Ccnt - усі атрибути, що складають посилку та висновок правила.

Виникнення в будь-якої помилки є невизначеною подією з точки зору моменту k її появи, помилкового кортежу з , атрибута, в якому вона з'явиться, конкретного виду помилки. Тому є достатньо очевидним, що підхід, який використовується в існуючих системах і полягає в послідовній перевірці кожного кортежу з на відповідність кожному правилу з F, буде неефективним. Разом із тим подібна проблема ефективно вирішується в рамках системного підходу до діагностування систем управління (СУ) та інших об'єктів, запропонованого професором Куліком А.С., де створюється ефективна процедура діагностування шляхом послідовного зняття невизначеності щодо стану СУ та використання концепції діагностичних моделей (ДМ), що дозволяють діагностувати за непрямими ознаками відмов та ін. Положення згаданого підходу було використано для створення ефективного методу діагностування даних. Так, згідно з принципом послідовного зняття невизначеності щодо стану даних було розроблено послідовність діагностування, яка складається із задач виявлення помилок, пошуку кортежів із помилками, пошуку помилкових атрибутів і визначення виду помилки. Розглянемо вирішення кожної з них.

Результатом вирішення задачі виявлення помилок є встановлення факту, чи є хоча б один кортеж у , який суперечить хоча б одному правилу з F, тобто

. (5)

Визначимо допоміжні функції Q_supp(R,Z) (підтримка множини атрибутів Z у відношенні R) та d_det(R,F): , , де R - відношення, визначене на бінарному домені; z₁,z₂,…,z_n - множина атрибутів відношення R, що складає у сукупності вихідний набір Z; - оператор реляційної алгебри, що позначає вибірку з R за заданою умовою; F_ruleset і F_hyp - множини наборів атрибутів, що визначаються на основі множини правил таким чином: , , де - оператор реляційної алгебри, що позначає проекцію з R за заданою множиною атрибутів; EXT R ADD (вираз) AS Ім'яАтрибута - оператор розширення відношення R, що додає новий атрибут Ім'яАтрибута, обчислюючи його для кожного кортежу, як указано у виразі; - i-та множина атрибутів із F_ruleset та F_hyp відповідно. За допомогою таких функцій було визначено ДМ виявлення помилок: , де - еталонне відношення; - непряма ознака наявності помилки.

Окрім формування ДМ у процесі вирішення задачі було строго доведено такі твердження.

Твердження 1. Якщо R₁ - відношення, що містить тільки один кортеж r, а F - множина правил, то значення функції d_det(R₁,F) буде дорівнювати нулю тоді й тільки тоді, коли кортеж r не суперечить жодному з правил F, та буде меншим за нуль тоді й тільки тоді, коли кортеж r суперечить хоча б одному з правил F, тобто і . Твердження 2. Відношення R є безпомилковим, тобто жоден із кортежів R не суперечить жодному з правил F тоді й тільки тоді, коли значення функції d_det(R,F) буде дорівнювати нулю, тобто .

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

На етапі пошуку кортежів із помилками треба знайти конкретні кортежі з , що суперечать хоча б одному правилу з F, тобто прямою ознакою наявності помилки в кортежі є

. (6)

Для побудови ДМ на цьому етапі потрібно було визначити такі допоміжні функції: , де - множина усіх атрибутів кортежу r, що дорівнюють одиниці; М - деяка множина, елементами якої, в свою чергу, є множини атрибутів; . Тоді ДМ пошуку помилкових кортежів , де - еталонний кортеж. Як і при вирішенні попередньої задачі, наведені вище твердження дозволили не обчислювати еталонний кортеж, оскільки , та засвідчити повну діагностованість ДМ. Результатом вирішення пошуку кортежів із помилками є розбиття вихідного відношення на безпомилкове відношення і відношення, яке містить усі кортежі з помилками . Слід також відмітити, що при використанні ДМ і відомого алгоритму обчислення підтримки наборів, який використовують при знаходженні асоціативних правил, алгоритмічна складність вирішення цієї та попередньої задачі становить , у той час як при використанні (5),(6) становить , що підтверджує тезу про ефективність діагностування за непрямими ознаками.

Вирішення задачі пошуку помилкових атрибутів здійснюється в два етапи. На першому з них для кожного кортежу за існуючими правилами виконують прямий логічний висновок. Результатом такого висновку стає кортеж , атрибути якого дорівнюють одиниці, якщо вони дорівнюють одиниці в або існують правила, згідно з якими вони мають дорівнювати одиниці. На другому етапі для кожного атрибута з вихідного неперетворюваного відношення формується множина відповідних значень A_i з . Тоді ДМ, що дозволяє виявити помилковість атрибута, можна визначити як , де - функція, що дорівнює кількості одиниць у підмножині атрибутів W кортежу r.

При визначенні виду помилки в дисертаційній роботі розглянуто найбільш поширений випадок, коли спосіб введення даних оператором дозволяє звузити множину можливих видів до однократних транскрипцій, додавання символу, пропуск символу, транспозиції суміжних символів і двократних транскрипцій. Після вирішення попередньої задачі є рядок , який був введений користувачем, та рядок , який ймовірно мав бути введеним. Показано, що так же, як і раніше, діагностування за прямими ознаками не є ефективним. Описано такі непрямі ознаки: , , , та , де Eq(v1,v2) - функція від двох рядків v1,v2 однакової довжини, значення якої дорівнює кількості позицій, у яких символи з v1 та v2 неоднакові; Cmp(v₁,v₂) - функція від двох рядків, значення якої дорівнює n-1, де n - номер першої позиції, в якій рядки неоднакові; - рядок, що є дзеркальним відображенням рядка v, тобто останній символ із v є першим у і т.д. Із використанням цих непрямих ознак було збудовано ДМ для кожного виду помилки з наведених вище: , , , і , де - істина, якщо була допущена однократна транскрипція; - додавання символу; - пропуск символу; - транспозиція суміжних символів; - двократна транскрипція. За результатами аналізу сформульованих ДМ було збудовано дихотомічне дерево, яке дозволяє виконувати операцію визначення виду в найгіршому випадку за час , у той час, коли діагностування за прямими ознаками знадобилося би .

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

(7)

де - ймовірність помилки у випадково вибраному серед атрибутів, що надійшли до методу діагностування; , - ймовірність помилки серед атрибутів, що складають посилку відповідно першого та другого правил; - ймовірність появи кортежу, у якому мають виконуватися як правило f₁, так й f₂; - ймовірність появи кортежу, у якому має виконуватися правило f₂, але не f₁ і т.д.

Рівняння (7) дозволило також створити евристику, за допомогою якої можна зменшити кількість правил у системі діагностування даних. Дійсно, неважко переконатися, що якщо для двох правил з однаковим висновком виконується умова H₁ H₂, то друге правило можна без втрати в ефективності системи вилучити з множини правил.

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

Основний зміст розділу опубліковано у роботах [2, 4, 5, 10-12].

У третьому розділі викладено суть нового методу злиття записів, затребуваність якого полягає у неможливості за умови застосування існуючих методів урахування поширеної ситуації, коли оператором використовуються скорочення та абревіатури. Як і в інших методах злиття записів, ключовими частинами запропонованого методу є пошук схожих рядків і пошук схожих кортежів. Для пошуку схожих рядків на основі вербального опису було таким чином формалізовано поняття скорочень та абревіатур: F(p,w)=S₂[p{,c₁z,..., c₁c₂...c_mz}], a=p₁…p_k, p_iF(p_i,w_i), де - пустий символ; с₁, …, с_m - змістові символи, що належать алфавіту _с, будь-який ланцюжок якого дозволяє сформувати слово; - позначення операції конкатенації двох ланцюжків; z -ланцюжок над алфавітом _del з довжиною, що дорівнює нулю або одиниці; _del - алфавіт символів-роздільників, що використовуються для розділення слів у словосполученнях; F(p,w) - предикат, що є істинним, у випадку коли рядок p є скороченням слова w= c₁c₂...c_m; а - абревіатура словосполучення, поданого рядком st=w₁z₁ w₂z₂…z_k-1w_k.

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

, (8)

де d_a(st₁, st₂) - відстань редагування абревіатур між рядками st₁ і st₂; л - деякий поріг схожості.

Тоді задачею пошуку схожих рядків буде пошук у деякому наборі рядків ST={st₁, st₂,...,st_n}, усіх пар рядків st₁, st₂ST, для яких виконується умова (8). Одним з очевидних, але неефективних, шляхів вирішення цієї задачі є підхід, у рамках якого потрібно виконати (n*(n-1))/2 обчислень відстані редагування абревіатур для всіх можливих пар рядків із ST. Замість такого вирішення в роботі запропоновано швидкий метод пошуку схожих за моделлю (8) рядків суть полягає у виконанні таких двох етапів.

На першому етапі усі рядки з ST відображаються в - мірний евклідів простір , з осями якого асоціюються , - к випадково вибраних рядків із ST, тобто кожному рядку st_iST ставиться у відповідність точка , координати якої дорівнюють простим відстаням Левенштейна до осей , де ' - позначення операції видалення з рядка усіх символів-роздільників.