Instituto Politécnico de Viana do Castelo
Licenciatura em ECGM
Trabalho Prático da disciplina de Inteligência Artificial
Gustavo Maçães, n.º 4843 Waldir Lima, n.º 5034
Ano lectivo 2006, 2007 Docente Responsável pela disciplina: Jorge Ribeiro |
[email protected]
20062007, Trabalho Prático da disciplina de Inteligência Artificial
Índice 1. Introdução e Objectivos.........................................................................................................3 2. Extracção de Conhecimento em Base de Dados ECBD ......................................................3 2.1. Metodologias Orientadas Para o Processo de ECBD .....................................................5 2.1.1. CRISPDM..............................................................................................................5 2.1.2. SEMMA ..................................................................................................................5 2.1.3. A Especificação PMML ...........................................................................................5 3. Caso de Aplicação Prática ....................................................................................................6 3.1 Caracterização do Caso de Estudo .................................................................................6 3.2 Análise do Conjunto de Dados ........................................................................................6 3.3 O Processo de Extracção de Conhecimento....................................................................6 3.4. O Modelo de Classificação.............................................................................................6 3.5. Conjunto de Casos de Teste Externo .............................................................................8 3.6. Classificação de Novos Casos .....................................................................................10 3.7. Interpretação de Resultados e Derivação de Regras ....................................................10 4. Conclusões .........................................................................................................................11 5. Bibliografia ..........................................................................................................................11
Gustavo Maçães, Waldir Lima
2/11
20062007, Trabalho Prático da disciplina de Inteligência Artificial
1. Introdução e Objectivos O presente trabalho consistia na execução de determinadas técnicas de data mining sobre um conjunto de dados, referentes à doença Hipotiroidismo (Hypothyroidism), retirados do Instituto Garvan de pesquisa médica, na Austrália. O trabalho enquadrase no âmbito da cadeira de Inteligência Artificial, leccionada no curso de Engenharia da Computação Gráfica e Multimédia, com o fim de nos familiarizarmos com as técnicas de data mining e inteligência artificial.
O objectivo do trabalho consistia na criação de um modelo que fosse capaz de classificar correctamente os casos dessa doença, de acordo com vários valores e medições feitas aos pacientes.
2. Extracção de Conhecimento em Base de Dados – ECBD A extracção de conhecimento em base de dados é uma área da inteligência artificial que engloba a mineração de dados (data mining) e as tarefas necessárias à mesma. Assim, o processo pode ser dividido em diferentes fases (processos aplicados sobre os dados): 1. Selecção e tratamento Redução do espaço de pesquisa através dos parâmetros de inclusão da informação pretendida; remoção de entradas duplicadas, limpeza dos dados, correcção de inconsistências.
2. Préprocessamento Diminuição da quantidade de dados a analisar pela discretização de valores contínuos, o que reduz o numero de linhas ou colunas a analisar.
3. Transformação Aumento da eficiência da pesquisa através da agregação dos dados em classes.
4. Data Mining Pesquisa de informação valiosa e padrões complexos em grandes quantidades de dados de forma automática, que não seriam detectáveis com uma análise manual
5. Interpretação Análise dos resultados obtidos, teste dos modelos com novos conjuntos de dados para determinar a sua performance, desempenho, precisão, eficiência e eficácia.
Os objectivos a atingir com o data mining são os seguintes: 1. Classificação Agrupamento dos dados em classes discretas através de funções, de acordo com um determinado modelo.
2. Previsão de séries temporais Inferência de valores futuros com base em padrões detectados nos dados.
3. Regressão linear Linearização das funções de relação entre variáveis (recta de melhor aproximação) para separação dos valores
Gustavo Maçães, Waldir Lima
3/11
20062007, Trabalho Prático da disciplina de Inteligência Artificial 4. Segmentação (Clustering) Detecção de grupos relativamente homogéneos nos dados, para aglomerar os dados num número finito de classes.
5. Associação Identificação de relações e dependências significativas entre variáveis, identificando grupos de dados interligados directa ou indirectamente entre si.
6. Sumariação Procura de uma descrição compacta para um subconjunto dos dados usando regras de resumo.
7. Visualização Representação dos resultados da análise do data mining de forma gráfica.
8. Detecção de desvios Descoberta de quebras em padrões relativamente regulares, útil para detecção de situações anómalas
Várias áreas relacionadas com o data mining são importantes na ECBD, nomeadamente: 1. Reconhecimento de padrões 2. Bases de dados e Data WareHouses 3. Estatísticas e matemática em geral 4. Sistemas periciais 5. Visualização de dados/computação gráfica 6. Aprendizagem automática a. Aprendizagem supervisionada Com um conjunto de treino fornecido previamente
b. Aprendizagem não supervisionada Feita sobre dados não classificados previamente, através de reconhecimento de padrões, procura de clusters, indução de regras de associação entre os dados, etc.
c. Aprendizagem por reforço Usando um sistema de tentativaeerro, o que gera um mecanismo de recompensas/punições, criando assim uma série de regras e conhecimento que se equilibram numa hierarquia à medida que o peso de cada uma vai variando.
Diversas técnicas são aplicadas aos processos de ECGB, especialmente na fase de data mining. Desses, podemos enumerar os seguintes: 1. Árvores de decisão 2. Algoritmos genéticos 3. Redes neuronais artificiais 4. Regras de associação A árvore de decisão é uma das técnicas mais usadas, pela simplicidade da sua interpretação e eficiência das implementações dos algoritmos já desenvolvidos. Basicamente tratamse de um conjunto de regras que seguem uma hierarquia de classes ou valores, expressando uma lógica simples condicional, sendo graficamente semelhantes a uma árvore invertida. Podem ser binárias ou não. Cada nó é um teste (condição) a um dos atributos, e os ramos descendentes
Gustavo Maçães, Waldir Lima
4/11
20062007, Trabalho Prático da disciplina de Inteligência Artificial
desse nó são os diversos valores possíveis para esse atributo. Numa aplicação de classificação, as folhas (terminais das ramificações) representam as classes.
2.1. Metodologias Orientadas Para o Processo de ECBD 2.1.1. CRISPDM CRISPDM é o acrónimo de Cross Industry Standard Process for Data Mining. É possivelmente a metodologia de ECBD mais usada. Consiste num ciclo de vida composto por seis fases: 1. Business understanding Conversão objectivos do negócio em objectivos de data mining
2. Data understanding Estudo dos dados e identificação da informação a extrair
3. Data preparation Obtenção e tratamento dos dados (selecção, tratamento, préprocessamento e transformação)
4. Modeling Selecção dos algoritmos de data mining e parametrização dos mesmos
5. Evaluation Apreciação do processo (precisão desempenho, eficiência, eficácia e utilidade)
6. Deployment Produção de relatórios da analise efectuada e elaboração de planas de aplicaçao do modelo à organização.
2.1.2. SEMMA SEMMA é uma metodologia alternativa para extracção de conhecimento em base de dados, cujas fases do ciclo de vida são descritas pelo próprio nome da metodologia: 1. Sample Selecção de uma amostra dos dados. Incluída na fase de data understanding do CRISP.
2. Explore Analise da amostra. Também incluída na fase de data understanding do CRISP.
3. Modify Tratamento, Préprocessamento e Transformação dos dados. Equivalente à fase de data preparation do CRISP.
4. Model Escolha de técnicas de data mining e parametrizaçao das mesmas de acordo com os objectivos de data mining. Equivalente à fase de Modeling do CRISP.
5. Assessment Avaliação dos resultados da extracção Equivalente à fase de Evaluation do CRISP.
2.1.3. A Especificação PMML A PMML é uma sublinguagem derivada do XML, não sendo propriamente uma metodologia, com um ciclo de vida e as fases associadas, mas sim uma linguagem standard para a descrição de modelos estatísticos e de data mining, de forma a permitir às diversas ferramentas existentes interagir umas com as outras e com dados tratados, independentemente dos formatos em que estão definidos.
Gustavo Maçães, Waldir Lima
5/11
20062007, Trabalho Prático da disciplina de Inteligência Artificial
3. Caso de Aplicação Prática 3.1 Caracterização do Caso de Estudo O caso apresentado para análise consistia de um conjunto de dados, referentes a uma amostra de pacientes da doença Hipotiroidismo (Hypothyroidism), retirados do Instituto Garvan de pesquisa médica, na Austrália. Com base nessa amostra, pretendiase desenvolver um modelo de data mining que futuramente classificasse correctamente os novos pacientes inseridos na base de dados como casos dessa doença (ou não), de acordo com vários indicadores recolhidos.
3.2 Análise do Conjunto de Dados Precedemos então à análise da amostra, averiguando a qualidade dos dados, consistência do conjunto (e, mais importante, inconsistências pontuais), tipo dos valores (discretos ou contínuos), quantidade de dados não preenchidos, etc.
3.3 O Processo de Extracção de Conhecimento Começámos por fazer uma limpeza dos dados iniciais, convertendo os ficheiros para o formato csv (comma separated values) aceite pelo Weka; fizemos alguns testes prévios de relação das variáveis, após os quais eliminámos uma coluna que estava vazia em todas as entradas (TBG); Também substituímos uma entrada da coluna idade que tinha um valor irreal (455), pela média das idades 51 (arredondamento da média de 51,446 – média já após a remoção do campo; com a inclusão desse campo a média teria um valor de 51,606, o que arredondaria para 52). Por último, removemos na coluna das classes o sufixo .XXXX (sendo X números diversos), o que fazia com que existissem várias dúzias de classes em vez de apenas 4 (negative, compensated_hypothyroid, primary_hypothyroid e secondary_hypothyroid).
3.4. O Modelo de Classificação Para produzir o modelo usámos árvores de decisão, mais propriamente o J.48. Testámos inicialmente o modelo aplicado à amostra com Crossvalidation a 10folds, com a idade discretizada em 5 intervalos de aproximadamente 20 anos; Obtivemos bons resultados (92,2% de casos bem classificados). Com 20 folds, obtivemos valores melhores. A seguir, testámos sem discretizar a idade, e obtivemos ainda melhores resultados. Abaixo apresentamos uma tabela com as estatísticas dos modelos testados: Nº folds
1 Precisão
2 kstat
3 MAE
4 RMSE
5 RAE
6 RRSE
10
92.5 %
0.097
0.0650
0.1816
88.939 %
95.357 %
20
92.8 %
0.147
0.0620
0.1755
84.685 %
92.166 %
10
99.6 %
0.970
0.0037
0.0450
5.053 %
23.652 %
20
99.6 %
0.970
0.0035
0.0454
4.835 %
23.817 %
Com a idade discretizada
Sem discretizar a idade
Gustavo Maçães, Waldir Lima
6/11
20062007, Trabalho Prático da disciplina de Inteligência Artificial 1
– Percentagem de casos correctamente classificados.
2
Kappa statistic mede a razão entre o excedente efectivo de acerto em relação à probabilidade, e o excendente máximo possível.
Assim, um valor mais próximo de 1 representa uma melhor taxa de acerto. 3
– Erro absoluto médio (mean absotute error). Quanto menor, melhor.
4
– Raiz do erro quadrático médio (root mean square error). Quanto menor, melhor.
5
– Erro relativo absoluto (relative absolute error). Quanto menor, melhor.
6
– Raiz do erro quadrático relativo (root relative square error). Quanto menor, melhor.
Abaixo se apresentam as árvores de decisão desses quatro modelos, para uma comparação visual.
Com a idade discretizada, a 10 folds
Com a idade discretizada, a 20 folds
Sem discretizar a idade, com 10 folds
Gustavo Maçães, Waldir Lima
7/11
20062007, Trabalho Prático da disciplina de Inteligência Artificial
Sem discretizar a idade, com 20 folds Como é evidente, decidimos manter o campo da idade discretizada. No entanto, ao analisar o modelo da árvore, notámos que certos parâmetros tinham um peso indevido, nomeadamente os booleanos “XXX measured”; o facto de ter sido medida ou não um certo sintoma num paciente não influencia por si só no resultado no diagnóstico, mas sim o valor da análise ao sintoma. Assim, decidimos remover essas colunas dos dados, tendo obtido resultados bastante promissores. Na próxima secção apresentamos os resultados dessa análise, em comparação com as análises feitas sem discretizar a idade.
3.5. Conjunto de Casos de Teste Externo Aplicando o mesmo método com o conjunto de casos de teste fornecido, conseguimos resultados menos exactos, o que era previsível já que antes estávamos a testar o modelo com o próprio conjunto inicial, que pode conter algum desvio, e ainda torna o modelo menos eficiente por considerar um conjunto de treino menor. Abaixo os valores da avaliação do modelo com o conjunto de casos externos, em comparação com a avaliação por cross
validation já acima apresentada: Método de av aliação
Precisão
kstat
MAE
RMSE
RAE
RRSE
Crossvalidation a 10 folds
99.56 %
.9700
.0037
.0450
5.1 %
23.7 %
Crossvalidation a 20 folds
99.56 %
.9700
.0035
.0454
4.8 %
23.8 %
Conjunto de casos de teste externo
99.36 %
.9563
.0040
.0513
5.5 %
26.9 %
Eliminadas as colunas “XXX measured”
99.56 %
.9698
.0120
.0520
16.5 %
27.3 %
Sem “XXX measured”, com caso de teste
99.44 %
.9621
.0129
.0576
17.6 %
30.2 %
Abaixo apresentamos as árvores de decisão induzidas com os modelos que ainda não tinham sido apresentadas (os três últimos da tabela):
Gustavo Maçães, Waldir Lima
8/11
20062007, Trabalho Prático da disciplina de Inteligência Artificial
Com as colunas “XXX measured”, usando um caso de teste externo
Sem as colunas “XXX measured”, com crossvalidation a 10 folds
Sem as colunas “XXX measured”, usando um caso de teste externo
Gustavo Maçães, Waldir Lima
9/11
20062007, Trabalho Prático da disciplina de Inteligência Artificial
Notese que a primeira árvore é idêntica às duas anteriores; no entanto, os valores de desempenho entre essa e aquelas variam, pois se altera o conjunto de casos de teste. Já as árvores induzidas com as colunas removidas são visivelmente mais simples (e são diferentes porque havendo menos dados, é mais significativa a diferença entre usar o todo ou parte do conjunto de dados de origem para induzir o modelo), e apesar de terem valores de desempenho inferiores, consideramos que são mais exactas pelos motivos acima apresentados (irrelevância das colunas “measured” para o diagnóstico).
3.6. Classificação de Novos Casos Para a classificação de novos casos, teve que ser usada a linha de comandos do Weka. Tivemos alguns problemas com os caminhos, pelo que tivemos que colocar os ficheiros na raiz do disco (C:) Criámos um ficheiro newC.arff com valores modificados por nós a partir das amostras disponibilizadas. Abaixo os resultados: > java weka.classifiers.trees.J48 —p 29 —l C:\classified_99percent.model —T C:\hypo.new.arff —d C:\hypo.newC.arff 0 negative 0.9995549205913682 ? 1 negative 1.0 ? 2 negative 0.9996022275258637 ? 3 negative 0.9995549205913682 ? 4 negative 0.9995549205913682 ? 5 negative 0.9995549205913682 ? 6 negative 0.9995549205913682 ? 7 negative 0.9995549205913682 ? 8 negative 0.9995549205913682 ? 9 negative 1.0 ?
3.7. Interpretação de Resultados e Derivação de Regras A árvore de decisão é a compilação das regras derivadas pelo modelo a partir dos casos de treino. Abaixo apresentamos as regras deduzidas pelo Weka: TSH <= 6: negative (1119.57/1.0) TSH > 6 | FTI <= 60: primary_hypothyroid (34.4/4.9) | FTI > 60 | | on thyroxine = t: negative (20.96) | | on thyroxine = f | | | thyroid surgery = t: negative (3.0) | | | thyroid surgery = f | | | | TT4 <= 133: compensated_hypothyroid (75.7/12.73) | | | | TT4 > 133: negative (4.37/0.04)
Podese assim detectar uma forte influência do parâmetro TSH; caso ele seja inferior ou igual a 6, o resultado é imediatamente negativo. Se o TSH for superior a 6 e o FTI for inferior ou igual a 60, o diagnóstico é também imediato: hipotiróide primária; caso contrário, ele estará, de acordo com outros factores, sujeito a uma hipotiróide compensada ou a um diagnóstico negativo. O caso de hipotiróide secundária não é contemplado, o que é natural visto que nos dados disponíveis havia apenas um caso dessa ocorrência, em 1258 amostras, de acordo com a matriz da confusão desse modelo.
Gustavo Maçães, Waldir Lima
10/11
20062007, Trabalho Prático da disciplina de Inteligência Artificial
4. Conclusões Após a execução do processo de extracção de conhecimento da base de dados e análise dos resultados obtidos, podemos concluir que os métodos de data mining foram satisfatoriamente eficientes. Conseguimos classificar correctamente os casos de teste com grande precisão, e derivar regras simples mas eficazes que permitem uma seriação rápida dos pacientes, pela análise dos parâmetros mais importantes. O trabalho não foi executado sem problemas; no entanto, fomos capazes de os resolver ou contornar, à medida das nossas limitações e das do software. A ajuda do docente também foi valiosa no esclarecimento de dúvidas que surgiram durante o desenvolvimento do trabalho. Ainda, é de referir a nossa tentativa de incursão na proposta alternativa de trabalho que incluía o estabelecimento de uma interface entre o .NET e o Java (Weka) para a implementação de uma aplicação de data mining para PDA; obtivemos resultados encorajadores de início, mas abandonámos o projecto a conselho do docente. Assim, podemos considerar que o trabalho foi executado com sucesso, tendo contribuído para uma melhor compreensão e assimilação na nossa parte dos conceitos envolvidos no processo de extracção de conhecimento em bases de dados.
5. Bibliografia ·
Apontamentos da disciplina
·
Wikipédia
Gustavo Maçães, Waldir Lima
11/11