Exercitando a Análise e Escrita de Experimentos

Vania Bogorny(material baseado no Livro de Justin

Zobel e prof Mirella Moura Moro)

Partes de um experimento

• Configuração. Como foi preparado o experimento• Parâmetros de execução do experimento para possível

reprodução do mesmo• Resultados. É preciso de detalhes específicos dos

resultados• Análise. Se for uma pesquisa quantitativa comente os

resultados com base em dados estatísticos

Interpretaçao dos experimentos

• A sua interpretação e compreensão dos experimentos é tão importante quanto os resultados propriamente ditos– Ao escrever o resultado de um experimento, não apenas

compile listas de figuras ou seqüência de gráficos. Analise os resultados e explique o seu significado, selecionando resultados típicos e importantes , explicando porque eles são significativos

– Mostre porque os resultados comprovam ou não a sua hipótese

• Experimentos só tem valor se forem cuidadosamente descritos, facilmente verificáveis e reproduzíveis

Descrevendo um experimento

• Os resultados de um experimento precisam ser descritos de forma qualitativa e quantitativa.– Dados quantitativos são aqueles que se expressam de forma numérica, como

percentagens e estatísticas. – Exemplo: o algoritmo proposto obteve uma redução de 50% no tempo de

processamento em relação a abordagens existentes.– Dados qualitativos são derivados de uma questão ampla, e se manifestam sob a forma

de respostas descritivas dos participantes do estudo.– Exemplo: O tempo de processamento reduziu porque o método proposto faz menos

acessos a disco, possui uma chave de busca direta e processa a parte x do algoritmo em memória .....

• Certifique-se de que os resultados sejam exibidos tanto graficamente como elaborados em uma descrição detalhada.

Descrevendo um experimento:

• Comece com um resumo dos experimentos: o que é medido, o que não é, por que, …

• Adicione um parágrafo com o modelo de simulação ou a infraestrutura das medições (configuração do sistema, tipo de máquinas usadas, linguagens, …). Apresente os resultados dos experimentos:

• Use um subtítulo (em negrito) para diferenciar experimentos (avaliando tamanho da entrada, variando a quantidade de consultas, usando dados sintéticos, usando dados reais, …).

Exemplo I (objetivo é ganhar performance)

• In this section, we present a performance comparison of FP-growth with the classical frequent pattern mining algorithm Apriori, and a recently proposed ecient method TreeProjection. All the experiments are performed on a 450- MHz Pentium PC machine with 128 megabytes main memory, running on Microsoft Windows/NT. All the programs are written in Microsoft/Visual C++6.0. Notice that we do not directly compare our absolute number of runtime with those in some published reports running on the RISC workstations because diferent machine architectures may difer greatly on the absolute runtime for the same algorithms. Instead, we implement their algorithms to the best of our knowledge based on the published reports on the same machine and compare in the same running environment. Please also note that run time used here means the total execution time, i.e., the period between input and output, instead of CPU time measured in the experiments in some literature. Also, all reports on the runtime of FP-growth include the time of constructing FP-trees from the original databases. The synthetic data sets which we used for our experiments were generated using the procedure described in [3]. We report experimental results on two data sets. The first one is T25:I10:D10K with 1K items, which is denoted as D1. ….

• Fonte (Han et al 2000) - Mining Frequent Patterns without Candidate Generation

O que é medido

Onde foi executado

Em que linguagem foi implementado

Quais dados foram usados

Exemplo II (objetivo é ganhar em performance)

• To assess the relative performance of the algorithms for discovering large itemsets, we performed several experiments on an IBM RS/6000 530H workstation with a CPU clock rate of 33 MHz, 64 MB of main memory, and running AIX 3.2. The data resided in the AIX le system and was stored on a 2GB SCSI 3.5" drive, with measured sequential throughput of about 2 MB/second. We first give an overview of the AIS [4] and SETM [13] algorithms against which we compare the performance of the Apriori and AprioriTid algorithms. We then describe the synthetic datasets used in the performance evaluation and show the performance results. Finally, we describe how the best performance features of Apriori and AprioriTid can be combined into an AprioriHybrid algorithm and demonstrate its scale-up properties.

• Fonte (Agrawal et al 1994) - Fast Algorithms for Mining Association Rules

Exemplo III (objetivo é descobrir um tipo novo de padrão)• The goal of this section is to evaluate the proposed algorithm under

