Análisis cluster basado en campos alfanuméricos

Buenas, estoy empezando en este mundo del data mining y tengo una duda sobre si es posible hacer algo que estamos queriendo hacer.

El problema es el siguiente: tenemos un archivo (10 millones de registros aproximadamente) con nombre, apellido, domicilio, etc. Sabemos que hay un número importante de registros repetidos ( que corresponden a la misma persona ) pero escritos diferente, con faltas de ortografía, variaciones en el formato del domicilio, etc.

Para detectarlos, lo que habíamos pensado era ejecutar algún tipo de análisis cluster para lograr agrupar los nombres similares, y obtener un número razonable de registros que "a priori serían el mismo" para revisarlos manualmente.

 

Por ejemplo, quisieramos que los siguientes 2 registros se agrupen en un mismo cluster:

"Santiago Hernandez; Avenida Olleros 1234;"

"Santiago Hernandes; Avda Olleros 1234;"

 

El problema es que todas las herramientas que estuve probando hasta ahora (Knime, Rapidminer ), quizás por desconocimiento mío, solo me permiten hacer análisis cluster basado en campos numéricos, calculando la distancia, o categóricos. No sé si es posible aplicar este tipo de metodología a campos de tipo string.  La única que me sirvió para hacer algo similar es Open Refine, pero es online y no me permite manipualr volúmenes tan grandes de información.

 

La pregunta en concreto es, es posible aplicar este método a campos tipo string ? Como se hace ? Alguien conoce alguna herramienta, o sugerencia de por donde podría orientarme ?

 

Desde ya muchas gracias,

Saludos

 

Hola,

Si se puede hacer cluster con campos de tipo string. Una solución es transformarlos a variables dummy (1/0), ejemplo: estado_civil: soltero, casado, divorciado pasaría a estado_soltero: 1/0 , estado_asado: 1/0, estado_divorciado: 1/0. Una vez que es 1/0 se trata como numérico.

Hay también algoritmos de cluster que  trabajan con distancias que se pueden aplicar a strings y están suelen basarse en grado de similitud.

El caso que planteas debería basarse en una distancia que se base en diferencias entre cadenas. Hay varios algoritmos que obtienen diferencias entre cadenas, lo que no se es si pueden aplicarse en un algoritmo de cluster tipo k-means.

En SAS el procedure kclus puede utilizar algoritmos de cluster cuya distancia trabaja con strings, pero no sé si es la que buscas. Creo que también hay algo en R.

Una posibilidad es tomar una cadena de referencia y comparar todas las cadenas contra esta utilizando un algoritmo que compare diferencias entre cadenas (los hay fonéticos, de posiciones...) el valor obtenido que será numérico y lo añades como campo al dataset, luego basas el clustering en este campo.

Espero haberte ayudado algo

Saludos,

En respuesta a por Juan_Vidal

Yo he trabajado en detección de duplicados de este tipo con aproximaciones más clásicas, directamente con SQL o procedimientos almacenados, pero me interesa mucho ver si se puede resolver por clustering, y comprobar qué método puede devolver mejores resultados y en menos tiempo, algo muy importante en un proceso que hagas lo que hagas va a consumir muchísimo tiempo de procesamiento.

Creo que, tal como apunta Juan, todo pasa por utilizar k-means u otro algoritmo de comparación de distancias entre cadenas para poder tener un valor numérico que pueda utilizar el clustering.

Quiero apuntar además, que para obtener buenos resultados hay que tener en cuenta el peso que cada campo o variable va a tener dentro de la comparación del registro completo, es decir, que no puedes dar el mismo valor a la hora de identificar un duplicado a una coincidencia entre dos valores de 'estado_soltero' que a una coincidencia entre 'DNI', o 'email', cada variable ha de tener un peso en función de lo identificadora que sea por sí misma dentro del registro completo.

Ya sé que esto es complicarlo más aún, pero si no se tiene en cuenta dudo que el clustering pueda llegar a dar buenos resultados.