Tutorial de Análise de Envelope de Dados

• 24 de fevereiro de 2014
• Vasilis Vryniotis
• . 3 Comentários

A Análise de envoltória de dados, também conhecida como DEA, é um método não paramétrico para realizar a análise de fronteira. Ele usa programação linear para estimar a eficiência de várias unidades de tomada de decisão e é comumente usado em produção, gerenciamento e economia. A técnica foi proposta pela primeira vez por Charnes, Cooper e Rhodes em 1978 e, desde então, tornou-se uma ferramenta valiosa para estimar as fronteiras de produção.

Atualização: O Datumbox Machine Learning Framework agora é de código aberto e gratuito para download. Confira o pacote com.datumbox.framework.algorithms.dea para ver a implementação da Análise de Envelopamento de Dados em Java.

Quando encontrei o método pela primeira vez, há 5 a 6 anos, fiquei surpreso com a originalidade do algoritmo, sua simplicidade e a inteligência das ideias que ele usava. Fiquei ainda mais surpreso ao ver que a técnica funcionou bem fora de suas aplicações usuais (financeiras, pesquisa operacional etc.), uma vez que poderia ser aplicada com sucesso em Marketing Online, Ranking de Mecanismos de Busca e para a criação de métricas compostas. Apesar disso, hoje a DEA é quase exclusivamente discutida no contexto dos negócios. É por isso que, neste artigo, irei cobrir as idéias básicas e a estrutura matemática por trás do DEA e no próximo post irei mostrar algumas novas aplicações do algoritmo em aplicações web.

Por que a análise de envoltório de dados é interessante?

Análise de envoltório de dados é um método que nos permite comparar e classificar registros (lojas, funcionários, fábricas, páginas da web, campanhas de marketing, etc) com base em seus recursos (peso, tamanho, custo, receitas e outras métricas ou KPIs) sem fazer quaisquer suposições anteriores sobre a importância ou pesos dos recursos. A parte mais interessante dessa técnica é que ela nos permite comparar registros compostos por vários recursos que têm unidades de medida totalmente diferentes. Isso significa que podemos ter registros com características medidas em quilômetros, quilogramas ou unidades monetárias e ainda ser capazes de comparar, classificá-los e encontrar os registros de melhor / pior e de desempenho médio. Soa interessante? Continue lendo.

A descrição e as premissas da Análise de Envelopamento de Dados

Como discutimos anteriormente, DEA é um método que foi inventado para medir a produtividade nos negócios. Assim, várias de suas ideias vêm da maneira como a produtividade é medida neste contexto. Uma das principais características do método é a separação dos recursos de registro em duas categorias: entrada e saída. Por exemplo, se medirmos a eficiência de um carro, poderíamos dizer que a entrada são os litros de gasolina e a saída é o número de quilômetros que ele percorre.

No DEA, todos os recursos devem ser positivos e assume-se que quanto maior seu valor, maior será sua entrada / saída. Além disso, a Análise de envoltória de dados pressupõe que os recursos podem ser combinados linearmente como uma soma ponderada de pesos não negativos e formar uma razão entre a entrada e a saída que medirá a eficiência de cada registro. Para que um registro seja eficiente, ele deve nos dar uma saída “boa” em relação à entrada fornecida. A eficiência é medida pela razão entre a produção e a entrada e então comparada com a razão dos outros registros.

A ideia genial por trás da DEA

O que cobrimos até agora é um bom senso / prática. Usamos entradas e saídas, somas ponderadas e proporções para classificar nossos registros. A ideia inteligente do DEA está na maneira como os pesos dos recursos são calculados. Em vez de definir os pesos dos recursos e decidir sobre sua importância antes de executarmos a análise, a Análise de Envelopamento de Dados os calcula a partir dos dados. Além disso, os pesos NÃO são os mesmos para todos os registros!

Aqui está como o DEA seleciona os pesos: Tentamos maximizar a proporção de cada registro selecionando os pesos de recurso apropriados; ao mesmo tempo, devemos garantir que, se usarmos os mesmos pesos para calcular as proporções de todos os outros registros, nenhum deles se tornará maior do que 1.

A ideia parece um pouco estranha no início. Isso não levará ao cálculo de proporções com pesos diferentes? A resposta é sim. Isso não significa que, na verdade, calculamos de forma diferente as proporções para cada registro? A resposta é novamente sim. Então, como isso funciona? A resposta é simples: para cada registro, dadas as suas características, procuramos encontrar a “situação ideal” (pesos) em que sua proporção seja a mais alta possível e assim torná-la o mais eficaz possível. MAS ao mesmo tempo, dada esta “situação ideal”, nenhuma das relações de saída / entrada dos outros registros deve ser maior que 1, o que significa que eles não podem ser mais eficazes do que 100%! Depois de calcularmos as proporções de todos os registros em cada “situação ideal”, usamos suas proporções para classificá-los.

