2

在 DBSCAN 中，如果我们有 minPoints=3 并且我们想确定一个点是否是核心点，你是在 Eps 中计算点本身还是需要在它的 Eps 中有 3 个其他点？

4

2 回答 2

1

DBSCAN 是一种具有数据库上下文的算法。

为了获得良好的性能，您需要一个可以使用索引加速此类查询的数据库 - 这将运行时间O(n^2)从O(n log n).

如果您向数据库发送范围查询，它将返回该区域内的所有对象，包括查询点。您必须手动从结果中删除查询点。

而且从逻辑的角度来看：这是一个密度度量。为什么密度估计必须排除查询对象？它是数据集的一部分，它应该像任何其他对象一样有助于密度！

我看不出有什么理由应该从每个查询的数据集中删除查询点。

于 2014-05-12T11:31:30.360 回答
0

根据 Wikipedia 中提出的算法，一个点的区域查询P返回P's eps邻域内的所有点，包括P.

这是算法（来自维基百科）

DBSCAN(D, eps, MinPts)
   C = 0
   for each unvisited point P in dataset D
      mark P as visited
      NeighborPts = regionQuery(P, eps)
      if sizeof(NeighborPts) < MinPts
         mark P as NOISE
      else
         C = next cluster
         expandCluster(P, NeighborPts, C, eps, MinPts)

expandCluster(P, NeighborPts, C, eps, MinPts)
   add P to cluster C
   for each point P' in NeighborPts 
      if P' is not visited
         mark P' as visited
         NeighborPts' = regionQuery(P', eps)
         if sizeof(NeighborPts') >= MinPts
            NeighborPts = NeighborPts joined with NeighborPts'
      if P' is not yet member of any cluster
         add P' to cluster C

regionQuery(P, eps)
   return all points within P's eps-neighborhood (including P)

由于核心点被定义为一个比 具有更多点MinPts的点Eps，我会说在确定它是否是核心点时计算点本身。

于 2014-05-12T11:15:18.610 回答