Неметрическое шкалирование

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

Р.Шепард, а затем Дж. Краскал, предложили метод оценки координат объектов при менее жестких предположениях, чем у Торгерсона [26]. В отличие от модели Торгерсона, требующей выполнение условия (5.26), алгоритм Шепарда основан на следующем предположении:

, (5.34)

где – произвольная монотонная функция, такая, что

. (5.35)

Примерами таких функций могут служить линейная, степенная, показательная, логарифмическая функции.

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

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

Определение

Любой алгоритм оценки координат объектов, основанный на предположении, что различия между объектами связаны с расстояниями в пространстве неизвестной монотонной функцией, удовлетворяющей условию (5.35), называется алгоритмом неметрического многомерного шкалирования [26].

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

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

. (5.36)

Рассмотрим три основных меры соответствия: «стресс», «S-стресс» и «коэффициент отчуждения». Краскал предложил две стресс-формулы («стресс, формула 1» и «стресс, формула 2»):

; (5.37)

, (5.38)

где – среднее арифметическое значение оценок расстояний.

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

Ф. Юнг предложил две формулы типа «S-стресс»:

; (5.39)

, (5.40)

где – среднее арифметическое значение квадратов оценок расстояний.

С вычислительной точки зрения удобнее использовать функцию (5.37) или (5.39) [26].

Л. Гуттман предложил третью меру – коэффициент отчуждения:

, (5.41)

где – коэффициент монотонности.

Коэффициент монотонности является мерой согласованности исходных данных и оценок расстояний. Поэтому максимизация равносильна минимизации коэффициента отчуждения K. Чем лучше подогнана неметрическая модель к исходным данным, тем меньше величина K, т.е. K – это мера несоответствия.

Для анализа качества модели в многомерном шкалировании используют два типа графиков разброса [26, 16].

1. Диаграмма образов Гуттмана: по одной оси откладываются оценки расстояний , а по другой – оценки отклонений . Чем ближе точки к биссектрисе первого координатного угла, тем лучше модель описывает данные. Резко выделяющиеся точки нужно подвергнуть тщательному анализу.

2. Диаграммы Шепарда – это графики зависимости оценок отклонений или оценок расстояний от исходных данных . Эти графики дают наглядное представление о функции, которая может быть взята в качестве монотонной функции f из (5.34).

Алгоритм неметрического многомерного шкалирования состоит из четырех основных этапов:

1. поиск стартовой конфигурации;

2. стандартизация расстояний и оценок координат;

3. оценка отклонений (неметрический этап);

4. оценка координат объектов (метрический этап).

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

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

Вначале каждой итерации осуществляется стандартизация текущих расстояний () и оценок координат (). На первой итерации текущими расстояниями и координатами являются те, которые получены из стартовой конфигурации. Для всех остальных итераций текущие расстояния и оценки – те, которые получены на метрическом этапе предыдущей итерации. Стандартизация расстояний снижает вероятность получения вырожденного решения. Тип стандартизации расстояний зависит от используемой функции стресса. При использовании функции стресса (5.37) расстояния стандартизируются так, чтобы сумма их квадратов была равна 1: . Эта стандартизация может быть выполнена путем умножения каждой нестандартизированной оценки расстояния на такую константу, что сумма их квадратов будет равна 1. Поскольку оценки координат объектов должны быть выражены в том же масштабе, что и расстояния, каждая оценка координат должна быть умножена на ту же константу. После стандартизации расстояний указанным способом формула (5.37) принимает вид:

. (5.42)

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

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

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

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

Рассмотрим алгоритм неметрического этапа, предложенный Л. Гуттманом. Он является альтернативой описанному неметрическому алгоритму Краскала. На неметрическом этапе Гуттмана каждое отклонение устанавливается равным одной из текущих оценок расстояний. А именно, если пара объектов соответствует r -му по величине различию , то отклонение устанавливается равное r -ой по величине оценке расстояния [26].

Монотонную последовательность можно получить также как оценку монотонной функции регрессии (линейной, параболической, логистической) по [16].

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

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

Задача нахождения состоит в минимизации выбранной меры соответствия и решается чаще всего градиентными методами: методом наискорейшего спуска или методом сопряженных градиентов. Чем меньшее значение принимает каждый из представленных критериев (5.37)-(5.41), тем лучше неметрическая модель подогнана к данным.

Для нахождения можно также воспользоваться формулой, предложенной Дж. Лингосом и Э. Роскамом [43, 16, 33, 26]:

, , . (5.43)

Для того чтобы избежать деления на нуль, при отношение полагают равным 1.

Как и в метрическом шкалировании, в неметрическом шкалировании сталкиваются с решением вопросов о размерности, вращении и интерпретации полученного решения.

На практике при решении задачи неметрического многомерного шкалирования размерность конфигурации k, как правило, не известна и определяется в процессе анализа. В этом случае рекомендуется получить решения в пространствах различных размерностей k и выбрать одно из них исходя из критериев интерпретируемости, воспроизводимости и соответствия. Критерий интерпретируемости диктует выбор минимально возможно размерности, в которой проявляются существенные характеристики объектов (упорядочения или группировки). Воспроизводимость требует, чтобы решение было составлено из тех координатных осей, которые возникают в разных подвыборках. Один из способов оценки соответствия состоит в построении графика зависимости меры соответствия от размерности признакового пространства. Значение, при котором наблюдается изгиб графика, и рекомендуется выбрать в качестве k. На практике редко возникает необходимость добавлять больше координатных осей, чем это необходимо для снижения стресса ниже 0, 05. Согласно Дж. Краскалу и М.Вишу, не следует признавать решение со значением стресса выше 0, 1, если это решение не одномерно. При значение стресса равное 0, 15 и ниже свидетельствует о хорошем соответствии данным. Одномерное решение часто образует при шкалировании в двумерном пространстве формы типа C или U. Упорядочение объектов вдоль C или U должно соответствовать их упорядочению по одной координате [26].

Неевклидовы решения поворачивать не следует, так как при этом уменьшается соответствие оценок расстояний данным. В приложениях типа «верификация конфигурации» и «сжатие данных» в размерностях 1 и 2 важные характеристики объектов будут очевидны и без поворота. В координатных приложениях, а также в размерностях 3 и больше для интерпретации поворот может быть необходим.

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

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