different points of view. First, we quantitatively test the effectiveness of the algorithm by analyzing the ability to correctly detect expected avoidance behaviors. To this end we use an ad-hoc annotated dataset, our ground truth, created for the purposes of this work (Section 6.1). Second, we compare our approach with the one presented in [11]. The work [11], as pointed out in Section 2, is the only work dealing with avoidance detection between moving objects we are aware of (Section 6.2). Third, we assess the ability of the algorithm in highlighting interesting and previously unknown patterns emerging from avoidance behaviors when using datasets for which no prior knowledge related to avoidance behaviors is available (Section 6.3)

• Fonte: Lettich et al 2015 - Detecting Avoidance Behaviors Between Moving Object Trajectories

Exemplo III (continuação)• We exploit a ground truth of annotated trajectories,

explicitly created for this work, whose data derive from real GPS observations of moving objects collected in Florianopolis and Venice. This public dataset1 contains an overall amount of 86 trajectories representing pedestrian movements, for a total of 7,834 samples and an average sampling rate of one second. Although this dataset is not large, it is sufficient to validate the proposed method.

• Fonte: Lettich et al 2015 - Detecting Avoidance Behaviors Between Moving Object Trajectories

Descrevendo o experimento• Todos os gráficos e diagramas devem ter um número e um título.

– Por exemplo, se estiver testando o efeito do fertilizante no crescimento das plantas, você precisará de um gráfico mostrando a média de crescimento das plantas fertilizadas e das que cresceram naturalmente.

• Você também deve descrever o resultado. – Por exemplo, "as plantas que receberam uma concentração de 1ml de

fertilizante cresceram uma média de 4 cm a mais do que aqueles que não foram fertilizadas".

• Explique o que é representado em cada eixo de um gráfico• cada gráfico deve ter uma razão clara para aparecer no seu

artigo

Descrevendo um experimento:

• explique cada gráfico: os eixos, o que o gráfico mostra, qual é a tendência, por que a tendência aparece, por que um algoritmo apresenta melhores resultados que outro, …

• cada gráfico deve ser auto-contido: legendas devem ser legíveis e compreensíveis.

• encerre a seção com comentários finais, discussões, explicações adicionais.

• Como sugestão para organização da seção de experimentos considere a seguinte exemplo de (ZHANG @ SIGMOD 1996):– 6. Performance studies 6.1 Analysis 6.2 Synthetic Dataset Generator 6.3 Parameters and

Default Setting 6.4 Base Workload Performance 6.5 Sensitivity to Parameters 6.6 Time Scalability 6.7 Comparison of BIRCH and CLARANS 6.8 Application to Real Datasets

Exemplo de gráfico com tendência

Exemplo de Gráfico

Atenção a Escala dos eixos!

Descrevendo um experimento

• A medida que você continua esta seção, narre seus resultados. – Diga ao leitor porque o resultado é significativo para o experimento ou

problema. Isso permitirá que ele siga sua linha de pensamento.

• Compare seus resultados com sua hipótese original. • Declare se sua hipótese foi ou não sustentada pela sua

experiência.

Detalhando um experimento

• Exemplo:To explain these performance trends, we show in Figure 5 the

sizes of the large and candidate sets in different passes for the xxxx dataset for the minimum support of 75%. Note that the Y-axis in this graph has a log scale…..

Cuidado ao relatar resultados negativos ou falhas

• Por exemplo, a frase “we have shown that it is not possible to make further improvement”, pode levar o revisor/leitor a pensar que o que foi mostrado é que o autor não é competente para fazer mais experimentos

• Uma falha num experimento não deve ser relatada, mas sim, levar você a refazer ou redefinir um novo experimento

• Uma falha no resultado pode mostrar uma falha na hipótese ou nos testes

Parâmetros e Ordem dos Resultados

• Não esqueça de justificar os valores dos parâmetros escolhidos• Mostre os resultados com diferentes valores de parâmetros, e não mude

todos os parâmetros de uma só vez. Mude um parâmetro e mantenha fixos os valores dos demais.– Só assim você estará analisando o efeito de UM parâmetro no experimento. Mudando

vários parâmetros AO MESMO TEMPO vc não saberá quem gerou o efeito no resultado (provavelmente todos).

• Mostre direto o resultado o final, e depois vá mostrando detalhes e explicando o porquê dos resultados– Mesmo que seu método tenha vários passos, os meios serão usados para explicar os fins

(o resultado final), não precisando de um detalhamento passo a passo (veja se isso é coerente com o seu propósito)

• Compare seu trabalho com abordagens existentes, pois sem a comparação o revisor não saberá se sua proposta é interessante.

Importância da Escolha do Método a ser comparado (baseline)

• Desde o inicio da pesquisa já se preocupe em obter o código do trabalho que vc deve comparar com o seu

• Escolha o método correto a ser comparado.• A escolha do método errado para comparação pode levar a

rejeição do trabalho– Exemplo: Se você estiver propondo um método que reduza o número

