PDF de programación - Capítulo 6 Evaluación de algoritmos

Capítulo 6

Evaluación de algoritmos



La evaluación de los algoritmos propuestos en el capítulo 2 (Soundex, Similarex,

Clases de Caracteres), se realizó en base a las características del texto previamente

reconocido con OCR. De ahí que se utilizaran algoritmos que trabajaran bajo este contexto,

en donde la información presentaría cierto grado de error, para el cual era necesario

establecer criterios y parámetros de evaluación, aspecto al cual se dedica este capítulo.



El material utilizado como indicamos en capítulos anteriores, fue material

bibliográfico perteneciente al acervo franciscano, colección que está constituida por libros

que datan aproximadamente del siglo XVI a XIX y cuyas características iban a propiciar la

existencia de errores en cuanto al reconocimiento de caracteres se refiere.



Como muestra se tomaron 6 libros de esta colección, de los cuales se digitalizaron

aproximadamente 25 páginas por unidad(libro). El tamaño de dicha muestra pudiera

parecer pequeño, sin embargo, fue suficiente para definir la eficiencia de cada algoritmo, ya

que estos trabajan a nivel de error en la información, no a nivel de volumen o cantidad,

debido a sus características.



A su vez, se analizó el texto generado por OCRde cada página para obtener una lista

de palabras (150) que presentaban errores por reconocimiento y que nos permitirían realizar

las pruebas de estos algoritmos. También fue necesario corregir cada una de las páginas de

la muestra para así poder calcular el número de ocurrencias reales de este conjunto de

palabras en la misma, valor que nos serviría posteriormente para el cálculo de los

porcentajes de precisión del apartado 6.1.

6.1 Parámetros de evaluación

Para

poderdeterminar

la

eficiencia

de

dichosalgoritmos,fue

necesario

establecerciertos parámetros de evaluación. En este caso nuestro parámetro fue la precisión,

que es la exactitud en la localización y recuperación del texto buscado en la información

existente.

Debido a la escasez en la información con respecto a estos algoritmos, no fue posible

localizar parámetros de evaluación preestablecidos por lo cual se proponen los siguientes.



-porcentaje de información correcta recuperada

-porcentaje de información relevante en resultados

-promedio general.

6.1.1 Porcentaje de información correcta recuperada



Por porcentaje de información correcta recuperada nos referimos a que parte del

total de ocurrencias existentes de una palabra en la muestra fueron obtenidas por el

algoritmo.

Para calcular este porcentaje tomamos como referencia el número de ocurrencias

correctas localizadas por el algoritmoy lo dividimos entre el numero total de ocurrencias

reales existentes en la muestra.

De esta manera tenemos que:



PICR = OCLX100



NTOR

donde:



PICR: porcentaje de información correcta recuperada

OCL: ocurrencias correctas localizadas por algoritmo





NTOR: número total de ocurrencias reales

Ejemplo:

Palabra buscada:

puntos



Ubicación real:



libro 1 página 5

libro 3 página 163

libro 4 página 145



Tabla 6.1 Ejemplo de ocurrencias recuperadas poralgoritmo

Palabra encontrada

Libro en la que se encontró

libro 4
libro 1
libro 1
libro 3

Número de página

145
201
5
144



puntos
apunto
puntos
punto

En este ejemplo la información correcta recuperada serán solamente las ocurrencias

que correspondan exactamente a la palabra puntos (Tabla 6.1), así nuestro PICR para el

mismo queda de la siguiente manera:



OCL = 2

NTOR = 3

Por lo tantoPICR = (2/3) * 100 =66.66%.



Esto significaría que de 100 ocurrencias reales que existan de una palabra en el

acervo, este algoritmo nos estaría encontrando solamente 66 .

6.1.2 Porcentaje de información relevante en resultados



Entiéndase por información relevante aquella que presenta una correspondencia

exacta con la palabra buscada con respecto al total de la información recuperada por el

algoritmo. Para calcular este porcentajese consideró el número de ocurrencias

correctamente localizadas por el algoritmo, dividido entre el número total de ocurrencias

recuperadas por el mismo,así:



PIR = OCL X100



NTO

Donde:



PIR: porcentaje de información relevante

NTO: número total de ocurrencias recuperadas en la búsqueda.

OCL: ocurrencias correctas localizadas por algoritmo

Continuando con el ejemplo de la sección6.1.1la información relevante se refiere

alas ocurrencias que correspondan exactamente a la palabra puntos (Tabla 6.1). De esta

manera el PIR sería:

OCL = 2

