ПРИМЕНЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ В КЛАСТЕРНОМ АНАЛИЗЕ
Рубрики: ОБРАЗОВАНИЕ
Авторы:
Тип:
Статья
Страницы:
с 0
по 0
Статус:
Опубликован
Получено:
12.01.2015
Одобрено:
12.01.2015
Опубликовано:
12.01.2015
Язык материала:
русский
Ключевые слова:
кластер, линейное программирование, кратчайший цикл, минимальное остовное дерево
Аннотация (русский):
Кластерный анализ [3] является сравнительно новым разделом математики, в котором изучаются методы разбиения совокупности объектов, заданных конечными наборами признаков, на однородные группы (кластеры). Кластерный анализ широко применяется в психологии, социологии, экономике (сегментация рынка) и многих других областях, в которых возникает задача классификации объектов по их признакам. Методы кластеризации реализованы в пакетах STATISTICA [1] и SPSS [2], они возвращают разбиения на кластеры, дисперсионную статистику кластеризации и дендрограммы иерархических алгоритмов кластеризации. Макросы MS Excel основных методов кластеризации и примеры применения приведены в монографии [5]. Одной из центральных проблем кластерного анализа является определение по некоторому критерию числа кластеров, обозначим это число через K, на которые разбивается заданное множество объектов. Существуют несколько десятков подходов [4] к определению числа K. В частности, согласно [6] число кластеров K – минимальное число, для которого выполняется , где – минимальное значение суммарной дисперсии при разбиении на K кластеров, N – число объектов. К числу кластеров автоматически приводит последовательное применение аномальных кластеров [4]. В 2010 году предложен и экспериментально проверен метод получения числа K посредством применения функции плотности [4]. В статье предлагаются два простых подхода к определению K, когда каждый кластер имеет не менее двух объектов. В первом число K определяется через кратчайшие гамильтоновы циклы, во втором – через минимальные остовные деревья. Приведены примеры кластеризации с подробными пошаговыми решениями и графическими иллюстрациями. Показано применение макроса VBA Excel, возвращающего минимальное остовное дерево, к задачам кластеризации. В статью вошел код макроса, снабженный комментариями к основным блокам.
Кластерный анализ [3] является сравнительно новым разделом математики, в котором изучаются методы разбиения совокупности объектов, заданных конечными наборами признаков, на однородные группы (кластеры). Кластерный анализ широко применяется в психологии, социологии, экономике (сегментация рынка) и многих других областях, в которых возникает задача классификации объектов по их признакам. Методы кластеризации реализованы в пакетах STATISTICA [1] и SPSS [2], они возвращают разбиения на кластеры, дисперсионную статистику кластеризации и дендрограммы иерархических алгоритмов кластеризации. Макросы MS Excel основных методов кластеризации и примеры применения приведены в монографии [5]. Одной из центральных проблем кластерного анализа является определение по некоторому критерию числа кластеров, обозначим это число через K, на которые разбивается заданное множество объектов. Существуют несколько десятков подходов [4] к определению числа K. В частности, согласно [6] число кластеров K – минимальное число, для которого выполняется , где – минимальное значение суммарной дисперсии при разбиении на K кластеров, N – число объектов. К числу кластеров автоматически приводит последовательное применение аномальных кластеров [4]. В 2010 году предложен и экспериментально проверен метод получения числа K посредством применения функции плотности [4]. В статье предлагаются два простых подхода к определению K, когда каждый кластер имеет не менее двух объектов. В первом число K определяется через кратчайшие гамильтоновы циклы, во втором – через минимальные остовные деревья. Приведены примеры кластеризации с подробными пошаговыми решениями и графическими иллюстрациями. Показано применение макроса VBA Excel, возвращающего минимальное остовное дерево, к задачам кластеризации. В статью вошел код макроса, снабженный комментариями к основным блокам.
Ключевые слова:
кластер, линейное программирование, кратчайший цикл, минимальное остовное дерево
кластер, линейное программирование, кратчайший цикл, минимальное остовное дерево
1. Вуколов, Э.А. Основы статистического анализа: практикум по статистическим методам и исследованию операций с использованием пакетов STATISTICA и EXCEL. - М.: ИНФРА-М, 2004.
2. Дубов, И.Ю. Обработка статистической информации с помощью SPSS. - М.: НТ Пресс, 2004.
3. Мандель, И.Д. Кластерный анализ. - М.: Финансы и статистика, 1988.
4. Миркин, Б.Г. Методы кластер-анализа для поддержки принятия решений. - М.: изд. дом «Высшая школа экономики», 2011.
5. Сдвижков, О. А. Дискретная математика и математические методы экономики с применением VBA Excel. - М.: ДМК Пресс, 2012.
6. Hartigan J. A. Clustering Algorithms. N.Y.: J. Wiley & Sons, 1975.
