DBSCAN返回部分集群

我想实现的代码DBSCAN这里：http://en.wikipedia.org/wiki/DBSCAN DBSCAN返回部分集群

我感到困惑的部分是

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

我的代码如下。因为它现在返回的是部分集群，即使它不在最近的eps附近，点应该被密度连接。我的代码只返回每个点的前几个邻居。

import numpy 
import time 
from math import radians, cos, sin, asin, sqrt 
import re, math 


def haversine(lon1, lat1, lon2, lat2): 
    """ 
    Calculate the great circle distance between two points 
    on the earth (specified in decimal degrees) returned as kilometers 
    """ 
    # convert decimal degrees to radians 
    lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2]) 
    # haversine formula 
    dlon = lon2 - lon1 
    dlat = lat2 - lat1 
    a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2 
    c = 2 * asin(sqrt(a)) 
    km = 6367 * c 
    return km 



def ST_DBSCAN(points,max_distance,MinPts): 
    global visited 
    visited = [] 
    noise = [] 
    cluster_id = 0 
    clusters = [] 
    in_cluster = [] 
    for p in points: 
     if p not in visited: 
      # neighbor_points = [] 
      visited.append(p) 
      NeighborPts = regionQuery(p,points,max_distance) 
      if len(NeighborPts) < MinPts: 
       noise.append(p) 
      else: 
       cluster_id = cluster_id + 1 
       g = expandCluster(p,NeighborPts,max_distance,MinPts,in_cluster) 
       clusters.append(g) 
    return clusters 

#return len(NeighborPts) 

def expandCluster(p,NeighborPts,max_distance,MinPts,in_cluster): 
    in_cluster.append(p[0]) 
    cluster = [] 
    cluster.append(p[0]) 
    for point in NeighborPts: 
     if point not in visited: 
      visited.append(point) 
      new_neighbors = regionQuery(point,points,max_distance) 
      if len(new_neighbors) >= MinPts: 
       new_neighbors.append(NeighborPts) 
      if point[0] not in in_cluster: 
       in_cluster.append(point[0]) 
       cluster.append(point[0])    
    return cluster 




def regionQuery(p,points,max_distance): 
    neighbor_points = [] 
    for j in points: 
     if j != p: 
      # print 'P is %s and j is %s' % (p[0],j[0]) 
      dist = haversine(p[1],p[2],j[1],j[2]) 
      if dist <= max_distance: 
       neighbor_points.append(j) 
    neighbor_points.append(p) 
    return neighbor_points

我在下面有一个子集。点1和点5应该是开10.76公里因此它们不应该在初始查询但它们应包括在相同的簇中，因为点5密度经由点连接3.

pointList = [[1,36.4686,2.8289], 
[2,36.4706,2.8589], 
[3,36.4726,2.8889], 
[4,36.4746,2.9189], 
[5,36.4766,2.9489], 
[6,36.4786,2.9789], 
[7,36.4806,3.0089], 
[8,36.4826,3.0389], 
[9,36.4846,3.0689], 
[10,36.4866,3.0989]] 

points= pointList 

g = ST_DBSCAN(points,10,3)

来源

2015-06-01 mech

这不回答你的问题，但如果你想要的是一个工作DBSCAN实现，scikit学习有着相当不错的一个 – oxymor0n

@ oxymor0n感谢您的评论。我试图实现我自己的功能，以提高我对它的工作方式的理解，并在距离调用中给予一定的灵活性（最终，我想添加更多维度）。 – mech

我认为scikit版本不是很好*如果你想修改距离函数。它对于欧几里得距离来说太优化了。 –

你expandCluster功能忘记新邻居。

你集更新被交换。

来源

2015-06-04 09:03:11

谢谢，我能够通过切换由pop（）方法关闭在new_neighbors每个点的集更新，并将其追加到NeighborPts修复错误。 – mech

DBSCAN返回部分集群

回答

相关问题