Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como implementar um programa para checar a moda de elementos de um vetor?

+1 voto
24 visitas
perguntada Jun 20 em Ciência da Computação por João Gabriel Souza (76 pontos)  
republicada Jun 23 por João Gabriel Souza

Implemente na linguagem de sua preferência a versão força bruta do problema e a versão transforme e conquiste. Para versão transforme e conquiste, utilize o método de pré-sorting. Compare a complexidade dos algoritmos teoricamente usando a análise assintótica e empiricamente através de gráficos.

Compartilhe

1 Resposta

+1 voto
respondida Jun 20 por João Gabriel Souza (76 pontos)  
editado Jun 23 por João Gabriel Souza

Introdução

A moda é uma das medidas de tendência central de um conjunto de dados, tal como a média e mediana. Esta pode ser definida em moda amostral e populacional.

A moda amostral de um conjunto de dados trata do valor de que ocorre com maior frequência, ou mais comum, na série de dados. A moda amostral única como a média e a mediana, podem existir mais de uma moda e um um conjunto de dados. Uma série de dados que possui duas moda é chamada de bimodal, caso a série possua várias modas, esta é chamada de multimodal.

Já a moda populacional de uma distribuição de probabilidade discreta é o valor \(x\), em que a função massa de probabilidade atinge o valor máximo. Em outras palavras, é o valor que é mais provável de ser amostrado. Moda populacional de uma distribuição de probabilidade contínua é o valor \( x\) , em que a função densidade de probabilidade atinge o valor máximo. Em outras palavras, é o valor que está no pico. Moda populacional também não é necessariamente única, uma vez que a função massa de probabilidade ou a função densidade de probabilidade podem ter o mesmo valor máximo em vários pontos \( x_{1},x_{2}\dots\). O caso extremo ocorre nas distribuições uniformes, em que todos os valores ocorrem com igual frequência. No caso de a sequência de dados possuir todos seus elementos diferentes não há moda na série.

Força Bruta
A força bruta é um procedimento direto para resolver um problema tendo como base a definição deste problema e os conceitos diretamente envolvidos. Na ciência da computação, busca por força bruta ou busca exaustiva, também conhecido como gerar e testar, é uma técnica de solução de problemas trivial, porém muito geral que consiste em enumerar todos os possíveis candidatos da solução e checar cada candidato para saber se ele satisfaz o enunciado do problema.

Para aplicar busca por força bruta para uma classe específica de problemas, é preciso implementar quatro procedimentos, sendo estes: primeiro, próximo, válido, e saída. Estes procedimentos devem ter como parâmetro os dados \(P\) para a instância do problema que será resolvido, e deve fazer o seguinte:

  1. primeiro \((P)\): gera o primeiro candidato à solução de \(P\).
  2. próximo \((P, C)\): gera o próximo candidato de \(P\) depois de \(C\).
  3. válido \((P, C)\): checa se o candidato \(C\) é a solução de \(P\).
  4. saída \((P, C)\): usa a solução \(C\) de \(P\) como for conveniente para a aplicação.

O procedimento próximo também deve dizer quando não há mais candidatos à \(P\), após o \(C\) atual. Uma maneira conveniente de fazer isto é retornando um "candidato nulo", um valor de dados comum \(Λ\) que é distinto de qualquer outro candidato real. Da mesma maneira primeiro deve retornar \(Λ\) se não houver nenhum candidato para a instância \(P\).

O código Força Bruta em Python para encontrar a moda de um sequência de dados segue abaixo.

Em primeiro plano importa-se a biblioteca \(numpy\), na qual será utilizado algumas funções.

import numpy as np

A priori defini-se a função moda. Como recurso utiliza-se o recurso \(empty\) da biblioteca \(numpy\). Esse recurso preenche um array com um shapedefinido e com o formato dos elementos também pré-definido. Neste caso o formato float64 representam os números reais (\(\mathbb{R}\)). O shape representará o valor da sequência e sua freqüência de aparição neste conjunto de dados.

def moda(x):
    newrow = np.empty((1, 2), dtype='float64')
    newrow[0,] = [x[0], 0]
    i = 0
    maximo = 0
    vmaximo = []

No segundo plano o código irá realizar a operação em si. Primeiro, este, percorre a sequência em relação ao shape de \(newrow\). Depois percorre em relação ao comprimento da sequência guardando o valor do elemento e sua frequência. Caso o elemento seja igual ao próximo da iteração, este guarda no campo onde o array guarda a frequência.

while i < np.shape(newrow)[0]:
    j = 0
    while j < len(x):
        if newrow[i, 0] == x[j]:
            newrow[i, 1] = newrow[i, 1] + 1
            x.pop(j)
        else:
            if x[j] not in newrow[:, 0]:
                newrow = np.vstack([newrow, [x[j], 0]])
            j = j + 1
    if maximo <= newrow[i, 1]:
        if maximo == newrow[i, 1]:
            vmaximo = np.append(vmaximo, newrow[i, 0])
            print vmaximo
        else:
            vmaximo = newrow[i, 0]
            maximo = newrow[i, 1]
    i = i + 1
return (newrow, vmaximo, maximo)

O código retorna o array "\(newrow\)", o valor que representa a frequência máxima e a frequência máxima. Por último chama-se a função dada a sequência \(x\).

if __name__ == '__main__':
    x = [1, 2, 3, 1, 2, 3, 4, 3, 2, 1]
    out = moda(x)
    print(out)  

O resultado do algoritmo força bruta para encontrar a moda de um conjunto de dados segue abaixo.

(array([[ 1.,  3.],
       [ 2.,  3.],
       [ 3.,  3.],
       [ 4.,  1.]]), array([ 1.,  2.,  3.]), 3.0)

Ou seja, a sequência \(x\) possui como moda os números \(1, 2, 3\) com frequência de \(3\) vezes.

Transformação e Conquista (Pré-sorting) - Quicksort

Assim como Merge Sort, o Quicksort usa divisão e conquista, portanto ele é um algoritmo recursivo. O modo como o Quicksort usa divisão e conquista é um pouco diferente de como o Merge Sort faz. No Merge Sort, o passo da divisão não faz muita coisa, e todo o trabalho acontece na etapa de combinar. No Quicksort é o oposto: todo o trabalho acontece na etapa da divisão. Na verdade, o passo de combinar no Quicksort não faz absolutamente nada. Para mais informações sobre o algoritmo Merge Sort ver Post sobre maior variação positiva de uma sequência.

O quicksort tem como base a ideia de particionar uma lista de números em duas partes de acordo com um elemento chamado \(pivot\). Uma das partes deve conter todos os elementos menores que o\(pivot\) e a outra parte deve conter todos os elementos maiores que o \(pivot\).

  1. Escolha um elemento do vetor e chame de \(pivot\).
  2. No início, têm-se o \(pivot\), e uma parte do vetor que não está ordenada.
  3. Para cada elemento do vetor, procede-se da seguinte forma: Se o elemento em questão for menor que o \(pivot\), o coloque na esquerda. Se o elemento for maior que o \(pivot\), o coloque na direita. Caso o elemento seja o próprio \(pivot\) o mantenha na posição.
  4. Por fim chama-se a função colocando os elementos a esquerda do \(pivot\), o próprio \(pivot\) e os elementos a direita do \(pivot\).

    O código utilizando transformação e conquista, via pré-sorting, em Python para encontrar a moda de um sequência de dados segue abaixo.

Primeiramente importa-se as bibliotecas \(numpy\) e \(random\), a biblioteca \(random\) é importante para a seleção do elemento \(pivot\) do Quicksort.

import numpy as np
import random as rd

Defini-se a função de ordenamento via quicksort, conforme mencionado acima.

def quicksort(d):
    if len(d) <= 1:
        return d
    pivot = rd.choice(d)
    equal = [y for y in d if y == pivot]
    lesser = [y for y in d if y < pivot]
    greater = [y for y in d if y > pivot]
    return quicksort(lesser) + equal + quicksort(greater)

Após a função ordenada, o código irá comparar o elemento do vetor com o próximo caso seja igual irá guardar o valor e a frequência em que este apareceu. Similar ao código feito por força bruta. quando o elemento passa a ser diferente, então este não é mais comparado apenas o seguinte com o seu próximo. Com isso eliminando um processo de iteração se comparado com o código de força bruta.

def smart_mode(d):
    n = len(quicksort(d))
    l = quicksort(d)
    vmoda = []
    freq = 1
    freqmax = 0
    for i in range(0, n - 1):
        if l[i] == l[i + 1]:
            freq = freq + 1
            if freq > freqmax:
                if len(vmoda) != 0:
                    vmoda = []
                vmoda = np.append(vmoda, l[i])
                freqmax = freq
            elif freq == freqmax:
                vmoda = np.append(vmoda, l[i])
        else:
            freq = 1

    return (vmoda, freqmax)

Assim como o código de força bruta, o código de moda via pré-sorting retorna o valor da moda do conjunto de dados e a frequência máxima deste conjunto. Por último chama-se a função dada a sequência \(x\).

if __name__ == '__main__':
    x = [1, 2, 3, 1, 2, 3, 4, 3, 2, 1]
    print(quicksort(x))
    out = smart_mode(quicksort(x))
    print(out)

O resultado do algoritmo de pré-sorting para encontrar a moda de uma sequência \(x\) de dados é o seguinte.

[1, 1, 1, 2, 2, 2, 3, 3, 3, 4]
(array([ 1.,  2.,  3.]), 3)

Observa-se que a sequência \(x\) está ordenada e que sua moda são os números \(1, 2, 3\) com frequência de \(3\) vezes.

Complexidade Assintótica

A complexidade assintótica do algoritmo de força bruta é na ordem de \( \Theta (n^2) \), pois o código utiliza um \(while\) para percorrer o shape da sequência e um \(while\) que irá comparar termo a termo e guardar os valores junto com suas frequências.

O tempo gasto em geral no Quicksort segue a seguinte formulação.

\[ T(n) = T(k) + T(n - k - 1) + \Theta(n) \]

Os primeiros dois termos são oriundos das duas chamadas recursivas, já o último termo é do processo de partição da série. O termo \(k\) representa os números que são menores que o \(pivot\).

O pior caso ocorre sempre que o processo de partição seleciona como \(pivot\) o maior ou o menor elemento da sequência. O processo de recorrência no pior caso segue a seguinte forma.

\[ T(n) = T(n - 1) + \Theta(n) \]

A solução da recorrência acima é \(\Theta(n^2)\).

O melhor caso ocorre quando o processo sempre pega a mediana como elemento \(pivot\). O processo recursivo no melhor caso será:

\[ T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)\]

A solução desse processo recursivo utiliza o 2º caso do Teorema Mestre. A solução é \(\Theta(n \ log(n))\).

Em média ao escolher o elemento \(pivot\) aleatoriamente, observa-se que a complexidade será de \(\Theta(n \ log(n))\).

Levando-se em conta mais uma complexidade linear na ordem de \(n\) para selecionar e guardar o valor da moda e a frequência dos elementos que mais aparecem na série.

A complexidade assintótica desse algoritmo será de \(\Theta(n \ log(n))\).

Complexidade Empírica

Em primeiro plano analisa-se séries montadas aleatoriamente nos quais alteram-se seu tamanho.

Para gerar os gráficos em princípio determina-se uma função que irá salvar as bases que contemplam o tamanho das séries e o tempo gasto para rodar cada algoritmo. O tamanho das séries foi até 10.000 elementos na sequência.

# ==================================================================================
# salvando os dados - gráfico
def save_output(path_data, n, tempo):
    for t in range(0, len(n)):

        # OUTPUTs of results for analysis
        output_txt = open(path_data, 'a')
        output_txt.write('%d, %.8f \n' % (n[t], tempo[t]))
        output_txt.close()

O código em Python para força bruta segue abaixo.

# ============================================================================
# Encontrar a moda de uma série - força bruta_com timer

import numpy as np
import random as rd
from timeit import default_timer as timer

lista_tempo = []
lista_n = []
n = 100
for i in range(0, n):
    lista_process = [rd.randint(0,10+i) for r in range(i**2)]
    start_create = timer()

    def moda(x):
        newrow = np.empty((1, 2), dtype='float64')
        newrow[0,] = [x[0], 0]
        i = 0
        maximo = 0
        vmaximo = []
        while i < np.shape(newrow)[0]:
            j = 0
            while j < len(x):
                if newrow[i, 0] == x[j]:
                    newrow[i, 1] = newrow[i, 1] + 1
                    x.pop(j)
                else:
                    if x[j] not in newrow[:, 0]:
                        newrow = np.vstack([newrow, [x[j], 0]])
                    j = j + 1
            if maximo <= newrow[i, 1]:
                if maximo == newrow[i, 1]:
                    vmaximo = np.append(vmaximo, newrow[i, 0])
                    print vmaximo
                else:
                    vmaximo = newrow[i, 0]
                    maximo = newrow[i, 1]
            i = i + 1
        return (newrow, vmaximo, maximo)

    end_create = timer()
    resultado = (end_create-start_create)
    lista_tempo.append(resultado)
    lista_n.append(len(lista_process))

if __name__ == '__main__':
    out = moda(lista_process)
    print(out)
    m, s = divmod(resultado, 60)
    h, m = divmod(m, 60)
    print("Elapsed time produce to START : %d hs %.d min %.8f sec" % (h, m, s))
    print('')
    print(lista_n)
    print(lista_tempo)
    print("mode", i)
    save_output("D:/PPGA/mode.txt", lista_n, lista_tempo)

O código em Python para o cálculo da moda via pré-sorting segue abaixo.

# ========================================================================
# Encontrar a moda de uma série com pré sorting - quicksort_com timer

import numpy as np
import random as rd
from timeit import default_timer as timer

