2.4. Вычислительные аспекты полного перебора

Имея целевую функцию, например внутригрупповую сумму квадратов, которая эквивалентна евклидовой метрике, оптимальное решение кластерной проблемы теоретически

может быть получено перебором всех возможных альтернатив разбиения; при этом оптимальному разбиению отвечает и оптимальное значение целевой функции. Однако этот процесс практически неосуществим за исключением случаев, когда мало. При полном переборе некоторые кластеры для разных альтернатив разбиения будут совпадать, что приводит к лишним вычислениям, которые можно сократить.

Поэтому при кластеризации методом полного перебора желательно иметь такую схему или алгоритм, которые исключали бы излишнюю вычислительную работу. Это приводит к рассмотрению методов динамического программирования, которые, значительно сокращая общее число вычислений, в то же время сходятся к оптимальному решению. Рассмотренные в первой главе методы кластеризации также достаточно быстро приводят к оптимальному решению. К таким методам, например, принадлежат методы последовательной кластеризации. Однако эти методы работают только на подмножестве всех возможных альтернатив разбиения и поэтому не гарантируют того, что найденное решение будет оптимальным или близким к нему.

При кластеризации с помощью полного перебора необходимо иметь в памяти одну матрицу наблюдений X, и все вычисления будут основываться только на ней без привлечения дополнительных массивов. Однако необходимый объем вычислений так велик, что, несмотря на высокое быстродействие современных вычислительных машин, решение задачи остается безнадежным. (В табл.

2.1 приводится общее число кластеров для различных значений (число объектов меньших 9)

Привлечение методов динамического программирования для решения кластерной проблемы требует большой скорости при обращении к дополнительным массивам, хранящим информацию. Эти методы привлекают «старые» вычисления и выполняют «новые». Таким образом, высокая скорость обращения к хранящейся информации очень желательна, если не обязательна. Один из методов динамического программирования был разработан Дженсеном [183]; этот метод будет описан в следующей главе. Там же будут рассмотрены другие методы, основанные на динамическом программировании.