Google+ Seguidores

jueves, 19 de julio de 2018

Árbol binario de búsqueda - Estructura de datos en Python

Introducción:

Hola amigos de Internet, mi nombre es Luis, y les doy nuevamente la bienvenida a "Mi Diario Python", el mejor blog hispanoamericano para Aprender Python.

En el día de hoy veremos un tema de estudio universitario muy importante en el área de ciencias de la computación, Árboles binario. Más específicamente, hablaremos sobre Árboles binario de búsqueda.

Al final, como siempre, realizaremos una implementación en Python.

Árbol Binario:

Un árbol binario es un conjunto de elementos cada uno de los cuales de denomina nodo. Si un nodo no contiene datos, se dice que es un nodo externo, de lo contrario lo denominamos nodo interno.

Un árbol binario es una estructura de dato no lineal en la que cada nodo puede apuntar a uno o máximo dos nodos, por ello el nombre "binario". 




La  imagen anterior representa un árbol binario de tamaño 9, 3 niveles, y altura 3 con un nodo raíz cuyo valor es 2.

Los árboles binarios son considerados como estructuras de datos jerárquicas y como tal su forma de recorrerlos difiere sustancialmente.El recorrido de un árbol binario se lleva a cabo en tres sentidos: Preorden, Inorden y Postorden.

Recorrido en Preorden:

El recorrido en preorden consiste, en primer lugar, en examinar el dato del nodo raíz, posteriormente se recorre el subárbol derecho en preorden y luego el subárbol izquierdo en preorden.

A continuación te mostrare una image con un árbol binario cuyo recorrido es en preorden:

preorden

El recorrido inicia con el subárbol izquierdo, el primer nodo a visitar es  la raíz  que es el nodo 10, luego se visita el subárbol izquierdo  con el nodo 5,  posteriormente el 3, luego el nodo 1, sigue con el nodo 4, pasamos al nodo 7  y luego el 9.
Continuamos con el recorrido del subárbol derecho en preorden, con la  visita del  nodo 15, luego el 14, se continúa con el 17, se visita el 16  y  se finaliza con la visita del nodo 20.

Recorrido en Inorden:

El recorrido en Inorden consiste en recorrer el subárbol izquierdo en Inorden, luego se examina el dato del nodo raíz, y finalmente se recorre el subárbol derecho en Inorden.

inorden


El recorrido inicia con el subárbol izquierdo, el primer nodo a visitar es el  3 luego se visita el 5 y posteriormente el 7, con esto se garantiza que el recorrido del subárbol izquierdo se hizo en Inorden.
 Finalizado el recorrido del subárbol izquierdo se visita el nodo de la raíz, que para este caso es el numero 10.
Solo queda recorrer el subárbol derecho en Inorden, es decir se visita el 11 luego el 12 y se finaliza con la visita del nodo 15.

Recorrido en Posorden:

El recorrido en postorden consiste en recorrer el subárbol izquierdo en postorden, luego el subárbol derecho en postorden, y finalmente examinar el dato del nodo raíz.

postorden

El recorrido inicia con el subárbol izquierdo, el primer nodo a visitar es el  3 luego se visita el 7 y posteriormente el 5 que es la raíz, con esto se garantiza que el recorrido del subárbol izquierdo se hizo en Postorden.
Finalizado el recorrido del subárbol izquierdo se inicia la visita al subárbol derecho en Postorden, es decir, se visita el 11 luego el 15 y se finaliza con la visita del nodo 12 que sería la raíz de este subárbol.
Solo queda recorrer la raíz del árbol que para este caso es el número 10.

Árbol binario de búsqueda:

Los árboles binarios de búsqueda, son un tipo especial de árbol binario cuya característica radica en la forma ordenada de insertar sus elementos, facilitando así la búsqueda de un nodo en particular.

La forma en la que se ordenan los nodos es la siguiente:
  • la rama de la izquierda contendrá elementos menores
  • la rama de la derecha contendrá elementos mayores




