Автоматична класифікація багатовимірних об’єктів із застосуванням апарату нейронних мереж

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

Київський національний університет імені Тараса Шевченка

Автореферат

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

Автоматична класифікація багатовимірних об'єктів із застосуванням апарату нейронних мереж

Порхун О.В.

01.05.01 - теоретичні основи інформатики та кібернетики

Київ - 2009

Вступ

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

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

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

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

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

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

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

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

1) науково-технічної бюджетної теми: Б/Т № 06БФ015-01 "Cтворення теоретичних основ, методів та засобів інтелектуалізації інформаційно-комунікаційних технологій для розподілених комп'ютерних систем" (№ держреєстрації 0106U005860);

2) державної науково-технічної програми "Образний комп'ютер", зокрема, у науково-дослідних роботах за договорами:

№ 03ДП015-01 "Розробити інформаційну технологію синтезу, аналізу, реферування, пошуку і смислової інтерпретації текстової інформації та смислового перекладу текстової інформації з однієї мови на іншу" (№ держреєстрації 0103U005499). Замовник Міністерство промислової політики;

№ 04ДП015-06 "Розробити експериментальну комп'ютерно-лінгвістичну технологію змістовного аналізу текстової інформації" (№ держреєстрації 0104U004834). Замовник Міжнародний науково-навчальний центр інформаційних технологій та систем;

№ 06ДП015-05 "Розробити ескізний проект системи мультилінвістичної фільтрації та семантичного аналізу текстової інформації на базі мультилінгвістичної бази знань типу WordNet" (№ держреєстрації 0106U006685). Замовник Міжнародний науково-навчальний центр інформаційних технологій та систем;

№ 07ДП015-04 "Розробити систему смислового контекстного аналізу текстових документів на основі онтологічної бази знань" (№ держреєстрації 0107U003920). Замовник Міжнародний науково-навчальний центр інформаційних технологій та систем;

№ 08ДП015-07 "Розробити системи смислової класифікації, рубрикації та кластеризації природно мовних текстових документів на основі семантичного аналізу" (№ держреєстрації 0108U007255). Замовник Міжнародний науково-навчальний центр інформаційних технологій та систем.

3) науково-технічних робіт за договорами:

№ 05ДП015-03 "Створення технології компю'терно - лінгвістичної обробки текстової інформації на природній мові" (№ держреєстрації 0105U008126). Замовник Міністерство освіти та науки України;

№ 07ДП015-06 "Створення глобальної україномовної лексико-семантичної онтологічної бази лінгвістичних знань та розробка пакету програм інтелектуальної обробки текстових документів" (№ держреєстрації 0107U006801). Замовник Міністерство освіти та науки України.

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

У відповідності до поставленої мети визначено такі основні задачі дослідження:

визначення числа кластерів при розв'язанні задачі кластеризації багатовимірних об'єктів;

побудова вектора ознак для вирішення задачі класифікації об'єктів, представлених різнорідними групами числових ознак;

розробка автоматичних систем класифікації та кластеризації текстової інформації;

експериментальне випробування розроблених систем на прикладі розв'язання задач атрибуції текстів.

Об'єкт дослідження. Об'єктом дослідження є автоматична класифікація багатовимірних об'єктів, що задані векторами числових ознак.

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

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

Наукова новизна одержаних результатів полягає в наступному:

вперше запропоновано метод визначення числа кластерів при кластеризації корпусу об'єктів із застосуванням нейронної мережі Кохонена, критерію якості отриманих кластерів та методу ідеальної точки;

розроблено нову автоматичну систему кластеризації текстів з можливостями здійснення кластеризації при відомій кількості кластерів та з використанням запропонованого методу визначення числа кластерів;

вперше запропоновано метод побудови вектора ознак об'єкту із врахуванням випадків їх розподілу по різнорідним групам;

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

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

Особистий внесок здобувача полягає у розробці нових методів для розв'язання основних задач, що виникають в процесі класифікації багатовимірних об'єктів. Всі основні результати дисертаційної роботи одержані автором самостійно. У публікаціях, написаних у співавторстві, здобувачеві належить: у роботі [3] - розробка, обґрунтування та програмна реалізація методу побудови вектора ознак об'єкту, що класифікується, розробка автоматичної системи класифікації текстів та її випробування для вирішення задачі атрибуції художніх творів; у роботах [4, 5] - розробка автоматичної системи класифікації текстів та методу визначення числа кластерів при кластеризації корпусу об'єктів.

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

Міжнародній конференції "Стилистика и теория языковой коммуникации", Москва, 20-21 апреля 2005 г.

Міжнародній конференції з автоматичного управління "Автоматика - 2006", Вінниця, 25-28 вересня, 2006 р.

