2018-02-14
181
Дана симметричная матрица различий между объектами 
.
Требуется построить пространство возможно меньшей размерности r и найти в нем координаты точек-объектов 
так, чтобы матрица расстояний 
между ними, вычисленная по введенной на Х метрике, была, в смысле некоторого критерия, близка к исходной матрице G попарных различий.
При решении поставленной задачи возможны два подхода: метрический, при котором матрица различий G изначально является искомой матрицей расстояний D, и неметрический (монотонный, ранговый), ориентированный на сохранение того же порядка попарных расстояний, что и в исходной матрице различий: 
→ 
.
Неметрический этап
На этом этапе данные о различиях и стандартизированные оценки расстояний из предыдущей итерации используются для вычисления отклонений.
Этап состоит из нескольких шагов.
1. Упорядочить по возрастанию данные о различиях по исходной матрице G. Получившийся порядок пар объектов задает и порядок оценок расстояний или отклонений.
2. Серия проходов: в начале первого прохода на конкретной итерации отклонениями являются текущие оценки расстояний из предыдущей итерации или стартовой конфигурации. В начале каждого последующего прохода на той же итерации отклонения берутся из предыдущего прохода. Проход начинается с разбиения оценок отклонений на блоки равных значений. Пусть m= (1 ,...,M) будет индексом, обозначающим блоки от самого верхнего (m= 1) до самого низкого (m=M). Начиная с m= 1, элементы m -го блока сравниваются с элементами (m +1)-го блока. Если элементы m -го блока меньше элементов (m+ 1)-го блока, необходимо перейти к сравнению двух следующих блоков. Как только элементы m -го блока окажутся больше элементов (m +1)-го блока, то все элементы m -го и (m +1)-го блоков приравниваются среднему арифметическому обоих блоков. Эти два блока объединяют в один, который становится новым
m -ым блоком. Затем опять сравнивают m -й и (m +1)-й блоки; проход заканчивается после сравнения всех соседних блоков. Результат прохода – новый набор оценок отклонений. После завершения проходов отклонения будут удовлетворять условию монотонности (12.1). Пример работы алгоритма дается в табл.27.
|
|
|
Таблица 27
| № п/п | Различие | До объединения | После 1-го прохода | После 2-го прохода | |||
| Откло- нение | Блок | Откло-нение | Блок | Откло-нение | Блок | ||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 1 | 0,19 | 0,11 | 1 | 0,11 | 1 | 0,11 | 1 |
| 2 | 0,22 | 0,12 | 2 | 0,12 | 2 | 0,12 | 2 |
| 3 | 0,23 | 0,16 | 3 | 0,15 | 3 | 0,15 | 3 |
| 4 | 0,25 | 0,14 | 4 | 0,15 | 3 | 0,15 | 3 |
Продолжение табл.27
| № п/п | Различие | До объединения | После 1-го прохода | После 2-го прохода | |||
| Откло- нение | Блок | Откло-нение | Блок | Откло- нение | Блок | ||
| 5 | 0,26 | 0.21 | 5 | 0.21 | 4 | 0.21 | 4 |
| 6 | 0,27 | 0,23 | 6 | 0,23 | 5 | 0,23 | 5 |
| 7 | 0,28 | 0,25 | 7 | 0,25 | 6 | 0,24 | 6 |
| 8 | 0,29 | 0,23 | 8 | 0,23 | 7 | 0,24 | 6 |
| 9 | 0,32 | 0.27 | 9 | 0.27 | 8 | 0,27 | 7 |
|
|
|
В столбце 3 нет подряд идущих одинаковых чисел, так что каждая строка образует блок. Просматривая этот столбец сверху вниз, обнаруживаем, что в строках 3 и 4 имеет место инверсия (нарушение монотонности –– 0,16>0,14). Блоки 3 и 4 объединяются в один со значением (0,16+0,14)/2=0,15. Просматривая теперь столбец 5, убеждаемся в необходимости слияния блоков 6 и 7. Как видно из 7-го столбца нарушений условия монотонности не осталось, что позволяет считать элементы столбца 7 искомыми отклонениями 
.
Метрический этап
На этом этапе решают задачу математического программирования, в результате чего получают новые оценки координат, по которым рассчитывают новые оценки расстояний. Исходными данными являются отклонения, рассчитанные на неметрическом этапе, оценки координат и расстояний предыдущей итерации. В качестве целевой функции выступает S 1 (12.2).
Минимизация S 1 проводится одним из градиентных методов.
ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 12
- Многомерные методы экспериментальной оптимизации.