Las operaciones de un árbol binario de búsqueda son las siguientes:
  • Búsqueda: consiste en acceder a la raíz del árbol si el elemento a localizar coincide con éste la búsqueda ha concluido con éxito, si el elemento es menor se busca en el subárbol izquierdo y si es mayor en el derecho.
  • Inserción: es muy similar a la búsqueda y se puede dar una solución tanto iterativa como recursiva. Si tenemos inicialmente como parámetro un árbol vacío se crea un nuevo nodo como único el elemento a insertar. Si no lo está, se comprueba si el elemento dado es menor que la raíz.
  • Borrado: La operación de borrado se puede realizar de tres formas diferentes. Borrar un nodo sin hijos o nodo hoja, Borrar un nodo con su subárbol hijo y Borrar un nodo con dos subárboles hijo.
  • Recorridos: ya repasamos los recorridos de un árbol binario. Veamos otro ejemplo: 
Ejemplo árbol binario de búsqueda
Inorden = [6, 9, 13, 14, 15, 17, 20, 26, 64, 72].
Preorden = [15, 9, 6, 14, 13, 20, 17, 64, 26, 72].
Postorden =[6, 13, 14, 9, 17, 26, 72, 64, 20, 15].

Implementación:

Ahora, pongamos a prueba todo lo aprendido. Realizaremos todos los procesos mencionados anteriormente, crearemos un árbol binario de búsqueda con todas sus operaciones y su respectivo recorrido:

Puedes descargar y visualizar el código ingresando al siguiente enlace:

from __future__ import print_function

# Declaramos la clase "Node"
class Node:

    def __init__(self, label, parent):
        self.label = label
        self.left = None
        self.right = None
        self.parent = parent

        # Métodos para asignar nodos
    def getLabel(self):
        return self.label

    def setLabel(self, label):
        self.label = label

    def getLeft(self):
        return self.left

    def setLeft(self, left):
        self.left = left

    def getRight(self):
        return self.right

    def setRight(self, right):
        self.right = right

    def getParent(self):
        return self.parent

    def setParent(self, parent):
        self.parent = parent


class BinarySearchTree:

    def __init__(self):
        self.root = None

    def insert(self, label):
        # Creamos un nuevo nodo
        new_node = Node(label, None)
        # Si el árbol esta vacio
        if self.empty():
            self.root = new_node
        else:
            # Si el árbol no esta vacio
            curr_node = self.root
            while curr_node is not None:
                parent_node = curr_node
                if new_node.getLabel() < curr_node.getLabel():
                    curr_node = curr_node.getLeft()
                else:
                    curr_node = curr_node.getRight()
            if new_node.getLabel() < parent_node.getLabel():
                parent_node.setLeft(new_node)
            else:
                parent_node.setRight(new_node)
            new_node.setParent(parent_node)      
    
    # Operación de borrado
    def delete(self, label):
        if (not self.empty()):
            node = self.getNode(label)
            if(node is not None):
                if(node.getLeft() is None and node.getRight() is None):
                    self.__reassignNodes(node, None)
                    node = None
                elif(node.getLeft() is None and node.getRight() is not None):
                    self.__reassignNodes(node, node.getRight())
                elif(node.getLeft() is not None and node.getRight() is None):
                    self.__reassignNodes(node, node.getLeft())
                else:
                    tmpNode = self.getMax(node.getLeft())
                    self.delete(tmpNode.getLabel())
                    node.setLabel(tmpNode.getLabel())
    
    def getNode(self, label):
        curr_node = None
        if(not self.empty()):
            curr_node = self.getRoot()
            while curr_node is not None and curr_node.getLabel() is not label:
                if label < curr_node.getLabel():
                    curr_node = curr_node.getLeft()
                else:
                    curr_node = curr_node.getRight()
        return curr_node

    def getMax(self, root = None):
        if(root is not None):
            curr_node = root
        else:
            curr_node = self.getRoot()
        if(not self.empty()):
            while(curr_node.getRight() is not None):
                curr_node = curr_node.getRight()
        return curr_node

    def getMin(self, root = None):
        if(root is not None):
            curr_node = root
        else:
            curr_node = self.getRoot()
        if(not self.empty()):
            curr_node = self.getRoot()
            while(curr_node.getLeft() is not None):
                curr_node = curr_node.getLeft()
        return curr_node

    def empty(self):
        if self.root is None:
            return True
        return False

    def __InOrderTraversal(self, curr_node):
        nodeList = []
        if curr_node is not None:
            nodeList.insert(0, curr_node)
            nodeList = nodeList + self.__InOrderTraversal(curr_node.getLeft())
            nodeList = nodeList + self.__InOrderTraversal(curr_node.getRight())
        return nodeList

    def getRoot(self):
        return self.root

    def __isRightChildren(self, node):
        if(node == node.getParent().getRight()):
            return True
        return False

    def __reassignNodes(self, node, newChildren):
        if(newChildren is not None):
            newChildren.setParent(node.getParent())
        if(node.getParent() is not None):
            if(self.__isRightChildren(node)):
                node.getParent().setRight(newChildren)
            else:
                node.getParent().setLeft(newChildren)

    def traversalTree(self, traversalFunction = None, root = None):
        if(traversalFunction is None):
            return self.__InOrderTraversal(self.root)
        else:
            return traversalFunction(self.root)

    def __str__(self):
        list = self.__InOrderTraversal(self.root)
        str = ""
        for x in list:
            str = str + " " + x.getLabel().__str__()
        return str

