Методи стохастичної квантизації для масштабованого кластерного аналізу великих даних
| dc.contributor.advisor | Норкін, Володимир Іванович | |
| dc.contributor.author | Козирєв, Антон Юрійович | |
| dc.date.accessioned | 2026-08-19T07:05:15Z | |
| dc.date.available | 2026-08-19T07:05:15Z | |
| dc.date.issued | 2026 | |
| dc.description.abstract | Козирєв А.Ю. Методи стохастичної квантизації для масштабованого кластерного аналізу великих даних. – Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 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 якості кластеризації, порівнянної з повністю керованими базовими методами, зберігаючи стійкість в умовах обмеженого розмічування даних. Практична значущість роботи підтверджена застосуваннями до стиснення кольорових зображень з втратами, потокової кластеризації в умовах сезонних та соціологічних змін розподілу даних, а також інтеграції з системами векторного пошуку та підтримки прийняття рішень; результати впроваджено в навчальний процес кафедри штучного інтелекту ННІПСА КПІ ім. Ігоря Сікорського. Перспективними напрямами подальших досліджень є поширення розробленого стохастичного підходу на моделі гаусівських сумішей, методи кластеризації на основі щільності тощо. | |
| dc.description.abstractother | Kozyriev A.Yu. Methods of Stochastic Quantization for Scalable Cluster Analysis of Big Data. – Qualifying scientific work as a manuscript. Thesis for the degree of Doctor of Philosophy in the specialty 113 «Applied Mathematics». – National Technical University of Ukraine «Igor Sikorsky Kyiv Polytechnic Institute», Kyiv. – 2026. The purpose of the work is to improve the quality of clustering and reduce computational costs when processing big data, as well as to ensure iterative update of index structures in vector databases that is robust to distributional drift without the need for their periodic complete reconstruction. To achieve the stated purpose, the following research tasks have been defined: conduct an analysis of existing clustering methods and identify their advantages and disadvantages in solving cluster analysis problems; develop the stochastic quasigradient clustering method based on the transportation problem with moving centers using the Kiefer–Wolfowitz stochastic approximation; derive convergence conditions of the proposed method and investigate the convergence rate using elements of non-smooth analysis; introduce a stochastic inverted file index data structure based on an existing data structure using the proposed method to partition the metric space of the input data; conduct experimental studies on open datasets Iris, MNIST, and ImageNet and assess the accuracy of the obtained results using statistical metrics such as the Rand index and mean squared error. Scientific novelty. The thesis presents the following novel scientific results: 1. The clustering problem is reduced to a new non-convex non-smooth stochastic optimization problem, which allows for its solution to apply modern adaptive stochastic optimization methods used for training deep neural networks; 2. A new stochastic quasigradient clustering method is developed, which uses a subdifferentiated transport distance objective function and stochastic approximation, which allows estimating optimal centroid placements using only a subset of the training data and requires fewer computational resources. The proposed method has theoretically proven asymptotic convergence guarantees based on the properties of generalized differentiability of the objective function; 3. Considering that the stochastic quasi-gradient clustering method has proven convergence only to local extrema of the objective function, a new method of initial centroid initialization using a greedy algorithm in combination with discrete optimization and a modification of stochastic quasigradient clustering using the metaheuristic method of differential evolution is proposed, which allows searching for global extrema of a nonsmooth non-convex objective function and improving the quality of clustering by avoiding convergence to suboptimal local solutions; 4. The finite-difference method of optimizing non-smooth non-convex objective functions is improved using the method of smoothing (averaging) functions to search for extrema points, using finite-difference approximation of gradients along stochastic directions. The sublinear convergence rate of the stochastic finite-difference method for Lipschitz convex functions has been theoretically proven; 5. The structure of the stochastic inverted file index for incremental indexing of vector data has been improved, where the proposed stochastic quasi-gradient clustering method is used for indexing, under conditions of dynamic change of the corresponding data distribution due to seasonal changes, sociological factors, etc. Problem statement. Cluster analysis constitutes the foundation of modern artificial intelligence systems, particularly similarity-search architectures (RAG, RETRO) and billion-scale vector databases, where inverted file indices are constructed predominantly by means of the -means method. Existing centroid-based clustering methods exhibit a number of substantial limitations. First, the classical -means, - medians, harmonic and fuzzy -means methods exhibit per-iteration computational and memory complexity of order , since updating the centroids requires a full pass over the entire set of vectors of dimension , which becomes infeasible on commodity hardware as reaches - . Second, the within-cluster sum-of-squares objective is non-convex, finding its global optimum is NP-hard, and deterministic methods converge only to a local optimum whose quality depends strongly on the initial choice of centroids; even refinements such as -means++ provide only an guarantee. Third, once an stochastic inverted file index has been built, its centroids and partition boundaries remain frozen, so that under dynamic distributional drift (seasonal changes, sociological factors, evolving content) the quantization error grows, the partition sizes become unbalanced, and the quality of downstream retrieval and generative models deteriorates; the only commonly used remedy is periodic full re-indexing, whose computational cost at billionvector scale amounts to several days. In addition, the centroid-based clustering objective is non-smooth because of the minimum function, which precludes direct application of classical gradient methods, while high-dimensional clustering is further impeded by the curse of dimensionality, under which distance loses its discriminative power in the raw feature space. Proposed solution. To overcome the above problems, the optimal clustering problem is reformulated as a transportation problem with movable centers based on the Kantorovich-Rubinstein (Wasserstein) distance between the empirical data distribution and the discrete distribution induced by centroids. Analytical elimination of the transport variables reduces the original problem to a non-convex non-smooth stochastic optimization problem . Applying the generalized differentiation to the subdifferential of the minimum function makes it possible to construct an unbiased stochastic subgradient from a single random sample and to define the stochastic quasigradient clustering method, in which at every iteration only the centroid nearest to the drawn sample is updated; this reduces the per-step memory requirement from to . On this basis, adaptive variants have been developed, which adaptively rescale the step size for each centroid and automatically balance the load between frequently and rarely updated clusters. Instead of the probabilistic -means++ initialization, a deterministic greedy aggregation of nearby data combined with a cardinality-constrained integer linear program over the candidate centers has been proposed. For the resulting method, almost-sure convergence of the centroid sequence to a connected component of the set of stationary points has been proved analytically under Robbins-Monro conditions on the step size and compactness of the feasible region; the result has been extended to the adaptive variant. The stochastic inverted file index data structure is constructed by exploiting the equivalence between inverted file index codebook training and the stochastic quasigradient clustering objective with and uniform weights: each insertion of a new vector is accompanied by an stochastic update of the nearest centroid using the adaptive moments, which provides continuous adaptation of the index to data-distribution drift and compatibility with product quantization. To overcome the curse of dimensionality, the stochastic quasigradient clustering method is composed with a triplet neural network that, via contrastive learning, maps the original high-dimensional data into a low-dimensional latent space suitable for effective clustering. The practical significance of the results obtained lies in the experimental confirmation of convergence of the proposed quantization method on open datasets with comparison of convergence speed and accuracy of optimal centers. Experimental results show that, on average, the proposed method reduces the number of distance-function evaluations by approximately 70% compared to the number of evaluations performed by the classical -means cluster analysis method, which is the standard centroid-based clustering method. The scalability of the method has been demonstrated on open datasets ranging in size from to elements. The proposed clustering method can be applied to iterative data indexing in very large databases under conditions of data changes. It can also be applied to iterative approximation of continuous and discrete probability distributions, and to solving problems of logistics, warehouse placement, and service-center location. The results of the work have been incorporated into the educational process of the Department of Artificial Intelligence of the Educational and Scientific Institute for Applied System Analysis (ESIASA) of the National Technical University of Ukraine «Igor Sikorsky Kyiv Polytechnic Institute» within the educational component «Modern Optimization Methods» for first (bachelor's) level higher education applicants of the educational-professional program «Systems and Methods of Artificial Intelligence» (lectures 6, 10), which is reflected in the syllabus of the corresponding educational component, approved at the meeting of the Department of Artificial Intelligence (protocol No. 14 of 11.06.2024) and by the methodological commission of ESIASA (protocol No. 10 of 24.06.2024), (url: https://ai.kpi.ua/ua/bachelors/syllabus/2024- 2025/28343_3_suchasni_metody_optymizatsii.pdf). Conclusions. The thesis provides a unified mathematical and software foundation for scalable centroid-based cluster analysis of big data, based on the reduction of the optimal clustering problem to a non-convex non-smooth stochastic optimization problem and the application to it of modern adaptive methods transferred from the field of deep learning. The proposed stochastic quasigradient clustering method and its adaptive modifications reduce the per-iteration memory requirement from to and lower the number of distance-function evaluations by approximately 70% with respect to the classical -means method while preserving quantization accuracy; almost-sure convergence of the method to a stationary point has been proved analytically under Robbins-Monro conditions. The developed stochastic inverted file index data structure provides, for the first time, a theoretically grounded mechanism for incremental, driftresilient maintenance of inverted file indices in vector databases, eliminating the need for periodic full re-indexing and integrating seamlessly with existing approximate-nearestneighbor systems (such as FAISS) and with product quantization. The combination of stochastic quasigradient clustering with contrastive triplet-network learning has made it possible to overcome the «curse of dimensionality» and to attain MNIST clustering quality comparable with fully supervised baselines, while remaining robust under limited data labeling. The practical significance of the work has been confirmed by applications to lossy color image compression, streaming clustering under seasonal and sociological distribution changes, and integration with vector-search and decision-support systems; the results have been incorporated into the educational process of the Department of Artificial Intelligence of ESIASA at the Igor Sikorsky Kyiv Polytechnic Institute. Promising directions for further research include the extension of the developed stochastic approach to Gaussian mixture models, density-based clustering methods etc. | |
| dc.format.extent | 177 с. | |
| dc.identifier.citation | Козирєв, А. Ю. Методи стохастичної квантизації для масштабованого кластерного аналізу великих даних : дис. … д-ра філософії : 113 Прикладна математика / Козирєв Антон Юрійович. - Київ, 2026. - 177 с. | |
| dc.identifier.uri | https://ela.kpi.ua/handle/123456789/82578 | |
| dc.language.iso | uk | |
| dc.publisher | КПІ ім. Ігоря Сікорського | |
| dc.publisher.place | Київ | |
| dc.subject | теорія оптимізації | |
| dc.subject | стохастична оптимізація | |
| dc.subject | негладка оптимізація | |
| dc.subject | адаптивні градієнтні методи | |
| dc.subject | кластерний аналіз | |
| dc.subject | векторна квантизація | |
| dc.subject | -середніх | |
| dc.subject | машинне навчання | |
| dc.subject | глибинне навчання | |
| dc.subject | аналіз даних | |
| dc.subject | статистика | |
| dc.subject | штучний інтелект | |
| dc.subject | інтелектуальний аналіз тексту | |
| dc.subject | семантична нейронна мережа | |
| dc.subject | optimization theory | |
| dc.subject | stochastic optimization | |
| dc.subject | non-smooth optimization | |
| dc.subject | adaptive gradient methods | |
| dc.subject | cluster analysis | |
| dc.subject | vector quantization | |
| dc.subject | -means method | |
| dc.subject | machine learning | |
| dc.subject | deep learning | |
| dc.subject | data analysis | |
| dc.subject | statistics | |
| dc.subject | artificial intelligence | |
| dc.subject | text mining | |
| dc.subject | semantic network | |
| dc.subject.udc | 004.8:519.85 | |
| dc.title | Методи стохастичної квантизації для масштабованого кластерного аналізу великих даних | |
| dc.title.alternative | Methods of Stochastic Quantization for Scalable Cluster Analysis of Big Data | |
| dc.type | Thesis Doctoral |
Файли
Контейнер файлів
1 - 1 з 1
Вантажиться...
- Назва:
- Kozyriev_dys.pdf
- Розмір:
- 10.55 MB
- Формат:
- Adobe Portable Document Format
Ліцензійна угода
1 - 1 з 1
Ескіз недоступний
- Назва:
- license.txt
- Розмір:
- 8.98 KB
- Формат:
- Item-specific license agreed upon to submission
- Опис: