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

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

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

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

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

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

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

TopSOM метод класифікації інформації заснований на поданні множини документів, що класифікуються, у вигляді двовимірної області (так званої “семантичної карти”), близькі точки якої (документи, що класифікуються) мають і близьке змістове значення.

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

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

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

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

Під системою документообігу будемо розуміти сукупність тематичних розділів Ci, i=1,…,n, структурованих певним чином, до яких можуть належати документи, що надходять. Належність даного документа D до певного тематичного розділу (класу) Ci позначатимемо: D Ci. Загалом, той самий документ може належати до декількох класів. Системою класифікації (класифікатором) будемо називати пристрій, що зараховує документ, який надходить на вхід системи, Dj (j=1, 2, …), до певного класу (класів) Ci. Ця система у своїй роботі повинна, очевидно, використати певну інформацію про документ Dj, на основі якої вона й приймає класифікаційне рішення. Така інформація в теорії розпізнавання називається вектором ознак образу. Як елемент такого вектора розглядатимемо факт входження (або не входження) до документа певного терміна (дескриптора) з множини V={v1, v2, …, vm}, яку назвемо тезаурусом або словником даних. Таким чином, під вектором ознак документа-образу будемо розуміти вектор x(j)={x1, x2, …, xm}(j), де

xk=

У теорії розпізнавання прийнято як систему класифікації розглядати систему розв'язувальних функцій di, i=1,…,n... Для таких функцій приймається рішення про зарахування образа x(j) до класу Ci, якщо di(x(j))dl(x(j)) для будь-якого l=1,…,n, li....

У процесі роботи системи класифікації можливі дві ситуації. Перша, коли система зараховує образ x(j), що дійсно належить до класу Ci, до цього класу. Таку ситуацію будемо називати успіхом (правильною класифікацією). Протилежний випадок, коли документ із вектором ознак x(j), що насправді належить до класу Ci, зараховується системою до класу Cp, pi, будемо називати помилкою класифікації (неуспіхом). Очевидно, що серед множини всіх класифікаторів нас цікавлять саме ті, які менше помиляються. Існують кілька підходів до побудови подібних критеріїв якості класифікації. У статистичній теорії розпізнавання найвідомішим є критерій, що називається байєсівським класифікатором, заснованим на мінімізації середніх втрат при використанні системи класифікації. Під втратою розуміється програш гравця - системи класифікації - у грі з нульовою сумою проти іншого гравця - природи, що поставляє образи на вхід системи класифікації. Вважатимемо, що природа в цій грі обирає стратегію Ci, коли на вхід системи розпізнавання видається документ DCi. Імовірність вибору цієї стратегії позначимо через P(Ci). Стратегією системи розпізнавання буде зазначення класу Cl, до якого вона зараховує даний документ. Зазначена гра характеризуватиметься матрицею втрат Lil. Припустимо, що природа видає образи незалежно один від іншого, керуючись імовірностями P(Ci). Тоді математичне очікування втрат, пов'язаних із зарахуванням системою образу x(j) до класу Cl, визначиться за формулою

rl(x(j))= ,

де P(Ci|x(j)) - умовна ймовірність появи класу Ci, коли на вхід системи був поданий образ x(j).

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

Lil=1-il ,

де il - символи Кронекера.

Для матриці втрат (3) байєсівське класифікаційне правило буде визначатися набором вирішальних функцій вигляду

di(x(j))= P(x(j)|Ci)P(Ci),

де P(x(j)|Ci) - імовірність появи образу x(j), коли випав клас Ci.

Одержання оцінок для величини P(x(j)|Ci) є основою для побудови класифікаційних розв'язувальних функцій di(x(j)), які обумовлені формулою (4) і реалізують байєсівське класифікаційне правило в припущенні про взаємну незалежність появи різних термінів зі словника даних у документі, що класифікується, а також формулювання методів класифікації на основі даного правила. Для одержання зазначеної вище оцінки в дисертаційній роботі доведено теорему 2.

У припущенні незалежності компонент випадкового вектора x(j)={x1,x2,…,xm}(j), умовна ймовірність

P(x(j)|Ci)= , де ik=

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

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

Метод 1. Метод одиничної класифікації документів в інформаційно-пошукових системах.

Випадок взаємної незалежності появи термінів у документі.

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

2. На основі цієї інформації обчислюються величини:

та для кожного i=1,...,n обчислюються значення розв'язувальних функцій:

(x)= , де =

де - число документів, зарахованих до класу Ci, у яких зустрічається термін vk;;

- загальне число документів, зарахованих до класу Ci.

= ;

= ,

= .

Використовуючи оцінки (15) - (17) і роблячи певні припущення про закон розподілу коефіцієнтів довіри, розглянутих як випадкові величини, можна одержати оцінки довірчих інтервалів для цих параметрів.

Для реалізації розроблених методів у рамках реляційної моделі передбачається використання спеціальної схеми зберігання даних. Оскільки кількість термінів, які можуть зустрітися в документі, що належить до кожного з класів, обмежена (як правило, воно набагато менше розміру словника даних), вибірка інформації з таблиці “Документ-термін” для добування інформації про входження терміна до заданого документа може ефективно реалізовуватися ядром СУБД.

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

