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

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

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

3. Измерение характеристик объектов и их представление в задачах кластеризации

4. Целевые функции кластеризации

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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