PGC201 - Mineracao de Dados

Marcelo K. Albertini

11 de Agosto de 2015

Organizacao da disciplina

Prof. Marcelo Keese Albertini

Sala: Bloco 1B - sala 1B150

Horario de atendimento: Sexta-feira 14h-17h ou comagendamento

E-mail: albertini@ufu.br

Site da disciplina:http://www.facom.ufu.br/~albertini/md

2/46

Atividades previstas

Dois trabalhos - 20 pontos estudo da area implementacao e aplicacao escrita de artigo

Tres provas - 80 pontos Prova 1 - 25 pontos - 15/09 - Conceitos basicos, classificacao

e agrupamento Prova 2 - 25 pontos - 26/10 - Mineracao de itens, sequencias e

grafos Prova 3 - 30 pontos - 07/12 - Sistemas de recomendacao e

mineracao de grandes quantidades de dados

3/46

Materiais de estudo

Data mining and analysis de Zaki e Meira (2010)

Mining massive datasets de Rajaraman, Leskovec e Ullman(2014)

Machine Learning de T. Mitchell. (1997)

Artigos cientıficos

4/46

Exemplos de areas com aplicacoes de Mineracao de Dados

Motor de busca Web: ≈ 40 bilhoes de documentos

Comercio: base de transacoes Wal-Mart de 24TB (1997)

Astronomia: Very Long Baseline Inteferometry com 16telescopios gera 1Gb/s

E-comercio: sistema de recomendacao da Amazon, Netflix

Genoma humano ≈ 3 bilhoes de pares de base

Robotica: carro autonomos

Redes sociais: Facebook, NSA

Biologia computacional: projeto de remedios

Redes de ligacoes telefonicas: Uberlandia > 1 milhao por dia

5/46

Quais perguntas podemos fazer sobre os dados?

Exemplo: dados sobre o ingresso de estudantes na UFU

Perguntas: Existe ligacao entre a nota do ENEM dos ingressantes e

situacao socio-economica? Correlacao, informacao mutua, comparacao de similaridade

6/46

Quais perguntas podemos fazer sobre os dados?

Exemplo: dados sobre o ingresso de estudantes na UFU

Perguntas: Existe ligacao entre a nota do ENEM dos ingressantes e

situacao socio-economica? Correlacao, informacao mutua, comparacao de similaridade

Quais grupos de estudantes tem mesmo desempenhoacademico?

Agrupamento, co-ocorrencia, associacao

6/46

Quais perguntas podemos fazer sobre os dados?

Exemplo: dados sobre o ingresso de estudantes na UFU

Perguntas: Existe ligacao entre a nota do ENEM dos ingressantes e

situacao socio-economica? Correlacao, informacao mutua, comparacao de similaridade

Quais grupos de estudantes tem mesmo desempenhoacademico?

Agrupamento, co-ocorrencia, associacao

Existem estudantes de destaque? Categorizacao, classificacao, deteccao de anomalias

6/46

Quais perguntas podemos fazer sobre os dados?

Exemplo: dados sobre o ingresso de estudantes na UFU

Perguntas: Existe ligacao entre a nota do ENEM dos ingressantes e

situacao socio-economica? Correlacao, informacao mutua, comparacao de similaridade

Quais grupos de estudantes tem mesmo desempenhoacademico?

Agrupamento, co-ocorrencia, associacao

Existem estudantes de destaque? Categorizacao, classificacao, deteccao de anomalias

Podemos sugerir ao estudante mudar de curso de acordo comseu perfil?

Recomendacao, predicao

6/46

Top 10 algorithms in data mining (2008) da IEEE

Computer Society

Classificacao: C4.5 (1), CART (10), kNN (7),Naive Bayes (7)

Aprendizado estatıstico: SVM (3), EM (5)

Bagging e Boosting: AdaBoost (7)

Agrupamento: K -means (2), BIRCH, DBSCAN (TTA 2014)

Analise de associacoes: Apriori (4), FP-Tree

Mineracao de links: PageRank (6) e HITS

Padroes sequenciais: GSP, PrefixSpan

Mineracao de Grafos: gSpan

