Fundamentos de Machine Learning (Parte 2)

Algoritmos de agrupamiento

Estos algoritmos buscan agrupar elementos de un arreglo, busca características similares en los elementos e intenta agruparlos basandose en dichas características.
Lógicamente, estos algoritmos son especialmente de utilidad en los casos en los que no es sencillo un agrupamiento de los datos, tal vez por la gran cantidad de los mismos, porque son muy variables entre sí o porque sus características similares no son tan evidentes.
Por ejemplo, en redes sociales se utiliza este tipo de algoritmos para agrupar personas que aparentemente son muy diferentes, tal vez ni se conocen y se arman nichos a los que puede interesarle el mismo tipo de cosas, De esa manera se les envía publicidad que puede motivarlos a comprar.
En escenarios con grandes cantidades de datos, los algoritmos de agrupamiento también nos permiten tener una idea de la forma en la que los datos en conjunto están estructurados.

Agrupamiento jerárquico

Toma los puntos (elemanto, datos) más cercanos, los agrupa en un cluster. Posteriormente toma este cluster y ubica el punto más cercano a dicho cluster. Finalmente, crea un cluster nuevo formado por el cluster del paso anterior junto con el punto más cercano encontrado en este último paso. Este algoritmo se repite hasta que ya queda un sólo "supercluster" que incorpora a todos los puntos o datos.
El resultado de este algoritmo es un dendograma. Esta gráfica señala o describe la relación de cada individuo, dato o elemente, con respecto al grupo o supercluster como tal.

Aspectos que se tienen en cuenta en el agrupamiento jerárquico

• Se parte del supuesto de que todos los puntos con los que se inicia, corresponden a un dato único e individual. En otras palabras, el punto de inicio es un set de datos sin clusterizar o agrupar.
• Se debe determinar la forma en la que se calculará la distancia entre los puntos. (euclidiana, de Manhattan, etc.) El tipo de proyecto o lo que se quiere encontrar, determinará el tipo de cáculo para la distancia que se utilizará.
• Qué tipo de criterio se usará para enlazar los puntos. Es decir, a partir de la segunda iteración, deberemos calcular la distancia del cluster que formamos en el primer paso al siguiente punto más cercano. Sin embargo, si notamos bien, un cluster es un grupo de datos, gráficamente sería un grupo de coordenadas cartesianas, entonces nos preguntamos, de este grupo de coordenadas, ¿cuál será la que usarémos como punto de referencia a partir del cual calcular la distancia? a eso nos referimos al decir, "'¿qué tipo de criterio se usará para enlazar los puntos?". Para responder esta pregunta, tenemos 3 opciones de criterio.
  • Single Linkage, consiste en tomar los puntos más cercanos.
  • Complete Linkage, consiste en tomar los puntos más lejanos
  • Average Linkage, consiste en encontrar una coordenada promedio y usar esta coordanda como punto referencia para el cluster, en otras palabras el punto punto representativo a partir del cual se calculará la distancia.

Agrupamiento K means

Este proceso está bajo el contexto de aprendizaje no supervisado. En el agrupamiento K means, se tiene un set de datos del que se desea conocer cómo los features vectores se correlacionan entre sí. Este ejercicio permite entre otra cosas, encontrar grupos de personas con intereses similares, automatizar el control de calidad de granos de café, etc.

El proceso consiste en seleccionar el número de grupos (k) en los que se desea agrupar el dataset.
Por cada k, se seleccionan k puntos del dataset que serán los centroides iniciales. Esta selección de centroides, es arbitraria y sirve nada más que, como punto de partida inicial de la ejecución del algoritmo. Se asume que, cada centroide corresponde a un grupo diferente....
Con el valor de k, es decir, numero de grupos en los que se agrupará y los k centroides elegidos al azar, se inicia un proceso iterativo.

1. Se calcula la distancia de cada punto del dataset a los centroides seleccionados.
2. Una vez calculadas las distancias a cada centroide, por cada punto, se toma la distancia más cerca a un centroide y se asigna dicho punto como parte del grupo al que el centroide pertenece.
3. Teniendo los puntos del dataset, asignados a un grupo, se calcula la media de los datos de cada grupo, obtendremos k medias y estas medias serán nuestros nuevos centroides.
4. Repetimos los pasos 1 al 3 hasta que los centroides ya no cambien de una iteración a otra. ### Aspectos que se tienen en cuenta en el agrupamiento K means Con relación a la selección del valor k. En general, ese valor (k) es arbitrario, sin embargo, para una mayor precisión y efectividad del algoritmo, se recomienda seleccionar este número basado en la intuición que viene de entender con claridad la lógica del negocio. Al ser un algoritmo iterativo y que calcula la distancia por cada punto, es computacionalmente costoso. Teniendo en cuenta lo anterior, no se recomienda ejecutar el algoritmo sobre todo el dataset. Tal vez es suficiente utilizar una muestra representativa y por infererencia, hacer una generalización para toda la población.

import math
from functools import reduce

class Node:
    def __init__(self, coordinates, children, distance):
        self.coordinates = coordinates
        self.children = children
        self.distance = distance

    def addChildren (self, children):
        self.children = children

class Coordinate:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def calcEuclidianDistanceTo(self, anotherCoordinate):
        a = (anotherCoordinate.x - self.x) ** 2
        b = (anotherCoordinate.y - self.y) ** 2
        return math.sqrt(a + b)

def avg(l): 
    avg = reduce(lambda x, y: x + y, l) / len(l)
    return avg

def clustering(dataSet):
    if (len(dataSet) == 1) :
        return dataSet
    else :
        lowest = None
        i = 0
        index1 = None
        index2 = None
        for element1 in dataSet:
            j = 0
            for element2 in dataSet:
                currentDistance = element1.coordinates.calcEuclidianDistanceTo(element2.coordinates)
                if ((lowest != None and lowest > currentDistance) or lowest == None):
                    index1 = i
                    index2 = j
                    lowest = currentDistance
                j = j + 1
            i = i + 1
        newX = avg([ dataSet[index1].coordinates.x, dataSet[index2].coordinates.x ])
        newY = avg([ dataSet[index1].coordinates.y, dataSet[index2].coordinates.y ])
        newCoordinates = Coordinate(newX, newY)
        newNode = Node(newCoordinates, [ dataSet[index1], dataSet[index2] ], lowest)
        del dataSet[index1]
        del dataSet[index2]
        dataSet.append(newNode)
        return clustering(dataSet)

def main():
    coord1 = Coordinate(1.0, 1.0)
    coord2 = Coordinate(2.0, 2.0)
    coord3 = Coordinate(5.0, 5.0)
    coord4 = Coordinate(8.0, 8.0)
    coord5 = Coordinate(10.0, 10.0)
    node1 = Node(coord1, None, None)
    node2 = Node(coord2, None, None)
    node3 = Node(coord3, None, None)
    node4 = Node(coord4, None, None)
    node5 = Node(coord5, None, None)
    dataSet = [node1, node2, node3, node4, node5]
    cluster = clustering(dataSet)

if __name__ == "__main__":
    main()