[en] This thesis is about using small decision trees for classification and data mining. The intuitive idea behind this thesis is that a sequence of small decision trees may perform better than a large decision tree, reducing both training and exploitation costs. Our first goal was to develop a system capable to recognize several kinds of elements present in a document such as background, text, horizontal and vertical lines, line drawings and images. Then, each element would be treated accordingly to its characteristics. For example, background regions would be removed and not processed at all, while the other regions would be compressed using an appropriate algorithm, the lossy JPEG standard operation mode for images and a lossless method for the rest, for instance. Our first experiments using decision trees showed that the decision trees we built were too large and they suffered from overfitting. Then, we tried to take advantage of spatial redundancy present in images, using a multi-resolution approach: if a large block cannot be correctly classified, split it in four subblocks and repeat the process recursively for each subblock, using all previous computed knowledge about such block. Blocks that could not be processed at a given block size were labeled as mixed, so the word progressive came up: a first low resolution version of the classified image is obtained with the first classifier, and it is refined by the second one, the third one, etc, until a final version is obtained with the last classifier in the ensemble. Furthermore, the use of the progressive scheme yield to the use of smaller decision trees, as we no longer need a complex classifier. Instead of building a large and complex classifier for classifying the whole input training set, we only try to solve the easiest part of the classification problem, delaying the rest for a second classifier, and so. The basic idea in this thesis is, therefore, a trade-off between cost and accuracy under a confidence constraint. A first classification is performed at a low cost; if an element is classified with a high confidence, it is accepted, and if not, it is rejected and a second classification is performed, and so. It is, basically, a variation of the cascading paradigm, where a first classifier is used to compute additional information from each input sample, information that will be used to improve classification accuracy by a second classifier, and so on. What we present in this thesis, basically, is an extension of the cascading paradigm and an exhaustive empirical evaluation of the parameters involved in the creation of progressive decision trees. Some basic theoretical issues related to progressive decision trees such as system complexity, for example, are also addressed.

[es] Esta tesis trata sobre la utilización de árboles de decisión pequeños para la clasificación y la minería de datos. La idea intuitiva detrás de esta tesis es que una secuencia de árboles de decisión pequeños puede rendir mejor que un árbol de decisión grande, reduciendo tanto el coste de entrenamiento como el de explotación. Nuestro primer objetivo fue desarrollar un sistema capaz de reconocer diferentes tipos de elementos presentes en un documento, como el fondo, texto, líneas horizontales y verticales, dibujos esquemáticos y imágenes. Entonces, cada elemento puede ser tratado de acuerdo a sus características. Por ejemplo, el fondo se elimina y no se procesa, mientras que las otras regiones serían comprimidas usando el algoritmo apropiado, JPEG con pérdida para las imágenes y un método sin pérdida para el resto, por ejemplo. Los primeros experimentos usando árboles de decisión mostraron que los árboles de decisión construidos eran demasiado grandes y que sufrían de sobre-entrenamiento. Entonces, se trató de aprovechar la redundancia espacial presente en las imágenes, utilizando una aproximación de resolución múltiple: si un bloque grande no puede ser correctamente clasificado, romperlo en cuatro sub-bloques y repetir el proceso recursivamente para cada sub-bloque, usando todo el conocimiento que se haya calculado con anterioridad. Los bloques que no pueden ser procesados para una medida de bloque dada se etiquetan como "mixed", por lo que la palabra progresivo toma sentido: una primera versión de poca resolución de la imagen clasificada se obtiene con el primer clasificador, y se refina por el segundo, el tercero, etc., hasta que una versión final es obtenida con el último clasificador del montaje. De hecho, el uso del esquema progresivo lleva al uso de árboles de decisión más pequeños, ya que ya no es necesario un clasificador complejo. En lugar de construir un clasificador grande y complejo para clasificar todo el conjunto de entrenamiento, sólo tratamos de resolver la parte más fácil del problema de clasificación, retardando el resto para un segundo clasificador, etc. La idea básica de esta tesis es, entonces, un compromiso entre el coste y la precisión bajo una restricción de confianza. Una primera clasificación es efectuada a bajo coste; si un elemento es clasificado con una confianza elevada, se acepta, y si no lo es, se rechaza y se efectúa una segunda clasificación, etc. Es básicamente, una variación del paradigma de "cascading", donde un primer clasificador se usa para calcular información adicional para cada elemento de entrada, que será usada para mejorar la precisión de clasificación de un segundo clasificador, etc. Lo que presentamos en esta tesis es, básicamente, una extensión del paradigma de "cascading" y una evaluación empírica exhaustiva de los parámetros involucrados en la creación de árboles de decisión progresivos. Algunos aspectos teóricos relacionados con los árboles de decisión progresivos como la complejidad del sistema, por ejemplo, también son tratados.