Bonjour. DBSCAN Qu'est-ce qu'un algorithme [^ 1], un type de clustering de données, proche-recherche (exemple / c0fadee57b03f9f08d22)) et la méthode [structure de données de l'ensemble élémentaire](https://ja.wikipedia.org/wiki/elemental structure de données de l'ensemble).
J'ai lu moi-même la source [^ 2] de scicit-learn et j'ai écrit l'algorithme DBSCAN (deux types, type profondeur d'abord et type largeur d'abord) presque en copiant.
Juste au cas où, j'ai vérifié s'il correspond au résultat par scicit-learn.
$ ./dbscan.py
True : depth-first
True : breadth-first
dbscan.py
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import print_function
import numpy as np
import sklearn.cluster
from scipy import spatial
def dbscandepth(neigh, minp):
ilabel = 0
labels = [-1 for _ in neigh] # initialized as noise
for i in range(len(neigh)):
if labels[i] >= 0 or len(neigh[i]) < minp: # visited or noise
continue
candid = [i]
while len(candid) > 0:
i = candid.pop()
if len(neigh[i]) >= minp: # core only
for j in neigh[i]:
if labels[j] < 0:
candid.append(j)
labels[j] = ilabel
ilabel += 1
return labels
def dbscanbreadth(neigh, minp):
def expandcandid(candid):
candid = filter(lambda j: len(neigh[j]) >= minp, candid) # core only
if candid != []:
candid = [neigh[j] for j in candid]
candid = list(set.union(*map(set, candid)))
candid = filter(lambda j: labels[j] < 0, candid)
return candid
ilabel = 0
labels = [-1 for _ in neigh] # initialized as noise
for i, candid in enumerate(neigh):
if labels[i] >= 0 or len(candid) < minp: # visited or noise
continue
while len(candid) > 0:
candid = expandcandid(candid)
for j in candid:
labels[j] = ilabel
ilabel += 1
return labels
def main():
minp = 4
radius = 0.1
points = np.random.uniform(size=(100,2))
labels_sklearn = list(sklearn.cluster.DBSCAN(radius, minp).fit(points).labels_ # scikit-learn
tree = spatial.cKDTree(points)
neigh = [tree.query_ball_point(p, radius) for p in points] #Recherche de quartier
labels = dbscandepth(neigh, minp)
print(labels == labels_sklearn, ": depth first")
labels = dbscanbreadth(neigh, minp)
print(labels == labels_sklearn, ": breadth first")
return 0
if __name__ == '__main__':
main()
[^ 1]: Il y a aussi un article ici: "DBSCAN Blues" [^ 2]: Les sources sont _dbscan_inner.pyx et [dbscan_.py](https :: //github.com/scikit-learn/scikit-learn/blob/21e63aaf01404f4eb3e7ae54ef9f71e8bb905f6b/sklearn/cluster/dbscan_.py)