«Стабильный» алгоритм многомерного масштабирования

Question

У меня есть беспроводная сеть с узлами, каждая из которых способна сообщать о своем «расстоянии» соседей, измеряя их (упрощенную) силу сигнала. Узлы географически расположены в трехмерном пространстве, но из-за радиопомех расстояние между узлами не должно быть тригонометрическим (тригономически?) Согласованным. То есть, если заданы узлы A, B и C, расстояние между A и B может быть 10, между A и C также 10, но между B и C 100.

Что я хочу сделать, это визуализировать логическую схему сети в условия подключения узлов, т.е. включают логическое расстояние между узлами в визуальном.

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

Теперь, похоже, существует много алгоритмов MDS, см., Например, http://homepage.tudelft.nl/19j49/Matlab_Toolbox_for_Dimensionality_Reduction.html и http://tapkee.lisitsyn.me/. Мне нужно сделать это на C++, и я надеюсь, что смогу использовать готовый компонент, т. Е. Не придется повторно реализовывать алгоритм из бумаги. Итак, я подумал: https://sites.google.com/site/simpmatrix/ будет билетом. И это работает, но:

• Схема не стабильна, то есть каждый раз, когда алгоритм повторно запускается, меняется положение узлов (см различия между изображением 1 и 2 ниже - это от того, чтобы выполняются дважды, без каких-либо дальнейших изменений). Это связано с матрицей инициализации (которая содержит начальное местоположение каждого узла, которое алгоритм затем итеративно исправляет), который передается этому алгоритму - я пропускаю пустой, а затем реализация получает случайную. В общем, макет подходит к макету, который я ожидал от данных ввода. Кроме того, между различными прогонами направление узлов (по часовой стрелке или против часовой стрелки) может меняться. См. Изображение 3 ниже.

• «Решение», которое я считал очевидным, состояло в том, чтобы передать стабильную матрицу инициализации по умолчанию. Но когда я сначала кладу все узлы в одном и том же месте, они вообще не перемещаются; когда я помещаю их на одну ось (узел 0 на 0,0, узел 1 на 1,0, узел 2 - 2,0 и т. д.), они перемещаются только по этой оси. (см. изображение 4 ниже). Однако относительные расстояния между ними в порядке.

Так кажется, что этот алгоритм изменяет только расстояние между узлами, но не изменяет их местоположение.

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

• Где я могу найти дополнительную информацию о свойствах каждого из многих алгоритмов MDS?
• Существует ли алгоритм, который выводит полное местоположение каждого узла в сети, без необходимости передавать начальную позицию для каждого узла?
• Есть ли способ оценить местоположение каждой точки, чтобы алгоритм мог правильно масштабировать расстояние между ними? У меня нет географического местоположения каждого из этих узлов, это и есть цель этого упражнения.
• Существуют ли какие-либо алгоритмы для сохранения «угла», при котором сеть получается постоянной между циклами?

Если все остальное не удается, мой следующий вариант будет состоять в использовании алгоритма, упомянутого выше, увеличьте количество итераций, чтобы сохранить изменчивость между прогонами на несколько пикселей (мне пришлось бы экспериментировать с сколько будет выполняться итераций), затем «поверните» каждый узел вокруг узла 0, чтобы, например, выровнять узлы 0 и 1 по горизонтальной линии слева направо; таким образом, я бы «исправил» местоположение точек после того, как их относительные расстояния были определены алгоритмом MDS. Я должен был бы корректировать порядок подключенных узлов (по часовой стрелке или против часовой стрелки) вокруг каждого узла. Это может стать волосатым довольно быстро.

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

Спасибо.

EDIT: Мне было передано сообщение cs.stackexchange.com, и некоторые замечания были сделаны там; для алгоритмических предложений, см. https://cs.stackexchange.com/questions/18439/stable-multi-dimensional-scaling-algorithm.

Изображение 1 - со случайной матрицей инициализации:

Изображение 2 - после того, как работает с такими же входными данными, повернуто по сравнению с 1:

Изображения 3 - то же самое как и предыдущие 2, но узлы 1-3 находятся в другом направлении:

Изображение 4 - с начальной компоновки узлов на одной линии, их положение на оси у не изменяется:

Answer 1

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

(Это некорректный объяснение во многих отношениях, но он работает на интуиции)

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

Если библиотека недетерминирована, либо найдите другую библиотеку, которая является детерминированной, либо откройте исходный код и замените генератор случайности на PRNG, инициализированный фиксированным семенем. Я бы порекомендовал бывшую опцию, хотя, как и другие, более продвинутые библиотеки должны позволять вам устанавливать края, которые вы хотите «игнорировать» тоже.

Answer 2

Я прочитал коды библиотеки MDS «SimpleMatrix» и обнаружил, что для определения порядка точек используется случайная матрица перестановок.После исправления порядка перестановки (просто используйте srand (12345) вместо srand (time (0))), результат же данных не изменится.

Answer 3

Очевидно, что в этом нет точного решения; всего 4 узла ABCD и расстояния AB=BC=AC=AD=BD=1CD=10 вы не можете четко нарисовать подходящую 2D-диаграмму (и даже не трехмерную).

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

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