1/18/2014IA - Prof. Paulemir Campos1 UPE – Caruaru – Sistemas de Informação Disciplina: Inteligência Artificial Prof.: Paulemir G. Campos Mineração de

04/11/23 IA - Prof. Paulemir Campos 1

UPE – Caruaru – Sistemas de InformaçãoDisciplina: Inteligência ArtificialProf.: Paulemir G. Campos

Mineração de Dados


Roteiro da Aula

Introdução; Pré-Processamento de Dados; Técnicas de Mineração de Dados; Aplicações; Referências.


Introdução


Explosão de Dados Ferramentas automáticas de coleta

de dados mais maturidade das tecnologias de bancos de dados;

Enorme quantidade de dados armazenados em bases de dados e outros meios de armazenamento;

Abundância de dados ao lado de escassez de conhecimentos.

Motivação


Soluções para a Explosão de Dados data warehouse e mineração de dados.

Assim, pretende-se descobrir conhecimentos (regras, regularidades, padrões) a partir de enormes bases de dados.

Motivação


KDD: Descoberta de Conhecimentos a partir de Banco de dados

Limpeza de Dados

Integração de Dados

Bases de dados

Data Warehouse

Dados Relevantes

Seleção

Mineração de Dados

Avaliação dos Padrões


Processo de KDD (Knowledge Discovery in Databases) Estudo do domínio de aplicação

Conhecimento a priori relevante; Objetivo da aplicação.

Seleção dos dados; Limpeza e pré-processamento dos

dados (60% do esforço); Redução e transformação de dados

Seleção de atributos; Redução de dimensionalidade.


Processo de KDD (Knowledge Discovery in Databases) Escolha dos modelos de mineração

Classificação, Regressão, Associação, Clustering, etc;

Escolhas dos algoritmos de mineração;

Mineração de Dados Busca de padrões interessantes.


Processo de KDD (Knowledge Discovery in Databases) Avaliação dos padrões e

apresentação do conhecimento Visualização, transformação, remoção

de padrões redundantes.

Uso do conhecimento descoberto.


Pré-Processamentode Dados


Os dados no mundo real estão “sujos”: Incompletos

ausência de atributos de interesse; apenas dados agregados; ausência de valores (missing values).

Ruidosos erros aleatórios; valores aberrantes (outliers);

Inconsistentes Divergências nas codificações ou nos nomes.

Introdução


Introdução Sem dados de boa qualidade o

resultado da mineração é pobre;

Assim, é importante efetuar um pré-processamento nos dados, antes de aplicar algum algoritmo de mineração de dados;


Introdução Os pré-processamentos mais

aplicados em bases de dados são:

Limpeza dos Dados; E, Transformação dos Dados.


Limpeza dos Dados Consiste basicamente em

Preencher dados ausentes; “Alisar” ruído; Identificar e/ou remover valores

aberrantes; E, resolver inconsistências.


Limpeza dos Dados Valores ausentes podem resultar de:

defeito do equipamento de coleta dos dados;

inconsistência com outros dados gravados e conseqüente supressão;

não entrada de dados devido a enganos; determinados dados podem não ser

considerados importantes no momento do registro, etc.


Limpeza dos Dados Tratamentos usuais para valores ausentes:

Eliminar o atributo ou mesmo o padrão; Preencher os valores ausentes manualmente; Usar uma constante global para representar os

valores ausentes (não recomendado, pois o sistema pode identificar esse valor como um conceito);

Usar a média (ou a moda); Usar a média (ou a moda) por classe.


Limpeza dos Dados Dados com ruído:

Consiste em erros aleatórios ou variabilidade presente nos descritores.

O ruído nos dados pode ser tratado pela técnica de alisamento.


Limpeza dos Dados Alisamento do ruído dos dados:

Consiste em distribuir dados ordenados em caixas tendo como referência os seus vizinhos.

Exemplo: Ordenação: 1, 1, 2, 3, 3, 3, 4, 5, 5, 7

Particionamento em “caixas”:

Resultado após alisamento:

321

7,5,5,4 3,3,3 2,1,1caixacaixacaixa

3caixa2caixa1caixa

5,5,5,5 3,3,3 1,1,1


Limpeza dos Dados Detecção e remoção de valores

aberrantes: Cluster

