Redes Bayesianas en Minería de Datos

Las redes bayesianas son una alternativa para minería de datos, la cual tiene varias ventajas:

• Permiten aprender sobre relaciones de dependencia y causalidad.
• Permiten combinar conocimiento con datos.
• Evitan el sobre-ajuste de los datos.
• Pueden manejar bases de datos incompletos.

El obtener una red bayesiana a partir de datos es un proceso de aprendizaje,el cual se divide, naturalmente, en dos aspectos:

1. Aprendizaje paramétrico: dada una estructura, obtener las probabilidades a priori y condicionales requeridas.
2. Aprendizaje estructural: obtener la estructura de la red Bayesiana, es decir, las relaciones de dependencia e independencia entre las variables involucradas.

Las técnicas de aprendizaje estructural dependen del tipo de estructura de red: árboles, poliárboles y redes multicomectadas. Otra alternativa es combinar conocimiento subjetivo del experto con aprendizaje. Para ello se parte de la estructura dada por el experto, la cual se valida y mejora utilizando datos estadísticos.

Aprendizaje Paramétrico

El aprendizaje paramétrico consiste en encontrar los parámetros asociados a una estructra dada de una red bayesiana. Dichos parámetros consisten en las probabilidades a priori de los nodos raíz y las probabilidades condicionales de las demás variables, dados sus padres.

Si se conocen todas las variables, es fácil obtener las probabilidades requeridas. Las probabilidades previas corresponden a las marginales de los nodos raíz, y las condicionales se obtienen de las conjuntas de cada nodo con su(s) padre(s).

Para que se actualizen las probabilidades con cada caso observado, éstas se pueden representar como razones enteras, y actualizarse con cada observación. En el caso de un árbol, las fórmulas para modificar las probabilidades correspondientes son:

Probabilidades previas

$$P(A_{i})=(a_{i}+1)/(s+1)$$

$i=k$

$$P(A_{i})=a_{i}/(s+1)$$

$i\neq k$

Probabilidades condicionales

$$P(B_{j}\mid A_{i})=(b_{j}+1)/(a_{i}+1)$$

$i=k$ y $j=l$

$$P(B_{j}\mid A_{i})=b_{j}/(a_{i}+1)$$

$i=k$ y $j\neq l$

$$P(B_{j}\mid A_{i})=b_{j}/a_{i}$$

$i\neq k$

Donde $s$ corresponde al número de casos totales, $i$, $j$ los índices de las variables, $k$, $l$ los índices de las variables observadas.

Aprendizaje Estructural

Naïve Bayes

Como vimos antes, el clasificar Bayesiano Naive (CBN) asume independencia entre los atributos dada la clase y su estructura ya esta dada, por lo que solo se tienen que aprender las probabilidades de los valores de los atributos dada la clase.

Una forma de mejorar la estructura de un CBN es añadiendo entre los nodos o atributos que tengan cierta dependencia. Existen dos estructuras básicas:

• TAN: clasificador bayesiano simple aumentado con un árbol.
• BAN: clasificador bayesiano simple aumentado con una red.

Otra forma es realizando operaciones locales hasta que no mejore la predicción:

1. eliminar un atributo,
2. unir dos atributos en una nueva variable combinada,
3. introducir un nuevo atributo que haga que dos atributos dependientes sean independientes (nodo oculto).

Se pueden ir probando cada una de las opciones anteriores midiendo la dependencia de los atributos dada la clase:

$$I(X_{i},X_{j} \mid C) = \sum_{X_{i},X_{j}} P(X_{i},X_{j} \mi... ...og ( P(X_{i},X_{j} \mid C) / P(X_{i} \mid C) P(X_{j} \mid C) )$$

En base a lo anterior puede integrarse el siguiente algoritmo.
Algoritmo de Mejora Estructural:

1. Obtener la información mutua condicional (IMC) entre cada par de atributos.
2. Seleccionar el par de atributos de IMC mayor.
3. Probar las 3 operaciones básicas (i) eliminación, (ii) unión, (iii) inserción.
4. Evaluar las 3 estructuras alternativas y la original, y quedarse con la ``mejor'' opción.
5. Repetir 2-4 hasta que ya no mejore el clasificador.

Para evaluar las estructuras resultantes se pueden usar datos de prueba o una medida basada en MDL.

Árboles

El método para aprendizaje estructural de árboles se basa en el algoritmo desarrollado por Chow y Liu (68) para aproximar una distribución de probabilidad por un producto de probabilidades de segundo orden, lo que corresponde a un árbol. La probabilidad conjunta de $n$ variables se puede representar (aproximar) como:

$$P (X_{1},X_{2}, \ldots, X_{n}) = \prod_{i=1}^{n} P(X_{i}) P (X_{i} \mid X_{j(i)} ))$$

donde $X_{j(i)}$ es la causa o padre de $X_{i}$.

