UPE – Caruaru – Sistemas de Informação
Disciplina: Mineração de Dados
Prof.: Paulemir G. Campos
Modelos de Mineração
de Dados
11/4/2015
MD - Prof. Paulemir Campos
1
Roteiro da Aula




Introdução;
Técnicas de Mineração de Dados;
Aplicações;
Referências.
11/4/2015
MD - Prof. Paulemir Campos
2
Introdução

Basicamente compreende os diversos
algoritmos de aprendizado de máquina,
tais como:

Classificação:




11/4/2015
Regressão Linear;
Redes MLP e RBF;
Árvores de Decisão ID3 e C4.5;
Regras de Classificação.
MD - Prof. Paulemir Campos
3
Introdução

Basicamente compreende os diversos
algoritmos de aprendizado de máquina,
tais como (Cont.):

Cluster ou Agrupamento:


Regras de Associação:


K-Means;
APRIORI
A seguir serão descritos alguns destes.
11/4/2015
MD - Prof. Paulemir Campos
4
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.
11/4/2015
MD - Prof. Paulemir Campos
5
Regressão Linear - Exemplo
Salary (in $1,000)
100
80
60
40
20
0
0
11/4/2015
5
10
15
Years experience
20
25
MD - Prof. Paulemir Campos
6
Á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:

11/4/2015
ID3 e C4.5.
MD - Prof. Paulemir Campos
7
Árvores de Decisão

Algoritmo Básico:





11/4/2015
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).
MD - Prof. Paulemir Campos
8
Árvores de Decisão

Condições de parada:



11/4/2015
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.
MD - Prof. Paulemir Campos
9
Árvores de Decisão - Exemplo
11/4/2015
MD - Prof. Paulemir Campos
10
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.
11/4/2015
MD - Prof. Paulemir Campos
11
Regras de Classificação

Exemplos:


11/4/2015
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
MD - Prof. Paulemir Campos
12
K-Means

Dado k, o algoritmo k-means é implementado
em 4 passos:




11/4/2015
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.
MD - Prof. Paulemir Campos
13
K-Means - Exemplo
10
10
9
9
8
8
7
7
6
6
5
5
4
4
3
3
2
2
1
1
0
0
0
1
2
3
4
5
6
7
8
9
10
10
10
9
9
8
8
7
7
6
6
5
5
4
4
3
3
2
2
1
1
0
1
2
3
4
5
6
7
8
9
10
0
0
11/4/2015
0
1
2
3
4
5
6
7
8
9
10
0
1
2
MD - Prof. Paulemir Campos
3
4
5
6
7
8
9
10
14
K-Means

Pontos Fortes



É relativamente eficiente;
Geralmente encontra um ótimo local.
Pontos Fracos




11/4/2015
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.
MD - Prof. Paulemir Campos
15
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.
11/4/2015
MD - Prof. Paulemir Campos
16
Regras de Associação

Conceitos Básicos:


11/4/2015
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.
MD - Prof. Paulemir Campos
17
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.
11/4/2015
MD - Prof. Paulemir Campos
18
Regras de Associação

Assim, a idéia é:




11/4/2015
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.
MD - Prof. Paulemir Campos
19
Regras de Associação

O Algoritmo APRIORI:


11/4/2015
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.
MD - Prof. Paulemir Campos
20
O Algoritmo APRIORI
Exemplo
Database D
TID
100
200
300
400
itemset sup.
C1
{1}
2
{2}
3
Scan D
{3}
3
{4}
1
{5}
3
Items
134
235
1235
25
C2 itemset sup
L2 itemset sup
2
2
3
2
{1
{1
{1
{2
{2
{3
C3 itemset
{2 3 5}
Scan D
{1 3}
{2 3}
{2 5}
{3 5}
11/4/2015
2}
3}
5}
3}
5}
5}
1
2
1
2
3
2
L1 itemset sup.
{1}
{2}
{3}
{5}
2
3
3
3
C2 itemset
{1 2}
Scan D
{1
{1
{2
{2
{3
3}
5}
3}
5}
5}
L3 itemset sup
{2 3 5} 2
MD - Prof. Paulemir Campos
21
Aplicações Potenciais

Análise de bases de dados e suporte à
decisão

Análise de Mercado


Análise de Risco


11/4/2015
alvo de campanhas, análise de compras, segmentação
do mercado, gerencia de relações com clientes, vendas
cruzadas;
fidelização de clientes, controle de qualidade, análise de
competitividade;
Detecção de Fraude
MD - Prof. Paulemir Campos
22
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.
11/4/2015
MD - Prof. Paulemir Campos
23
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.
11/4/2015
MD - Prof. Paulemir Campos
24