os valores são organizados em grupos; os valores isolados podem ser

considerados aberrantes. E, Inspeção Visual


Limpeza dos Dados Detecção e remoção de valores

aberrantes (Exemplo: uso de Cluster):


Limpeza dos Dados Inconsistências:

Mesmo atributo com diferentes codificações;

Mesmo padrão com classes diferentes;

Duplicidade de padrões de uma mesma classe.


Limpeza dos Dados Nestes casos, as inconsistências

podem ser resolvidas por:

eliminação de padrões redundantes; e, uniformização da codificação de

um dado atributo.


Transformação dos Dados É necessário para obter os dados

numa forma mais apropriada para a mineração de dados.

Em geral, transformação de dados envolve: Normalização; Redução de Dados.


Transformação dos Dados Normalização

Objetiva minimizar os problemas oriundos do uso de unidades e dispersões distintas entre os atributos.


Transformação dos Dados Redução dos Dados

Almeja obter uma representação reduzida da série de dados que é muito menor no volume, contudo produz os mesmos (ou quase os mesmos) resultados analíticos.


Transformação dos Dados Redução dos Dados

Alguns estratégias: Redução de Dimensionalidade:

Empregando técnicas de seleção de atributos;

Discretização: Representa valores contínuos em intervalos (de mesma largura ou freqüência). Os rótulos dos intervalos substituem os valores contínuos.


Técnicas de Mineração de Dados


Introdução Basicamente compreende os

diversos algoritmos de aprendizado de máquina, tais como: Classificação:

Regressão Linear; Redes MLP e RBF; Árvores de Decisão ID3 e C4.5; Regras de Classificação.


Introdução Basicamente compreende os diversos

algoritmos de aprendizado de máquina, tais como (Cont.): Cluster ou Agrupamento:

K-Means; Regras de Associação:

APRIORI

A seguir serão descritos alguns destes.


Regressão Linear Utiliza uma representação

matemática linear para detectar algum padrão presente nos dados observados.

Modelo clássico de regressão linear: Y = X. + onde: Y é o vetor n x 1; X é uma matriz n x (p+1) do

modelo; é uma matriz (p+1)x1 de parâmetros desconhecidos e é um vetor de erros aleatórios nx1.


Regressão Linear - Exemplo

50

80

100

10 15

60

40

20

020 25

Ye a rs e xp e rie nc e

Sala

ry (i

n $1

,000

)


Árvores de Decisão Um método "divide e conquista"

para o problema de aprendizado de um conjunto de instâncias independentes, onde a classificação é dada pelo nó folha, partindo-se da raiz da árvore.

Principais algoritmos: ID3 e C4.5.


Árvores de Decisão Algoritmo Básico:

A árvore é construída recursivamente de cima para baixo no modo dividir para conquistar;

No início todos os exemplos se encontram na raiz;

Os atributos são discretos (os atributos contínuos são discretizados previamente);

Os exemplos são particionados recursivamente com base em atributos selecionados;

Os atributos são selecionados heuristicamente ou através de uma critério estatístico (ex., ganho de informação).


Árvores de Decisão Condições de parada:

Todas as amostras de um dado nó pertencem a mesma classe;

Não há mais atributo disponível para futuras partições – usa-se voto da maioria para classificar a folha;

Não há mais exemplos disponíveis.


Árvores de Decisão - Exemplo


Regras de Classificação É uma alternativa popular para

árvores de decisão. Os antecedentes de uma regra

equivalem aos nós que vão sendo testados até se atingir o nó folha, que é o conseqüente dessa regra.


Regras de Classificação Exemplos:

Se Aumento_de_Salario_1_ano > 2.5 e Estututo_de_Feriados > 10 Então Candidato_a_Promocao = Bom

Se Aumento_de_Salario_1_ano =< 2.5 Então Candidato_a_Promocao = Ruim


K-Means Dado k, o algoritmo k-means é

implementado em 4 passos: Partição dos objetos em k grupos não

vazios; Defina as sementes como os centróides dos

grupos da partição atual; Associe cada objeto ao grupo cuja semente

é a mais próxima ao mesmo; Volte para o passo 2 até que não haja novas

associações de objetos a algum grupo.


K-Means - Exemplo

0

1

2

3

