Python: agrupación de cadenas con el dbscan de scikit-learn, utilizando la distancia de Levenshtein como métrica:

He estado tratando de agrupar múltiples conjuntos de datos de URL (alrededor de 1 millón cada uno), para encontrar el original y los errores tipográficos de cada URL. Decidí usar la distancia de levenshtein como una métrica de similitud, junto con dbscan, ya que el algoritmo de agrupación como k-means no funcionará porque no conozco la cantidad de agrupaciones.

Estoy enfrentando algunos problemas al usar la implementación de dikscan de Scikit-learn.

Este fragmento de código a continuación funciona en pequeños conjuntos de datos en el formato I y en el uso, pero dado que se trata de un cálculo previo de toda la matriz de distancia, eso requiere espacio y tiempo O (n ^ 2) y es demasiado para mis grandes conjuntos de datos. He ejecutado esto durante muchas horas, pero solo termina tomando toda la memoria de mi PC.

lev_similarity = -1*np.array([[distance.levenshtein(w1[0],w2[0]) for w1 in words] for w2 in words]) dbscan = sklearn.cluster.DBSCAN(eps = 7, min_samples = 1) dbscan.fit(lev_similarity) 

Así que pensé que necesitaba alguna forma de calcular la similitud sobre la marcha y, por tanto, probé este método.

 dbscan = sklearn.cluster.DBSCAN(eps = 7, min_samples = 1, metric = distance.levenshtein) dbscan.fit(words) 

Pero este método termina dándome un error:

 ValueError: could not convert string to float: URL 

Me doy cuenta de que significa que está intentando convertir las entradas a la función de similitud en flotadores. Pero no quiero que haga eso. Según tengo entendido, solo necesita una función que pueda tomar dos argumentos y devolver un valor flotante que luego pueda comparar con eps, lo que debería hacer con la distancia de levenshtein.

Estoy atascado en este punto, ya que no conozco los detalles de implementación de dbscan de sklearn para descubrir por qué está intentando convertirlo en flotante, y tampoco tengo una mejor idea sobre cómo evitar la matriz O (n ^ 2) cálculo.

Por favor, avíseme si hay alguna forma mejor o más rápida de agrupar estas cadenas que quizás haya pasado por alto.

Desde las preguntas frecuentes de scikit-learn, puede hacer esto haciendo una métrica personalizada :

 from leven import levenshtein import numpy as np from sklearn.cluster import dbscan data = ["ACCTCCTAGAAG", "ACCTACTAGAAGTT", "GAATATTAGGCCGA"] def lev_metric(x, y): i, j = int(x[0]), int(y[0]) # extract indices return levenshtein(data[i], data[j]) X = np.arange(len(data)).reshape(-1, 1) dbscan(X, metric=lev_metric, eps=5, min_samples=2) 

Prueba ELKI en lugar de sklearn.

Es la única herramienta que conozco que permite el índice DBSCAN acelerado con cualquier métrica.

Incluye la distancia de Levenshtein. -db.index agregar un índice a su base de datos con -db.index . Siempre uso el índice del árbol de la cubierta (¡por supuesto que debes elegir la misma distancia para el índice y para el algoritmo!)

Podría usar distancias “pyfunc” y árboles de bolas en sklearn, pero el rendimiento fue realmente malo debido al intérprete. Además, DBSCAN en sklearn requiere mucha más memoria.