Тема Системы линейных уравнений

4Меры сходства и различия.

Мы рассмотрим меры сходства между двумя индивидами или, что менее обычно, между двумя признаками. Строго говоря, увеличение положительной меры соответствует увеличению сходства в случае меры сходства и уменьшению сходства в случае меры различия, однако это различие не всегда соблюдается, и часто в обоих случаях говорят о мерах сходства. На практике все современные системы имеют дело с мерами различия. Различают два главных класса. Первый включает (i,j) -меры, т.е. меры, которые могут быть вычислены для двух элементов или групп элементов до их объединения, если известны характеристики этих элементов или групп. Второй класс включает (ij,k)-меры, связывающие характеристики групп до и после объединения. В литературе можно найти огромное число предлагаемых мер, некоторые из которых довольно необычны, однако превалируют четыре главных класса. Это следующие меры: 1) коэффициент корреляции; 2) меры, основанные на евклидовой метрике; 3) меры, основанные на манхеттенской мере (называемой также мерой в городских кварталах или мерой на решетке) и 4) информационные статистики. Мы рассмотрим каждый из этих классов. Элементы матрицы исходных данных будем обозначать , где i – номер индивида, а j – номер признака. В случае бинарных признаков будем использовать (а, b, с, d)-обозначения, где а — число признаков, которыми обладают оба индивида; d —число признаков, не встречающихся ни у одного из двух индивидов; b и с - числа признаков, которыми обладает только один из индивидов. Будем называть (1-х) "дополнением х до единицы". Другие символы и термины будут определяться по мере надобности.

Коэффициент корреляции. Коэффициент корреляции используется в классической статистике как мера связи между двумя переменными. Пусть имеется всего n индивидов и пусть — средние по всем индивидам значения для j-го и k-го признаков соответственно. Тогда коэффициент корреляции между признаками j и k вычисляют по формуле

В бинарном случае, когда , мы можем использовать обозначения а, b, с, d. Формула для коэффициента корреляции, известного в этом случае обычно как φ-коэффициент Пирсона, принимает тогда вид

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

Евклидова метрика. Это метрика Минковского второго порядка, определяемая формулой (расстояние между индивидами 1 и 2):

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

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

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

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

Манхеттенская метрика. Эта метрика, являющаяся частным случаем метрики Минковского порядка 1, определяется формулой

Приведенное выражение часто делится на число признаков.

Стандартизация числовых признаков осуществляется разными способами. К числу наиболее известных относятся канберровская метрика и метрика Брея-Кертиса.

Метрика Брея—Кертиса. Эта метрика задается формулой

Хотя в этом случае значения и заключены между 0 и 1, все же признаки с большим размахом будут оказывать доминирующее влияние. Обычно перед использованием этой метрики данные стандартизуют (первоначально метрика была предназначена для случая, когда все х_1j были процентными долями). Данные после стандартизации должны быть неотрицательными. Процедура используется не часто, однако имеет своих приверженцев.

Канберровская метрика. Эта метрика задается выражением

MERGEFORMAT

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

Порядковые переменные. Обрабатываются как числовые.

Номинальные переменные. Представляет интерес лишь ситуация, когда результат сравнения по номинальному признаку равен 1, если состояния пересекаются, и 0 – в остальных случаях. В этом случае наиболее подходящей будет мера Брея — Кертиса. В полностью бинарном случае мера Брея-Кертиса принимает вид (b+с)/(2а+b+с). Канберровская мера аналогичным образом принимает вид (b+c)/(а+b+с).

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

Бинарные признаки. Пусть имеется группа из п элементов, описываемых присутствием или отсутствием s признаков, и пусть а_j элементов обладают признаком j. Определим информационное содержание такой группы выражением

Пусть информационное содержание двух групп А и В равно соответственно I_A и I_B, и пусть обе группы объединены в одну группу С с информационным содержанием I_C. Тогда можно определить информационный выигрыш от слияния двух групп формулой

Информационное содержание одного элемента или группы одинаковых элементов в этой модели всегда равно нулю.

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

Информационный выигрыш определяется, как и прежде. Запишем его в явном виде. Пусть два объединяющихся элемента представлены векторами-строками (a_1j) и (a_2j), r_i - суммы по строкам (i = 1, 2), с_j- сумма по столбцу и N - общая сумма. Тогда

Эта величина называется также переданной информацией.

5Стратегии объединения (агломеративные системы).

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

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