Conjuntos Aproximados (Rough Sets): Finding reduct

7/46

Culturas em Mineracao de Dados

Banco de Dados: foco em grandes quantidades de dados Para um DBA, mineracao de dados e forma extrema de

consultas que geram muitos dados O resultado e a resposta a query

8/46

Culturas em Mineracao de Dados

Banco de Dados: foco em grandes quantidades de dados Para um DBA, mineracao de dados e forma extrema de

consultas que geram muitos dados O resultado e a resposta a query

Inteligencia Artificial/Aprendizado de maquina: foco emmetodos complexos e (mudando) poucos dados

Dedicam-se ao metodo de aprendizado O resultado e composto por modelos, funcoes ou outro

resultado de aprendizado

8/46

Culturas em Mineracao de Dados

Banco de Dados: foco em grandes quantidades de dados Para um DBA, mineracao de dados e forma extrema de

consultas que geram muitos dados O resultado e a resposta a query

Inteligencia Artificial/Aprendizado de maquina: foco emmetodos complexos e (mudando) poucos dados

Dedicam-se ao metodo de aprendizado O resultado e composto por modelos, funcoes ou outro

resultado de aprendizado

Estatıstica: foco em modelos Para estatısticos, mineracao de dados e usar tecnicas de

inferencia O resultado resume-se ao parametros inferidos

8/46

Mineracao de dados e aprendizado de maquina

Desafios em mineracao de dados

Atender a consultas e encontrar informacoes relevantes

Processar grandes quantidades de dados em tempo habil

Encontrar padroes interessantes automaticamente

Mineracao de dados

Boa parte de mineracao de dados hoje e realizada com algoritmosde aprendizado de maquina.

9/46

O que e Aprendizado de Maquina?

Mineracao de dados para automatizar automacao

Fazer computadores programarem eles mesmos

A escrita de software e um gargalo para tratar dadosdisponıveis

Permitir os dados fazerem o trabalho sozinhos

Programacao tradicional

Dados + Programa → computador → saıda

Aprendizado de Maquina

Dados + saıda → computador → programa

10/46

Metafora: agricultura

Mineracao de dados nao e

magica, e como agricultura

sementes = algoritmos

nutrientes = dados

agricultor = voce

plantas e frutos =programas, informacoes econhecimento

11/46

Funcionamento de algoritmos de mineracao de dados

Existem milhares de algoritmos de mineracao de dados

Algoritmos de mineracao costumam ter tres componentes: Representacao Avaliacao Otimizacao

12/46

Representacao: “a linguagem”

Qual linguagem usar?

Arvores de decisao

Conjuntos de regras

Programas logicos (Prolog)

Aprendizado Baseado em Instancias

Modelos baseados em grafos (Redes Bayesianas/Markovianas)

Representacao de dependencias

Redes neurais – “competicao” biologica

Maquinas de vetores suporte (instancias + redes neurais)

Mistura de modelos – “a melhor decisao e aquela maisvotada”

13/46

Avaliacao: medidas

Esta funcionando?Qual e a qualidade do obtido ate agora?

Suporte e confianca (frequencia de repeticao do padrao)

14/46

Avaliacao: medidas

Esta funcionando?Qual e a qualidade do obtido ate agora?

Suporte e confianca (frequencia de repeticao do padrao)

Acuracia – quantos acertos das tentativas?

14/46

Avaliacao: medidas

Esta funcionando?Qual e a qualidade do obtido ate agora?

Suporte e confianca (frequencia de repeticao do padrao)

Acuracia – quantos acertos das tentativas?

Precisao e recuperacao – ORI

14/46

Avaliacao: medidas

Esta funcionando?Qual e a qualidade do obtido ate agora?

Suporte e confianca (frequencia de repeticao do padrao)

Acuracia – quantos acertos das tentativas?

Precisao e recuperacao – ORI

Erro quadratico – erro em quantidade numerica

14/46

Avaliacao: medidas

Esta funcionando?Qual e a qualidade do obtido ate agora?

Suporte e confianca (frequencia de repeticao do padrao)

Acuracia – quantos acertos das tentativas?

Precisao e recuperacao – ORI

Erro quadratico – erro em quantidade numerica

