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:
- primeiro \((P)\): gera o primeiro candidato à solução de \(P\).
- próximo \((P, C)\): gera o próximo candidato de \(P\) depois de \(C\).
- válido \((P, C)\): checa se o candidato \(C\) é a solução de \(P\).
- 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\).
- Escolha um elemento do vetor e chame de \(pivot\).
- No início, têm-se o \(pivot\), e uma parte do vetor que não está ordenada.
- 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.
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 gerada pelo código de pré-sorting é a seguinte.
A imagem combinada dos dois códigos seguem abaixo.
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 gerada pelo código de pré-sorting é a seguinte.
A imagem combinada dos dois códigos seguem abaixo.
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.