Застосування теорії оптимального розбиття множин до розв’язання задач штучного інтелекту та розпізнавання образів
The paper substantiates the possibility of applying the mathematical theory of continuous problems of optimal partitioning of sets of n-dimensional Euclidean space, which belong to the non-classical problems of infinite-dimensional mathematical programming, to the solution of problems of artificial...
Saved in:
| Date: | 2021 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2021
|
| Subjects: | |
| Online Access: | https://journal.iasa.kpi.ua/article/view/252300 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | System research and information technologies |
| Download file: |  |
Institution
System research and information technologies| _version_ | 1866302798755266560 |
|---|---|
| author | Kiseleva, Elena Prytomanova, Olga Hart, Liudmyla |
| author_facet | Kiseleva, Elena Prytomanova, Olga Hart, Liudmyla |
| author_sort | Kiseleva, Elena |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2022-06-20T14:19:48Z |
| description | The paper substantiates the possibility of applying the mathematical theory of continuous problems of optimal partitioning of sets of n-dimensional Euclidean space, which belong to the non-classical problems of infinite-dimensional mathematical programming, to the solution of problems of artificial intelligence and pattern recognition. The problems of pattern recognition both in conditions of certainty and in conditions of uncertainty are formulated. A particular attention is paid to the application of methods of the theory of optimal partitioning for the construction of fuzzy Voronoi diagrams. Examples of constructing fuzzy Voronoi diagrams with the optimal placement of generating points are given. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2021.4.07 |
| first_indexed | 2025-07-17T10:27:46Z |
| format | Article |
| fulltext |
О.М. Кісельова, О.М. Притоманова, Л.Л. Гарт, 2021
Системні дослідження та інформаційні технології, 2021, № 4 91
TIДC
МЕТОДИ ОПТИМІЗАЦІЇ, ОПТИМАЛЬНЕ
УПРАВЛІННЯ І ТЕОРІЯ ІГОР
УДК 519.8
DOI: 10.20535/SRIT.2308-8893.2021.4.07
ЗАСТОСУВАННЯ ТЕОРІЇ ОПТИМАЛЬНОГО РОЗБИТТЯ
МНОЖИН ДО РОЗВ’ЯЗАННЯ ЗАДАЧ ШТУЧНОГО
ІНТЕЛЕКТУ ТА РОЗПІЗНАВАННЯ ОБРАЗІВ
О.М. КІСЕЛЬОВА, О.М. ПРИТОМАНОВА, Л.Л. ГАРТ
Анотація. Обґрунтовано можливість застосування математичної теорії непе-
рервних задач оптимального розбиття множин n-вимірного евклідового прос-
тору, які належать до некласичних задач нескінченновимірного математичного
програмування, до розв’язання задач штучного інтелекту та розпізнавання об-
разів. Наведено постановки задач розпізнавання образів як в умовах визначе-
ності, так і в умовах невизначеності, підходи до їх розв’язання із застосуван-
ням теорії оптимального розбиття множин. Особливу увагу приділено
застосуванню методів теорії оптимального розбиття для побудови нечітких ді-
аграм Вороного. Наведено приклади побудови нечітких діаграм Вороного
з оптимальним розміщенням точок-генераторів.
Ключові слова: розпізнавання образів, штучний інтелект, нечітка діаграма
Вороного, точки-генератори, оптимальне розбиття множин, нескінченно-
вимірне математичне програмування.
ВСТУП
Теорія оптимального розбиття множин (ОРМ) є новим розділом нескінчен-
новимірного математичного програмування і присвячена розробленню й
обґрунтуванню нових підходів до розв’язання різних недостатньо вивчених
класів неперервних задач оптимального розбиття множин n -вимірного евк-
лідового простору на їх неперетинні підмножини, а також розробленню ал-
горитмів для числового розв’язання великого класу теоретично та практично
важливих задач, які зводяться до неперервних задач оптимального розбиття.
Створення теоретичних основ розв’язання неперервних задач оптималь-
ного розбиття множин з n -вимірного евклідового простору nE започатко-
вано у 70-і роки минулого сторіччя членом-кореспондентом НАН України
О.М. Кісельовою [1]. Натепер науковою школою під її керівництвом розроб-
лено ряд напрямів у теорії ОРМ, обумовлених різними типами математич-
них постановок задач розбиття. Це лінійні і нелінійні, однопродуктові і ба-
гатопродуктові, детерміновані і стохастичні, в умовах повної та неповної
інформації про вихідні дані, статичні та динамічні задачі ОРМ без обмежень
і з обмеженнями, як із заданим положенням центрів підмножин, так і з від-
шуканням оптимального варіанта їх розташування [2–4]. Створена теорія
О.М. Кісельова, О.М. Притоманова, Л.Л. Гарт
ISSN 1681–6048 System Research & Information Technologies, 2021, № 4 92
ґрунтується на єдиному підході, що полягає у зведенні початкових нескін-
ченновимірних задач оптимізації певним чином (наприклад, через функціо-
нал Лагранжа) до негладких, як правило, скінченновимірних задач оптимі-
зації, для числового розв’язання яких застосовуються сучасні ефективні
методи недиференційовної оптимізації різні варіанти r-алгоритму, розроб-
лені в Інституті кібернетики ім. В.М. Глушкова НАН України під керівниц-
твом Н.З. Шора.
Технології, які ґрунтуються на математичному та алгоритмічному апа-
ратах теорії неперервних задач оптимального розбиття множин і відповід-
ному програмному забезпеченні, дозволяють ефективно розвивати один з
пріоритетних напрямів інформатики — інтелектуальні інформаційні техно-
логії і системи. Це — теорія розпізнавання образів (чітких та нечітких), кла-
стеризації, класифікації; теорія статистичних рішень; теоретичні задачі оп-
тимізації, які зводяться до задач оптимального розбиття множин, а саме:
задачі глобальної оптимізації, задачі побудови оптимальних квадратур, не-
перервні задачі кульового покриття, задачі обчислювальної геометрії та ін.
Наукова значущість та актуальність теорії ОРМ визначаються її широ-
кими практичними застосуваннями для розв’язання задач територіального
планування сфер обслуговування, геологічного прогнозування, задач охоро-
ни навколишнього середовища, медичної діагностики та інших задач,
пов’язаних із розбиттям множини довільної структури чи форми на підмно-
жини. Більш повний перелік практичних задач, які зводяться до задач ОРМ,
можна знайти у працях [2, 4].
У роботі описано застосування теорії ОРМ до розв’язання задач розпі-
знавання образів з метою мінімізації втрат від хибного розпізнавання.
ОБГРУНТУВАННЯ МОЖЛИВОСТІ ЗАСТОСУВАННЯ МЕТОДІВ ТЕОРІЇ
ОПТИМАЛЬНОГО РОЗБИТТЯ МНОЖИН ДО РОЗВ’ЯЗАННЯ ЗАДАЧ
РОЗПІЗНАВАННЯ ОБРАЗІВ
Розглядаючи задачу розпізнавання образів, будемо вважати, що досліджува-
ні зображення можна описати як набір N ознак, кожна з яких набуває зна-
чень деякої дискретної або неперервної множини. Тоді кожне зображення
можна подати у вигляді точки n-вимірного простору, координати якої відпо-
відають значенням ознак, що характеризують це зображення. Такий простір
називають простором ознак.
Якщо тепер у цьому просторі ввести якимось чином поняття відстані
(евклідової, Махаланобіса та ін.), то зображення, розміщені на невеликій
відстані одне від одного, можна вважати подібними і відносити їх до одного
класу, тоді як зображення, що розділені великими відстанями, вважати різ-
ними і відносити до різних класів.
Кожний образ (клас) з урахуванням таких припущень можна подати де-
якою множиною в n -вимірному просторі ознак.
Іноді передбачається виконання гіпотези компактності [5], тобто відпо-
відність таким припущенням:
1) завжди можливий такий плавний перехід від одного зображення до
іншого всередині даного образу, за якого всі проміжні етапи будуть його
зображеннями і, навпаки, не можливо плавно перейти від зображень одного
образу до зображень іншого без того, щоб не з’явилися зображення неви-
значеної належності;
2) мала деформація зображень у будь-якому напрямку не призводить до
виходу за межі даного образу.
Застосування теорії оптимального розбиття множин до розв’язання задач …
Системні дослідження та інформаційні технології, 2021, № 4 93
Можливість застосування методів ОРМ до розв’язання задач розпізна-
вання базується на тому, що після виділення простору ознак задача про по-
діл зображень на класи фактично зводиться до розбиття множини, що міс-
тить усі зображення, на підмножини, що відповідають різним класам
(образам) [6].
Задачу навчання (самонавчання) можна вважати розв’язаною, якщо
вдасться сформулювати алгоритм, за допомогою якого за навчальною по-
слідовністю можна знайти оптимальні в певному сенсі центри та межі класів
у просторі ознак або, інакше кажучи, розбити всі множини зображень на N
класів певним оптимальним способом [5].
Таким чином, можемо розглядати розпізнавання образів як задачу оп-
тимального розбиття множини Ω (яка містить усі зображення) n-вимірного
простору ознак на її підмножини i , Ni ,...,2,1 , кожна з яких відповідає
деякому образу (класу), тобто отримуємо таку задачу.
Задача А [7]. Нехай nE . Необхідно розбити множину Ω на N під-
множин, що не перетинаються, N ,...,1 так, щоб виконувались умови
,
1
N
i i 0)( jimes , Njiji ,...,1,, ,
а функціонал
dxxxcF
N
i
iNN
i
)() ,(}),...,{},,...,({
1
11
досягав мінімального значення.
Тут )(mes означає міру Лебега, функція ),( ixc означає втрати через
те, що елемент x віднесений до класу i з центром i , а функціонал
}),...,{},,...,({ 11 NNF означає сумарні втрати через неправильну класи-
фікацію.
Задачі розпізнавання образів можуть бути сформульовані по-різному з
урахуванням взаємного розташування образів у просторі ознак, виду
вихідних даних, відомої апріорної інформації тощо. Відповідно до цього
будуть сформульовані і різні задачі ОРМ.
Розглянемо ці задачі, а також їх особливості, дотримуючись класифіка-
ції з літературних джерел [5, 8].
Задачі розпізнавання образів в умовах визначеності
Припустімо, що межі образів у просторі ознак постійні, образи не перети-
наються між собою і кожна точка простору ознак завжди належить лише до
певного образу. У цьому випадку для кожного елемента навчальної послідов-
ності повинен бути точно вказаний клас, до якого він належить, і якщо якесь
зображення трапляється в цій послідовності кілька разів, то з кожного його
появою повідомляється той самий клас належності.
Задача навчання розпізнавання образів має на меті визначити, керую-
чись навчальною послідовністю, межі образів у просторі ознак.
Задача розпізнавання передбачає класифікацію пропонованого зобра-
ження відповідно до множини в n-вимірному просторі ознак, що містить
точку, яка є цим зображенням.
Постановка задачі. Нехай образи у просторі ознак не перетинають-
ся і відома досить представницька навчальна послідовність зображень
О.М. Кісельова, О.М. Притоманова, Л.Л. Гарт
ISSN 1681–6048 System Research & Information Technologies, 2021, № 4 94
},...,,{ 21 kxxxX , що належать до різних образів, і достеменно відомо, до
якого образу кожне зображення ix навчальної вибірки належить. Необхідно
визначити межі класів у просторі ознак.
Сформулюємо математичну постановку цієї задачі як задачі ОРМ.
Задача 1. Нехай — обмежена, вимірна за Лебегом множина
n -вимірного евклідового простору n . Потрібно знайти підмножини i ,
Ni ,..,1 , множини , що задовольняють умови
,
1
N
i i 0)( jimes , Njiji ,...,1,, ,
а функціонал
dxxcF
N
i
iN
i
1
1 )(}),...,({
досягав мінімального значення.
Функція )(xci тут означає втрати внаслідок належності елемента x до
класу i , а функціонал }),...,({ 1 NF визначає сумарні втрати за помил-
кової класифікації.
Таким чином, сформульовано задачу ОРМ без обмежень із фіксовани-
ми центрами підмножин (аналог задачі А1 з [3]), оптимальний розв’язок
якої має такий вигляд:
випадках,інших в 0
;,...,1 ,)(min)( якщо ,1
)( ,...,1
*
Nixcxc
x
k
Nk
i
i
де )(* xi , ,,...,1 Ni — характеристичні функції підмножин i , Ni ,..,1 ,
відповідно.
Для розв’язання задачі 1 методом ОРМ застосуємо такий алгоритм.
1. У просторі ознак виділяємо множину , яка містить усі образи з
i , Ni ,..,1 .
2. Вважаємо, що
, якщо ,1
; якщо ,0
)(
ij
ij
ji
x
x
xc
де jx — елемент навчальної послідовності; i , Ni ,..,1 — образи.
3. Будь-яким способом відновлюємо функцію )(xci для всіх елементів
x так, щоб вона була вимірною.
4. Для кожного об’єкта x навчальної послідовності обчислюємо харак-
теристичні функції образів i , Ni ,..,1 за такою формулою:
.випадках інших в 0
;,...,1 ),(min)( якщо ,1
)( ,...,1
Nixcxc
x Nk
i
i
5. Відносимо зображення x до i -го класу, якщо 1)( xi .
Алгоритм описано.
Очевидно, що для елементів навчальної послідовності забезпечується
нульова помилка розпізнавання.
Застосування теорії оптимального розбиття множин до розв’язання задач …
Системні дослідження та інформаційні технології, 2021, № 4 95
Порівняння з методом еталонів. Запропонований метод розв’язання
так само, як і метод еталонів, дозволяє побудувати вирішальне правило, ко-
ли багатовимірні розподіли образів невідомі, а обсяг навчальної послідов-
ності недостатній для отримання оцінок розподілів. Основна відмінність
його від методу еталонів полягає в тому, що функцію належності образу, а,
відповідно, і межі образів можна визначити без визначення функцій належ-
ності елемента послідовності.
Оскільки метод оптимального розбиття множин дозволяє отримати
розв’язання задачі у явному вигляді, то основна обчислювальна складність
зумовлена необхідністю відновити значення функцій втрат )(xci , Ni ,..,1
за їх значеннями у навчальній послідовності.
Крім того, межі між образами визначаються в цьому випадку як геоме-
тричне місце точок, що задовольняють рівність )()( xcxc ji ; цим забезпе-
чується нульова міра перетину образів.
Порівняння з методом потенційних функцій. Застосування методу по-
тенційних функцій до задачі розпізнавання образів в умовах визначеності
ґрунтується на припущенні про те, що у просторі ознак існує така система
функцій )(xi , Ni ,..,1 , що шукану розподільну функцію f можна подати у
вигляді розкладання
N
i
ii xcxf
1
* )()( ,
коефіцієнти якого задовольняють таку умову: існує числова послідовність
}{ i , Ni ,..,1 , де суми
1
2
i
i і 2
1
* )/(
i
iic — скінченні. Тим самим обме-
жується вигляд шуканої розподільної функції.
У разі застосування методу ОРМ жодних обмежень на вигляд розподі-
льної функції немає. Для підмножин i і j , ji , вона згідно з дослі-
дженнями [3] визначається у вигляді
)()()( xcxcxf ji .
Задача розпізнавання нечітких образів
Зауважимо, що задача розпізнавання образів за умов невизначеності нале-
жить до задач штучного інтелекту. Використання нечітких множин у розпі-
знаванні образів включає три основні можливості:
1) нечіткі мітки, які вказують, що належність елементів навчальної по-
слідовності до якої-небудь множини може бути нечіткою, тобто передбача-
ється належність кожного елемента відразу до кількох класів;
2) нечіткі ознаки, задані не конкретними значеннями, а нечіткими
множинами;
3) нечіткі класифікації, що використовують для отримання гнучкого
вичерпного опису реально існуючої класифікації об’єктів.
Постановка задачі. Нехай задано деяку множину об’єктів, що під-
лягають класифікації, а також відоме нечітке відношення, яке визначає різ-
ницю між елементами цієї множини. Необхідно розбити множину на N
нечітких класів так, щоб об’єкти, що містяться в одному класі, були більш
схожими, ніж об’єкти, що містяться в різних класах.
О.М. Кісельова, О.М. Притоманова, Л.Л. Гарт
ISSN 1681–6048 System Research & Information Technologies, 2021, № 4 96
Розв’язання цієї задачі може бути реалізовано у вигляді нечіткого оп-
тимального розбиття множин (аналог задачі A1 із [3]) згідно з наведеною
нижче постановкою.
Задача 2. Це задача знаходження такого нечіткого розбиття множини
nE на N нечітких підмножин N ,...,1 (серед яких можуть бути і по-
рожні), щоб виконувались умови
1sup
ji
x
, Njiji ,...,1,, , ,Ω
1
N
i i
а функціонал
dxxxcF
N
i
iNN
i
)() ,(}),...,{},,...,({
1
11
досягав у певному сенсі «мінімального» значення.
Тут операції об’єднання і перетину розуміються як операції на нечітких
множинах: dxxxc
i
i )(),(
— інтеграл за нечіткої множини [9]; ),( ixc —
дійсна, вимірна за х, опукла за змінною i на множині функція, що ви-
значає нечітке відношення відмінності, задане на множині ; )(x — не-
від’ємна, дійсна, вимірна функція.
Розв’язок цієї задачі, згідно з дослідженнями [7], може мати такий вигляд:
;0= )()(),( ],1,0[)(
;0> )()(),( ,0
;0< )()(),( ,1
)(
*
0
*
*
0
*
*
0
*
*
якщо
якщо
якщо
xxxcx
xxxc
xxxc
x
ii
ii
ii
i
))(min)((
2
1
)(
,...,1
*
0 xcxcx
Nk
ki
, )(min)(
,...,1
xcxc
Nj
ji
,
тут )(* xi — функція належності до нечіткої множини (образу) *
i ,
Ni ,..,1 , значення функції )(x визначається якимось способом або зали-
шається невизначеним, а точки x , для яких 0= )()(),( *
0
* xxxc ii ,
класифікуються як область відмови від розпізнавання.
Далі розглянемо задачу розпізнавання нечітких образів на прикладах
побудови нечітких діаграм Вороного з використанням теорії оптимального
розбиття множин, теорії нечітких множин та нечіткої логіки.
ПОБУДОВА НЕЧІТКИХ ДІАГРАМ ВОРОНОГО НА ОСНОВІ ТЕОРІЇ
ОПТИМАЛЬНОГО РОЗБИТТЯ МНОЖИН
Математичним апаратом побудови діаграм Вороного, який має ряд переваг
порівняно з відомими підходами, описаними в науковій літературі, є теорія
оптимального розбиття множин.
У праці [10] на основі методів теорії ОРМ запропоновано алгоритми
побудови як стандартної діаграми Вороного з чіткими параметрами, так і
різних її узагальнень, а у праці [11] показано, що за відповідного формулю-
вання неперервної лінійної задачі оптимального розбиття множини
розв’язання цієї задачі призводить до того чи іншого варіанта діаграми Во-
Застосування теорії оптимального розбиття множин до розв’язання задач …
Системні дослідження та інформаційні технології, 2021, № 4 97
роного заданої кількості точок-генераторів. При цьому алгоритми
розв’язання неперервних лінійних задач ОРМ не залежать від розмірності
евклідового простору nE , що містить обмежену множину, яка підлягає роз-
биттю на підмножини; не залежить від геометрії множини, що підлягає роз-
биттю; складність реалізації алгоритмів побудови діаграм Вороного на ос-
нові методів теорії ОРМ не збільшується зі збільшенням кількості N точок-
генераторів, а швидкодія допоміжних ітераційних процедур недиферен-
ційовної оптимізації дозволяє розв’язувати задачі великих розмірностей
300,200,100( N і т.д.); алгоритми можуть бути застосовні до побудови не
тільки діаграм Вороного заданої кількості точок-генераторів із фіксованим
їх розташуванням, а й з оптимальним розміщенням цих точок в обмеженій
множині простору nE .
Запропонований у працях [12, 13] підхід має високий ступінь універса-
льності, оскільки дає змогу легко будувати не тільки вже відомі діаграми
Вороного, а і конструювати нові. Зокрема, моделі і методи розв’язання не-
перервних задач ОРМ можна узагальнити на випадки нечіткого задання ви-
хідних параметрів задач або вимоги нечіткого розбиття множини, у резуль-
таті чого результуючі діаграми Вороного також можуть мати нечіткий
характер (нечіткі діаграми Вороного).
За аналогією з класифікацією нечітких задач ОРМ можна виділити два
основні типи нечітких діаграм Вороного: діаграми Вороного з нечіткими
параметрами і діаграми Вороного, у яких множина точок, що утворюють
клітинки Вороного, є нечіткими множинами (нечіткі клітинки). А розв’язання
нечітких задач ОРМ, як і детермінованих задач ОРМ, приводить до побудо-
ви нечітких діаграм Вороного двох основних типів: діаграми Вороного
з нечіткими параметрами і діаграми з нечіткими клітинками Вороного.
У праці [14] описано алгоритм побудови мультиплікативно зваженої
діаграми Вороного за наявності нечітких параметрів з оптимальним розмі-
щенням скінченної кількості N точок-генераторів в обмеженій множині
з n ‐вимірного евклідового простору nE )2( n . Алгоритм розроблено на
основі синтезу методів розв’язання задач теорії ОРМ [3] з нейронечіткими
технологіями [15] і модифікаціями r -алгоритму Н.З. Шора для розв’язання
негладких задач оптимізації [16]. У праці [9] запропоновано алгоритм побу-
дови одного з варіантів нечітких діаграм Вороного, коли множина точок, що
утворюють клітинку Вороного, може бути нечіткою. Алгоритм розроблено
на основі синтезу методів теорії оптимального розбиття множин [3] і теорії
нечітких множин [17].
Універсальність пропонованого підходу до побудови діаграм Вороного
підтверджується ще й тим, що моделі і методи розв’язання неперервних за-
дач ОРМ можуть бути узагальнені на випадок нечіткого задання вихідних
параметрів задачі або вимоги нечіткого розбиття множини, у результаті чого
і результуючі діаграми Вороного можуть мати нечіткий характер. У праці
[18] наведено відповідність між конкретним варіантом діаграми Вороного і
математичною моделлю неперервної задачі ОРМ, у результаті розв’язання
якої може бути отримана ця діаграма.
Таким чином, діаграми Вороного з нечіткими клітинками, як із задани-
ми координатами точок-генераторів, так і з відшуканням їх оптимального
розміщення, можна отримати як розв’язання відповідних неперервних задач
нечіткого оптимального розбиття чіткої множини на нечіткі підмножини.
Методи і алгоритми розв’язання таких задач теоретично обґрунтовані та
сформульовані у праці [9].
О.М. Кісельова, О.М. Притоманова, Л.Л. Гарт
ISSN 1681–6048 System Research & Information Technologies, 2021, № 4 98
Наведемо результати числових експериментів нечіткого оптимального
розбиття одиничного квадрата з евклідовою метрикою за допомогою алго-
ритму [9] для сітки 1024×1024. На рис. 1–3 центри підмножини позначено
«•», сірим кольором — нечітка межа підмножин (клітинок Вороного).
Для інтерпретації отриманих результатів — належності кожного вузла
сітки до будь-якої нечіткої підмножини або до нечіткої межі, уведемо допо-
міжне поняття ступеня недовіри (СН).
Ступінь недовіри [0;1]СН — це мінімальне значення функції належ-
ності деякої нечіткої множини, за якого дана точка може із впевненістю на-
лежати до цієї нечіткої підмножини, тобто, за якого вважаємо цю точку та-
кою, що належить до даної підмножини. Цей показник можна також
інтерпретувати як мінімальний ступінь достовірності факту «дана точка х
належить до даної підмножини», достатній для його прийняття. Чим вищий
ступінь недовіри, тим ширшими будуть області нечіткої межі. Якщо 1CH ,
отримуємо нечітке розбиття, за якого до певної підмножини буде належати
лише його центр і точки ядра, якщо такі з’являться.
Нечіткі діаграми Вороного двох точок-генераторів як результат
розв’язання неперервної задачі оптимального розбиття чіткої множини на
дві нечіткі підмножини зображено на рис. 1. У результаті роботи алгоритму
за 37 ітерацій отримано оптимальні координати розміщення точок-
а б в г
Рис. 1. Діаграми Вороного з нечіткими клітинками та оптимальним розміщенням двох
точок-генераторів: a — 0CH ; б — 55,0CH ; в — 78,0CH ; г — 1CH
а б в г
Рис. 2. Діаграми Вороного з нечіткими клітинками та оптимальним розміщенням трьох
точок-генераторів: a — 0CH ; б — 37,0CH ; в — 67,0CH ; г — 1CH
а б в г
Рис. 3. Діаграми Вороного з нечіткими клітинками та оптимальним розміщенням чоти-
рьох точок-генераторів: a — 0CH ; б — 30,0CH ; в — 50,0CH ; г — 1CH
Застосування теорії оптимального розбиття множин до розв’язання задач …
Системні дослідження та інформаційні технології, 2021, № 4 99
генераторів )86,0;41,0(1 ; )14.0;42.0(2 і мінімальне значення цільово-
го функціонала 206463,0F .
Нечіткі діаграми Вороного трьох точок-генераторів як результат
розв’язання неперервної задачі оптимального розбиття чіткої множини на
три нечіткі підмножини зображено на рис. 2. У результаті роботи алгоритму
за 31 ітерацію отримано оптимальні координати розміщення точок-
генераторів )88,0;27,0(1 ; )57,0;90,0(2 ; )14,0;45,0(3 і мінімальне
значення цільового функціонала 134476,0F .
Нечіткі діаграми Вороного чотирьох точок-генераторів як результат
розв’язання неперервної задачі оптимального розбиття чіткої множини на
чотири нечіткі підмножини зображено на рис. 3. У результаті роботи алгоритму
за 24 ітерації отримано оптимальні координати розміщення точок-генераторів
)76,0;12,0(1 ; )38,0;90,0(2 ; )75,0;90,0(3 ; )28.0;12.0(4 і міні-
мальне значення цільового функціонала 100338,0F .
Із рис. 1–3 видно, що з підвищенням ступеня недовіри СН нечітка межа
збільшується, а форми чітких підмножин наближаються до кола. Це можна по-
яснити тим, що чим ближче вузол сітки до точки-генератора, тим з більшою
достовірністю він може належати до даної нечіткої підмножини (клітинки Во-
роного). Для розбиття на чотири підмножини з підвищенням ступеня недовіри
області підмножин деформуються, вони вже не є колом, а ніби зазнають впливу
інших підмножин. Цікаво також те, що на рис. 3, б, за досить низького рівня
недовіри, першими в область нечіткої межі потрапили точки, що містяться між
усіма підмножинами одразу. Це і не дивно: важко визначитися з підмножиною,
коли вплив усіх їх досить відчутний, кожна намагається «захопити» точку. До-
речно зазначити, що кількість ітерацій та значення цільового функціонала зі
збільшенням кількості підмножин зменшується.
ВИСНОВКИ
На основі викладеного можна виокремити такі переваги застосування мето-
дів теорії оптимального розбиття множин у задачах розпізнавання образів:
дозволяють для досить великої кількості образів (300 і більше, що
залежить тільки від можливості ЕОМ) та будь-якої розмірності простору
ефективно знаходити розподільні гіперповерхні як в аналітичному вигляді,
так і у числовому, при цьому задачі розпізнавання образів розв’язуються без
будь-яких припущень про вигляд розподільної гіперповерхні;
надають змогу побудувати вирішальне правило у випадках, коли ба-
гатовимірний розподіл образів невідомий, а обсяг навчальної послідовності
недостатній;
під час розв’язання задач розпізнавання образів в умовах визначено-
сті забезпечується неперетинність образів за мірою;
моделі та методи теорії оптимального розбиття множин можуть бути
узагальнені для розв’язання задач розпізнавання нечітких образів.
ЛІТЕРАТУРА
1. Е.М. Киселева, Математические методы оптимального разбиения множеств и их
приложения. Дн-ск: ДГУ, 1982, 108 с.
2. E.M. Kiseleva, “The Emergence and Formation of the Theory of Optimal Set Partitioning for
Sets of the n-Dimensional Euclidean Space. Theory and Application”, Journal of Automation and
Information Sciences, no. 50(9), pp. 1–24, 2018.
3. Е.М. Киселева и Н.З. Шор, Непрерывные задачи оптимального разбиения множеств:
теория, алгоритмы, приложения. Киев: Наукова думка, 2005, 564 с.
О.М. Кісельова, О.М. Притоманова, Л.Л. Гарт
ISSN 1681–6048 System Research & Information Technologies, 2021, № 4 100
4. О.М. Кісельова, Становлення та розвиток теорії оптимального розбиття множин.
Теоретичні і практичні застосування: монографія. Дніпро: Ліра, 2018, 532 с.
5. В.И. Васильев, Распознающие системы: справочник; 2-е изд., перераб. и доп. Киев:
Наукова думка, 1983, 422 с.
6. Б.Н. Бублик и Н.Ф. Кириченко, Основы теории управления. Киев: Вища школа, 1975, 327 с.
7. Е.М. Киселева, Л.С. Коряшкина, С.А. Ус, Теория оптимального разбиения множеств в
задачах распознавания образов, анализа и идентификации систем. Днипро: НГУ, 2015, 270 с.
8. Нечеткие множества в моделях управления и искусственного интеллекта / под ред.
Д.А. Поспелова. Москва: Наука, 1986, 312 с.
9. О.М. Кісельова, Л.Л. Гарт, O.M. Притоманова, та Н.В. Балейко, Нечіткі задачі
оптимального розбиття множин: теоретичні основи, алгоритми, застосування:
монографія. Дніпро: Ліра, 2020, 400 с.
10. E.M. Kiseleva and L.S. Koriashkina, “Theory of continuous optimal set partitioning problems as a
universal mathematical formalism for constructing Voronoi diagrams and their generalizations
I. Theoretical foundations”, Cybernetics and Systems Analysis, no. 51(3), pp. 325–335, 2015.
11. E.M. Kiseleva and L.S. Koriashkina, “Theory of continuous optimal set partitioning problems
as a universal mathematical formalism for constructing voronoi diagrams and their
generalizations. II. Algorithms for constructing Voronoi diagrams based on the theory of optimal
set partitioning”, Cybernetics and Systems Analysis, no. 51(4), pp. 489–499, 2015.
12. Е.М. Киселева, Л.Л. Гарт, и О.М. Притоманова, “Алгоритм построения диаграмм Вороного с
оптимальным размещением точек-генераторов на основе теории оптимального разбиения
множеств”, Проблемы управления и информатики, № 2, с. 5–15, 2020.
13. E.M. Kiseleva, L.L. Hart, O.M. Prytomanova, and S.V. Zhuravel, “Construction of a
generalized Voronoi diagram with optimal placement of generator points based on the theory of
optimal set partitioning”, Matematychni Studii, no. 53(1), pp. 109–112, 2020.
14. E. Kiseleva, O. Prytomanova, and V. Padalko, “An algorithm for constructing additive and
multiplicative Voronoi diagrams under uncertainty”, in Babichev S., Lytvynenko V., Wójcik
W., Vyshemyrskaya S. (eds) Lecture Notes in Computational Intelligence and Decision
Making, Springer: Cham, ISDMCI 2020, vol. 1246, pp. 714–727, 2020.
15. E.M. Kiseleva, O.M. Prytomanova, and S.V. Zhuravel, “Algorithm for Solving a Continuous
Problem of Optimal Partitioning with Neurolinguistic Identification of Functions in Target
Functional”, Journal of Automation and Information Science, no. 50(3), pp. 1–20, 2018.
16. N.Z. Shor, Nondifferentiable optimization and polynomial problems. Boston, Dordrecht,
London: Kluwer Acad. Publ., 1998, 412 p.
17. L.A. Zadeh, “Fuzzy sets”, Information and Control, no. 8, pp. 338–353, 1965.
18. В.Г. Падалко, “Структура та основні напрями розвитку математичної теорії
оптимального розбиття множин”, Питання прикладної математики та
математичного моделювання, вип. 21, с. 161–180, 2021.
Надійшла 23.11.2021
INFORMATION ON THE ARTICLE
Elena M. Kiseleva, ORCID: 0000-0003-4303-1707, Oles Honchar Dnipro National Uni-
versity, e-mail: kiseleva47@ukr.net
Olga M. Prytomanova, ORCID: 0000-0003-1878-6120, Oles Honchar Dnipro National
University, e-mail: olga.prytomanova@gmail.com
Liudmyla L. Hart, ORCID: 0000-0003-2617-7851, Oles Honchar Dnipro National
University, e-mail: ll_hart@ukr.net
ПРИМЕНЕНИЕ ТЕОРИИ ОПТИМАЛЬНОГО РАЗБИЕНИЯ МНОЖЕСТВ К
РЕШЕНИЮ ЗАДАЧ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА И РАСПОЗНАВАНИЯ
ОБРАЗОВ / Е.М. Киселева, О.М. Притоманова, Л.Л. Гарт
Аннотация. Обоснована возможность применения математической теории
непрерывных задач оптимального разбиения множеств n-мерного эвклидова
пространства, которые относятся к неклассическим задачам бесконечномерно-
го математического программирования, к решению задач искусственного ин-
теллекта и распознавания образов. Приведены постановки задач распознавания
образов как в условия определенности, так и в условиях неопределенности. Осо-
бое внимание уделено применению методов теории оптимального разбиения
для построения нечетких диаграмм Вороного. Приведены примеры построения
нечетких диаграмм Вороного с оптимальным размещением точек-генераторов.
Ключевые слова: распознавание образов, искусственный интеллект, нечеткая
диаграмма Вороного, точки-генераторы, оптимальное разбиение множеств, бе-
сконечномерное математическое программирование.
Застосування теорії оптимального розбиття множин до розв’язання задач …
Системні дослідження та інформаційні технології, 2021, № 4 101
APPLICATION OF OPTIMAL SET PARTITIONING THEORY TO SOLVING
PROBLEMS OF ARTIFICIAL INTELLIGENCE AND PATTERN RECOGNITION /
E.M. Kiseleva, O.M. Prytomanova, L.L. Hart
Abstract. The paper substantiates the possibility of applying the mathematical
theory of continuous problems of optimal partitioning of sets of n-dimensional
Euclidean space, which belong to the non-classical problems of infinite-dimensional
mathematical programming, to the solution of problems of artificial intelligence and
pattern recognition. The problems of pattern recognition both in conditions of
certainty and in conditions of uncertainty are formulated. A particular attention is
paid to the application of methods of the theory of optimal partitioning for the
construction of fuzzy Voronoi diagrams. Examples of constructing fuzzy Voronoi
diagrams with the optimal placement of generating points are given.
Keywords: pattern recognition, artificial intelligence, fuzzy Voronoi diagram, point
generators, optimal set partitioning, infinite-dimensional mathematical programming.
REFERENCES
1. E.M. Kiseleva, Mathematical Methods for Optimal Set Partitioning and Their Applications [in
rus]. Dn-sk: DGU, 1982, 108 p.
2. E.M. Kiseleva, “The Emergence and Formation of the Theory of Optimal Set Partitioning for
Sets of the n-Dimensional Euclidean Space. Theory and Application”, Journal of Automation and
Information Sciences, no. 50(9), pp. 1–24, 2018.
3. E.M. Kiseleva and N.Z. Shor, Continuous problems of optimal partitioning of sets: theory, al-
gorithms, applications [in rus]. Kyiv: Naukova Dumka, 2005, 564 p.
4. E.M. Kiseleva, The formation and development of the theory of optimal set partitioning. Theoretical
and practical applications: monograph [in ukr]. Dnipro: Lira, 2018, 532 p.
5. V.I. Vasiliev, Recognising Systems: A Handbook [in rus]. Kyiv: Naukova Dumka, 1983, 422 p.
6. B.N. Bublik and N.F. Kirichenko, Fundamentals of control theory [in rus]. Kyiv: Vishcha
shkola, 1975, 327 p.
7. E.M. Kiseleva, L.S. Koriashkina, and S.A. Us, Optimal Set Partitioning Theory In Pattern
Recognition, Analysis And Identification Problems [in rus]. Dnipro: NGU, 2015, 270 p.
8. Fuzzy Sets In Control Models And Artificial Intelligence [in rus]; ed. by D.A. Pospelov.
Moskva: Nauka, 1986, 312 p.
9. E.M. Kiseleva, L.L. Hart, O.M. Prytomanova, and N.V. Baleiko, Fuzzy problems of optimal
partitioning of sets: theoretical foundations, algorithms, applications: monograph [in ukr].
Dnipro: Lyra, 2020, 400 p.
10. E.M. Kiseleva and L.S. Koriashkina, “Theory of continuous optimal set partitioning problems
as a universal mathematical formalism for constructing Voronoi diagrams and their
generalizations I. Theoretical foundations”, Cybernetics and Systems Analysis, no. 51(3),
pp.325–335, 2015.
11. E.M. Kiseleva and L.S. Koriashkina, “Theory of continuous optimal set partitioning problems
as a universal mathematical formalism for constructing voronoi diagrams and their
generalizations. II. Algorithms for constructing Voronoi diagrams based on the theory of
optimal set partitioning”, Cybernetics and Systems Analysis, no. 51(4), pp. 489–499, 2015.
12. E.M. Kiseleva, O.M. Prytomanova, and L.L. Hart, “Algorithm for constructing voronoi
diagrams with optimal placement of generator points based on optimal set partitioning
theory”, Journal of Automation and Information Science, no. 52(3), pp. 1–12, 2020.
13. E.M. Kiseleva, L.L. Hart, O.M. Prytomanova, and S.V. Zhuravel, “Construction of a
generalized Voronoi diagram with optimal placement of generator points based on the theory
of optimal set partitioning”, Matematychni Studii, no. 53(1), pp. 109–112, 2020.
14. E. Kiseleva, O. Prytomanova, and V. Padalko, “An algorithm for constructing additive and
multiplicative Voronoi diagrams under uncertainty”, in Babichev S., Lytvynenko V.,
Wójcik W., Vyshemyrskaya S. (eds) Lecture Notes in Computational Intelligence and Decision
Making, Springer: Cham, ISDMCI 2020, vol. 1246, pp. 714–727, 2020.
15. E.M. Kiseleva, O.M. Prytomanova, and S.V. Zhuravel, “Algorithm for Solving a Continuous
Problem of Optimal Partitioning with Neurolinguistic Identification of Functions in Target
Functional”, Journal of Automation and Information Science, no. 50(3), pp. 1–20, 2018.
16. N.Z. Shor, Nondifferentiable optimization and polynomial problems. Boston, Dordrecht,
London: Kluwer Acad. Publ., 1998, 412 p.
17. L.A. Zadeh, “Fuzzy sets”, Information and Control, no. 8, pp. 338–353, 1965.
18. V.G. Padalko, “Structure and main directions of development of the mathematical theory of
optimal set partitioning [in ukr]”, Problems of applied mathematics and mathematical model-
ling, vol. 21, pp. 161–180, 2021.
|
| id | journaliasakpiua-article-252300 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2025-07-17T10:27:46Z |
| publishDate | 2021 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/6e/02e5cddd75a66f07d83a1358256de76e.pdf |
| spelling | journaliasakpiua-article-2523002022-06-20T14:19:48Z Application of optimal set partitioning theory to solving problems of artificial intelligence and pattern recognition Применение теории оптимального разбиения множеств к решению задач искусственного интеллекта и распознавания образов Застосування теорії оптимального розбиття множин до розв’язання задач штучного інтелекту та розпізнавання образів Kiseleva, Elena Prytomanova, Olga Hart, Liudmyla розпізнавання образів штучний інтелект нечітка діаграма Вороного точки-генератори оптимальне розбиття множин нескінченновимірне математичне програмування pattern recognition artificial intelligence fuzzy Voronoi diagram point generators optimal set partitioning infinite-dimensional mathematical programming распознавание образов искусственный интеллект нечеткая диаграмма Вороного точки-генераторы оптимальное разбиение множеств бесконечномерное математическое программирование The paper substantiates the possibility of applying the mathematical theory of continuous problems of optimal partitioning of sets of n-dimensional Euclidean space, which belong to the non-classical problems of infinite-dimensional mathematical programming, to the solution of problems of artificial intelligence and pattern recognition. The problems of pattern recognition both in conditions of certainty and in conditions of uncertainty are formulated. A particular attention is paid to the application of methods of the theory of optimal partitioning for the construction of fuzzy Voronoi diagrams. Examples of constructing fuzzy Voronoi diagrams with the optimal placement of generating points are given. Обоснована возможность применения математической теории непрерывных задач оптимального разбиения множеств n-мерного эвклидова пространства, которые относятся к неклассическим задачам бесконечномерного математического программирования, к решению задач искусственного интеллекта и распознавания образов. Приведены постановки задач распознавания образов как в условия определенности, так и в условиях неопределенности. Особое внимание уделено применению методов теории оптимального разбиения для построения нечетких диаграмм Вороного. Приведены примеры построения нечетких диаграмм Вороного с оптимальным размещением точек-генераторов. Обґрунтовано можливість застосування математичної теорії неперервних задач оптимального розбиття множин n-вимірного евклідового простору, які належать до некласичних задач нескінченновимірного математичного програмування, до розв’язання задач штучного інтелекту та розпізнавання образів. Наведено постановки задач розпізнавання образів як в умовах визначеності, так і в умовах невизначеності, підходи до їх розв’язання із застосуванням теорії оптимального розбиття множин. Особливу увагу приділено застосуванню методів теорії оптимального розбиття для побудови нечітких діаграм Вороного. Наведено приклади побудови нечітких діаграм Вороного з оптимальним розміщенням точок-генераторів. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2021-12-22 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/252300 10.20535/SRIT.2308-8893.2021.4.07 System research and information technologies; No. 4 (2021); 91-101 Системные исследования и информационные технологии; № 4 (2021); 91-101 Системні дослідження та інформаційні технології; № 4 (2021); 91-101 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/252300/249601 |
| spellingShingle | розпізнавання образів штучний інтелект нечітка діаграма Вороного точки-генератори оптимальне розбиття множин нескінченновимірне математичне програмування Kiseleva, Elena Prytomanova, Olga Hart, Liudmyla Застосування теорії оптимального розбиття множин до розв’язання задач штучного інтелекту та розпізнавання образів |
| title | Застосування теорії оптимального розбиття множин до розв’язання задач штучного інтелекту та розпізнавання образів |
| title_alt | Application of optimal set partitioning theory to solving problems of artificial intelligence and pattern recognition Применение теории оптимального разбиения множеств к решению задач искусственного интеллекта и распознавания образов |
| title_full | Застосування теорії оптимального розбиття множин до розв’язання задач штучного інтелекту та розпізнавання образів |
| title_fullStr | Застосування теорії оптимального розбиття множин до розв’язання задач штучного інтелекту та розпізнавання образів |
| title_full_unstemmed | Застосування теорії оптимального розбиття множин до розв’язання задач штучного інтелекту та розпізнавання образів |
| title_short | Застосування теорії оптимального розбиття множин до розв’язання задач штучного інтелекту та розпізнавання образів |
| title_sort | застосування теорії оптимального розбиття множин до розв’язання задач штучного інтелекту та розпізнавання образів |
| topic | розпізнавання образів штучний інтелект нечітка діаграма Вороного точки-генератори оптимальне розбиття множин нескінченновимірне математичне програмування |
| topic_facet | розпізнавання образів штучний інтелект нечітка діаграма Вороного точки-генератори оптимальне розбиття множин нескінченновимірне математичне програмування pattern recognition artificial intelligence fuzzy Voronoi diagram point generators optimal set partitioning infinite-dimensional mathematical programming распознавание образов искусственный интеллект нечеткая диаграмма Вороного точки-генераторы оптимальное разбиение множеств бесконечномерное математическое программирование |
| url | https://journal.iasa.kpi.ua/article/view/252300 |
| work_keys_str_mv | AT kiselevaelena applicationofoptimalsetpartitioningtheorytosolvingproblemsofartificialintelligenceandpatternrecognition AT prytomanovaolga applicationofoptimalsetpartitioningtheorytosolvingproblemsofartificialintelligenceandpatternrecognition AT hartliudmyla applicationofoptimalsetpartitioningtheorytosolvingproblemsofartificialintelligenceandpatternrecognition AT kiselevaelena primenenieteoriioptimalʹnogorazbieniâmnožestvkrešeniûzadačiskusstvennogointellektairaspoznavaniâobrazov AT prytomanovaolga primenenieteoriioptimalʹnogorazbieniâmnožestvkrešeniûzadačiskusstvennogointellektairaspoznavaniâobrazov AT hartliudmyla primenenieteoriioptimalʹnogorazbieniâmnožestvkrešeniûzadačiskusstvennogointellektairaspoznavaniâobrazov AT kiselevaelena zastosuvannâteorííoptimalʹnogorozbittâmnožindorozvâzannâzadačštučnogoíntelektutarozpíznavannâobrazív AT prytomanovaolga zastosuvannâteorííoptimalʹnogorozbittâmnožindorozvâzannâzadačštučnogoíntelektutarozpíznavannâobrazív AT hartliudmyla zastosuvannâteorííoptimalʹnogorozbittâmnožindorozvâzannâzadačštučnogoíntelektutarozpíznavannâobrazív |