Marcus Sampaio DSC/UFCG Alguns slides foram adaptados, traduzidos ou copiados de Pang-Ning Tan (ver Bibliografia) Sumário Contexto Outro Exemplo de Motivação Modelos de Conhecimento Algoritmos de Mineração de Dados Métricas de Mineração de Dados Questões em Aberto Marcus Sampaio DSC/UFCG Sumário Contexto Outro Exemplo de Motivação Modelos de Conhecimento Algoritmos de Mineração de Dados Métricas de Mineração de Dados Questões em Aberto Marcus Sampaio DSC/UFCG O Que É / Não É Mineração de Dados? O que não é? Marcus Sampaio DSC/UFCG O que é? – Achar um número de – Certos nomes são mais freqüentes em telefone em um catálogo certas regiões do Brasil (Cacciola, Armani, Gutierrez… na Grande São Paulo) Probabilidade – Procurar numa máquina de busca informação sobre “Amazônia” – Agrupar documentos por similaridade de contexto (p.e. Amazônia) – Reconhecimento de Padrões (“Pattern Recognition”) Marcus Sampaio DSC/UFCG • Confluência de várias disciplinas Machine Learning Probability / Pattern Recognition Data Mining Database Marcus Sampaio DSC/UFCG • Machine Learning – O conhecimento é induzido (treinado) de um conjunto de dados de treinamento (ctrein) • O histórico de mudanças de classes de software é um exemplo de conjunto de treinamento – O conhecimento induzido é validado com o auxílio de um conjunto de teste (ctest) ctrein ctest = • Se X Y foi induzido de um conjunto de treinamento, esta regra deve ser confirmada por um conjunto de teste – Uma vez validado, o conhecimento pode ser usado em diferentes aplicações • Análise de Impacto de Mudança de Software Marcus Sampaio DSC/UFCG • Padrão (“Pattern”) – A regra X Y é um padrão – A qualidade de um padrão é diretamente proporcional a seu suporte (repetição) • Banco de Dados (BD) – Desnormalizados • A repetição facilita o reconhecimento de padrões – O histórico de mudanças de classes de software é um BD desnormalizado – A conclusão é que os BDs relacionais normalizados não podem ser usados diretamente em MD Sumário Contexto Outro Exemplo de Motivação Modelos de Conhecimento Algoritmos de Mineração de Dados Métricas de Mineração de Dados Questões em Aberto Marcus Sampaio DSC/UFCG Marcus Sampaio DSC/UFCG • Um robot que prescreve lentes de contato – Oftalmologista: quais as condições gerais – padrões – pelas quais eu sempre tenho receitado lentes de contato duras? ou gelatinosas? ou não tenho recomendo o uso de lentes? Caracterização do Problema: Classificatório Tid 10 Idade Idade Acuidad Astigma Tipo e Visual tismo Lente Marcus Sampaio DSC/UFCG Acuidad Astigma Tipo e Visual tismo Lente 1 Jovem Míope Sim 1 Jovem Míope Não ? 2 Jovem Míope Sim 1 Jovem Hiperm Não ? 3 Velho Hiperm Não 2 Jovem Hiperm Sim ? 4 Velho Hiperm Não 2 Velho Míope Não ? 5 Velho Míope Não 2 Maduro Míope Não ? 6 Maduro Míope Não 1 Maduro Hiperm Sim ? 7 Jovem Hiperm Sim 3 8 Maduro Hiperm Não 3 9 Jovem Não 1 10 Maduro Míopr Sim 2 Hiperm 10 Conj. Treinamento Clasificador Induzido Conj. Teste Modelo Marcus Sampaio DSC/UFCG Conjunto de Treinamento idade acuidade visual astigmatismo taxa de produção de lágrima tipo de lente jovem míope não reduzida nenhum jovem míope não normal gelatinosa jovem míope sim reduzida nenhum jovem míope sim normal dura jovem hipermétrope não reduzida nenhum jovem hipermétrope não normal gelatinosa Marcus Sampaio DSC/UFCG jovem hipermétrope sim reduzida nenhum jovem hipermétrope sim normal dura maduro míope não reduzida nenhum maduro míope não normal gelatinosa maduro míope sim reduzida nenhum maduro míope sim normal dura maduro hipermétrope não reduzida nenhum Marcus Sampaio DSC/UFCG maduro hipermétrope não normal gelatinosa maduro hipermétrope sim reduzida nenhum maduro hipermétrope sim normal nenhum idoso míope não reduzida nenhum idoso míope não normal nenhum idoso míope sim reduzida nenhum idoso míope sim normal dura Marcus Sampaio DSC/UFCG idoso hipermétrope não reduzida nenhum idoso hipermétrope não normal gelatinosa idoso hipermétrope sim reduzida nenhum idoso hipermétrope sim normal nenhum Conhecimento Induzido Marcus Sampaio DSC/UFCG • se taxa_de_produção_de_lágrima = ‘reduzida’ então tipo_de_lente = ‘nenhum’ – Padrão expressado em forma de regra de classificação se ... então classe • Regra de Classificação é um dentre outros modelos de conhecimento – Um outro: Regra de Associação • A regra se verifica em todos os casos em que a taxa de produção de lágrima é reduzida? – Via de regra, não há certeza, apenas probabilidade • Quantas e quais são as outras regras para não receitar lente de contato (somente do ctrein, podemos extrair mais três regras – verifique) Marcus Sampaio DSC/UFCG • Quão confiável é uma regra de classificação? – se idade = ‘maduro’ e acuidade_visual = ‘hipermétrope’ e astigmatismo = ‘sim’ e taxa_de_produção_de_lágrima = ‘normal’ então tipo_de_lente = ‘nenhum’ • Ela se verifica em somente um caso do ctrein – Provavelmente, não tem validade estatística • Qual a freqüência mínima estatisticamente aceitável? – O conhecimento deve ser validado via o conjunto de teste Sobre os Conjuntos de Treinamento e Teste Marcus Sampaio DSC/UFCG • Note que os conjuntos de treinamento e teste apresentados certamente não têm validade estatística – Um exemplo de ‘brincadeira’ • Necessidade de um processo rigoroso de MD – Último item da disciplina Sumário Contexto Outro Exemplo de Motivação Modelos de Conhecimento Algoritmos de Mineração de Dados Métricas de Mineração de Dados Questões em Aberto Marcus Sampaio DSC/UFCG Marcus Sampaio DSC/UFCG • Tipos de modelo – Preditivo • Faz predição acerca de valores de dados usando resultados conhecidos de outros dados • Em geral, a modelagem é baseada em dados históricos, para fazer predição (ou previsão) sobre novos dados – Descritivo • Identifica padrões ou relacionamentos em dados, históricos ou não – Importante para se conhecer os dados Marcus Sampaio DSC/UFCG Modelo Preditivo Classificação Regressão Série Temporal Descritivo Clustering Síntese Regra de Associação Modelos em verde: o foco da disciplina Descoberta de Seqüência Marcus Sampaio DSC/UFCG • Modelos de classificação que serão vistos – Regra de Classificação – Árvore de Decisão – Bayes Simples (“Naive Bayes”) • Modelos de Classificação que não serão vistos – Rede Neural – ... • Modelo de Regra de Associação Sumário Contexto Outro Exemplo de Motivação Modelos de Conhecimento Algoritmos de Mineração de Dados Métricas de Mineração de Dados Questões em Aberto Marcus Sampaio DSC/UFCG Marcus Sampaio DSC/UFCG • Os algoritmos diferem segundo os modelos de conhecimento que eles induzem Modelo Algoritmo Regra de Associação Apriori Árvore de Decisão Id3, J48 Naive Bayes NaiveBayeSimple Regra de Classificação Prism Sumário Contexto Outro Exemplo de Motivação Modelos de Conhecimento Algoritmos de Mineração de Dados Métricas de Mineração de Dados Questões em Aberto Marcus Sampaio DSC/UFCG Marcus Sampaio DSC/UFCG • Dado um problema de mineração, há potencialmente uma grande quantidade de processos de MD que podem resolver o problema – Um processo de MD é, simplificadamente, uma tripla <preparação de dados, execução de um algoritmo de mineração de dados, avaliação dos resultados> • Processo de MD será visto no final da disciplina – Total possível de processos: No. de técnicas de preparação X no. de algoritmos de MD • Qual o melhor processo de MD para o problema? – A resposta depende das métricas de desempenho escolhidas Marcus Sampaio DSC/UFCG • Métricas – As tradicionais, como as de espaço e tempo, baseadas em análise de complexidade de algoritmo – Para algoritmos de classificação, a acurácia do conhecimento induzido • Acurácia de uma regra = No.de acertos treinamento (teste) / No. de casos cobertos de treinamento (teste) • Acurácia de um modelo (conjunto de regras) = No.de acertos treinamento (teste) / Tamanho do conjunto de treinamento (teste) • Precisão • “Recall” – Para algoritmos de análise de associação • Suporte • Confiança Sumário Contexto Outro Exemplo de Motivação Modelos de Conhecimento Algoritmos de Mineração de Dados Métricas de Mineração de Dados Questões em Aberto Marcus Sampaio DSC/UFCG Marcus Sampaio DSC/UFCG • Integração com SGBDs – Os algoritmos de MD não lêem diretamente de SGBDs • Dados são extraídos de um BD, via comandos SQL, e armazenados em um arquivo "flat", desnormalizado • O arquivo "flat"é a entrada para os algoritmos de mineração – Note que desnormalização (repetição) favorece a descoberta de padrões – BDOR é desnormalizado implicações? • Termos relacionais (<atributo1> <opcomp> <atributo2>) – Os termos dos modelos de MD são da forma <atributo> <opcomp> valor • Uma enorme simplificação – Objetivo: produzir algoritmos de complexidade baixa • Porém, limitados Marcus Sampaio DSC/UFCG • Escala – Algoritmos de MD sem escala são de limitada utilidade • Minas de Dados são Impuras – Dados do mundo real têm muita ‘sujeira’, e muito valor faltando (“null values”). Algoritmos de MD têm que ser capazes de trabalhar com minas impuras • Dinâmica dos Dados – Muitos algoritmos de MD trabalham com dados estáticos (comportamento invariável, ao longo do tempo). Isto pode não ser um modus operandi realista Marcus Sampaio DSC/UFCG • Facilidade de Assimilação – Embora alguns algoritmos possam trabalhar bem, eles podem induzir modelos muito complexos, de difícil assimilação mesmo por especialistas • Conhecimento inútil misturado com conhecimento útil • Padrões complexos • Padrões não sintetizados