Pratiques et algorithmes DBSCAN

DBSCAN est une technique de clustering «basée sur la densité».

Le papier pour lequel DBSCAN a été proposé

Martin Ester，Hans-Peter Kriegel，Jorg Sander，Xiaowei Xu. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. Proccrdings of 2ndInternational Conference on Knowledge Discovery and Data Mining (KDD-96),1996.

Ainsi, l'algorithme de cet article est également proposé dans scikit-learn.

L'algorithme DBSCAN est décrit dans le Wiki comme suit.

DBSCAN requires two parameters: ε (eps) and the minimum number of points required to form a dense regiona. It starts with an arbitrary starting point that has not been visited. This point's ε-neighborhood is retrieved, and if it contains sufficiently many points........ (http://en.wikipedia.org/wiki/DBSCAN)

J'essaierai d'interpréter cela à ma manière.

La zone est jugée comme un groupe en fonction du nombre de points dans le rayon ε. De plus, tant que la densité du quartier dépasse un certain seuil, la grappe peut continuer à croître, de sorte que tout le voisinage du quartier peut être considéré comme une région.

Cela ressemble à ceci sur la figure.

Si vous regardez cette vidéo, vous pouvez bien comprendre DBSCAN (je pense). http://www.youtube.com/watch?v=5E097ZLE9Sg

mérite (1) Contrairement à Mean-shift, vous n'avez pas à définir le nombre de clusters. (2) Puisque le cluster est calculé récursivement, il est robuste contre les valeurs aberrantes. Démérite (1) Coût de calcul élevé et difficile à mettre en œuvre dans les applications temps réel

Enfin, le code source est décrit. Déterminez la plage à rechercher par eps (combien de points il y a à partir d'un certain point X), et combien de points existent dans eps avec min_samples pour le considérer comme un cluster.

    def (eps,min_samples):
        db = DBSCAN(eps, min_samples).fit(point_data)
        core_samples_mask = np.zeros_like(db.labels_, dtype=bool)
        core_samples_mask[db.core_sample_indices_] = True
        labels = db.labels_
        n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)

        print('Estimated number of clusters: %d' % n_clusters_)