71
Data Mining: Conceitos e Técnicas

Data Mining : Conceitos e Técnicas

Embed Size (px)

DESCRIPTION

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: - PowerPoint PPT Presentation

Citation preview

Page 1: Data Mining :  Conceitos e Técnicas

Data Mining: Conceitos e Técnicas

Page 2: 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).

Page 3: Data Mining :  Conceitos e Técnicas

Data Mining: Regras de Associação

Page 4: Data Mining :  Conceitos e Técnicas

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.

Page 5: Data Mining :  Conceitos e Técnicas

Regras de associação

• Exemplo: – Formato da regra:

“corpo => cabeça [suporte, confiança]”;

– compra(X, “fraldas”) => compra (X, “cerveja”) [0.5%, 60%]

Page 6: Data Mining :  Conceitos e Técnicas

Regras de associação

• Dados: 1. Uma DB da transações;

2. Cada transação constituída de uma lista de itens (compras de um cliente);

• Encontrar: 1. Todas as regras que correlacionam a presença

de um conjunto de itens com outro conjunto de itens.

2. Exemplo: 98 % das pessoas que compram pneus e assessórios também compram sua instalação.

Page 7: Data Mining :  Conceitos e Técnicas

Regras de associação

• Aplicações: 1. * => 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...

Page 8: Data Mining :  Conceitos e Técnicas

Regras de associação

Encontrar regras X & Y Z com suporte e confiança mínimos– 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

Transação Itens2000 A,B,C1000 A,C4000 A,D5000 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%)

Customerbuys diaper

Customerbuys both

Customerbuys beer

Page 9: Data Mining :  Conceitos e Técnicas

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 ?

Page 10: Data Mining :  Conceitos e Técnicas

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)?

Page 11: Data Mining :  Conceitos e Técnicas

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.

Page 12: Data Mining :  Conceitos e Técnicas

Regras de associação - exemplo

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 C2

Scan D

C3 L3itemset{2 3 5}

Scan D itemset sup{2 3 5} 2

Page 13: Data Mining :  Conceitos e Técnicas

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%]

Page 14: Data Mining :  Conceitos e Técnicas

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.

Page 15: Data Mining :  Conceitos e Técnicas

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;

Page 16: Data Mining :  Conceitos e Técnicas

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.

Page 17: Data Mining :  Conceitos e Técnicas

Data Mining: Classificação e Predição

Page 18: Data Mining :  Conceitos e Técnicas

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 ...

Page 19: Data Mining :  Conceitos e Técnicas

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;

Page 20: Data Mining :  Conceitos e Técnicas

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.

Page 21: Data Mining :  Conceitos e Técnicas

Classificação: passo 1

TrainingData

NAME RANK YEARS TENUREDMike Assistant Prof 3 noMary Assistant Prof 7 yesBill Professor 2 yesJim Associate Prof 7 yesDave Assistant Prof 6 noAnne Associate Prof 3 no

ClassificationAlgorithms

IF rank = ‘professor’OR years > 6THEN tenured = ‘yes’

Classifier(Model)

Page 22: Data Mining :  Conceitos e Técnicas

Classificação: passo 2

Classifier

TestingData

NAME RANK YEARS TENUREDTom Assistant Prof 2 noMerlisa Associate Prof 7 noGeorge Professor 5 yesJoseph Assistant Prof 7 yes

Unseen Data

(Jeff, Professor, 4)

Tenured?

Page 23: Data Mining :  Conceitos e Técnicas

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.

Page 24: Data Mining :  Conceitos e Técnicas

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.

Page 25: Data Mining :  Conceitos e Técnicas

Árvores de decisão

Page 26: Data Mining :  Conceitos e Técnicas

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.

Page 27: Data Mining :  Conceitos e Técnicas

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.

Page 28: Data Mining :  Conceitos e Técnicas

Exemplo: árvore de decisão

age income student credit_rating buys_computer<=30 high no fair no<=30 high no excellent no31…40 high no fair yes>40 medium no fair yes>40 low yes fair yes>40 low yes excellent no31…40 low yes excellent yes<=30 medium no fair no<=30 low yes fair yes>40 medium yes fair yes<=30 medium yes excellent yes31…40 medium no excellent yes31…40 high yes fair yes>40 medium no excellent no

Exemplo:ID3 de Quinlan

Page 29: Data Mining :  Conceitos e Técnicas

Exemplo: árvore de decisão

age?

overcast

student? credit rating?

no yes fairexcellent

<=30 >40

no noyes yes

yes

30..40

Buys computer ?

Page 30: Data Mining :  Conceitos e Técnicas

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”

Page 31: Data Mining :  Conceitos e Técnicas

Classificador Bayesiano

Page 32: Data Mining :  Conceitos e Técnicas

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.

Page 33: Data Mining :  Conceitos e Técnicas

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:

• A probabilidade máxima a posteriori MAP é:

• Dificuldade prática: requer conhecimento inicial de muitas probabilidades, custo computacional elevado;