Se plantea el problema como uno de optimización y lo que se desea es obtener la estructura en forma de árbol que más se aproxime a la distribución ``real''. Para ello se utiliza una medida de la diferencia de información entre la distribución real ($P$) y la aproximada ($P^{*}$):

$$I(P,P^{*}) = \sum_{x} P(\mathbf{X}) log (P(\mathbf{X}) / P^{*}(\mathbf{X}))$$

Entonces el objetivo es minimizar $I$. Para ello se puede definir dicha diferencia en función de la información mutua entre pares de variables, que se define como:

$$I(X_{i}, X_{j}) = \sum_{x} P(X_{i},X_{j}) log (P(X_{i},X_{j}) / P(X_{i})P(X_{j}))$$

Se puede demostrar (Chow 68) que la diferencia de información es una función del negativo de la suma de las informaciones mutuas (pesos) de todos los pares de variables que consituyen el árbol. Por lo que encontrar el árbol más próximo equivale a encontrar el árbol con mayor peso. Basado en lo anterior, el algoritmo para determinar árbol Bayesiano óptimo a partir de datos es el siguiente:

1. Calcular la información mutua entre todos los pares de variables ($n(n-1)/2$).
2. Ordenar las informaciones mutuas de mayor a menor.
3. Seleccionar la rama de mayor valor como árbol inicial.
4. Agregar la siguiente rama mientras no forme un ciclo, si es así, desechar.
5. Repetir (4) hasta que se cubran todas las variables ($n-1$ ramas).

El algoritmo NO provee la direccionalidad de los arcos, por lo que esta se puede asignar en forma arbitraria o utilizando semántica externa (experto).

Por ejemplo, para el ejemplo de la tabla 2.2 para jugar golf nos queda la tabla 8.1.

Tabla 8.1: Información mutua entre pares de variables para el ejemplo del golf.

No.	Var 1	Var 2	Info. mutua
1	temp.	ambiente	.2856
2	juega	ambiente	.0743
3	juega	humedad	.0456
4	juega	viento	.0074
5	humedad	ambiente	.0060
6	viento	temp.	.0052
7	viento	ambiente	.0017
8	juega	temp.	.0003
9	humedad	temp.	0
10	viento	humedad	0

Poliárboles

Rebane y Pearl [89] extendieron el algoritmo de Chow y Liu para poliárboles. Para ello parten del esqueleto (estructura sin direcciones) obtenido con el algoritmo anterior y determinan las dirección de los arcos utilizando pruebas de dependencia entre tripletas de variables.

De esta forma se obtiene una red bayesiana en forma de poliárbol. En el caso de un poliárbol, la probabilidad conjunta es:

$$P(X) = \prod_{i=1}^{n} P (X_{i} \mid X_{j1(i)},X_{j2(i)},...,X_{jm(i)} )$$

donde $\{ X_{j1(i)},X_{j2(i)},...,X_{jm(i)} \}$ es el conjunto de padres de la variable $X_{i}$.

El algoritmo de Rebane y Pearl se basa en probar las relaciones de dependencia entre todas las tripletas de variables en el esqueleto. Dadas 3 variables, existen 3 casos posibles:

• Arcos divergentes: $X \leftarrow Y \rightarrow Z$.
• Arcos secuenciales: $X \rightarrow Y \rightarrow Z$.
• Arcos convergentes: $X \rightarrow Y \leftarrow Z$.

Los primeros dos casos son indistinguibles, pero el tercero es diferente, ya que las dos variables ``padre'' son marginalemente independientes. Entonces el algoritmo consiste en:

1. Obtener el esqueleto utilizando el algoritmo de Chow y Liu.
2. Recorrer la red hasta encontrar una tripleta de nodos que sean convergentes (tercer caso) -nodo multipadre-.
3. A partir de un nodo multipadre determinar las direcciones de los arcos utilizando la prueba de tripletas hasta donde sea posible (base causal).
4. Repetir 2-3 hasta que ya no se puedan descubrir más direcciones.
5. Si quedan arcos sin direccionar utilizar semántica externa para obtener su dirección.

El algoritmo está restringido a poliárboles y no garantiza obtener todas las direcciones. Desde el punto de vista práctico, un problema es que generalmente no se obtiene independencia absoluta (información mutua cero), por lo que habría que considerar una cota empírica.

Redes Generales

Existen dos clases de métodos para el aprendizaje genérico de redes bayesianas, que incluyen redes multiconectadas. Éstos son:

1. Métodos basados en medidas de ajuste y búsqueda.
2. Métodos basados en pruebas de independencia.

Dentro de los métodos basados en ajsute y búsqueda, se generan diferentes estructuras y se evalúan respecto a los datos utilizando alguna medida de ajuste. Estos métodos tienen dos aspectos principales:

