Implémentation Python de L'algorithme optique (Clustering)
Je cherche une implémentation décente de l'algorithme OPTICS en Python. Je vais l'utiliser pour former des groupes de points basés sur la densité (paires(x,y)).
Je cherche quelque chose qui prend des paires (x,y) et génère une liste de clusters, où chaque cluster de la liste contient une liste de paires (x, y) appartenant à ce cluster.
6 réponses
EDIT: ce qui suit est connu pour Pas Être une implémentation complète de L'optique.
J'ai fait une recherche rapide et trouvé ce qui suit (optique ). Je ne peux pas garantir sa qualité, mais l'algorithme semble assez simple, donc vous devriez être en mesure de le valider/l'adapter rapidement.
Voici un exemple rapide de la façon de construire des clusters sur la sortie de l'algorithme optique:
def cluster(order, distance, points, threshold):
''' Given the output of the options algorithm,
compute the clusters:
@param order The order of the points
@param distance The relative distances of the points
@param points The actual points
@param threshold The threshold value to cluster on
@returns A list of cluster groups
'''
clusters = [[]]
points = sorted(zip(order, distance, points))
splits = ((v > threshold, p) for i,v,p in points)
for iscluster, point in splits:
if iscluster: clusters[-1].append(point)
elif len(clusters[-1]) > 0: clusters.append([])
return clusters
rd, cd, order = optics(points, 4)
print cluster(order, rd, points, 38.0)
Je ne suis pas au courant d'une implémentation complète et exacte de L'optique Python. Les liens postés ici ne semblent que des approximations approximatives de l'idée D'optique. Ils n'utilisent pas non plus d'index pour l'accélération, ils fonctionneront donc dans O(n^2) ou plus probablement même O(n^3).
L'optique a un certain nombre de choses délicates en plus de l'idée évidente. En particulier, le seuillage est proposé avec des seuils relatifs ("xi") au lieu des seuils absolus affichés ici (à quel point le résultat sera approximativement celui de DBSCAN!).
Le document D'optique original contient une approche suggérée pour convertir la sortie de l'algorithme en clusters réels:
Http://www.dbs.informatik.uni-muenchen.de/Publikationen/Papers/OPTICS.pdf
L'implémentation optique dans Weka est essentiellement non maintenue et tout aussi incomplète. Il ne produit pas réellement de clusters, il ne calcule que l'ordre du cluster. Pour cela, il crée une copie de la base de données - ce n'est pas vraiment du code Weka.
Il semble y avoir une implémentation assez étendue disponible dans ELKI en Java par le groupe qui a publié OPTICS en premier lieu. Vous voudrez peut-être tester toute autre implémentation par rapport à cette version "officielle".
Bien qu'il ne soit pas techniquement optique, il existe une implémentation HDBSCAN * pour python disponible à https://github.com/lmcinnes/hdbscan . Ceci est équivalent à L'optique avec un epsilon maximal infini, et une méthode d'extraction de cluster différente. Puisque l'implémentation donne accès à la hiérarchie de cluster générée, vous pouvez en extraire des clusters via des méthodes optiques plus traditionnelles si vous préférez.
Notez que bien que ne limitant pas le paramètre epsilon cette l'implémentation atteint toujours les performances O(N log (n)) en utilisant des algorithmes d'arborescence minimale basés sur KD-tree et ball-tree, et peut gérer des ensembles de données assez volumineux.
Il existe maintenant la bibliothèque pycustering qui contient, entre autres, un python et une implémentation C++ de L'optique.
Voir "approches de clustering basées sur la densité" sur http://www.chemometria.us.edu.pl/index.php?goto=downloads
Vous voulez regarder une courbe de remplissage d'espace ou un index spatial. Un sfc réduit la complexité 2d à une complexité 1d. Vous voulez regarder Hilbert courbe de Nick quadtree spatial index blog. Vous voulez télécharger mon implémentation d'un sfc à phpclasses.org (courbe de hilbert).