Характеристика моделирования, понятия модели (стр. 10 из 10)
51. Алгоритм «краб»
В алгоритме «Краб» предусмотрена процедура фильтрации при заданной целевой функции отбора лучшего варианта. Оптимальный набор кластеров имеет жесткую, единственно возможную форму поля, причем контуры отдельных кластеров необязательно должны иметь сферическую оболочку.
Положительные стороны алгоритма «Краб» заключаются в возможности реализации поставленных целей кластеризации. В результате использования целевых функций удается ограничить количество рассматриваемых вариантов кластеризации до числа, определяемого целевыми функциями. Алгоритмом предусматривается формулировка суперцели, включающей в себя определенное число целевых функций. В этом случае результатом классификации будет единственный, наилучший вариант распределения объектов по кластерам.
Обозначим: М=åm - суммарное количество объектов, рассматриваемых в условиях данной задачи классификации; n - количество кластеров, полученных в результате классификации объектов; F - критерий оптимальности классификации, причем Fmax - суперцель.
Последовательность процедур алгоритма «Краб»:
1. Построение информационного поля m-объектов кластеризации, вычисление характеристик объектов и евклидовых расстояний между ними.
2. Формирование матрицы минимальных расстояний между объектами. Размерность симметричной матрицы (m - 1).
3. Построение контура минимальных расстояний между объектами и нанесение граничной линии на кластерное поле. Проверка замкнутости граничной линии.
4. Разделение информационного массива на возможные кластеры, количество которых находится на отрезке [1; m - 1].
5. Сравнение качества кластеризации по заданным критериям F. Формирование информационных массивов кластеров и значений F.
6. Фильтрация вариантов кластеризации по локальным критериям F1, F2, F3, …, Fk, а также по комплексным критериям F1,2 и так далее.
7. Определение наилучшего варианта кластеризации по критерию суперцели Fmax.
8. Описание характеристик объектов, содержащихся в кластерах при наилучшем варианте Fmax или соответствующих локальным критериям оптимальной кластеризации.
В результате вычислительных процедур алгоритма «Краб» исходные объекты распределяются по кластерам достаточно простым способом и соответствуют сформулированным критериям оптимальности разбиения. Но, несмотря на простоту вычислительных процедур, количество вариантов кластеризации чрезвычайно велико. Кроме того, при расчете каждого варианта приходится рассматривать множество значений расстояний между объектами внутри кластера для расчета критериев F. Поэтому исследователи обычно вводят промежуточные ограничения для сокращения числа рассматриваемых вариантов.
52. Кластеризация с помощью экспертных оценок. Задачи
Прямое использование коллективного опыта специалистов при классификации объектов нашло решение в задачах кластерного анализа с участием мнений экспертов. Этот метод применяется при начальном разделении множества объектов, когда ведется поиск принципов распределения элементов по кластерам, или в случае необходимости поиска нетривиальных, но предсказуемых решений, или в простейших формулировках исследования, при дефиците ресурсов для сбора и обработки материалов. Бывает также, что формальная кластеризация дает разбиение, малопригодное в реальных условиях управления.
Экспертные оценки при кластеризации применяются в чистом виде или в комбинации с формальными процедурами, обеспечивая последним содержательный контроль за результатами классификации и способствуя углубленному пониманию постановочных задач. Таким образом, применение экспертных оценок в задачах кластеризации повышает эффективность работы в отношении как качества классификации, так и упрощения вычислительных процедур.
С помощью экспертных оценок возможно решение следующих задач кластерного анализа:
• установление границ кластеров и определение дискриминантных функций;
• поименное отнесение каждого объекта к определенному кластеру в соответствии с субъективным мнением экспертов;
• целевой отбор признаков (характеристик) для формирования кластеров и последующего изучения пространства объектов или придания признакам «весовых» оценок;
• разработка правил коллективной выработки функций формирования кластеров, установка формальных процедур классификации.
На этапе предварительного отбора параметров экспертиза необходима для того, чтобы какая-либо характеристика не оказалась неучтенной. На этом этапе эксперт достигает полноты учета характеристик за счет понимания содержания исследования с одновременным использованием фактографического материала кластерной матрицы. При этом эксперты, как правило, игнорируют формализованные правила выбора признаков, а придают решающее значение опыту и интуиции. Очевидно, руководитель исследования имеет возможность сделать поправку на компетентность эксперта в рассматриваемом вопросе.
Практически в задачах кластерного анализа компетентность экспертов измеряется как отклонение заявленных ими образов от установившихся и обоснованных кластеров.
Компетентность экспертов может быть вычислена как метрическая мера вероятности ошибки распознавания уже классифицированных объектов. Исследователем устанавливаются границы допустимых погрешностей экспертов, причем далеко уклонившиеся от нормы эксперты признаются нерелевантными источниками информации, использование мнений которых неэффективно.
53. Кластеризация с помощью экспертных оценок. Алгоритм.
54. Кластеризация методом определения «ближайших соседей».
Этот универсальный метод классификации может использовать критерий близости объектов в метрической системе мер, или критерий подобия объектов. Исходные данные об элементах рассматриваемого множества должны быть представлены в матричной форме. Обязательной характеристикой исходных данных должна быть возможность их сравнения для определения иерархических уровней.
Метод «ближайших соседей» основан на иерархической агломеративной модели обработки матрицы, содержащей данные обо всех парах объектов классификации, расстояниях между ними или коэффициентах подобия. Таким образом, возможна классификация исходного множества малыми кластерами с очень близкими характеристиками. С увеличением радиусов кластеров сходство будет уменьшаться, а количество объектов в каждом кластере увеличиваться.
Метод «ближайших соседей» ставит задачу выбора первого объекта классификации, которая в предыдущих методах решалась случайным образом. В предлагаемой постановке подобный подход не может быть реализован, потому что содержание классификации зависит от того, какой элемент будет назван первым. В связи с этим предлагается до начала кластеризации сформулировать критерий значимости характеристик объектов и в соответствии с этим критерием выбрать первый объект.
Очевидно, при жестких граничных условиях первоначально каждый объект образует единственный собственный кластер, куда другие объекты не могут входить, затем постепенно кластер включает в себя и другие объекты из наиболее близких по схожести или подобию. Это включение происходит путем парных сравнений.
Алгоритм кластеризации методом «ближайшего соседа» по эффективности не уступает более сложным методам, а по доступности расчетов превосходит их. К ограничениям метода можно отнести требование минимальной изменчивости во времени исходного множества объектов. Поэтому динамично развивающиеся системы не могут быть объективно классифицированы методом «ближайшего соседа».
В иерархической системе, которая должна быть разделена на условно однородные группы объектов, выделяется или один признак, или группа признаков, определяющая значимость объектов. Таким образом, выстраивается цепочка ранжированных объектов, пригодных для последующей кластеризации.
Метод «ближайших соседей» предусматривает последовательную сортировку объектов исследования (элементов классифицируемого множества). Таким образом, выстроив иерархическую последовательность кластеров, можно определить, какой минимально допустимый уровень сходства объекта и кластера достаточен для получения приемлемого уровня их объединения. Все коэффициенты сходства или подобия должны быть определены заранее и занесены в матрицу. По этим коэффициентам выполняется идентификация априорных совокупностей (подмножеств) с «ближайшими соседями». Алгоритмом предусматривается, что все значения коэффициентов (элементов матрицы) после идентификации и включения в кластерную модель должны быть исключены из дальнейшего рассмотрения.