PDF de programación - Árboles de Decisión para Grandes Conjuntos de Datos

Árboles de Decisión para Grandes
Conjuntos de Datos

Anilu Franco-Arcega, J. Ariel Carrasco-Ochoa,

Guillermo Sánchez-Díaz, J. Francisco Martínez-Trinidad



Reporte Técnico No. CCC-08-001

13 de Febrero de 2008



Coordinación de Ciencias Computacionales

© 2008

INAOE



Luis Enrique Erro 1
Sta. Ma. Tonantzintla,
72840, Puebla, México.

·Arboles de Decisi·on para Grandes Conjuntos de Datos

Anilu Franco Arcega1, Jes·us Ariel Carrasco Ochoa2, Guillermo S·anchez D·az3,

Jos·e Francisco Mart·nez Trinidad4

Coordinaci·on de Ciencias Computacionales

Instituto Nacional de Astrof·sica, ·Optica y Electr·onica

Luis Enrique Erro # 1, Santa Mar·a Tonantzintla, Puebla, 72840, M·exico

1;2;4fanifranco6,ariel,[email protected]

Calzada General Luis Caballero No. 1200, Cd. Victoria, Tamaulipas, 87070, M·exico

Tecnolog·as de Informaci·on

Universidad Polit·ecnica de Victoria

[email protected]

Resumen. Esta propuesta de tesis doctoral aborda el problema de generaci ·on de ·arboles de decisi·on para
grandes conjuntos de datos. Como resultado preliminar se propone un algoritmo incremental para construir
·arboles de decisi·on multivaluados para grandes conjuntos de datos num·ericos que procese uno a uno los
objetos del conjunto de entrenamiento. Los resultados obtenidos muestran que el algoritmo propuesto es
competitivo en calidad y m·as r·apido que el algoritmo C4.5. Adem·as, se compar·o con ICE que es un algorit-
mo de generaci·on de ·arboles de decisi·on para grandes conjuntos de datos.

Palabras Clave. ·Arboles de decisi·on, clasificaci·on supervisada, grandes conjuntos de datos.

1.

Introducci·on

Dentro del Reconocimiento de Patrones uno de los problemas m·as estudiados es el de Clasificaci·on
Supervisada, en donde se conoce que un universo de objetos se agrupa en un n ·umero dado de clases de las
cuales se tiene de cada una, una muestra de objetos que se sabe pertenecen a ella y el problema consiste en
dado un nuevo objeto poder establecer sus relaciones con cada una de dichas clases [1].

Los algoritmos de clasificaci·on supervisada tienen como objetivo determinar la pertenencia de un objeto
(descrito por un conjunto de atributos) a una o varias clases, bas·andose en la informaci·on contenida en un
conjunto de objetos previamente clasificados (conjunto de entrenamiento - CE).

Dentro de los algoritmos utilizados para resolver problemas de clasificaci ·on supervisada se encuentran
los ·arboles de decisi·on. Un ·arbol de decisi·on es una estructura que se compone de nodos (internos y hojas)
y de arcos. Sus nodos internos est·an caracterizados por uno o varios atributos de prueba y de estos nodos
se desprenden uno o m·as arcos. Cada uno de estos arcos tiene asociado un valor del atributo de prueba y
estos valores determinan qu·e camino seguir en el recorrido del ·arbol. Los nodos hoja contienen informaci·on

1

que permite determinar la pertenencia del objeto a una clase. Las carater·sticas principales de un ·arbol de
decisi·on son: construcci·on sencilla, no necesita determinar de antemano par·ametros para su construcci·on,
puede tratar problemas multi-clase de la misma forma en que trabaja con problemas de dos clases, facilidad
para ser representado mediante un conjunto de reglas y la f·acil interpretaci·on de su estructura.

Existen diversas clasificaciones de los ·arboles de decisi·on, por ejemplo de acuerdo al n·umero de atributos

de prueba en sus nodos internos existen 2 tipos de ·arboles:

Univaluados, s·olo contienen un atributo de prueba en cada nodo. Ejemplos de estos algoritmos son:
ID3 [2], C4.5 [3], CART [4], FACT [5], QUEST [6], Model Trees [7], CTC [8], ID5R [9], ITI [10]
[11], UFFT [12] [13], StreamTree [14], FDT [15], G-DT [16] y SPIDA [17].

Multivaluados, que poseen a un subconjunto de atributos en cada uno de sus nodos. Por ejemplo, PT2
[18], LMDT [19] [20], GALE [21] y C-DT [22] [23].

De acuerdo al tipo de decisi·on tomada por el ·arbol, hay dos tipos de ·arboles:

Difusos, dan un grado de pertenencia a cada clase del conjunto de datos, como por ejemplo, C-DT,
FDT, G-DT y SPIDA.

Duros, asignan la pertenencia del objeto a solamente una clase, as· el objeto pertenece o no pertenece
a una clase, ejemplos de estos algoritmos son: ID3, C4.5, CART, FACT, QUEST, Model Trees, CTC,
LMDT, GALE, ID5R, ITI, UFFT, PT2 y StreamTree.

Los algoritmos de generaci·on de ·arboles de decisi·on pueden ser clasificados de acuerdo a su capacidad de
procesar conjuntos de datos din·amicos, es decir, conjuntos en los cuales se permite agregar nuevos objetos.
De acuerdo a esto existen 2 tipos de algoritmos de generaci·on de ·arboles de decisi·on:

