¿Cómo funciona el clustering (especialmente el clustering de cadenas)?
He oído hablar de clustering 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 (ej.: house, house!!, hooouse, HoUse, @house, "house", etc...).
¿Qué se necesita para identificar la similitud y agrupar cada palabra en un clúster? ¿Qué algoritmo se recomienda más para esto?
3 answers
Para entender lo que es clustering imagine un mapa geográfico. Puedes ver muchos objetos distintos (como casas). Algunos de ellos están cerca unos de otros, y otros están lejos. En base a esto, puede dividir todos los objetos en grupos (como ciudades). Los algoritmos de clustering hacen exactamente esto: le permiten dividir sus datos en grupos sin especificar previamente los bordes de los grupos.
Todos los algoritmos de clustering se basan en la distancia (o verosimilitud) entre 2 objetos. En 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 distance . En su caso particular Levenshtein distance if more preferable (Hamming distance funciona solo con las cadenas del mismo tamaño).
Ahora puedes usar uno de algoritmos de clustering existentes. Hay un montón de ellos, pero no todos pueden satisfacer sus necesidades. Por ejemplo, pure k-means, ya mencionado aquí difícilmente te 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 sabes el número. Así que otros algoritmos pueden ser más apropiados.
Uno de ellos es maximización de expectativas algoritmo. Su ventaja es que puede encontrar el número de clústeres automática. Sin embargo, en la práctica a menudo da resultados menos precisos que otros algoritmos, por lo que es normal usar k-means encima de EM, es decir, primero encuentre el número de clústeres y sus centros con EM y luego use k-means para ajustar el resultado.
Otra rama posible de algoritmos, que puede ser adecuada para su tarea, es agrupación jerárquica. El resultado del análisis de clústeres en este caso no es un conjunto de grupos independientes, sino más bien un árbol (jerarquía), donde varios clústeres más pequeños se agrupan en uno más grande, y todos los clústeres son finalmente parte de un gran cluster. En su caso, significa que todas las palabras son similares entre sí hasta cierto punto.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-11-19 21:14:11
Hay un paquete llamado stringdist que permite la comparación de cadenas usando varios métodos diferentes. Copypasting de esa página:
- Hamming distance: Número de posiciones con el mismo símbolo en ambas cadenas. Solo se define para cadenas 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.
- (Completo) Damerau-Levenshtein distancia: Como Levenshtein distancia, pero se permite la transposición de símbolos adyacentes.
- Alineación óptima de cadenas / distancia Damerau-Levenshtein restringida: Igual que la distancia (completa) de Damerau-Levenshtein, pero cada subcadena solo se puede editar una vez.
- Mayor distancia de subcadenas comunes: Número mínimo de símbolos que deben eliminarse en ambas cadenas hasta que las subcadenas resultantes sean idénticas.
- distancia q-gram: Suma de las diferencias absolutas entre vectores N-gram de ambas cadenas.
- Distancia del coseno: 1 menos la similitud coseno de ambos vectores N-gram.
- Distancia Jaccard: 1 minuta el cociente de los N-gramos compartidos y todos los N-gramos observados.
- Distancia Jaro: La distancia Jaro es una fórmula de 4 valores y efectivamente un caso especial de la distancia 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 de [0, 0.25].
Eso te dará la distancia. Usted es posible que no necesite realizar un análisis de clúster, tal vez ordenar por la distancia de la cadena en sí es suficiente. He creado un script para proporcionar la funcionalidad básica aquí... siéntase libre de mejorarlo según sea necesario.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-11-30 15:48:50
Puede utilizar un algoritmo como la distancia Levenshtein para el cálculo de la distancia y k-means para agruparse.
La distancia de 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.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-11-19 19:21:18