Assim, a ideia principal do DEA pode ser resumida da seguinte forma: “Encontre a situação ideal em que possamos alcançar a melhor pontuação de proporção com base nas características de cada registro. Em seguida, calcule essa proporção ideal de cada registro e use-a para comparar sua eficácia ”.

Vamos ver um exemplo

Vejamos um exemplo onde podemos usar DEA.

Suponha que estejamos interessados ​​em avaliar a eficiência das lojas de supermercados de uma determinada rede com base em uma série de características: o número total de funcionários, o tamanho da loja em metros quadrados, a quantidade de vendas que geram e o número de clientes que eles veiculam todos os meses, em média. Torna-se óbvio que encontrar os armazenamentos mais eficientes exige que comparemos registros com vários recursos.

Para aplicar DEA, devemos definir qual é a nossa entrada e saída. Nesse caso, a saída é obviamente a quantidade de vendas e o número de clientes que atendem. A entrada é o número de funcionários e o tamanho da loja. Se executarmos o DEA, estimaremos a razão de produto para entrada para cada loja sob os pesos ideais (conforme discutido acima). Assim que tivermos seus índices, os classificaremos de acordo com sua eficiência.

É hora da matemática!

Agora que temos uma intuição de como o DEA funciona, é hora de nos aprofundarmos na matemática.

A taxa de eficiência de um determinado registro i com entrada x ey saída (ambos os vetores de características com valores positivos) é estimada usando a seguinte fórmula:

Onde uev são os pesos de cada saída e entrada do registro, s é o número de recursos de saída e m é o número de recursos de entrada.

O problema de encontrar os pesos melhores / ideais para um determinado registro i pode ser formulado da seguinte forma:

Novamente, o acima é apenas a maneira matemática de encontrar os pesos uev que maximizam a eficiência do registro i, desde que esses pesos não tornem nenhum dos outros registros mais eficiente do que 100%.

Para resolver este problema, devemos usar a programação linear. Infelizmente, a programação linear não nos permite usar frações e, portanto, precisamos transformar a formulação do problema da seguinte forma:

Devemos enfatizar que o problema de programação linear acima nos dará os melhores pesos para o registro i e calculará sua eficiência sob esses pesos ótimos. O mesmo deve ser repetido para cada registro em nosso conjunto de dados. Portanto, se temos n registros, temos que resolver n problemas lineares separados. Aqui está o pseudocódigo de como o DEA funciona:

ratio_scores = [];
for every record i {
    i_ratio = get_maximum_effectiveness();
    ratio_scores[i] = i_ratio;
}

Limitações da análise de envelope de dados

DEA é uma ótima técnica, mas tem suas limitações. Você deve entender que o DEA é como uma caixa preta. Como os pesos usados ​​na proporção de eficácia de cada registro são diferentes, tentar explicar como e por que cada pontuação foi calculada é inútil. Normalmente, nos concentramos na classificação dos registros, e não nos valores reais das pontuações de eficácia. Observe também que a existência de extremos pode fazer com que as pontuações tenham valores muito baixos.

Lembre-se de que o DEA usa combinações lineares dos recursos para estimar as proporções. Assim, se combiná-los linearmente não for apropriado em nossa aplicação, devemos aplicar transformações nos recursos e torná-los possíveis de serem combinados linearmente. Outra desvantagem dessa técnica é que temos que resolver tantos problemas de programação linear quanto o número de registros, algo que requer muitos recursos computacionais.

Outro problema que o DEA enfrenta é que ele não funciona bem com dados dimensionais elevados. Para usar DEA, o número de dimensões d = m + s deve ser significativamente menor do que o número de observações. Executar DEA quando d é muito próximo ou maior que n não fornece resultados úteis, pois muito provavelmente todos os registros serão considerados ótimos. Observe que conforme você adiciona uma nova variável de saída (dimensão), todos os registros com valor máximo nesta dimensão serão considerados ótimos.

Finalmente, devemos notar que na forma geral do algoritmo, os pesos dos recursos no DEA são estimados a partir dos dados e, portanto, eles não usam nenhuma informação prévia sobre a importância dos recursos que podemos ter em nosso problema (é claro é possível incorporar essas informações como restrições em nosso problema linear). Além disso, as pontuações de eficiência calculadas são, na verdade, as razões de eficiência de limite superior de cada registro, uma vez que são calculadas em “situações ideais”. Isso significa que o DEA pode ser uma boa solução quando não é possível fazer suposições sobre a importância dos recursos, mas se tivermos alguma informação prévia ou pudermos quantificar sua importância, então recomendamos o uso de técnicas alternativas.

No próximo artigo, mostrarei como desenvolver uma implementação de Análise de envoltória de dados em JAVA e usaremos o método para estimar a popularidade de páginas da web e artigos em redes de mídia social.

Se você gostou do artigo, reserve um momento para compartilhá-lo no Twitter ou Facebook. 🙂