Исследователь может менять параметры алгоритма «Форель». В зависимости от правильности выбора начальной точки - центра сферы конфигурация кластера и число кластеров существенно меняются. Поэтому имеет смысл провести кластеризацию несколько раз, меняя начальную точку и сравнивая полученные варианты. В том случае, если исследователя не удовлетворяет количество объектов, вошедших в кластер, или число сфер, то для измерения этих параметров можно варьировать значения радиуса сферы. Очевидно, увеличение радиуса приведет к расширению состава кластера, и наоборот.
Алгоритм «Форель» имеет существенные недостатки:
-отсутствуют автоматические критерии качества кластеризации
-границы между кластерами могут не иметь явно выраженных функций «водораздела».
-нет возможностей изменения правил выбора граничных значений кластеров, как следствие - ограниченные возможности для практического использования.
47. Сферический метод двухступенчатой кластеризации
Метод разработан на основе алгоритма «Форель», устраняя некоторые его недостатки. Сферический принцип построения кластеров более жесткий и предполагает минимальное вмешательство исследователя в классификацию на стадии вычисления и группировки кластеров. Множество объектов в сфере (гиперсфере) разделяется на ядро (наибольшее сгущение) и менее плотную часть.
Сферический метод кластеризации позволяет строго очертить границы между кластерами и однозначно присваивать каждому объекту принадлежность к какой-либо сфере. Но такие строгие границы оставляют достаточно много объектов (до 60 %) за пределами классифицированных множеств. Повышение качества кластеризации требует значительного уменьшения диаметра сфер, что приводит к увеличению кластеров, вплоть до числа, сопоставимого с числом объектов. Но в этом случае кластеризация не упрощает, а усложняет систему управления и теряет практический смысл.
Поэтому метод сферической кластеризации применим для такого расположения множества объектов, при котором существуют плотные ядра с малыми расстояниями между элементами и значительные межгрупповые расстояния, позволяющие пренебречь теми объектами, которые неизбежно окажутся вне сформированных кластеров. Сферический метод предполагает равноудаленность объектов от зоны сгущения с постепенным разрежением по мере удаления от центра сферы или зоны ядра.
48. Метод определения центра кластера с помощью вычисления среднеарифметических расстояний между объектами
Рассматриваемый метод предполагает наличие определенных сведений о содержании кластеров до начала вычислительных процедур. Естественно, априорные предположения могут быть достаточно приближенными. Во избежание ошибочных предположений исследователь может рассмотреть несколько вариантов начальной группировки объектов. Этот метод кластеризации не предполагает каких-либо ограничений геометрической формы кластера.
Предлагаемый алгоритм кластеризации состоит из следующих блоков:
1. Некоторой точке, принадлежащей множеству изучаемых объектов, присваивается геометрический признак центра координатной системы, причем первый объект в этой системе является началом отсчета.
2. Выбирается определенное число объектов (только количество), которые будут участвовать в расчетах условного центра кластера.
3. Далее необходимо задать какой-либо критерий, ограничивающий содержание кластера. В качестве примера ограничений может быть использовано предельное количество объектов в кластере или максимально допустимое расстояние от условного центра до наиболее удаленного объекта, или максимально возможный «водораздел» между наиболее близкими объектами. Исследователь, как правило, самостоятельно решает, какому критерию отдать предпочтение или выработать собственное ограничение на процесс формирования кластера.
4. В зависимости от выбранного алгоритма определения критерия, необходимого для завершения формирования кластера, вычисляется максимально допустимое расстояние между объектами d. Расстояние может задаваться исследователем, исходя из анализа содержательного образа кластера или из соображений насыщенности кластера.
5. Методом перебора определяется объект АК, наиболее близкий к объекту-центру Ац. Далее проверяется выполнение неравенства: |АК - АЦ|£d и, в случае безусловного выполнения этого неравенства, объект АК заносится в матрицу данного кластера. Из дальнейшего рассмотрения объект АЦ исключается.
6. В дальнейшем операции перебора повторяются, причем объект АК становится центром рассматриваемой композиции. Итерации предыдущего блока выполняются до тех пор, пока не останется ни одного объекта вблизи любой из рассматриваемых точек, т. е. будет превышено пороговое значение d.
Варианты классификации предлагаемым методом определяются перебором значений d и начального объекта Ац. При этом достаточно проблематично найти «водораздел» между кластерами из-за случайных помех на поле, в промежутках между сгустками объектов информации. Поскольку метод уравнивает значимость в замкнутом кластере сгущений и одиночных объектов, качество классификации случайно и требует специального изучения. Кроме того, в ряде случаев возможно объединение всех объектов информационного поля в один-два кластера. И наоборот, жестко заданные граничные условия способны вытеснить за пределы кластеров значительное число объектов.
В связи с последовательным включением объектов в кластеры разница между характеристиками начальных и конечных объектов может быть весьма существенной.
49. Метод постоянных кластеров и характеристик
Этот метод удобен в тех случаях, когда классифицируемая система хорошо изучена, и у исследователя существует определенная ясность относительно наиболее значимых характеристик кластеров. При этом исследователь может установить рациональные границы количества кластеров и их характеристики, не производя сложных вычислений. Тогда распределение объектов по кластерам происходит в результате простых арифметических расчетов, без циклических повторений, а в результате одной-двух итераций.
Алгоритм предлагаемого метода основан на содержательном анализе информационного поля до начала процедур кластеризации. На этом этапе исследователь должен определить рациональное число кластеров. исходя из физических возможностей оценки поля объектов, полезности для управления и возможности получения нетривиальных результатов. Введем обозначения: л - рациональное количество кластеров; Аш (1с, I, т) ~ центр «массы» /-го кластера, имеющий координаты ^, /, т.
Рассматриваемый метод позволяет включить все объекты в кластеры. Это серьезный недостаток метода, потому что содержательный анализ информационного поля классификации свидетельствует о существовании достаточно большого количества объектов, которые не могут быть без искажения свойств причислены ни к одному из существующих кластеров. Вообще говоря, этот недостаток можно устранить введением вспомогательных функций максимально допустимых расстояний от центра кластера до наиболее удаленного объекта. Эта функция не может быть постоянной величиной, а должна вычисляться для каждого кластера в зависимости от плотности ядра кластера, количества объектов, дисперсии характеристик и других признаков. Впрочем, это отдельная научная задача.
Вторым недостатком рассматриваемого метода является необходимость предварительного определения количества кластеров и их типовых характеристик. Класс подобных задач чрезвычайно узок и, скорее всего, может быть вторым этапом классификации. То есть вначале каким-либо методом классификация уже проведена, а предлагаемый метод используется для подтверждения или опровержения полученных результатов.
Ограниченный объем вычислений и простота логических процедур позволяют менять количество кластеров при решении одной задачи и выбирать наиболее удобный для интерпретации вариант классификации.
50. Алгоритм метода постоянных кластеров и их характеристик
Рассмотрим алгоритм метода постоянных кластеров и их характеристик:
1-й шаг. Изучение содержательных характеристик информационного поля, анализ данных и определение количества кластеров, их основных характеристик - граничных условий.
2-й шаг. Распределение объектов по кластерам в зависимости от включения координат объекта в граничные условия кластера.
3-й шаг. Вычисление координат центров «массы» кластеров Аш как средних арифметических координат объектов, входящих в рассматриваемый кластер.
4-й шаг. Замена априорных характеристик - границ кластеров на новые критерии кластеризации.
5-й шаг. Принимая точки Ащ,А,а, •••, Ац„ за центры «масс» кластеров (их количество сохранилось), начинаем формирование кластеров заново. При этом используем принцип наибольшей близости объекта к какому-либо центру кластера.
6-й шаг. Пересчитав все расстояния от объектов до каждого из центров и присоединив их к ближайшему, получим новое поле кластеров, при котором все объекты будут принадлежать какому-либо кластеру из определенных заранее.
7-й шаг. Для вновь сформированных кластеров производится перерасчет центров «массы», вычисляются типовые характеристики.