Ентропійні методи в задачах нечіткої кластеризації

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

ДНІПРОПЕТРОВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

ІМЕНІ ОЛЕСЯ ГОНЧАРА

Блюсс Олег Борисович

УДК 519.237.8

ЕНТРОПІЙНІ МЕТОДИ В ЗАДАЧАХ НЕЧІТКОЇ КЛАСТЕРИЗАЦІЇ

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

АВТОРЕФЕРАТ

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

кандидата фізико-математичних наук

Дніпропетровськ - 2011

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

Робота виконана в Дніпропетровському національному університеті імені Олеся Гончара Міністерства освіти і науки України.

Науковий керівник: заслужений діяч науки і техніки України, доктор фізико-математичних наук, професор Кісельова Олена Михайлівна, Дніпропетровський національний університет імені Олеся Гончара, декан факультету прикладної математики.

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

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

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

З дисертацією можна ознайомитися в бібліотеці Дніпропетровського національного університету імені Олеся Гончара за адресою: 49050, м. Дніпропетровськ, вул. Козакова, 8.

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

спеціалізованої вченої ради В.А. Турчина

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційну роботу виконано в період з 2007 р. по 2011 р. на кафедрі обчислювальної математики та математичної кібернетики Дніпропетровського національного університету імені Олеся Гончара у відповідності з індивідуальним планом аспіранта. Наукові дослідження, результати яких увійшли до дисертації, проводились у межах держбюджетних тем «Математичні моделі та алгоритми розв'язання задач оптимального розбиття множин в умовах невизначеності» (2006-2008 р., ДР№0106U000800) та «Математичні моделі задач охорони навколишнього середовища, методи їх розв'язання на основі теорії оптимального розбиття» (2009-2011 р., ДР№0109U000145).

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

Основними завданнями дослідження є:

- обґрунтування використання функції ентропії як критерію якості нечіткої кластеризації;

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

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

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

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

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

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

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

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

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

Наукова новизна отриманих результатів. Основні результати, що визначають наукову новизну і виносяться на захист, такі:

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

- розроблено нові алгоритми розв'язання задач нечіткої кластеризації з обмеженнями, складовою частиною яких є r-алгоритм Н.З. Шора;

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

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

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

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

Особистий внесок здобувача. Всі результати дисертаційної роботи, що виносяться на захист, отримані особисто автором.

У працях, опублікованих у співавторстві, здобувачу належить наступне: у [2] - аналіз результатів нечіткої кластеризації, отриманих за допомогою розроблених алгоритмів; [3] - розробка алгоритму нечіткої кластеризації з адаптивним вибором експоненціальної ваги; [4] - постановка й доведення існування розв'язку задачі багатокритеріальної нечіткої кластеризації; [5] - аналіз результатів прогнозу викидонебезпеки гірських порід, отриманого за допомогою модифікованого методу с-середніх; [7] - побудова математичної моделі задачі класифікації препаратів за їх біологічною активністю; [8] - постановка багатокритеріальної задачі вибору експоненціальної ваги; [9] - обґрунтування вибору експоненціальної ваги на основі мінімізації ентропії Реньї; [12] - модифікація методу с-середніх на основі використання згортки критеріїв; [13] - застосування модифікації методу с-середніх для прогнозу біологічної активності.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідалися та обговорювалися на таких конференціях:

- X, XIII Міждержавні науково-методичні конференції «Проблеми математичного моделювання», 2006 р., 2009 р., м. Дніпродзержинськ, Дніпродзержинський державний технічний університет.

- IV, V, VI, VII, VIII Міжнародні науково-практичні конференції «Математичне та програмне забезпечення інтелектуальних систем», 2006 р. - 2010 р., м. Дніпропетровськ, ДНУ.

- Міжнародна науково-практична конференція «Системний аналіз та інформаційні технології», 2010, м. Київ, ННК «ІПСА» НТУУ «КПІ».

- 30-th Dynamics Days Europe, 2010, Bristol, University of Bristol.

Публікації. Основні результати дисертації опубліковано в 14 наукових працях, серед яких 5 статей у наукових фахових виданнях, 9 - в збірниках тез доповідей наукових конференцій.

Структура й обсяг роботи. Дисертаційна робота складається із вступу, чотирьох розділів, висновків, списку використаної літератури з 119 джерел на 11 сторінках та двох додатків. Загальний обсяг дисертації складає 167 сторінок, основного тексту - 130 сторінок, ілюстрацій - 38, додатків - 26 сторінок. ентропія нечіткий кластеризація задача алгоритм

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

Виявлено напрямки подальших наукових досліджень.

У другому розділі розглянуто задачу математичного програмування в такій постановці:

(1)

(2)

, (3)

де , - параметри, які визначаються типом задачі. Задачі типу (1)-(3) розв'язуються на основі ряду ентропійних методів моделювання складних систем.

