ESPECIFICAÇÃO FINAL DO TRABALHO DE ACH2016 - INTELIGÊNCIA ARTIFICIAL - 2012 Profa. Patrícia Oliveira

Datas de apresentação: 04/12 e 05/12, das 10:15 às 12:00, na sala 220.

Entrega no COL: até a meia-noite do dia 03/12. Devem ser postados o código fonte, o código executável (junto com eventuais instruções de execução do mesmo) e apresentação em PowerPoint. Basta uma postagem por grupo. Não se esqueçam de colocar a identificação dos integrantes nos arquivos editáveis.

Observação 1: Este trabalho deve ser realizado por um grupo de no mínimo 4 e no máximo 5 alunos.

Observação 2: Pode ser utilizada qualquer linguagem de programação (Java, C, C++, etc). Fica vedado o uso de softwares e pacotes utilitários que já contenham algoritmos de aprendizado de máquina implementados (por exemplo, WEKA).

Observação 3: Plágios, mesmo que parciais, serão punidos com nota zero para os copiadores e copiados envolvidos. O mesmo acontecerá caso seja detectado plágio com arquivos disponíveis na internet.

Objetivos Gerais: Implementar o algoritmo Naive Bayes para classificação de mensagens de SPAM e utilizar Algoritmos Genéticos para selecionar atributos para o mesmo problema.

Passo 1) Implemente o algoritmo Naive Bayes e teste o seu programa com o conjunto de treinamento "PlayTennis", descrito no Capítulo 3 do livro do Mitchell. Nessa etapa, o grupo deve implementar métodos (procedimentos) para:

a) Utilizar o conjunto de treinamento para aprender as probabilidades a priori e condicionais a serem aplicadas no item b.

b) Classificar exemplos no conjunto de teste (a ser definido arbitrariamente pelo grupo).

Passo 2) Adapte o programa desenvolvido no Passo1 para a base de dados SPAM (ftp://ftp.ics.uci.edu/pub/machine-learning-databases/spambase/), com o objetivo de predizer se uma determinada mensagem eletrônica é SPAM (1) ou não (0). Cada exemplo possui 57 atributos, como descrito no arquivo “spambase.names”, além do atributo classe. Nessa etapa, o grupo deve conduzir experimentos utilizando duas técnicas de amostragem, conforme especificado a seguir.

a) Treinamento e avaliação de desempenho do classificador bayesiano utilizando o método holdout. Para esse experimento, deve-se dividir, aleatoriamente, os dados em conjunto de treinamento e conjunto de teste, em que o conjunto de treinamento deve ter aproximadamente 2/3 do tamanho do conjunto de dados original. Proceda com as fases de aprendizagem (usando o conjunto de treinamento) e classificação (usando o conjunto de teste). A seguir, registre a matriz de confusão para o classificador e a sua acurácia.

b) Treinamento e Avaliação de Desempenho do Classificador Bayesiano utilizando o método Crossvalidation. Para esse experimento, deve-se dividir, aleatoriamente, os dados em 10 (dez) partições (folds). Proceda com as fases de treinamento e teste do classificador utilizando o método Crossvalidation. Devem ser registrados, os erros verdadeiros obtidos pelo classificador para cada uma das 10 etapas do Crossvalidation e a estimativa final para o desempenho do modelo, considerando um intervalo de confiança de 95%.

Passo 3) Implemente um Algoritmo Genético para selecionar atributos para o algoritmo Naive Bayes desenvolvido no passo anterior.

• a) Dividir novamente o conjunto de dados SPAM Criar, aleatoriamente, uma nova partição do conjunto, com três subconjuntos disjuntos, de aproximadamente mesmo tamanho: conjunto de treinamento, conjunto de teste e conjunto de validação.

• b) Modelar a seleção de atributos via Algoritmo Genético (AG) O AG deve trabalhar com cadeias de bits de tamanho 57, em que 1 significa “use esse atributo” e 0 significa “não use esse atributo”.

Suponha que os subconjuntos da partição tenham sido nomeados da seguinte forma: spam.trein (para o conjunto de treinamento), spam.val (para o conjunto de validação) e spam.test (para o conjunto de teste). A função de aptidão para um indivíduo i deve ser calculada da seguinte forma:

• 1a Etapa: Treine o seu classificador Naive Bayes usando o conjunto spam.trein, porém considerando somente os atributos cujos valores correspondentes em i sejam iguais a 1.

• 2a Etapa: Utilize o classificador resultante da 1a Etapa para classificar os dados do conjunto spam.val. O valor de aptidão do indivíduo i será a acurácia do classificador Naive Bayes para essa tarefa.

• c) Executar o AG para a tarefa de seleção de atributos Fixe os seguintes parâmetros para o AG: - Número máximo de gerações: 40 - Tamanho da população: 15

Os outros parâmetros do AG devem ser escolhidos pelo grupo.

O AG deve ser executado 10 vezes, de forma independente. Para cada execução, registre qual foi o maior valor de aptidão encontrado e o fenótipo do respectivo indivíduo. (Se houver mais do que um indivíduo com o mesmo valor de aptidão, escolha um deles arbitrariamente).

Selecionados os 10 melhores indivíduos (um para cada execução do AG), aplique o classificador Naïve Bayes ao conjunto de teste, spam.test. Registre o número e a identificação dos atributos considerados e a acurácia obtida em cada um dos 10 experimentos de testes. Compare esses resultados com o desempenho do algoritmo quando este foi aplicado para todos os 57 atributos do conjunto original.

Observação final: A apresentação do grupo deve mostrar os resultados de todos os passos especificados neste documento, além das escolhas e discussões realizadas pelo grupo para cada um desses estágios.