Predicting Human Errors in Forms with Levenshtein Distance

4 min read

Every human task can have an error involved, regardless of the nature or degree of experience of the person who executes it. For some reason, it is a rule to think that we should never trust our user.

In the case of IFARHU, records are kept of nearly 800 thousand different students (with their guardians) within the different scholarship programs. All of these procedures have been carried out, at some point, by a person who played the role of processor.

Historically, many of these data came with processing defects such as errors in the names or surnames of the students or their legal representatives, which caused problems when accruing their financial benefits.

Given this problem, in 2016 and for the first time, a cross-verification procedure was implemented with the Electoral Tribunal of Panama (T.E.), for all students belonging to the Universal Scholarship program, the largest IFARHU program. Now, what to do with the students who were processed?

#.Mass Cross Check

First, it was necessary to carry out a massive verification of the nearly 1.5 Million records. To do this, we rely on the Electoral Court, requesting the general information (ID, First Name and First Surname) of the students and legal representatives.

From this file, we develop a file in CSV format with the following columns:

  • ID
  • First Name T.E.
  • First Last Name T.E.
  • First Name IFARHU
  • First Surname IFARHU

These data were dumped into a temporary Database and all students with the same First and Last Name (both in T.E. and IFARHU) were marked with a flag. More than 90,000 registrations gave some type of error, but we couldn’t simply cancel these registrations, since most were due to human error.

#.Levenshtein Distance

The Levenshtein Distance is “a measure of similarity between two strings of texts (…). The distance is the number of deletions, insertions or substitutions required to transform the input string into the target string.” That is, the Levenshtein Distance indicates, by means of a number, how many differences there are between two text strings.

Let’s look at the following example:

  • We have the word “mouth” at the outset.
  • We are targeting the word “rock.”

The distance between the word “mouth” and “rock” would be 1, since a substitution (b to r) is needed to transform the input into the target. Thanks to this algorithm, it is possible to verify how many differences there are between two words and therefore, we could determine when a person made a human error or if it was a complete processing error (for example, if the person used a completely wrong ID number).

#.Implementation

For the implementation, it was necessary to transform the original CSV into a CSV with a structure similar to the following:

  • ID
  • Name T.E. (First Name and First Last Name)
  • Name IFARHU (First and Last Names)
  • Distance

Next, a script written in Ruby language was developed that would perform the following actions:

  • I would clean both fields (eliminating spaces at the beginning and end, converting everything to upper case).
  • I would verify how many parts the IFARHU Name has (using the empty spaces - ” ” - as a guide).
  • If the IFARHU Name consists of 4 parts, it is assumed that it has First and Middle Name, First and Middle Last Name.
  • If the IFARHU Name consists of 3 parts, it is assumed that it has First Name, First and Second Last Name.
  • If the IFARHU Name consists of 2 parts, it is assumed to have First Name, First Last Name.
  • If the IFARHU Name has the word “DE”, it will be assumed that the person has a Home Last Name (DE GARCÍA, for example) and only the First Name is verified.
  • If the IFARHU Name does not consist of the word “DE”, the First Name + First Last Name (of both IFARHU and T.E.) are used as the input and target string, respectively.

From this and against the clock, we ended up developing a code similar to the following:

#!/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}"

Maybe the code is not the cleanest or the prettiest, but after about 15 minutes we were able to run it and we had interesting results. More than a programming post, it is a post to demonstrate that the implementation of a little technology can help any operational area that faces large problems.

#.Results

Thanks to this implementation and having as an admitted margin up to a distance of 3, it was possible to correct about 80% of the processing errors in less than 20 minutes of effort, understanding that up to a distance of 3 (between student and legal representative) could be considered a human error by the processor.