1/18/2014MD - Prof. Paulemir Campos1 UPE – Caruaru – Sistemas de Informação Disciplina: Mineração de Dados Prof.: Paulemir G. Campos Modelos de Mineração

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

UPE – Caruaru – Sistemas de InformaçãoDisciplina: Mineração de DadosProf.: Paulemir G. Campos

Modelos de Mineração de Dados


Roteiro da Aula

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


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


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/2014MD - Prof. Paulemir Campos1 UPE – Caruaru – Sistemas de Informação Disciplina: Mineração de Dados Prof.: Paulemir G. Campos Modelos de Mineração