问题标签 [dbscan]

我正在尝试根据视觉接近度对网页内容进行聚类。您可以在http://i.stack.imgur.com/qzGKE.png下方的链接上看到块的可视化显示

我尝试使用带有以下功能的 DBSCAN 聚类与 sckikit-learn 并没有太大成功： - 块的左 X 坐标（因为内容经常左对齐） - 块的右 X 坐标（因为内容经常右对齐） - 顶部 Y块的坐标（进一步关闭块）

你对更好的功能有什么想法吗

我有 100,000 个点要使用 ELKI 中的 OPTICS 算法进行聚类。对于这个点集，我有一个大约 50 亿个条目的上三角距离矩阵。在 ELKI 想要的矩阵格式中，大约需要 100GB 的内存。我想知道 ELKI 是否处理这种数据负载？任何人都可以确认您以前是否做过这项工作？

I've been looking around scipy and sklearn for clustering algorithms for a particular problem I have. I need some way of characterizing a population of N particles into k groups, where k is not necessarily know, and in addition to this, no a priori linking lengths are known (similar to this question).

I've tried kmeans, which works well if you know how many clusters you want. I've tried dbscan, which does poorly unless you tell it a characteristic length scale on which to stop looking (or start looking) for clusters. The problem is, I have potentially thousands of these clusters of particles, and I cannot spend the time to tell kmeans/dbscan algorithms what they should go off of.

Here is an example of what dbscan find:

You can see that there really are two separate populations here, though adjusting the epsilon factor (the max. distance between neighboring clusters parameter), I simply cannot get it to see those two populations of particles.

Is there any other algorithms which would work here? I'm looking for minimal information upfront - in other words, I'd like the algorithm to be able to make "smart" decisions about what could constitute a separate cluster.

我需要一个类似于 的命令length()来查找在 dbscan 中创建的集群的数量。

假设我对这个数据集执行了 dbscan

我可以使用命令 ds 来查看集群的数量

是否有我可以键入的命令并返回集群数量的值？即我输入一个命令，返回值 12。

其实我不知道 map() 的 key 和 value 应该是什么，输入格式和输出格式应该是什么。如果我通过 map() 一次读取一个点，那么如何使用一个点计算邻居，因为尚未读取剩余点。

我遇到的问题是矩形中有矩形。想想一张地图，除了以下特征，关键点是：具有相似密度的矩形通常与其他矩形共享相似的尺寸和在 x 轴上的相似位置，但有时这些矩形之间的距离可能很大但通常很小。如果 x 轴上的位置或尺寸明显偏离，它们就不会相似。

• 矩形不相交，较小的矩形完全位于较大的矩形内。

• 矩形通常具有相似的 x 位置和相似的尺寸（相似的高度和宽度），并且内部具有较小的矩形。矩形本身将被视为它自己的集群。

• 有时这些集群与另一个集群的距离可能相当大（想想岛屿）。通常这些簇共享相同或相似的维度以及相同或相似的子矩形密度。如果是这样，尽管两个集群之间存在距离，但它们应被视为同一集群的一部分。

• 矩形越密集（内部的矩形越小），附近有相似或相同的密集矩形共享相同或相似维度的可能性就越大。

我附上了一张图表来更清楚地描述这种情况：

• 红色边框表示这些组是异常值，不属于任何集群并被忽略。

• 蓝色边框有很多簇（黑色边框包含黑色实心矩形）。由于上述标准（相似的宽度、相似的 X 位置、相似的密度），它们形成了一组相似的集群。由于标准（相似的宽度、相似的 X 位置、相似的密度），即使是右下角的集群仍然被认为是该组的一部分。

• 绿松石边框有很多簇（黑色边框包含黑色实心矩形）。然而，这些集群在维度、x 位置和密度上与蓝色边框中的集群不同。他们被认为是他们自己的一个群体。

到目前为止，我发现 DBSCAN 之类的密度聚类似乎很完美，因为它考虑了噪声（异常值），而且您不需要提前知道会有多少聚类。

但是，您需要定义形成集群所需的最小点数和阈值距离。如果您不知道这两个会发生什么，并且它可能会根据上述问题而有所不同？

另一个看似合理的解决方案是分层（凝聚）聚类（r-tree），但我担心我仍然需要知道树深度级别的截止点以确定它是否是一个集群。

I am working with GPS data (latitude, longitude). For density based clustering I have used DBSCAN in R.

Advantages of DBSCAN in my case:

1. I don't have to predefine numbers of clusters

2. I can calculate a distance matrix (using Haversine Distance Formula) and use that as input in dbscan

   /li>

Now, when I look at the clusters, they are not meaningful. Some clusters have points which are more than 1km apart. I want dense clusters but not that big in size.

Different values of MinPts and eps are taken care of and I have also used k nearest neighbor distance graph to get an optimum value of eps for MinPts=25

What dbscan is doing is going to every point in my dataset and if point p has MinPts in its eps neighborhood it will make a cluster but at the same time it is also joining the clusters which are density reachable (which I guess are creating a problem for me).

It really is a big question, particularly "how to reduce size of a cluster without affecting its information too much", but I will write it down as the following points:

1. How to remove border points in a cluster? I know which points are in which cluster using dens$cluster, but how would I know if a particular point is core or border?
2. Is cluster 0 always noise?
3. I was under the impression that the size of a cluster would be comparable to eps. But that's not the case because density reachable clusters are combined together.
4. Is there any other clustering method which has the advantage of dbscan but can give me more meaningful clusters?

OPTICS is another alternative but will it solve my issue?

Note: By meaningful I want to say closer points should be in a cluster. But points which are 1km or more apart should not be in the same cluster.

假设一个域有一个 url 列表，具有不同级别的路径深度和相似性

我可以使用什么算法根据 URL 字符串的密度（斜杠数量）和相似性（文本距离，Levenshtein）来聚类 URL 字符串？

所以输出将被分组：

一些特征： - url 字符串越密集（或更深），它就越相关，并且可能在序列中重复。- 类似的网址块一个接一个地重复。不同的 url 似乎离大量相似的 url 更远。

DBSCAN 在这里合适吗？

（密度，LV 距离）

我想擦除最后一个字符直到斜线，然后在后续字符串中搜索匹配项。如果匹配是列表中的下一个 url，它们很可能是一个块。如果在列表的下方找到匹配项，则它可能不是任何块的一部分。

这几乎随处可见，因此不是任何块的一部分。

找到 2 个后续匹配，在候选之后立即找到。

找到 3 个随后出现的匹配项。所以它们被分块在一起。

在底部找到另一个匹配项，由于距离，它们都不是任何块的一部分。这种方法是否有名称或类似的名称？

我想对 DBSCAN 算法进行某种改进，用户不需要输入输入参数（minPts 和 Eps）。我的想法是使用 K 距离图，但是计算该图的“拐点”的最佳方法是什么？当情节上有2个或更多膝盖时如何计算？

在哪里可以找到一些 DBSCAN 改进的源代码，例如 AUTODBSCAN、VDBSCAN、PDBSCAN 或 DBSCAN-DLP？我正在寻找一些基础知识，但在任何地方我都找不到很好的帮助。也许您在某处看到过示例源代码？

我在http://scikit-learn.org中发现 DBSCAN 算法的示例令人困惑。我有一个纬度和经度列表，并且很好奇如何在这里为 DBSCAN 算法准备输入。