1. Una medida para evaluar que tan buena es cada estructura respecto a los datos.
2. Un método de búsqueda que genere diferentes estructuras hasta encontrar la óptima, de acuerdo a la medida seleccionada.

Existen varias medidas pero dos son las más utilizadas:

• Medida bayesiana: estima la probabilidad de la estrutura dado los datos la cual se trata de maximizar. La medida bayesiana busca maximizar la probabilidad de la estructura dados los datos, esto es:
  
  $$P(Es \mid D)$$
  
  
  Donde $Es$ es la estructura y $D$ son los datos. La cual podemos escribir en términos relativos al comparar dos estructuras, $i$ y $j$ como:
  
  $$P(Es_i \mid D) / P(Es_j \mid D) = P(Es_i, D) / P(Es_j, D)$$
  
  
  Considerando variables discretas y que los datos son independientes, las estructuras se pueden comparar en función del número de ocurrencias (frecuencia) de los datos predichos por cada estructura.

• Longitud de descripción mínima (MDL): estima la longitud (tamaño en bits) requerida para representar la probabilidad conjunta con cierta estructura, la cual se compone de dos partes:
  1. Representación de la estructura,
  2. Representación del error de la estructura respecto a los datos.

  La medida MDL hace un compromiso entre la exactitud y la complejidad del modelo. La exactitud se estima midiendo la información mutua entre los atributos y la clase; y la complejidad contando el número de parámetros.

  Una constante, $\alpha$, en [0, 1], se utiliza para balancear el peso de cada aspecto, exactitud contra complejidad. Así, la medida de calidad está dada por:
  

  $$MC = \alpha (W / Wmax) + (1 - \alpha) (1- L / Lmax)$$
  
  
  Donde $W$ representa la exactitud del modelo y $L$ la complejidad, mientras que $Wmax$ y $Lmax$ representan la máxima exactitud y complejidad, respectivamente.

  Para determinar estos máximoa normalmente se considera una limitación en cuanto al número de padres máximo permitido por nodo.

  La complejidad está dada por el número de parámetros requeridos para representar el modelo, la cual se puede calcular con la siguiente ecuación:
  

  $$L= S_{i} [ k_{i} log_{2} n + d(S_{i} - 1) F_{i}]$$
  
  
  Donde, $n$ es el número de nodos, $k$ es el número de padres por nodo, $S_{i}$ es el número de valores promedio por variable, $F_{i}$ el número de valores promedio de los padres, y $d$ el número de bits por parámetro.

  La exactitud se puede estimar en base al ``peso" de cada nodo, en forma análoga a los pesos en el método de aprendizaje de árboles. En este caso el peso de cada nodo se estima en base a la información mutua con sus padres:
  

  $$w(xi, Fxi) = \sum_{xi} P(xi, Fxi) log [P(xi,Fxi)/P(xi)P(Fxi)]$$
  
  
  Y el peso (exactitud) total está dado por la suma de los pesos de cada nodo:
  
  $$W = \sum_{i} w(xi, Fxi)$$
  
  

Para utilizar la medida MDL se puede hacer un hill-climbing iniciando con una estructura simple (por ejemplo un árbol construido con Chow-Liu) y agregando las ligas que mejoren la medida MDL hasta alcanzar un mínimo local.

Algoritmo - búsqueda de la mejor estructura:

1. Generar estructura incial - árbol.
2. Calcular medida de calidad de la estructura inicial.
3. Agregar / invertir un arco en la estructura actual.
4. Calcular medida de calidad de nueva estructura.
5. Si se mejor la calidad conservar el cambio, si no dejar estructura anterior.
6. Repetir 3 a 5 hasta que ya no haya mejoras.

Otra posibilidad es empezar con una estructura compleja y eliminar ligas que reduzcan la medida MDL hasta llegar a un mínimo local.

Una última posibilidad es combinar los dos enfoques.

A diferencia del enfoque basado en una medida global, el enfoque basado en pruebas de independiencia usa medidas de dependencia local entre subconjuntos de variables.

El caso más sencillo es el del algoritmo de Chow y Liu, en el cual se mide la información mutua entre pares de variables. A partir de estas medidas, como se vió previamente, se genera una red bayesiana en forma de árbol. Analizando dependencias entre tripletas de variables, el método se extiende a poliárboles.

Este enfoque se puede generalizar para el aprendizaje de redes multiconectadas, haciendo pruebas de dependencia entre subconjunto de variables, normalmente dos o tres variables. Por ejemplo, se puede continuar el método de Chow y Liu agregando más arcos aunque se formen ciclos, hasta un cierte umbral mínimo de información mutua.

La desventaja es que pueden generarse muchos arcos ``innecesarios'', por lo que se incorporan formas de luego eliminar arcos. Hay diferentes variantes de este enfoque que consideran diferentes medidas de dependencia y diferentes etrategias para eliminar arcos innecesarios.