Data Mining:
Conceitos e Técnicas
Algumas técnicas para Data Mining
• Geração de regras de associação;
• Classificação e predição;
• Agrupamento (clustering).
Data Mining:
Regras de Associação
Regras de associação
•
Mineração de associações ou de regras de
associação:
–
•
Encontrara padrões freqüentes, associações,
correlações, ou estruturas causais a partir de
conjuntos de itens ou objetos em DB de
transações, relacionais, ou em outros repositórios
de informações.
Aplicações:
–
Análise de cestas de dados (basket data),
marketing cruzado, projeto de catálogos,
agrupamento, etc.
Regras de associação
•
Exemplo:
–
Formato da regra:
“corpo => cabeça [suporte, confiança]”;
–
compra(X, “fraldas”) => compra (X, “cerveja”)
[0.5%, 60%]
Regras de associação
•
Dados:
1.
2.
•
Uma DB da transações;
Cada transação constituída de uma lista de itens
(compras de um cliente);
Encontrar:
1.
2.
Todas as regras que correlacionam a presença
de um conjunto de itens com outro conjunto de
itens.
Exemplo: 98 % das pessoas que compram
pneus e assessórios também compram sua
instalação.
Regras de associação
•
Aplicações:
* => contratos de manutenção (o que fazer para
aumentar as vendas de contratos de
manutenção)
2. Eletrônicos => * (que outros produtos devem ser
estocados)
3. Indicativos em marketing direto;
4. Detecção de “ping-pong” de pacientes,
colisões...
1.
Regras de associação
Customer
buys both
Customer
buys diaper
– Suporte, s, é a probabilidade de
uma transação conter {X  Y  Z}
– Confiança, c, é a probabilidade
condicional da transação tendo {X
 Y} também conter Z
