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

Размещено на http://www.allbest.ru/

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

Сдвижков О.А.

Кластерный анализ [3] является сравнительно новым разделом математики, в котором изучаются методы разбиения совокупности объектов, заданных конечными наборами признаков, на однородные группы (кластеры). Кластерный анализ широко применяется в психологии, социологии, экономике (сегментация рынка) и многих других областях, в которых возникает задача классификации объектов по их признакам. Методы кластеризации реализованы в пакетах STATISTICA [1] и SPSS [2], они возвращают разбиения на кластеры, дисперсионную статистику кластеризации и дендрограммы иерархических алгоритмов кластеризации. Макросы MS Excel основных методов кластеризации и примеры применения приведены в монографии [5].

Одной из центральных проблем кластерного анализа является определение по некоторому критерию числа кластеров, обозначим это число через K, на которые разбивается заданное множество объектов. Существуют несколько десятков подходов [4] к определению числа K. В частности, согласно [6] число кластеров K - минимальное число, для которого выполняется , где - минимальное значение суммарной дисперсии при разбиении на K кластеров, N - число объектов. К числу кластеров автоматически приводит последовательное применение аномальных кластеров [4]. В 2010 году предложен и экспериментально проверен метод получения числа K посредством применения функции плотности [4].

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

Приведены примеры кластеризации с подробными пошаговыми решениями и графическими иллюстрациями. Показано применение макроса VBA Excel, возвращающего минимальное остовное дерево, к задачам кластеризации. В статью вошел код макроса, снабженный комментариями к основным блокам.

Ключевые слова: кластер, линейное программирование, кратчайший цикл, минимальное остовное дерево

Application of optimization tasks in cluster analysis

Sdvizhkov Oleg Aleksandrovich

Cluster analysis [3] is a relatively new branch of mathematics that studies the methods partitioning a set of objects, given a finite set of attributes into homogeneous groups (clusters). Cluster analysis is widely used in psychology, sociology, economics (market segmentation), and many other areas in which there is a problem of classification of objects according to their characteristics. Clustering methods implemented in a package STATISTICA [1] and SPSS [2], they return the partitioning into clusters, clustering and dispersion statistics dendrogram of hierarchical clustering algorithms. MS Excel Macros for main clustering methods and application examples are given in the monograph [5].

One of the central problems of cluster analysis is to define some criteria for the number of clusters, we denote this number by K, into which separated are a given set of objects. There are several dozen approaches [4] to determine the number K. In particular, according to [6], the number of clusters K - minimum number which satisfies where - the minimum value of total dispersion for partitioning into K clusters, N - number of objects. Among the clusters automatically causes the consistent application of abnormal clusters [4]. In 2010, proposed and experimentally validated was a method for obtaining the number of K by applying the density function [4].

The article offers two simple approaches to determining K, where each cluster has at least two objects. In the first number K is determined by the shortest Hamiltonian cycles in the second - through the minimum spanning tree. The examples of clustering with detailed step by step solutions and graphic illustrations are suggested. Shown is the use of macro VBA Excel, which returns the minimum spanning tree to the problems of clustering. The article contains a macro code, with commentaries to the main unit.

Keywords: cluster, linear programming, the shortest cycle, the minimum spanning tree

Кластеризация методом минимальных гамильтоновых циклов

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

Будем говорить, что совокупность точек разбивается методом минимальных гамильтоновых циклов на кластеры , если суммарная длина минимальных гамильтоновых циклов этих кластеров не больше, чем суммарная длина минимальных гамильтоновых циклов кластеров при любом другом разбиении.

Обозначим через матрицу расстояний между точками в некоторой выбранной метрике (евклидовой, квадрата евклидовой и т.д.), будем считать . Методом от противного доказывается теорема 1.

Теорема 1. Матрица смежности графа , состоящего из циклов , является решением задачи линейного программирования с двоичными (булевыми) переменными:

.

В силу теоремы 1, число кластеров K равно числу компонент связности графа , каждый кластер состоит из вершин, через которые проходит цикл , .

Пример 1. Применяя метод минимальных гамильтоновых циклов, провести классификацию 10 объектов, заданных значениями трех признаков (табл.1).

Таблица 1

1. Вводим данные на рабочий лист (рис. 1):

Рисунок 1

2. Составляя в диапазоне E1:N10 с помощью функции СУММКВРАЗН матрицу расстояний между точками, по главной диагонали ставим 10, получаем (рис. 2):

Рисунок 2

3. Диапазон оставляем за независимыми двоичными переменными.

4. В ячейку вводим формулу и копируем ее в ячейки .

5. В ячейку вводим формулу и копируем ее в ячейки .

6. В ячейку вводим формулу целевой функции: = СУММПРОИЗВ(E1:N10;E12:N21).

7. Вызываем диалоговое окно «Поиск решения» и задаем сценарий решения (рис. 3).

Рисунок 3

8. Команда «Выполнить» в диапазоне возвращает (рис. 4):

Рисунок 4

В первой строке значение 1 во втором столбце, т.е. в цикл включается звено (1, 2), во второй строке значение 1 в четвертом столбце, т.е. следующее звено (2, 4). Продолжая цепочку, приходим к циклу . Аналогично показывается, что второй цикл . Следовательно, заданная совокупность объектов разбивается на два кластера {1, 2, 3, 4} и {5, 6, 7, 8, 9, 10}. Графическая иллюстрация, выполненная в пакете STATISTICA, приведена на рисунке 5.

Рисунок 5

Кластеризация методом минимальных остовных деревьев

Остовным деревом (деревом-остовом) графа G называется дерево , содержащее все вершины графа G. Минимальным остовным деревом называется дерево-остов , имеющее минимальную сумму весовых коэффициентов.