Verossimilhanca – modelo obtido e provavel?

14/46

Avaliacao: medidas

Esta funcionando?Qual e a qualidade do obtido ate agora?

Suporte e confianca (frequencia de repeticao do padrao)

Acuracia – quantos acertos das tentativas?

Precisao e recuperacao – ORI

Erro quadratico – erro em quantidade numerica

Verossimilhanca – modelo obtido e provavel?

Probabilidade a posteriori – verossimilhanca + conhecimentoprevio

14/46

Avaliacao: medidas

Esta funcionando?Qual e a qualidade do obtido ate agora?

Suporte e confianca (frequencia de repeticao do padrao)

Acuracia – quantos acertos das tentativas?

Precisao e recuperacao – ORI

Erro quadratico – erro em quantidade numerica

Verossimilhanca – modelo obtido e provavel?

Probabilidade a posteriori – verossimilhanca + conhecimentoprevio

Custo/Utilidade – na pratica, custos diferentes para acertos eerros

14/46

Avaliacao: medidas

Esta funcionando?Qual e a qualidade do obtido ate agora?

Suporte e confianca (frequencia de repeticao do padrao)

Acuracia – quantos acertos das tentativas?

Precisao e recuperacao – ORI

Erro quadratico – erro em quantidade numerica

Verossimilhanca – modelo obtido e provavel?

Probabilidade a posteriori – verossimilhanca + conhecimentoprevio

Custo/Utilidade – na pratica, custos diferentes para acertos eerros

Margem – SVM: encontrar limite entre decisoes

14/46

Avaliacao: medidas

Esta funcionando?Qual e a qualidade do obtido ate agora?

Suporte e confianca (frequencia de repeticao do padrao)

Acuracia – quantos acertos das tentativas?

Precisao e recuperacao – ORI

Erro quadratico – erro em quantidade numerica

Verossimilhanca – modelo obtido e provavel?

Probabilidade a posteriori – verossimilhanca + conhecimentoprevio

Custo/Utilidade – na pratica, custos diferentes para acertos eerros

Margem – SVM: encontrar limite entre decisoes

Entropia – quantidade de informacao

14/46

Avaliacao: medidas

Esta funcionando?Qual e a qualidade do obtido ate agora?

Suporte e confianca (frequencia de repeticao do padrao)

Acuracia – quantos acertos das tentativas?

Precisao e recuperacao – ORI

Erro quadratico – erro em quantidade numerica

Verossimilhanca – modelo obtido e provavel?

Probabilidade a posteriori – verossimilhanca + conhecimentoprevio

Custo/Utilidade – na pratica, custos diferentes para acertos eerros

Margem – SVM: encontrar limite entre decisoes

Entropia – quantidade de informacao

Divergencia Kullback-Liebler – aumento relativo de informacao

14/46

Otimizacao

Como usar a linguagem para fazer funcionar?

Formas de busca de solucoes. Depende da linguagem e daavaliacao.

Otimizacao combinatorial Exemplo: busca greedy (gananciosa)

Otimizacao convexa Gradiente descendente – “qual e a melhor direcao”

Otimizacao com restricoes Programacao linear

15/46

Mineracao de dados e o processo de descoberta de

conhecimento

1. Entender o domınio, conhecimento a priori e objetivos Exemplo: projeto de novos remedios Duas pessoas: especialista no domınio e especialista em

mineracao

2. Coletar, integrar, selecionar, limpar e pre-processar dados Consumo da maior parte do tempo

3. Criacao de modelos de predicao, classificacao, agrupamentoou associacao

4. Interpretacao de resultados – caixa preta vs. branca

5. Consolidacao e uso do conhecimento descoberto

6. Iterar para melhorar aprendizado de maquina

16/46

Mineracao de dados na pratica: APIs

1. Busca de padroes (reducao de dimensionalidade)

Primeira opcao PCA, ouN > 10000 Isomap, Spectral embedding, LLEN < 10000 Kernel approximation

2. Identificacao de categorias Com dados rotulados (classificacao) Sem dados rotulados (agrupamento)

3. Predicao de quantidades (regressao)