Розв'язок задачі (1)-(3) при може бути записаний у вигляді

, (4)

де визначаються із системи рівнянь, яку отримують підстановкою (4) в (2).

Доведено такі теореми.

Теорема 2.1. Нехай у задачі (1)-(3) , і величини . Тоді для параметру в розв'язку (4) мають місце такі оцінки:

а) якщо , то , де ;

б) якщо , то , де .

Теорема 2.2. Нехай у задачі (1)-(3) , і величини . Тоді мають місце такі твердження:

а) якщо виконується нерівність

, (5)

то , і розв'язок задачі (1)-(3) набуває вигляду .

б) якщо виконується нерівність

, (6)

то в виразі (4) і справедливою є оцінка

.

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

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

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

Наведемо постановку задачі нечіткої кластеризації в методі с-середніх. Нехай - скінченна множина даних у просторі ознак , - ціле число, ; і нехай означає множину всіх дійсних матриць.

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

Уведемо множину нечітких - розділень множини

. (7)

Потрібно розв'язати задачу

, (8)

де , - центр -го кластеру; означає норму в , -експоненціальна вага.

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

Задача 1.

.

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

Доведено теореми.

Теорема 3.1. Нехай у задачі 1 послідовність упорядковано за зростанням, , . Тоді

1. Якщо має місце співвідношення , то

.

2. Якщо , то мають місце такі оцінки:

,,

де .

Теорема 3.2. Нехай виконуються умови теореми 3.1. Тоді, якщо

, то .

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

(9)

де - параметр методу штрафних функцій, як правило, .

Розроблено алгоритм нечіткої кластеризації, який ґрунтується на перерахуванні ступенів приналежності у відповідності з розв'язками скінченної послідовності задач безумовної оптимізації. Складовою частиною алгоритму є метод узагальненого градієнтного спуску з розтягненням простору в напрямку різниці двох послідовних антиградієнтів (r-алгоритм Н.З. Шора).

Алгоритм 1.

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

Нехай в результаті обчислень після кроків алгоритму отримано значення .

Опишемо -й крок:

1. Формуємо нове нечітке розбиття множини об'єктів кластеризації на непустих кластерів, які характеризуються сукупністю ступенів приналежності та визначаються при будь-якому фіксованому , виходячи з розв'язку задачі безумовної оптимізації (9).

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

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

4. Приймаємо .

Задача 2.

,

Доведено теорему.

Теорема 3.3. Нехай у задачі 2 послідовність є упорядкованою за зростанням, , . Тоді має місце нерівність

. (10)

Відзначимо випадок, коли оцінки знизу и зверху є близькими. Нехай .

При нерівність (10) набуває вигляду

.

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

.

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

Аналіз результатів обчислювальних експериментів підтверджує можливість отримання розділення даних, яке характеризується наперед заданим набором показників якості: компактністю, ентропією розбиття та індексом Ксі-Бені, який визначається нижче

.

Зазначимо, що чим менше значення , тим вище якість кластеризації.

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

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

, (11)

де - параметр методу, .

Алгоритм 2.

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

Нехай в результаті обчислень після кроків алгоритму отримано значення .

Опишемо -й крок:

1. Визначаємо оптимальне значення експоненціальної ваги на -му кроці алгоритму, виходячи з розв'язку задачі (11).

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

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

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

5. Приймаємо .

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

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

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

Проведено дослідження впливу параметра на кінцеве значення експоненціальної ваги. В результаті обчислювальних експериментів виявлено, що оптимальні значення експоненціальної ваги за будь-якого значення залишаються в межах інтервалу (1; 5). Цей факт продемонстровано на рис. 3.

Рис. 1. Залежність кінцевих значень функцій від при нечіткій кластеризації ірисів Фішера



Рис. 2. Значення величини по ітераціях для трьох виконань нечіткої кластеризації ірисів Фішера за різних початкових матриць приналежності

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

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



Рис. 3. Залежність кінцевого значення експоненціальної ваги від при розв'язанні задачі нечіткої кластеризації ірисів

Рис. 4. Залежність індекса Ксі-Бені від при розв'язанні задачі нечіткої кластеризації ірисів

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

,

де - константа, .

Розглянемо -й доданок критерію як функцію відносно при інших фіксованих ступенях приналежності:

.

Існування розв'язку задачі

(12)

випливає з теореми.

Теорема 4.1. Нехай у задачі (12) послідовність є упорядкованою за зростанням, , , . Тоді має місце така оцінка:

де - корінь рівняння

. (13)

Розв'язок трансцендентного рівняння (13) отриманий у вигляді

,

де , - W-функція Ламберта, для обчислення якої використовується наступна наближена формула:

