Моделі та методи класифікації текстових документів в спеціалізованих інформаційно-пошукових системах
Принципи створення електронного документообігу. Розробка системи автоматизованої класифікації документів управління митної служби України. Вивчення алгоритмів роботи глобальних комп’ютерних мереж. Апробація і реалізація інформаційно-пошукових програм.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | автореферат |
| Язык | украинский |
| Дата добавления | 27.08.2014 |
| Размер файла | 892,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://allbest.ru
Харківський національний університет радіоелектроніки
УДК 658.012.011.56 681.012
Автореферат
дисертації на здобуття наукового ступеня
кандидата технічних наук
МОДЕЛІ ТА МЕТОДИ КЛАСИФІКАЦІЇ ТЕКСТОВИХ ДОКУМЕНТІВ В СПЕЦІАЛІЗОВАНИХ ІНФОРМАЦІЙНО-ПОШУКОВИХ СИСТЕМАХ
05.13.06 - автоматизовані системи управління та прогресивні інформаційні технології
Кабак Леонід Віталійович
Харків - 2006
Дисертацією є рукопис.
Робота виконана в Академії митної служби України, Державна митна служба України.
Науковий керівник - доктор технічних наук, професор Мороз Борис Іванович, Академія митної служби України, начальник факультету організації та технології митного контролю, начальник кафедри інформаційних систем та технологій.
Офіційні опоненти: доктор технічних наук, професор Авраменко Валерій Павлович, Харківський національний університет радіоелектроніки, м. Харків, професор кафедри інформаційних управляючих систем;
кандидат технічних наук, Гнатушенко Володимир Володимирович, Дніпропетровський національний університет, м. Дніпропетровськ, доцент кафедри електронних засобів телекомунікацій.
Провідна установа - Національний аерокосмічний університет ім. М.Є. Жуковського “Харківський авіаційний інститут”, кафедра інформаційних управляючих систем, м. Харків.
Захист відбудеться “14”червня 2006 р. о ___ годині на засіданні спеціалізованої вченої ради Д 64.052.01 у Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14, тел.: (057) 702-14-51.
З дисертацією можна ознайомитися у бібліотеці Харківського національного університету радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.
Автореферат розіслано “13”травня 2006 р.
Вчений секретар
спеціалізованої вченої ради С.Ф. Чалий
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Становлення й розвиток ринкових відносин в Україні приводить до неухильного збільшення кількості документів, які проходять через митну службу, що ставить проблему їх своєчасної та якісної обробки. Система документообігу, яка існує нині як частина Єдиної автоматизованої інформаційної системи митної служби України (ЄАІС), заснована на базі поштового сервера й автоматизована лише частково. Існуючі в системі управління митної служби України методи організації баз даних великих масивів документів не повною мірою задовольняють постійно зростаючі потреби. Розвиток індустрії систем електронного документообігу, що супроводжується ростом масивів оброблюваних повнотекстових документів, потребує розробки нових методів організації баз даних великих масивів текстових документів. З огляду на великий обсяг документів, які надходять, доцільно організувати процес автоматизованої класифікації.
Нині спостерігається помітне зростання інтересу до методів класифікації й змістового пошуку необхідного документа з великої кількості документів. На сервері бази даних накопичуються величезні масиви документів і на пошук необхідного документа, як правило, співробітники Державної митної служби України витрачають дуже велику кількість часу. Для вирішення цієї проблеми необхідно розробити систему автоматизованої класифікації документів, що буде враховувати особливості документообігу в митній службі й специфіку інформаційної системи, яка використовується в митних органах.
На даний момент розроблено багато методик, орієнтованих на класифікацію й пошук необхідного документу у великих масивах документів. Однак більшість подібних алгоритмів орієнтовано в основному на роботу в пошукових системах глобальних комп'ютерних мереж. У таких пошукових системах користувач задає один або кілька термінів, за якими програма видає йому сукупність документів або рубрик документів, з яких користувач потім вибирає необхідну інформацію. Інше завдання постає перед автоматизованими системами класифікації, коли необхідно за обмеженої участі користувача забезпечити прийнятну якість класифікації великого потоку документів.
Одним з можливих варіантів вирішення цієї проблеми є розробка нового методу класифікації, який істотно підвищить швидкість обробки інформації, якість класифікації, буде досить гнучким і зручним у вивченні.
Розробка методів класифікації є перспективним напрямком дослідження. Інтенсивний розвиток цього напряму відзначається в останні двадцять років з появою сучасних серверів, які дозволяють накопичувати й обробляти більші масиви документів, що конче потрібно при переході багатьох організацій на систему електронного документообігу. Класичними роботами з проектування й розробки принципів створення сучасних систем класифікації є роботи О.Є. Єрмакова і В.В. Плешка, І.І. Попова, І.А. Мельчука, Дж. Солтона, І.Є. Кураленка та І.С. Некрестьянова, Ю.О. Шрейдера, T. Kohonen. S. Kaski, K. Lagus, van Rijsbergen та інших авторів. Розвиток ідей, закладених у цих роботах, знайшов своє відбиття в ряді досліджень, що вивчають проблеми організації баз даних великих масивів документів, моделей і методів сучасних класифікаторів. Проведений аналіз робіт у даному напрямку дозволяє зробити висновок, що розробка сучасних методів класифікації нині дуже актуальна.
Зв'язок роботи з науковими програмами, планами, темами.
Дисертацію виконано на кафедрі інформаційних систем та технологій Академії митної служби України в рамках держбюджетної науково-дослідної роботи кафедри “Дослідження й розробка методів і засобів обробки інформації в автоматизованих системах митної служби України з урахуванням якісно-кількісних характеристик інформації” (№ держреєстрації 0104U008458).
Мета й завдання дослідження. Метою дисертаційної роботи є підвищення ефективності та якості пошуку текстових документів в інформаційно-пошуковій системі (ІПС) Єдиної автоматизованої інформаційної системи митної служби України, завдяки розвитку існуючих та розробці нових методів класифікації текстових документів.
Для досягнення поставленої мети в роботі вирішуються такі завдання:
- дослідження існуючих методів класифікації;
- розробка й дослідження сучасних методів класифікації, які будуть враховуватимуть можливості сучасного обладнання й програмного забезпечення;
- програмна реалізація отриманих результатів;
- апробація розроблених програм.
Об'єкт дослідження - процес класифікації текстових документів в інформаційно-пошукових системах.
Предмет дослідження - моделі й інструментальні засоби підвищення ефективності функціонування інформаційно-пошукових систем.
Методи дослідження - методи теорії ймовірності, методи теорії ігор, методи адаптивної класифікації текстових документів.
Наукова новизна одержаних результатів.
1. Уперше розроблено новий метод множинної класифікації текстових документів в інформаційно-пошукових системах, який відрізняється від існуючих урахуванням імовірності появи визначених груп термінів у документі, що класифікується, та введенням коефіцієнта довіри класифікації, метод дозволяє зарахувати документ як до одного, так і до декількох класів і таким чином підвищити якість класифікації.
2. Набув подальшого розвитку метод вибору критерію якості класифікації, що за допомогою введення вагових коефіцієнтів, дає можливість регулювати значення сукупного параметра “якість класифікації - витрати обчислювальних ресурсів”, що дозволяє ефективно використовувати обчислювальні ресурси системи автоматичної класифікації документів з урахуванням витрат.
3. Набув подальшого розвитку метод одиничної класифікації текстових документів в інформаційно-пошукових системах, заснований на ймовірності входження певного терміна в документ заздалегідь визначеного класу, що дозволило автоматизувати класифікацію документів, які надходять до системи, з певною гнучкістю та простотою настроювання параметрів класифікації.
4. Набула подальшого розвитку модель системи класифікації текстових документів, яка базується на розроблених методах класифікації текстових документів та запропонованому критерію якості класифікації, що дає можливість отримувати похибки класифікації належного рівня з прийнятною витратою обчислювальних ресурсів системи.
Практичне значення одержаних результатів. На основі проведених досліджень:
- розроблено засоби (алгоритм і програмна реалізація) вирішення завдання автоматичної класифікації текстових документів для автоматизованих інформаційно-пошукових систем;
- розроблено засоби (алгоритм і програмна реалізація), які дозволяють характеризувати класифікацію за критерієм “якість класифікації - витрати обчислювальних ресурсів”, що робить можливим, регулюючи відповідні параметри алгоритмів класифікації, домагатися оптимального співвідношення між якістю класифікації й продуктивністю обчислювальної системи;
- розроблено метод, що робить можливим оптимально використати здатності сервера БД Oracle з метою підвищення продуктивності при автоматизованій класифікації, пошуку й обробці великих масивів текстових документів.
Результатом даної роботи є методи класифікації. За допомогою цих методів розроблено програмне забезпечення, що використовується в митній службі України для автоматизованої класифікації документів. Програмне забезпечення було розроблено й упроваджено як елемент ЄАІС митної служби України, що дозволило істотно підвищити продуктивність сервера документів і якість їх класифікації, про що свідчить акт упровадження. Розроблені методи також було випробувано під час розробки програмного забезпечення у відділі по боротьбі з контрабандою й порушеннями митних правил Дніпровської регіональної митниці. У результаті впровадження скоротився час, необхідний для пошуку й контролю документів, що проходять через даний відділ, про що свідчить акт упровадження. За результатами апробації можна зробити висновок, що порівняльна алгоритмічна простота розглянутих методів дає можливість використати їх у складі комбінованих систем аналізу й класифікації документів, які використовують складніші принципи класифікації. Отримані результати можуть бути затребувані в різних галузях промисловості, де необхідна обробка великих масивів документів.
Особистий внесок здобувача. У роботах [1, 9, 10] набув подальший розвиток метод вибору критерію якості класифікації, який завдяки введенню вагових коефіцієнтів, дозволяє регулювати параметри “якість класифікації - витрати обчислювальних ресурсів”, що дозволило підвищити ефективність системи автоматизованої класифікації текстових документів. Отримано оцінки числа арифметичних операцій при використанні кожного методу. У роботі [2] проаналізовано методи класифікації, що існують, та набув подальшого розвитку новий метод одиничної класифікації текстових документів. Метод одиничної класифікації засновано на ймовірності входження певного терміна в документ заздалегідь визначеного класу, що уможливлює зробити автоматизовану класифікацію документів, які надходять до системи; розглянуто питання раціональної організації структури реляційної бази даних для ефективної реалізації методу. У роботах [3, 7, 8] розроблено новий метод множинної класифікації, що враховує ймовірність появи певних груп термінів в документі, який класифікується, що дозволило підвищити якість класифікації. Розроблений метод дозволяє зарахувати документ, що надходить до системи, як до одного, так і до декількох класів. У роботах [4, 5, 6] автором проаналізовано документообіг Дніпропетровської регіональної митниці, розроблено автоматизовану інформаційно-пошукову систему та модель системи класифікації для збереження, обробки та пошуку інформації.
Апробація результатів дисертації. Основні результати дисертаційної роботи доповідалися й обговорювалися: на науково-методичній конференції “Актуальні проблеми підготовки фахівців з митної справи” (м. Дніпропетровськ, 2000 та 2001 рр.), науково-методичній конференції “Митна політика України в контексті Європейського вибору: проблеми та шляхи їх вирішення” (м. Дніпропетровськ, 2003 р.), 8-му Міжнародному молодіжному форумі “Радіоелектроніка і молодь у ХХІ столітті” (м. Харків, 2004 р.); 2-му Міжнародному радіоелектронному форумі “Прикладная радиоэлектроника. Состояние и перспективы развития” МРФ - 2005 (м. Харків, 2005 р.).
Публікації. Результати наукових досліджень опубліковані в 10 друкованих працях, з них 5 статей у збірниках наукових праць, що входять до переліків ВАК України, а також 5 робіт у матеріалах всеукраїнських і міжнародних конференцій.
Структура дисертації. Дисертація складається із вступу, 4 розділів, висновків, списку використаних джерел, що включає 122 найменування, 3 додатка. Обсяг дисертації - 122 сторінки.
ОСНОВНИЙ ЗМІСТ РОБОТИ
У вступі відзначено актуальність дисертаційної роботи, сформульовано мету й завдання дослідження. Дано коротку анотацію одержаних у дисертації результатів, визначено їх наукову новизну й практичне значення. Показано особистий внесок здобувача, наведено дані про публікації та апробації за темою роботи, про впровадження результатів проведених досліджень.
У першому розділі виконано аналіз існуючих методів і систем класифікації. Виділено для подальшого дослідження завдання розробки методу класифікації з урахуванням швидкодії і якості. Проведено огляд літературних джерел для певного класу завдань, показано сучасний стан проблеми. Виконано постановку завдання.
У практичній роботі корпорацій, урядових організацій тощо істотною проблемою є обробка різноманітної інформації, пов'язаної з поточною діяльністю підприємства. Інформація ця як циркулює усередині організації, так і надходить ззовні (від інших підприємств і організацій, маркетингових служб і т. п.). З цієї точки зору, не є винятком організації митної служби України, яким за родом діяльності доводиться мати справу з обробкою великих потоків нормативної, правової, службової й іншої різноманітної інформації.
У зв'язку з цим особливої актуальності набувають питання автоматизованої (за мінімальної участі користувача) системи класифікації інформації, що надходить до організації.
Нині розроблено досить велику кількість методів автоматизованої класифікації інформації. Переважну більшість таких методів орієнтовано на системи автоматизованого пошуку інформації в мережі Інтернет. Найбільш уживані алгоритми класифікації текстових документів використовують три основних підходи.
Асоціативно-статистичний підхід ураховує кореляційний зв'язок появи різних термінів зі словника в документах певного класу, а також відносну частоту, з якою з'являється той чи інший термін у документах цього класу.
Синтактико-семантичний підхід передбачає аналіз речень документа з метою виділення в них певної синтаксичної структури, аналізуючи яку можна зробити висновок про зміст документа, отже, й класифікувати його.
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= (1)
Таким чином, завдання полягає в побудові системи класифікації, яка буде на основі цієї інформації, а також рішень про розпізнавання попередніх j-1 документів, що до прийняття рішення, до якого з класів Ci зарахувати заданий документ.
У теорії розпізнавання прийнято як систему класифікації розглядати систему розв'язувальних функцій 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))= ,(2)
де P(Ci|x(j)) - умовна ймовірність появи класу Ci, коли на вхід системи був поданий образ x(j).
Байєсівським називається класифікаційне правило, яке мінімізує величину (2). У більшості випадків природно припустити, що втрати при правильній класифікації дорівнюють нулю, а в противному разі дорівнюють одиниці, тобто
Lil=1-il ,(3)
де il - символи Кронекера.
Теорема 1.
Для матриці втрат (3) байєсівське класифікаційне правило буде визначатися набором вирішальних функцій вигляду
di(x(j))= P(x(j)|Ci)P(Ci),(4)
де P(x(j)|Ci) - імовірність появи образу x(j), коли випав клас Ci.
Одержання оцінок для величини P(x(j)|Ci) є основою для побудови класифікаційних розв'язувальних функцій di(x(j)), які обумовлені формулою (4) і реалізують байєсівське класифікаційне правило в припущенні про взаємну незалежність появи різних термінів зі словника даних у документі, що класифікується, а також формулювання методів класифікації на основі даного правила. Для одержання зазначеної вище оцінки в дисертаційній роботі доведено теорему 2.
Теорема 2.
У припущенні незалежності компонент випадкового вектора x(j)={x1,x2,…,xm}(j), умовна ймовірність
P(x(j)|Ci)= , де ik=(5)
де pik - імовірність появи k-го терміна зі словника в документі, що належить до класу Ci.
На базі отриманих результатів були розроблені такі методи.
Метод 1. Метод одиничної класифікації документів в інформаційно-пошукових системах.
Випадок взаємної незалежності появи термінів у документі.
1.Для перших j-1 документів здійснюється навчання системи класифікації, тобто для кожного документа вказується клас, до якого він належить.
2.На основі цієї інформації обчислюються величини:
=, = (6)
та для кожного i=1,...,n обчислюються значення розв'язувальних функцій:
(x)= , де =(7)
де - число документів, зарахованих до класу Ci, у яких зустрічається термін vk;;
- загальне число документів, зарахованих до класу Ci.
3.Рішення про віднесення j-го документа до класу Ci приймається, якщо (x(j)) (x(j)) для будь-якого li.
Метод 2. Метод множинної класифікації документів в інформаційно-пошукових системах.
Метод враховує ймовірність появи певних груп термінів у документі і дозволяє відносити текстовий документ до декількох класів.
Припускаємо залежною одночасну появу груп термінів числом, меншим або рівним r, і незалежною появу груп термінів числом, більшим r.
P(xk=bk| = , = , … , =, xCi) ? P(x(j)=b|Ci),
P(xk= bk| = , = , … , =, xCi) = PCi(xk=bk), (8)
bk{0;1}k,lp=1,2, … m, k?lp, p=1, … , r ....
1. Для перших j-1 документів здійснюється навчання системи класифікації, тобто для кожного документа вказується клас, до якого він належить.
2. На підставі цієї інформації для кожного i=1,…,n обчислюються значення розв'язувальних функцій (x) за формулами:
(x)= ,(9)
=(10)
=(11)
(12)
- число перестановок з m елементів по r.
Рішення про належність j-го документа до класу Ci приймається, якщо (x(j)) (x(j)) для будь-якого li.
3. Для кожного i обчислюються значення розв'язувальних функцій (x(j)), i=1,…,n...
4. Для кожного класу задається певне значення .
5. Рішення про належність образа x(j) до класу Ci приймається, якщо виконується нерівність:
(x(j))?.(13)
Вибір залежить від бажаного рівня довіри класифікації документів. Можна порекомендувати вибір у вигляді:
= max ( (x(j))),(14)
де -коефіцієнт довіри класифікації, що змінюється в межах
0<?1.
Слід зазначити, що вибір коефіцієнта довіри може змінюватися від одного документа до іншого.
Його вибір може бути зроблено на основі статистичних даних про результати класифікації попередніх j-1 документів.
Зокрема, середнє значення коефіцієнта довіри для кожного класу, а також його дисперсія, можуть бути оцінені за формулами:
= ;(15)
= ,(16)
= . (17)
Використовуючи оцінки (15) - (17) і роблячи певні припущення про закон розподілу коефіцієнтів довіри, розглянутих як випадкові величини, можна одержати оцінки довірчих інтервалів для цих параметрів.
Для реалізації розроблених методів у рамках реляційної моделі передбачається використання спеціальної схеми зберігання даних. Оскільки кількість термінів, які можуть зустрітися в документі, що належить до кожного з класів, обмежена (як правило, воно набагато менше розміру словника даних), вибірка інформації з таблиці “Документ-термін” для добування інформації про входження терміна до заданого документа може ефективно реалізовуватися ядром СУБД.
Третій розділ присвячено розробці основних алгоритмів класифікації. У цьому розділі зроблено дослідження і практичну перевірку розроблених алгоритмів класифікації документів, у результаті якої визначено розмір навчальної вибірки, зроблено порівняльну оцінку алгоритмів одиничної й множинної класифікації, а також аналіз ефективності викладених алгоритмів з погляду різних критеріїв оптимальності.
У розглянутих вище методах класифікації істотним є ще один параметр - якість класифікації.
Цей параметр здобуває особливу важливість, коли ставиться завдання: якщо можна, найточніше класифікувати документи без втручання користувача, який вносить зміни до результатів класифікації.
Задачею розроблювача при виборі методики класифікації є вибір методу, що забезпечує максимально можливу точність класифікації при витраті прийнятної кількості оперативної пам'яті й часу роботи центрального процесора системи, що класифікує. Для вирішення цього завдання було удосконалено метод вибору крітерію якості класифікації.
Метод 3. Метод вибору крітерію якості класифікації.
Для вирішення завдання вибору найкращого алгоритму класифікації варто задатися якимось критерієм ефективності алгоритму. Як відзначалося вище, “якість” системи класифікації в загальному випадку визначається не одним, а відразу декількома параметрами.
Найважливішими з них є кількість помилок у результаті класифікації, час роботи алгоритму, потреба в оперативній і дисковій пам'яті й інші параметри.
Нехай q1, q2, …, qs - параметри, що визначають у загальному випадку якість системи класифікації. Тоді критерієм якості буде функція:
Q=Q(q1, q2, …, qs).(18)
Вибір функції (18) дозволяє гнучко регулювати показники якості роботи алгоритмів. У нашому випадку задамося найпростішим вибором функції Q - лінійної. А саме, нехай q1 - кількість помилок алгоритму в процесі класифікації, а q2 - час виконання розрахунків у даному алгоритмі. Тоді функцію критерію будемо розглядати у вигляді:
Q(q1, q2)=K1q1+K2q2,(19)
де 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.
Рис. 1. Графіки значення критерія Q класифікованих документів для метода 3 (r=1, r=2, r=3, r=4) залежно від числа самостійно розпізнаних системою документів
При подальшому збільшенні вибірки величина Q для всіх алгоритмів збільшується, Однак швидше за все цей показник зростає для алгоритмів, що враховують найбільшу кількість взаємозалежних термінів. Для методу з r = 4 за досить великої вибірки якість стає гірше, ніж у методі з r = 2, тобто використовувані обчислювальні витрати не є достатніми для реалізації розроблених алгоритмів такої складності. Відповідно до рис. 1 оптимальним за якістю для даного набору вагових коефіцієнтів K1 і K2 є метод 3 для r = 3.
У четвертому розділі розглянуто практичну реалізацію розроблених методів класифікації в підрозділах митної служби України та удосконалена модель системи класифікації яка зображена на рис. 2.
Розглянемо принципи роботи даної системи згідно з наведеною моделлю. Документи надходять до електронної поштової скриньки митної служби як текстові файли різних типів (txt, doc, html тощо). Отриманий файл обробляється конвертером тексту. На виході конвертера одержуємо чистий текст, що задовольняє вимогам системи. Потім чистий текст надходить до граматичного аналізатора тексту. Тут відбувається формування всього списку термінів, що входять до даного документа.
Однією з основних складових частин системи є блок управління системою класифікації документів. У цьому блоці адміністратор може визначити, які слова з отриманого списку термінів, що містяться в документі, вже занесені до БД, якщо вони раніше зустрічалися, а які не занесені. Крім того, за необхідності виконується відновлення бази незначущих термінів, які знайдено в даному документі. Якщо в тексті виявляються значущі слова й словосполучення, не занесені до БД, то адміністраторові БД пропонується їх занести. У цьому блоці здійснюється “ручна” класифікація документів, а також виправлення помилок класифікації, тобто навчання системи.
Рис. 2 Модель системи класифікації
Наступна складова частина системи - блок безпосередньої класифікації. У цьому блоці для значущих термінів (і їх сполучень), що входять до документа, визначається відносна частота, з якою вони зустрічаються в документах кожного тематичного розділу. Визначаються також інші параметри, необхідні для обчислення вирішальних функцій, що класифікують. Результатом роботи блоку буде відновлення таблиці “Документ-клас”, тобто збереження в БД прийнятого рішення про класифікацію документа. Окремим блоком системи класифікації є блок настроювання параметрів класифікації системи. Ця частина системи дозволяє адміністраторові задавати тип методу класифікації, що використовується в системі. У цьому блоці адміністратор може також переглянути статистику, що характеризує параметри роботи системи класифікації, а також задавати вагові коефіцієнти для функції критерію класифікації, що задається формулою (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. У дисертаційній роботі пропонуються методи автоматизованої класифікації документів, які враховують відносну частоту появи певних термінів зі словника даних (глосарія) у документах, які належать до різних тематичних розділів, а також взаємну залежність появи різних термінів у документах певного класу.
Ключові слова: автоматизована інформаційно-пошукова система, розв'язувальні функції, система класифікації, інформаційна модель.
АННОТАЦИЯ
Кабак Леонид Витальевич. Методы и модели классификации текстовых документов в специализированных информационно-поисковых системах. - Рукопись.
Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 - автоматизированные системы управления и прогрессивные информационные технологии. - Харьковский национальный университет радиоэлектроники, Харьков, 2006.
Диссертация посвящена разработке современных методов классификации, которые можно применять при обработке больших массивов текстовой документации в системе документооборота Единой автоматизированной информационной системы (ЕАИС) таможенной службы Украины.
Одним из актуальных для таможенной службы Украины является вопрос классификации документов, поступающих в базу данных автоматизированной информационно-поисковой системы (АИПС), с помощью почтового сервера внутренней таможенной сети INTRANET. В диссертационной работе предлагаются методы автоматизированной классификации документов, учитывающие относительную частоту встречаемости определенных терминов из словаря данных (глоссария) в документах, принадлежащих к различным тематическим разделам, а также взаимную зависимость появления различных терминов в документах определенного класса.
В соответствии с этим проведен анализ методов классификации, применяющихся в АИПС. В результате проведенного анализа произведена постановка задачи и определены основные требования для разработки методов классификации документов.
Выполнена формализация задачи классификации документов в АИПС. Основной информацией для классификации является значение случайного вектора, характеризующего вхождение в текущий документ терминов из словаря данных. Получены выражения для условных вероятностей случая, когда в документ данного класса входит определенный набор терминов из словаря данных.
Указанные выражения получены в предположениях о взаимной независимости появления различных терминов в документе, а также взаимной независимости появления всевозможных пар терминов, троек терминов и т. д. Для всех рассмотренных случаев получены оценки указанных условных вероятностей на основе информации о классификации предыдущих документов (информации об обучающей выборке документов). На основе полученных оценок построены выражения для решающих функций байесовского классификатора.
Эти решающие функции являются основой численных алгоритмов классификации. На основании методов классификации, полученных в предыдущем разделе, разрабатывается алгоритм классификации документов в АИПС. Решающие функции, которые используются в этих методах, являются основой для численных алгоритмов классификации.
Рассмотрены практические аспекты построения общих методов обработки и классификации документов, в частности, вопросы автоматического формирования тезауруса (словаря данных). На производительность и качество работы системы классификации в АИПС большое влияние оказывает размер обучающей выборки. Рассмотрен вопрос о минимальном размере обучающей выборки и его влиянии на качество классификации. Проведена оценка эффективности алгоритмов, учитывающих различную степень взаимной зависимости появления терминов в документе определенного класса.
Рассмотрена апробация разработанных алгоритмов, которая проводилась в ЕАИС таможенной службы Украины. Первым этапом реализации является разработка программного модуля для организации обработки и хранения документов в отделе по борьбе с контрабандой и нарушением таможенных правил Днепропетровской региональной таможни. Реализация данного программного продукта существенно оптимизировала и упростила обработку текстовой документации данного отдела, после чего было принято решение о возможности внедрения программного продукта в ЕАИС. Второй этап реализации - это разработка и внедрение программных модулей классификации документов ЕАИС.
Ключевые слова: автоматизированная информационно-поисковая система, решающие функции, система классификации, информационная модель.
THE SUMMARY
Kabak Leonid. Methods and models of classification of text documents in the specialized information retrieval systems. - Manuscript.
The dissertation for the degree of candidate of engineering sciences on the speciality 05.13.06 - the automated control systems and progressive information technologies. - Kharkov National University of Radio Electronics, Kharkov, 2006.
The thesis is devoted to the development of modern methods of classification which can be applied for computing large scale arrays of the text documentation in the system of document circulation of the Common automated information system of the customs service of Ukraine. One of the actual questions for the customs service of Ukraine is the problem of classification of the documents functioning in the database of the automated information retrieval system, with the helping of the mail server of internal customs network INTRANET. In the dissertation methods of the automated classification of the documents, taking into account a relative frequency coming across the definite belonging to the various subject sections, and also interdependence of the appearance of different terms in documents of the definite class are offered.
Key words: the automated information retrieval system, the decisive functions, the system of classification, information technologies.
Размещено на Allbest.ru
Подобные документы
Принципи та особливості роботи пошукових роботів. Аналіз відмінностей каталогів від пошукових систем. Шляхи та параметри оцінювання обсягів індексації сучасних пошукових систем. Загальні рекомендації щодо додавання сайту до пошукової системи чи каталогу.
реферат [101,3 K], добавлен 18.11.2010Аналіз властивостей безкоштовних пошукових та поштових серверів Інтернету. Огляд методики ранжирування результатів пошуку в інформаційно-пошукових системах бібліотек. Вивчення можливостей пошукової системи "Мета", пошуку по реєстру українських сайтів.
курсовая работа [142,9 K], добавлен 17.11.2011Постановка задачi інформаційно-аналітичної системи сiльськогосподарських пiдприємств по вирощуванню сої. Комп'ютерна реалізація автоматизованої системи. Схема даних сої на підприємстві. Ескіз головної кнопкової форми. Макет форми: "Дані про сою".
курсовая работа [1,7 M], добавлен 17.04.2011Установки протоколів TCP/IP. Налаштування поштової програми MS Outlook Express. Класифікація пошукових систем та принципи їх роботи. Створення електронних документів в WWW для публікації в мережі Інтернет на мові HTML. Основи впровадження JavaScript.
лабораторная работа [259,9 K], добавлен 06.11.2011Обґрунтований вибір засобів для проектування автоматизованої інформаційно-довідкової системи. Опис структури технологічного процесу обробки даних для розв’язання задачі. Комп'ютерна реалізація окремих об'єктів системи (таблиці, форми, звіти, запити).
курсовая работа [30,7 K], добавлен 14.05.2011Розробка автоматизованої інформаційно-довідкової системи "Шовкова фея". Область використання системи, визначення функцій, вибір програмних засобів для розв’язання задачі, її комп’ютерна реалізація. Вимоги до ПЗ. Аналіз вихідних даних засобами MS Excel.
презентация [980,4 K], добавлен 09.09.2010Особливості архітектури комп'ютерних мереж. Апаратні та програмні засоби комп'ютерних мереж, їх класифікація та характеристика. Структура та основні складові комунікаційних технологій мереж. Концепції побудови та типи функціонування комп'ютерних мереж.
отчет по практике [1,2 M], добавлен 12.06.2015Історія створення комп’ютерних комунікацій та принципи їх побудови. Характеристика устаткування для створення комп’ютерних мереж. Поняття адресації, види протоколів, їх розвиток, комбінування та особливості використання. Стандарти бездротових мереж.
курс лекций [1,3 M], добавлен 04.06.2011Термінологія, сучасне діловодство: сутність, особливості, структура, фіксація. Базові групи документів, що підлягають реєстрації. Використання комп’ютерних технологій на етапі документування та організація документообігу. Сімейства текстових редакторів.
курсовая работа [44,9 K], добавлен 19.09.2010Інформаційні потреби: типи та характеристики. Етапи і порядок підготовки інформаційно-аналітичних документів, загальна методика їх створення. Напрямки інформаційно-аналітичної діяльності державної науково-педагогічної бібліотеки ім. В.О. Сухомлинського.
курсовая работа [51,2 K], добавлен 19.07.2011
