KDD. Fases limpeza etc. Datamining OBJETIVOS PRIMÁRIOS. Conceitos o que é? - PDF
Download "KDD. Fases limpeza etc. Datamining OBJETIVOS PRIMÁRIOS. Conceitos o que é?"
Giulia Arruda Caminha
1 KDD Conceitos o que é? Fases limpeza etc Datamining OBJETIVOS PRIMÁRIOS
2 TAREFAS PRIMÁRIAS Classificação Regressão Clusterização
3 OBJETIVOS PRIMÁRIOS NA PRÁTICA SÃO DESCRIÇÃO E PREDIÇÃO Descrição Wizrule encontrar os padrões de interpretação humana a partir da descrição dos dados (por ex.: A produção de um determinado cereal na última colheita pode ser apontado a partir de um conjunto de dados armazenados). Predição Wizwhy e Predict utiliza-se algumas variáveis ou campos na base de dados para predizer o desconhecido ou valores futuros de outras variáveis de interesse (por ex.: A previsão da produção do mesmo cereal na próxima colheita a partir do conjunto de dados usado na descrição).
4 Problemas baseados em descoberta de conhecimento pode-se destacar: Tarefas primárias A) Detecção de desvio identifica mudanças nos padrões anteriormente detectados (relacionado análise estatística). Técnicas clássicas teste de significância (médias, e desvios de padrões,usa-se método estatístico para mineração de dados).
5 Problemas baseados em descoberta de conhecimento pode-se destacar: Tarefas primárias B) Clustering parecido com segmentação de bases de dados, MAS PARTE DE CONJUNTOS DE CASOS que não possuem resposta previamente conhecidas (usa métodos de REDES NEURAIS).
6 Problemas baseados em descoberta de conhecimento pode-se destacar: Tarefas primárias Cluster existe um número finito de categorias ou agrupamentos (cluster) para descrever os dados. As categorias podem ser mutualmente exclusivas e exaustivas ou consistir numa representação como categorias hierárquicas ou sobrepostas.
7 Problemas baseados em descoberta de conhecimento pode-se destacar: Cluster Exemplo: subpopulações homogêneas para consumidores do mercado. Débitos X X Cl 3 X X X X X Cl 1 Cl 2 - X os membros das classes não são mais conhecidos - Cluster se sobrepõem Salários O relacionamento do Cluster é a tarefa de estimativa da probabilidade multi-variada de todas variáveis/campos dos BD.
8 Problemas baseados em descoberta de conhecimento pode-se destacar: Tarefas primárias C) Regras de associação são associações na forma de regras de decisão. Normalmente não existe informação armazenada na BD sobre as características que definem estas regras (é um problema de descoberta de conhecimento normalmente usa-se Árvore de decisão).
9 Problemas baseados em descoberta de conhecimento pode-se destacar: Tarefas primárias D) Classificação função de aprendizado que mapea um dado em uma das diversas classes pré-definidas (descobrir o relacionamento entre os registros previsores (qualitativos) e o atributo objetivo (meta) usando registros cuja classe é conhecida. (Café, leite e pão. SE comprar café e pão ENTÃO compra manteiga). Exemplo no caso de empréstimo veja abaixo: Débitos (empréstimo) X X * X Decisão linear Salários
10 Problemas baseados em descoberta de conhecimento pode-se destacar: Tarefas primárias E) Regressão é a função de aprendizado que mapea os dados com predição variável de valores reais - Exemplos de aplicação de regressão: estimar a probabilidade de um paciente sobreviver dado o resultado de um conjunto de exames. predizer a demanda do consumo de um novo produto em função de despesas feitas. no nosso exemplo de empréstimos.
11 Problemas baseados em descoberta de conhecimento pode-se destacar: Tarefas primárias Débitos X X X X Salários O débito total é visto como uma função linear da renda, a predição é pobre pois existe uma correlação fraca entre duas variáveis.
12 Problemas baseados em descoberta de conhecimento pode-se destacar: Tarefas primárias Tarefas de DM Algoritmos Associados Associações Classificação Clusterização Estatística, Teoria dos Conjuntos Árvores de Decisão, RN Redes Neurais Estatística Análise de cestas de mercado Mercado alvo, Taxas de risco Segmentação de mercado Modelagem de dependência Regressão Linear e não linear RN Colocação de Clientes, modelos de estimativa de preço controle de processo
13 Algoritmo (método de busca): Árvore de Decisão / Regras de Produção - Algoritmo ID3 (Iterative Dichotomizer 3) Você em DM : tem a TAREFA e tem os Algoritmos. Os ALGORITMOS DM por sua vez tem seus componentes primários que são: MODELOS DE REPRESENTAÇÃO MODELOS DE AVALIAÇÃO MODELOS DE BUSCA UM PONTO IMPORTANTE É QUE O ANALISTA DE DADOS COMPREENDA A REPRESENTAÇÃO que está utilizando, pois esta pode ser inerente a um modelo particular (para que não ocorra a sobreposição dos dados de Treinamento por exemplo).
14 MODELOS DE REPRESENTAÇÃO Linguagem L para descrever padrões possíveis de serem descobertas. Na representação da ÁRVORE DE DECISÃO usa-se uma divisão de nós univariados (campos simples).
15 MODELOS DE AVALIAÇÃO Este modelo estima quão bem um determinado padrão (o modelo e seus parâmetros) pode encontrar o critério procurado pelo processo KDD. Pode-se utilizar critérios lógicos ou estatísticos. O princípio da máxima probabilidade escolhe os parâmetros para os modelos que produzem os melhores ajustes para o treinamento dos dados.
16 MODELOS DE BUSCA É determinado por dois componentes: parâmetros de busca e modelos de busca. Os algoritmos devem buscar parâmetros de busca que otimizem o critério do modelo de avaliação dada. Os métodos iterativos são usados de forma geral (por exemplo: método do gradiente descendente retropropagação dos erros em Redes Neurais).
17 TÉCNICAS DE DM O BD é um estoque de informações. A informação recuperada não é obrigatoriamente uma cópia exata das informações armazenada no BD, mas sim a informação que pode ser INFERIDA a partir desses dados.
18 DUAS TÉCNICAS DE INFERÊNCIA SE DESTACAM: DEDUÇÃO E INDUÇÃO Dedução infere a partir de uma seqüência lógica da informação na Base de Dados. Por exemplo nos DBMS relacionais, o operador JOIN aplicado em duas Tabelas relacionais, onde a 1ª administra as relações entre solicitantes de empréstimos e agências bancárias e a 2 administra as relações entre agências e gerentes, INFERE a relação entre solicitantes de empréstimos e gerentes.
19 DUAS TÉCNICAS DE INFERENCIA SE DESTACAM: DEDUÇÃO E INDUÇÃO Indução é a técnica para inferir informação que é GENERALIZADA a partir da informação na base de dados. Por exemplo: a partir das tabelas citadas, pode ser inferido que, cada solicitante de empréstimo tem um gerente responsável. Lembrar que isto não está no BD
20 DUAS TÉCNICAS DE INFERENCIA SE DESTACAM: DEDUÇÃO E INDUÇÃO A diferença mais importante entre DEDUÇÃO e INDUÇÃO é que no primeiro caso, os resultados formados por declaração do mundo real são provavelmente corretas, desde que o BD esteja correto. Enquanto a INDUÇÃO resulta em declarações que são suportadas pelo BD mas não são necessariamente verdades no mundo real. (Veja o exemplo do aquario!).
21 MÉTODOS DE BUSCA EM DM Estatísticos, métodos Lineares Regressão Linear e análise linear de discriminante (superfície de regressão ou classificação é um plano); Métodos não paramétricos (livres do modelo) RNV+P; Métodos da projeção de busca; Métodos das Redes Polinomiais GMDH (Group Method of Data Handling); ALGORITMOS GENÉTICOS = algoritmo de busca alternativa (heurística).
22 MÉTODO DAS ÁRVORES DE DECISÃO E REGRAS Forma de representação simples e fácil de ser compreendida pelos usuários mas pode reduzir a forma funcional do modelo (poder de aproximação do modelo). Por exemplo quando se adotou a divisão do limite sobre o salário t e se aplicou sobre esta variável o conjunto de dados de empréstimos, limitou-se severamente o tipo de classificação através das fronteiras induzidas. As árvores e as regras não são usadas em geral para descrição dos BD pois em geral é um número muito grande de regras.
23 ID3 Foi desenvolvido por Ross Quinlan,1983, e apresenta resultados práticos. Início para classificar movimentos do Xadrez, mas despertou interesse de vários pesquisadores e hoje existe uma centenas de correlatos.
24 ID3 Objetivo: Formar uma árvore de decisão que classifique uma lista de exemplos, ou seja, a partir de um conjuntos de exemplos o algoritmo INDUZ regras do tipo SE...ENTÃO onde cada regra corresponde a um caminho da árvore de decisão.
25 ID3 O conjunto de exemplos é a REPRESENTAÇÃO DO PROBLEMA e tem a forma de uma matriz, onde cada coluna é uma característica, ou atributo do problema e cada linha descreve um exemplo através dos valores dos atributos e sua conclusão, ou classificação.
26 ID3 A qualidade das regras produzidas pelo algoritmo ID3 depende diretamente da qualidade do conjunto de exemplos. A grande VANTAGEM deste algoritmo é a capacidade de gerar uma árvore de decisão a partir de poucos exemplos. Se se tem um conjunto de centenas ou milhares de exemplos o processo ficará difícil e demorado, o ID3, então, utiliza subconjuntos, chamadas janelas.
27 FUNCIONAMENTO BÁSICO DE ALGORITMO 1 Seleciona-se um conjunto janela (subconjunto se for o caso) do conjunto de todos os exemplos. 2 Aplica-se o algoritmo de classificação dos atributos no conjunto janela, para gera a árvore de decisão na forma de regras. 3 Verifica-se a validade das regras, procurando exceções no conjunto de todos os exemplos (discutidas com o especialista). 4 Se existirem exceções, insere algumas delas no conjunto janela e volta-se ao passo 2. OBS.: para escolha do conjunto janela, deve-se levar em conta a proporção da ocorrência de cada classe no conjuntos de exemplos.
28 CLASSIFICAÇÃO DOS ATRIBUTOS A) Encontrar o atributo mais DISCRIMINATÓRIO, ou seja, o que representa menor incerteza com relação às classes, e dividir a janela em sub-janelas referentes a cada valor deste atributo.uma pessoa quer saber se uma empresa vai dar lucro ou não! (A tabela a seguir reflete o conhecimento do assunto.)
29 CLASSIFICAÇÃO DOS ATRIBUTOS L U C R O ID A D E C O M P E T IÇ Ã O T IP O N V e lh o N S o ftw a re N M é d io S S o ftw a re S M é d io N H a rd w a re N V e lh o N H a rd w a re S N o v o N H a rd w a re S N o v o N S o ftw a re S M é d io N S o ftw a re S N o v o S S o ftw a re N M é d io S H a rd w a re N V e lh o S S o ftw a re
30 CLASSIFICAÇÃO DOS ATRIBUTOS Uma pessoa quer saber de uma empresa vai dar lucro ou não! DIALOGO COM ESPECIALISTA E. A empresa é de Hardware ou Software? Pessoa Software E. Seus produtos são novos, velhos ou médio? Pessoa Médios E. Os produtos tem alguma competição significativa? Pessoa Não E. De acordo com os meus conhecimentos esta empresa tende a ter lucro.
31 CLASSIFICAÇÃO DOS ATRIBUTOS Janela classe idade = médio LUCRO IDADE COMPETIÇÃO TIPO Não Médio Sim Software Sim Médio Não Hardware Sim Médio Não Software Não Médio Sim Hardware
32 CLASSIFICAÇÃO DOS ATRIBUTOS B) Esse processo se repete a cada sub-janela, até que todas contenham somente elementos de mesma classe;
33 CLASSIFICAÇÃO DOS ATRIBUTOS C) Verifica-se no conjunto de todos os exemplos aqueles que não são classificados pela árvore fornecida. Então uma seleção destes é feita de forma a incluí-los no conjunto de janelas. A partir da nova janela, o algoritmo formará uma nova árvore de decisão e o processo de classificação se repetirá até que todos os exemplos sejam classificados. A árvore de decisão resultante representa o conjunto de regras que constitui o conhecimento correspondente à lista de exemplos.
34 MÉTODO UTILIZADO PARA ENCONTRAR O ATRIBUTO MAIS DISCRIMINATORIO - cálculo de entropia, onde o atributo de menor entropia é o que contem maior quantidade de informação A entropia de um atributo A é a média ponderada das entropias dos valores de A. Por exemplo a entropia de IDADE é a média ponderada das entropias de média, velho e novo.
35 MÉTODO UTILIZADO PARA ENCONTRAR O ATRIBUTO MAIS DISCRIMINATORIO - cálculo de entropia, onde o atributo de menor entropia é o que contem maior quantidade de informação Matematicamente N n.º valores do atributo A H(C!A) = P(Vi) e H (C!vi) P(Vi) é a probabilidade do valor vi aparecer no conjunto janela. H(C!vi) é a entropia do valor vi de A dada pela expressão M n.º de classes. H(C!vi) = N i= 1 M j= 1 P(Cj!Vi) * - log 2 P(Cj!Vi)
36 MÉTODO UTILIZADO PARA ENCONTRAR O ATRIBUTO MAIS DISCRIMINATORIO - cálculo de entropia, onde o atributo de menor entropia é o que contem maior quantidade de informação P(Cj!Vi) é a probabilidade de se ter um exemplo com valor Vi concluindo Cj. Existem muitas deficiências no algoritmo ID3 as regras produzidas não são probabilísticas; a freqüência de um exemplo não é relevante.
37 MÉTODO UTILIZADO PARA ENCONTRAR O ATRIBUTO MAIS DISCRIMINATORIO - cálculo de entropia, onde o atributo de menor entropia é o que contem maior quantidade de informação Para melhorar deve-se calcular o grau de certeza das regras. Para calcular os FC usa-se um algoritmo D-5 baseado na teoria das evidências de Dempster-Shafer. (FC de uma regra é calculado a partir da evidência com que cada condição da regra contribui para a conclusão da regra) A árvore pode mostrar algumas inconsistências, atributos com valores iguais e conclusões diferentes (o especialista resolve).
38 MÉTODO UTILIZADO PARA ENCONTRAR O ATRIBUTO MAIS DISCRIMINATORIO - cálculo de entropia, onde o atributo de menor entropia é o que contem maior quantidade de informação Por exemplo a entropia do atributo IDADE H(Classe=sim! IDADE=médio) = -1/2 log 2 1/2 = 0,5 H(Classe=não! IDADE=médio) = -1/2 log 2 1/2 = 0,5 H(Classe! IDADE=médio) = 0,5 + 0,5 =1 (soma dos dois) H Classe! IDADE=novo = - 3/3 log 2 3/3-0 = 0 H Classe! IDADE=velho = - 3/3 log 2 3/3-0 = 0 H(Classe! IDADE) = 4/10 x 1 + 3/10 x 0 + 3/10 x 0 = 0,4 Dos outros H(Classe! Competição) = 0,8752 H(Classe! Tipo) = 1
39 MÉTODO UTILIZADO PARA ENCONTRAR O ATRIBUTO MAIS DISCRIMINATORIO - cálculo de entropia, onde o atributo de menor entropia é o que contem maior quantidade de informação Então IDADE será a raiz da árvore de decisão. IDADE Como a entropia Novo e Velha é Zero então já estão classificados NOVO MÉDIO VELHO Resta Janela para IDADE = Médio
40 MÉTODO UTILIZADO PARA ENCONTRAR O ATRIBUTO MAIS DISCRIMINATORIO - cálculo de entropia, onde o atributo de menor entropia é o que contem maior quantidade de informação H(Classe! Competição) = 0 Então competição é o 2º H(Classe! Tipo) = 1 IDADE NOVO MÉDIO VELHO COMPETIÇÃO LUCRO = NÃO LUCRO = SIM