Применение задач оптимизации в кластерном анализе

Кластерный анализ [3] является сравнительно новым разделом математики, в котором изучаются методы разбиения совокупности объектов, заданных конечными наборами признаков, на однородные группы (кластеры). Кластерный анализ широко применяется в психологии, социологии, экономике (сегментация рынка) и многих других областях, в которых возникает задача классификации объектов по их признакам. Методы кластеризации реализованы в пакетах STATISTICA [1] и SPSS [2], они возвращают разбиения на кластеры, дисперсионную статистику кластеризации и дендрограммы иерархических алгоритмов кластеризации. Макросы MS Excel основных методов кластеризации и примеры применения приведены в монографии [5]. Одной из центральных проблем кластерного анализа является определение по некоторому критерию числа кластеров, обозначим это число через K, на которые разбивается заданное множество объектов. Существуют несколько десятков подходов [4] к определению числа K. В частности, согласно [6] число кластеров K - минимальное число, для которого выполняется , где - минимальное значение суммарной дисперсии при разбиении на K кластеров, N - число объектов. К числу кластеров автоматически приводит последовательное применение аномальных кластеров [4]. В 2010 году предложен и экспериментально проверен метод получения числа K посредством применения функции плотности [4]. В статье предлагаются два простых подхода к определению K, когда каждый кластер имеет не менее двух объектов. В первом число K определяется через кратчайшие гамильтоновы циклы, во втором - через минимальные остовные деревья. Приведены примеры кластеризации с подробными пошаговыми решениями и графическими иллюстрациями. Показано применение макроса VBA Excel, возвращающего минимальное остовное дерево, к задачам кластеризации. В статью вошел код макроса, снабженный комментариями к основным блокам.