string - ¿Cómo funciona el clustering(especialmente el clustering de cadenas)?

cluster-analysis data-mining (3)

Hay un paquete llamado stringdist que permite la comparación de cadenas usando varios métodos diferentes . Copypasting desde esa página:

Distancia de Hamming: Número de posiciones con el mismo símbolo en ambas cadenas. Solo definido para cuerdas de igual longitud.
Distancia de Levenshtein: Número mínimo de inserciones, eliminaciones y reemplazos necesarios para transformar la cadena a en la cadena b.
(Completa) Distancia Damerau-Levenshtein: Como la distancia Levenshtein, pero se permite la transposición de símbolos adyacentes.
Alineación óptima de cuerdas / distancia Damerau-Levenshtein restringida: distancia Damerau-Levenshtein (completa), pero cada subcadena solo se puede editar una vez.
Distancia más larga de subcadena común: Número mínimo de símbolos que deben eliminarse en ambas cadenas hasta que las subcadenas resultantes sean idénticas.
Distancia q-gramo: suma de las diferencias absolutas entre los vectores N-gramo de ambas cadenas.
Distancia del coseno: 1 menos la similitud del coseno de ambos vectores N-gramo.
Distancia Jaccard: 1 minuto el cociente de N-gramos compartidos y todos los N-gramos observados.
Distancia de Jaro: La distancia de Jaro es una fórmula de 4 valores y, efectivamente, es un caso especial de la distancia de Jaro-Winkler con p = 0.
Distancia Jaro-Winkler: esta distancia es una fórmula de 5 parámetros determinados por las dos cadenas comparadas (A, B, m, t, l) y p elegidas entre [0, 0.25].

Eso te dará la distancia. Es posible que no necesite realizar un análisis de clúster, tal vez la ordenación por la distancia de la cadena sea suficiente. He creado un script para proporcionar la funcionalidad básica here ... siéntase libre de mejorarlo según sea necesario.

Escuché sobre el agrupamiento para agrupar datos similares. Quiero saber cómo funciona en el caso específico de String.

Tengo una tabla con más de 100.000 palabras diferentes.

Quiero identificar la misma palabra con algunas diferencias (por ejemplo: house, house!!, hooouse, HoUse, @house, "house", etc... ).

¿Qué se necesita para identificar la similitud y agrupar cada palabra en un grupo? ¿Qué algoritmo es más recomendable para esto?

Para entender qué agrupamiento es imaginar un mapa geográfico. Puedes ver muchos objetos distintos (como casas). Algunos de ellos están cerca uno del otro, y otros están lejos. En función de esto, puede dividir todos los objetos en grupos (como ciudades). Los algoritmos de agrupación hacen exactamente esto: le permiten dividir sus datos en grupos sin especificar previamente los bordes de los grupos.

Todos los algoritmos de agrupamiento se basan en la distancia (o probabilidad) entre 2 objetos. En el mapa geográfico, es la distancia normal entre 2 casas, en el espacio multidimensional puede ser la distancia euclidiana (de hecho, la distancia entre 2 casas en el mapa también es la distancia euclidiana). Para la comparación de cadenas tienes que usar algo diferente. 2 buenas opciones aquí son Hamming y Levenshtein distancia . En su caso particular, la distancia Levenshtein si es más preferible (la distancia Hamming solo funciona con las cuerdas del mismo tamaño).

Ahora puedes usar uno de los algoritmos de agrupamiento existentes. Hay un montón de ellos, pero no todos pueden satisfacer sus necesidades. Por ejemplo, k-means puro, que ya se mencionó aquí difícilmente le ayudará, ya que requiere un número inicial de grupos para encontrar, y con un gran diccionario de cadenas puede ser 100, 200, 500, 10000, simplemente no sabe el número . Así que otros algoritmos pueden ser más apropiados.

Uno de ellos es el algoritmo de maximización de expectativas . Su ventaja es que puede encontrar varios clusters automáticamente. Sin embargo, en la práctica a menudo se obtienen resultados menos precisos que otros algoritmos, por lo que es normal utilizar k-means encima de EM , es decir, primero encontrar el número de agrupaciones y sus centros con EM y luego usar k-means para ajustar resultado.

Otra posible rama de algoritmos, que puede ser adecuada para su tarea, es la agrupación jerárquica . El resultado del análisis de conglomerados en este caso no es un conjunto de grupos independientes, sino más bien un árbol (jerarquía), donde varios conglomerados más pequeños se agrupan en uno más grande, y todos los conglomerados son finalmente parte de un conglomerado grande. En su caso, significa que todas las palabras son similares entre sí hasta cierto punto.

Puede usar un algoritmo como la distancia Levenshtein para el cálculo de la distancia y k-means para agrupar.

La distancia Levenshtein es una métrica de cadena para medir la cantidad de diferencia entre dos secuencias

Haga algunas pruebas y encuentre un umbral de similitud por palabra que decidirá sus grupos.