Метод 3. Метод вибору крітерію якості класифікації.

Для вирішення завдання вибору найкращого алгоритму класифікації варто задатися якимось критерієм ефективності алгоритму. Як відзначалося вище, “якість” системи класифікації в загальному випадку визначається не одним, а відразу декількома параметрами. Найважливішими з них є кількість помилок у результаті класифікації, час роботи алгоритму, потреба в оперативній і дисковій пам'яті й інші параметри. Нехай q1, q2, …, qs - параметри, що визначають у загальному випадку якість системи класифікації. Тоді критерієм якості буде функція:

Q=Q(q1, q2, …, qs).

Вибір функції (18) дозволяє гнучко регулювати показники якості роботи алгоритмів. У нашому випадку задамося найпростішим вибором функції Q - лінійної. А саме, нехай q1 - кількість помилок алгоритму в процесі класифікації, а q2 - час виконання розрахунків у даному алгоритмі. Тоді функцію критерію будемо розглядати у вигляді:

Q(q1, q2)=K1q1+K2q2,

де K1 і K2 - вагові коефіцієнти. Ці коефіцієнти дозволяють регулювати пріоритети: якщо нас цікавить поліпшена якість роботи алгоритму й при цьому менше цікавить необхідний час розрахунку, то треба збільшити K1 у порівнянні з K2, і навпаки. Крім того, відповідний вибір величин вагових коефіцієнтів дає можливість зробити розмірними (величинами одного порядку) доданки у формулі (19).

Параметр, що характеризує розмір оперативної й дискової пам'яті обчислювальної системи, на якій реалізується алгоритм, не був уключений до складу критеріальної функції (19), оскільки корелює з параметром необхідного часу обчислень q2. Відзначимо, що вибір лінійної функції як критерію, безумовно, не єдиний з практично можливих. Для якісної оцінки інших показників алгоритму доцільно використати інші форми критерію (18). На рис. 1 представлені результати оцінки якості методу 1 (r=1) та методу 3 (r=2, r=3, r=4) залежно від числа самостійно розпізнаних системою документів. програмний забезпечення автоматизований пошуковий

На осі ординат відкладено значення критерію Q, обраного відповідно до формули (19). Коефіцієнти K1 і K2 підібрано з тим наміром, щоб параметри якості й часу q1 і q2 давали приблизно однаковий внесок до значення функції критерію Q. З рис. 1 видно, що методи, які враховують взаємну залежність появи термінів у документі для невеликих вибірок документів, мають значно кращі показники якості в порівнянні з методом 1

для метода 3 (r=1, r=2, r=3, r=4) залежно від числа самостійно розпізнаних системою документів

При подальшому збільшенні вибірки величина Q для всіх алгоритмів збільшується, Однак швидше за все цей показник зростає для алгоритмів, що враховують найбільшу кількість взаємозалежних термінів. Для методу з r = 4 за досить великої вибірки якість стає гірше, ніж у методі з r = 2, тобто використовувані обчислювальні витрати не є достатніми для реалізації розроблених алгоритмів такої складності. Відповідно до рис. 1 оптимальним за якістю для даного набору вагових коефіцієнтів K1 і K2 є метод 3 для r = 3.

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

Розглянемо принципи роботи даної системи згідно з наведеною моделлю. Документи надходять до електронної поштової скриньки митної служби як текстові файли різних типів (txt, doc, html тощо). Отриманий файл обробляється конвертером тексту. На виході конвертера одержуємо чистий текст, що задовольняє вимогам системи. Потім чистий текст надходить до граматичного аналізатора тексту. Тут відбувається формування всього списку термінів, що входять до даного документа.

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

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

Розроблені в попередніх розділах роботи методи й алгоритми класифікації документів було реалізовано як програмні модулі автоматизованої ІПС. Апробація цих модулів проводилася в ЄАІС митної служби України. Першим етапом реалізації є розробка програмного модуля для організації обробки й зберігання документів у відділі по боротьбі з контрабандою й порушеннями митних правил Дніпровської регіональної митниці. Реалізація даного програмного продукту істотно оптимізувала й спростила обробку текстової документації даного відділу. Другий етап - це розробка й упровадження програмних модулів класифікації документів ЄАІС.

ВИСНОВКИ

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

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

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

3. Уперше розроблено метод множинної класифікації текстових документів в інформаційно-пошукових системах, заснований на ймовірностях появи в документах груп термінів зі словника даних, які складаються з двох або більше термінів, що дає можливість отримувати похибки класифікації належного рівня та підвищити якість класифікації. Розроблений метод класифікації відрізняється від існуючих адаптованістю, можливістю варіювання параметрів таких, як кількість термінів у документі й урахування їх одночасної появи. Запропонований метод має можливість регулювання сукупного параметра “якість класифікації” й гарну пристосованість до практичної реалізації на сучасних реляційних СУБД.

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