Customer
buys beer
Transação
2000
1000
4000
5000
Encontrar regras X & Y  Z com
suporte e confiança mínimos
Itens
A,B,C
A,C
A,D
B,E,F
Para um suporte mínimo de
50%, e confiança mínima de
50%, tem-se:
– A  C (50%, 66.6%)
– C  A (50%, 100%)
Regras de associação
•
•
•
Associações booleanas x quantitativas: conforme
os valores manuseados:
– compra(X, “SQLServer”) ^ compra(X, “DMBook”)
=> compra(X, “DBMiner”) [0.2%, 60%]
– idade(Y, “30..39”) ^ renda(Y, “42..48K”) =>
compra(Y, “PC”) [1%, 75%]
Associações uni e multi dimensionais;
Análises uni e multi-níveis:
– Que marcas de cervejas estão associadas a
marcas de fraldas ?
Regras de associação
•
Varias extensões:
– Correlação, análise causal:
• Associação não necessariamente implica em
correlação ou causalidade;
– Padrões maximais e conjuntos fechados de itens;
– Restrições forçadas:
• E.g., pequenas vendas (valor < 100) disparam
grandes vendas (valor > 1000)?
Regras de associação
•
Algoritmo utilizado:
–
APRIORI;
– Princípio: todo subconjunto de um conjunto
freqüente de itens deve ser freqüente;
– Várias otimizações para melhoria da performance
computacional.
Regras de associação 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}
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
L3 itemset sup
{2 3 5} 2
{1
{1
{2
{2
{3
3}
5}
3}
5}
5}
Regras de associação
•
Regras de associação multi-níveis:
–
–
–
Pressupõe uma hierarquia;
Abordagem top-down progressiva;
Inicialmente: encontrar as regras “fortes” de alto
nível:
•
–
Leite => pão [20%, 60%]
Em seguida, regras “fracas” de mais baixo nível:
•
2% leite => pão branco [6%, 50%]
Sumário
•
Mineração de regras de associação:
–
–
Provavelmente a contribuição mais significativa da
comunidade de DB à KDD;
Inúmeros trabalhos publicados;
•
Muitos pontos importantes explorados;
• Direções de pesquisa:
–
Análise de associações em outros tipos de dados:
espaciais, multimídia, temporais, etc.
Aprendizagem supervisionada e
não supervisionada
• Aprendizagem supervisionada (classificação)
– Supervisão: O conjunto de treinamento
(observações, medições, etc.) é acompanhado dos
rótulos indicativos das classes das observações;
– Novos dados são classificados com base na
estrutura gerada a partir do conjunto de
treinamento;
Aprendizagem supervisionada e
não supervisionada
• Aprendizagem não supervisionada (agrupamento =
clustering)
– Os rótulos das classes no conjunto de treinamento
são desconhecidos;
– Dado um conjunto de medidas, observações, etc. o
objetivo é estabelecer a existência de classes ou
grupos nos dados.
Data Mining:
Classificação e Predição
Classificação e Predição
• Classificação:
– Predição dos nomes (rótulos) das classes;
– Classifica os dados (constrói um modelo) com
base no conjunto de treinamento e nos valores
(rótulos) do atributo classificador, de forma a
determinar a classe dos novos dados;
• Predição:
– Modela funções sobre valores contínuos, i.e.,
prediz valores desconhecidos ou perdidos;
• Aplicações típicas:
– Aprovação de crédito, marketing dirigido,
diagnóstico médico ...
Classificação: um processo de
dois passos
1. Construção do modelo:
Descrição de um conjunto de um conjunto de
classes pré-determinadas:
– Cada tupla (exemplo) é considerada como
pertencente a uma classe pré-definida,
determinada pelo rótulo de seu atributo-classe;
– O conjunto de tuplas usado na construção do
modelo é o conjunto de treinamento;
– O modelo pode ser representado por regras de
classificação, árvores de decisão ou fórmulas
matemáticas;
Classificação: um processo de
dois passos
2. Uso do modelo:
– Para a classificação futura ou de elementos
desconhecidos;
– Correção estimada do modelo:
– Uso de conjunto de teste;
– O rótulo conhecido é comparado ao rótulo
fornecido pelo modelo;
– O conjunto de teste deve ser diferente do
conjunto de treinamento, de forma a evitar
overfitting.
Classificação: passo 1
Classification
Algorithms
Training
Data
NAME RANK
M ike
M ary
B ill
Jim
D ave
Anne
A ssistan t P ro f
A ssistan t P ro f
P ro fesso r
A sso ciate P ro f
A ssistan t P ro f
A sso ciate P ro f
YEARS TENURED
3
7
2
7
6
3
no
yes
yes
yes
no
no
Classifier
(Model)
IF rank = ‘professor’
OR years > 6
THEN tenured = ‘yes’
Classificação: passo 2
Classifier
Testing
Data
Unseen Data
(Jeff, Professor, 4)
NAME
Tom
M erlisa
G eorge
Joseph
RANK
Y E A R S TE N U R E D
A ssistant P rof
2
no
A ssociate P rof
7
no
P rofessor
5
yes
A ssistant P rof
7
yes
Tenured?
Preparação do dados
• Limpeza dos dados:
– Pré-processamento dos dados para reduzir o ruído
e tratar valores desconhecidos;
• Análise de relevância (seleção de características):
– Remoção de atributos irrelevantes ou redundantes;
• Transformação de dados:
– Generalização e normalização dos dados.
Avaliação da classificação
• Correção preditiva;
• Performance e escalabilidade;
– Construção do modelo e seu uso;
• Robustez:
– Manuseio de dados ruidosos e incompletos;
• Interpretabilidade:
– Compreensão oferecida pelo modelo;
• Utilidade das regras:
– Tamanho, facilidade de leitura, etc.
Árvores de decisão
Classificação por árvore de
decisão
• Árvores de decisão:
– Estrutura do tipo “fluxograma”;
– Nós internos denotam testes em atributos;
– Ramos representam saídas dos testes;
– Nós folha representam rótulos de classe.
Classificação por árvore de
decisão
•
Construção da árvore:
1. No início, todos os exemplos de treinamento são
associados à raiz;
2. Os exemplos são particionados com base nos
atributos selecionados;
3. Poda da árvore: ramos que refletem desvios e/ou
ruído são eliminados;
•
Uso da árvore de decisão:
– Os valores dos atributos do novo exemplo são
testados diretamente na árvore atingindo o nó
folha da classe correspondente.
Exemplo: árvore de decisão
Exemplo:
ID3 de
Quinlan
age
<=30
<=30
31…40
>40
>40
>40
31…40
<=30
<=30
>40
<=30
31…40
31…40
>40
income student credit_rating
high
no fair
high
no excellent
high
no fair
medium
no fair
low
yes fair
low
yes excellent
low
yes excellent
medium
no fair
low
yes fair
medium
yes fair
medium
yes excellent
medium
no excellent
high
yes fair
medium
no excellent
buys_computer
no
no
yes
yes
yes
no
yes
no
yes
yes
yes
yes
yes
no
Exemplo: árvore de decisão
age?
<=30
overcast
30..40
student?
yes
>40
credit rating?
no
yes
excellent
fair
no
yes
no
yes
Buys computer ?
Exemplo: árvore de decisão
•
Ordem dos atributos: ganho de informação (página
70/421 do Mitchell)...
•
•
Representação por regras IF-THEN:
–
–
Uma regra para cada caminho da raiz à folha;
Cada par (atributo, valor) forma uma conjunção;
–
Cada folha determina a classe prevista;
Regras são de mais fácil compreensão aos
usuários:
IF age = “<=30” AND student = “no”
THEN buys_computer = “no”
IF age = “>40” AND credit_rating = “excellent”
THEN buys_computer = “yes”
Classificador Bayesiano
Classificador bayesiano
•
•
•
Aprendizagem probabilista: cálculo da
probabilidade explícita da hipótese, de ampla
aplicação em vários domínios;
Incremental:
– cada exemplo de treinamento pode aumentar /
diminuir a probabilidade da hipótese;
– Conhecimento a priori pode ser combinado com os
dados observados;
Previsão probabilista:
– Várias hipótese podem ser previstas, ponderadas
por suas probabilidades;
– Fornece uma referência a ser comparada a outros
métodos.
Classificador bayesiano
Fundamento: Teorema de Bayes;
• Dado um conjunto de treinamento D, a probabilidade
a posteriori de uma hipótese h, P(h|D) é dada por:
P(h | D)  P(D | h)P(h)
P(D)
•
A probabilidade máxima a posteriori MAP é:
h
 arg max P(h | D)  arg max P(D | h)P(h).
