计算科学 - 通过 Fiedler 向量对邻接矩阵进行排序 - 吾爱随笔录

计算科学线性代数

2021-12-23 01:01:10

我有一个相当稀疏的邻接矩阵，显示我的数据集中大约 5,000 个点之间的连接。我正在寻找各种方法来分析数据点之间的关系。

作者通过 Fiedler 向量对邻接矩阵进行排序，得到了看起来很有趣的结果。

我正在寻找有关这种方法的参考资料。我发现很多参考资料描述了使用 Fiedler 向量的符号将数据分成两组（这可以递归应用）。使用 Fiedler 向量的直接排序是我在文献中没有找到的。谁能告诉我这是否是一种已知的技术，如果是，请指出一些关于它的参考资料？

谢谢！杰里米

3个回答

不确定这是否有名字，但如果 $v_1$ 是 Fiedler 向量（对于第一个非零特征值），并且 $v_2$ , $v_3$ 是接下来两个最小特征值的特征向量，您可以将它们相互绘制，以可能显示划分为多个块。

例如，我构建了一个简单的邻接矩阵，其中包含 4 个组，然后我随机排列。

如果我们绘制 Fiedler 向量，我们可以看到我们不能真正分辨超过 2 个组（它可能看起来像 3 个，但这只是因为我们已经按顺序绘制了索引）。

在此处输入图像描述

如果我们现在改为绘制 Fiedler 向量 $v_1$ 反对 $v_2$ 和 $v_3$ ，它在 3D 中显示了 4 个集群。

在此处输入图像描述

当然，这仍然意味着您必须以某种方式检测您拥有的结果数据中的集群，因此它在实践中可能不太有用。然而，这是一种从图拉普拉斯算子的特征向量中强制提取更多信息的方法。你绝对不想做的是使用 Fiedler 向量 $v_1$ 分成两组以上。

更常见的是，人们只会使用递归谱分区，以及足够的硬编码保护措施来强制您生成的分区正常工作（例如，注意接口）。

我们在 SIGGRAPH 2010 上与同事 (Richard Hao Zhang) 一起提供了关于光谱网格处理的课程。我们给出了光谱分解的不同直觉，作为约束优化问题（瑞利商），作为振动模式（克拉尼板），作为代数问题，作为几何问题以及与热核的联系。

ACM 数字图书馆参考：

幻灯片在这里：

我关于这个主题的（旧）文章：

我使用 PyTorch 创建了一个使用 Fiedler Vector 对距离矩阵进行排序的演示。您可以在这里查看源代码： https ://github.com/dimkastan/PyTorch-Spectral-clustering

其它你可能感兴趣的问题