Меры Расстояния

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

Евклидово расстояние.

Это вероятно наиболее часто используемый тип расстояния. Оно является простым геометрическим расстоянием в многомерном пространстве и вычисляется как:

distance (x, y) = {S (x - y)}

Квадрат евклидова расстояния.

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

distance (x, y) =S (x - y)

Покоординатное расстояние.

Это расстояние в некотором смысле усредняет разницу между различными компонентами векторов. В большинстве случаев, эта мера расстояния дает результаты, подобные простому евклидову расстоянию. Однако, отметим, что при данной мере, эффект привносимый отдельными большими компонентами демпфируется (так как они не возводятся в квадрат). Покоординатное расстояние вычисляется так:

distance (x, y) =S | x - y |

Расстояние Чебышева.

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

distance (x, y) =Maximum | x - y |

Степенное расстояние.

Иногда может потребоваться увеличить или уменьшить вес увеличения расстояний по измерениям. Это может быть достигнуто путем использования степенного расстояния. Расстояние это вычисляется как:

distance (x, y) = (S | x - y |)

Где r и p - определяемые пользователем параметры. Поведение данной меры выглядит следующим образом: Параметр p контролирует вес разностей по отдельным компонентам, параметр r контролирует вес придаваемый расстоянию между объектами в целом. Если r и p равны 2, то это расстояние равно Евклидову расстоянию.

Мера “доли рассогласования”

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

distance (x, y) = (Кол-во x # y) /i

Объединение или Правила связывания

На первом шаге, когда каждый объект представляет собой кластер, мы определяем расстояния между объектами выбирая соответствующую меру. Однако, когда несколько объектов были связаны вместе, как нам определить расстояние между новыми кластерами? Другими словами, нам требуется правило слияния, определяющее являются ли два кластера достаточно близкими для того, чтобы быть связанными. Имеются различные возможности: например, мы могли бы связывать два кластера вместе, когда любые два их представителя ближе друг к другу чем соответствующий порог связывания. Другими словами, мы используем " ближайших соседей ", чтобы определить расстояние между кластерами; этот метод называется одиночным связыванием. Это правило порождает "размытые" кластеры, то есть кластеры связанные только одиночными объектами, оказавшимися близко друг к другу. Альтернативно, мы можем использовать наиболее удаленных соседей,; Этот метод называется полным связыванием. Имеется множество других правил связывания типа тех, которые были предложены, и модуль кластерного анализа предлагает широкий выбор таких правил.

Одиночное связывание (метод ближайшего соседа).

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

Полное связывание (метод дальнего соседа).

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

Невзвешенное попарно-групповое среднее.

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

Взвешенное попарно-групповое среднее.

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

Невзвешенное расстояние между центрами масс.

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

Взвешенное расстояние между центрами масс.

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

Метод Ward’а.

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

Метод K-внутригрупповых средних - Краткий обзор

Общая логика

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

Пример.

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

Вычисления.

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

Интерпретация результатов.

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

Метод K-внутригрупповых средних - Краткий обзор

Общая логика

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

Пример.

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

Вычисления.

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

Интерпретация результатов.

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

Двунаправленное объединение - Краткий обзор.

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