Міжнародній конференції "Теоретичні та прикладні аспекти побудови програмних систем", Київ, 5-8 грудня 2006 р.

Міжнародній науковій конференції MegaLing'2007 "Горизонти прикладної лінгвістики та лінгвістичних технологій", Крим, Партеніт, 2007 р.

Публікації. Основні результати роботи викладені в 6 друкованих працях, з яких 3 - статті у наукових фахових журналах, рекомендованих ВАК України (з них 2 виконано без співавторів) та 3 публікації у вигляді тез міжнародних наукових конференцій.

Структура дисертації. Дисертація складається зі вступу, п'яти розділів, висновків, трьох додатків та списку використаних джерел з 100 найменувань. Обсяг дисертації - 110 сторінок основного тексту українською мовою, ілюстрованих 5 рисунками та 12 таблицями.

1. Зміст роботи

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

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

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

Альтернативою методам дискримінації є методи, що базуються на обчисленні відстаней: метод k-найближчих сусідів, метод міркування за аналогією (Case Based Reasoning, CBR), класифікатор Роше. Вони не потребують фази навчання та відносяться до класу методів, робота яких базується на збереженні даних у пам'яті для порівняння з новими елементами.

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

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

Актуальною є проблема класифікації текстів на природній мові. За роки досліджень в області автоматичної класифікації текстової інформації було використано ряд відомих методів класифікації: метод Байєса, метод опорних векторів, метод k-найближчих сусідів, класифікатор Роше. Для класифікації різнорідних за характером текстів при виборі різних основ класифікації російським вченим В.Г. Васильєвим було запропоновано метод комбінованої ієрархічної класифікації.

На основі проведеного аналізу методів класифікації було виявлено їх основний недолік - залежність від розмірності простору ознак об'єктів та об'єму вхідних даних. Цю проблему допомагає вирішити апарат нейронних мереж. Важливими результатами в області класифікації багатовимірних об'єктів із застосуванням нейронних мереж є розробки з реалізації моделі поведінки користувачів Grid-систем українськими вченими: О.М. Куссулем, С.В. Скакуном. Відомими роботами з автоматичної класифікації текстів із застосуванням нейронних мереж є дослідження російських вчених: А.Ф. Гареєва, О.Г. Шевельова, А.В. Петракова, А.М. Андреєва, Д.В. Березкіна, В.В. Сюзєва, В.І. Шабанова.

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

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

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

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

,

де , , , .

Кожній матриці ставиться у відповідність граф. Для кожного ребра графу вказується оцінка c(e), як сила зв'язку i-го вузла з j-м, яка обчислюється за формулою:

,

де

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

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

,

де - сума відстаней точок кластеру від центру кластеру по всіх кластерах, i=, M - кількість кластерів розбиття, g - сумарна відстань між центрами кластерів.

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

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

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

Для набору ознак, що розподілені на 2 різнорідні групи та формуються 3 вибірки векторів:

- вибірка А складається з векторів, що містять лише ознаки групи , інші компоненти вектора нульові:

р = (),

де p - вектор-приклад з навчальної вибірки, i - ознака групи ;

- вибірка В містить вектори, що складаються із ознак групи ; компоненти, що відповідають ознакам групи - нульові:

р = (,),

де j - ознака групи ;

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

p =

де

, .

Кожній із сформованих вибірок ставиться у відповідність точка з відрізку [0,1]: вибірці С - точка 0.5, вибіркам А та В, відповідно - 0 та 1.

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

,

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

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

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

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

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

Лема 2.1. Нехай n - розмірність вектора ознак об'єкту одноелементної вибірки; - задана точність алгоритму А1 (довжина відрізку, одна з крайніх точок якого відповідає оптимальній вибірці); W - кількість вагових зв'язків між нейронами, включаючи зсуви внутрішніх та вихідних нейронів. Тоді оцінка складності алгоритму А1 з використанням одноелементної вибірки складає:

.

Для випадку, коли навчальні вибірки представляють множину об'єктів, має місце

Теорема 2.1. Нехай N - розмірність вектора ознак для об'єктів навчальної вибірки, вихідний опис яких задається групами ознак; P - кількість об'єктів (прикладів) у вибірці; - задана точність алгоритму А1; W - кількість вагових зв'язків між нейронами, включаючи зсуви внутрішніх та вихідних нейронів. Тоді для алгоритму А1 справедлива оцінка:

.

Позначимо через приклад виду T - приклад, для якого вектор по одній з груп ознак не містить значень, а по іншій групі ознак його розмірність дорівнює N (довжині вектора-прикладу). Тоді для випадку наявності у вибірці об'єктів з нерівномірним розподілом груп ознак мають місце:

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

Якщо навчальна вибірка із P прикладів містить приклад виду T, то оцінка складності алгоритму А1 дорівнює:

.