MAP
hH
hH
•
•
Dificuldade prática: requer conhecimento inicial de
muitas probabilidades, custo computacional elevado;
Simplificação: independência dos atributos.
Exemplo: jogar ou não tênis ?
Outlook
sunny
sunny
overcast
rain
rain
rain
overcast
sunny
sunny
rain
sunny
overcast
overcast
rain
Temperature Humidity Windy Class
hot
high
false
N
hot
high
true
N
hot
high
false
P
mild
high
false
P
cool
normal false
P
cool
normal true
N
cool
normal true
P
mild
high
false
N
cool
normal false
P
mild
normal false
P
mild
normal true
P
mild
high
true
P
hot
normal false
P
mild
high
true
N
outlook
P(sunny|p) = 2/9
P(sunny|n) = 3/5
P(overcast|p) = 4/9
P(overcast|n) = 0
P(rain|p) = 3/9
P(rain|n) = 2/5
temperature
P(hot|p) = 2/9
P(hot|n) = 2/5
P(mild|p) = 4/9
P(mild|n) = 2/5
P(cool|p) = 3/9
P(cool|n) = 1/5
humidity
P(p) = 9/14
P(n) = 5/14
P(high|p) = 3/9
P(high|n) = 4/5
P(normal|p) = 6/9
P(normal|n) = 2/5
windy
P(true|p) = 3/9
P(true|n) = 3/5
P(false|p) = 6/9
P(false|n) = 2/5
Exemplo: jogar ou não tênis ?
• Um novo exemplo: X = <rain, hot, high, false>
• P(X|p)·P(p) =
P(rain|p)·P(hot|p)·P(high|p)·P(false|p)·P(p) =
3/9·2/9·3/9·6/9·9/14 = 0.010582
• P(X|n)·P(n) =
P(rain|n)·P(hot|n)·P(high|n)·P(false|n)·P(n) =
2/5·2/5·4/5·2/5·5/14 = 0.018286
• O exemplo X é classificado como da classe n (não
jogar).
Redes Neurais
Redes Neurais
Vantagens:
• Correção de predição em geral elevada;
• Robustez, bom funcionamento na presença de
ruídos;
• Saídas discretas, reais, ou mistas;
• Avaliação rápida da função de aprendizagem.
Desvantagens / crítica:
• Tempo de treinamento lento;
• Dificuldade no entendimento da função de
aprendizagem (pesos);
• Difícil incorporação de conhecimento de domínio.
Um neurônio
- mk
x0
w0
x1
w1
xn