5. Розроблено метод формалізованого опису коефіцієнта довіри, завдяки якому з'явилась можливість зарахувати документ, що надходить до системи, як до одного, так і до декількох класів і використовувати у методі множинної класифікації, що підвищує якість класифікації документів.

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

7. Отримані результати впроваджено як елемент ЄАІС митної служби України, що дозволило істотно підвищити якість функціонування інформаційно-пошукової системи ЄАІС митної служби України завдяки розвитку існуючих та розробці нових методів класифікації текстових документів, які забезпечують скорочення часу, зменшення обсягів щодо підготовки та пошуку даних в інформаційно-пошукових системах, про що свідчить акт впровадження Управління інформаційного забезпечення та митної статистики державної митної служби України (акт упровадження від 14.06.2004). Отримані результати впроваджено у вигляді програмного модуля для організації обробки й зберігання документів у відділі по боротьбі з контрабандою й порушеннями митних правил Дніпровської регіональної митниці (акт упровадження від 21.09.2000). Теоретичні результати дисертаційної роботи у вигляді моделей подання знань і методів обробки інформації впроваджені в навчальний процес Академії митної служби України на кафедрі інформаційних систем і технологій у дисципліні “Організація баз даних і знань” і використовуються в курсовому й дипломному проектуванні (акт упровадження від 25.10.2005 ).

ПУБЛІКАЦІЇ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Кабак Л.В. Методы классификации документов, учитывающие одновременное появление групп терминов в документе// АСУ и приборы автоматики. - Харьков: ХНУРЭ, 2005. - Вып. 130. - С. 74-81.

2. Мороз Б.И., Кабак Л.В., Трофимов О.В. Методы оценки эффективности систем классификации текстовых документов в автоматизированных информа-ционно-поисковых системах // Системные технологии. Региональный межвузовский сборник научных работ. - Днепропетровск, 2005. - Вып. 1 (11). - С. 56-62.

3. Кабак Л.В. Методы повышения эффективности информационно-поиско-вых систем таможенной службы // Системні технології. Регіональний міжвузівський збірник наукових праць. - Дніпропетровськ, 2005. - Вип. 2 (37). - С. 64-73.

4. Мороз Б.І., Кабак Л.В., Літвінов В.М., Дюбко В.П. Організація обробки одного класу спеціалізованої митної інформації // Вісник Академії митної служби України. - 2001. - № 2. - С. 105-112.

5. Мороз Б.І., Кабак Л.В., Дюбко В.П. Раціональна організація документопотоку в митній службі України // Вісник Академії митної служби України. - 2003. - № 2 - C. 43-48.

6. Мороз Б.І., Кабак Л.В., Дюбко В.П. Деякі аспекти та проблеми використання СУБД ORACLE 8 в Єдиній автоматизованій системі управління Держмитслужби України // Тези доповідей науково-практичної конференції “Митна справа в Україні: сучасні проблеми та шляхи вдосконалення”. - Дніпропетровськ: АМСУ, 1999. - С. 56-60.

7. Трофімов О.В., Кабак Л.В., Рижанкова Г.І. Методи класифікації документів у системі документообігу // Тези науково-методичної конференції “Митна політика України в контексті європейського вибору: проблеми та шляхи їх вирішення”. - Дніпропетровськ: АМСУ, 2003. - С. 184-185.

8. Кабак Л.В. Оптимізаційний підхід до створення автоматизованої системи документообігу // Материалы 8-го Международного молодежного форума “Радиоэлектроника и молодежь в ХХІ веке”. - Харьков: ХНУРЭ, 2004. - С. 36.

9. Трофімов О.В., Кабак Л.В., Рижанкова Г.І. Статистичні алгоритми автоматичної класифікації текстових документів у системах документообігу// Тези доповідей науково-методичної конференції “Актуальні проблеми підготовки фахівців з митної справи”. - Дніпропетровськ: АМСУ, 2005. - С. 174-176.

10. Кабак Л.В. Инструментальные средства повышения производительности ИПС // Материалы 2-го Международного радиоэлектронного форума “Прикладная радиоэлектроника. Состояние и перспективы развития” МРФ-2005. - Харьков: ХНУРЭ, 2005. - С. 16-18.

АНОТАЦІЯ

Кабак Леонід Виталійович. Методи та моделі класифікації текстових документів в спеціалізованих інформаційно-пошукових системах. - Рукопис.

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

Дисертація присвячена розробці сучасних методів класифікації, які можна застосовувати під час обробки великих масивів текстової документації в системі документообігу Єдиної автоматизованої інформаційної системи (ЄАІС) митної служби України. Одним з актуальних для митної служби України є питання класифікації документів, які надходять до бази даних автоматизованої інформаційно-пошукової системи (АІПС), за допомогою поштового сервера внутрішньої митної мережі INTRANET. У дисертаційній роботі пропонуються методи автоматизованої класифікації документів, які враховують відносну частоту появи певних термінів зі словника даних (глосарія) у документах, які належать до різних тематичних розділів, а також взаємну залежність появи різних термінів у документах певного класу.

Ключові слова: автоматизована інформаційно-пошукова система, розв'язувальні функції, система класифікації, інформаційна модель.