Комбинаторные решения. Если при заданной начальной матрице различий все остальные меры между индивидом и группой или между двумя группами вычисляются, исходя из нее, рекурсивно, то процедура называется рекурсивной. (i,j)-меры обычно могут рассматриваться с позиций одной линейной модели. Пусть имеются две группы i и j с п_i и n_j элементами соответственно; мера различия между этими группами обозначается d_ij. Допустим, что d_ij — минимальная мера из всех оставшихся, так что i и j объединяются и образуют новую группу k с элементами. При объединении должны быть вычислены меры различия вновь образованной группы со всеми остальными группами. Рассмотрим некоторую другую группу h с n_h элементами. Перед объединением известны значения . Положим

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

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

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

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

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

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

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

Стратегия группового среднего. Если одна группа состоит из m₁, а другая из m₂ индивидов, то расстояние между этими группами в данной стратегии определяется как среднее арифметическое из расстояний между индивидами из этих групп. Параметры стратегии равны: . Стратегия монотонна и сохраняет метрику пространства. Она рекомендуется, когда искусственное разделение групп не нужно.

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

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

Гибкая стратегия. Применима для любой меры различия и определяется четырьмя ограничениями .

Стратегия монотонна, и ее свойства полностью зависят от β. Если β=0, то стратегия сохраняет метрику пространства. Если β принимает положительные значения, то стратегия сжимает пространство, а если отрицательные, то растягивает. На практике обычно используют значение β =-0,25.

6Разделяющие (дивизивные) стратегии.

Теоретические преимущества дивизивных стратегий перед агломеративными состоят в следующем: 1) процесс начинается с использования максимального информационного содержания; 2) деление не обязательно должно продолжаться до тех пор, пока вся популяция будет разделена до отдельных индивидов; 3)если число признаков меньше, чем число индивидов, то количество вычислений уменьшается, так как время, требуемое для реализации дивизивного процесса, приблизительно пропорционально квадрату числа признаков s², тогда как для агломеративного - квадрату числа индивидов n². Однако до недавнего времени все дивизивные программы были монотетическими, т.е. дихотомизация популяции проводилась на каждом шаге на основании только одного признака. Такая процедура чувствительна к ошибкам определения или кодирования признака, по которому проводится деление. Все индивиды с отклоняющимися значениями этого признака порождают "ложные" ветви иерархии.

7Приведем пример кластеризации на основе объединяющей стратегии.

Пусть имеется 5 законодателей, обозначенных буквами от V до Z и результаты их персональных голосований по 8 законопроектам, обозначенным буквами от a до h. Эти результаты в оцифрованном виде, приведены в следующей таблице:
abcdefghV10111001W10110101X01101010Y01111011Z01111000

Будем использовать Манхеттенскую метрику, то есть будем считать, что мера различия между законодателями есть число несовпадений в их голосовательных векторах. Подсчитаем все меры различия. Для того, чтобы подсчитать меру различия между V и W, сравним соответствующие вектора-строки: число несовпадений – 2. Продолжая процесс, получим следующую матрицу расстояний:

VWXYZV0W20X570Y3520Z35220

Будем использовать для объединения законодателей стратегию группового среднего. Минимальное из расстояний равно 2. Начнем объединение с образования группы VW, состоящей из V и W. Необходимо рассчитать расстояния между новой группой и остальными законодателями. Рассчитаем расстояние d(VW,X) между VW и X. Согласно стратегии группового среднего оно равно среднему арифметическому из расстояний d(V,X) и d(W,X):

Рассчитав аналогичным образом остальные расстояния, получаем новую матрицу расстояний:

VWXYYZVW0X60Y420Z4220

Минимальное из расстояний по-прежнему равно 2. Объединим пару XY, соответствующую этому расстоянию. После перерасчета расстояний получаем:

VWXYZVW0XY50Z420

Объединяем XY и Z.

VWXYZVW0XYZ4,6670

Полученные группы можно слить в одну. Однако это объединение происходит на качественно ином уровне. Если до сих пор объединение происходило при значении расстояния 2, то есть практически при одинаковой степени близости, то сейчас расстояние между кластерами составляет уже 4,667, что составляет резкий скачок. Разумно, поэтому, остановиться на данном этапе кластеризации. Окончательной структурой кластеров считаем структуру VW-XYZ. Процесс объединения можно проиллюстрировать дендрограммой:

V 2

VW

W

VWXYZ

X XY 4,667

Y 2 XYZ

2

Z