ЭФФЕКТИВНЫЕ АЛГОРИТМЫ ОДНОМЕРНОЙ КЛАСТЕРИЗАЦИИ

Аннотация

В данной работе рассматриваются алгоритмы кластеризации данных. Ознакомление с данной тематикой началось с формулировки задач кластеризации в математических терминах. Были даны определения для конкретных методов: k-means, k-medians и k-medoids. Поскольку, основной темой дипломной работы является метод кластеризации k-means, был описан классический алгоритм реализации этого метода. В общем случае задача кластеризации методом k-means является NP-трудной, поэтому поиск частных случаев этой задачи, решаемых за полиномиальное время актуален в связи с потребностью обработки больших данных в наше время. В данной работе рассмотрены алгоритмы одномерной кластеризации и время их работы. Описан алгоритм работающий за время O(kn2), в основе которого лежит реккурентное соотношение. В статье [1] был предложен алгоритм, работающий за время O(kn), на основе алгоритма SMAWK для тотально монотонных матриц, который является эффективной версией алгоритма O(kn2). Для использования алгоритма SMAWK авторы статьи [1] приводят доказательство тотальной монотонности преобразованной матрицы, которое не является корректным. Одной из целей данной работы было построение контрпримера