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:

view sourceprint?

001.import math

002.import random

003.import cTurtle

004. 

005.def dist_euclidiana(p1,p2):

006.    """

007.    Distância euclidiana entre dois pontos. Os pontos são tuplos n-dimensionais.

008.    """

009.    soma =0

010.    for i in range(len(p1)):

011.        soma = soma + (p2[i] - p1[i])**2

012.    distancia = math.sqrt(soma)

013.    return distancia

014.     

015.def centroide(pontos):

016.    """

017.    Calcula o centróide de um conjunto de pontos n-dimensionais.

018.    Entrada = uma lista de pontos. Saida = tuplo

019.    Assume a existência de pelo menos um ponto!!

020.    """

021.    cent = [sum(ponto)/len(ponto) for ponto in zip(*pontos)]

022.    return tuple(cent)

023. 

024.def cria_dicio_dados(ficheiro):

025.    """

026.    Lê as coordenadas dos pontos a partir de um ficheiro.

027.    Incorpora num dicionário.

028.    """

029.    f_in = open(ficheiro,'r')

030.    dicio_dados = dict()

031.     

032.    chave = 0

033.    linha = f_in.readline()

034.    while linha != '': # EOF?

035.        chave = chave + 1

036.        tuplo = tuple([int(valor) for valor in linha[:-1].split()])

037.        dicio_dados[chave] = tuplo

038.        linha = f_in.readline()

039.    f_in.close()

040.    return dicio_dados

041. 

042.def cria_centroides(k,dicio_dados):

043.    """

044.    Devolve uma lista com k pontos distintos como centróides.

045.    """

046.    centroides = []

047.    chaves_centroides = []

048.    for i in range(k):

049.        chave_alea = random.randint(1,len(dicio_dados))

050.        while chave_alea  in chaves_centroides:

051.            chave_alea = random.randint(1,len(dicio_dados))

052.        centroides.append(dicio_dados[chave_alea])

053.        chaves_centroides.append(chave_alea)

054.    return centroides

055. 

056.def cria_agrupamentos(k,centroides,dicio_dados,repete):

057.    """

058.    k = número de agrupamentos

059.    centroides = lista de centroides inicial

060.    dicio_dados = os dados organizados num dicionário {1:(...), 2: (...),...}

061.    repete = número de passagens

062.    Os dados podem ser n-dimensionais. Cada ponto é um tuplo.

063.    """

064.    for passo in range(repete):

065.        print "----- Passagem:\t {0}\t-----".format(passo)

066.        # Cria contentor para os agrupamentos

067.        agrupamentos = []

068.        for conta in range(k):

069.            agrupamentos.append([])

070.             

071.        # Determina agrupamento para cada dado

072.        for chave in dicio_dados:

073.            distancias = []

074.            for indice_agrupamento in range(k):

075.                dist = dist_euclidiana(dicio_dados[chave],centroides[indice_agrupamento])

076.                distancias.append(dist)

077.            menor = min(distancias)

078.            indice = distancias.index(menor)

079.             

080.            agrupamentos[indice].append(chave)

081. 

082.        # Actualiza centróides

083.        for indice in range(k):

084.            agrupa = [dicio_dados[chave] for chave in agrupamentos[indice]]

085.            centroides[indice] = centroide(agrupa)

086.        # Mostra resultado

087.        mostra_agrupamentos(agrupamentos,dicio_dados)

088.         

089.    return agrupamentos

090. 

091.def mostra_agrupamentos(agrupamentos,dicio_dados):

092.    """

093.    Mostra os agrupamentos.

094.    """

095.    for indice,agrupamento in enumerate(agrupamentos):

096.        print "AGRUPAMENTO %d: " % (indice + 1)

097.        for chave in agrupamento:

098.            print dicio_dados[chave],

099.        print

100. 

101.def main(ficheiro,numero_grupos):

102.    """

103.    Faz a análise de agrupamentos segundo K-médias.

104.    """

105.    dicio_dados = cria_dicio_dados(ficheiro)

106.    centroides = cria_centroides(numero_grupos, dicio_dados)

107.    agrupamentos = cria_agrupamentos(numero_grupos,centroides, dicio_dados,3)

108. 

109. 

110.if __name__ =='__main__':

111.    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.