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

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

Максимальная концентрация объектов в каждом кластере около расчетного ядра.

Максимальное приближение реального числа кластеров к теоретически идеальному.

Максимальное однородность объектов в каждом кластере

Максимальное суммарное расстояние между границами кластеров

Максимально возможная компактность каждого кластера

Компактность кластера можно определить следующим образом:

• разделить исходное множество на кластеры;

• у каждого кластера вычислить условный «центр массы».

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

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

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

Лекция №4 Методы кластеризации

I. Кластеризация полным перебором объектов

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

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

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

II. Кластеризация методом перебора фиксированных расстояний от центров сфер (алгоритм «форель»).

Существует последовательность действий, характерная для большинства известных процедур алгоритма «Форель»:

1. Случайно-интуитивным способом выбирается точка (объект классификации) в некотором метрическом пространстве.

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

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

4. Все объекты, попавшие в построенную сферу, становятся элементами кластера. Далее выбирается какой-либо новый элемент из сферы, который становится центром новой сферы того же радиуса.

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

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

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

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

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

Алгоритм «Форель» имеет существенные недостатки:

~ отсутствуют автоматические критерии качества кластеризации

~ границы между кластерами могут не иметь явно выраженных функций «водораздела».

~ нет возможностей изменения правил выбора граничных значений кластеров, как следствие - ограниченные возможности для практического использования.

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

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

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

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

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

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

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

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

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

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

Недостатки метода:

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

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

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

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

С помощью экспертных оценок возможно решение следующих задач кластерного анализа:

• установление границ кластеров и определение дискриминантных функций;

• поименное отнесение каждого объекта к определенному кластеру в соответствии с субъективным мнением экспертов;

• целевой отбор признаков (характеристик) для формирования кластеров и последующего изучения пространства объектов или придания признакам «весовых» оценок;

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

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

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

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

VII. Кластеризация методом определения «ближайших соседей», включая иерархическое распределение объектов.

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

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

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

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

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

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

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

Дата добавления: 2014-01-11