domingo, 13 de dezembro de 2009

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.

2 comentários:

  1. Seu algoritmo tem um problema. Às vezes são gerados grupos vazios, causando assim problemas na hora de recalcular os centróides.

    ResponderEliminar
  2. É verdade. Essa questão é abordada e resolvida noutro post. Veja a resposta no post de 14 de Dezembro de 2009, chamado Problema 9.10.

    ResponderEliminar