def InPreOrder(curr_node):
    nodeList = []
    if curr_node is not None:
        nodeList = nodeList + InPreOrder(curr_node.getLeft())
        nodeList.insert(0, curr_node.getLabel())
        nodeList = nodeList + InPreOrder(curr_node.getRight())
    return nodeList

# Función para probar las clases
def testBinarySearchTree():
    '''
    Ejemplo
                  8
                 / \
                3   10
               / \    \
              1   6    14
                 / \   /
                4   7 13 
    '''

    '''
    Ejemplo luego del borrado
                  7
                 / \
                1   4

    '''
    # Instancia del árbol binario de búsqueda
    t = BinarySearchTree()
    #Insertamos los elementos
    t.insert(8)
    t.insert(3)
    t.insert(6)
    t.insert(1)
    t.insert(10)
    t.insert(14)
    t.insert(13)
    t.insert(4)
    t.insert(7)

    print(t.__str__())

    if(t.getNode(6) is not None):
        print("El elemento 6 existe")
    else:
        print("El elemento 6 no existe")

    if(t.getNode(-1) is not None):
        print("El elemento -1 existe")
    else:
        print("El elemento -1 no existe")
    
    if(not t.empty()):
        print(("Valor Max: ", t.getMax().getLabel()))
        print(("Valor Min: ", t.getMin().getLabel()))
    
    t.delete(13)
    t.delete(10)
    t.delete(8)
    t.delete(3)
    t.delete(6)
    t.delete(14)

    # Obtenemos todos los elementos del árbol en preorden
    list = t.traversalTree(InPreOrder, t.root)
    for x in list:
        print(x)

if __name__ == "__main__":
    testBinarySearchTree()


8 3 1 6 4 7 10 14 13
El elemento 6 existe
El elemento -1 no existe
('Valor Max: ', 14)
('Valor Min: ', 1)
7
1
4

Como pueden observar, el resultado es satisfactorio. Nos muestra el árbol. Lo elementos los cuales solicitamos su estado de existencia. El valor más alto y el más bajo. Y el árbol luego de eliminar algunos nodos.

Estructura de datos es un tema muy interesante e importante, por ello tratare de darle más espacio en el blog.

¿Alguna duda? ¿Alguna sugerencia? Deja tu comentario.

Mi nombre es Luis, y fue un placer compartir mis conocimientos con todos ustedes :D.
Seguir Leyendo

lunes, 16 de julio de 2018

Introducción a las Redes Neuronales: Parte #1 - Métodos de Aprendizaje

En este articulo nos centraremos en conocer los métodos de aprendizaje para el entrenamiento de las redes neuronales.

Como siempre, trata de explicarlo de manera clara  sencilla, sin tantas expresiones matemáticas. Claro, es inevitable tener que colocar más de 3 formulas, ya que es muy importante conocer los procesos matemáticos de las redes neuronales. Sabes que si tienes alguna duda, puedes dejar un comentario, y con gusto responderé.

Imagen relacionada

1.3 Métodos de Aprendizaje

Ya hemos vistos cual es la estructura de una red neuronal, vimos cuales eran sus capas y las funciones que realiza una neurona para recibir y transmitir información.

Las redes neuronales buscan imitar el proceso por el que pasa nuestro cerebro para aprender e interpretar los datos que se le den como entrada.

Igual que en el mundo físico, hay diferentes maneras en la que una red neuronal puede aprender. 

Una red neuronal debe aprender a calcular la salida correcta para un vector de entrada de un conjunto de ejemplos. Este proceso de aprendizaje los denominamos "proceso de entrenamiento o acondicionamiento". 

