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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обозначим: М=å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. Поэтому исследователи обычно вводят промежуточные ограничения для сокращения числа рассматриваемых вариантов.