4

5

6

7

8

9

10

0 1 2 3 4 5 6 7 8 9 10

0

1

2

3

4

5

6

7

8

9

10

0 1 2 3 4 5 6 7 8 9 10

0

1

2

3

4

5

6

7

8

9

10

0 1 2 3 4 5 6 7 8 9 10

0

1

2

3

4

5

6

7

8

9

10

0 1 2 3 4 5 6 7 8 9 10


K-Means Pontos Fortes

É relativamente eficiente; Geralmente encontra um ótimo local.

Pontos Fracos Aplicável apenas quando a média é definida; É necessário especificar a priori k, o número

de grupos; É sensível a ruídos e valores aberrantes; Não é apropriado para a descoberta de

grupos não esféricos.


Regras de Associação Diferem das regras de

classificação devido a poderem predizer qualquer atributo, não somente a classe.

Assim, dão a liberdade de predizer também combinações de atributos.


Regras de Associação Conceitos Básicos:

Dados: (1) conjunto de transações, (2) cada transação é uma lista de itens (comprados por um cliente em uma visita);

Achar: todas as regras que correlacionam a presença de um conjunto de itens com a presença de outro conjunto de itens em uma mesma transação.


Regras de Associação Exemplo:

Dado: 98% das pessoas que compram pneus e auto-acessórios, também fazem algum serviço automotivo.

Achar: todas as regras X & Y Z com um mínimo de suporte e confiança

Suporte (support), s, probabilidade que uma transação contenha {X Y Z};

Confiança (confidence), c, probabilidade condicional que uma transação que contenha {X Y} também contém Z.


Regras de Associação Assim, a idéia é:

Achar os conjuntos de itens freqüentes (itemsets freqüentes): o conjunto de itens que tem um mínimo de suporte;

Um subconjunto de um itemset freqüente, também deve ser um itemset freqüente;

Achar iterativamente itemsets freqüentes com cardinalidade de 1 à k (k-itemset);

Usar os itemsets freqüentes para gerar as regras de associação.


Regras de Associação O Algoritmo APRIORI:

Passo de união (join): Ck é gerado, unindo Lk-1 com ele mesmo;

Passo de poda (prune): Qualquer (k-1)-itemset que não seja freqüente, não pode ser um subconjunto de um k-itemset freqüente.


O Algoritmo APRIORIExemplo

TID Items100 1 3 4200 2 3 5300 1 2 3 5400 2 5

Database D itemset sup.{1} 2{2} 3{3} 3{4} 1{5} 3

itemset sup.{1} 2{2} 3{3} 3{5} 3

Scan D

C1L1

itemset{1 2}{1 3}{1 5}{2 3}{2 5}{3 5}

itemset sup{1 2} 1{1 3} 2{1 5} 1{2 3} 2{2 5} 3{3 5} 2

itemset sup{1 3} 2{2 3} 2{2 5} 3{3 5} 2

L2

C2 C2Scan D

C3 L3itemset{2 3 5}

Scan D itemset sup{2 3 5} 2


Avaliação dos Modelos Os modelos podem ser avaliados

usando-se os seguintes critérios para partição dos conjuntos de treinamento e de teste: Holdout; Validação Cruzada (k-fold cross-

validation); Leave-one-out; e, bootstrap.


Aplicações


Análise de bases de dados e suporte à decisão Análise de Mercado

alvo de campanhas, análise de compras, segmentação do mercado, gerencia de relações com clientes, vendas cruzadas;

Análise de Risco fidelização de clientes, controle de qualidade,

análise de competitividade; Detecção de Fraude

Aplicações Potenciais


Referências Witten, I. H. e Frank, E. Data Mining:

Practical Machine Learning Tools and Techniques with Java Implementations. Morgan Kaufmann, 1999.

Han, J. e Kamber, M. Data Mining: Concepts and Techniques. Morgan Kaufmann, 2001.


Referências Notas de aulas dos profs. Francisco

A. T. de Carvalho, Paulo Adeodato e Jacques Robin de Mineração de Dados do Cin/UFPE.

Documents

1/18/2014IA - Prof. Paulemir Campos1 UPE – Caruaru – Sistemas de Informação Disciplina: Inteligência Artificial Prof.: Paulemir G. Campos Mineração de