NTO = 4

Por lo tanto PIR = (2/4) * 100 = 50%



Este resultado implicaría entonces que de 100 ocurrencias devueltas por la

búsqueda, solamente 50 corresponde exactamente a la palabra buscada.

6.1.3 Promedio general



Debido a que el porcentaje deinformación recuperada representa qué tanto de la

información existente en la muestra se va a recuperar, y a que el porcentaje de información

relevante nos dice de los resultados obtenidos por el algoritmo qué porcentaje corresponde

a la búsqueda original, ambos se encuentran ligados debido a que un algoritmo que obtenga

un porcentaje alto de información recuperada, pero un bajo porcentaje de información

relevante no resulta práctico, ya que aunque se localice la mayor parte de la información

existente, esta se encontraría dentro de una gran cantidad de información incorrecta, por

ejemplo, si un algoritmo obtiene un porcentaje de información recuperada de 100% y un

porcentaje de información relevante recuperada de 10%significaría que de 100 ocurrencias

existentes de una palabra se recuperarían las 100,pero habría 900 ocurrencias incorrectas

más,por lo que la eficiencia general del algoritmo no seria muy buena. En base a lo anterior

se promediaran ambos porcentajes para obtener un porcentaje general de eficiencia.

6.2Metodología de evaluación



Para poder evaluar los parámetros anteriormente mencionados necesitábamos

establecer una metodología acorde a la naturaleza de loserrores en la información

almacenada, por lo cual se estimó necesario realizar las pruebas en base a los siguientes

criterios

•

•

•

ubicación del error en una palabra

longitud de palabra buscada

localización de palabra con error específico

6.2.1 Ubicación del error en una palabra



Uno de los criterios de evaluación establecidos se refiere a la ubicación que presenta

el error dentro de una palabra.

Para esto fue necesario realizar un análisis del texto reconocido para obtener

palabras claves que sirvieran para las pruebas en la búsqueda de información. Dichas

palabras se eligieron y clasificaron en las siguientes categorías:

•

•

•

palabras que presentaron errores al inicio

palabras que tuvieron errores en su punto medio

palabras que presentaron errores al final



Entiéndase como error al inicio de una palabra cuando este se ubica dentro de su

primera sílaba. Un error al final por lo tanto corresponderá al que se ubica en la última

sílaba. Por último el error en el punto medio es el que no se encuentra en ninguno de los

dos casos anteriores.

Este criterio se consideró importante debido aque es muy probable que una palabra

que tenga error al inicio sea más difícil de localizar por la forma de codificación de los

algoritmos.

6.2.2 Longitud de palabras buscadas



Para poder efectuar la prueba en base al tamaño de una palabra respecto a su

longitud, fue necesario primeramente establecer el número mínimo y máximo permisible en

la longitud de una cadena. Esto con la finalidad de aislar aquellaspalabras que no tuvieran

relevancia en la búsqueda,así como de considerar la mayor cantidad de palabras existentes

en nuestro lenguaje, para lo cual se generó la siguiente tabla.

Tabla 6.2 Longitud de palabra establecidos

Longitud de palabra

5
6
7
8
9
10
11



Debido a que una palabra de longitud pequeña puede presentar una probabilidad

mayor de pérdida de información en comparación con una de tamañomás grande por la

confusión durante el reconocimiento, seconsideró importante basar parte de las pruebas en

este criterio

6.2.3 Localización de palabra con error específico





Para esta prueba se seleccionaron palabras del

texto

reconocido que

presentabanerror en más de una sílaba. A diferencia de las dos evaluaciones anteriores, en

esta sólo se tomó en cuenta si se encontraba o no la palabraen la ubicación original de

donde se seleccionó, no tomando en cuenta cualquier otra ocurrencia de la misma dentro

del acervo.



Finalmente, las pruebas se realizaron empleando el software desarrollado y la base

de datos que contenía la información de los libros utilizados,que consistieron básicamente

en la búsqueda de información a nivel de contenido.

En la siguiente sección se mostrarán los resultados de esta evaluación así como las

conclusiones obtenidas de la misma.

6.3 Evaluación de los algoritmos propuestos

En base a las pruebasy parámetros establecidos en los apartados anteriores, se llegó

a los resultados que se describirán a continuación. Los parámetros de evaluación PICR,

PIR,sobre los cuales se obtuvieron los promedios generales mostrados en las Tablas 6.3 y

6.4 se muestran en el Apéndice B.

6.3.1 Resultados de pruebas por longitud de palabra buscada



En estos resultado