Кластеризация с использованием методов удовлетворения табличных ограничений
Автор: Зуенко А.А., Зуенко О.Н.
Журнал: Онтология проектирования @ontology-of-designing
Рубрика: Инжиниринг онтологий
Статья в выпуске: 3 (53) т.14, 2024 года.
Бесплатный доступ
Исследования посвящены развитию методов кластерного анализа, в частности методов кластеризации с частичным привлечением учителя, в которых при отнесении объектов к классам анализируются фоновые знания из предметной области. Традиционный подход к решению рассматриваемой задачи состоит в модификации существующих методов кластеризации, большинство из которых является методами локального поиска. В статье развивается подход к систематическому поиску оптимальных разбиений в рамках парадигмы программирования в ограничениях. Оригинальность представленных исследований состоит в том, что задачу кластеризации предложено решать как задачу удовлетворения ограничений, причём для моделирования ряда основных и дополнительных условий используются специализированные табличные ограничения - смарт -таблицы D -типа. Для организации процедур логического вывода на смарт -таблицах D -типа используются правила редукции табличных ограничений. Обсуждаются преимущества данного подхода. Показано, как анализ одного из оптимальных решений может помочь в выявлении объектов, лежащих на границе кластеров, и объектов, принадлежащих одному и тому же кластеру при любом оптимальном разбиении.
Программирование в ограничениях, табличные ограничения, кластеризация, машинное обучение, интеллектуальный анализ данных
Короткий адрес: https://sciup.org/170206318
IDR: 170206318 | DOI: 10.18287/2223-9537-2024-14-3-391-407
Список литературы Кластеризация с использованием методов удовлетворения табличных ограничений
- Grossi V., Romei A., Turini F. Survey on using constraints in data mining // Data Mining and Knowledge Discovery. 2017. № 2. P.424-464. DOI: 10.1007/s10618-016-0480-z.
- Dao T.-B.-H., Duong K.-C., Vrain C. Constrained clustering by constraint programming. // Artificial Intelligence. 2017. № 244. P.70-94. DOI: 10.1016/j.artint.2015.05.006.
- Qin Y., Ding S., Wang L., Wang Y. Research Progress on Semi-Supervised Clustering. // Cognitive Computation. 2019. №11. P.599-612. DOI: 10.1007/s12559-019-09664-w.
- Falkner J.K., Thyssens D., Bdeir A., Schmidt-Thieme L. Learning to Control Local Search for Combinatorial Optimization // ECML PKDD 2022: Machine Learning and Knowledge Discovery in Databases, (Grenoble, France 2022 September 19-23). P.361-376. DOI: 10.1007/978-3-031-26419-1_22.
- Gabbrielli M., Martini S. Programming Languages: Principles and Paradigms. Cham: Springer, 2023. 561 p.
- Зуенко А.А. Компактное представление ограничений на основе новой интерпретации понятия «кортеж многоместного отношения» // Онтология проектирования. 2020. Т.10, №4(38). С.503-515. DOI: 10.18287/2223-9537-2020-10-4-503-515.
- Зуенко А.А., Зуенко О.Н. Поиск зависимостей в данных на основе методов удовлетворения табличных ограничений // Онтология проектирования. 2023. Т.13, №3(49). С.392-404. DOI: 10.18287/2223-9537-202313-3-392-404.
- Sinaga K.P., Yang M.-S. Unsupervised K-Means Clustering Algorithm // IEEE Access. 2020. № 8. P.80716-80727. DOI: 10.1109/ACCESS.2020.2988796.
- Ran X., Xi Y., Lu Y., Wang X., Lu Z. Comprehensive survey on hierarchical clustering algorithms and the recent developments // Artificial Intelligence Review. 2022. № 56. P.8219-8264. DOI: 10.1007/s10462-022-10366-3.
- King C. A spectral-based clustering algorithm for directed graphs // CSE 521: "Design and Analysis of Algorithms" — Fall 2020. P.1-8.
- Brubach B., Chakrabarti D., Dickerson J.P., Srinivasan A., Tsepenekas L. Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints. In: Proc. of the AAAI Conference on Artificial Intelligence. (2021 February 2-9.). P.6822-6830. DOI: 10.1609/aaai.v35i8.16842.
- Bibi A., Alqahtani A., Ghanem B. Constrained Clustering: General Pairwise and Cardinality Constraints // IEEE Access. 2023. № 11. P.5824-5836. DOI: 10.1109/ACCESS.2023.3236608.
- Li M., Xu D., Zhang D., Zou J. The seeding algorithms for spherical k-means clustering // Journal of global optimization. 2019. № 76. P.695-708. DOI: 10.1007/s10898-019-00779-w.
- Wagstaff K., Cardie C., Rogers S., Schrodl S. Constrained K-means Clustering with Background Knowledge // In Proceedings of the 18th International Conference on Machine Learning (Williamstown, USA 2001 June 28 - July 1). P.577-584.
- MacQueen J.B. Some Methods for Classifcation and Analysis of Multivariate Observations // In Proceedings of the fifth Berkeley Symposium on Mathematical Statistics and Probability (Berkeley, USA 1967). P.281-297.
- Baumann P., Hochbaum D.S. A k-Means Algorithm for Clustering with Soft Must-link and Cannot-link Constraints // In Proceedings of the 11th International Conference on Pattern Recognition Applications and Methods (Vienna, Austria 2022 February 3-5). P.195-202. DOI: 10.5220/0010800000003122.
- Svehla J. Active Semi-Supervised Clustering. Master's thesis. Prague: Faculty of Information Technology, 2018. 63 p.
- Li M., Xu D., Yue J., Zhang D. The seeding algorithm for k-means problem with penalties // Journal of Combinatorial Optimization. 2020. № 39. P. 15-32. DOI: 10.1007/s10878-019-00450-w.
- Khong M.T. Algorithms for table constraints and soft-regular constraints. Louvain-la-Neuve. UCLouvain. 2019. 105 p.
- Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. 360 с.
- Lattanzi S., Sohler C. A Better k-means++ Algorithm via Local Search. In: Proceedings of the 36th International Conference on Machine Learning (Long Beach, USA, 2019) P. 3662-3671.