f
output y
wn
Input
weight
vector x vector w
weighted
sum
Activation
function
• Um vetor n-dimensional x de entrada é mapeado em
uma variável y por meio de um produto escalar e de um
mapeamento não-linear.
Rede perceptron multi-camadas
Output vector
Err j  O j (1  O j ) Errk w jk
Output nodes
k
 j   j  (l) Err j
wij  wij  (l ) Err j Oi
Hidden nodes
Err j  O j (1  O j )(T j  O j )
wij
Input nodes
Oj 
I
1 e j
I j   wij Oi   j
i
Input vector: xi
1
Rede perceptron multi-camadas
Treinamento:
• Obtenção dos pesos que tornam a maior parte das
tuplas no conjunto de treinamento corretamente
classificadas;
Passos:
• Inicialização randômica dos pesos;
• Alimentação da rede pelas tuplas, uma a uma;
• Para cada unidade:
– Computar a entrada da rede à unidade como combinação
linear das entradas da unidade;
– Computar a saída em função dos pesos e da função de
ativação;
– Calcular o erro;
– Modificar os pesos e recomputar.
Aprendizagem baseada em
instâncias:
K-vizinhos mais próximos
K-vizinhos mais próximos
Aprendizagem baseada em instâncias (IBL):
• Armazenamento dos exemplos de
treinamento (avaliação preguiçosa = “lazy
evaluation”) até que a nova instância deva
ser classificada;
K-vizinhos mais próximos:
• Algoritmo mais utilizado em IBL;
• As instâncias são associadas a pontos no
espaço euclidiano;
• Métrica de distância para selecionar os
vizinhos.
K-vizinhos mais próximos (k-NN)
• Todas as instâncias correspondem a pontos
no espaço n- dimensional;
• Os vizinhos mais próximos são usualmente
definidos em função da distância euclidiana;
• A função objetivo (classe) pode ser discreta
ou real;
• Para os casos discretos o k-NN retorna a
classe mais comum entre as classes dos k
vizinhos mais próximos à nova instância;
K-vizinhos mais próximos (k-NN)
• Diagrama de Voronoi: descreve a superfície
de decisão induzida;
• No exemplo a seguir, um caso típico para 1NN
.
_
_
_
+
_
_
.
+
+
xq
_
+
.
.
.
.
Predição
Similar à classificação no caso em que o
atributo “classe” é contínuo;
Etapas:
• Construção do modelo;
• Uso do modelo para predizer um valor
desconhecido:
– O método mais utilizado é a regressão:
• Regressão linear e múltipla;
• Regressão não-linear.
Sumário
• Classificação é provavelmente uma das técnicas mais
utilizadas de data mining, com muitas possibilidades de
aplicação;
• É uma problema extensivamente estudado,
especialmente com o uso de análise estatística,
aprendizagem de máquina e redes neurais;
• A escalabilidade é muito importante em aplicações de
DB: o uso conjunto de de classificação e técnicas de
DB é uma área promissora de estudos;
• Muitas novas áreas podem ser vislubradas:
classificação de dados não-relacionais, e.g. textuais,
espaciais, multimídia, etc.
Data Mining:
Agrupamento (clustering)
Agrupamento (clustering)
Cluster: uma coleção de objetos de dados;
• Similares entre si no mesmo cluster;
• Não similares aos objetos fora do respectivo cluster;
Análise de clusters:
• Agrupamento de dados em clusters;
Agrupamento (clustering) é uma classificação nãosupervisionada: não há classes pré-definidas.
Aplicações típicas:
• Como ferramenta para análise da distribuição dos
dados;
• Como pré-processamento para outros métodos.
Aplicações gerais do agrupamento
• Reconhecimento de padrões;
• Análise de dados espaciais:
– Criação de mapas temáticos em GIS por
agrupamento de espaços de características;
– Detecção de clusters espaciais e sua explanação
em data mining;
• Processamento de imagens;
• Pesquisas de mercado;
• WWW:
– Classificação de documentos;
– Agrupamento de dados de weblogs para descobrir
padrões similares de acesso;
Exemplos de aplicações
• Marketing: ajuda na descoberta de grupos distintos
de clientes, e uso deste conhecimento para criar
campanhas dirigidas;
• Uso de terras: identificação de áreas de uso similar
a partir de uma base de observação via satélite;
• Seguros: identificação de grupos de assegurados
com alto custo de sinistro;
• Planejamento urbano: identificação de grupos de
casa de acordo com seu tipo, valor e localização
geográfica;
• Estudos sobre terremotos: identificação de
epicentros e seu agrupamento ao longo de falhas
geológicas.
O que é um bom clustering ?
• Um bom método de agrupamento (clustering)
deve produzir clusters de qualidade com:
– Alta similaridade intra-classe;
– Baixa similaridade inter-classes.
• A qualidade do resultado de um processo de
clustering depende da medida de similaridade,
do método utilizado e de sua implementação;
• A qualidade um um processo de clustering
também deve ser avaliada pela sua habilidade de
descobrir alguns ou todos os padrões
escondidos (hidden patterns).
Requisitos do clustering
•
•
•
•
•
•
•
•
•
Escalabilidade;
Habilidade de tratar diferentes tipos de atributos;
Descoberta de clusters de formas arbitrárias;
Requisitos mínimos de conhecimento de domínio
para determinar parâmetros de entrada;
Habilidade para tratar ruído e desvios;
Insensibilidade à ordem de entrada dos registros;
Alta dimensionalidade;
Incorporação de restrições específicas dos
usuários;
Interpretabilidade e utilidade.
Estruturas de dados
• Matriz de dados
– (dois modos)
• Matriz de
• dissimilaridade
– (um modo)
 x11

 ...