Розроблено алгоритм багатокритеріальної нечіткої кластеризації, складовою частиною якого є розв'язок такої задачі безумовної оптимізації:

за допомогою r-алгоритму Н.З Шора.

Аналіз застосування алгоритму багатокритеріальної нечіткої кластеризації проведено шляхом порівняння результатів, отриманих при розв'язанні тестової задачі класифікації ірисів Фішера, з кластеризацією методом с-середніх. Досліджено вплив параметра на кінцеві значення функції Беждека й ентропії (рис. 5, 6).



Рис. 5. Залежність кінцевого значення функції Беждека від

Рис. 6. Залежність кінцевого значення функції ентропії від

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

ВИСНОВКИ

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

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

1. Для формулювання нових математичних постановок задач нечіткої кластеризації

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

- виявлено основні властивості функції ентропії, суттєві при нечіткій кластеризації; обґрунтовано необхідність урахування ентропії розбиття для підвищення якості кластеризації;

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

2. Сформульовано дві нові задачі нечіткої кластеризації, в математичну постановку яких включено такі компоненти: цільову функцію методу с-середніх для нечіткої кластеризації та ентропію розбиття. При цьому в одній задачі мінімізується цільова функція методу с-середніх при обмеженнях на ентропію розбиття, у другій - мінімізується ентропія розбиття при обмеженні на цільову функцію методу с-середніх. З використанням теорії функціональних нерівностей доведено теореми про існування розв'язків сформульованих задач. Розроблено алгоритми їх розв'язання, складовою частиною яких є r-алгоритм Н.З. Шора.

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

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

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

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

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

- кристалограм біологічних рідин для діагностики патологій на основі аналізу текстурних ознак.

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

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

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

1. Блюсс О.Б. Нечітка кластеризація фармакологічних препаратів за комплексним впливом на фізіологічні системи // Зб. наук. пр. «Питання прикладної математики і математичного моделювання». - Д.: Вид-во Дніпропетр. нац. ун-ту, 2007.-С.10-19.

2. Киселева Е.М. Особенности некоторых алгоритмов многокритериальной нечеткой кластеризации / Е.М. Киселева, О.Б. Блюсс // Зб. наук. пр. «Питання прикладної математики і математичного моделювання». - Д.: Вид-во Дніпропетр. нац. ун-ту, 2008.-С.86-92.

3. Киселева Е.М. Особенности выбора весовых коэффициентов в векторном критерии задачи нечеткой кластеризации / Е.М. Киселева, О.Б. Блюсс // Зб. наук. пр. «Питання прикладної математики і математичного моделювання». - Д.: Вид-во Дніпропетр. нац. ун-ту, 2009.-С.134-141.

4. Булат А.Ф. Модификация метода с-средних на основе нелинейного векторного критерия / А.Ф. Булат, Е.М. Киселева, С.А. Пичугов, О.Б. Блюсс // Международный научно-технический журнал «Проблемы управления и информатики». - К., 2010. - №6. - С. 46-54.

5. Булат А.Ф. Прогнозная оценка выбросоопасности слоев песчаников на основе кластеризации в пространстве геологических данных / А.Ф. Булат, В.В. Лукинов, Е.М. Киселева, О.Б. Блюсс // Науково-теоретичний журнал Президії Національної академії наук України «Доповіді НАН України». - К., 2010. - №11. - С. 85-89.

6. Блюсс О.Б. Нейронечеткие технологии в задачах фармакологии / О.Б. Блюсс // «Проблеми математичного моделювання»: матеріали Міждержавної науково-практичної конференції. - Дніпродзержинськ: ДДТУ, 2006. - С.129.

7. Киселева Е.М. Классификация фармацевтических препаратов по их биологической активности на основе теории адаптивного резонанса / Е.М. Киселева, О.Б. Блюсс // «Математичне та програмне забезпечення інтелектуальних систем»: матеріали IV Міжнародної науково-практичної конференції. - Д.: ДНУ, 2006. - С.58.

8. Киселева Е.М. Выбор экспоненциального веса в методе с-средних для нечеткой кластеризации / Е.М. Киселева, О.Б. Блюсс // «Математичне та програмне забезпечення інтелектуальних систем»: матеріали V Міжнародної науково-практичної конференції. - Д.: ДНУ, 2007. - С.71.

9. Киселева Е.М. Использование энтропии Реньи в методах нечеткой кластеризации / Е.М. Киселева, О.Б. Блюсс // «Математичне та програмне забезпечення інтелектуальних систем»: матеріали VI Міжнародної науково-практичної конференції. - Д.: ДНУ, 2008. - С.156.

10. Блюсс О.Б. О монотонной зависимости энтропии от экспоненциального веса в задачах многокритериальной оптимизации // «Проблеми математичного моделювання»: матеріали Міждержавної науково-практичної конференції. - Дніпродзержинськ: ДДТУ, 2009. - С.150.

