'稳定'的多维缩放算法

Question

我有一个节点的无线网状网络,每个节点都能够向其邻居报告它的"距离",以(简化的)信号强度测量它们.节点在地理上位于3d空间中,但由于无线电干扰,节点之间的距离不需要三角(三角)？一致.即,给定节点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 - 与之前的2相同,但节点1-3在另一个方向:

图4 - 在一条线上的节点的初始布局,它们在y轴上的位置不会改变:

Answer 1

大多数缩放算法有效地在节点之间设置“弹簧”，其中弹簧的静止长度是边缘的所需长度。然后，他们尝试最小化弹簧系统的能量。但是，当您初始化所有节点时，移动任何一个节点时释放的能量在每个方向上都是相同的。因此，相对于每个节点位置的能量梯度为零，因此算法将节点留在原来的位置。类似地，如果您以直线开始它们，则渐变始终沿着该线，因此节点仅沿着该线移动。

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

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

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