Incrementales, pueden procesar conjuntos de datos din·amicos de los cuales van obteniendo una solu-
ci·on parcial conforme se van analizando los objetos. Algunos ejemplos de este tipo de algoritmos son:
ID5R, ITI, UFFT, PT2 y StreamTree.

No incrementales, s·olo pueden trabajar sobre conjuntos de datos est·aticos, ya que para obtener la
soluci·on necesitan al conjunto de datos en su totalidad. Ejemplos de ellos son: ID3, C4.5, CART,
FACT, QUEST, Model Trees, CTC, FDT, G-DT, SPIDA, LMDT, GALE y C-DT.

Recientemente, se ha abordado el problema de generar ·arboles de decisi·on para grandes conjuntos de
datos. Estos conjuntos cuentan con una gran cantidad de objetos y en la mayoria de los casos no caben en
la memoria disponible, con lo cual la aplicaci·on de los algoritmos mencionados anteriormente resulta en un
alto costo computacional, tanto en tiempo como en espacio.

Por esa raz·on se han desarrollado algoritmos de generaci·on de ·arboles de decisi·on capaces de trabajar
con grandes conjuntos de datos, sin tener que mantener en memoria todo el conjunto de datos necesario para
generar el ·arbol de decisi·on. Ejemplos de algoritmos de este tipo son: SLIQ [24], SPRINT [25], CLOUDS
[26], RainForest [27], BOAT [28], ICE [29] y PUDT [30]. La problem·atica principal atacada por estos
algoritmos es precisamente poder manipular todo el conjunto de datos, a fin de construir un ·arbol de decisi·on
que permita determinar la pertenencia de nuevos objetos a alguna clase. Sin embargo, algunos algoritmos
mencionados contin·uan presentando restricciones en cuanto al manejo de la memoria, por la representaci ·on
que usan para el conjunto de datos (como SLIQ, SPRINT y CLOUDS), o bien algunos otros no procesan
todo el conjunto de datos al generar el ·arbol de decisi·on (como BOAT e ICE).

2

Otro problema en algoritmos para generar ·arboles de decisi·on que procesan grandes conjuntos de datos, es
el n·umero de veces que recorren el conjunto de datos completo, algunos de ellos (como RainForest) accesan
al conjunto hasta dos veces en cada nivel del ·arbol, con lo que resulta en un mayor tiempo de procesamiento.
De lo anterior, surge la motivaci·on de proponer un algoritmo para generar ·arboles de decisi·on, capaz
de procesar grandes conjuntos de datos, posiblemente din·amicos, que procese todo el conjunto de datos
disponible en un tiempo menor al de los algoritmos existentes.

2. Trabajo Relacionado

Esta secci·on est·a divida en dos partes, primero se presentan algunos conceptos b·asicos utilizados a lo
largo de este documento. Posteriormente se describen los trabajos relacionados con la l·nea de investigaci·on
de algoritmos que generan ·Arboles de Decisi·on para grandes conjuntos de datos.

2.1. Conceptos B·asicos

Un ·Arbol de Decisi·on (AD) es un grafo ac·clico dirigido, compuesto de un nodo llamado ra·z, el cual no
tiene arcos de entrada, y de un conjunto de nodos que poseen un arco de entrada. Aquellos nodos con arcos
de salida son llamados nodos internos o nodos de prueba y los que no tienen arcos de salida son conocidos
como hojas, nodos terminales o nodos de decisi·on [31].

Los principales objetivos que se persiguen al crear un AD [32] son:

Clasificar correctamente la mayor cantidad de objetos del CE.

Generalizar, durante la construcci·on del ·arbol, el CE a fin de que nuevos objetos sean clasificados con
el mayor porcentaje de aciertos posible.

Si el conjunto de datos es din·amico, la estructura del AD debe poder actualizarse f·acilmente.

Un algoritmo de generaci·on de ·arboles de decisi·on consta de 2 etapas: la primera es la etapa de inducci·on
del ·arbol y la segunda es la etapa de clasificaci·on. En la primer etapa se construye el ·arbol de decisi·on a
partir del conjunto de entrenamiento, com·unmente cada nodo interno del ·arbol se compone de un atributo de
prueba y la porci·on del conjunto de entrenamiento presente en el nodo es dividida de acuerdo a los valores
que pueda tomar ese atributo. La construcci·on del ·arbol inicia generando su nodo ra·z, eligiendo un atributo
de prueba y particionando el conjunto de entrenamiento en dos o m·as subconjuntos, para cada partici·on se
genera un nuevo nodo y as· suvesivamente. Cuando en un nodo se tienen objetos de m·as de una clase se
genera un nodo interno, cuando contiene objetos de una clase solamente, se forma una hoja a la cual se le
asigna la etiqueta de la clase. En la segunda etapa del algoritmo, cada objeto nuevo es clasificado por el
·arbol construido, se recorre el ·arbol desde el nodo ra·z hasta una hoja, a partir de la cual se determina la
pertenencia del objeto a alguna clase. El camino a seguir en el ·arbol lo determinan las decisiones tomadas
en cada nodo interno, de acuerdo al atributo de prueba presente en ·el.

Existen diversos criterios de selecci·on de atributos que se pueden utilizar para determinar el o los atributos

para caracterizar a los nodos internos del AD. Entre los criterios m·as usados se pueden encontrar:

Ganancia de Informaci·on [2]. La Ganancia de Informaci·on se defi