4. Predicao de estruturas e sequencias Modelos baseados em grafos (HMM, Conditional Random

Fields) Modelos sequenciais: Perceptron estruturado

scikit-learn (Python) -http://scikit-learn.org/stable/tutorial/machine_learning_map/

Dlib C++ Library - http://dlib.net/ml_guide.svg

17/46

Princıpio de Bonferroni

Risco em mineracao de dados: torturar os dados ate elesconfessarem!

Princıpio de Bonferroni: descoberta de “padroes” semsignificado

Deve-se considerar um padrao como relevante se ele forsignificamente diferente do aleatorio

Experimentos de percepcao extra-sensorial de Rhine comcartas

18/46

Exercıcio mental

Objetivo: detectar terroristas que se encontram em hoteis

Metodo: listar pessoas que se hospedaram no mesmo hotelno mesmo dia pelo menos duas vezes

Detalhes: 109 pessoas em vigilancia durante 1000 dias Cada pessoa se hospeda em hotel por 10 dias Hoteis tem capacidade para 100 pessoas, ao todo, 105 hoteis

Pergunta: se todos sao aleatorios, quantos sao suspeitos?

19/46

Exercıcio mental: contas

Probabilidade de p e q estarem no mesmo hotel no dia d e10−9

P(p no hotel a) = 1/100, P(q no hotel b) = 1/100,P(a = b) = 1/(105)

Probabilidade p e q estarem no mesmo hotel nos dias d1 e d2e 10−18

Numero de pares de dias e(

10002

)

≈ 5× 105

Chance de p e q estarem no mesmo hotel em dois diasdurante o perıodo de 1000 dias

5× 105 × 10−18

Pares de pessoas ≈ 5× 1017

Numero esperado de pares de pessoas:5× 1017 × 5× 10−13 = 250000

Numero de suspeitos e 250000

Quer dizer que duas pessoas ficarem no mesmo dia erelativamente comum

20/46

Mineracao de grandes quantidades de dados: tempo

Sendo o tempo de um acesso a memoria principal 10−7s (10ns)

Tempo de acesso a memoria secundaria e 100 a 1000 vezesmais lento

Sendo que para cada elemento, faz-se um acesso

Custo

n itens ∼ n ∼ n log(n) ∼ n2

100 K 0.001s 0.005s 100s

1M 0.01s 0.06s 2.7 horas

100 M 1 s 8s 3.1 anos

100 G 20min 3 horas 0.015 ano galactico

Numeros de latencia por ano: http://www.eecs.berkeley.edu/~rcs/research/interactive_latency.html

21/46

Funcoes de complexidade

Funcao limitante superior Big-O O(n): limx→∞f (x)g(x) < ∞

Se f (n) ∈ O(g(n)), entao f (n) < cg(n) para algum c e x > a Se f ∈ O(g), entao crescimento f nao e maior que de g x2 ∈ O(x2), x2 ∈ O(x2 + x), x2 ∈ O(200x2)

Funcao limitante estritamente superior Little-O o(n) (mais

exigente): limx→∞f (x)g(x) = 0

Se f (n) ∈ o(g(n)), entao f (n) < cg(n) para todo c > 0 ex > a

Se f ∈ o(g), entao crescimento de f e estritamente menor queg

n2 ∈ o(x3), n2 /∈ o(n2)

Funcao limitante inferior Ω(n): limx→∞f (x)g(x) > 0

Funcao limitante estritamente inferior Ω(n):

limx→∞f (x)g(x) = ∞

Funcao limitante superior e inferior Θ(n): limx→∞f (x)g(x) ∈ ℜ+

22/46

Representacao de dados

Escalares, Vetores e Espacos Vetoriais Componentes pode ser chamados de: dimensoes,

caracterısticas, atributos ou features Componentes: numericos ou categoricos

Matrizes

Conjuntos e Sequencias

Variaveis aleatorias e Processos estocasticos

Arvores e Grafos

23/46

Vetores e Espacos vetoriais

Figura: Dataset Iris: xi = xi1, xi2, . . . , xid

24/46

Vetores e Espacos vetoriais

25/46

Vetores e Espacos vetoriais

26/46

