Решение задачи кластеризации методами оптимизации на графах

Быстрый рост объёмов обрабатываемой информации, наблюдаемый в последнее время, увеличение размерности решаемых задач обусловливают актуальность разработки и применения методов снижения размерности. Одним из подходов к снижению размерности данных является их кластеризация, то есть объединение в максимально однородные группы. При этом желательно, чтобы представители разных кластеров были бы максимально «непохожими» друг на друга. Помимо снижения размерности, задачи кластеризации имеют и самостоятельное значение, например, в экономике это связано с сегментированием рынка, в социологии — с типологизацией признаков, в геологии — с фациальной диагностикой пород и т. д.
Несмотря на большое число известных методов решения задачи кластеризации, проблема разработки и исследования новых алгоритмов не теряет актуальности. Дело в том, что не существует алгоритма, который превосходил бы все остальные по всем критериям (быстродействие, нечувствительнсть к размерам и форме кластеров, количество параметров и т. д.).
В статье представлен алгоритм кластеризации, основанный на применении теории графов (теоремы о максимальном потоке и минимальном разрезе) и проведён сравнительный анализ его с четырьмя другими алгоритмами — представителями различных классов методов кластеризации.