Problema 9.10

A questão dos agrupamentos vazios obriga a algum trabalho de alteração do código. Mas o que importa mais é definir a estratégia para lidar com esses agrupamentos. Uma solução simples seria deixar que existam.Mas não é isso que queremos! Então o que fazer? Bom, uma solução razoável será escolher o pior elemento de todo o conjunto de pontos. E qual é o pior? Começamos por calcular o pior dentro de cada agrupamento: o ponto mais distante ao respectivo centróide. De entre estes pontos vamos optar, uma vez mais, pelo mais distante. Esse elemento é retirado do seu agrupamento e é colocado no agrupamento vazio, passando a ser o seu centróide.

No código abaixo é fácil identificar as novas operações e a parte do código que foi alterada.

import math
import random
import cTurtle
import operator

def dist_euclidiana(p1,p2):
    return math.sqrt(sum([(p[1] - p[0])**2 for p in zip(p1,p2)]))

def centroide(pontos):
    """
    Calcula o centróide de um conjunto de pontos n-dimensionais.
    Entrada = uma lista de pontos.
    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()
    return dicio_dados

# por localização
def cria_dicio_dados_terramoto(ficheiro):
    """
    Extrai os dados do ficheiro e constrói o dicionário.
    """
    f_in = open(ficheiro,'r')
    dicio_dados = dict()
    
    chave = 0
    linha = f_in.readline()
    while linha != '': # EOF?
        chave = chave + 1
        latitude = float(linha[:-1].split()[3])
        longitude = float(linha[:-1].split()[4])
        dicio_dados[chave] = (longitude,latitude)
        linha = f_in.readline()
    return dicio_dados

def cria_centroides(k,dicio_dados):
    """ 
    Devolve uma lista com k pontos distintos como centróides.
    Apenas com intensidade...
    """
    centroides = []
    conta_centroides = 0
    chaves_centroides = []
    while conta_centroides < k:
        chave_alea = random.randint(1,len(dicio_dados))
        if chave_alea not in chaves_centroides:
            centroides.append(dicio_dados[chave_alea])
            chaves_centroides.append(chave_alea)
            conta_centroides = conta_centroides + 1
    return centroides

#-- alterado por causa dos vazios
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)
            
        # agrupamentos vazios: o elemento de um agrupamento não vazio de
        # maior distância é movido
        if agrupamento_vazio(agrupamentos):
            agrupamentos = consolida_agrupamentos(centroides,agrupamentos,dicio_dados)
        
        # 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 agrupamento_vazio(agrupa):
    """ Algum agrupamento vazio."""
    return any([len(elem) == 0 for elem in agrupa])

def indices_agrupa_vazios(agrupa):
    """ lista de índices dos agrupamentos vazios."""
    return [indice for indice in range(len(agrupa)) if len(agrupa[indice]) == 0]

def indice_max_dist(centroides, agrupamentos, dicio_dados):
    """ Determina o agrupamento e o índice do elemento mais distante do centroide
    considerando todos os agrupamentos.
    """
    max_dist = []
    for indice,agrupa in enumerate(agrupamentos):
        if len(agrupa) > 0:
            lista_dist = []
            for elemento in agrupa:
                lista_dist.append((elemento,dist_euclidiana(centroides[indice], dicio_dados[elemento])))
            lista_dist.sort(key=operator.itemgetter(1), reverse = True)
            maior = (indice,lista_dist[0][0])
            max_dist.append(maior)
    max_dist.sort(key=operator.itemgetter(1),reverse=True)
    return max_dist[0] # -- (indice agrupamento, indice elemento)
            
        

def consolida_agrupamentos(centroides, agrupamentos,dicio_dados):
    """ Devolve agrupamentos sem elementos vazios."""
    indice_vazios = indices_agrupa_vazios(agrupamentos)

    while indice_vazios:

        # qual o elemento à distância máxima do seu centróide?
        # qual o máximo dos máximos?
        maximo = indice_max_dist(centroides,agrupamentos,dicio_dados)
        # coloca o máximo dos máximos num agrupamento vazio
        agrupamentos[indice_vazios[0]].append(maximo[1])
        # retira do agrupamento origem
        agrupamentos[maximo[0]].remove(maximo[1])
        indice_vazios = indice_vazios[1:]
    return agrupamentos
    

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)