11. Блюсс О.Б. Использование неравенств Гёльдера в методах нечеткой кластеризации // «Математичне та програмне забезпечення інтелектуальних систем»: матеріали VII Міжнародної науково-практичної конференції. - Д.: ДНУ, 2009. - С.42-43.

12. Киселева Е.М. О задаче нечеткой кластеризации с векторным критерием / Е.М. Киселева, О.Б. Блюсс // «Системний аналіз та інформаційні технології»: матеріали 12-ї Міжнародної науково-практичної конференції SAIT 2010. - К.: ННК «ІПСА» НТУУ «КПІ», 2010. - С.97.

13. Blyuss K.B. Fuzzy clustering of biologically active compounds using impedance spectroscopy / K.B. Blyuss, E.M. Kiseleva, O.B. Blyuss // Dynamics Days Europe 2010. - Bristol, 2010.- pp.91.

14. Блюсс О.Б. Анализ показателей оценки качества нечеткой кластеризации // «Математичне та програмне забезпечення інтелектуальних систем»: матеріали VIII Міжнародної науково-практичної конференції. - Д.: ДНУ, 2010. - С.31.

АНОТАЦІЇ

Блюсс О. Б. Ентропійні методи в задачах нечіткої кластеризації.- Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 - теоретичні основи інформатики та кібернетики. - Дніпропетровський національний університет імені Олеся Гончара, Дніпропетровськ, 2011.

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

Сформульовано дві нові задачі нечіткої кластеризації, в математичну постановку яких включено такі компоненти: цільову функцію методу с-середніх для нечіткої кластеризації та ентропію розбиття. Доведено теореми про існування розв'язків цих задач. Розроблено алгоритми їх розв'язання, складовою частиною яких є r-алгоритм Н.З. Шора.

Вперше обґрунтовано вибір експоненціальної ваги в методі с-середніх. Побудовано відповідний алгоритм нечіткої кластеризації з адаптивним вибором експоненціальної ваги.

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

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

Блюсс О. Б. Энтропийные методы в задачах нечеткой кластеризации.- Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.01 - теоретические основы информатики и кибернетики. - Днепропетровский национальный университет имени Олеся Гончара, Днепропетровск, 2011.

В диссертационной работе сформулированы новые задачи нечеткой кластеризации, которые включают энтропию разбиения в качестве вспомогательного критерия.

Исследованы свойства решений задачи математического программирования с целевой функцией, учитывающей энтропию. Показано, что решение такой задачи определяется конечным числом параметров. Для частных случаев задачи получены интервалы изменения этих параметров, что позволило упростить поиск оптимального решения.

Определены свойства функции энтропии, существенные при нечеткой кластеризации.

Сформулированы две новые задачи нечеткой кластеризации, в математическую постановку которых включены следующие компоненты: целевая функция метода с-средних и энтропия разбиения. При этом в одной задаче минимизируется целевая функция метода с-средних при ограничении на энтропию разбиения, а в другой - минимизируется энтропия разбиения при ограничении на целевую функцию метода с-средних. С применением теории функциональных неравенств доказаны теоремы о существовании решения сформулированных задач. Разработаны алгоритмы их решения, составной частью которых является r-алгоритм Н.З. Шора.

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

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

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

Ключевые слова: нечеткая кластеризация, энтропия разбиения, функциональные неравенства, свертка критериев, согласованность результатов кластеризации.

Blyuss O. B. Entropy methods in fuzzy clustering problems.- Manuscript.

Thesis for the degree of candidate of sciences in physics and mathematics by specialization 01.05.01 - theoretical foundations of informatics and cybernetics.- O. Honchar Dnipropetrovsk National University, Dnipropetrovsk, 2011.

This thesis introduces new fuzzy clustering problems that include partition entropy as an auxiliary criterion. The methods and algorithms of solving these problems are derived.

Two new fuzzy clustering problems are derived and studied, whose mathematical formulation includes the fuzzy c-means objective function and the partition entropy. Theorems of existence of solutions for these problems are proved. Numerical algorithms based on Shor's algorithm are derived and analysed.

The method for selection of the exponential weight in the fuzzy c-means scheme is proposed for the first time and analysed in detail. The corresponding algorithm for fuzzy clustering with an adaptive exponential weight is derived.

Multicriteria fuzzy clustering problem is formulated, which is reduced to minimizing a nonlinear combined criterion. Obtained bounds on the minimal value of the combined criterion provide the existence of solutions to the problem. An algorithm of solving this problem is developed. Analysis of the results of numerical computations demonstrates the possibility to substantially improve the results of the multicriteria fuzzy clustering by choosing respective weights of criteria in the combined criterion.

Keywords: fuzzy clustering, partition entropy, functional inequalities, combined criterion, consistency of clusterization results.

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

...