Наслідок 2.2. Якщо у вибірці з P прикладів є приклад виду T по групі та приклад виду T по групі , то оцінка складності алгоритму А1 складає:

.

Наслідок 2.3. Якщо у вибірці з Р прикладів є приклад виду T та приклад, для якого одна з груп ознак обмежена по довжині значенням С, то оцінка складності для алгоритму А1 складає:

.

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

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

Умова 1. Ідентичність граматичних ознак іменника та описових характеристик, які йому співставляються.

Умова 2. Мінімальна відстань між словами. Чим менше відстань між іменником та описовою характеристикою, що йому співставляється, тим більша ймовірність даного зв'язку.

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

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

- частку появи внутрішніх розділових знаків (двокрапка, кома, тире, крапка з комою, дужки, лапки);

- частку появи зовнішніх розділових знаків (крапка, знак оклику, знак питання, три крапки, комбінація знаків оклику та знаків питання);

- середню довжину речення у словах;

- частку слів певної довжини (з однієї літери, з 2-х і т.д. до 10);

- частку речень певної довжини (з одного слова, з 2-х і т.д. до 30);

- середню кількість прикметників, дієприкметників і дієприслівників до іменника (окремо).

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

Остання група ознак, що характеризує складність речення, визначається із застосуванням запропонованого методу визначення зв'язку між іменником та його описовими характеристиками (прикметником, дієприкметником та дієприслівником).

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

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



Рис. 1. Архітектура нейронної мережі в експерименті

Для нейронів кожного блоку були використані відповідно такі функції виходу: exp(-x2), 1-( exp(-x2)) та th(x). Для вихідного шару нейронів використана функція: 1/(1+exp(-x)).

Налаштування системи реалізовано з використанням методу зворотного розповсюдження помилки та алгоритмів А1 та А2. Групи ознак складають частоти слів з результуючих частотних словників текстів та синтаксичні ознаки у поєднанні з статистикою службових слів.

Навчання та тестування системи проводилось на текстах з обмеженням об'єму до 2000 слів. Навчальна вибірка, що використовувалась, включала 100 художніх творів наступних авторів (по 10 творів кожного автора): О. Пушкіна, В. Набокова, М. Горького, М. Булгакова, І. Тургенєва, Л. Толстого, А. Чехова, М. Шолохова, Ф. Достоєвського, М. Гоголя.

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

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

Для тестування системи Atributer було використано 100 художніх творів тих же авторів, які не ввійшли у навчальну вибірку (по 10 творів кожного автора).



Рис. 2. Пошук оптимальної вибірки

Результати, одержані системою Atributer, подано у наступній інтерпретації. Нехай Hi - подія, яка полягає в тому, що тексти і-го автора вірно розпізнані системою Atributer; Hi / Hj - подія, яка полягає в тому, що тексти і-го автора віднесені до автора j (при j=i дана подія співпадає з подією Hi). Покладемо, що P(Hi) - правдоподібність події Hi, яка визначається як відношення кількості вірно розпізнаних системою текстів і-го автора до кількості всіх текстів автора і; P(Hi / Hj) - правдоподібність події Hi / Hj.

Результати класифікації, отримані системою Atributer для заданої тестової вибірки, наведені у таблиці 1, в якій рядки та стовпчики відповідають авторам з тестової вибірки, а комірка і-го рядка та j-го стовпчика містить правдоподібність події P(Hi/Hj). Діагональні елементи таблиці представляють правдоподібності того, що всі тексти одного автора розпізнані вірно. Індекси подій відповідають заданому порядку авторів у навчальній вибірці.

Згідно з даними таблиці 1 вірно розпізнані системою Atributer тексти складають 71%; середня кількість невірно розпізнаних текстів для кожного з 10 авторів у даному експерименті становить 3 тексти.

Таблиця 1

Hj, Hi,	H1	H2	H3	H4	H5	H6	H7	H8	H9	H10
H1	6/10	1/10	0	0	1/10	2/10	0	0	0	0
H2	0	9/10	1/10	0	0	0	0	0	0	0
H3	0	0	5/10	2/10	1/10	1/10	0	1/10	0	0
H4	0	1/10	2/10	6/10	1/10	0	0	0	0	0
H5	0	0	1/10	1/10	8/10	0	0	0	0	0
H6	1/10	0	0	0	1/10	7/10	0	0	0	1/10
H7	0	0	0	0	1/10	0	9/10	0	0	0
H8	0	0	1/10	0	0	1/10	0	7/10	1/10	0
H9	0	1/10	2/10	1/10	0	0	0	1/10	5/10	0
H10	0	1/10	0	0	0	0	0	0	0	9/10

