Agrupación de texto con distancias de Levenshtein

levenshtein distance java

Question

Tengo un conjunto (2k - 4k) de cadenas pequeñas (3-6 caracteres) y quiero agruparlos. Dado que uso cadenas, respuestas anteriores sobre ¿Cómo funciona la agrupación en clústeres (especialmente la agrupación de cadenas)? , me informó que la distancia de Levenshtein es buena para ser utilizada como una función de distancia para cuerdas. Además, dado que no sé de antemano la cantidad de clusters, la agrupación jerárquica es el camino a seguir y no k-means.

Aunque tengo el problema en su forma abstracta, no sé cuál es la forma más fácil de hacerlo realmente. Por ejemplo, es MATLAB o R una mejor opción para la implementación real del agrupamiento jerárquico con la función personalizada (distancia Levenshtein). Para ambos software, uno puede encontrar fácilmente una implementación de distancia Levenshtein. La parte de agrupamiento parece ser más difícil. Por ejemplo, el clúster de texto en MATLAB calcula la matriz de distancia para todas las cadenas, pero no puedo entender cómo usar la matriz de distancia para obtener realmente la agrupación. ¿Pueden alguno de ustedes, los gurús, mostrarme cómo se implementa la agrupación jerárquica en MATLAB o R con una función personalizada?

Answer 1

Esto puede ser un poco simplista, pero aquí hay un ejemplo de código que usa la agrupación jerárquica basada en la distancia de Levenshtein en R.

set.seed(1)
rstr <- function(n,k){   # vector of n random char(k) strings
  sapply(1:n,function(i){do.call(paste0,as.list(sample(letters,k,replace=T)))})
}

str<- c(paste0("aa",rstr(10,3)),paste0("bb",rstr(10,3)),paste0("cc",rstr(10,3)))
# Levenshtein Distance
d  <- adist(str)
rownames(d) <- str
hc <- hclust(as.dist(d))
plot(hc)
rect.hclust(hc,k=3)
df <- data.frame(str,cutree(hc,k=3))

En este ejemplo, creamos un conjunto de 30 cadenas de caracteres aleatorios (5) artificialmente en 3 grupos (comenzando con "aa", "bb" y "cc"). Calculamos la matriz de distancia de Levenshtein usando adist(...) y ejecutamos clustering hclust(...) usando hclust(...) . Luego cortamos el dendrograma en tres clusters con cutree(...) y anexamos los id del clúster a las cadenas originales.

Answer 2

Si bien la respuesta depende en cierto grado del significado de las cadenas, en general su problema se resuelve con la familia de técnicas de análisis de secuencias. Más específicamente, Optimal Matching Analysis (OMA).

La mayoría de las veces el OMA se lleva a cabo en tres pasos. Primero, defines tus secuencias. De su descripción puedo suponer que cada letra es un "estado" separado, el bloque de construcción en una secuencia. En segundo lugar, utilizará uno de los varios algoritmos para calcular las distancias entre todas las secuencias en su conjunto de datos, obteniendo así la matriz de distancia. Finalmente, alimentará esa matriz de distancia en un algoritmo de agrupamiento, como la agrupación jerárquica o Partitioning Around Medoids (PAM), que parece ganar popularidad debido a la información adicional sobre la calidad de los clusters. Este último lo guía en la elección del número de clústeres, uno de los varios pasos subjetivos en el análisis de secuencia.

En R el paquete más conveniente con un gran número de funciones es TraMineR , el sitio web se puede encontrar here . Su guía de usuario es muy accesible y los desarrolladores también están más o menos activos en SO.

Es probable que descubra que la agrupación no es la parte más difícil, excepto la decisión sobre la cantidad de clústeres. La guía de TraMineR muestra que la sintaxis es muy directa, y los resultados son fáciles de interpretar en función de los gráficos de la secuencia visual. Aquí hay un ejemplo de la guía del usuario:

clusterward1 <- agnes(dist.om1, diss = TRUE, method = "ward")

dist.om1 es la matriz de distancia obtenida por OMA, la pertenencia al clúster está contenida en el objeto clusterward1 , con lo que puede hacer lo que desee: trazado, recodificación como variables, etc. La opción diss=TRUE indica que el objeto de datos es la diferencia ( o distancia) matriz. Fácil, ¿eh? La elección más difícil (no sintáctica, sino metodológicamente) es elegir el algoritmo de distancia correcto, adecuado para su aplicación particular. Una vez que tienes eso, pudiendo justificar la elección, el resto es bastante fácil. ¡Buena suerte!

Answer 3

Si desea una explicación clara de cómo usar el agrupamiento de particiones (que seguramente será más rápido) para resolver su problema, consulte este documento: Métodos efectivos de revisión ortográfica utilizando algoritmos de agrupamiento. https://www.researchgate.net/publication/255965260_Effective_Spell_Checking_Methods_Using_Clustering_Algorithms?ev=prf_pub

Los autores explican cómo agrupar un diccionario utilizando una versión modificada (similar a PAM) de iK-Means.

¡La mejor de las suertes!

Answer 4

ELKI incluye la distancia Levenshtein, y ofrece una amplia variedad de algoritmos de clustering avanzados, por ejemplo, agrupamiento OPTICS .

El soporte de clustering de texto fue contribuido por Felix Stahlberg, como parte de su trabajo en:

Stahlberg, F., Schlippe, T., Vogel, S., y Schultz, T.
Segmentación de palabras a través de la alineación interlingüística de palabra a teléfono.
Taller de Tecnología del Lenguaje Hablado (SLT), 2012 IEEE. IEEE, 2012.

Por supuesto, apreciaríamos contribuciones adicionales.