稳定的多维缩放算法

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算法确定它们的相对距离之后“校正”点的位置。 我还必须纠正每个节点周围连接节点的顺序(顺时针或逆时针)。这可能会很快变得混乱。

显然，我更喜欢稳定的算法解决方案 - 增加迭代次数以平滑随机性不是非常可靠。

谢谢。

编辑：我被引荐到cs.stackexchange.com，那里进行了一些评论。有关算法建议，请参见https://cs.stackexchange.com/questions/18439/stable-multi-dimensional-scaling-algorithm。

图1-使用随机初始化矩阵：

图2-在使用相同输入数据后运行后，与1相比旋转：

图3-与前两者相同，但节点1-3朝另一个方向：

图4-将节点的初始布局放在一条线上，它们在y轴上的位置没有改变:

- Roel

---

在进一步开发我的测试数据集后，我发现我有另一个要求。我没有所有节点之间的距离 - 网络一侧的节点可能无法到达另一侧的节点。我需要一种能够指定这一点的方法，而不必在那些彼此无法到达的节点之间指定较大的距离，因为这样，结果图中它们之间的距离将是相同的。最好是让彼此无法到达的节点相互远离，但如果我只是不在它们之间绘制连接，也许视觉上也会很清晰。 - Roel

你可以添加一个虚假的距离来分离未连接的组（也许你已经知道这一点，但你想要的是图中的"简单连通分量"），但每个组都可以单独进行反射和旋转，不幸的是。我刚刚删除了我的答案，因为它只是重复了你已经有的想法。 - andrew cooke

谢谢，我不知道那个术语，我会朝那个方向进行调查。关于另一个答案，好的，清楚了 - 我只是在检查是否漏掉了什么细节。我能找到的关于这个主题的信息比我的正常工作要密集得多，我需要经常进行二次和三次检查 :) 再次感谢您参与这个小众问题 - 我甚至找不到任何标签可以归类它。 - Roel

没有问题。这些类型的问题最有趣，但它们变得越来越少了... - andrew cooke

Answer 1

大多数缩放算法有效地在节点之间设置“弹簧”，其中弹簧的休息长度是边缘的期望长度。然后，它们试图最小化弹簧系统的能量。但是，当您将所有节点初始化到彼此之上时，任何一个节点移动时释放的能量量在每个方向上都相同。因此，对于每个节点的位置，能量的梯度为零，因此算法保持节点在原处。类似地，如果您将它们全部放在一条直线上，则梯度始终沿着该直线，因此节点只会沿着该直线移动。

（这在许多方面都是有缺陷的解释，但它适用于理解）

尝试将节点初始化为位于单位圆上，网格上或以任何其他方式，使它们不全共线。假设库算法的更新方案是确定性的，则应该给您可重复使用的可视化效果并避免退化情况。

如果库是非确定性的，请找到另一个确定性的库，或打开源代码并使用固定种子初始化的PRNG替换随机生成器。我建议选择前者选项，因为其他更高级的库还应允许您设置要“忽略”的边缘。

- Andy Jones

---

感谢您的回答。自从我提出这个问题以来，我的研究已经让我相信MDS不是解决我的问题的正确方法。（一旦我通过找到一个可行的替代方案来确认这一点，我会尽快更新问题...）可能存在术语问题，但是根据我所知，您所描述的并不是MDS算法，而是图形布局算法。这就是我要使用的方法，主要基于这篇论文：https://www.cs.ubc.ca/~tmm/courses/533/morereadings/dejordy.pdf。Boost.Graph实现了几种基于弹簧的图形布局算法。 - Roel

MDS算法的一个基本特性是需要完整的距离矩阵，即每个节点之间都需要有吸引或排斥作用。而像基于弹簧的图形算法则不需要这样。非常感谢您的回答 - 这正是我要尝试的。正如我所提到的，一旦我验证了实际实现的结果，我将立即更新这个问题。 - Roel

是的，MDS算法与图形布局算法不同（我想知道为什么你不使用后者，但我觉得你有你的理由），但许多/大多数MDS算法在每对节点之间求和某种成本函数，然后使用下山优化技术来使总和的值最小化。在这种情况下，我描述的弹簧比喻仍然是一个漂亮的、物理意义的类比，即使它不像力导向图绘制中那样是算法的基础。无论如何，祝你实现好运！ - Andy Jones

好的，我觉得你的评论在我回复之前的前几次阅读中让我有些困惑。你的新评论让我恍然大悟。感谢你将这两个问题联系起来 - 确实现在我明白了为什么当所有节点都在一行上时我看到了那种行为。在这个心理模型下，确实应该像你说的那样“忽略”边缘，尽管这仍然不能给我想要的行为，就是像我理解的Kamada/Kawai算法那样将网络的“边缘”节点放置在彼此远离的位置，我是对的吗？ - Roel

是的，MDS算法会愉快地显示出所有点共线的树形结构，除非你添加模拟弹簧来强制分离子节点。专门用于图形绘制的算法不应该有这个问题。 - Andy Jones

Answer 2

我已经阅读了"SimpleMatrix" MDS库的代码，并发现它使用随机置换矩阵来决定点的顺序。在修复置换顺序后（只需使用srand(12345)而不是srand(time(0))），相同数据的结果不会改变。

- dydx

Answer 3

显然，这个问题通常没有确切的解决方案；仅有4个节点ABCD和距离AB=BC=AC=AD=BD=1CD=10，你无法清楚地绘制出适合的2D图（甚至不是3D图）。

这些算法所做的就是在节点之间放置弹簧，然后模拟排斥/吸引力（取决于弹簧是否比规定距离短或长），可能还会添加空间摩擦以避免共振和爆炸。

为了保持“稳定”的图表，只需构建一个解决方案，然后仅更新距离，重复使用前一个解决方案的当前位置作为起点。选择两个固定节点并将它们对齐似乎是一个不错的想法，可以防止缓慢漂移，但我认为弹簧力永远不会产生旋转动量，因此我预计只需缩放和居中解决方案即可。

- 6502