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.

view sourceprint?

001.import math

002.import random

003.import cTurtle

004.import operator

005. 

006.def dist_euclidiana(p1,p2):

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

008. 

009.def centroide(pontos):

010.    """

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

012.    Entrada = uma lista de pontos.

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

014.    """

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

016.    return tuple(cent)

017. 

018.def cria_dicio_dados(ficheiro):

019.    """

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

021.    Incorpora num dicionário.

022.    """

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

024.    dicio_dados = dict()

025.     

026.    chave = 0

027.    linha = f_in.readline()

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

029.        chave = chave + 1

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

031.        dicio_dados[chave] = tuplo

032.        linha = f_in.readline()

033.    return dicio_dados

034. 

035.# por localização

036.def cria_dicio_dados_terramoto(ficheiro):

037.    """

038.    Extrai os dados do ficheiro e constrói o dicionário.

039.    """

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

041.    dicio_dados = dict()

042.     

043.    chave = 0

044.    linha = f_in.readline()

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

046.        chave = chave + 1

047.        latitude = float(linha[:-1].split()[3])

048.        longitude = float(linha[:-1].split()[4])

049.        dicio_dados[chave] = (longitude,latitude)

050.        linha = f_in.readline()

051.    return dicio_dados

052. 

053.def cria_centroides(k,dicio_dados):

054.    """

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

056.    Apenas com intensidade...

057.    """

058.    centroides = []

059.    conta_centroides = 0

060.    chaves_centroides = []

061.    while conta_centroides < k:

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

063.        if chave_alea not in chaves_centroides:

064.            centroides.append(dicio_dados[chave_alea])

065.            chaves_centroides.append(chave_alea)

066.            conta_centroides = conta_centroides + 1

067.    return centroides

068. 

069.#-- alterado por causa dos vazios

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

071.    """

072.    k = número de agrupamentos

073.    centroides = lista de centroides inicial

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

075.    repete = número de passagens

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

077.    """

078.    for passo in range(repete):

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

080.        # cria contentor para os agrupamentos

081.        agrupamentos = []

082.        for conta in range(k):

083.            agrupamentos.append([])

084.             

085.        # Determina agrupamento para cada dado

086.        for chave in dicio_dados:

087.            distancias = []

088.            for indice_agrupamento in range(k):

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

090.                distancias.append(dist)

091.            menor = min(distancias)

092.            indice = distancias.index(menor)

093.             

094.            agrupamentos[indice].append(chave)

095. 

096.        # Actualiza centróides

097.        for indice in range(k):

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

099.            centroides[indice] = centroide(agrupa)

100.             

101.        # agrupamentos vazios: o elemento de um agrupamento não vazio de

102.        # maior distância é movido

103.        if agrupamento_vazio(agrupamentos):

104.            agrupamentos = consolida_agrupamentos(centroides,agrupamentos,dicio_dados)

105.         

106.        # mostra resultado

107.        mostra_agrupamentos(agrupamentos,dicio_dados)

108.         

109.    return agrupamentos

110. 

111.def mostra_agrupamentos(agrupamentos,dicio_dados):

112.    """

113.    Mostra os agrupamentos.

114.    """

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

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

117.        for chave in agrupamento:

118.            print dicio_dados[chave],

119.        print

120. 

121.def agrupamento_vazio(agrupa):

122.    """ Algum agrupamento vazio."""

123.    return any([len(elem) == 0 for elem in agrupa])

124. 

125.def indices_agrupa_vazios(agrupa):

126.    """ lista de índices dos agrupamentos vazios."""

127.    return [indice for indice in range(len(agrupa)) if len(agrupa[indice]) == 0]

128. 

129.def indice_max_dist(centroides, agrupamentos, dicio_dados):

130.    """ Determina o agrupamento e o índice do elemento mais distante do centroide

131.    considerando todos os agrupamentos.

132.    """

133.    max_dist = []

134.    for indice,agrupa in enumerate(agrupamentos):

135.        if len(agrupa) > 0:

136.            lista_dist = []

137.            for elemento in agrupa:

138.                lista_dist.append((elemento,dist_euclidiana(centroides[indice], dicio_dados[elemento])))

139.            lista_dist.sort(key=operator.itemgetter(1), reverse = True)

140.            maior = (indice,lista_dist[0][0])

141.            max_dist.append(maior)

142.    max_dist.sort(key=operator.itemgetter(1),reverse=True)

143.    return max_dist[0] # -- (indice agrupamento, indice elemento)

144.             

145.         

146. 

147.def consolida_agrupamentos(centroides, agrupamentos,dicio_dados):

148.    """ Devolve agrupamentos sem elementos vazios."""

149.    indice_vazios = indices_agrupa_vazios(agrupamentos)

150. 

151.    while indice_vazios:

152. 

153.        # qual o elemento à distância máxima do seu centróide?

154.        # qual o máximo dos máximos?

155.        maximo = indice_max_dist(centroides,agrupamentos,dicio_dados)

156.        # coloca o máximo dos máximos num agrupamento vazio

157.        agrupamentos[indice_vazios[0]].append(maximo[1])

158.        # retira do agrupamento origem

159.        agrupamentos[maximo[0]].remove(maximo[1])

160.        indice_vazios = indice_vazios[1:]

161.    return agrupamentos

162.     

163. 

164.def main(ficheiro,numero_grupos):

165.    """

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

167.    """

168.    dicio_dados = cria_dicio_dados(ficheiro)

169.    centroides = cria_centroides(numero_grupos, dicio_dados)

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