[PYTHON] Algorithme DBSCAN (clustering de données)

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)