En un artículo previo, he definido un algoritmo para detectar el Índice de Coincidencia (IC) entre dos identidades de personas. Estas identidades están formadas por un conjunto de datos arbitrario, como nombres, apellidos, sexo fecha de nacimiento, etc. En el artículo previo, no se especificó cómo eran seleccionadas las idendidades a ser comparadas. En este artículo la idea es definir los conceptos que permitan entender las distintas formas de pre-selección de identidades de forma que las comparaciones no tarden años en ejecutarse, y a la vez permita detectar la mayor cantidad de registros duplicados en una base de datos.
Objetivo
El objetivo final del cálculo del IC entre dos identidades es poder encontrar posibles duplicados en los registros de las personas (sobre todo entre los pacientes). Una vez que se encuentran dos o más registros duplicados, se procede a la unión de esos registros. Esto es esencial para garantizar que los procesos de identificación de personas (en el ámbito de la salud) funcionen correctamente, y para garantizar que el registro clínico se realiza para la persona correcta, y que todos los registros clínicos de esa persona están asignados a una única identidad (si la persona tiene más de una identidad, por tener registros de identidades duplicadas, su información sanitaria estará fragmentada, o sea siempre será incompleta).
Entonces, es necesario ejecutar el algoritmo que detecta coincidencias tomando y comparando de a 2 los registros de las personas en la base de datos de pacientes de una o múltiples instituciones sanitarias. El problema es que si en una base de datos con 1000 pacientes se hacen comparaciones de a 2, se terminan haciendo 1.000.000 (1M) comparaciones. Tal vez 1M comparaciones no sea un gran problema, pero ¿qué pasaría si la base de datos tuviera 1M registros de pacientes?, ¡las comparaciones se disparan a un millón de millones!. En este caso, si cada comparación tarda unos 3 segundos, el total de las comparaciones tardarían unos 95129 años aproximadamente.
El objetivo es claramente bajar ese tiempo de ejecución, pero a la vez garantizar que se encontrarán todos los duplicados en las identidades persentes en la base de datos.
Para lograr esto es necesario disminuir la cantidad de registros a comparar de 2 en 2, por lo que previamente a ejecutar la comparación entre 2 identidades, ejecutaremos una heurística que permita preseleccionar todas las identidades que deben compararse, siendo esta cantidad mucho menor a la cantidad de identidades de personas guardadas en la base de datos.
Debe quedar claro que el único método que garantiza que se encuentran todos los duplicados en una base de datos es comparar 2 a 2 todos los registros de la base, cosa que, como ya mencionamos, es impracticable en bases de datos con muchos registros.
La heurística con la que se consigan encontrar todos los duplicados, será la heurística óptima, pero ninguna heurística puede garantizar esto para cualquier base de datos con identidades de personas. O sea, que la los resultados de aplicar la heurística para preselección de registros, depende de la base de datos. Profundizaré sobre este concepto más adelante.
Metodología
El objetivo de las heurísticas es obtener conjuntos de registros de identidades que "se parecen en algo", pero sin necesidad de ejecutar el Algoritmo de Verificación de Identidades (AVI) para calcular el Índice de Coincidencia entre las identidades. A estos conjuntos de identidades "parecidas" les llamaremos "Clases de Preselección" o solo "CP". De este modo, las compararciones de a 2 identidades usando el AVI, se hacen solo sobre las identidades de cada CP, no sobre todos los registros de identidades.
A continuación voy a mostrar el camino lógico que seguí para ir de una comparación de 2 en 2 sobre todos los registros de una base, hasta la solución final encontrando algunas heurísticas por "sentido común", que luego fueron probadas y funcionaron correctamente.
El peor caso empieza teniendo que comparar todas las identidades de la base, de 2 en 2. Esto se puede representar en un cuadro de doble entrada, donde cada par de entradas señalan una comparación a realizar. En la fig. 1 se puede apreciar este cuadro, y como se realizan todas las comparaciones de 2 en 2, aparece todo pintado de verde (este color indica las comparaciones a realizar).
Fig. 1: cuadro de comparaciones inicial
La primer optimización es que si se compara la identidad A con la identidad B, no es necesario hacer la comparación de B con A, por lo que se reducen las comparaciones a algo menos que la mitad, ya que también se evitan las comparaciones de A con A, B con B, etc. En la fig. 2, las comparaciones se hacen solo sobre la mitad de los registros.
Fig. 2: se comparan solo la mitad de las identidades
Esta primer optimización reduce la cantidad total de comparaciones pero no cambia el orden o la magnitud de comparaciones a realizar, es decir, si antes había que hacer millones de comparaciones, ahora hay que hacer millones/2. Por lo que si antes tardábamos más de 95000 años en hacer las comparaciones de 1M registros, ahora tardaremos más de 47000 años, cosa que sigue siendo impracticable.
Bien, ahora ¿qué pasaría si tuviéramos algo que nos dijera que comparaciones hacer antes de hacerlas?, podríamos bajar el número total de comparaciones y llevar el tiempo total de ejecución a algo razonable. Hacer esto implica que debemos agrupar identidades "parecidas" pero sin calcular el IC, ya que eso nos llevaría de nuevo al problema inicial. La idea es que el algoritmo que agrupe entidades parecidas en Clases de Preselección, también sea un algoritmo rápido. O sea que el tiempo total de hacer la preselección, más el tiempo total de calcular el IC entre 2 identidades, para todas las identidades de cada CP, sea muchísimo menor al tiempo total de ejecución de la primer optimización que se muestra en la fig. 2.
La idea es bien fácil, primero hay que definir el criterio por el cual se agrupan las identidades en las Clases de Preselección. Los criterios que he utilizado en mis pruebas son:
- Agrupar por primer letra del primer nombre
- Agrupar por primer letra del primer apellido
- Agrupar por fecha de nacimiento:
- Total: día, mes y año (no sirve si las fechas tienen errores en alguno de sus 3 campos)
- Parcial: solo día y mes, o solo mes y año (es más fuerte ante errores en algún campo de la fecha)
Para el criterio 1, lo que se hace es ordenar todas las identidades por primer nombre y tomar de a X identidades con X arbitrario, tomando como CPs por los registros 1..X, X+1..2X, etc., de esta forma cada CP tendrá solo X registros, siendo X mucho menor a N, con N la cantidad total de registros. Con N=1M y X=200, las comparaciones totales serían 5000 x 200^2 / 2 = 100M (en lugar de 1M de millones!). Igualmente este ejemplo, con cada comparación hecha en 3 segundos, tardaría unos 9 años. Si varía X, se podrá variar la cantidad total de comparaciones necesarias. Obviamente el tiempo de comparación de 2 registros dependerá de la velocidad del hardware y de lo complicado que sea el algoritmo de comparación entre 2 identidades.
En la fig. 3 se visualizan las comparaciones a realizar usando Clases de Preselección. Las flechas indican que hubo un ordenamiento de los registros según algún criterio. Se puede ver claramente que la cantidad total de comparaciones disminuye de forma considerable.
Fig. 3: primer aproximación para encontrar Clases de Preselección
De forma análoga se pueden aplicar otros criterios y obtener CPs alternativas. Un potencial problema es que los registros tengan errores y esos errores repercutan en el criterio que se use para crear las CPs. Por ejemplo, si se usa el criterio de tomar de a X identidades, tal que estén ordenadas por la primer letra del primer nombre, si existen muchos primeros nombres con error de registro en la primer letra, un potencial duplicado puede no ser detectado, ya que las identidades con error en la primer letra del primer nombre van a parar a otra CP. Con esto fundamentamos una afirmación hecha previamente: la heurística o criterio que se utilice para crear las CPs depende de cada base de datos, porque depende de los errores que haya en el registro.
Para conseguir una heurística fuerte ante los errores más comunes en nuestros registros, se pueden optar por dos estrategias:
- Hacer un estudio estadístico de los errores más comunes en el registro
- Utilizar más de una heurística para calcular los ICs entre las identidades
En mi caso opté por la segunda estrategia. Lo que hice fue calcular el IC para los registros de cada CP creada a partir del criterio de "primer letra del primer nombre", pero luego calculé de nuevo el IC para los CPs creados a partir del criterio "primer letra del primer apellido", de esa forma las comparaciones que se me escaparon en la primer vuelta, por tener errores en el primer nombre, en la segunda vuelta, utilizando el criterio por primer apellido, logro que se comparen. Obviamente, un registro puede tener errores en el primer nombre y en el primer apellido, pero la probabilidad de que esto suceda es menor de que un registro tenga error en el primer nombre o en el primer apellido.
Existe una optimización a este tercer paso, debido a un problema que presenta en los límites de las CPs. Ya que si se ordenan los registros y se toman 2 CPs contiguas, es problable que los últimos registros de la primer CP se parezcan a los primeros registros de la segunda CP, y al no considerar esto, estamos perdiendo duplicados potenciales. Para cubrir esto, lo que se hace es solapar un poco las CPs, así la primer CP calcula el IC entre sus identidades, pero también incluye a las primeras identidades de la segunda CP. En la fig. 4 se muestran las CPs solapadas para evitar que se escapen duplicados en los límites de las CPs.
Fig. 4: Clases de Preselección solapadas para incluir comparaciones de casos límite
Otras heurísticas pueden crearse en base a los datos disponibles, y usarse de forma coplementaria para no dejar registros parecidos afuera de las comparaciones.
Conclusiones
Es necesario crear alguna heurística que permita preseleccionar los registros que luego se van a comparar de 2 en 2, para así bajar los tiempos totales de ejecución.
Vimos que el éxito las heurísticas depende de los errores que se tengan en los registros de datos personales, por este motivo, antes de aplicar una heurística cualquiera para encontrar las CPs, es útil estudiar la base de datos para determinar cuáles son los errores más frecuentes y en cuáles datos. De este modo, podemos encontrar heurísticas que sean fuertes ante esos errores, permitiendo encontrar la mayor cantidad de duplicados posible.
Acompañando a las heurísticas se pueden usar otros métodos para acelerar las comparaciones entre las identidades de cada Clase de Preselección. Por ejemplo, el uso de programación paralela, donde distintos CPs puedan ser procesados en simultáneo, permite acelerar un poco las comparaciones totales, aunque no disminuye el orden de las comparaciones. Por ejemplo, si cada CP tiene 250 identidades, y cada comparación tarda 3 seg., las comparaciones para cada CP serán unas 250*250/2 = 31250 y tardarán unas 26 horas. Si se tienen 4 procesadores en paralelo, el tiempo total de ejecución bajará a unas 6,5 horas.
Espero que se haya entendido la idea, si no, comentan abajo y lo explicamos mejor.
Entradas
