Система QPSLab для анализа и распознавания числовых последовательностей с квазипериодической структурой

Проблема кластеризации векторов

Задача разбиения множества векторов евклидова пространства на подмножества (кластеры) по критерию минимума суммы квадратов расстояний от элементов кластеров до их центров известна как задача MSSC (от Minimum-Sum-of-Squares Clustering). Центр кластера определяется как сумма векторов из кластера, деленная на его мощность. Эта же задача часто фигурирует под названием k-Means (k средних).

Четыре возможных случая задачи MSSC индуцируются комбинированием размерности пространства q и числа кластеров M, которые либо являются, либо не являются частью входа задачи.

Все четыре случая задачи являются NP-полными.