Норкін, Володимир ІвановичКозирєв, Антон Юрійович2026-08-192026-08-192026Козирєв, А. Ю. Методи стохастичної квантизації для масштабованого кластерного аналізу великих даних : дис. … д-ра філософії : 113 Прикладна математика / Козирєв Антон Юрійович. - Київ, 2026. - 177 с.https://ela.kpi.ua/handle/123456789/82578Козирєв А.Ю. Методи стохастичної квантизації для масштабованого кластерного аналізу великих даних. – Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 113 «Прикладна математика». – Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», Київ. – 2026. Мета роботи – підвищення якості кластеризації та зменшення обчислювальних витрат під час оброблення великих даних, а також забезпечення стійкого до розподільного дрейфу ітеративного оновлення індексних структур у векторних базах даних без потреби в їх періодичній повній перебудові. Для досягнення мети в роботі визначено наступні наукові завдання: аналіз існуючих методів кластеризації та виявлення їх переваг і недоліків при вирішенні задач кластерного аналізу; розробка методу стохастичної квазіградієнтної кластеризації на основі транспортної задачі з рухомими центрами за допомогою стохастичної апроксимації Кіфера-Вольфовіца; виведення умов збіжності запропонованого методу та дослідження швидкості збіжності з використанням елементів негладкого аналізу; запровадження структури даних стохастичного інвертованого файлового індексу на основі існуючої структури даних з використанням запропонованого методу для розбиття метричного простору вхідних даних; проведення експериментальних досліджень на відкритих наборах даних Iris, MNIST та ImageNet з оцінкою точності за допомогою статистичних метрик, таких як індекс Ранда та середньоквадратична помилка. Наукова новизна. У дисертації одержано нові наукові результати: 1. Задачу кластеризації зведено до нової неопуклої негладкої задачі стохастичної оптимізації, що дозволяє для її розв'язання застосувати сучасні адаптивні методи стохастичної оптимізації, які використовуються для навчання глибинних нейронних мереж; 2. Розроблено новий метод стохастичної квазіградієнтної кластеризації, який використовує субдиференційовану цільову функцію транспортної відстані та стохастичну апроксимацію, що дозволяє оцінювати оптимальні розміщення центроїдів лише з використанням підмножини навчальних даних і потребує меншу кількість обчислювальних ресурсів. Запропонований метод має теоретично доведені асимптотичні гарантії збіжності на основі властивостей узагальненої диференційованості цільової функції; 3. Враховуючи, що метод стохастичної квазіградієнтної кластеризації має доведену збіжність лише до локальних екстремумів цільової функції, запропоновано новий метод початкової ініціалізації центроїдів за допомогою жадібного алгоритму в комбінації з дискретною оптимізацією та модифікацію стохастичної квазіградієнтної кластеризації з використанням мета-евристичного методу диференціальної еволюції, що дозволяє здійснювати пошук глобальних екстремумів негладкої неопуклої цільової функції та підвищити якість кластеризації за рахунок уникнення збіжності до неоптимальних локальних розв'язків; 4. Удосконалено скінченно-різницевий метод оптимізації негладких неопуклих цільових функцій за допомогою методу згладжування (усереднення) функцій для пошуку точок екстремумів, використовуючи скінченно-різницеву апроксимацію градієнтів вздовж стохастичних напрямків. Теоретично доведено сублінійну швидкість збіжності стохастичного скінченно-різницевого методу для Ліпшицевих опуклих функцій; 5. Удосконалено структуру стохастичного інвертованого файлового індексу для інкрементного індексування векторних даних, де для індексації використовується запропонований метод стохастичної квазіградієнтної кластеризації, в умовах динамічної зміни відповідного розподілу даних через сезонні зміни, соціологічні фактори, тощо. Проблематика. Кластерний аналіз є основою сучасних систем штучного інтелекту, зокрема архітектур з пошуком за схожістю (RAG, RETRO) та векторних баз даних мільярдного масштабу, де інвертовані файлові індекси будуються переважно методом -середніх. Існуючі методи кластеризації на основі центроїдів мають низку суттєвих обмежень. По-перше, класичні методи -середніх, -медіан, гармонічних та нечітких -середніх потребують обчислювальної складності та пам'яті порядку на ітерацію, оскільки оновлення центроїдів вимагає повного проходу по всьому набору з векторів розмірності , що стає важкою задачею на масштабах порядку - на типовому обчислювальному обладнанні. По-друге, цільова функція внутрішньокластерної суми квадратів є неопуклою та задача пошуку її глобального мінімуму NP-важка, а класичні детерміновані методи збігаються лише до локального оптимуму, який сильно залежить від початкової ініціалізації центроїдів. Навіть удосконалення як -середніх++ забезпечують лише гарантію. По-третє, після побудови індексу його центроїди та межі розбиття залишаються незмінними, що в умовах розподільного дрейфу призводить до зростання помилки квантизації, дисбалансу розмірів кластерів і деградації якості пошуку. Єдиним поширеним засобом протидії є періодична повна перебудова індексу, обчислювальна вартість якої при мільярдних масштабах сягає декількох діб. Крім того, цільова функція кластеризації є негладкою через наявність функції мінімуму, що унеможливлює пряме застосування класичних градієнтних методів, а в задачах кластеризації даних високої розмірності проявляється «прокляття розмірності», за якого відстань втрачає здатність розрізняти об'єкти у вихідному просторі ознак. Запропоноване вирішення. Для подолання зазначених проблем у роботі задачу оптимальної кластеризації переформульовано як транспортну задачу з рухомими центрами через відстань Канторовича-Рубінштейна (Вассерштейна) між емпіричним розподілом даних та дискретним розподілом, що його апроксимують центроїдів. Аналітичне виключення транспортних змінних дозволяє звести вихідну задачу до неопуклої негладкої задачі стохастичної оптимізації. Застосування узагальненого диференціального числення до субдиференціала мінімуму дозволяє побудувати незміщений стохастичний субградієнт лише за одним випадковим спостереженням і визначити метод стохастичної квазіградієнтної кластеризації, у якому на кожній ітерації оновлюється лише центроїд, найближчий до вибраного зразка, що зменшує вимоги до пам'яті з до на крок. На цій основі розроблено адаптивні варіанти, що адаптивно масштабують крок для кожного центроїда та автоматично балансують навантаження між часто й рідко оновленими кластерами. Замість імовірнісної ініціалізації -середніх++ запропоновано детерміновану жадібну агрегацію близьких даних із розв'язанням задачі цілочисельного лінійного програмування з обмеженням на потужність множини центроїдів. Для отриманого методу аналітично доведено збіжність послідовності центроїдів до зв'язної компоненти множини стаціонарних точок за умов Роббінса-Монро на крок і компактності допустимої області. Структуру даних стохастичного інвертованого файлового індекса побудовано на основі еквівалентності задачі побудови розбиттів класичного індекса та задачі стохастичної квазіградієнтної кластеризації при й рівномірних вагах: кожне додавання нового вектора супроводжується стохастичним коригуванням найближчого центроїда з використанням адаптивної оцінки моментів, що забезпечує безперервну адаптацію індексу до зміни розподілу даних та сумісність з квантизацією добутку. Для подолання «прокляття розмірності» метод стохастичної квазіградієнтної кластеризації поєднано з трійковою нейронною мережею, яка через контрастне навчання відображає вихідні високовимірні дані в низьковимірний латентний простір, придатний для ефективної кластеризації. Практичне значення отриманих результатів полягає в експериментальному підтвердженні збіжності запропонованого методу квантизації на відкритих наборах даних з порівнянням швидкості збіжності та точності оптимальних центрів. В експериментальних результатах показано, що запропонований метод в середньому скорочує кількість обчислень функції відстань приблизно на 70% порівняно з числом обчислень класичного методу кластерного аналізу -середніх, який є стандартним методом кластеризації на основі центроїдів. Масштабованість методу продемонстрована на відкритих наборах даних з варіацією від до елементів. Запропонований метод кластеризації може бути застосований для ітеративної індексації даних в дуже великих базах даних в умовах нестаціонарності. Також він може бути застосований для ітеративної апроксимації неперервних та дискретних ймовірнісних розподілів, для розв’язання задач логістики, розміщення складів, сервісних центрів. Результати роботи впроваджено у навчальний процес кафедри штучного інтелекту ННІПСА Національного технічного університету України «Київський політехнічний інститут імені Ігоря Сікорського» в рамках освітнього компонента «Сучасні методи оптимізації» для здобувачів першого (бакалаврського) рівня вищої освіти за освітньо-професійною програмою «Системи та методи штучного інтелекту» (лекції 6, 10), що відображено в силабусі відповідної освітньої компоненти, ухваленому на засіданні кафедри штучного інтелекту (протокол №14 від 11.06.2024) та погодженому методичною комісією ННІПСА (протокол №10 від 24.06.2024), (url: https://ai.kpi.ua/ua/bachelors/syllabus/2024- 2025/28343_3_suchasni_metody_optymizatsii.pdf). Висновки. У дисертаційній роботі побудовано цілісну математичну та програмну основу для масштабованого кластерного аналізу великих даних, що ґрунтується на зведенні задачі оптимальної кластеризації до неопуклої негладкої задачі стохастичної оптимізації та застосуванні до неї сучасних адаптивних методів, перенесених із галузі глибинного навчання. Запропонований метод стохастичної квазіградієнтної кластеризації та його адаптивні модифікації забезпечують зменшення вимог до пам'яті з до на ітерацію та скорочення кількості обчислень функції відстані приблизно на 70% порівняно з класичним методом -середніх при збереженні точності квантизації, а також збіжність методу до стаціонарної точки доведено аналітично за умов Роббінса-Монро. Розроблена структура даних стохастичного інвертованого файлового індексу вперше надає теоретично обґрунтований механізм інкрементного, стійкого до розподільного дрейфу обслуговування інвертованих файлових індексів у векторних базах даних, що усуває потребу в періодичній повній перебудові індексу та інтегрується з існуючими системами наближеного пошуку (зокрема FAISS) і продуктовою квантизацією. Поєднання методу стохастичної квазіградієнтної кластеризації з контрастним навчанням трійкових нейронних мереж дозволяє подолати «прокляття розмірності» та досягти на наборі MNIST якості кластеризації, порівнянної з повністю керованими базовими методами, зберігаючи стійкість в умовах обмеженого розмічування даних. Практична значущість роботи підтверджена застосуваннями до стиснення кольорових зображень з втратами, потокової кластеризації в умовах сезонних та соціологічних змін розподілу даних, а також інтеграції з системами векторного пошуку та підтримки прийняття рішень; результати впроваджено в навчальний процес кафедри штучного інтелекту ННІПСА КПІ ім. Ігоря Сікорського. Перспективними напрямами подальших досліджень є поширення розробленого стохастичного підходу на моделі гаусівських сумішей, методи кластеризації на основі щільності тощо.177 с.ukтеорія оптимізаціїстохастична оптимізаціянегладка оптимізаціяадаптивні градієнтні методикластерний аналізвекторна квантизація-середніхмашинне навчанняглибинне навчанняаналіз данихстатистикаштучний інтелектінтелектуальний аналіз текстусемантична нейронна мережаoptimization theorystochastic optimizationnon-smooth optimizationadaptive gradient methodscluster analysisvector quantization-means methodmachine learningdeep learningdata analysisstatisticsartificial intelligencetext miningsemantic networkThesis Doctoral004.8:519.85