Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Неметрическое шкалирование. Схема алгоритма Каскала.




Читайте также:
  1. E) схема данных.
  2. Алгоритм. Свойства алгоритма. Способы описания алгоритма. Примеры.
  3. Архитектура монитора обработки транзакций (схема и описание).
  4. Архитектура ЭВМ. Обобщенная структурная схема ЭВМ (классическая).
  5. Балансная схема УПТ
  6. Бизнес-процесс: общая схема, описание
  7. БЛОК-СХЕМА АЛГОРИТМУ
  8. Блок-схема осциллографа.
  9. Вопр. Понятие алгоритма. Способы описания алгоритмов
  10. Вопрос 41.Основные ф-ии СЧМ.Понятие замкнутой и разомкнутой СЧМ.Схема замк-й СЧМ. Показатели качества систем человек-машина

Рассмотрим один из известных алгоритмов неметрического многомерного шкалирования, предложенный Дж. Краскалом. Пусть – оценки координат, где i – номер точки; k – номер координаты; – оценка расстояний по -метрике; ранговые образы расстояний, иначе отклонения. Эти величины должны соответствовать, насколько это возможно, оценкам расстояний, но с сохранением условия монотонности: . (12.1)

Для оценки степени расхождения вводят меру соответствия (S-стресс):

либо , где – среднее арифметическое оцененных расстояний.

Наряду с S-стрессом используется SS-стресс, где в числителе оценки расстояний и отклонения заменены их квадратами. SS-стресс обеспечивает более быструю сходимость, если матрица различий симметрична.

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

1) формирование стартовой конфигурации, то есть получение начальных оценок координат (размерность пространства предполагается известной);

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

3) неметрический этап, в ходе которого вычисляются отклонения;

4) метрический этап: перерасчет оценок координат;

5) подсчет меры соответствия.

Если мера улучшилась, то возвращаются к этапу 2; в противном случае работа алгоритма завершается.

Рассмотрим перечисленные этапы подробнее. Стартовая конфигурация строится по методу Торгерсона (ортогональное проектирование). Затем по координатам найденных точек вычисляется матрица расстояний с элементами .

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

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


Дата добавления: 2015-01-19; просмотров: 10; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.018 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты