Joining (tree clustering)

В агломеративных методах происходит последовательное объединение наиболее близких объектов в один кластер. Процесс такого последовательного объединения можно показать на графике в виде дендрограммы, или дерева объединения.

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

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

Исходными данными для анализа могут быть сырые данные (объекты и их параметры) или матрица расстояний между объектами. Если матрица расстояний еще не вычислена, то агломеративный алгоритм tree clustering начинается с вычисления расстояний между
объектами, так как в основе процедур кластерного анализа лежит группировка сходных между собой объектов в некоторые группы (или кластеры). Именно поэтому понятие сходства имеет для него первостепенное значение. Несмотря на кажущуюся простоту, понятие сходства и особенно процедуры, используемые при измерении сходства, не так просты. Количественное оценивание сходства отталкивается от понятия метрики, или расстояния (distance) между объектами. Интуитивно понятно, что чем меньше расстояние между объектами, тем больше сходство между ними.

Обычно рассматриваются следующие меры сходства:

• Евклидова метрика - наиболее часто используемая мера сходства.

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

Расстояние (х, y)=yi(x/-y/)².

• Квадрат евклидовой метрики. Расстояние (х, у)= 2(х/-у/)².

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

Расстояние (х, у)= s|x/-y/|

• Метрика Чебышева. Расстояние (х, у)= мах\_х. - у .

• Метрика Минковского. Расстояние (х, у)= yZ(x/-y/)^p.

• Коэффициент корреляции Пирсона (точнее, 1 - коэффициент корреляции Пирсона).

• Коэффициент совстречаемости - метрика, наиболее пригодная для данных, представленных в шкалах наименований.

Однозначного ответа на вопрос, какую из мер сходства выбрать, не существует. Ответ зависит от типа данных и природы решаемой задачи.

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

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

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

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

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

6. Центроидный метод.Расстояние между двумя кластерами определяется как евклидово расстояние между центрами (средними) этих кластеров. Кластеризация осуществляется поэтапно: на каждом шаге объединяют два кластера, расстояние между которыми минимально.

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

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

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

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

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

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

Можно сказать, что вычислительная процедура данного метода представляет собой дисперсионный анализ «наоборот». Программа начинает работу с к случайных кластеров, а затем перемещает объекты из одного кластера в другой с целью (1) минимизировать вариативность (дисперсию) внутри кластера и (2) максимизировать вариативность между кластерами. Это аналогично дисперсионному анализу «наоборот» в том смысле, что в дисперсионном анализе при определении значимости различий в средних значениях групп оценивается межгрупповая дисперсия в сравнении с внутригрупповой дисперсией. В методе k-средних программа пытается перемещать объекты между группами (кластерами) таким образом, чтобы получить наиболее значимые результаты дисперсионного анализа. Поэтому и результаты этого самого дисперсионного анализа приводятся в разделе результатов применения данного метода.