Розглянуто застосування автоматичної системи класифікації Atributer для встановлення авторства твору "Роман з кокаїном". Проведений дослідниками аналіз, що базувався на використанні суб'єктивно-атрибутивного підходу, дозволив висунути гіпотезу про те, що автором даного твору є В. Набоков, який писав під псевдонімом М. Агеєв.

Результати класифікації даного твору за допомогою системи Atributer подано у наступній інтерпретації. Виходи системи Atributer xTi для даного тексту T розглядаються як відстані до кожного з класів авторів Ci, i=1,…, n, тобто:

xTi =,

де V(Ci) - вектор, що відповідає автору Ci, V(PT ) - вектор ознак для даного тексту. Відстань x* до найближчого для тексту T класу визначається за формулою:

,

С* - найближчий для тексту T клас.

Згідно з наведеними результатами у таблиці 2 найближчим класом для твору "Роман с кокаїном" є клас творів Набокова: x*==0,00535, С*=C2. Це дає підстави стверджувати, що він подібний за даним простором ознак до творів Набокова, які використовувались для навчання системи та творів Набокова, які були вірно розпізнані системою.

Таблиця 2

Класи авторів (Сi - <автор>)	Виходи системи Atributer, xTi
C1 - < О. Пушкін >	0,98781
C2 - < В. Набоков>	0,00535
C3 - < М. Горький>	0,03467
C4 - < М. Булгаков>	0,53489
C5 - < І. Тургенєв>	1,02340
C6 - < Л. Толстой>	0,02978
C7 - < А. Чехов>	0,78796
C8 - < М. Шолохов>	0,08872
C9 - <Ф. Достоєвський>	0,00745
C10 - < М. Гоголь>	0,82435

Із застосовуванням нейронної мережі Кохонена та запропонованого методу визначення числа кластерів була розроблена автоматична система кластеризації текстів на природній мові - Clasterizator. Дана система призначена для вирішення задач кластеризації документів масиву за вибраним профілем - тематикою тексту або стилем його написання. Для тестування системи Clasterizator її було застосовано для кластеризації вибірки художніх творів за стилістичними ознаками. Навчальна вибірка, що використовувалась, включала 85 художніх творів російських письменників: М. Гоголя, О. Купріна, М. Салтикова-Щедріна, М. Горького, В. Набокова, М. Булгакова, І. Тургенєва, Л. Толстого, М. Шолохова, О. Толстого, О. Пушкіна, А. Чехова.

Кластеризація проводилась окремо за: синтаксичними ознаками та статистикою службових слів; частотами слів з результуючих частотних словників; незваженими ознаками всіх груп; зваженими ознаками всіх груп, відповідно до числа з, визначеного із застосуванням алгоритму пошуку оптимальної вибірки. Найкращий результат отримано при кластеризації заданої вибірки текстів за зваженими ознаками всіх груп: вірно розпізнані системою Clasterizator тексти складають ~ 70,6%; середня кількість невірно розпізнаних текстів для кожного з 12 авторів у даному експерименті становить 2 тексти.

автоматичний кластеризація нейронний

Висновки

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

В роботі поставлено та вирішено такі завдання:

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

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

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

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

Список опублікованих праць за темою дисертації

1. Порхун О.В. Методи та алгоритми для розв'язання задач класифікації // Вісник Київського університету. Серія фіз.-мат. наук. - 2005. - №1. - С. 212-220.

2. Порхун О.В. Побудова параметричного простору в задачах атрибуції текстів. Метод формування вхідного вектору для розпізнавання стилю тексту нейронною мережею // Вісник Київського університету. Серія фіз.-мат. наук. - 2005. - №4. - С. 207-212.

3. Анисимов А.В., Порхун Е.В., Тарануха В.Ю. Алгоритм формирования параметрического вектора для решения задач классификации нейронной сетью прямого распространения // Кибернетика и системный анализ. - 2007. - №2. - C. 3-14.

4. Анисимова Е.А., Порхун Е.В., Тарануха В.Ю. Информационные технологии обработки документов, представленных в виде текстов на естественном языке. Возможности применения WORDNET и нейронных сетей // Матеріали міжнародної конференції з автоматичного управління "Автоматика - 2006". - Вінниця, 2006. - С. 344.

5. Порхун Е.В., Тарануха В.Ю. Применение WORDNET и нейронных сетей в создании интеллектуальных систем обработки текстов на естественном языке // Матеріали міжнародної конференції TAAPSD'2006 "Теоретичні та прикладні аспекти побудови програмних систем". - Київ, 2006. - С. 183-186.

6. Порхун Е.В. Разработка автоматической системы классификации текстов с применением аппарата нейронных сетей // Матеріали міжнародної наукової конференції MegaLing'2007 "Горизонти прикладної лінгвістики та лінгвістичних технологій". - Крим, Партеніт, 2007. - С. 283-285.

Размещено на Allbest.ru