Fermín Pitol, Blog de Inteligencia Artificial en Español: Algoritmo de discretización CAIM

Bien como el nombre de esta entrada indica, hablaré de l algoritmo de discretización CAIM[1]. Antes de continuar, abordemos la definición de discretización desde el punto de vista de la minería de datos:

Discretización: Es el proceso mediante el cual los valores se incluyen en depósitos para que haya un número limitado de estados posibles. Los depósitos se tratan como si fueran valores ordenados y discretos [2].

En pocas palabras es crear rangos, por ejemplo, veamos una parte de la famosa tabla iris [3]:

Como podemos observar, tenemos aquí una tabla con atributos continuos, esto es común es cualquier tabla. Bueno ahora supongamos que deseamos crear rangos para uno de sus atributos, digamos “sepalwidth”, tenemos aquí varias soluciones posibles:

Utilizar el conocimiento inherente de los datos y elegir manualmente los rangos.
Crear algún modelo en el cual se cree ‘x’ cantidad de rangos y cada rango contenga en promedio la misma cantidad de valores, esto es, por ejemplo, tener rangos con la misma diferencia 2-4, 4-6, 6-8 etc.
Parecido al anterior pero en vez de que los rangos tengan las mismas distancias ahora se intentará que cada uno contenga la misma cantidad de elementos, es decir, si tenemos una base con 1500 registros, podríamos crear tres rangos y que cada uno contuviera 500 registros.
Utilizar algún algoritmo de discretización que se encargue de la creación de los rangos en base a heurísticas que intenten agrupar los datos con la mayor ganancia de información.

Como se puede observar, si se tiene suficiente conocimiento de la información, pues no hablar más, el primer punto es el más indicado, pero de no ser así, bueno cada quien sus gustos, yo me decantaré por explicar el último punto, el de crear un algoritmo que me entrega rangos que maximicen mi ganancia de información (se escucha bonito pero se refiere a que pueda explicar mejor mis datos).

Existen varios métodos creados con este fin, por citar algunos:

· Maximum entropy
· IEM
· CADD
· CAIR
· CAIM
· FCAIM
· Shanon
· Paterson-Niblett
· Equal Width
· Equal Frequency

Básicamente estos algoritmos se dividen en dos tipos, basados en clase y no basados en clase. Los primeros requieren de una clase que identifique a sus datos (en la tabla mostrada anterior tenemos un atributo llamado “class” que se encarga de realizar esto), estos algoritmos son un poco más “fiables”, debido a que se cuenta con mayor información para poder tomar decisiones al momento de crear los rangos, usualmente sus algoritmos son muy parecidos pero cambia la fórmula que nos brinda la ganancia de información. Los no basados en clase son algoritmos en general más rápidos, aquí no se tiene algo que identifique a los datos, entonces no existe mucho de donde buscarle, simplemente ordenan la información y la distribuyen de manera equitativa en un número x de valores discretos.

En esta entrada nos centraremos en el algoritmo CAIM[1] por sus siglas en inglés (class attribute interdependence maximization).

Este algoritmo posee las siguientes ventajas:

Intenta reducir el número de intervalos a ser creados, el algoritmo determina cuantos rangos serán creados y no necesita supervisión alguna por parte de una persona.
Es rápido o al menos no tiene un alto coste computacional.
Maximiza la interdependencia entre los intervalos creados y las clases.
Minimiza la información perdida en el proceso de discretización.

Sin entrar más en terminologías veamos el algoritmo:

Entrada: un conjunto de datos, clases y atributos continuos, M, S, F respectivamente.

Para cada Fi realizar

Paso uno:

1.1 Encontrar en valor mínimo (d0) y el valor máximo (dn)
1.2 Formar un conjunto de todos los valores distintos de Fi, colocados en orden ascendente, crear una variable B que contendrá la siguiente información: d0, todos los valores intermedios sin repetir, dn. (Por valores intermedios se refiere a sumar los atributos y dividirlos entre dos, es decir, si tenemos como datos 4,5 entonces un punto intermedio seria 4.5)
1.3 Crear una variable D que contendrá el esquema de discretización, e inicializarla con D[0] = d0 y D[1] = dn. Establecer la variable GlobalCaim = 0;

Paso dos:

2.1 Inicializar una variable K = 1
2.2 Tentativamente agregar algunos límites, de B que no se encuentren ya en D y calcular su correspondiente valor CAIM
2.3 Aceptar el límite que posea el valor mayor de CAIM
2.4 Si (CAIM > GlobalCAIM or K < S (Donde S es la cantidad de clases existentes)) entonces actualiza D con el limite aceptado en el paso 2.3 y establece GlobalCAIM = CAIM, sino terminar el proceso
2.5 establece K = K + 1

Salida: El vector D que indica los valores discretizados

Como podemos observar no se trata de un algoritmo complicado, aunque claro, debemos de calcular el valor CAIM. La fórmula es la siguiente:

Para obtener las variables y calcular la fórmula debemos de hacer uso de una matriz llamada "quanta matrix":

En donde:

C1,Ci ...Cs. :Son las clases (para el caso de la tabla iris serian: Iris-setosa, Iris-versicolor, Iris-virginica.
[d0, d1]..[dn-1,dn] : Son los intervalos.
q11.: Es la cantidad de atributos de la clase C1 es encontrado en el intervalo [d0,d1].
Interval Total: es la suma de las columnas de la matriz.
Class Total: Es la suma de las filas.
M: representa al total de atributos proporcionados

Ahora bien para crear la "quanta matrix" es necesario se creen los intervalos, estos se crean en el paso 2.2, y la matriz se creará una por cada nuevo limite a verificar es decir, supongamos que tenemos a D[0] = 4.5 y D[1] = 7.9 (valores iniciales mínimo y máximo paso 1.3) y decidimos probar con el limite 6.8(obtenido aleatoriamente de B por ejemplo). Entonces tendríamos a D como:

D[0] = 4.5
D[1] = 6.8
D[2] = 7.9

Entonces nuestros intervalos serian:

4.5-6.8
6.8-7.9

Pues bien una vez creada la "quanta matrix" ya podemos obtener los valores para calcular la función de CAIM:

N: número de intervalos proporcionados por F
Maxr : Este es el máximo valor de cada columna para cada intervalo (por supuesto sin incluir la suma, es decir , solo las variables q)
M+r: Es la suma de un atributo en particular, es decir el resultado de cada columna en “Interval Total” de la “quanta matrix”

Simplemente se debe mandar a llamar a la función:

var D = ObtenDatos(data, S, atributo_a_discretizar, numero_limites_inferiores_a_probar);

en donde:

data: es la tabla en formato JSON explicada anteriormente.
S: Es un vector con las clases(S[0] = "Iris - setosa",S[1] = "Iris - versicolor",S[2] = "Iris - versicolor").
atributo_a_discretizar: Este es el nombre de la columna que se desea discretizar, ejemplo : "sepallength"
numero_limites_inferiores_a_probar: Es el número de intentos a realizar en el paso 2.2 del algoritmo.

Y lo que nos regresara será un vector D con todos los límites.

Espero les haya gustado la entrada. Cualquier duda pueden enviarme un correo a ferpitol@gmail.com

Referencias:

[1] http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=1269594&queryText%3Dcaim

[2] http://msdn.microsoft.com/es-es/library/ms174512.aspx

[3] http://archive.ics.uci.edu/ml/datasets/Iris

Fermín Pitol, Blog de Inteligencia Artificial en Español

Buscar este blog

lunes, 10 de marzo de 2014

Algoritmo de discretización CAIM

1 comentario: