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
246 visitas
perguntada Jun 20, 2017 em Ciência da Computação por João Gabriel Souza (81 pontos)  
republicada Jun 23, 2017 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, 2017 por João Gabriel Souza (81 pontos)  
editado Jun 23, 2017 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.

comentou Mar 27 por DanWilliams (1 ponto)  
You can refer below resource regarding sorting in programming,

http://www.flowerbrackets.com/how-to-implement-quick-sort-in-java-program/
...