基于权重的图顶点分类算法

Question

基于权重的图顶点分类算法

3

我有一个完整的加权图，每个权重代表下一个顶点属于相同类别的概率。我预先知道某些顶点所属的类别；那么我如何能够对其余每个顶点进行分类？

在更详细的描述中，我可以将问题描述如下：对于所有顶点N和簇C，我们有一个集合，其中我们确定了节点属于哪个特定的簇：P(v_n|C_n)=1。从给定的图中，我们还知道每个节点与其他节点属于相同簇的概率：P(v_n1∩C_n2)。基于此，我们如何估计每个其他节点的簇？

- Eduardo Gonçalves

概率是多少（100%？）您有没有一些方法来检查您的答案是否正确？您想要一个聚类，还是目标是从可能的聚类中进行抽样？ - templatetypedef

似乎是页面排名的变体（或加权页面排名）。在n->无穷大步骤之后，随机冲浪者停留在一个顶点的概率是（我想？）一个顶点在同一类中的概率。 - amit

听起来你想要的是类似于多路割的东西。 - David Eisenstat

第一次提问还不错，加1并欢迎您来到这里。但是要注意：您的任务没有明确定义，缺少重要信息。最好补充完整。 - Gangnus

@Gangnus 謝謝。我想盡可能保持問題簡潔。我還在閱讀您的回答，但同時我會根據要求添加更多細節。 - Eduardo Gonçalves

@templatetypedef 我们可以这样假设。这个图只是我找到的一个可以作为示例的图。重点是根据给定节点集合对每个其他顶点进行分类，我们知道它属于哪个簇。我已经编辑了问题，以包含更多关于此的细节。 - Eduardo Gonçalves

2个回答

1

让w_i成为一个向量，其中w_i[j]是节点j在迭代i中属于簇的概率。

我们定义w_i：

w_0[j] =  1       j is given node in the class
          0       otherwise
w_{i}[j] = P(j | w_{i-1})

其中：P(j | w_{i-1}) 是假设我们已知每个其他节点 k 在该聚类中的概率为 w_{i-1}[k] 的情况下，j 在该聚类中的概率。

我们可以计算上述概率：

P(j | w_{i-1}) = 1- (1- w_{i-1}[0]*c(0,j))*(1- w_{i-1}[1]*c(1,j))*...*(1- w_{i-1}[n-1]*c(n-1,j))

在这里：

w_{i-1} 是上一次迭代的输出。
c(x,y) 是边 (x,y) 的权重。
c(x,x) = 1。

重复直到收敛，在收敛后的向量中（假设为 w），j 成为簇的概率为 w[j]。

概率函数的解释：

为了使一个节点不在集合中，需要所有其他节点“决定”不分享它。
因此，这种情况发生的概率是：

(1- w_{i-1}[0]*c(0,j))*(1- w_{i-1}[1]*c(1,j))*...*(1- w_{i-1}[n-1]*c(n-1,j))
      ^                            ^                       ^
node 0 doesn't share      node 1 doesn't share     node n-1 doesn't share

为了进入该类，至少需要一个节点“共享”，因此发生这种情况的概率是互补事件，即我们推导出的P(j | w_{i-1})公式。请保留HTML标签。

- amit

进行迭代而不知道解决方案是否存在或稳定是毫无意义的。 - Gangnus

@amit 感谢您详细的回复。我仍在努力理解提出的解决方案。请告诉我是否有误；如果我们知道节点n在集群中：P(v_n|C_n)=1，则节点j在n集群中的概率为：P(v_{n+j}|C_n)=1*P(v_{n+1}∩C_n)*P(v_{n+2}∩C_ {n+1})*P(v_{n+3}∩C_{n+2})...；其中P(v_x∩C_y)是您所称的c(x, y)。这背后的原因是什么？ - Eduardo Gonçalves

@amit 为了澄清我的上一条评论，我的问题是你的分布函数是否暗示了我所说的内容。另外，如果我有N个节点，每个节点我都事先知道它们所属的集群，那么我将得到不同的值，具体取决于我从哪个特定节点开始迭代，你会如何解决这个问题？此外，我的假设是你从已经分类的节点开始迭代，对吗？ - Eduardo Gonçalves

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Gangnus · Accepted Answer

你应该从结果的定义开始。如何展示属于某个类别的概率？

在我看来，结果应该是一组类别和一个表格：行代表顶点，列代表类别，在单元格中将显示该顶点属于此类别的可能性。

只有当你已经有了一些起始的已知概率时，你的图形才能设置一些属于某个类别的概率，也就是说，那个表格已经部分填充。

在根据起始值和边缘权重填充表格时，我们肯定会遇到这样的情况：通过不同的方式进入单元格时，会得到不同的概率。还应该设置一个问题：我们可以更改表格中的起始值吗？或者它们是固定的？对于边缘权重，也是同样的问题。

现在任务已经部分定义，而且非常小。你甚至不知道类别的数量！

在你设置了所有这些规则和数字之后，一切都很琐碎 - 使用最小二乘高斯方法。至于迭代方式，要小心 - 你事先不知道解是否稳定或者是否存在。如果不是，迭代不会收敛，你为其编写的整个代码片段就毫无意义了。而通过高斯方法，你可以得到一组线性方程，并且标准算法被编写来解决所有情况。最后，你不仅拥有解决方案，还可以得到每个最终值的可能误差。