• Simplificação: independência dos atributos.

)()()|()|(

DPhPhDPDhP

.)()|(maxarg)|(maxarg hPhDPHh

DhPHhMAP

h

Page 34: Data Mining :  Conceitos e Técnicas

Exemplo: jogar ou não tênis ?

Outlook Temperature Humidity Windy Classsunny hot high false Nsunny hot high true Novercast hot high false Prain mild high false Prain cool normal false Prain cool normal true Novercast cool normal true Psunny mild high false Nsunny cool normal false Prain mild normal false Psunny mild normal true Povercast mild high true Povercast hot normal false Prain mild high true N

outlookP(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(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

P(p) = 9/14

P(n) = 5/14

Page 35: Data Mining :  Conceitos e Técnicas

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).

Page 36: Data Mining :  Conceitos e Técnicas

Redes Neurais

Page 37: Data Mining :  Conceitos e Técnicas

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.

Page 38: Data Mining :  Conceitos e Técnicas

Um neurônio

k-

f

weighted sum

Inputvector x

output y

Activationfunction

weightvector w

w0

w1

wn

x0

x1

xn

• 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.

Page 39: Data Mining :  Conceitos e Técnicas

Rede perceptron multi-camadas

Output nodes

Input nodes

Hidden nodes

Output vector

Input vector: xi

wij

i

jiijj OwI

jIje

O

1

1

))(1( jjjjj OTOOErr

jkk

kjjj wErrOOErr )1(

ijijij OErrlww )(jjj Errl)(

Page 40: Data Mining :  Conceitos e Técnicas

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.

Page 41: Data Mining :  Conceitos e Técnicas

Aprendizagem baseada em instâncias:

K-vizinhos mais próximos

Page 42: Data Mining :  Conceitos e Técnicas

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.

Page 43: Data Mining :  Conceitos e Técnicas

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;

Page 44: Data Mining :  Conceitos e Técnicas

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 1-NN

.

_+

_ xq

+

_ _+

_

_

+

.

..

. .

Page 45: Data Mining :  Conceitos e Técnicas

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.

Page 46: Data Mining :  Conceitos e Técnicas

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.

Page 47: Data Mining :  Conceitos e Técnicas

Data Mining: Agrupamento (clustering)

Page 48: Data Mining :  Conceitos e Técnicas

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ão-

supervisionada: 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.

Page 49: Data Mining :  Conceitos e Técnicas

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;

Page 50: Data Mining :  Conceitos e Técnicas

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.

Page 51: Data Mining :  Conceitos e Técnicas

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).

Page 52: Data Mining :  Conceitos e Técnicas

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.

Page 53: Data Mining :  Conceitos e Técnicas

Estruturas de dados

• Matriz de dados– (dois modos)

• Matriz de • dissimilaridade

– (um modo)

npx...nfx...n1x

...............ipx...ifx...i1x

...............1px...1fx...11x

0...)2,()1,(

:::

)2,3()

...ndnd

0dd(3,1

0d(2,1)

0

Page 54: Data Mining :  Conceitos e Técnicas

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.

Page 55: Data Mining :  Conceitos e Técnicas

Tipos de dados em clustering

• Variáveis intervalares;

• Variáveis binárias;

• Variáveis nominais, ordinais, e proporções;

• Variáveis de tipo misto.

Page 56: Data Mining :  Conceitos e Técnicas

Similaridade entre objetos: distâncias

• Distância típica: de Minkowski;

– Onde i = (xi1, xi2, …, xip) e j = (xj1, xj2, …, xjp) são vetores p-dimensionais e q é um inteiro positivo.

qq

pp

qq

jx

ix

jx

ix

jx

ixjid )||...|||(|),(

2211

Page 57: Data Mining :  Conceitos e Técnicas

Similaridade entre objetos: distâncias

• q =1: distância de Manhattan:

• q =2: distância euclidiana:

||...||||),(2211 pp jxixjxixjxixjid

)||...|||(|),( 22

22

2

11 pp jx

ix

jx

ix

jx

ixjid

Page 58: Data Mining :  Conceitos e Técnicas

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.

Page 59: Data Mining :  Conceitos e Técnicas

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.

Page 60: Data Mining :  Conceitos e Técnicas

O método 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

Page 61: Data Mining :  Conceitos e Técnicas

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.

Page 62: Data Mining :  Conceitos e Técnicas

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 Step 1 Step 2 Step 3 Step 4

b

d

c

e

a a b

d e

c d e

a b c d e

Step 4 Step 3 Step 2 Step 1 Step 0

aglomerativo

divisivo

Page 63: Data Mining :  Conceitos e Técnicas

O clustering hierárquico bottom-up

• AGNES (Agglomerative Nesting), Kaufmann and Rousseeuw (1990);

• Agrupa (merge) nós de menor dissimilaridade, de maneira bottom-up.

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

Page 64: Data Mining :  Conceitos e Técnicas

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.

0

1

2

3

4

5

6

7

8

9

10

0 1 2 3 4 5 6 7 8 9 100

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

Page 65: Data Mining :  Conceitos e Técnicas

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).

Page 66: Data Mining :  Conceitos e Técnicas

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.

Page 67: Data Mining :  Conceitos e Técnicas

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.

Page 68: Data Mining :  Conceitos e Técnicas

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.

Page 69: Data Mining :  Conceitos e Técnicas

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.

Page 70: Data Mining :  Conceitos e Técnicas

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;

Page 71: Data Mining :  Conceitos e Técnicas

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.