Data Mining

Á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

© 2008
Coordinación de Ciencias Computacionales
INAOE

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

´
Arboles de Decisi´ n para Grandes Conjuntos deDatos
o
Anilu Franco Arcega1 , Jes´ s Ariel Carrasco Ochoa2 , Guillermo S´ nchez D´az3 ,
u
a
ı
Jos´ Francisco Mart´nez Trinidad4
e
ı
Coordinaci´ n de Ciencias Computacionales
o
´
Instituto Nacional de Astrof´sica, Optica y Electr´ nica
ı
o
Luis Enrique Erro # 1, Santa Mar´a Tonantzintla, Puebla, 72840, M´ xico
ı
e
1,2,4
{anifranco6,ariel,fmartine}@inaoep.mx
Tecnolog´as deInformaci´ n
ı
o
Universidad Polit´ cnica de Victoria
e
Calzada General Luis Caballero No. 1200, Cd. Victoria, Tamaulipas, 87070, M´ xico
e
3
gsanchezdiaz@yahoo.es
´
´
Resumen. Esta propuesta de tesis doctoral aborda el problema de generaci on de arboles de decisi´ n para
o
grandes conjuntos de datos. Como resultado preliminar se propone un algoritmo incremental para construir
´
arboles dedecisi´ n multivaluados para grandes conjuntos de datos num´ ricos que procese uno a uno los
o
e
objetos del conjunto de entrenamiento. Los resultados obtenidos muestran que el algoritmo propuesto es
competitivo en calidad y m´ s r´ pido que el algoritmo C4.5. Adem´ s, se compar´ con ICE que es un algoritaa
a
o
´
mo de generaci´ n de arboles de decisi´ n para grandes conjuntos de datos.o
o
´
Palabras Clave. Arboles de decisi´ n, clasificaci´ n supervisada, grandes conjuntos de datos.
o
o

1.

Introducci´ n
o

Dentro del Reconocimiento de Patrones uno de los problemas m´ s estudiados es el de Clasificaci´ n
a
o
´
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 deobjetos 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´ n supervisada tienen como objetivo determinar la pertenencia de un objeto
o
(descrito por un conjunto de atributos) a una o varias clases, bas´ ndose en la informaci´ n contenida en un
a
o
conjunto de objetospreviamente clasificados (conjunto de entrenamiento - CE ).
´
Dentro de los algoritmos utilizados para resolver problemas de clasificaci on supervisada se encuentran
´
´
los arboles de decisi´ n. Un arbol de decisi´ n es una estructura que se compone de nodos (internos y hojas)
o
o
y de arcos. Sus nodos internos est´ n caracterizados por uno o varios atributos de prueba y de estos nodos
a
sedesprenden uno o m´ s arcos. Cada uno de estos arcos tiene asociado un valor del atributo de prueba y
a
´
´
estos valores determinan qu´ camino seguir en el recorrido del arbol. Los nodos hoja contienen informacion
e
1

´
que permite determinar la pertenencia del objeto a una clase. Las carater´sticas principales de un arbol de
ı
decisi´ n son: construcci´ n sencilla, no necesitadeterminar de antemano par´ metros para su construcci´ n,
o
o
a
o
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´ cil interpretaci´ n de su estructura.
a
o
´
´
Existen diversas clasificaciones de los arboles de decisi´ n, por ejemplo de acuerdo al numero de atributos
o
´de prueba en sus nodos internos existen 2 tipos de arboles:
Univaluados, s´ lo contienen un atributo de prueba en cada nodo. Ejemplos de estos algoritmos son:
o
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...