Я пытаюсь реализовать код для DBSCAN здесь: http://en.wikipedia.org/wiki/DBSCANDBSCAN возвращает частичные кластеры
Часть Я смущен о том,
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)
это не отвечает на ваш вопрос, но если все, что вы хотите, это работающая реализация DBSCAN, scikit-learn имеет довольно хороший номер – oxymor0n
@ oxymor0n Спасибо за комментарий. Я пытаюсь реализовать свою собственную функцию, чтобы улучшить свое понимание того, как она работает, и дать некоторую гибкость в дистанционных вызовах (в конце концов, я хочу добавить больше измерений). – mech
Я думаю, что версия scikit не очень хорошая * если * вы хотите изменить функцию расстояния. Он слишком оптимизирован для евклидова расстояния. –