El aprendizaje de una red neuronal significa "adaptación de los pesos". Por lo tanto podemos decir que el aprendizaje es el proceso por el cual una red neuronal modifica sus pesos en respuesta a una información de entrada. Los cambios que se producen durante el mismo se reducen a la destrucción, modificación y creación de conexiones entre las neuronas. En los modelos de redes neuronales artificiales, la creación de una nueva conexión implica que el peso de la misma pasa a tener un valor distinto de cero. De la misma manera, una conexión se destruye cuando su peso pasa a ser cero.

Cuando la red neuronal esta en proceso de aprendizaje, los pesos de las conexiones de la red sufren modificaciones, por lo tanto, se puede afirmar que este proceso ha terminado (la red ha aprendido) cuando los valores de los pesos permanecen estables.

Una generalización de la fórmula o regla para decir los cambios en los pesos es
la siguiente:

Peso Nuevo = Peso Viejo + Cambio de Peso

Matemáticamente esto es:

wij(t+1) = wij(t) + Δwij(t)

donde t hace referencia a la etapa de aprendizaje, wij(t+1) al peso nuevo y wij(t) al peso
viejo.

Hay dos métodos de aprendizaje los cuales son los más importantes:
  • Aprendizaje Supervisado
  • Aprendizaje no supervisado

1.3.1 Aprendizaje Supervisado

El aprendizaje supervisado se caracteriza porque el proceso de aprendizaje se
realiza mediante un entrenamiento controlado por un agente externo (supervisor,
maestro) que determina la respuesta que debería generar la red a partir de una entrada
determinada. El supervisor controla la salida de la red y en caso de que ésta no coincida
con la deseada, se procederá a modificar los pesos de las conexiones, con el fin de
conseguir que la salida obtenida se aproxime a la deseada.

En este tipo de aprendizaje se suelen considerar, a su vez, tres formas de llevarlo
a cabo, que dan lugar a los siguientes aprendizajes supervisados:

  1. Aprendizaje por corrección de error
  2. Aprendizaje por refuerzo
  3. Aprendizaje estocástico

1.3.1.1 Aprendizaje por corrección de error 

Consiste en ajustar los pesos de las conexiones de la red en función de la
diferencia entre los valores deseados y los obtenidos a la salida de la red, es decir, en
función del error cometido en la salida.

Un ejemplo de este tipo de algoritmos lo constituye la regla de aprendizaje del
Perceptron, utilizada en el entrenamiento de la red del mismo nombre que desarrolló
Rosenblatt en 1958 [Rosenblatt 58]. Esta es una regla muy simple, para cada neurona en
la capa de salida se le calcula la desviación a la salida objetivo como el error, δ. El cual
luego se utiliza para cambiar los pesos sobre la conexión de la neurona precedente. El
cambio de los pesos por medio de la regla de aprendizaje del Perceptron se realiza
según la siguiente regla:

Δwij = σ*outj*(aqi – outi);

donde: aqi es la salida deseada/objetivo de la neurona de salida Ni, δi = (aqi – outi) la
desviación objetivo de la neurona Ni y σ el aprendizaje.

La salida de la neurona Nj (outj) se utiliza, porque este valor influye en la entrada
global y, por ende, en la activación y luego en la salida de la neurona Ni. Esto es
semejante a un “efecto en cadena”.

Otro algoritmo muy conocido y que pertenece a esta clasificación es la regla de
aprendizaje Delta o regla del mínimo error cuadrado (LMS Error: Least Mean Squared
Error), que también utiliza la desviación a la salida objetivo, pero toma en consideración
a todas las neuronas predecesoras que tiene la neurona de salida. Esto permite
cuantificar el error global cometido en cualquier momento durante el proceso de
entrenamiento de la red, lo cual es importante, ya que cuanto más información se tenga
sobre el error cometido, más rápido se puede aprender. Luego el error calculado (δ) es
igualmente repartido entre las conexiones de las neuronas predecesoras.

Por último se debe mencionar la regla de aprendizaje de propagación hacia
atrás o de backpropagation, también conocido como regla LMS multicapa, la cual es
una generalización de la regla de aprendizaje Delta. Esta es la primer regla de
aprendizaje que permitió realizar cambios sobre los pesos en las conexiones de la capa
oculta.

1.3.1.2 Aprendizaje por refuerzo

Se trata de un aprendizaje supervisado, más lento que el anterior, que se basa en
la idea de no disponer de un ejemplo completo del comportamiento deseado, es decir, de
no indicar durante el entrenamiento exactamente la salida que se desea que proporcione
la red ante una determinada entrada.

