Итерационные методы кластерного анализа

Сущность этих методов заключается в том, что процесс классификации начинается с задания некоторых начальных условий (количество образуемых кластеров, порог завершения процесса классификации и т.д.). К итерационным методам кластерного анализа относят метод k -средних (Мак-Куина), метод поиска сгущений, метод взаимного поглощения и др. [12, 43].

Метод k-средних

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

Для начала процедуры классификации задаются р случайно выбранных объектов – эталонов классов (ε). Каждому эталону приписывается порядковый номер, который, одновременно, является номером класса. Из оставшихся n - p объектов извлекается объект и проверяется, к какому из эталонов он находится ближе. Данный объект присоединяется к тому эталону, расстояние до которого наименьшее. Веса и эталоны классов пересчитываются по правилу:

где – «вес» класса, – номер итерации.

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

Через n - p итераций все объекты будут отнесены к одному из p кластеров. Для достижения устойчивого разбиения, все n объектов опять разбиваются на p классов. Новое разбиение сравнивается с предыдущим. Если они совпадают, то работа алгоритма завершается, в противном случае алгоритм повторяется.

Метод поиска сгущений

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

Метод поиска сгущений требует вычисления матрицы расстояний (матрицы мер сходства) между объектами. Затем выбирается объект, который является первоначальным центром первого кластера. Выбранная точка принимается за центр гиперсферы заданного радиуса . Определяется совокупность точек, попавших внутрь этой сферы, и для них вычисляются координаты центра (вектор средних значений признаков). Далее вновь рассматриваем гиперсферу такого же радиуса, но с новым центром, и для совокупности попавших в нее точек опять рассчитываем вектор средних значений, принимаем его за новый центр сферы и т.д. Когда очередной пересчет координат центра сферы приводит к такому же результату, как и на предыдущем шаге, перемещение сферы прекращается, а точки, попавшие в нее, образуют кластер и из дальнейшего процесса кластеризации исключаются. Для всех оставшихся точек процедуры повторяются, то есть опять выбирается произвольный объект, который является первоначальным центром сферы радиуса , и т.д.

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

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

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

Если начинать работу алгоритма с величины и при каждом его повторении изменять на небольшую величину, то можно выявить значения радиусов, которые приводят к образованию одного и того же числа кластеров, то есть к устойчивому разбиению [43].

Метод взаимного поглощения

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

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

Изменяя величину , можно повторить разбиение несколько раз. В качестве окончательного решения задачи следует выбирать вариант разбиения, сохраняющийся при нескольких значениях , как наиболее устойчивый [43].

Все задачи кластерного анализа в зависимости от назначения можно разделить по следующим критериям:

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

2. В случае А2 речь идет о классификации достаточно больших массивов многомерных наблюдений (n – порядка нескольких сотен и тысяч) – классификация индивидуумов, семей, изделий.

Такое разделение задач классификации хотя и условно, но весьма необходимо с точки зрения принципиального различия идей и методов, на основе которых конструируются кластер-процедуры. Так, иерархические кластер-процедуры предназначены в основном для решения задач типа А1Б1, А1Б2, А1Б3, итерационные кластер-процедуры – А2Б1, А2Б2.