Algoritmo

A continuación se presenta el pseudo-código de K-medias.

El código principal kmedias recibe dos parámetros, los datos que queremos separar, y k que es la cantidad de grupos.  Las sentencias que arrancan con el símbolo #, son los comentarios respectivos de cada una de las diferentes partes del algoritmo.

function kmedias(data,k)
    # Calculo dimensión y cantidad de puntos de los datos recibidos.
    # La dimensión se corresponde con la cantidad de atributos que tienen los datos
    (dimension,cantidad_de_puntos) = obtener_tamano(data)
    centroides = []
    centroides_anterior = []
    # Se definen los centroides aleatoriamente
    # la variable dimensión es para que tengan la misma dimensión que los datos.
    for i=1:k
       push!(centroides,crear_punto_aleatorio(data))
       push!(centroides_anterior,vec(ones(dimension)*Inf))
    end

    while centroides_cambian(centroides,centroides_anterior)
        centroides_anterior = copiar(centroides)
        #Asigno puntos al centroide más cercano
        asignaciones = zeros(cantidad_de_puntos)
        for i=1:cantidad_de_puntos
            distancia_minima = Inf
            for j=1:k
                distancia_centroide = distancia( get_punto(data,i), centroides[j])
                if distancia_centroide < distancia_minima
                    distancia_minima    = distancia_centroide
                    asignacion          = j
                end
            end
            asignaciones[i] = asignacion
        end
        
        #Recalculo los centroides
        for j=1:k
            centroide_nuevo = vec(zeros(dimension))
            cantidad_puntos_cluster = 0
            cantidad_puntos_grupo= 0
            for i=1:length(asignaciones)
                if asignaciones[i] == j
                    cantidad_puntos_grupo = cantidad_puntos_grupo +1
                    centroide_nuevo = centroide_nuevo .+ get_punto(data,i)
                end
            end
           
            #calculo el promedio de los datos asignados al grupo j
            centroide_nuevo = centroide_nuevo / cantidad_puntos_grupo
            
            #actualizo el nuevo centroide
            centroides[j] = centroide_nuevo
        end
    end
    return centroides
end

La función distancia recibe dos puntos, y calcula la distancia euclídea entre ellos.

function distancia(p1, p2)
    dist = 0
    for i=1:length(p1)
       dist = dist + (p1[i]-p2[i])^2
    end
    # sqrt es una función que calcula la raíz cuadrada.
    return sqrt(dist)
end

La función centroides_cambian recibe el centroide actual y el centroide anterior, y calcula si los centroides son diferentes. A su vez, se establece una variable umbral que define el margen que se considera para saber si dos centroides son iguales.

function centroides_cambian(centroides_act,centroides_ant)
    umbral = 0.001
    for i=1:length(centroides_act)
        if (distancia(centroides_act[i],centroides_ant[i]) > umbral)
            return true
        end
    end
    return false
end