Будем говорить, что совокупность точек разбивается методом минимальных остовных деревьев на кластеры , если суммарная длина минимальных остовных деревьев этих кластеров не больше, чем суммарная длина минимальных остовных деревьев при любом другом разбиении на кластеры.

Составим матрицу , , если , , если , где . Имеет место теорема 2, аналогичная теореме 1.

Теорема 2. При разбиении точек на кластеры методом минимальных остовных деревьев число кластеров равно числу компонент связности графа, матрица смежности которого находится как решение задачи линейного программирования с двоичными переменными:

, .

Понятно, что вершины каждой компоненты связности образуют кластер.

Пример 2. Применяя метод минимальных остовных деревьев, разбить на кластеры объекты, заданные таблицей 1.

1. Приводим диапазон E1:N10 (рис. 2) к виду (рис. 6):

Рисунок 6

2. Диапазон оставляем за независимыми двоичными переменными.

3. В ячейку O12 вводим формулу =СУММ(E12:N12)+СУММ(E12:E21), в ячейку О13 - формулу =СУММ(E13:N13)+СУММ(F12:F21) и так далее, до ячейки О21, в которую вводим формулу =СУММ(E21:N21)+СУММ(N12:N21).

4. В ячейку O22 вводим формулу целевой функции: =СУММПРОИЗВ(E1:N10;E12:N21).

5. Вызываем диалоговое окно «Поиск решения» и задаем сценарий решения (рис. 7).

Рисунок 7

6. Команда «Выполнить» в диапазоне возвращает (рис. 8):

Рисунок 8

Откуда следует, что кластеры {2, 3, 4}, {1, 6}, {5, 7, 10}, {8, 9}.

Теорема 3. Если матрица приводится к виду, в котором , где , то для метода минимальных остовных деревьев K=1.

Применение макроса Skeleton

Для нахождения минимального остовного дерева разработан макрос Skeleton [5].

Код макроса:

Sub Skeleton()

Dim n As Integer, p() As Integer, q() As Integer, _

s As Single, a As Integer, b As Integer, t As Single

n = Selection.Rows.Count

'Задание массивов с первоначальным разбиением вершин:

ReDim p(1 To 1)

ReDim q(2 To n)

p(1) = 1

For i = 2 To n

q(i) = i

Next

'Нахождение оценки сверху заданных значений:

t = Application.WorksheetFunction.Max(Selection) + 1

'Вычислительный цикл:

For k = 1 To n - 1

s = t

For Each x In p

For Each y In q

If y > 0 Then

If Cells(x, y).Value <> Empty And Cells(x, y).Value < s Then

s = Cells(x, y).Value

a = x: b = y

End If

End If

Next

Next

'Вывод результатов:

Cells(n + 1 + k, 1).Value = a

Cells(n + 1 + k, 2).Value = b

Cells(n + 1 + k, 3).Value = s

'Присоединение к p нового значения:

ReDim Preserve p(1 To 1 + k)

p(k + 1) = b

'Исключение b из q, учитывая y>0:

q(b) = 0

Next

'Вывод минимальной суммы:

Cells(2 * n + 1, 3).Value = Application.WorksheetFunction. _

Sum(Range(Cells(n + 2, 3), Cells(2 * n, 3)))

End Sub

В частности, для данных диапазона E1:N10 рисунка 2 он возвращает (рис. 9):

Рисунок 9

То есть в минимальное остовное дерево входят дуги (1, 6), (6, 5), (5, 7), (6, 8), (7, 10), (8, 9), (1, 2), (2, 4), (4, 3), в диапазоне С12:С20 - их весовые коэффициенты. Наибольший вес 0,3 имеет дуга (1, 2), удаление ее приводит к двум кластерам (2, 3, 4), (1, 5, 6, 7, 8, 9, 10).

После этого дерево, связывающее вершины 1, 5, 6, 7, 8, 9, 10, распадается, если удаляется одна из дуг (5, 7), (6, 8), (5, 6), из которых наибольший вес 0,09 имеет дуга (6, 8). Поэтому разбиение на три кластера получается удалением дуги (6, 8), что дает {2, 3, 4}, {1, 5, 6, 7, 10}, {8, 9}. Следующее разбиение приводит к кластерам, полученным в примере 2.

Заключение

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

Литература

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.

References

оптимизация кластерный задача

1.Vukolov, E.A. Osnovy statisticheskogo analiza: praktikum po statisticheskim metodam i issledovaniiu operatsii s ispol'zovaniem paketov STATISTICA i EXCEL [Basics of statistical analysis: a workshop on statistical methods and operations research using STATISTICA packages and EXCEL]. - M.: INFRA-M, 2004.

2.Dubov, I.Iu. Obrabotka statisticheskoi informatsii s pomoshch'iu SPSS [Statistical information processing using SPSS]. - M.: NT Press, 2004.

3.Mandel', I.D. Klasternyi analiz [Cluster analysis]. - M.: Finansy i statistika, 1988.

4.Mirkin, B.G. Metody klaster-analiza dlia podderzhki priniatiia reshenii [Methods of cluster analysis to support decision making]. - M.: izd. dom «Vysshaia shkola ekonomiki», 2011.

5.Sdvizhkov, O. A. Diskretnaia matematika i matematicheskie metody ekonomiki s primeneniem VBA Excel [Discrete mathematics and mathematical methods in economics using VBA Excel]. - M.: DMK Press, 2012.

6.Hartigan, J. A. Clustering Algorithms. N.Y.: J. Wiley & Sons, 1975.

Размещено на Allbest.ru