Характеристика моделирования, понятия модели

47. Сферический метод  двухступенчатой  кластеризации

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

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

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

48. Метод определения  центра кластера  с помощью вычисления  среднеарифметических  расстояний между  объектами

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

Предлагаемый  алгоритм кластеризации состоит  из следующих блоков:

1. Некоторой  точке, принадлежащей множеству  изучаемых объектов, присваивается  геометрический признак центра  координатной системы, причем  первый объект в этой системе  является началом отсчета.

2. Выбирается  определенное число объектов (только  количество), которые будут участвовать  в расчетах условного центра  кластера.

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

4. В  зависимости от выбранного алгоритма  определения критерия, необходимого  для завершения формирования  кластера, вычисляется максимально  допустимое расстояние между  объектами d. Расстояние может задаваться исследователем, исходя из анализа содержательного образа кластера или из соображений насыщенности кластера.

5. Методом  перебора определяется объект  А_К, наиболее близкий к объекту-центру А_ц. Далее проверяется выполнение неравенства: |А_К - А_Ц|£d и, в случае безусловного выполнения этого неравенства, объект А_К заносится в матрицу данного кластера. Из дальнейшего рассмотрения объект А_Ц исключается.

6. В  дальнейшем операции перебора  повторяются, причем объект  А_К становится центром рассматриваемой композиции. Итерации предыдущего блока выполняются до тех пор, пока не останется ни одного объекта вблизи любой из рассматриваемых точек, т. е. будет превышено пороговое значение d.

Варианты  классификации предлагаемым методом  определяются перебором значений d и начального объекта Ац. При этом достаточно проблематично найти «водораздел» между кластерами из-за случайных помех на поле, в промежутках между сгустками объектов информации. Поскольку метод уравнивает значимость в замкнутом кластере сгущений и одиночных объектов, качество классификации случайно и требует специального изучения. Кроме того, в ряде случаев возможно объединение всех объектов информационного поля в один-два кластера. И наоборот, жестко заданные граничные условия способны вытеснить за пределы кластеров значительное число объектов.

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

49. Метод постоянных  кластеров и характеристик

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

Алгоритм  предлагаемого метода основан на содержательном анализе информационного  поля до начала процедур кластеризации. На этом этапе исследователь должен определить рациональное число кластеров. исходя из физических возможностей оценки поля объектов, полезности для управления и возможности получения нетривиальных результатов. Введем обозначения: л - рациональное количество кластеров; А_ш (1с, I, т) ~ центр «массы» /-го кластера, имеющий координаты ^, /, т.

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

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

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

50. Алгоритм метода  постоянных кластеров  и их характеристик

Рассмотрим  алгоритм метода постоянных кластеров  и их характеристик:

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

2-й шаг.  Распределение объектов по кластерам  в зависимости от включения  координат объекта в граничные  условия кластера.

3-й шаг.  Вычисление координат центров  «массы» кластеров А_ш как средних арифметических координат объектов, входящих в рассматриваемый кластер.

4-й шаг.  Замена априорных характеристик  - границ кластеров на новые  критерии кластеризации.

5-й шаг.  Принимая точки Ащ,А,а, •••, Ац„ за центры «масс» кластеров (их количество сохранилось), начинаем формирование кластеров заново. При этом используем принцип наибольшей близости объекта к какому-либо центру кластера.

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

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

51. Алгоритм «краб»

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

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

Обозначим:   М=åm - суммарное количество объектов, рассматриваемых в условиях данной задачи классификации; n - количество кластеров, полученных в результате классификации объектов; F - критерий оптимальности классификации, причем F_max - суперцель.

Последовательность  процедур алгоритма «Краб»:

1. Построение  информационного поля m-объектов кластеризации, вычисление характеристик объектов и евклидовых расстояний между ними.

2. Формирование  матрицы минимальных расстояний  между объектами. Размерность  симметричной матрицы (m - 1).

3. Построение  контура минимальных расстояний  между объектами и нанесение  граничной линии на кластерное  поле. Проверка замкнутости граничной  линии.

4. Разделение  информационного массива на возможные  кластеры, количество которых находится  на отрезке [1; m - 1].

5. Сравнение  качества кластеризации по заданным  критериям F. Формирование информационных массивов кластеров и значений F.

6. Фильтрация  вариантов кластеризации по локальным  критериям F₁, F₂, F₃, …, F_k,  а также по комплексным критериям F_1,2 и так далее.

7. Определение  наилучшего варианта кластеризации  по критерию суперцели F_max.

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

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

52. Кластеризация с  помощью экспертных  оценок. Задачи

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