• Blog
  • Prediciendo errores humanos de trámites con la distancia de Levenshtein

Prediciendo errores humanos de trámites con la distancia de Levenshtein

30 de diciembre de 2016

Toda tarea humana puede tener un error de por medio, sin importar la naturaleza o el grado de experiencia del que la ejecute. Por algo, es una norma pensar que no debemos nunca confiar en nuestro usuario.

En el caso del IFARHU, se guardan registros de cerca de 800 mil estudiantes distintos (con sus acudientes) dentro de los distintos programas de becas. Todos estos trámites han sido realizado, en algún momento, por una persona que jugó el rol de tramitador.

Históricamente, muchos de estos datos venían con defectos de tramitación como errores en los nombres o apellidos de los estudiantes o sus representantes legales, lo que ocasionaba problemas al momento de devengar sus beneficios económicos.

Dado este problema, se implementó en 2016 y por primera vez, un trámite cruzado bajo verificación con el Tribunal Electoral de Panamá (T.E.), para todos los estudiantes pertenecientes al programa de Beca Universal, el programa más grande del IFARHU. Ahora, ¿cómo hacer con los estudiantes que estaban tramitados?.

#.Verificación masiva cruzada

Primero, fue necesario realizar una verificación masiva de los cerca de 1.5 Millones de registros. Para ello, nos apoyamos con el Tribunal Electoral, solicitándole las generales (Cédula, Primer Nombre y Primer Apellido) de los estudiantes y representantes legales.

A partir de este archivo, desarrollamos un archivo en formato CSV con las siguientes columnas:

  • Cédula
  • Primer Nombre T.E.
  • Primer Apellido T.E.
  • Primer Nombre IFARHU
  • Primer Apellido IFARHU

Estos datos fueron volcados en una Base de Datos temporal y todos los estudiantes con igual Nombre y Apellido (tanto en T.E. como en IFARHU) fueron marcados con una bandera. Más de 90,000 registros dieron algún tipo de error, pero no podíamos simplemente cancelar estos registros, ya que la mayoría se debían a errores humanos.

#.Distancia de Levenshtein

La Distancia de Levenshtein es “una medida de similaridad entre dos cadenas de textos (…). La distancia es el número de borrados, inserciones o substituciones requeridas para transformar la cadena de entrada en la cadena objetivo”. Es decir, la Distancia de Levenshtein indica mediante un número, cuantas diferencias hay entre dos cadenas de texto.

Veamos el siguiente ejemplo:

  • Tenemos de entrada la palabra “boca”.
  • Tenemos de objetivo la palabra “roca”.

La distancia entre la palabra “boca” y “roca” sería 1, puesto que se necesita una substitución (b a r) para transformar la entrada en el objetivo.

Gracias a este algoritmo, es posible verificar cuantas diferencias hay entre dos palabras y por ende, podríamos determinar cuando una persona cometió un error humano o si es un error completo de tramitación (por ejemplo, si la persona utilizó un número de cédula totalmente errado).

#.Implementación

Para la implementación, fue necesario transformar el CSV original en un CSV con una estructura similar a la siguiente:

  • Cédula
  • Nombre T.E. (Primer Nombre y Primer Apellido)
  • Nombre IFARHU (Nombres y Apellidos)
  • Distancia

Paso seguido, se desarrollo un script escrito en lenguaje Ruby que realizaría las siguientes acciones:

  • Haría una limpieza de ambos campos (eliminando espacios al inicio y al final, convirtiendo todo a mayúscula).
  • Verificaría cuantas partes tiene el Nombre IFARHU (utilizando los espacios vacíos - ” ” - de guía).
  • Si el Nombre IFARHU consta de 4 partes, se asume que tiene Primer y Segundo Nombre, Primer y Segundo Apellido.
  • Si el Nombre IFARHU consta de 3 partes, se asume que tiene Primer Nombre, Primer y Segundo Apellido.
  • Si el Nombre IFARHU consta de 2 partes, se asume que tiene Primer Nombre, Primer Apellido.
  • Si el Nombre IFARHU tiene la palabra ” DE ”, se asumirá que la persona tiene Apellido de Casa (DE GARCÍA, por ejemplo) y se verifica únicamente el Primer Nombre.
  • Si el Nombre IFARHU no consta de la palabra ” DE ”, el Primer Nombre + Primer Apellido (tanto de IFARHU como de T.E.) se utilizan como la cadena de entrada y objetivo, respectivamente.

A partir de esto esto y contra el reloj, terminamos desarrollando un código similar al siguiente:

#!/usr/bin/env ruby

require 'rubygems'
require 'levenshtein'
require 'csv'

# Config
counter = 0
maxError = 3
inFile = 'entrada.csv'
outFile = 'salida.csv'
total = 0

# Extending String class for blank? method
class String
  def blank?
    self.strip.empty?
  end
end

# Formatting strings
def format_string str
  str.upcase.strip
end

# Does name has a "DE" inside?
def has_de? str
  str.include? " DE "
end

# Calculate Distance between two strings (te, ifarhu)
def calculate_distance te, ifarhu
  distance = 99
  ifarhuParts = ifarhu.split(" ")

  if ifarhuParts.length == 4 and !has_de? ifarhu
    # El nombre del IFARHU tiene 4 partes y ningun "DE"
    clearedName = "#{ifarhuParts[0]} #{ifarhuParts[2]}"
    distance = Levenshtein.distance te, clearedName
  elsif ifarhuParts.length == 3 and !has_de? ifarhu
    # El nombre del IFARHU tiene 3 partes y ningun "DE"
    clearedName = "#{ifarhuParts[0]} #{ifarhuParts[1]}"
    distance = Levenshtein.distance te, clearedName
  elsif te.blank? or ifarhu.blank?
    # El nombre del TE o del IFARHU viene vacio
    distance = 99
  elsif has_de? ifarhu
    # El nombre tiene "DE" en algun lado
    teParts = te.split(" ")
    distance = Levenshtein.distance teParts[0], ifarhuParts[0]
  else
    # El resto
    distance = Levenshtein.distance te, ifarhu
  end

  distance
end

# In
lines = CSV.read(inFile)
lines.each do |line|
  id        = format_string line[0]
  tribunal  = format_string line[1]
  ifarhu   	= format_string line[2]

  line[0] = id
  line[1] = tribunal
  line[2] = ifarhu

  distance = calculate_distance tribunal, ifarhu

  line << distance
end

# Out
CSV.open(outFile, 'w') do |csv|
  lines.each do |line|
    total = total + 1
    counter = counter + 1 if line[3] <= maxError
    csv << line
  end
end

# Print
p "Total: #{total}"
p "Corregidos: #{counter}"
p "Con error: #{total - counter}"

Quizás el código no es el más limpio ni el más lindo, pero luego de unos 15 minutos pudimos ejecutar el mismo y tuvimos resultados interesantes. Más que un post de programación, es un post para demostrar que con la implementación de un poquito de tecnología puede ayudarse a cualquier área operativa que confronte problemas de gran magnitud.

#.Resultados

Gracias a esta implementación y teniendo como márgen admitido hasta una distancia de 3, se pudo corregir cerca del 80% de los errores de tramitación en menos de 20 minutos de esfuerzo, entendiendo que hasta una distancia de 3 (entre estudiante y representante legal) podía ser considerado como un error humano del tramitador.