Introdução ao Data Mining Introdução e conceitos exemplos, relação com outras áreas Alípio Jorge ATDMLP Doutoramento em Informática – MAP-I [email protected] Objectivos desta aula Entender o que é Data Mining (DM) e como surgiu Conhecer/Reconhecer tipos de problemas/tarefas de data mining Entender o input e o output de um processo de DM Compreender a relação entre DM e Machine Learning Compreender como pode funcionar um algoritmo de DM Alípio Jorge MAP 2 Exemplo 1 Vendas de veículos TT – mailing convida para test-drive – brindes para quem aparecer – linha grátis (800) Problema – – – – Fraca resposta Custos Dados: lista com 1M de pessoas (nome, morada) + dados: conhecimento público associado a códigos postais • demográficos e “psicograficos” – + dados: quem respondeu, quem ligou, quem comprou Alípio Jorge MAP 3 Exemplo 2 Fertilização “in vitro” – – – – recolha de óvulos na mulher fertilização externa -> produção de vários embriões selecção de embriões colocação de embriões no útero O problema – – – – Alípio Jorge seleccionar os embriões mais promissores. 60 variáveis descritivas dados históricos limites cognitivos do embriologista MAP 4 Análise Elementos dos exemplos: Situação prática. Problema de decisão/análise. Falta de conhecimento sobre o processo de decisão. Necessidade de obtenção do conhecimento explícito. Necessidade de automação do processo. Existência de dados. Utilização de uma técnica de data mining (DM) ou aprendizagem automática (AA). Machine Learning Alípio Jorge MAP 5 Fertilização in vitro Análise: – Situação operacional: • recolha de vários óvulos de uma mulher, para fertilização externa e posterior reimplantação no útero da mulher. – Problema de decisão: • Quais os embriões a seleccionar (quais os que têm mais hipóteses de sobreviver?) – Falta de conhecimento sobre o processo de decisão: • não há teoria (ou é incompleta) sobre como seleccionar os embriões. – Necessidade de obtenção do conhecimento explícito: • Validação dos critérios de decisão obtidos automaticamente – Necessidade de automação do processo: • demasiadas variáveis e conhecimento relacionado, limites cognitivos do embriologista. – Existência de dados: • Registos históricos. – Utilização de uma técnica de DM: • classificação. Alípio Jorge MAP 6 Porquê Data Mining? Grandes quantidades de dados (bases de dados) Conhecimento dos mercados / clientes – Sectores muito dependentes da informação • banca, seguros, telecomunicações, retalho – Forte pressão competitiva – Vantagem económica Respostas mais rápidas – Produtividade Personalização em massa – Promoção directa em função das compras Automação de tarefas /Apoio à decisão – Detecção de fraude – Classificação de corpos celestes Alípio Jorge MAP 7 O que é então Data Mining / Extracção de Conhecimento ? Procura de padrões úteis em grandes quantidades de dados – padrão: motivo que se repete com alguma frequência – útil: o padrão deve servir para resolver um problema classificação regressão clustering associação outros Alípio Jorge MAP 8 Data Mining como passo no processo KDD Fayyad & Simoudis (1997) Conhecimento Avaliação Data Mining Transformação & Redução Processamento e Limpeza Selecção e Amostragem Alípio Jorge MAP 9 Data mining: o ciclo age DB DB DB young young young young young young prepresbyopic prepresbyopic prepresbyopic prepresbyopic prepresbyopic presbyopic presbyopic presbyopic presbyopic presbyopic presbyopic DW spectacleprescrip myope myope myope hypermetrope hypermetrope hypermetrope myope no no yes no yes yes no astigmatism tear-prodrate reduced normal reduced normal reduced normal reduced contactlenses none soft none soft none hard none myope no normal soft hypermetrope no normal soft hypermetrope yes reduced none hypermetrope yes normal none myope myope hypermetrope hypermetrope hypermetrope hypermetrope no yes no no yes yes reduced normal reduced normal reduced normal none hard none soft none none flat dataset data warehouse data bases action IDA=bcde IMC=ade PROF>=3.5 alto medio baixo ESCOL=ace IDA=cde medio ACTIV>=2.5 baixo medio baixo Data Mining model evaluation decision support Alípio Jorge MAP 10 Alípio Jorge MAP 11 Ponto da situação Vimos – conceito de extracção de conhecimento de dados • dados (data mining) conhecimento – tipos de problemas/tarefas de data mining • classificação, regressão, ... Vamos ver – modelação dos dados – modelação do conhecimento Alípio Jorge MAP 12 Tipos de problemas de DM Classificação Regressão data mining dirigido Clustering Associação data mining exploratório Outros – o conjunto de tipos de problemas não é fechado Alípio Jorge MAP 13 Problemas de Classificação Dados – N casos de classes conhecidas Descobrir – descobrir uma relação funcional f(X) =y – que a um novo caso X, faça corresponder uma classe y sexo IDA m 40anos f 40anos f 50anos m 60anos f 60anos f 50anos m 40anos m 40anos m 40anos m 60anos m 60anos m 50anos f 40anos m 40anos f 50anos m 50anos Alípio Jorge m 40anos CIV c c s c c c c c c c c c v c c c d ESCOL EstSuperiores 12ano 9Classe 4Classe 4Classe EstSuperiores 4Classe EstSuperiores 4Classe EstSuperiores 4Classe 9Classe 4Classe 9Classe 12ano 12ano EstSuperiores PROF sup int sup semi-qual sem-prof sup esp-man sup esp-n-man sup semi-qual esp-n-man esp-n-man esp-n-man int int sup HDORM 8ha10h 6ha8h 6ha8h 6ha8h menos6h 8ha10h mais10h 6ha8h 6ha8h 8ha10h 8ha10h 8ha10h 8ha10h 6ha8h 6ha8h 6ha8h 6ha8h ACTIV pouca pouca pouca pouca alguma pouca alguma nenhuma pouca nenhuma pouca pouca nenhuma nenhuma alguma pouca pouca DESP TAB nao nao sim nao nao nao nao ex nao nao sim nao nao ex sim ex sim nao sim ex nao ex nao nao nao nao sim fuma sim ex sim nao simMAPfuma ALC bebe bebe nao bebe nao ocas bebe bebe bebe bebe ex bebe nao bebe bebe bebe bebe CAF sim sim sim nao sim sim sim sim sim sim sim sim sim sim sim sim sim Peso 70a60Kg 70a60Kg 50a60Kg mais80 50a60Kg 50a60Kg mais80 70a60Kg 80a70kg mais80 70a60Kg 70a60Kg 50a60Kg mais80 70a60Kg 80a70kg 70a60Kg ALT m160 m150 m150 m160 m150 m150 m170 m170 m160 m170 m180 m150 m160 m160 m150 m170 m160 3 classes: - alto - médio - baixo IMC normal excessopeso normal excessopeso excessopeso normal excessopeso normal excessopeso excessopeso normal excessopeso normal obesidade excessopeso normal normal Colest alto baixo baixo medio medio medio baixo baixo medio medio alto medio baixo alto medio medio alto 14 Classificação sexo IDA m 40anos f 40anos f 50anos m 60anos f 60anos f 50anos m 40anos m 40anos m 40anos m 60anos m 60anos m 50anos f 40anos m 40anos f 50anos m 50anos m 40anos CIV c c s c c c c c c c c c v c c c d ESCOL EstSuperiores 12ano 9Classe 4Classe 4Classe EstSuperiores 4Classe EstSuperiores 4Classe EstSuperiores 4Classe 9Classe 4Classe 9Classe 12ano 12ano EstSuperiores PROF sup int sup semi-qual sem-prof sup esp-man sup esp-n-man sup semi-qual esp-n-man esp-n-man esp-n-man int int sup HDORM 8ha10h 6ha8h 6ha8h 6ha8h menos6h 8ha10h mais10h 6ha8h 6ha8h 8ha10h 8ha10h 8ha10h 8ha10h 6ha8h 6ha8h 6ha8h 6ha8h ACTIV pouca pouca pouca pouca alguma pouca alguma nenhuma pouca nenhuma pouca pouca nenhuma nenhuma alguma pouca pouca DESP nao sim nao nao nao sim nao sim sim sim nao nao nao sim sim sim sim TAB nao nao nao ex nao nao ex ex nao ex ex nao nao fuma ex nao fuma ALC bebe bebe nao bebe nao ocas bebe bebe bebe bebe ex bebe nao bebe bebe bebe bebe CAF sim sim sim nao sim sim sim sim sim sim sim sim sim sim sim sim sim Peso 70a60Kg 70a60Kg 50a60Kg mais80 50a60Kg 50a60Kg mais80 70a60Kg 80a70kg mais80 70a60Kg 70a60Kg 50a60Kg mais80 70a60Kg 80a70kg 70a60Kg ALT m160 m150 m150 m160 m150 m150 m170 m170 m160 m170 m180 m150 m160 m160 m150 m170 m160 IMC normal excessopeso normal excessopeso excessopeso normal excessopeso normal excessopeso excessopeso normal excessopeso normal obesidade excessopeso normal normal Colest alto baixo baixo medio medio medio baixo baixo medio medio alto medio baixo alto medio medio alto IDA=bcde IMC=ade ESCOL=ace PROF>=3.5 alto medio baixo IDA=cde medio ACTIV>=2.5 baixo Previsão: Colest=alto Alípio Jorge baixo medio Novo caso: Sexo: m IDA: 39 … MAP 15 Classificação: breast cancer>diagnóstico Attributes 1. Sample code number 2. Clump Thickness 3. Uniformity of Cell Size 4. Uniformity of Cell Shape 5. Marginal Adhesion 6. Single Epithelial Cell Size 7. Bare Nuclei 8. Bland Chromatin 9. Normal Nucleoli 10. Mitoses 11. Class: Breast cytology – Análise de 699 exames Unif.cell.size< 2.5 Bare.nucl< 5.5 Unif.cell.shp< 2.5 Bland.chrom< 3.5 ben id number 1 - 10 1 - 10 1 - 10 1 - 10 1 - 10 1 - 10 1 - 10 1 - 10 1 - 10 benign, malignant Unif.cell.size< 4.5 mal Bare.nucl< 2.5 ben mal mal ben Alípio Jorge mal MAP 16 Típico problema de classificação Problema de classificação – um paciente que precisa de lentes de contacto, quero determinar o tipo de lentes que este paciente precisa Como obter automaticamente um modelo de classificação? – preciso de um histórico de receitas, que associa a cada paciente, o tipo de lentes receitadas: • Paciente tipo de lentes – forneço o histórico a um algoritmo de DM para problemas de classificação – obtenho um modelo de classificação age spectacleastigmatism tear-prodcontact- Como descrevo – um paciente? – tipo de lentes? Alípio Jorge young young young young young young pre- prescrip myope myope myope hypermetrope hypermetrope hypermetrope myope MAP no no yes no yes yes no rate reduced normal reduced normal reduced normal reduced lenses none soft none soft none hard none 17 Exemplos /instâncias Instância: exemplo de um conceito – concreto – “indivisível” Situação: modelo de decisão para atribuir crédito – qual é o conceito? – O que é um exemplo? Situação: prever clientes que vão abandonar o serviço – sequências temporais – multi registo Situação: prever subida da bolsa – a partir do histórico de cotações – individualizar os exemplos Alípio Jorge MAP 18 Conhecimento de fundo Background knowledge – conhecimento mais ou menos estável que pode servir para enriquecer os dados Situação: direccionar mailing – conhecimento genérico (dados demográficos) – multi tabela Situação: previsão da estrutura secundária de proteínas – conhecimento científico existente; proteinas homólogas Alípio Jorge MAP 19 Descrição de exemplos Linguagem de exemplos Tipicamente – conjunto de atributos (features, variáveis) – conjunto de valores para cada atributo – vectores de valores • <sol,23,baixa,forte> – conjuntos de pares atributo=valor • {tempo=sol, temp=23, humidade=baixa, vento=forte} Exercícios: carruagem de Michalsky, combóio, textos para classificar como “sobre DM” ou “outros”. Alípio Jorge MAP 20 Ponto da situação Vimos – como modelar os dados num problema de classificação / regressão – usamos sempre uma representação matricial (uma tabela) dos dados Vamos ver – limitações da representação matricial – tipos de atributos – 2 formatos populares Alípio Jorge MAP 21 Conjunto de exemplos (data sets) conjunto pré-definido de atributos – matriz de valores • n atributos • m exemplos – relação algébrica – tabela (BD) Vantagens – computacionais – simplicidade conceptual Restrições – a seguir Alípio Jorge MAP 22 Rep. Matricial: Restrições Combóios de Michalsky – representar um combóio de comprimento arbitrário. Atributos? Representações multi-relacionais – normais em BD Outro exemplo: encomendas - detalhes de encomenda – relações 1:N Alípio Jorge MAP 23 O formato “universal”: CSV (comma separated value) outlook, temperature, humidity, windy, play sunny, 85, 85, false, no sunny, 80, 90, true, no overcast, 83, 86, false, yes rainy, 70, 96, false, yes rainy, 68, 80, false, yes rainy, 65, 70, true, no overcast, 64, 65, true, yes sunny, 72, 95, false, no sunny, 69, 70, false, yes rainy, 75, 80, false, yes sunny, 75, 70, true, yes overcast, 72, 90, true, yes overcast, 81, 75, false, yes rainy, 71, 91, true, no Alípio Jorge MAP atributos valores e classe (classificação) 24 Um formato específico: ARFF do Weka % ARFF file for the weather data with some numeric features % @relation weather @attribute @attribute @attribute @attribute @attribute outlook { sunny, overcast, rainy } temperature numeric humidity numeric windy { true, false } play? { yes, no } @data % % 14 instances % sunny, 85, 85, false, no sunny, 80, 90, true, no overcast, 83, 86, false, yes rainy, 70, 96, false, yes rainy, 68, 80, false, yes rainy, 65, 70, true, no overcast, 64, 65, true, yes sunny, 72, 95, false, no sunny, 69, 70, false, yes rainy, 75, 80, false, yes sunny, 75, 70, true, yes overcast, 72, 90, true, yes overcast, 81, 75, false, yes rainy, 71, 91, true, no Alípio Jorge MAP comentários classe (classificação) 25 Dados de treino e dados de teste Exemplos de treino – para construir o modelo – training-set (AA) treino Exemplos de teste modelo teste – para avaliar o modelo – test-set (AA) avaliação Distribuição dos exemplos – geralmente assume-se dist. treino = dist. teste – concept drift (deriva conceptual) Alípio Jorge MAP 26 Ponto da situação Vimos – como modelar os dados (o input) Vamos ver – como modelar o conhecimento (o output) Alípio Jorge MAP 27 Regras de classificação (ou de decisão) Problemas de classificação Classe ou decisão Tipicamente SE {Conjunto de condições} ENTÃO {Conclusão} IF age=presbyopic and astigmatic=no THEN recommendation=soft Linguagem de hipóteses (LH) – genericamente, é a linguagem em que exprimimos os modelos – Conjuntos de regras SE-ENTÃO – Sequências de regras Alípio Jorge MAP 28 Regras de classificação Dado um exemplo E e uma regra A C – Uma regra aplica-se se A é verdadeiro em E. • A é uma generalização de E. • A regra “dispara” Regra: IF age=presbyopic and astigmatic=no THEN recommendation=soft – Exemplo 1: {age=presbyopic,spectacle-prescription=myope, astigmatic=no,tear-prod-rate=reduced} – Exemplo 2: {age=presbyopic,spectacle-prescription=myope, astigmatic=yes,tear-prod-rate=reduced} Alípio Jorge MAP 31 Conjuntos de regras Mais do que uma regra dispara – pode ser evitado – respostas contraditórias – combinação de respostas • votação • selecção por confiança da regra – listas de decisão (a ordem é importante) Exemplo: age=young, spect-presc=myope astigmatic=no, tear-prod-rate=reduced Alípio Jorge age=young, astigmatic=no -> rec.=soft age=young, astigmatic=yes -> rec.=none -> rec.=none MAP 32 Conjuntos de regras Votação – Seja E um exemplo para classificar – Recolhem-se as respostas dadas pelas regras que disparam – A resposta combinada é a resposta mais “votada” Vantagens – simplicidade na resolução de conflitos – diminuição da variância Desvantagens – duas regras com qualidades e significâncias diferentes têm o mesmo peso no voto (uma regra, um voto) Alípio Jorge MAP 33 Listas de decisão (decision lists) A ordem das regras é importante – Seja E um exemplo – Seja R1, R2, ..., Rn uma sequência de regras (lista de decisão) – A resposta é dada pela regra de índice mais baixo que dispara Exemplo: age=young, spect-presc=myope astigmatic=no, tear-prod-rate=reduced Alípio Jorge age=young, astigmatic=no -> rec.=soft age=young, astigmatic=yes -> rec.=none -> rec.=none default rule MAP 34 Outras linguagens de hipóteses: Árvores de decisão Alípio Jorge 35 Muitas outras representações de conhecimento Modelos baseados em instâncias Lógica de primeira ordem Discriminantes lineares Tabelas de probabilidades Redes bayesianas Redes neuronais ... Representações complexas põem problemas à extracção automática. Alípio Jorge 36 Em resumo Podemos – representar um modelo de classificação – usando conjuntos / sequências de regras de decisão Alípio Jorge MAP 37 Exercício: Mailing Uma distribuidora de revistas quer enviar material promocional por correio a potenciais clientes. Dispõe de uma lista de centenas de pessoas que poderão estar interessadas em assinar as revistas que disponibiliza. As revistas dividem-se em três categorias: técnicas, sociais e desportivas. Para baixar os custos da operação, a empresa decidiu, para cada pessoa da lista, enviar material promocional apenas de um tipo de revista ou de nenhum, no caso de não parecer um cliente promissor. Tendo em conta a experiência acumulada pelo marketing da empresa, o critério para distinguir as pessoas foi o seguinte: Enviou-se propaganda a revistas técnicas a quadro técnicos e professores, independentemente do sexo ou da idade. Às pessoas que não estivessem nestas condições, enviou propaganda a revistas desportivas a homens com idade entre os 20 e os 50 anos, e de revistas sociais a mulheres maiores de 23. 1. Identifique os atributos e os valores necessários para descrever cada um dos casos (os potenciais leitores). 2. Identifique as categorias (classes) em que foram divididos os indivíduos. 3. Represente o modelo de decisão como um conjunto de regras. 4. Implemente uma função em R que represente o conjunto de regras. 5. Coloque alguns exemplos num data frame e classifique-os. Alípio Jorge MAP 38 Exercício: Sucesso escolar Um estudo do sucesso escolar (*) numa faculdade revelou que os alunos com nota de entrada superior ou igual a 14 e com nota a matemática (uma disciplina do 1º ano) de pelo menos 13, terminam o curso em 4 anos, a menos que sejam trabalhadores estudantes. Estes terminam o curso em 5 anos no caso de terem nota de entrada pelo menos 15, e 6 ou mais anos caso contrário. Os restantes alunos terminam o curso em 4 anos se tiram 15 ou mais a matemática e em 5 anos caso contrário. 1. Identifique os atributos e os valores necessários para descrever cada um dos casos (os alunos). 2. Identifique as categorias (classes) em que foram divididos os indivíduos. 3. Represente o modelo de decisão como um conjunto de regras. 4. Implemente uma função em R que represente a árvore de decisão. 5. Coloque alguns exemplos num data frame e classifique-os. (*) estes dados não correspondem a uma situação real. Alípio Jorge MAP 39 Extracção de Regras de Classificação Métodos de Extracção de Conhecimento Alípio Jorge ATDMLP Doutoramento em Informática – MAP-I [email protected] Ponto da situação Vimos – o que é o data mining – dados (o input) • como representar um problema com um conjunto de dados – modelos (o output) • como representar um modelo de decisão ou outros Vamos ver – extracção de conhecimento / data mining • como chegar ao modelo a partir dos dados Alípio Jorge MAP 41 1R (regras muito simples para classificação) Exemplos numa matriz (classe no fim) Modelo outlook sunny sunny overcast rainy rainy rainy overcast sunny sunny rainy sunny overcast overcast rainy temperature hot hot hot mild cool cool cool mild cool mild mild mild hot mild humidity high high high high normal normal normal high normal normal normal high normal high windy FALSE TRUE FALSE FALSE FALSE TRUE TRUE FALSE FALSE FALSE TRUE TRUE FALSE TRUE play no no yes yes yes no yes no yes yes yes yes yes no outlook=sunny -> no outlook=overcast -> yes outlook=rainy -> yes Alípio Jorge MAP 42 1R Raciocínio – frequentemente um atributo é suficiente para determinar a classe • frequentemente também não Método Para cada atributo A Para cada valor V1, ..., Vn do atributo, construir a regra A=Vi -> C: C é a classe mais frequente nos exemplos com A=Vi calcular o erro da regra (#respostas erradas) / (#respostas) calcular o erro da hipótese baseada em A Escolher a hipótese com menor erro Alípio Jorge MAP 43 1R (execução) outlook sunny sunny overcast rainy rainy rainy overcast sunny sunny rainy sunny overcast overcast rainy Alípio Jorge temperature hot hot hot mild cool cool cool mild cool mild mild mild hot mild humidity high high high high normal normal normal high normal normal normal high normal high windy FALSE TRUE FALSE FALSE FALSE TRUE TRUE FALSE FALSE FALSE TRUE TRUE FALSE TRUE play no no yes yes yes no yes no yes yes yes yes yes no MAP outlook=sunny ->no outlook=overcast-> yes outlook=rainy -> yes (2/5) (0/4) (2/5) total de erros.................4/14 temperature........................5/14 humidity..............................4/14 windy..................................5/14 44 1R - Notas outlook Modelo é uma árvore de decisão com 1 nível sunny overcast no yes rainy yes Quase sem procura – número de hipóteses consideradas = número de atributos – MUITO eficiente Surpreendentemente competitivo (R. C. Holte, 1993) Valores desconhecidos – missing tratado como mais um valor. WEKA: OneR Atributos numéricos – discretização dinâmica. Alípio Jorge MAP 45 1R (com valores desconhecidos) outlook sunny sunny ? rainy rainy rainy ? sunny sunny rainy sunny overcast overcast rainy temperature hot hot hot mild cool cool cool mild cool mild mild mild hot mild humidity high high high high normal normal normal high normal normal normal high normal high windy FALSE TRUE FALSE FALSE FALSE TRUE TRUE FALSE FALSE FALSE TRUE TRUE FALSE TRUE play no no yes yes yes no yes no yes yes yes yes yes no outlook=sunny ->no outlook=overcast-> yes outlook=rainy -> yes outlook=missing -> yes (2/5) (0/2) (2/5) (0/2) total de erros.................4/14 temperature........................5/14 humidity..............................4/14 windy..................................5/14 Alípio Jorge MAP 46 Exercício Utilizar o OneR no Weka – com o weather – com o contact lenses Experimentar – com treino só – com treino e teste (70% para treino) Comparar – com os resultados do J48 Alípio Jorge MAP 47 “Conhecimento” como output Resultado de um método DM Dados Alípio Jorge Método DM MAP Conhecimento/ Modelo 48 Ponto da situação Vimos – um método muito simples que constrói modelos de classificação (muito simples) Vamos ver – um método mais sofisticado de obter regras de decisão Alípio Jorge MAP 49 Construção de uma regra usando procura Dado um conjunto de exemplos discretos (Matriz) Vamos fazer uma procura heurística (hill-climbing) Do mais geral para o mais específico, dada uma classe Model-driven Ilustração: exemplos weather.nominal Linguagem de hipóteses – atributos outlook, temperature, humidity, windy – respectivos valores – classe play com dois valores {yes,no} Alípio Jorge MAP 50 Construção de uma regra usando procura Dada uma classe (e.g. play=yes) – Regra maximamente geral -> class=yes – Cobre todos os exemplos – Qualidade da regra heurística erro = (#respostas erradas) / (#exemplos cobertos) • no caso é 5/14 – Vamos refinar a regra enquanto erro > 0 Alípio Jorge MAP 51 Construção de uma regra usando procura Refinamentos de [ -> play=yes] – especializações maximamente gerais da regra (10 hipóteses), – nível imediatamente abaixo do espaço de hipóteses -> play=yes er = 5/14 outlook=sunny-> play =yes er = 3/5 outlook=overcast-> play =yes er = 0/4 ... regra que procurávamos Alípio Jorge MAP windy=true-> play =yes er = 3/5 52 Construção de uma regra usando procura Suponhamos que a classe dada era play=no outl=sunny-> play=no, er = 2/5 outl =overcast-> play=no, outl =rainy-> play=no, er = 4/4 er = 2/5 ... -> play=no er = 9/14 hum=high-> play=no, er = 3/7 ... windy=true-> play=no, er = 3/6 • nenhuma regra satisfaz o critério de paragem • vamos continuar a refinar a regra que optimiza localmente a heurística Alípio Jorge MAP 53 Construção de uma regra usando procura Novos refinamentos outl=sunny-> play=no, outl =sunny,temp=hot -> play=no, er = 0/2 er = 2/5 outl =overcast-> play=no, outl =rainy-> play=no, er = 4/4 er = 2/5 ... -> play=no er = 9/14 hum=high-> play=no, outl =sunny,temp=mild -> play=no, er = 1/2 ... er = 3/7 ... windy=true-> play=no, outl =sunny,hum=high -> play=no, er = 0/3 er = 3/6 ... • duas regras sem erros • preferimos a que maximiza a cobertura Alípio Jorge MAP 54 Exercício Para encontrarmos esta regra tivemos de considerar 17 hipóteses. – Usamos uma abordagem model-driven. – Sugira uma abordagem data-driven que reduza o número de hipóteses a considerar. – Altere o pseudo-código e construa a árvore de procura. – Quantas hipóteses foram consideradas? – Pista: uma regra tem de cobrir pelo menos um exemplo. Escolha um exemplo como semente de construção da regra. Alípio Jorge MAP 55 Construção de uma regra Pseudo-código Dada a classe C Contruír uma regra R da forma [ ->C] Até R ser perfeita (erro=0), ou acabarem os atributos Para cada atributo A não ocorrendo em R, e para cada valor V Considerar juntar A=V ao antecedente de R Seleccionar o par A=V que minimiza o erro Juntar esse par ao antecedente de R Alípio Jorge MAP 56 Algoritmo de cobertura Voltemos à regra outlook=overcast-> play =yes – cobre 4 exemplos – como proceder para cobrir os restantes exemplos? Algoritmo de cobertura – retiro os exemplos cobertos pela primeira regra – construo uma regra para os restantes exemplos – repito o processo até não ter mais exemplos – também chamado separar-e-conquistar (separate-and-conquer) Alípio Jorge MAP 58 Algoritmo de cobertura Resultado outlook=overcast-> play =yes hum=normal, windy=false -> play=yes temp=mild, humidity=normal -> play=yes outlook=rainy -> play=yes -> play=no (cob. (cob. (cob. (cob. (cob. 4) 3) 1) 3, er. 2/3) 3) erro no treino = 2/14 Exercício – qual seria o resultado se tivéssemos começado com play=no ? Alípio Jorge MAP 59 Algoritmo de cobertura Pseudo-código Para cada classe C seja E conjunto de exemplos inicial Enquanto E contiver exemplos da classe C Criar uma regra para a classe C Retirar de E os exemplos cobertos pela regra WEKA: Prism Alípio Jorge MAP 60 Algoritmo de cobertura O resultado é uma lista de decisão – a primeira regra que dispara dá a resposta – o ordem é importante – cada regra é construída assumindo que as anteriores não se aplicam ao conjunto de exemplos corrente. Critério de paragem na construção de regras – regras perfeitas – problemas: ruído e sobre-ajustamento (overfitting) Alípio Jorge MAP 61 Métodos de Procura para data mining Data mining como aprendizagem de conceitos,aprendizagem de conceitos como procura Procura Alípio Jorge ATDMLP Doutoramento em Informática – MAP-I [email protected] Ponto da situação Vimos que – um modelo de classificação pode ser obtido a partir de dados – um modelo de classificação pode ser representado de várias maneiras – como obter um modelo de forma muito simples (OneR) – como obter um modelo usando procura heurística Vamos ver – como um modelo de classificação pode corresponder à descrição de um conceito – como a descrição de um conceito pode ser produzida a partir de exemplos usando procura Alípio Jorge MAP 63 Conceito: Arco Exemplos positivos Alípio Jorge Exemplos negativos MAP 64 Aprender o conceito arco Objectivo – encontrar uma teoria ou um modelo que defina o conceito arco. • conhecimento Dispomos de – exemplos de arcos (positivos), falsos exemplos de arcos (negativos) Objectivo (reformulado) – encontrar uma teoria ou um modelo que aceite os exemplos positivos e rejeite os negativos Alípio Jorge MAP 65 Conceito: Arco Exemplos positivos Exemplos negativos Hipótese 1: “tudo é um arco” – demasiado geral, não exclui exemplos negativos Hipótese 2: “nada é um arco” – demasiado específica,... Alípio Jorge MAP 66 Conceito: Arco Exemplos positivos Exemplos negativos Hipótese 3: “um arco tem um bloco rectangular na vertical (A) que apoia outro bloco rectangular na horizontal (C). Um terceiro bloco rectangular apoia também o bloco C e está afastado do bloco A” – cobre alguns exemplos positivos, mas não todos – não cobre exemplos negativos Alípio Jorge MAP 67 Conceito: Arco Exemplos positivos Exemplos negativos Hipótese 3: é demasiado específica vamos GENERALIZAR a hipótese: Hipótese 4: “um arco tem um bloco rectangular na vertical (A) que apoia outro bloco rectangular na horizontal (C). Um terceiro bloco rectangular apoia também o bloco C e está afastado do bloco A” Alípio Jorge MAP 68 Aprender o conceito de arco uma resposta Exemplos positivos Exemplos negativos Uma teoria para o conceito: ARCO – um arco tem um bloco rectangular na vertical (A) que apoia outro bloco na horizontal (C). Um terceiro bloco rectangular apoia também o bloco C e está afastado do bloco A Alípio Jorge MAP 69 Aprendizagem de conceitos Procura de um conceito que se ajuste aos dados. Espaço de conceitos/hipóteses: tudo é um arco ...tem um bloco rectangular ... ... ... tem um bloco triangular... ... tem um bloco rectangular e um bloco triangular ... ... nada é um arco Alípio Jorge MAP 70 Machine Learning Aprendizagem automática “Programas de computador que melhoram automaticamente o seu desempenho através da experiência” (Mitchell) “Um sistema que usa uma amostra de dados (conjunto de treino) para gerar uma base actualizada para melhorar o seu desempenho em dados subsequentes” (Michie) “A aprendizagem é qualquer alteração num sistema que permita que ele tenha um melhor desempenho na repetição de uma tarefa ou na realização de outra tarefa extraída da mesma população” (Simon) Alípio Jorge MAP 71 Aprendizagem como Procura Dados – um conjunto de hipóteses LH – uma relação de generalidade (R) – um objectivo (H tal que ...) Encontrar – H que satisfaça o objectivo Solução computacional: Hipotetisar e testar – Geração de hipóteses • data driven, model driven – Estratégia de procura – Selecção de hipóteses (critérios de preferência) Alípio Jorge MAP 72 Geração de hipóteses Data driven: guiada pelos dados (o típico) – as hipóteses são geradas em função dos exemplos que surgem Model driven: guiada pelo modelo – define-se a linguagem de hipóteses – as hipóteses são geradas segundo a definição da linguagem Exemplo – LH: regras da forma A->B, em que A é uma conjunção de pares atributo=valor e B é uma classe. – atributos vento={sim,não}, temp={alta,baixa} – classes: verdadeiro, falso Alípio Jorge MAP 73 Geração de hipóteses Suponhamos que começo pela hipótese mais geral Procuro uma regra para a classe verdadeiro Model driven ->verd vento=sim->verd vento=não->verd temp=alta->verd temp=baixa->verd Data driven (seguindo o exemplo {vento=sim,temp=alta,verd} vento=sim->verd ->verd temp=alta->verd Alípio Jorge MAP 74 Procura top-down em largura-primeiro Dados: H0 (maximamente geral), objectivo Obj, Relação de generalidade Fila <- [ ] H<-H0 Até H satisfazer Obj Gera hipóteses: especializações max. gerais de H Junta novas hipóteses ao fim de Fila Selecciona: H <- primeiro(Fila) retira primeiro da fila Repete retorna H Alípio Jorge MAP 75 Procura top-down em largura-primeiro (data-driven) X Y Z C 0 1 0 s 0 1 1 s Fila H [ ] ->s [X=0->s ; Y=1->s ; Z=0->s ] X=0->s 0 0 0 n 1 1 1 n [Y=1->s ; Z=0->s ; X=0&Y=1->s ; X=0&Z=0->s] Y=1->s [Z=0->s ; X=0&Y=1->s ; X=0&Z=0->s ; Y=1&Z=0->s] Z=0->s [X=0&Y=1->s ; X=0&Z=0->s ; Y=1&Z=0->s] X=0&Y=1->s satisfaz o objectivo zero erros Alípio Jorge MAP 76 Árvore de procura ->s X=0->s X=0&Y=1->s X=0&Z=0->s Y=1->s Z=0->s Y=1&Z=0->s X=0&Y=1&Z=0->s Alípio Jorge MAP 77 Procura top-down em largura-primeiro Completa – se existe solução encontra Pouco prática (em geral) – processamento – memória Procura bottom-up em largura primeiro – começa com hipótese maximamente específica Alípio Jorge MAP 78 Procura top-down em profundidade-primeiro Dados: H0 (maximamente geral), Obj, Rel. Gen. Fila <- [ ] H<-H0 Até H satisfazer Obj Gera hipóteses: especializações max. gerais de H Junta novas hipóteses ao início de Fila Selecciona: H <- primeiro(Fila) retira primeiro da fila Repete retorna H Alípio Jorge MAP 79 Procura top-down em profundidade-primeiro (data-driven) X Y Z C 0 1 0 s 0 1 1 s 0 0 0 n 1 1 1 n Fila H [ ] ->s [X=0->s ; Y=1->s ; Z=0->s ] X=0->s [ X=0&Y=1->s ; X=0&Z=0->s Y=1->s ; Z=0->s ] X=0&Y=1->s satisfaz o objectivo zero erros Alípio Jorge MAP 80 Procura top-down em profundidade-primeiro Problema dos caminhos infinitos retrocesso (backtracking) Pouco prática (em geral) – processamento – apesar de gastar pouca memória bottom-up boa base para procura heurística – associar a cada hipótese uma medida de qualidade q(H) Alípio Jorge MAP 81 Heurística [função] heurística: permite acelerar a procura, ainda que a custo da completude. Na Aprendizagem: – uma função heurística pode medir a qualidade de cada hipótese. – Exemplos: errosH q( H ) 1 respostasH Alípio Jorge q( H ) Com pletude( H ) Acerto( H ) respostasH Com pletude( H ) todos_ os _ exem plos errosH Acerto( H ) 1 respostasH MAP 82 Procura hill-climbing: uma proc. heurística Dados: H0 (maximamente geral), Obj, Rel. Gen. Fila <- [ ] H<-H0 Até H satisfazer Obj Gera hipóteses: especializações max. gerais de H Junta novas hipóteses a Fila Selecciona : HFila : argmax q(H) esvazia fila (poupa memória) Repete retorna H Alípio Jorge MAP 83 Procura hill-climbing, q=%resp. certas (data driven) X Y Z C 0 1 0 s 0 1 1 s 0 0 0 n Fila H [ ] ->s [X=0->s (0,67) ; Y=1->s (0,67); Z=0->s (0,5)] [ X=0&Y=1->s (1); X=0&Z=0->s (0,5)] 1 1 1 n X=0->s X=0&Y=1->s satisfaz o objectivo zero erros Alípio Jorge MAP 84 Procura hill-climbing: uma proc. heurística Incompleto mínimos locais sem retrocesso: greedy search muito popular em IA – computacionalmente atractiva • processamento e memória – bons resultados na prática Alípio Jorge MAP 85 Outras estratégias de procura heurísticas – Best-first – beam-search – A* completas – iterative deepening novos paradigmas – algoritmos genéticos – simulated annealing – tabu search Alípio Jorge MAP 86 Recapitulando Ordem de exploração das hipóteses a – Profundidade primeiro b d e a, b, d, e, c, f, g c f árvore de procura – Largura primeiro g a, b, c, d, e, f, g – Hill Climbing • assumindo q(c)>q(b), q(f)>q(g) a, c, f Alípio Jorge MAP 87 Bias (viés, enviesamento) – Qualquer base para restringir o tamanho do espaço de procura ou para preferir uma hipótese a outra, que não seja a consistência com os dados, designa-se por bias O bias é necessário ... – – – – escolha de uma linguagem de conceitos a ordem de procura critérios de paragem grande número de hipóteses compatível com os dados ...e uma fonte de problemas – na origem de algum erro sistemático – nenhum bias é sempre melhor que os outros O bias permite escolher uma de entre as hipóteses aceitáveis Alípio Jorge MAP 88 Espaço de versões Hipóteses demasiado gerais Versões aceitáveis do conceito Hipóteses demasiado específicas Alípio Jorge MAP 89 Tipos de bias Bias de linguagem – expressividade – problemas computacionais – legibilidade Bias de procura – não queremos procurar por todo o espaço – heurísticas – top-down, bottom-up Navalha de Occam – preferir as hipóteses mais simples entre outros... Alípio Jorge MAP 90 Exercícios Qual seria o resultado se a procura no algoritmo de aprendizagem (transp. 20) para o conceito “dia bom para o meu desporto favorito” fosse do mais geral para o mais específico? Quais são as versões que se ajustam aos dados? Qual a diferença entre os algoritmos de largura primeiro e profundidade primeiro? Proponha um algoritmo tipo hill-climbing para o mesmo problema. Qual poderia ser a heurística? Qual seria a sucessão de hipóteses visitadas? Encontre um conjunto de exemplos consistente (sem exemplos que sejam simultaneamente negativos e positivos) para o qual não seria possível encontrar uma hipótese compatível no bias de linguagem dado. Proponha outro bias de linguagem que permita capturar o conceito. Ou seja, defina uma linguagem de hipóteses mais expressiva que contenha uma hipótese que cubra todos os exemplos dados. Alípio Jorge MAP 91 Termos importantes – – – – – – Conceito, hipótese relação de generalidade espaço de hipóteses/conceitos linguagem de hipóteses Exemplos positivos, exemplos negativos procura • • • • top-down largura-primeiro, comprimento-primeiro heurística hill-climbing – bias Alípio Jorge MAP 92 Recursos Web – http: //www.kdnuggets.com Alípio Jorge MAP 93
Download
