Si bien se logró un algoritmo junto al Subcomité Técnico de Identificación de Personas (STID) de SUEIIDISS (HL7 Uruguay), del que participé en el 2009, yo me concentré en otro problema, el de la calidad de los datos. Si bien podemos pensar en cómo resolver las búsquedas de la mejor forma, si la calidad de los datos en nuestra base de datos es pobre, el resultado de la búsqueda será de poca utilidad, y si se llevara la calidad a niveles óptimos, cualquier mecanismo simple de búsqueda nos ayudaría a encontrar lo que necesitamos, por eso el cambio de enfoque. Dicho sea de paso, aquí se puede obtener una copia del documento logrado en el STID.
El resultado de mi investigación fue un algoritmo que sirve para comparar dos identidades, formadas por los atributos: nombres, apellidos, fecha de nacimiento y sexo de una persona. Cualquier tipo de identificador de la persona no forma parte de su identidad, por eso no se consideran números de documentos nacionales ni otros tipos de identificadores en las identidades. El resultado del algoritmo es un número entre 0 y 1 donde 0 indica coincidencia nula y 1 coincidencia total. Un resultado de 0.85 indica que las identidades coinciden en un 85%.
Este algoritmo fue probado en bases de datos con miles de registros, y los resultados obtenidos son óptimos. Según estos experimentos, las identidades cuya coincidencia supera el 95% corresponden a la misma persona, y la diferencia se debe a que hay errores en los datos, por ejemplo un nombre mal escrito, que en base a mis experimentos, es uno de los casos más frecuentes en los de fuentes de error, por ejemplo una letra faltante o la transposición de letras son de los errores más comunes.
Detrás del algoritmo hay tres ideas muy intuitivas:
- Distintos datos de la identidad de una persona pesan distinto en la identificación de la misma. Nuestra identidad es lo que nos diferencia de las demás personas, pero distintas partes de esta identidad puede diferenciarnos en mayor o menor medida. No es lo mismo diferenciarse por los nombres que por la fecha de nacimiento, seguramente hayan muchas más personas que nacieron el mismo día que uno, que personas que se llaman igual. Entonces cada atributo de la identidad tiene un peso asociado.
- No solo pasa que cada atributo pesa distinto en la identificación de la persona, si no que este peso en realidad debería variar dependiendo del valor de los atributos. Por ejemplo, si un apellido es muy común, el peso debería ser menor, y si es un apellido poco usual, su peso debería ser mayor. El algoritmo que considera esta afirmación se llamará "Algoritmo de Verificación de Identidades Avanzado" o "AVI-a", y no será descrito en este artículo.
- El algoritmo debe comportarse bien ante casos de errores en los datos, es decir que si se comparan dos identidades, y una tiene errores en los datos, el algoritmo debería igualmente detectar la similitud entre las identidades. Es por esto que condiciones de igualdad o igualdad parcial no son útiles para el cálculo del índice de coincidencia porque consideran a los datos como un todo o lo divide en grandes partes, es necesario llegar a un nivel de comparación con granularidad suficiente para que los errores no afecten tanto a las comparaciones.
Descripción del Algoritmo de Verificación de Identidades Básico (AVI-b):
Aquí voy a bajar a un nivel muy técnico, igualmente voy a ir explicando los detalles para que nadie pierda el hilo.
La identidad mínima de una persona, como mencioné antes, está formada por los atributos: nombres, apellidos, sexo y fecha de nacimiento. Vamos a tomar dos identidades id1 e id2 para compararlas según el AVI-b.
// Tipo que define la Identidad
Identidad {
String nom1
String nom2
String ap1
String ap2
CodigoSexo sexo
Fecha fecha_nac
}
const String MASCULINO = "M"
const String FEMENINO = "F"
const String IDENFINIDO = "UN"
// Debe ser alguna de las constantes definidas previamente
String codigo
}
// Tipo que define la el código para el sexo según la
// codificación utilizada en HL7 que se puede ver aquí:
CodigoSexo {const String MASCULINO = "M"
const String FEMENINO = "F"
const String IDENFINIDO = "UN"
// Debe ser alguna de las constantes definidas previamente
String codigo
}
// Identidades a comparar, con respectivos sus valores para cada atributo
Identidad id1 = { nom11, nom12, ap11, ap12, sexo1, fecha_nac1 }
Identidad id2 = { nom21, nom22, ap21, ap22, sexo2, fecha_nac2 }
Como se mencionó, una de las ideas detrás del algoritmo es que, cada atributo de la identidad tiene un peso distinto en cuanto a la identificación de la persona. A continuación se especifica el peso de cada atributo en la identificación, donde la regla que deben cumplir estos valores es que deben sumar 1, porque si se tienen todos los atributos de la identidad, estos sirven para identificar a la persona en un 100%. Esto se traduce a que si el peso del primer nombre es 0.175, quiere decir que el primer nombre identifica a una persona en un 17,5%. Los valores aquí propuestos son valores encontrados empíricamente, para los cuales se obtuvo un buen funcionamiento del algoritmo (AVI-b).
// Los pesos deben sumar 1
pesos[nom1] = 0.175
pesos[nom2] = 0.175
pesos[ap1] = 0.175
pesos[ap2] = 0.175
pesos[sexo] = 0.1
pesos[fecha_nac] = 0.2
No está de más comentar que si bien los pesos planteados para el algoritmo básico (AVI-b) son constantes, por lo expresado en las ideas que están detrás del algoritmo, para el algoritmo avanzado (AVI-a), estos pesos serían funciones que dependen del valor de cada atributo.
A continuación se especifican los algoritmos de comparación de atributos simples que se utilizan para calcular el índice de coincidencia, que es el resultado del AVI-b. Se plantean dos algoritmos distintos para la comparación de nombres y apellidos, uno para el sexo y otro para la fecha de nacimiento. El primer algoritmo para comparar nombres hace la cuenta de cuantos caracteres coinciden en valor y posición y retorna esta cantidad dividida el largo de la palabra más larga, por lo que se obtiene un resultado en el rango 0..1, con valor 1 cuando los nombres y apellidos coinciden completamente. El segundo algoritmo de comparación de nombres está basado en la distancia de Levenshtein, que calcula cuantos caracteres se le deben agregar a una palabra para hacerla coincidir con otra, por lo tanto si el resultado de Levenshtein es 0 las palabras son la misma. La el índice basado en Levenshtein va a dar resultados más altos cuando haya errores de transposición u omisión de caracteres en alguno de los nombres que se están comparando, mientras que el primer algoritmo va a dar más bajo cuando uno de los nombres que se compara tiene alguna letra de menos. Luego voy a mostrar un ejemplo de esto, así que si no se entendió, luego lo retomaremos.
// Case Insensitive Char by Char:
// comparacion de palabras utilizando indice basado en
// comparacion caracter a caracter.
// comparacion de palabras utilizando indice basado en
// comparacion caracter a caracter.
coin_ci_cbc( String a, String b)
{
// Se pasa todo a minusculas para comparar
a = pasar_a_minusculas( a )
b = pasar_a_minusculas( b )
// Se pasa todo a minusculas para comparar
a = pasar_a_minusculas( a )
b = pasar_a_minusculas( b )
int max_len = maxLargo(a, b) // Largo del string mas largo
int min_len = minLargo(a, b) // Largo de string mas corto
int coincidencias = 0
for (i = 0..min_len)
{
if ( a[i] == b[i] ) coincidencias ++
}
return coincidencias / max_len
}
// Case Insensitive Levenshtein:
// comparacion de palabras utilizando indice basado en distancia de Levenshtein
// Mas info>
// - http://www.levenshtein.net/
// - http://es.wikipedia.org/wiki/Distancia_de_Levenshtein
{
// Largo del string mas largo
int max_len = maxLargo(a, b)
// Calcula el indice basado en la distancia de levenshtein
return 1 - ( levenshtein(a, b) / max_len )
// Se pasa todo a minusculas para comparar
a = pasar_a_minusculas( a )
b = pasar_a_minusculas( b )
// Largo del string mas largo
int max_len = maxLargo(a, b)
// Calcula el indice basado en la distancia de levenshtein
return 1 - ( levenshtein(a, b) / max_len )
}
coinSEXO(CodigoSexo s1, CodigoSexo s2)
{
if (s1.codigo == s2.codigo) return 1
return 0
}
coinFECHA (Fecha f1, Fecha f2)
{
if (f1 == f2) return 1
return 0
}
Por último, el cálculo del Índice de Coincidencia que será resultado del AVI-b, como vemos usamos los pesos y los algoritmos para calcular la comparación de atributos simples. En el ejemplo se utiliza coin_ci_cbc como comparador de nombres, éste se podría cambiar por coin_ci_levens.
IC( id1, id2 ) = pesos[nom1] * coin_ci_cbc(id1.nom1, id2.nom1) +
pesos[nom2] * coin_ci_cbc(id1.nom2, id2.nom2) +
pesos[ap1] * coin_ci_cbc(id1.ap1, id2.ap1) +
pesos[ap2] * coin_ci_cbc(id1.ap2, id2.ap2) +
pesos[sezo] * coinSEXO(id1.sexo, id2.sexo) +
pesos[fecha_nac] * coinFECHA(id1.fecha_nac, id2.fecha_nac)
En la siguiente tabla se puede ver el comportamiento del algoritmo básico (AVI-b) probando con algunos casos donde se toma una identidad y se varía algún dato para verificar cómo esta modificación afecta al Índice de Coincidencia (IC) que obtengo como resultado. Algunas aclaraciones para poder interpretar correctamente los resultados:
- La identidad ID1 es siempre la misma, la que varía es ID2 en algunos valores.
- Se hicieron 3 casos de comparación, probando con los dos algoritmos distintos para la comparación de nombres y apellidos.
- Las filas de igual color corresponden a comparaciones de las mismas identidades pero utilizando algoritmos distintos para la comparación de nombres, es decir: ci_cbc o ci_levens.
- En las filas 1 y 4, la variación de ID2 con respecto a ID1 es que en el segundo nombre se sacó una letra, la C.
- En las filas 2 y 5, la variación de ID2 con respecto a ID1 es en la fecha de nacimiento.
- En las filas 3 y 6, la variación de ID2 con respecto a ID1 es el primer nombre completo, manteniendo todos los otros datos. Este caso se podría dar en hermanos gemelos o mellizos, y el algoritmo debería ayudar a diferenciar entre ellos, si no es así, se debería utilizar la identidad extendida mediante los datos de "indicador de nacimiento múltiple" y "orden de nacimiento" que se describen en el documento del STID.
| # | IC | Algor. | ID1 | ID1 fecha | ID2 | ID2 fecha |
|---|---|---|---|---|---|---|
| 1 | 0.86 | ci_cbc | Ana Jacqueline Gomez Rodriguez | 1983-11-22 F | Ana Jaqueline Gomez Rodriguez | 1983-11-22 F |
| 2 | 0.8 | ci_cbc | Ana Jacqueline Gomez Rodriguez | 1983-11-22 F | Ana Jacqueline Gomez Rodriguez | 1983-11-12 F |
| 3 | 0.825 | ci_cbc | Ana Jacqueline Gomez Rodriguez | 1983-11-22 F | Carla Jacqueline Gomez Rodriguez | 1983-11-22 F |
| 4 | 0.9825 | ci_levens | Ana Jacqueline Gomez Rodriguez | 1983-11-22 F | Ana Jaqueline Gomez Rodriguez | 1983-11-22 F |
| 5 | 0.8 | ci_levens | Ana Jacqueline Gomez Rodriguez | 1983-11-22 F | Ana Jacqueline Gomez Rodriguez | 1983-11-12 F |
| 6 | 0.895 | ci_levens | Ana Jacqueline Gomez Rodriguez | 1983-11-22 F | Carla Jacqueline Gomez Rodriguez | 1983-11-22 F |
Tabla de resultados
Trabajo futuro:
Si bien se probó empíricamente el buen funcionamiento del Algoritmo de Verificación de Identidades Básico (AVI-b) creo que se podría ajustar aún más el resultado utilizando el algoritmo avanzado, donde los pesos se ajustan según los valores de los atributos de las identidades. Esto sería fácil de hacer si se tienen calculadas las frecuencias de nombres y apellidos de las identidades que se tienen en la base de datos donde están registradas las identidades a verificar, esto quiere decir, calcular cuántas personas tienen cada nombre (Pablo, Pedro, Juan, etc) y dividir cada una de esas cantidades entre el número total de identidades en la base. Luego esa frecuencia sería utilizada para aumentar el peso de un atributo (si es que hay poca frecuencia de ese nombre o apellido), o disminuir el peso de un atributo (si es que hay muchas personas que se llaman igual). Esta técnica ajustaría los valores resultantes de las comparaciones a un porcentaje más ajustado a la realidad. Como puede resultar obvio, los valores de frecuencias se deberían actualizar cada tanto, y con esto logramos un resultado que puede estar oculto a primera vista: el algoritmo se ajusta a las distintas frecuencias de nombres que se dan en distintos momentos. Es sabido que hay épocas donde un nombre se hace muy popular, y en algunos años el nombre más popular cambia, cambiando la frecuencia de personas que podemos encontrar con esos nombres en nuestras bases de datos. Con esto logramos un algoritmo que se adapta automáticamente (algoritmo adaptable) a cambios que se dan en la cultura de la sociedad. ¿Interesante no?
Conclusiones:
Cómo se puede apreciar en las filas 1 y 4 de la tabla de resultados, al cambiar una sola letra de un nombre o un apellido, el IC es mucho más alto usando el algoritmo ci_levens que el ci_cbc para comparar nombres, esto se debe a que el índice que se calcula en base a Levenshtein es más fuerte o se comporta mejor ante pequeños cambios. Este cambio se puede deber a un error humano en el registro, y es bueno tener un algoritmo que lo pueda detectar. Es decir que la detección de duplicados también ayuda a la detección de errores en el registro, y por lo tanto a mejorar la calidad del mismo, que es el objetivo planteado al inicio.
En las filas 2 y 5 no vemos cambio en el resultado del CI porque lo que es distinto entre las identidades es la fecha de nacimiento.
Por último, en las filas 3 y 6 vemos una pequeña diferencia en el CI, esto se debe a que el primer nombre es tan distinto entre ID1 e ID2 que tanto el índice basado en Levenshtein como el índice basado en la cuenta carácter a carácter detectan que ambos nombres son distintos, bajando el valor del CI en cantidades similares.
Espero que se hayan entendido las ideas detrás del algoritmo, cuáles eran los objetivos y que hayan quedado claras las conclusiones. Por cualquier consulta o comentario no duden en agregar un comentario.
Entradas
