k-Médias

O algoritmo k-médias é um algoritmo de agrupamento conceptual. De um modo simples, dado um conjunto de objectos, descritos por atributos, como os dividir em k grupos por forma que os objectos de um dado grupo são maximanente semelhantes entre si e minimamente semelhantes em relação aos objectos dos outros grupos.


Computacionalmente, o algoritmo K-Médias desdobra-se nos seguintes passos:


(1) Escolhe o número, K, de agrupamentos
(2) Escolhe, de modo aleatório, K pontos para servirem de centróides iniciais de cada um dos K agrupamentos
(3) Repetir os seguintes passos:

--> (3a) Afectar cada ponto ao agrupamento de cujo centróide se encontrar mais perto

-->(3b) Recalcular os centróides

(4) Mostrar os K agrupamentos


Posto isto, o código:

import math
import random
import cTurtle

def dist_euclidiana(p1,p2):
    """
    Distância euclidiana entre dois pontos. Os pontos são tuplos n-dimensionais.
    """
    soma =0
    for i in range(len(p1)):
        soma = soma + (p2[i] - p1[i])**2
    distancia = math.sqrt(soma)
    return distancia
    
def centroide(pontos):
    """
    Calcula o centróide de um conjunto de pontos n-dimensionais.
    Entrada = uma lista de pontos. Saida = tuplo
    Assume a existência de pelo menos um ponto!!
    """
    cent = [sum(ponto)/len(ponto) for ponto in zip(*pontos)]
    return tuple(cent)

def cria_dicio_dados(ficheiro):
    """
    Lê as coordenadas dos pontos a partir de um ficheiro.
    Incorpora num dicionário.
    """
    f_in = open(ficheiro,'r')
    dicio_dados = dict()
    
    chave = 0
    linha = f_in.readline()
    while linha != '': # EOF?
        chave = chave + 1
        tuplo = tuple([int(valor) for valor in linha[:-1].split()])
        dicio_dados[chave] = tuplo
        linha = f_in.readline()
    f_in.close()
    return dicio_dados

def cria_centroides(k,dicio_dados):
    """ 
    Devolve uma lista com k pontos distintos como centróides.
    """
    centroides = []
    chaves_centroides = []
    for i in range(k):
        chave_alea = random.randint(1,len(dicio_dados))
        while chave_alea  in chaves_centroides:
            chave_alea = random.randint(1,len(dicio_dados))
        centroides.append(dicio_dados[chave_alea])
        chaves_centroides.append(chave_alea)
    return centroides

def cria_agrupamentos(k,centroides,dicio_dados,repete):
    """
    k = número de agrupamentos
    centroides = lista de centroides inicial
    dicio_dados = os dados organizados num dicionário {1:(...), 2: (...),...}
    repete = número de passagens
    Os dados podem ser n-dimensionais. Cada ponto é um tuplo.
    """
    for passo in range(repete):
        print "----- Passagem:\t {0}\t-----".format(passo)
        # Cria contentor para os agrupamentos
        agrupamentos = []
        for conta in range(k):
            agrupamentos.append([])
            
        # Determina agrupamento para cada dado
        for chave in dicio_dados:
            distancias = []
            for indice_agrupamento in range(k):
                dist = dist_euclidiana(dicio_dados[chave],centroides[indice_agrupamento])
                distancias.append(dist)
            menor = min(distancias)
            indice = distancias.index(menor)
            
            agrupamentos[indice].append(chave)

        # Actualiza centróides
        for indice in range(k):
            agrupa = [dicio_dados[chave] for chave in agrupamentos[indice]]
            centroides[indice] = centroide(agrupa)
        # Mostra resultado
        mostra_agrupamentos(agrupamentos,dicio_dados)
        
    return agrupamentos

def mostra_agrupamentos(agrupamentos,dicio_dados):
    """
    Mostra os agrupamentos.
    """
    for indice,agrupamento in enumerate(agrupamentos):
        print "AGRUPAMENTO %d: " % (indice + 1)
        for chave in agrupamento:
            print dicio_dados[chave],
        print

def main(ficheiro,numero_grupos):
    """
    Faz a análise de agrupamentos segundo K-médias.
    """
    dicio_dados = cria_dicio_dados(ficheiro)
    centroides = cria_centroides(numero_grupos, dicio_dados)
    agrupamentos = cria_agrupamentos(numero_grupos,centroides, dicio_dados,3)


if __name__ =='__main__':
    main('/tempo/data/notasmt1.txt',5) # no seu caso o local do ficheiro pode ser diferente!!!

O leitor deve estar atento à representação dos objectos! Em particular:

(a) os agrupamentos são guardados numa lista, sendo que cada agrupamento é descrito pela lista das chaves dos objectos;

(b) os centróides são guardados numa lista e descritos pelos atributos dos objectos;

(c) os objectos estão guardados num dicionário, sendo a chaves inteiros e os valores os atributos do objecto.
(d) durante a computação é usada uma lista com as distâncias de um objecto a cada um dos centróides.