Vetores e Espacos vetoriais

0 0.2

0.4 0.6

0.8 1 0

0.2 0.4

0.6 0.8

1

0

0.1

0.2

0.3

0.4

0.5

E[w]

w0

w1

E[w]

27/46

Matrizes

Marco Julio A Hamlet Otelo MacbethAntonio Cesar Tempestade

Antonio 157 73 0 0 0 1Brutus 4 157 0 2 0 0Cesar 232 227 0 2 1 0Calpurnia 0 10 0 0 0 0Cleopatra 57 0 0 0 0 0. . .

Cada documento e representado como vetor de contagem ∈ N|V |.

28/46

Matrizes

Marco Julio A Hamlet Otelo MacbethAntonio Cesar Tempestade

Antonio 157 73 0 0 0 1Brutus 4 157 0 2 0 0Cesar 232 227 0 2 1 0Calpurnia 0 10 0 0 0 0Cleopatra 57 0 0 0 0 0. . .

Cada documento e representado como vetor de contagem ∈ N|V |.

28/46

Conjuntos e sequencias

Um conjunto nao tem repeticoes C = 1, 2, 3, 4 = 1, 2, 4, 3

Uma sequencia tem ordem entre os elementosS = 1, 1, 2, 1, 1 6= 1, 2, 1, 1, 1

D A B C D E1 1 1 0 1 12 0 1 1 0 13 1 1 0 1 14 1 1 1 0 15 1 1 1 1 16 0 1 1 1 0

t i(t)

1 ABDE

2 BCE

3 ABDE

4 ABCE

5 ABCDE

6 BCD

x A B C D E

t(x) 1 1 2 1 13 2 4 3 24 3 5 5 35 4 6 6 4

5 56

Matriz binaria Conjuntos de itens Base vertical

29/46

Variaveis aleatorias e processos estocasticos

Variaveis aleatorias produzem amostras independentes dotempo

Variaveis aleatorias sao caracterizadas por funcoes deprobabilidade

P(Moeda = cara) = 0.5 P(Renda brasileira media em 2015 ≤ 2000) = 0.2

30/46

Variaveis aleatorias e processos estocasticos

Variaveis aleatorias produzem amostras independentes dotempo

Variaveis aleatorias sao caracterizadas por funcoes deprobabilidade

P(Moeda = cara) = 0.5 P(Renda brasileira media em 2015 ≤ 2000) = 0.2

Processos estocasticos produzem sequencias de amostrasindexadas com o tempo

Modelados como sequencias infinitas de variaveis aleatorias Series temporais

30/46

Variaveis aleatorias

Figura: Funcao de distribuicao de probabilidades de uma variavel normal31/46

Figura: Funcao de probabilidade cumulativa da distribuicao normal

f (x) = 1√

2πσ2exp

−(x−µ)2

2σ2

32/46

Figura: Funcao de probabilidade cumulativa da distribuicao normalbivariada

33/46

Grafos

OO

SS

OO

OO OO

HHHHHH

CC

HH

HH CC

OO

OO HH

CC

OO

OO OO

HH HH

NN

HH

HH HH

Amônia

Ácido carbônico

Ácido acéticoÁcido sulfúrico

Figura: Fonte: slides do livro “Practical Graph Mining With R”

34/46

Grafos

35/46

Grafos

Figura: Grafo inferido das distancias entre pontos do dataset Iris

36/46

Desafios computacionais em Mineracao de Dados

Tempo

Espaco

Modelo computacional Memoria principal Memoria secundaria (tempo de seek ≈ 0.01s) Dados sao obtidos em um fluxo contınuo

Exemplos de problemas

Como contar quais dois itens foram vendidos juntos em umsupermercado?

Como contar o numero de itens distintos em uma lista?

37/46

Problema da contagem dos itens distintos

Dada sequencia A = a1, . . . , an, onde ai ∈ 1 . . .m, contar onumero de elementos distintos em A.

Quantas palavras tem na web? Quantos clientes tem nessa lista de transacoes de bancarias?

Solucao depende do modelo computacional

38/46

Contagem dos itens distintos: modelo memoria principal

