Эффективный алгоритм кластеризации k-средних: анализ и реализация

В задаче кластеризации k-средних задано множество из n точек данных в d-мерном пространстве R^d и целое число k; требуется определить набор из k точек в R^d, называемых центрами, так чтобы минимизировать средний квадрат расстояния от каждой точки данных до ближайшего центра. Популярной эвристикой для кластеризации k-средних является алгоритм Ллойда (1982). Мы представляем простую и эффективную реализацию алгоритма Ллойда для k-средних, которую называем фильтрующим алгоритмом. Этот алгоритм прост в реализации и требует kd-дерева в качестве единственной основной структуры данных. Мы обосновываем практическую эффективность фильтрующего алгоритма двумя способами. Во-первых, мы приводим чувствительный к данным анализ времени выполнения алгоритма, который показывает, что алгоритм работает быстрее по мере увеличения раздельности кластеров. Во-вторых, мы приводим ряд эмпирических исследований на синтетически сгенерированных данных и на реальных наборах данных из приложений в квантовании цветов, сжатии данных и сегментации изображений.