lista_tempo = []
lista_n = []
n = 100
for i in range(0, n):
    lista_process = [rd.randint(0, 10+i) for r in range(i ** 2)]
    start_create = timer()

    def quicksort(d):
        if len(d) <= 1:
            return d
        # pivot = d[0]
        pivot = rd.choice(d)
        equal = [y for y in d if y == pivot]
        lesser = [y for y in d if y < pivot]
        greater = [y for y in d if y > pivot]
        return quicksort(lesser) + equal + quicksort(greater)

    def smart_mode(d):
        n = len(quicksort(d))
        l = quicksort(d)
        vmoda = []
        freq = 1
        freqmax = 0
        for i in range(0, n - 1):
            if l[i] == l[i + 1]:
                freq = freq + 1
                if freq > freqmax:
                    if len(vmoda) != 0:
                        vmoda = []
                    vmoda = np.append(vmoda, l[i])
                    freqmax = freq
                elif freq == freqmax:
                    vmoda = np.append(vmoda, l[i])
            else:
                freq = 1

        return (vmoda, freqmax)

    end_create = timer()
    resultado = (end_create-start_create)
    lista_tempo.append(resultado)
    lista_n.append(len(lista_process))


if __name__ == '__main__':
    out = smart_mode(lista_process)
    print(out)
    m, s = divmod(resultado, 60)
    h, m = divmod(m, 60)
    print("Elapsed time produce to START : %d hs %.d min %.8f sec" % (h, m, s))
    print('')
    print(lista_n)
    print(lista_tempo)
    print("smart_mode", i)
    save_output("D:/PPGA/smart_mode.txt", lista_n, lista_tempo)

O código para gerar a parte gráfica segue abaixo.

# =====================================================================================
# plot - parte gráfica

import matplotlib.pyplot as plt
plt.style.use('ggplot')
import pandas as pd

def plot_general(data_file):
    dat = pd.read_csv(data_file + ".txt", sep=",", header=None)
    dat.plot(x=[0], y=[1], kind='line', label='Time')
    plt.xlabel('Number of samples')
    plt.ylabel('Time process (secs)')
    plt.title('Evaluation of time', )
    plt.legend(["Time (secs)"])
    plt.savefig(data_file + "_evolution_time", ext="png", close=False, verbose=True)
    plt.show()

plot_general("D:/PPGA/smart_mode")
plot_general("D:/PPGA/mode")



import matplotlib.pyplot as plt
plt.style.use('ggplot')
import pandas as pd

def plot_general(dat_file, dat_file2):
    dat = pd.read_csv(dat_file, sep=",", header=None)
    dat2 = pd.read_csv(dat_file2, sep=",", header=None)
    data = pd.merge(dat, dat2, on=[0], how='outer')
    data.columns = ["n","mode","smart_mode"]
    plotfile = data.plot(x=["n"], title="Cumulative graph", colormap='Spectral')
    plotfile.set_xlabel('Number of sample')
    plotfile.set_ylabel('time in secs')
    plotfile.set_axis_bgcolor('w')
    fig = plotfile.get_figure()
    fig.set_size_inches(15,10)
    fig.savefig('D:/PPGA/graph_comparison_time.png', dpi=200)

plot_general("D:/PPGA/mode.txt", "D:/PPGA/smart_mode.txt")

A imagem gerada pelo o código de força bruta é a seguinte.

A imagem será apresentada aqui.

A imagem gerada pelo código de pré-sorting é a seguinte.

A imagem será apresentada aqui.

A imagem combinada dos dois códigos seguem abaixo.

A imagem será apresentada aqui.

Observa-se que em média o método pré-sorting de seleção da moda de uma série de dados é mais rápida que o modelo em força bruta. Resultado que comprova a relação assintótica de complexidade.

Elaborou-se também análise para uma série fixa de dados sendo realizada 1.000 vezes. A única alteração aos códigos acima é a substituição da elaboração aleatória das séries, para utilização da mesma série fixa apresentada acima, no qual gerou a moda como os números \(1, 2, 3\) com frequência de \(3\) vezes.

A alteração feita é a seguinte.

for i in range(0, n):
    x = [1, 2, 3, 1, 2, 3, 4, 3, 2, 1]

Os gráficos deste teste seguem abaixo.

A imagem gerada pelo o código de força bruta é a seguinte.

A imagem será apresentada aqui.

A imagem gerada pelo código de pré-sorting é a seguinte.

A imagem será apresentada aqui.

A imagem combinada dos dois códigos seguem abaixo.

A imagem será apresentada aqui.

Observa-se que em média o método pré-sorting de seleção da moda de uma série de dados é mais rápida que o modelo em força bruta. Resultado que comprova a relação assintótica de complexidade.

Referências
Moda.
Força Bruta.
Quicksort 1.
Quicksort 2.
Numpy.

...