Algoritmo H Inicializar C = 0, um array B[1 . . .O(n)] e uma funcao hash

h : 1 . . .m → 1 . . .O(n) Para cada ai ∈ A:

Obter a hash j = h(ai ) Ver se ai esta na lista em B[j ] Se nao esta, incrementar contagem C = C + 1

Supondo que temos memoria suficiente, tempo e O(n)

39/46

Contagem dos itens distintos: modelo memoria secundaria

M unidades de memoria principal, sendo entrada de tamanhon, temos n >> M

Dados tem que ser armazenamos em disco Espaco em disco e organizado em blocos de tamanho B ≤ M

unidades Custo de acesso em disco e significativo (tempo de seek

> 0.00001s, media 0.004s a 0.015s) Operacoes em memoria principal sao negligıveis

Se usarmos o algoritmo anterior H, ele vai fazer Θ(n) acessos(inviavel, por que?)

40/46

Contagem dos itens distintos: modelo memoria secundaria

Algoritmo H2: Merge sort com M/B vias em memoriasecundaria

Separar elementos em M/B segmentos Ordenar recursivamente cada segmento Merge em M/B vias em O(n/B) tempo (acessos a disco)

n/B acessos

Recorrencia: T (N) = KT (nK ) + O(n/B)

Tempo de ordenacao O((n/B) logM/B n

Apos ordenar, e possıvel fazer contagem em uma passada: 1, 2, 2, 2, 4, 4, 5, 6, . . .

41/46

Modelo de fluxo contınuo de dados

Memoria secundaria tem M unidades e M << n

Dados sao produzidos continuamente: ai Problema: para resolver o problema de contagem precisamos

de Ω(n) de espaco!!!

42/46

Modelo de fluxo contınuo de dados

Memoria secundaria tem M unidades e M << n

Dados sao produzidos continuamente: ai Problema: para resolver o problema de contagem precisamos

de Ω(n) de espaco!!! Por contradicao. Assuma que precisamos apenas

M = f (n) ∈ o(n) no algoritmo F Pegar elementos S ⊂ 1 . . .m tal que n ≤ m Passar S para algoritmo F , sendo que estado de A no

momento e X Podemos verificar se i ∈ S , para todo i ∈ 1 . . .M

Passar i para F Numero de elementos distintos aumenta se, e so se, i ∈ S

Dessa forma, poderıamos verificar S a partir de X , entao onumero de diferentes estados X deve ser pelo menos 2m

42/46

O que veremos nesta disciplina

Classificacao

Agrupamento

Mineracao de itens e sequencias

Mineracao de grafos

Mineracao de grandes quantidades de dados

43/46

Comeco do trabalho 1

Procurar artigo de 2013 a 2015 sobre um problema demineracao de dados publicado em um veıculo Qualis A1

Qualis de periodicos: http://qualis.capes.gov.br Qualis de conferencias: link

Escrever um pequeno resumo contendo o seguinte: Porque o problema e interessante? Porque o artigo e interessante? Descreva 3 qualidades do artigo. Descreva 3 defeitos do artigo. Cite 2 artigos/referencias para algoritmos sobre o mesmo

problema.

Enviar resumo (em latex e PDF) por email albertini @ ufu br

44/46

Sugestoes de Conferencias e Periodicos

Journal of Machine Learning Research -http://www.jmlr.org

Machine Learning -http://link.springer.com/journal/10994

NIPS - http://papers.nips.cc

ICML - http://jmlr.org/proceedings/papers/v28/

SIGKDD -http://dl.acm.org/citation.cfm?id=2623330

SIGIR - http://dl.acm.org/citation.cfm?id=2600428

VLDB - http://dl.acm.org/citation.cfm?id=J1174

IJCAI - http://ijcai.org/papers15/contents.php

Best paper awards

http://jeffhuang.com/best_paper_awards.html

45/46

Referencias

Video lectures:http://videolectures.net/Top/Computer_Science/Data_Mining/

Data Science blogs:https://github.com/rushter/data-science-blogs

6.897 - Algorithms for Massive Data Sets, Piotr Indyk (MIT)

Machine Learning (CSE 446), Pedro Domingos (U.Washington)

46/46