Формализация алгоритма решения задачи

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

Пример описания формализованного алгоритма решения задачи статистической группировки

… Одним из методов решения задачи разбиения земельных участков на группы, является метод кластерного анализа. Используя данный метод можно провести разбиение земельных участков на кластеры, основываясь на обобщенном сходстве признаков, в качестве которых выбираются стоимость и размер участка. Сущность метода кластерного анализа заключается в следующем.

На основе входных статистических данных производится разделение степени инцидента на подмножества, по сходству имеющихся признаков.

Кластерный анализ – это совокупность методов многомерной классификации, целью которой является образование групп (кластеров) схожих между собой объектов. В отличие от традиционных группировок, рассматриваемых в общей теории статистики, кластерный анализ приводит к разбиению на группы с учетом всех группировочных признаков одновременно. Например, если наблюдаемый объект характеризуется двумя признаками Х₁ иХ₂, то при использовании методов кластерного анализа оба эти признака учитываются одновременно при отнесении наблюдения в ту или иную группу. Методы кластерного анализа позволяют решать следующие задачи:

· проведение классификации объектов с учетом признаков, отражающих сущность, саму природу объектов;

· проверка выдвигаемых предположений о наличии некоторой структуры в изучаемой совокупности объектов, т.е. поиск существующей структуры;

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

Все методы кластерного анализа можно разделить на две группы: иерархические методы (агломеративные и дивизимные) и итеративные (метод k -cpeдних, метод поиска сгущений и т.д.).

Для записи формализованных алгоритмов кластерного анализа введем следующие условные обозначения:

X₁, X₂, … X_n – совокупность объектов наблюдения; – i-е наблюдение в m-мерном пространстве признаков (i = 1, 2, …, n);

d_kl – расстояние между k-м и l-м объектами;

z_ij – нормированные значения исходных переменных;

D – матрица расстояний между объектами.

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

В кластерном анализе для количественной оценки сходства вводится понятие метрики. Каждый объект описывается m-признаками и представлен как точка в m-мерном пространстве. Сходство или различие между классифицируемыми объектами устанавливается в зависимости от метрического расстояния между ними. В кластерном анализе используются различные меры расстояния между объектами:

евклидово расстояние ;

взвешенное евклидово расстояние ;

расстояние city-block ;

расстояние Минковского ;

расстояние Махаланобиса ,

где d_ij – расстояние между i-ым и j-ым объектами; xil, xjl – значения l-переменной и соответственно у i-го и j-го объектов;

X_i, X_j – векторы значений переменных у i-го и j-го объектов;

S* – общая ковариационная матрица;

f_l – вес, приписываемый l-й переменной.

Если алгоритм кластеризации основан на измерении сходства между переменными, то в качестве мер сходства могут быть использованы:

· линейные коэффициенты корреляции;

· коэффициенты ранговой корреляции;

· коэффициенты контингенции и т.д.

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

Из всех методов кластерного анализа наиболее распространенными являются иерархические агломеративные методы. Сущность этих методов заключается в том, что на первом шаге каждый объект выборки рассматривается как отдельный кластер. Процесс объединения кластеров происходит последовательно: на основании матрицы расстояний или матрицы сходства, объединяются наиболее близкие объекты. Если матрица расстояний первоначально имеет размерность m×m, то полностью процесс объединения завершается за m - 1 шагов. В итоге все объекты будут объединены в один кластер. Последовательность объединения может быть представлена в виде следующей дендрограммы (рис. 15).

Дендрограмма, изображенная на рисунке 1.3, показывает, что в данном случае на первом шаге были объединены в один кластер второй и третий объекты при расстоянии между ними 0,15. На втором шаге к ним присоединился первый объект. Расстояние от первого объекта до кластера, содержащего второй и третий объекты, было 0,3 и т.д.

Множество методов иерархического кластерного анализа отличаются алгоритмами классификации, из которых наиболее распространенными являются: метод одиночной связи, метод полных связей, метод средней связи, метод Уорда.

Объект

0,8

0,5

0,15

0,3

Рисунок 15 – Дендрограмма иерархического кластерного анализа

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

Рисунок 16 – Диаграмма состояний процедуры кластерного анализа

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

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

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

Существуют несколько способов выбора радиуса сферы. Если d_lk – расстояние между l-м и k-м объектами, то в качестве нижней границы радиуса RH выбирают , а верхняя граница радиуса R_в может быть определена как .

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