利用k最近邻求解相似度矩阵

Question

利用k最近邻求解相似度矩阵

在无向有权图中，如下图所示，利用k最近邻求解图的相似度矩阵，应该如何计算呢？希望可以举例说明。

另：对于顶点x5来说，与其连接的只有x2这一个点，对于其2个最近邻，x1与其没有直接的连接，x1能算为x5的2个最近邻中的一个吗？

Answer 1

因为KNN求W矩阵有两种原则，一种是只要其中一个顶点是另一个顶点的k近邻即可，还有一种是两个顶点要互为彼此的k近邻才行。
从这个图看，如果用前面的原则x1就是x5的一个最近邻。 但如果用后面的原则x1就不是x5的一个近邻，因为x5并非x1的2个最近邻中的1个，所以不满足后面的原则。