domingo, 1 de junho de 2008

Cálculo da variância com linguagem funcional

Paradigma funcional A implementação de cálculos básicos de estatística em linguagens funcionais é tremendamente mais simples do que usando linguagens imperativas, como a tradicional C, muito usada devido a sua abstração matemática¹.

Escolhi como exemplo o cálculo da variância, que determina o grau de dispersão dos elementos de um conjunto ou vetor.

Para o cálculo da variância é preciso calcular a média dos elementos do vetor.

Média


Em quase todos os textos que li sobre variância, covariância e outras operações estastísticas, é aconselhado usar a média quadrada dos elementos, mas meu professor de estatística diz pra usar a média aritmética.

Então vamos implementar as duas.

Média aritmética


Média aritmética consiste no somatório de todos os elementos dividido pelo número de elementos.

Em C a implementação é:
double arithmetic_mean(double *v, int len) {
double sum = 0;
int i;
for (i = 0; i < len; ++i)
sum += v[i];
return sum / len;
}


Em Common Lisp o mesmo algoritmo é implementado assim:
(defun arithmetic-mean (a-list)
(/ (reduce '+ a-list) (length a-list)))


Desconsiderando a implementação em duas linhas contra seis ou sete em C, podemos citar algumas vantagens:
  1. Em C é preciso informar o tamanho do vetor, enquanto em Common Lisp não – em C++ usando STL também não seria necessário.
  2. Em C usamos diversar variáveis que mudam de estado em ciclos. Em Common Lisp usamos funções e retornos, numa relação 1:1 com a Matemática – por exemplo, Σx vira (reduce '+ x).
  3. Realmente… duas linhas em Lisp contra seis ou sete em C. =)


Média quadrada


Média quadrada ou RMS consiste na raiz quadrado da razão do somatório dos quadrados dos elementos pela quantidade:
double root_mean_square(double *v, int len) {
double sum = 0;
int i;
for (int i = 0; i < len; ++i)
sum += v[i] * v[i];
return sqrt(sum / len);
}


Observação: para usar sqrt() é preciso incluir o cabeçalho math.h.

Agora vamos fazer a mesma coisa em Common Lisp:
(defun root-mean-square (a-list)
(sqrt
(/
(reduce '+ (mapcar (lambda (e) (* e e)) a-list))
(length a-list))))


[update 2008-06-14]O código acima foi alterado segundo a sugestão do Pedro – veja comentários abaixo.[/update]


Esse ficou maiorzinho, no entanto mantém uma relação muito mais próxima com a expressão matemática do que C. No caso o form loop criou um novo vetor contendo os quadrados dos elementos, que foi reduzido por reduce e '+ – Σ.

Escolhendo uma média


Se você escolher a média aritmética, faça:
#define mean(v, len) arithmetic_mean(v, len)


Em Lisp:
(defun mean (a-list)
(arithmetic-mean a-list))


E se escolher média quadrada:
#define mean(v, len) root_mean_square(v, len)

(defun mean (a-list)
(root-mean-square a-list))


Numerador da variância


Há dois tipos de variância: populacional e da amostra. O cálculo é similar, mudando apenas o denominador. Portanto vamos calcular primeiro o numerador, idêntico para os dois tipos de variância.

Em C, o cálculo do numerador é:
double varnum(double *v, int len) {
double mean_x = mean(v, len);
double sum = 0;
int i;
for (i = 0; i < len; ++i)
sum += pow(v[i] - mean_x, 2.);
return sum;
}


Observação: para usar pow() é preciso incluir o cabeçalho math.h.

Agora em Common Lisp:
(defun var-num (a-list)
(reduce #'+
(mapcar (lambda (e) (expt (- e (mean a-list)) 2)) a-list)))


[update 2008-06-14]O código acima foi alterado segundo a sugestão do Pedro – veja comentários abaixo.[/update]


É claro, para quem está acostumado a ver códigos e mais códigos em linguagens derivadas de C o código em Lisp pode parecer confuso, mas se você for tentar explicar a um matemático sem conhecimento de C, verá que programação funcional se encaixa melhor à Matemática pura.

Variância populacional


A variância populacional consiste na razão do numerador calculado pela quantidade de elementos e é usada quando o vetor representa todos os elementos do universo desejado.
double populational_variance(double *v, int len) {
return varnum(v, len) / len;
}


Em Common Lisp:
(defun populational-variance (a-list)
(/ (var-num a-list) (length a-list)))


Variância da amostra


A variância da amostra consiste na razão do numerador calculado pela quantidade de elementos menos um e é usada quando o vetor representa apenas uma amostragem do universo desejado.
double sample_variance(double *v, int len) {
return varnum(v, len) / (len - 1);
}


Em Common Lisp:
(defun sample-variance (a-list)
(/ (var-num a-list) (-(length a-list) 1)))


Conclusão


Para operações estatísticas ou puramente matemáticas, linguagens funcionais podem ser uma alternativa mais eficiente do que linguagens imperativas.

[update 2008-06-07]Versão em Ruby pelo Tiago no Programando sem cafeína![/update]
[update 2008-06-10]Versão em Python pelo LKRaider no LKVenia! =)[/update]


[]'s
Cacilhas, La Batalema

¹Abstração matemática: quis dizer abstração de alto nível em busca de uma representação mais matemática.
blog comments powered by Disqus