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

У меня есть беспроводная сетчатая сеть узлов, каждая из которых способна сообщать о своем "расстоянии" соседей, измеряя в них (упрощенную) силу сигнала. Узлы географически расположены в трехмерном пространстве, но из-за радиопомех расстояние между узлами не должно быть тригонометрическим (тригономически?) Согласованным. I.e., учитывая узлы 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/. Мне нужно сделать это на С++, и я надеюсь, что смогу использовать готовый компонент, т.е. Не придется повторно реализовывать алгоритм из бумаги. Итак, я подумал: https://sites.google.com/site/simpmatrix/ будет билетом. И это работает, но:

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

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

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

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

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

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

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

Спасибо.

РЕДАКТИРОВАТЬ: меня передали на cs.stackexchange.com, и некоторые комментарии были сделаны там; для алгоритмических предложений см. https://cs.stackexchange.com/info/18439/stable-multi-dimensional-scaling-algorithm.

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

Image 1 - with random initialization matrix

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

Image 2 - after running with same input data, rotated when compared to 1

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

Image 3 - same as previous 2, but nodes 1-3 are in another direction

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

Image 4 - with the initial layout of the nodes on one line, their position on the y axis isn't changed

Ответы

Ответ 1

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

(Это ошибочное объяснение во многих отношениях, но оно работает для интуиции)

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

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

Ответ 2

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

Ответ 3

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

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

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