Применение smart-таблиц и оценок целевой функции для снижения размерности и ускорения решения задач Constrained Clustering

Александр Анатольевич Зуенко; Ольга Владимировна Фридман; Ольга Николаевна Зуенко

doi:10.17308/sait.2021.3/3738

Александр Анатольевич Зуенко Институт информатики и математического моделирования — обособленное подразделение Федерального исследовательского центра «Кольский научный центр Российской академии наук» https://orcid.org/0000-0002-7165-6651
Ольга Владимировна Фридман Институт информатики и математического моделирования — обособленное подразделение Федерального исследовательского центра «Кольский научный центр Российской академии наук» https://orcid.org/0000-0003-1897-4922
Ольга Николаевна Зуенко Институт информатики и математического моделирования — обособленное подразделение Федерального исследовательского центра «Кольский научный центр Российской академии наук» https://orcid.org/0000-0001-5431-7538

DOI: https://doi.org/10.17308/sait.2021.3/3738

Ключевые слова: программирование в ограничениях, кластерный анализ, мультимножества, кластеризация с частичным привлечением учителя, smart-таблицы

Аннотация

В статье представлен комплексный подход к точному решению задач Constrained Clustering, то есть задач кластеризации, предполагающих анализ, помимо матрицы расстояний, фоновых знаний о необходимости/недопустимости вхождения некоторых объектов в те или иные кластеры. Подход реализован в рамках парадигмы программирования в ограничениях (Constraint Programming), ориентированной на построение процедур систематического поиска (процедур обхода дерева поиска) для решения сложных комбинаторных задач. При этом, вся исходная информация о задаче выражается с помощью ограничений, то есть качественных и количественных зависимостей. Существенная сложность заключается в том, что в современных средах и библиотеках программирования в ограничениях обработка качественных ограничений, которыми, в частности, являются правила отнесения объектов к одному или различным кластерам, производится недостаточно эффективно. Таким образом, представляется актуальной разработка способов ускорения обработки подобных ограничений. В статье предлагается представлять и обрабатывать качественные ограничения в форме табличных ограничений нового типа, а именно smart-таблиц D-типа. Для smart-таблиц D-типа разработаны высокоэффективные процедуры вывода на ограничениях, осуществляющие раннее отсечение неперспективных ветвей дерева поиска. Другое направление работ, которое активно развивается в настоящих исследованиях, связано с уменьшением количества ограничений, используемых для представления задачи, и с упрощением их вида. Предлагается генерировать ограничения лишь для некоторых пар объектов, основываясь на интервальной оценке для оптимального значения критерия кластеризации. Для получения данной оценки используется ранее предложенный авторами метод иерархической кластеризации, который позволяет анализировать ограничения на комбинации пар объектов внутри кластера. Предложенный подход позволяет находить все варианты разбиений, обеспечивающие глобальный оптимум целевой функции для рассматриваемых задач Constrained Clustering высокой размерности. Разработанный подход проиллюстрирован на примере задачи выявления зон участка горного массива с различной степенью сейсмической активности.

Скачивания

Данные скачивания пока не доступны.

Биографии авторов

Александр Анатольевич Зуенко, Институт информатики и математического моделирования — обособленное подразделение Федерального исследовательского центра «Кольский научный центр Российской академии наук»

канд. техн. наук, ведущий научный сотрудник, Институт информатики и математического моделирования — обособленное подразделение Федерального государственного бюджетного учреждения Федерального исследовательского центра «Кольский научный центр Российской академии наук» (ИИММ КНЦ РАН)

Ольга Владимировна Фридман, Институт информатики и математического моделирования — обособленное подразделение Федерального исследовательского центра «Кольский научный центр Российской академии наук»

канд. техн. наук, старший научный сотрудник, Институт информатики и математического моделирования — обособленное подразделение Федерального государственного бюджетного учреждения Федерального исследовательского центра «Кольский научный центр Российской академии наук» (ИИММ КНЦ РАН)

Ольга Николаевна Зуенко, Институт информатики и математического моделирования — обособленное подразделение Федерального исследовательского центра «Кольский научный центр Российской академии наук»

стажер-исследователь, аспирант ИИММ КНЦ РАН, Институт информатики и математического моделирования — обособленное подразделение Федерального государственного бюджетного учреждения Федерального исследовательского центра «Кольский научный центр Российской академии наук» (ИИММ КНЦ РАН)

Литература

1. Babaki B., Guns T., Nijssen S. (2014) Constrained Clustering using Column Generation: Proceedings of the 11th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. P. 438–454.
2. Bartak R. (1999) Constraint Programming: In Pursuit of the Holy Grail, Proceedings of the Week of Doctoral Students (WDS99), Part IV. Prague: MatFyzPress. P. 555–564.
3. Borovikov V. P. (2017) Popular introduction to modern data analysis and machine learning on STATISTICA. Moscow: Hot Line. Telecom.
4. Dao T.-B.-H., Duong K.-C., Vrain C. Constrained clustering by constraint programming. Artificial Intelligence. 244. P. 70–94.
5. Davidson I. Ravi S. S., Shamis L. (2010) A SAT-based Framework for Efficient Constrained Clustering: Proceedings of the 10th SIAM International Conference on Data Mining. P. 94–105.
6. Gonzalez T. (1985) Clustering to Minimize the Maximum Intercluster Distance. Theoretical Computer Science. 38. P. 293–306.
7. Guns T., Nijssen S., Raedt L. D. (2013) k-Pattern set mining under constraints. IEEE Transactions on Knowledge and Data Engineering. 25(2). P. 402–418.
8. Katsirelos G., Walsh T. (2007) A compression algorithm for large arity extensional constraints. CP 2007. LNCS, 4741. P. 379–393.
9. Mairy J., Deville Y., Lecoutre C. (2015) The Smart Table Constraint. In: Michel, L. (eds.) Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2015. Lecture Notes in Computer Science. Springer. Cham. 9075. P. 271–287.
10. Métivier J.-P. (2012) Constrained Clustering Using SAT: Proceedings of the 11th International Symposium on Advances in Intelligent Data Analysis. P. 207–218.
11. Mueller M., Kramer S. (2010) Integer Linear Programming Models for Constrained: Proceedings of the 13th International Conference on Discovery Science. P. 159–173.
12. Perez G. (2014) Improving GAC-4 for table and MDD constraints. CP 2014. LNCS. 8656. P. 606–621.
13. Petrovsky A. B. (2009) Methods for group classification of multi-feature objects (part 1). Artificial intelligence and decision making. 3. P. 3–14. (in Russian).
14. Russel S. & Norvig P. (2010) Artificial Intelligence: A Modern Approach. 3rd edition. Prentice Hall.
15. Ruttkay Zs. (1998) Constraint satisfaction a survey. CWI Quarterly. 11. P. 163–214.
16. Xia W. (2013) Optimizing STR algorithms with tuple compression. CP 2013. LNCS. 8124. P. 724–732.
17. Zuenko A. A. (2020) Representation and Processing of Qualitative Constraints Using a New Type of Smart Tables: Proceedings of the 4th International Conference on Computer Science and Application Engineering (CSAE ‘20). ACM New York, NY, USA, Article No 45. P. 1–7.
18. Zuenko A. A., Fridman O. V., Zhuravleva O. G. (2019) Application of limited clustering methods for the study of technogenic seismicity. Vestnik VSU, series: System analysis and information technology. 3. P. 29–41. (in Russian).