2.9.2 Grafos acíclicos dirigidos

Algunas de las técnicas más conocidas en la utilización de la minería de datos son árboles de decisión, las reglas de producción y las redes neuronales. Los grafos sirven para representar relaciones entre objetos de datos.

Una de las formas de representación del conocimiento y de los métodos de razonamiento utilizan las redes bayesianas. Estas redes bayesianas aprenden sobre las relaciones de dependencia y causalidad, combinan el conocimiento con los datos y pueden manejar relaciones entre distintas bases de datos.

La figura 2.13 muestra la estructura básica de Bayes en donde se comienza por una estructura de árbol con sus variables predictorias para posteriormente conectar la variable X con cada una de las variables predictorias R.

Figura 2.13 Representación básica del modelo de Bayes.

Como se puede apreciar, las redes bayesianas son modelos que describen las relaciones entre variables, estas pueden ser aplicadas a casi cualquier tipo de problema.

La conformación de una red bayesiana nos da información sobre las dependencias probabilísticas entre las variables y también sobre las independencias condicionales de una variable o variables. Dichas independencias simplifican la representación del conocimiento.

La aplicabilidad de las redes bayesianas para llevar a cabo la minería de datos sobre un conjunto de bases de datos permite articular de manera simbólica los patrones de relación que la red bayesiana genera. A la relación binaria entre los elementos de un conjunto se le denomina grafo.

Un grafo acíclico dirigido es una red bayesiana en el que cada nodo representa una variable y cada arco una dependencia probabilística, en la cual se especifica la probabilidad condicional de cada variable dados sus padres. Esta variable a la que apunta el arco es dependiente de la que está en el origen de éste.

En un grafo acíclico dirigido todas las conexiones están identificadas por un único camino simple que no repite vértices. Esto es, un vértice sólo se visita si han sido visitados todos sus predecesores.

El camino es simple si todos los nodos que forman el camino son distintos.

La aplicación de los grafos acíclicos dirigidos permite la representación del recorrido o navegación entre las redes de un determinado proyecto (transporte, comunicaciones, bases de datos, etc.), en donde cada vértice representan las tareas y las aristas las relaciones temporales entre ellas. Ver figura 2.14.

Figura 2.14 Representación de un grafo acíclico dirigido.

Como un primer aspecto que incorpora la teoría bayesiana es el control de la longitud o profundidad del camino recorrido por el grafo.

El recorrido de un grafo es uno de los problemas deducibles de las aplicaciones que pueden resolverse mediante diversos algoritmos existentes. Estos algoritmos de distancia pueden tomar decisiones sobre la navegación, los recorridos y sus ponderaciones de acuerdo a políticas de reducción en su longitud o en base al número de saltos necesarios.

Normalmente el orden de los algoritmos utilizados para la navegación del grafo esta definido por el número de saltos que se efectúan durante su recorrido : X=X+1, siendo su parámetro de representación una búsqueda binaria.

En la aplicación de la teoría de grafos acíclicos dirigidos hacia la generación, transmisión y distribución del conocimiento y su representación, se pueden identificar rápidamente cuales son los materiales más relevantes debido a que son aquellos de los cuales son ocupados por muchas referencias, generando con ello muchos arcos hacia los documentos de mayor relevancia.

La figura 2.15 muestra la representación gráfica de los arcos en un grafo acíclico dirigido. En la transmisión del conocimiento se observa que un material con más referencias (A) genera la mayor cantidad de arcos hacia las nuevas referencias, el material más nuevo (E) no cuenta con arcos debido a que no ha sido utilizado como referencia por otros materiales.

Figura 2.15 Recorrido de arcos en un grafo acíclico dirigido