de regras de associação geradas, você deveria comparar o seu método não apenas com o Apriori, que é o método original, mas com os métodos que eliminam regras redundantes (métodos recentes), para demonstrar que seu método supera ambas as abordagens.

– Não faria sentido comparar apenas com a abordagem antiga se já existe um método bem conhecido e que é melhor que o método antigo

Interpretação dos experimentos

• Quando analisar os experimentos, verifique se há possibilidade de ter outras interpretações dos resultados. Se tiver, já faça um experimento e avalie o resultado, isso evitará questionamentos do revisor sobre essas possibilidades

• Nunca escreva em um artigo: X “ we did several tests”, we performed several experiments

Discussão dos Resulados

• Discussão (se necessário)• Pode ser incluída como subseção final de Experimentos. A Discussão

mostra os relacionamentos entre os fatos e resultados observados. Sugestões:

• Lembre-se que é uma seção de discussão, na qual vocês discute, e não recapitula os resultados já mostrados nos Experimentos.

• liste qualquer exceção ou qualquer falta de relação e defina pontos incertos.

• mostre que seus resultados e interpretações concordam (ou contrastam) com trabalhos previamente publicados.

• discuta implicações teóricas e possíveis aplicações práticas.• resuma as evidências para cada conclusão, não assuma que o leitor é

super capaz de juntar todos os pontos sozinho.

Implementação (dicas de Justin Zobel)

• Computeiros perdem muito tempo tentando inserir a implementação em um sistema, ou implementando-a de forma que seja impossível fazer uma reprodução.– OBS: A não ser que o sistema seja de código aberto, disponível para uso geral, e de fácil

extensão• A regra básica é: mantenha as coisas de forma simples, • Mantenha uma versão na forma de script, que você possa colocar no seu site ou

no site do seu orientador para que outros pesquisadores possam reproduzir seu experimento

• Faça os parâmetros serem entradas como argumentos, isso evitará em muitos casos que outros pesquisadores precisem recompilar os seus programas

• A saida de um script pode ser armazenada em um arquivo, para fácil analise e backup posterior

• Um arquivo de saida bem projetado deveria conter: o nome do arquivo de entrada, a versao do codigo, os valores dos parametros, data e hora

Log de experimentos

• Mantenha um log dos experimentos realizados com data, conjunto de dados, parâmetros, resultado, etc, e selecione apenas os mais relevantes para reportar no artigo

• Os resultados mostrados no artigo podem representar apenas uma fração do seu trabalho de pesquisa.

• Você não precisa mostrar no artigo o quanto vc trabalhou, mas sim os resulados INTERESSANTES que obteve

Descrevendo um experimento: Estudo de Caso

• Se for usar um estudo de caso Inclua:– contexto geral,– regras ou condições específicas requeridas pelo caso, – modelagem, funcionamento, v– vantagens e desvantagens de usar o modelo proposto nesse caso.

Exemplo IV – Avaliando um modelo• 4. Experimenting CONSTANT in two case studies• In this section we present two case studies on two different applications, based on real trajectories. The

first case study is based on a tourist application, while the second one is based on a bird migration application.

• 4.1 CONSTANT instantiation for a Tourism Application• In this example we instantiate the CONSTANT model in a very common application for mobility: Tourism.

Usually, this kind of application needs to study the movement of people visiting a location – that can be a

• 4.2 Model Instantiation for a Bird Migration• This application case study is related to bird migration, since nowadays it is very common for biologists

to study animal behavior with tracking techniques, which can be radio-station based (with low spatio-temporal granularity) or GPS-based (with higher spatio-temporal granularity). Here we assume that the tracked animals are birds equipped with a GPS collar that has a sensor that measures the temperature of the bird. Because of energy consumption, the satellite communication rate of the device is much lower than in the tourism application, where the GPS of tourist in a car can collect a point every second. In the birds application we assume that the sampling rate is more or less 30 minutes.

• Fonte: Bogorny et al 2014 - CONSTAnT - A Conceptual Data Model for Semantic Trajectories of Moving Objects

Exercicio: Projete um experimento para comparar 2 algoritmos bem conhecidos para resolver algum problema

• Exemplo: busca binária x hash table (ou busca sequencial x busca binária)

1. Qual é a saída esperada? Ou seja, qual é a hipótese?2. Bons resultados justificam uma analise da complexidade?3. Quais fatores deveriam ser medidos? Como eles deveriam ser

medidos?4. Quais seriam bons e apropriados dados de teste?5. Os resultados dependem do que, características ou peculiaridades

dos dados?6. Quais propriedades os dados deveriam ter para confirmar a

hipótese?7. A qualidade da implementação afeta o resultado?