x
 i1
 ...
x
 n1
... x1f
... ...
... xif
...
...
... xnf
 0
 d(2,1)
0

 d(3,1) d ( 3,2)

:
 :
d ( n,1) d ( n,2)
... x1p 

... ... 
... xip 

... ... 
... xnp 





0

:

... ... 0
Medida da qualidade do cluster
• Métrica de similaridade / dissimilaridade:
expressa em termos de função de distância d(i, j)
• Existe uma função de “qualidade” que é uma
medida da “adequação” de um cluster;
• Existem definições de funções de distância que
são diferentes para variáveis intervalares,
booleanas, categóricas e proporções;
• Pesos devem ser associados às variáveis
baseados na aplicação e na semântica dos
dados;
• É difícil definir “suficientemente similar”, pois
tipicamente esta avaliação é subjetiva.
Tipos de dados em clustering
• Variáveis intervalares;
• Variáveis binárias;
• Variáveis nominais, ordinais, e
proporções;
• Variáveis de tipo misto.
Similaridade entre objetos: distâncias
• Distância típica: de Minkowski;
d (i, j)  q (| x  x |q  | x  x |q ... | x  x |q )
i1
j1
i2
j2
ip
jp
– Onde i = (xi1, xi2, …, xip) e j = (xj1, xj2, …, xjp)
são vetores p-dimensionais e q é um inteiro
positivo.
Similaridade entre objetos: distâncias
• q =1: distância de Manhattan:
d (i, j) | x  x |  | x  x | ... | x  x |
i1 j1 i2 j2
ip jp
• q =2: distância euclidiana:
d (i, j)  (| x  x |2  | x  x |2 ... | x  x |2 )
i1 j1
i2
j2
ip
jp
Principais abordagens para o
agrupamento
• Algoritmos de partição: construção de diversas
partições e sua avaliação por algum critério;
• Algoritmos hierárquicos: criação de uma
decomposição hierárquica do conjunto de dados
usando algum critério;
• Algoritmos fundamentados em densidade:
utilização funções de densidade e de conectividade;
• Algoritmos baseados em grades (grids): utilizam
uma estrutura de múltiplos níveis;
• Algoritmos baseados em modelos: utilizam um
modelo subjacente à cada cluster e a idéia é a de se
encontrar a melhor assinalação dos objetos aos
modelos.
O método k-means (k-médias)
•
Dado k, o algoritmo k-means é
implementado em quatro passos:
1. Partição dos objetos em k conjuntos não vazios;
2. Cálculo de pontos “semente” como os centróides
(médias) dos clusters das partições correntes;
3. Assinalação de cada objeto ao cluster
(centróide) mais próximo de acordo com a
função de distância;
4. Retorno ao passo 2 até que não haja mais
alterações de assinalação.
O método 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
0
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
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10
O método k-means (k-médias)
Vantagens:
• Relativamente eficiente O ( t k n) onde n é o
número de objetos, t é o número de iterações e k
de clusters;
• Em geral determina o ótimo local: para obtenção do
ótimo global usam-se outros métodos de busca,
como têmpera simulada ou algoritmos genéticos;
Deficiências:
• Como utilizar em dados categóricos;
• Necessita que se especifique o número de clusters;
• Não trata ruídos e desvios;
• Não descobre clusters de forma não-convexa.
O clustering hierárquico
•
Usa a matriz de distância como critério de
agrupamento; não pré-determina o número de
clusters, mas necessita critério de parada.
Step 0
a
Step 1
Step 2 Step 3 Step 4
ab
b
abcde
c
cde
d
de
e
Step 4
aglomerativo
divisivo
Step 3
Step 2 Step 1 Step 0
O clustering hierárquico bottom-up
•
AGNES (Agglomerative Nesting), Kaufmann and
Rousseeuw (1990);
Agrupa (merge) nós de menor dissimilaridade, de
maneira bottom-up.
•
10
10
10
9
9
9
8
8
8
7
7
7
6
6
6
5
5
5
4
4
4
3
3
3
2
2
2
1
1
1
0
0
0
1
2
3
4
5
6
7
8
9
10
0
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10
O clustering hierárquico top-down
•
DIANA (Divisive Analysis), Kaufmann and
Rousseeuw (1990);
Divide os nós de maior dissimilaridade, de maneira
top-down.
Ordem inversa do AGNES.
•
•
10
10
10
9
9
9
8
8
8
7
7
7
6
6
6
5
5
5
4
4
4
3
3
3
2
2
2
1
1
1
0
0
0
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
O clustering hierárquico
Maior desvantagem dos métodos de clustering
aglomerativo:
• Pouca escalabilidade: complexidade O(n2),
onde n é o número de objetos;
• Não refaz o que foi feito previamente (no
nível anterior).
Detecção de desvios (outliers)
•
O que são desvios ?
– Um conjunto de objetos muito diferente
(dissimilar) ao restante dos dados;
•
Problema:
– Determinar os n maiores desvios;
•
Aplicações:
–
–
–
–
Detecção de fraudes em cartões de crédito;
Detecção de fraudes telefônicas;
Segmentação de clientes;
Análise médica.
Método estatístico
para a detecção
de desvios
•
•
Assume a existência de uma distribuição para a
geração dos dados (e.g. distribuição normal);
Uso de testes de discordância dependendo da:
–
–
–
•
Distribuição de dados;
Distribuição de parâmetros (média, variância...);
Número esperado de desvios;
Problemas:
–
–
A maior parte dos testes é para um só atributo;
Em muitos casos a distribuição é desconhecida.
Método para a detecção de desvios
baseado em distâncias
•
Introduzidos para sobrepujar as limitações
dos métodos estatísticos:
– Necessidade de análise multi-dimensional sem
conhecer a distribuição dos dados.
•
•
Detecção de desvios baseada em distâncias:
um DB(p,D)-desvio é um objeto O em um
conjunto de dados T tal que pelo menos
uma fração p dos objetos em T está a uma
distância maior que D de O.
Vários algoritmos disponíveis.
Sumário
•
•
•
•
•
Análise de agrupamento (clustering) gera grupos de
objetos com base em sua similaridade e tem
inúmeras aplicações;
A medida de similaridade pode ser calculada sobre
diferentes tipos de dados;
Há vários tipos de algoritmos de clustering:
particionamento, hierárquicos, etc.
Exemplos: k-means, clustering hierárquico;
Detecção de desvios: é muito útil para a detecção
de fraudes e pode ser realizada por métodos
estatísticos e baseados em distâncias.
Avaliação
• Estudo de caso (equipes até 5);
• Relatório escrito de procedimento de
data-mining:
1. Descrição do problema alvo;
2. Objetivos da tarefa, caracterização;
3. Indicativos do pré-processamento;
Avaliação
4. Criação de base de teste;
5. Aplicação do algoritmo selecionado na
base;
6. Avaliação dos resultados;
7. Conclusões sobre o trabalho.