En el aprendizaje por refuerzo la función del supervisor se reduce a indicar
mediante una señal de refuerzo si la salida obtenida en la red se ajusta a la deseada
(éxito = +1 o fracaso = -1), y en función de ello se ajustan los pesos basándose en un
mecanismo de probabilidades. Se podría decir que en este tipo de aprendizaje la función
del supervisor se asemeja más a la de un crítico (que opina sobre la respuesta de la red)
que a la de un maestro (que indica a la red la respuesta concreta que debe generar),
como ocurría en el caso de supervisión por corrección del error.

1.3.1.3 Aprendizaje estocástico

Consiste básicamente en realizar cambios aleatorios en los valores de los pesos
de las conexiones de la red y evaluar su efecto a partir del objetivo deseado y de
distribuciones de probabilidad.

En el aprendizaje estocástico se suele hacer una analogía en términos
termodinámicos, asociando a la red neuronal con un sólido físico que tiene cierto estado
energético. En el caso de la red, la energía de la misma representaría el grado de
estabilidad de la red, de tal forma que el estado de mínima energía correspondería a una
situación en la que los pesos de las conexiones consiguen que su funcionamiento sea el
que más se ajusta al objetivo deseado.

Según lo anterior, el aprendizaje consistiría en realizar un cambio aleatorio de
los valores de los pesos y determinar la energía de la red (habitualmente la función
energía es una función de Liapunov). Si la energía es menor después del cambio, es
decir, si el comportamiento de la red se acerca al deseado, se acepta el cambio; si, por el
contrario, la energía no es menor, se aceptaría el cambio en función de una determinada
y preestablecida distribución de probabilidades.

1.3.2 Aprendizaje no supervisado

Las redes con aprendizaje no supervisado (también conocido como
autosupervisado) no requieren influencia externa para ajustar los pesos de las
conexiones entre sus neuronas. La red no recibe ninguna información por parte del
entorno que le indique si la salida generada en respuesta a una determinada entrada es o
no correcta.

Estas redes deben encontrar las características, regularidades, correlaciones o
categorías que se puedan establecer entre los datos que se presenten en su entrada.
Existen varias posibilidades en cuanto a la interpretación de la salida de estas redes, que
dependen de su estructura y del algoritmo de aprendizaje empleado.

En algunos casos, la salida representa el grado de familiaridad o similitud entre
la información que se le está presentando en la entrada y las informaciones que se le han
mostrado hasta entonces (en el pasado). En otro caso, podría realizar una clusterización
(clustering) o establecimiento de categorías, indicando la red a la salida a qué categoría
pertenece la información presentada a la entrada, siendo la propia red quien debe
encontrar las categorías apropiadas a partir de las correlaciones entre las informaciones
presentadas.

En cuanto a los algoritmos de aprendizaje no supervisado, en general se suelen
considerar dos tipos, que dan lugar a los siguientes aprendizajes:
  1. Aprendizaje hebbiano.
  2. Aprendizaje competitivo y comparativo.

1.3.1.1 Aprendizaje hebbiano

Esta regla de aprendizaje es la base de muchas otras, la cual pretende medir la
familiaridad o extraer características de los datos de entrada. El fundamento es una
suposición bastante simple: si dos neuronas Ni y Nj toman el mismo estado
simultáneamente (ambas activas o ambas inactivas), el peso de la conexión entre ambas
se incrementa.

Las entradas y salidas permitidas a la neurona son: {-1, 1} o {0, 1} (neuronas
binarias). Esto puede explicarse porque la regla de aprendizaje de Hebb se originó a
partir de la neurona biológica clásica, que solamente puede tener dos estados: activa o
inactiva.

1.3.1.2 Aprendizaje competitivo y comparativo

Se orienta a la clusterización o clasificación de los datos de entrada. Como
característica principal del aprendizaje competitivo se puede decir que, si un patrón
nuevo se determina que pertenece a una clase reconocida previamente, entonces la
inclusión de este nuevo patrón a esta clase matizará la representación de la misma. Si el
patrón de entrada se determinó que no pertenece a ninguna de las clases reconocidas
anteriormente, entonces la estructura y los pesos de la red neuronal serán ajustados para
reconocer la nueva clase.

Seguir Leyendo
Powered by Blogger .