DBSCAN 的距离函数

Question

我想使用聚类算法为一个大有向图找到一个聚类，我也想从这个图中去除噪音。所以，我想使用 DBSCAN 方法，因为我看到我们可以给算法一个距离函数来确定 distance/similarity 在两个不同的节点之间。

我的问题是，我如何定义一个距离函数，它增加两个节点之间的相似性在跳数方面接近并且减少当一个节点被隔离时。

我没有坐标或节点属性，所以我不能使用它们。我只有图的拓扑结构。

预期的输出将是这样的：

我真的很担心解决方案的复杂性。如何近似具有线性复杂度的聚类...

Answer 1

明显有什么问题？

Distance(a,b) = 最短路径的长度，如果有 none.

则为无穷大

您可能应该考虑方向，所以 a0 到 a3 是 1。

Answer 2

@Anony-Mousse 建议的距离度量很好和自然的一个，但我质疑 dbscan 的使用。使用提议

distance = length of shortest path, or infinity if there is none

直接链接的任何两个节点的距离为 1。如果您使用 dbscan 且 epsilon < 1，则所有点都是噪声点。所以你会想要 epsilon > 1。从你的例子来看，它看起来就像在距离 1 处甚至有一个点，你想让它们进入相同的组件所以看起来你想要 minNumPts = 2。这会给结果是两点通过任意长度的路径连接他们将在同一个集群中。在我看来像什么你追求的与密度和聚类无关，相反，我认为你想要的是连接的组件。如果两个节点由任意长度的路径连接，则它们是在同一个组件中。通过 dbscan 或其他一些集群查找方法可能是可行的，但这可能是错误的思考方式。你有一张图和一张图理论问题。您可能应该使用图中的方法理论。

我将使用 R 和 igraph 进行说明。还有其他工具如果你不关心这些。

大部分工作只是设置您的问题。

library(igraph)

to   = c("a1", "a2", "a3", "a0", "b1", "b2", "b3", "b0")
from = c("a0", "a1", "a2", "a3", "b0", "b1", "b2", "b3")
EL   =  data.frame(from, to)

Vert = c("a0", "a1", "a2", "a3", "b0", "b1", "b2", "b3", "c0", "d0")
Vdf  = data.frame(Vert)

g = graph_from_data_frame(d = EL, vertices=Vdf)
LO = matrix(c(1.2,1,1,1.2, 2.2,2,2,2.2, 0, 3, 4,3,2,1,4,3,2,1,4,4), 
    ncol=2)
plot(g, layout=LO)

现在我们可以使用一条线来获得我们需要的一切关于组件。

Comp = components(g, mode="weak")
Comp
$membership
a0 a1 a2 a3 b0 b1 b2 b3 c0 d0 
 1  1  1  1  2  2  2  2  3  4 
$csize
[1] 4 4 1 1
$no
[1] 4

这告诉我们节点的组件成员资格，每个组件的节点数和组件。因为你想调用单个节点组件 "noise" 在 dbscan 的风格，你可以看到组件 3 和 4 各有一个节点。
他们是噪音。其他的是 "real" 个组件。展示如何使用它并以一个结束漂亮的图片，我将绘制图表着色组件并为 "noise".

使用浅灰色

ColorMap = rainbow(Comp$no)
ColorMap[Comp$csize == 1] = "lightgray"
plot(g, layout=LO, vertex.color=ColorMap[Comp$membership])

我鼓励您将图形问题视为图形。

DBSCAN 的距离函数

Distance function for DBSCAN

cluster-analysis

machine-learning

unsupervised-learning